Abstract
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.
Keywords
Interior point methodMathematicsConic optimizationMathematical optimizationSecond-order cone programmingConic sectionHessian matrixConvex optimizationRegular polygonNorm (philosophy)Convex analysisApplied mathematicsGeometry
Affiliated Institutions
Related Publications
Interior-Point Polynomial Algorithms in Convex Programming
Written for specialists working in optimization, mathematical programming, or control theory. The general theory of path-following and potential reduction interior point polynom...
An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
We present an O(√nL)-iteration homogeneous and self-dual linear programming (LP) algorithm. The algorithm possesses the following features: • It solves the linear programming pr...
Duality Results for Conic Convex Programming
textabstractThis paper presents a unified study of duality properties for the problem of minimizing a linear function over the intersection of an affine space with a convex cone...
A globally convergent primal-dual interior point method for constrained optimization
Abstract This paper proposes a primal-dual interior point method for solving general nonlinearly constrained optimization problems. The method is based on solving the Barrier Ka...
A Primal-Dual Interior-Point Method for Nonlinear Programming with Strong Global and Local Convergence Properties
An exact-penalty-function-based scheme---inspired from an old idea due to Mayne and Polak [Math. Program., 11 (1976), pp.67--80]---is proposed for extending to general smooth co...
Publication Info
- Year
- 1997
- Type
- article
- Volume
- 22
- Issue
- 1
- Pages
- 1-42
- Citations
- 607
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
607
OpenAlex
Cite This
Yu. E. Nesterov,
Michael J. Todd
(1997).
Self-Scaled Barriers and Interior-Point Methods for Convex Programming.
Mathematics of Operations Research
, 22
(1)
, 1-42.
https://doi.org/10.1287/moor.22.1.1
Identifiers
- DOI
- 10.1287/moor.22.1.1