Optimization Online


On the Riemannian Geometry Defined by Self-Concordant Barriers and Interior-Point Methods

Yu. E. Nesterov (nesterov***at***core.ucl.ac.be)
M. J. Todd (miketodd***at***cs.cornell.edu)

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.

Keywords: interior-point methods, Riemannian geometry, geodesics

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming

Citation: Foundations of Computational Mathematics 2 (2002), 333--361. Available electronically at http://www.orie.cornell.edu/~miketodd/todd.html


Entry Submitted: 08/08/2001
Entry Accepted: 08/09/2001
Entry Last Modified: 04/15/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society