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 pa ir of linear programming problems and an infeasible interior point. Th en we study the boundary; of the surface by analyzing limiting behavio r of paths on the surface and sequences in a neighborhood of the surfa ce. We introduce generic primal-dual infeasible-interior-point algorit hms in which the search direction is the Newton direction for a system defining a paint on the surface. We show that feasible-interior-point algorithms for artificial self-dual problems and for an artificial pr imal-dual pair of linear programming problems can be considered as spe cial cases of these infeasible-interior-point algorithms or simple var iants of them. In this sense, there are O(root nL)-iteration primal-du al infeasible-interior-point algorithms for linear programming.