2 INFEASIBLE INTERIOR-POINT PREDICTOR-CORRECTOR ALGORITHMS FOR LINEAR-PROGRAMMING

Two new infeasible interior-point predictor-corrector algorithms for l inear programming are proposed; one uses a Newton direction and the ot her uses a Euler direction for the predictor step. They require the so lutions of two linear systems at each iteration. The algorithms are gl obally convergent, and epsilon-feasibility and epsilon-complementarity can be obtained in O(nln(1/epsilon)) iterations with proper initializ ation. The first algorithm is also quadratically convergent under the assumption that an optimal solution exists.