APPROXIMATE FARKAS LEMMAS AND STOPPING RULES FOR ITERATIVE INFEASIBLE-POINT ALGORITHMS FOR LINEAR-PROGRAMMING

In exact arithmetic, the simplex method applied to a particular linear programming problem instance with real data either shows that it is i nfeasible, shows that its dual is infeasible, or generates optimal sol utions to both problems. Most interior-point methods, on the other han d, do not provide such clear-cut information. If the primal and dual p roblems have bounded nonempty sets of optimal solutions, they usually generate a sequence of primal or primal-dual iterates that approach fe asibility and optimality. But if the primal or dual instance is infeas ible, most methods give less precise diagnostics. There are methods wi th finite convergence to an exact solution even with real data. Unfort unately, bounds on the required number of iterations for such methods applied to instances with real data are very hard to calculate and oft en quite large. Our concern is with obtaining information from inexact solutions after a moderate number of iterations. We provide general t ools (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 homogeneous self-dual algorithm and for a generic infeasible-interior-point method for line ar programming. These rules allow precise conclusions to be drawn abou t the linear programming problem and its dual: either near-optimal sol utions are produced, or we obtain ''certificates'' that all optimal so lutions, or all feasible solutions to the primal or dual, must have la rge norm. Our rules thus allow more definitive interpretation of the o utput 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 p rogramming. (C) 1998 The Mathematical Programming Society, Inc. Publis hed by Elsevier Science B.V.