Simple algorithms for optimization on Riemannian manifolds with constraints
From MaRDI portal
Publication:2019906
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.
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
Cites work
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 3914081 (Why is no real title available?)
- scientific article; zbMATH DE number 46303 (Why is no real title available?)
- scientific article; zbMATH DE number 52737 (Why is no real title available?)
- scientific article; zbMATH DE number 5223994 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- scientific article; zbMATH DE number 5066287 (Why is no real title available?)
- A Broyden class of quasi-Newton methods for Riemannian optimization
- A collection of nonsmooth Riemannian optimization problems
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- A note on the convergence of barrier algorithms to second-order necessary points
- A parallel Douglas-Rachford algorithm for minimizing ROF-like functionals on images with values in symmetric Hadamard manifolds
- A second-order sequential optimality condition associated to the convergence of optimization algorithms
- An example comparing the standard and safeguarded augmented Lagrangian methods
- Augmented Lagrangians with constrained subproblems and convergence to second-order stationary points
- Benchmarking optimization software with performance profiles.
- Generalized gradients and characterization of epi-Lipschitz sets in Riemannian manifolds
- Global minimization using an augmented Lagrangian method with variable lower-level constraints
- Global rates of convergence for nonconvex optimization on manifolds
- Intrinsic formulation of KKT conditions and constraint qualifications on smooth manifolds
- Iteration-complexity of gradient, subgradient and proximal point methods on Riemannian manifolds
- Line search algorithms for locally Lipschitz functions on Riemannian manifolds
- Manopt, a Matlab toolbox for optimization on manifolds
- Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
- Nonlinear optimization.
- On Augmented Lagrangian Methods with General Lower-Level Constraints
- On Smoothing Exact Penalty Functions for Convex Constrained Optimization
- On consistency and sparsity for principal components analysis in high dimensions
- On sequential optimality conditions for smooth constrained optimization
- Optimality conditions for the nonlinear programming problems on Riemannian manifolds
- Practical augmented Lagrangian methods for constrained optimization
- Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis
- Pymanopt: a Python toolbox for optimization on manifolds using automatic differentiation
- ROPTLIB: An object-oriented C++ library for optimization on Riemannian manifolds
- Robust low-rank matrix completion by Riemannian optimization
- Second-order optimality conditions for mathematical programs with equilibrium constraints
- Smoothing methods for convex inequalities and linear complementarity problems
- Statistical mechanics of complex networks
- \(\varepsilon\)-subgradient algorithms for locally Lipschitz functions on Riemannian manifolds
Cited in
(40)- First- and second-order analysis for optimization problems with manifold-valued constraints
- Riemannian optimization via Frank-Wolfe methods
- Dissolving Constraints for Riemannian Optimization
- Completely positive factorization by a Riemannian smoothing method
- Sequential optimality conditions for nonlinear optimization on Riemannian manifolds and a globally convergent augmented Lagrangian method
- Memoryless quasi-Newton methods based on the spectral-scaling Broyden family for Riemannian optimization
- Emergent behaviors of high-dimensional Kuramoto models on Stiefel manifolds
- Adaptive regularization with cubics on manifolds
- Riemannian Interior Point Methods for Constrained Optimization on Manifolds
- An exact penalty approach for optimization with nonnegative orthogonality constraints
- Riemannian proximal gradient methods
- Globally convergent optimization algorithms on Riemannian manifolds: Uniform framework for unconstrained and constrained optimization
- Numerical approaches for constrained and unconstrained, static optimization on the special Euclidean group \(\mathsf{SE}(3)\)
- Linear Programming on the Stiefel Manifold
- Sion’s Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm
- Mini-workshop: Computational optimization on manifolds. Abstracts from the mini-workshop held November 15--21, 2020 (online meeting)
- Optimality conditions and duality for multiobjective semi-infinite programming on Hadamard manifolds
- Proximal gradient method for nonconvex and nonsmooth optimization on Hadamard manifolds
- Accelerated optimization on Riemannian manifolds via discrete constrained variational integrators
- 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
- Practical gradient and conjugate gradient methods on flag manifolds
- Riemannian conjugate gradient methods: general framework and specific algorithms with convergence analyses
- Distance-preserving manifold denoising for data-driven mechanics
- Fenchel Duality and a Separation Theorem on Hadamard Manifolds
- Stochastic augmented Lagrangian method in Riemannian shape manifolds
- Stitching data: recovering a manifold's geometry from geodesic intersections
- scientific article; zbMATH DE number 836715 (Why is no real title available?)
- A Riemannian Newton trust-region method for fitting Gaussian mixture models
- Fenchel duality theory and a primal-dual algorithm on Riemannian manifolds
- A framework of constraint preserving update schemes for optimization on Stiefel manifold
- An SQP method for equality constrained optimization on Hilbert manifolds
- Dimensional reduction in constrained global optimization on smooth manifolds
- Slow and finite-time relaxations to \(m\)-bipartite consensus on the Stiefel manifold
- Riemannian optimization on unit sphere with \(p\)-norm and its applications
- Efficient Weingarten map and curvature estimation on manifolds
- Sequential quadratic optimization for nonlinear optimization problems on Riemannian manifolds
- Continuation methods for Riemannian optimization
- An interior proximal gradient method for nonconvex optimization
- Solving graph equipartition SDPs on an algebraic variety
Describes a project that uses
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)
