Source-linked AI summary
Manopt, a Matlab toolbox for optimization on manifolds
Nicolas Boumal, Bamdev Mishra, P. -A. Absil, Rodolphe Sepulchre
TL;DR
Structured optimization problems with rank and orthogonality constraints motivate methods that exploit manifold geometry. The paper presents Manopt, a user-friendly toolbox that combines reusable manifolds and Riemannian solvers for experimentation. Its examples include low-rank and fixed-rank formulations, including a max-cut workflow that increases rank to obtain a global solution of the max-cut semidefinite program and a formal upperbound.
Problem
Optimization on manifolds addresses nonlinear optimization problems whose search spaces have smooth geometry and structured rank or orthogonality constraints.
Method
Manopt provides reusable manifold representations, Riemannian optimization ingredients, and generic solvers for experimenting with these algorithms.
Results
Manopt supports fixed-rank manifold optimization, including a max-cut implementation that gradually increases rank to obtain a global solution of the max-cut SDP and a formal upperbound.
Takeaways & Limitations
Manopt simplifies experimentation with Riemannian optimization across applications involving rank, orthogonality, and other structured manifolds.
Abstract
from arXiv · showhide
Optimization on manifolds is a rapidly developing branch of nonlinear optimization. Its focus is on problems where the smooth geometry of the search space can be leveraged to design efficient numerical algorithms. In particular, optimization on manifolds is well-suited to deal with rank and orthogonality constraints. Such structured constraints appear pervasively in machine learning applications, including low-rank matrix completion, sensor network localization, camera network registration, independent component analysis, metric learning, dimensionality reduction and so on. The Manopt toolbox, available at www.manopt.org, is a user-friendly, documented piece of software dedicated to simplify experimenting with state of the art Riemannian optimization algorithms. We aim particularly at reaching practitioners outside our field.
1 Introduction
Riemannian optimization uses manifold geometry to formulate efficient algorithms for structured search spaces, including rank- and orthogonality-constrained problems. Manopt packages this theory into a user-friendly toolbox for experimentation.
- Foundations: Riemannian optimization equips smooth search spaces with tangent spaces and smoothly varying inner products, enabling geometric optimization methods.Retractions move from a manifold point along a tangent direction, supporting algorithmic updates.
- Application spaces: Manifold geometry supports applications involving orthogonality, rank, rotations, and related structured constraints.Examples include oblique, Stiefel, Grassmann, fixed-rank, and rotation-matrix manifolds.
- Application spaces: Fixed-rank positive semidefinite manifolds support low-rank algorithms for metric learning and Euclidean distance matrix completion.The fixed-rank spectrahedron is also used for relaxed sparse PCA formulations.
- Algorithms: Riemannian gradients, Hessians, and retractions generalize gradient descent, conjugate-gradients, quasi-Newton, and trust-region methods.The framework provides first- and second-order algorithms whose convergence guarantees essentially match those of their Euclidean counterparts.
- Manopt: Manopt was built as user-friendly software that helps researchers and practitioners experiment with Riemannian optimization tools.The toolbox code and documentation are available at www.manopt.org.
2 Architecture and features of Manopt
Manopt separates manifolds, solvers, and problem descriptions so users can assemble optimization problems from reusable components. Supporting utilities provide derivative checks, solver instrumentation, extensibility, and optional caching.
- Architecture: Manopt separates manifold definitions, solver implementations, and problem descriptions into distinct components.Basic use requires selecting a manifold, specifying the cost function and possible derivatives, and passing them to a solver.
- Manifolds: Manifold factories provide tangent-space projections, retractions, and conversions from Euclidean to Riemannian derivatives.Cartesian products of known manifolds are supported, and additional manifold types can be added.
- Solvers: Available solvers include trust-regions, conjugate-gradients with preconditioning, steepest-descent, and derivative-free schemes.Solvers log standard iteration information, support callbacks, and allow user-defined stopping criteria.
- Problem descriptions: Problem structures store a manifold description, the cost function, and optional derivatives behind an abstraction layer.The interface can be updated as new function descriptions such as subdifferentials or partial gradients are needed.
- Utilities: Optional caching reuses intermediate results from cost evaluations when computing derivatives, reducing redundant computations.This is useful when moving from a proof-of-concept algorithm to a convincing implementation.
3 Example: the maximum cut problem
The maximum-cut problem is formulated as a rank-constrained matrix optimization problem, then relaxed to a fixed-rank elliptope that Manopt can optimize with Riemannian methods.
- Given a weighted graph, max-cut seeks a binary node partition maximizing the total weight of edges crossing the two classes.
- Representing the partition by X = ss⊤ makes max-cut a positive-semidefinite, unit-diagonal, rank-one matrix problem.
- Dropping the rank constraint gives a semidefinite relaxation, while fixing rank(X) = r produces the smooth fixed-rank elliptope.
- Manopt encodes the elliptope with a manifold factory and supplies the cost, Euclidean gradient, and Euclidean Hessian for Riemannian optimization.
- Gradient and Hessian diagnostics can be run before minimizing with trust-regions from a random initial guess.
- Randomly projecting the optimized factor Y yields a cut, while caching and gradually increasing r support a global solution of the max-cut SDP and a formal upperbound.