SELF-SCALED BARRIERS AND INTERIOR-POINT METHODS FOR CONVEX-PROGRAMMING

This paper provides a theoretical foundation for efficient interior-po int algorithms for convex programming problems expressed in conic form , when the cone and its associated barrier are self-scaled. For such p roblems 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 b oundary of the feasible region, rather than being confined to a ball o f unit radius in the local norm defined by the Hessian of the barrier.