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

Yu. E. Nesterov (nesterovcore.ucl.ac.be)
M. J. Todd (miketoddcs.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

Download:

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

Modify/Update this entry