Primal-Dual Interior-Point Methods for Self-Scaled Cones

Yu.E. Nesterov and M.J. Todd

In this paper we continue the development of a theoretical foundation for efficient primal-dual interior-point algorithms for convex programming problems expressed in conic form, when the cone and its associated barrier are self-scaled (see (Nesterov and Todd 1994). The class of problems under consideration includes linear programming, semidefinite programming and quadratically constrained quadratic programming problems.

For such problems we introduce a new definition of affine-scaling and centering directions. We present efficiency estimates for several symmetric primal-dual methods that can loosely be classified as path-following methods. Because of the special properties of these cones and barriers, two of our algorithms can take steps that go typically a large fraction of the way to the boundary of the feasible region, rather than being confined to a ball of unit radius in the local norm defined by the Hessian of the barrier.

Technical Report No. 1125, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY 14853-3801.

(Revised August, 1995.)

[POSTSCRIPT] [IP PAGE] [SEARCH AGAIN]