PRIMAL-DUAL INTERIOR-POINT METHODS FOR SELF-SCALED CONES

In this paper we continue the development of a theoretical foundation for efficient primal-dual interior-point algorithms for convex program ming problems expressed in conic form, when the cone and its associate d barrier are self-scaled (see Yu. E. Nesterov and M.J. Todd, Math. Op er. Res., 22 (1997), pp. 1-42). The class of problems under considerat ion includes linear programming, semidefinite programming, and convex quadratically constrained, quadratic programming problems. For such pr oblems we introduce a new definition of affine-scaling and centering d irections. We present efficiency estimates for several symmetric prima l-dual methods that can loosely be classified as path-following method s. Because of the special properties of these cones and barriers, two of our algorithms can take steps that typically go a large fraction of the way to the boundary of the feasible region, rather than being con fined to a ball of unit radius in the local norm defined by the Hessia n of the barrier.