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