Self-scaled barriers and interior-point methods for convex programming. (English) Zbl 0871.90064

Summary: 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.


90C25 Convex programming
90C05 Linear programming
65Y20 Complexity and performance of numerical algorithms
Full Text: DOI Link