Simple algorithms for optimization on Riemannian manifolds with constraints
From MaRDI portal
Publication:2019906
DOI10.1007/S00245-019-09564-3zbMATH Open1468.65072arXiv1901.10000OpenAlexW2963704853WikidataQ115388211 ScholiaQ115388211MaRDI QIDQ2019906FDOQ2019906
Authors: Changshuo Liu, Nicolas Boumal 
Publication date: 22 April 2021
Published in: Applied Mathematics and Optimization (Search for Journal in Brave)
Abstract: 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 -means, especially in high dimensions.
Full work available at URL: https://arxiv.org/abs/1901.10000
Recommendations
- Sequential quadratic optimization for nonlinear optimization problems on Riemannian manifolds
- Riemannian optimization and its applications
- Accelerated optimization on Riemannian manifolds via discrete constrained variational integrators
- scientific article; zbMATH DE number 5267064
- Globally convergent optimization algorithms on Riemannian manifolds: Uniform framework for unconstrained and constrained optimization
constrained optimizationnonsmooth optimizationaugmented Lagrangian methoddifferential geometryRiemannian optimizationexact penalty method
Numerical mathematical programming methods (65K05) Nonlinear programming (90C30) Classical differential geometry (53A99)
Cites Work
- Title not available (Why is that?)
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- Practical augmented Lagrangian methods for constrained optimization
- Pymanopt: a Python toolbox for optimization on manifolds using automatic differentiation
- Manopt, a Matlab toolbox for optimization on manifolds
- ROPTLIB: An object-oriented C++ library for optimization on Riemannian manifolds
- Statistical mechanics of complex networks
- Title not available (Why is that?)
- Benchmarking optimization software with performance profiles.
- On consistency and sparsity for principal components analysis in high dimensions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Global minimization using an augmented Lagrangian method with variable lower-level constraints
- Title not available (Why is that?)
- Nonlinear optimization.
- On Augmented Lagrangian Methods with General Lower-Level Constraints
- \(\varepsilon\)-subgradient algorithms for locally Lipschitz functions on Riemannian manifolds
- Generalized gradients and characterization of epi-Lipschitz sets in Riemannian manifolds
- A Broyden class of quasi-Newton methods for Riemannian optimization
- On Smoothing Exact Penalty Functions for Convex Constrained Optimization
- On sequential optimality conditions for smooth constrained optimization
- Smoothing methods for convex inequalities and linear complementarity problems
- Second-order optimality conditions for mathematical programs with equilibrium constraints
- A note on the convergence of barrier algorithms to second-order necessary points
- A collection of nonsmooth Riemannian optimization problems
- Optimality conditions for the nonlinear programming problems on Riemannian manifolds
- Iteration-complexity of gradient, subgradient and proximal point methods on Riemannian manifolds
- An example comparing the standard and safeguarded augmented Lagrangian methods
- A second-order sequential optimality condition associated to the convergence of optimization algorithms
- Augmented Lagrangians with constrained subproblems and convergence to second-order stationary points
- Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis
- Global rates of convergence for nonconvex optimization on manifolds
- Robust low-rank matrix completion by Riemannian optimization
- A parallel Douglas-Rachford algorithm for minimizing ROF-like functionals on images with values in symmetric Hadamard manifolds
- Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
- Line search algorithms for locally Lipschitz functions on Riemannian manifolds
- Intrinsic formulation of KKT conditions and constraint qualifications on smooth manifolds
Cited In (40)
- Riemannian proximal gradient methods
- Mini-workshop: Computational optimization on manifolds. Abstracts from the mini-workshop held November 15--21, 2020 (online meeting)
- Dissolving Constraints for Riemannian Optimization
- Sequential optimality conditions for nonlinear optimization on Riemannian manifolds and a globally convergent augmented Lagrangian method
- An interior proximal gradient method for nonconvex optimization
- Numerical approaches for constrained and unconstrained, static optimization on the special Euclidean group \(\mathsf{SE}(3)\)
- Efficient Weingarten map and curvature estimation on manifolds
- Completely positive factorization by a Riemannian smoothing method
- An exact penalty approach for optimization with nonnegative orthogonality constraints
- Accelerated optimization on Riemannian manifolds via discrete constrained variational integrators
- Slow and finite-time relaxations to \(m\)-bipartite consensus on the Stiefel manifold
- Continuation methods for Riemannian optimization
- Fenchel conjugate via Busemann function on Hadamard manifolds
- Riemannian smoothing gradient type algorithms for nonsmooth optimization problem on compact Riemannian submanifold embedded in Euclidean space
- Adaptive regularization with cubics on manifolds
- A framework of constraint preserving update schemes for optimization on Stiefel manifold
- Riemannian conjugate gradient methods: general framework and specific algorithms with convergence analyses
- Fenchel Duality and a Separation Theorem on Hadamard Manifolds
- Memoryless quasi-Newton methods based on the spectral-scaling Broyden family for Riemannian optimization
- Title not available (Why is that?)
- Sion’s Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm
- Globally convergent optimization algorithms on Riemannian manifolds: Uniform framework for unconstrained and constrained optimization
- Linear Programming on the Stiefel Manifold
- Stochastic augmented Lagrangian method in Riemannian shape manifolds
- Distance-preserving manifold denoising for data-driven mechanics
- A Riemannian Newton trust-region method for fitting Gaussian mixture models
- Fenchel duality theory and a primal-dual algorithm on Riemannian manifolds
- Riemannian Interior Point Methods for Constrained Optimization on Manifolds
- Stitching data: recovering a manifold's geometry from geodesic intersections
- Emergent behaviors of high-dimensional Kuramoto models on Stiefel manifolds
- Optimality conditions and duality for multiobjective semi-infinite programming on Hadamard manifolds
- Proximal gradient method for nonconvex and nonsmooth optimization on Hadamard manifolds
- Riemannian optimization on unit sphere with \(p\)-norm and its applications
- Practical gradient and conjugate gradient methods on flag manifolds
- An SQP method for equality constrained optimization on Hilbert manifolds
- Sequential quadratic optimization for nonlinear optimization problems on Riemannian manifolds
- Solving graph equipartition SDPs on an algebraic variety
- Riemannian optimization via Frank-Wolfe methods
- First- and second-order analysis for optimization problems with manifold-valued constraints
- Dimensional reduction in constrained global optimization on smooth manifolds
Uses Software
This page was built for publication: Simple algorithms for optimization on Riemannian manifolds with constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2019906)
