Interior-point methods on manifolds: theory and applications

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 then analyze a short-step 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 show that on the positive-definite matrices and other symmetric spaces, the squared distance to a point is a self-concordant function. Our work is motivated by recent progress on scaling problems and non-commutative optimization, and we show that these fit into our framework, yielding algorithms with state-of-the-art complexity guarantees. Furthermore, we show how to apply our methods to computing geometric medians on spaces with constant negative curvature.