Nesterov, Yu. E.; Todd, M. J. Primal-dual interior-point methods for self-scaled cones. (English) Zbl 0922.90110 SIAM J. Optim. 8, No. 2, 324-364 (1998). 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. Cited in 3 ReviewsCited in 211 Documents MSC: 90C25 Convex programming 65Y20 Complexity and performance of numerical algorithms 90C05 Linear programming Keywords:convex programming; conical form; interior-point algorithms; self-concordant barrier; self-scaled cone; self-scaled barrier; path-following algorithms; symmetric primal-dual algorithms Citations:Zbl 0871.90064 PDFBibTeX XMLCite \textit{Yu. E. Nesterov} and \textit{M. J. Todd}, SIAM J. Optim. 8, No. 2, 324--364 (1998; Zbl 0922.90110) Full Text: DOI