INFEASIBLE-INTERIOR-POINT PRIMAL-DUAL POTENTIAL-REDUCTION ALGORITHMS FOR LINEAR-PROGRAMMING

In this paper, primal-dual potential-reduction algorithms are proposed that can start from an infeasible interior point. The authors first d escribe two such algorithms and show that both are polynomial-time bou nded. One of the algorithms decreases the Tanabe-Todd-Ye primal-dual p otential function by a constant at each iteration under the condition that the duality gap decreases by at most the same ratio as the infeas ibility. The other algorithm reduces a new potential function, which h as one more term in the Tanabe-Todd-Ye potential function, by a fixed constant at each iteration without any other conditions on the step si ze. Finally, modifications of these methods are described (incorporati ng centering steps) that dramatically decreases their computational co mplexity. The algorithms also extend to the case of monotone linear co mplementarity problems.