A Surface of Analytic Centers and Primal-Dual Infeasible-Interior-Point Algorithms for Linear Programming

We define a surface of analytic centers determined by a primal-dual pair of linear programming problems and an infeasible interior point. Then we study the boundary of the surface by analyzing limiting behavior of paths on the surface and sequences in a neighborhood of the surface. We introduce generic primal-dual infeasible-interior-point algorithms in which the search direction is the Newton direction for a system defining a point on the surface. We show that feasible-interior-point algorithms for artificial self-dual problems and for an artificial primal-dual pair of linear programming problems can he considered as special cases of these infeasible-interior-point algorithms or simple variants of them. In this sense, there are O(√nL)-iteration primal-dual infeasible-interior-point algorithms for linear programming.