On the Riemannian geometry defined by self-concordant barriers and interior-point methods
(2002) Foundations of Computational Mathematics — Vol. 2, n° 4, p. 333-361 (2002)
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- We consider the Riemannian geometry defined on a convex set by the Hessian of a self-concordant barrier function, and its associated geodesic curves. These provide guidance for the construction of efficient interior-point methods for optimizing a linear function over the intersection of the set with an affine manifold. We show that algorithms that follow the primal-dual central path are in some sense close to optimal. The same is true for methods that follow the shifted primal-dual central path among certain infeasible-interior-point methods. We also compute the geodesics in several simple sets.
- Affiliations
Cornell University Ithaca Industrial Engineering
Citations
Nesterov, Y., & Todd, M. (2002). On the Riemannian geometry defined by self-concordant barriers and interior-point methods. Foundations of Computational Mathematics, 2(4), 333-361. https://doi.org/10.1007/s102080010032 (Original work published 2002)