Interior-point methods on manifolds: theory and applications
arXiv:2303.04771 · doi:10.1109/FOCS57990.2023.00123
Abstract
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.
arXiv comment85 pages. v2: Merged with independent work arXiv:2212.10981 by Hiroshi Hirai
References in corpus (16)
- Entanglement Polytopes: Multiparticle Entanglement from Single-Particle Information
- Conic geometric optimisation on the manifold of positive definite matrices
- Newton Method on Riemannian Manifolds: Covariant Alpha-Theory
- Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes
- On vanishing of Kronecker coefficients
- Riemannian Median and Its Estimation
- On Approximating the Riemannian 1-Center
- Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
- Solving Linear Programs with Sqrt(rank) Linear System Solves
- Invariant theory and scaling algorithms for maximum likelihood estimation
- A Schwarz lemma for Kähler affine metrics and the canonical potential of a proper convex cone
- Membership in moment polytopes is in NP and coNP
- The minimal canonical form of a tensor network
- Interior-point methods on manifolds: theory and applications
- Toric invariant theory for maximum likelihood estimation in log-linear models
- Sufficient conditions for non-asymptotic convergence of Riemannian optimisation methods