##
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.)