  Interior-point methods offer a highly versatile framework for convex
optimization that is effective in theory and practice. A key notion in their
theory is that of a self-concordant barrier. We give a suitable generalization
of self-concordance to Riemannian manifolds and show that it gives the same
structural results and guarantees as in the Euclidean setting, in particular
local quadratic convergence of Newton's method. We analyze a path-following
method for optimizing compatible objectives over a convex domain for which one
has a self-concordant barrier, and obtain the standard complexity guarantees as
in the Euclidean setting. We provide general constructions of barriers, and
show that on the space of positive-definite matrices and other symmetric
spaces, the squared distance to a point is self-concordant. To demonstrate the
versatility of our framework, we give algorithms with state-of-the-art
complexity guarantees for the general class of scaling and non-commutative
optimization problems, which have been of much recent interest, and we provide
the first algorithms for efficiently finding high-precision solutions for
computing minimal enclosing balls and geometric medians in nonpositive
curvature.
