Self-Scaled Barriers and Interior-Point Methods for Convex Programming

Abstract

This paper provides a theoretical foundation for efficient interior-point algorithms for convex programming problems expressed in conic form, when the cone and its associated barrier are self-scaled. For such problems we devise long-step and symmetric primal-dual methods. Because of the special properties of these cones and barriers, 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.