Motzkin.m

[solution] = Motzkin(A,b,C,d,lambda,error)

An implementation of the Agmon, Motzkin, and Schoenberg relaxation method. Given a system Ax = b, Cx <= d, this returns a error-feasible solution.  That is, it returns a solution satisfying b - error <= Ax <= b + error, Cx <= d + error.  Each iteration projects to the maximally violated constraint, taking into account the under-/over-shooting specified by the input lambda.

As in most implementations of the Motzkin relaxation algorithm, we first transform the problem Ax = b, Cx <= d, into the equivalent problem b <= Ax <= b, Cx <=d.  We can then combine all the constraints into one matrix inequality, C'x <= d', and then proceed with the relaxation algorithm.  It is best ot run this algorithm on problems that are known to be feasible.  Otherwise the algorithm will cycle until the time-out limit is hit.  If the time-out limit is reached, the function returns x = 0.

INPUT:		A = matrix of equality constraints
		b = right-hand side of equality constraints
		C = matrix of inequality (<=) constraints
		d = right-hand side of inequality (<=) constraints
		lambda = under-/over-shooting parameter (e.g. lambda = 1 is regular projection, lambda > 1 projects beyond the constraint, lambda < 1 projects short of the constraint
		error = parameter that sets the acceptable approximation error

OUTPUT:		solution = error-approximate solution if one is found in the time limit; otherwise this is set to the scalar 0