Primal-dual interior-point methods for self-scaled cones. (English) Zbl 0922.90110

Summary: 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 Yu. E. Nesterov and M. J. Todd, Math. Oper. Res. 22, 1-42 (1997; Zbl 0871.90064)]. The class of problems under consideration includes linear programming, semidefinite programming, and convex 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 typically go 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
65Y20 Complexity and performance of numerical algorithms
90C05 Linear programming


Zbl 0871.90064
Full Text: DOI