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

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.