TY - JOUR
T1 - Simple Algorithms for Optimization on Riemannian Manifolds with Constraints
AU - Liu, Changshuo
AU - Boumal, Nicolas
N1 - Funding Information:
We thank an anonymous reviewer for detailed and helpful comments on the first version of this paper. NB is partially supported by NSF grant DMS-1719558.
Publisher Copyright:
© 2019, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2020/12/1
Y1 - 2020/12/1
N2 - We consider optimization problems on manifolds with equality and inequality constraints. A large body of work treats constrained optimization in Euclidean spaces. In this work, we consider extensions of existing algorithms from the Euclidean case to the Riemannian case. Thus, the variable lives on a known smooth manifold and is further constrained. In doing so, we exploit the growing literature on unconstrained Riemannian optimization. For the special case where the manifold is itself described by equality constraints, one could in principle treat the whole problem as a constrained problem in a Euclidean space. The main hypothesis we test here is whether it is sometimes better to exploit the geometry of the constraints, even if only for a subset of them. Specifically, this paper extends an augmented Lagrangian method and smoothed versions of an exact penalty method to the Riemannian case, together with some fundamental convergence results. Numerical experiments indicate some gains in computational efficiency and accuracy in some regimes for minimum balanced cut, non-negative PCA and k-means, especially in high dimensions.
AB - We consider optimization problems on manifolds with equality and inequality constraints. A large body of work treats constrained optimization in Euclidean spaces. In this work, we consider extensions of existing algorithms from the Euclidean case to the Riemannian case. Thus, the variable lives on a known smooth manifold and is further constrained. In doing so, we exploit the growing literature on unconstrained Riemannian optimization. For the special case where the manifold is itself described by equality constraints, one could in principle treat the whole problem as a constrained problem in a Euclidean space. The main hypothesis we test here is whether it is sometimes better to exploit the geometry of the constraints, even if only for a subset of them. Specifically, this paper extends an augmented Lagrangian method and smoothed versions of an exact penalty method to the Riemannian case, together with some fundamental convergence results. Numerical experiments indicate some gains in computational efficiency and accuracy in some regimes for minimum balanced cut, non-negative PCA and k-means, especially in high dimensions.
KW - Augmented Lagrangian method
KW - Constrained optimization
KW - Differential geometry
KW - Exact penalty method
KW - Nonsmooth optimization
KW - Riemannian optimization
UR - http://www.scopus.com/inward/record.url?scp=85064085605&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85064085605&partnerID=8YFLogxK
U2 - 10.1007/s00245-019-09564-3
DO - 10.1007/s00245-019-09564-3
M3 - Article
AN - SCOPUS:85064085605
SN - 0095-4616
VL - 82
SP - 949
EP - 981
JO - Applied Mathematics and Optimization
JF - Applied Mathematics and Optimization
IS - 3
ER -