Approximate Farkas Lemmas and Stopping Rules for Iterative Infeasible-Point Algorithms for Linear Programming

Todd, M. J. and Ye, Y.

In exact arithmetic, the simplex method applied to a particular linear programming problem instance either shows that it is infeasible, shows that its dual is infeasible, or generates optimal solutions to both problems. Interior-point methods do not provide such clear-cut information. We provide general tools (extensions of the Farkas Lemma) for concluding that a problem or its dual is likely (in a certain well-defined sense) to be infeasible, and apply them to develop stopping rules for a generic infeasible-interior-point method and for the homogeneous self-dual algorithm for linear programming. These rules allow precise conclusions to be drawn about the linear programming problem and its dual: either near-optimal solutions are produced, or we obtain ``certificates'' that all optimal solutions, or all feasible solutions to the primal or dual, must have large norm. Our rules thus allow more definitive interpretation of the output of such an algorithm than previous termination criteria. We give bounds on the number of iterations required before these rules apply. Our tools may also be useful for other iterative methods for linear programming.

Technical Report No. 1109, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY 14853-3801