A nonlinear equation for linear programming

Research paper by P. W. Smith, H. Wolkowicz

Indexed on: 01 Mar '86Published on: 01 Mar '86Published in: Mathematical Programming


We present a characterization of the ‘normal’ optimal solution of the linear program given in canonical form max{ctx: 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 − Atλr)+. Thus, we can findx* by solving the following equation forλr A(rc − Atλr)+ = b. Moreover,(1/r)λr then ‘converges’ to a solution of the dual program.