A nonlinear equation for linear programming

We present a characterization of the normal optimal solution of the linear program given in canonical form max{c^tx: Ax = b, x 0}. (P) We show thatx^* is the optimal solution of (P), of minimal norm, if and only if there exists anR > 0 such that, for eachr R, we havex^* = (rc – A^t_r)₊. Thus, we can findx^* by solving the following equation for_r A(rc – A^t_r)₊ = b. Moreover,(1/r)_r then converges to a solution of the dual program.On leave from The University of Alberta, Edmonton, Canada. Research partially supported by the National Science and Engineering Research Council of Canada.