×

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.

MSC:

90C25 Convex programming
65Y20 Complexity and performance of numerical algorithms
90C05 Linear programming

Citations:

Zbl 0871.90064
PDFBibTeX XMLCite
Full Text: DOI