Available solvers in Manopt.jl

Optimization problems can be classified with respect to several criteria. The following list of the algorithms is grouped with respect to the “information” available about an optimization problem

\[\operatorname*{arg\,min}_{p∈\mathcal M} f(p)\]

Within each group, short notes on advantages of the individual solvers, and required properties the cost $f$ should have, are provided. In that list a 🏅 is used to indicate state-of-the-art solvers that usually perform best in their corresponding group, and 🫏 for a maybe not so fast, maybe not so state-of-the-art method that nevertheless gets the job done most reliably.

Derivative free

For derivative free solvers only function evaluations of $f$ are used.

• Nelder-Mead a simplex based variant, that is using $d+1$ points, where $d$ is the dimension of the manifold.
• Particle Swarm 🫏 uses the evolution of a set of points, called swarm, to explore the domain of the cost and find a minimizer.
• Mesh adaptive direct search performs a mesh based exploration (poll) and search.
• CMA-ES uses a stochastic evolutionary strategy to perform minimization robust to local minima of the objective.

First order

Gradient

• Gradient Descent uses the gradient from $f$ to determine a descent direction. Here, the direction can also be changed to be averaged, momentum-based, or based on Nesterov's rule.
• Conjugate Gradient Descent uses information from the previous descent direction to improve the current (gradient-based) one including several such update rules.
• The Quasi-Newton Method 🏅 uses gradient evaluations to approximate the Hessian, which is then used in a Newton-like scheme, where both a limited memory and a full Hessian approximation are available with several different update rules.
• Steihaug-Toint Truncated Conjugate-Gradient Method a solver for a constrained problem defined on a tangent space.

Subgradient

The following methods require the Riemannian subgradient $∂f$ to be available. While the subgradient might be set-valued, the function should provide one of the subgradients.

• The Subgradient Method takes the negative subgradient as a step direction and can be combined with a step size.
• The Convex Bundle Method (CBM) uses a former collection of sub gradients at the previous iterates and iterate candidates to solve a local approximation to f in every iteration by solving a quadratic problem in the tangent space.
• The Proximal Bundle Method works similar to CBM, but solves a proximal map-based problem in every iteration.

Second order

• Adaptive Regularization with Cubics 🏅 locally builds a cubic model to determine the next descent direction.
• The Riemannian Trust-Regions Solver builds a quadratic model within a trust region to determine the next descent direction.

Splitting based

For splitting methods, the algorithms are based on splitting the cost into different parts, usually in a sum of two or more summands. This is usually very well tailored for non-smooth objectives.

Smooth

The following methods require that the splitting, for example into several summands, is smooth in the sense that for every summand of the cost, the gradient should still exist everywhere.

• Levenberg-Marquardt minimizes the square norm of $f: \mathcal M→ℝ^d$, that is $\operatorname*{arg\,min}_{p∈\mathcal M} \frac{1}{2}\lVert f(p) \rVert^2 = \frac{1}{2}\sum_{i=1}^d f_i(p)^2$, provided the gradients $\operatorname{grad} f_i$ of the component functions, or in other words the Jacobian of $f$. A robust variant is available as well, where each summand is additionally passed through a robustifier $ρ_i$, that is $\frac{1}{2}\sum_{i=1}^d ρ_i\bigl(f_i(p)^2\bigr)$, to reduce the influence of outliers. It is specified with the robustifier= keyword.
• Stochastic Gradient Descent is based on a splitting of $f$ into a sum of several components $f_i$ whose gradients are provided. Steps are performed according to gradients of randomly selected components.
• The Alternating Gradient Descent alternates gradient descent steps on the components of the product manifold. All these components should be smooth as it is required, that the gradient exists, and is (locally) convex.

Nonsmooth

If the gradient does not exist everywhere, that is if the splitting yields summands that are nonsmooth, usually methods based on proximal maps are used.

• The Chambolle-Pock algorithm uses a splitting $f(p) = F(p) + G(Λ(p))$, where $G$ is defined on a manifold $\mathcal N$ and the proximal map of its Fenchel dual is required. Both these functions can be non-smooth.
• The Cyclic Proximal Point 🫏 uses proximal maps of the functions from splitting $f$ into summands $f_i$.
• Difference of Convex Algorithm (DCA) uses a splitting of the (non-convex) function $f = g - h$ into a difference of two functions; for each of these it is required to have access to the gradient of $g$ and the subgradient of $h$ to state a sub problem in every iteration to be solved.
• Difference of Convex Proximal Point uses a splitting of the (non-convex) function $f = g - h$ into a difference of two functions; provided the proximal map of $g$ and the subgradient of $h$, the next iterate is computed. Compared to DCA, the corresponding sub problem is here written in a form that yields the proximal map.
• Douglas-Rachford uses a splitting $f(p) = F(p) + G(p)$ and their proximal maps to compute a minimizer of $f$, which can be non-smooth.
• The Gradient Sampling Algorithm samples the gradient at points in a ball around the current iterate to build a surrogate and solve that instead to find a next iterate.
• Primal-dual Riemannian semismooth Newton Algorithm extends Chambolle-Pock and requires the differentials of the proximal maps additionally.
• The Proximal Point uses the proximal map of $f$ iteratively.

Constrained

Constrained problems of the form

\[\begin{align*} \operatorname*{arg\,min}_{p∈\mathcal M}& f(p)\\ \text{such that } & g(p) \leq 0\\&h(p) = 0 \end{align*}\]

For these you can use

• The Augmented Lagrangian Method (ALM), where both g and grad_g as well as h and grad_h are keyword arguments, and one of these pairs is mandatory.
• The Exact Penalty Method (EPM) uses a penalty term instead of augmentation, but has the same interface as ALM.
• The Interior Point Newton Method (IPM) rephrases the KKT system of a constrained problem into a Newton iteration being performed in every iteration.
• Frank-Wolfe algorithm, where besides the gradient of $f$ either a closed form solution or a (maybe even automatically generated) sub problem solver for $\operatorname*{arg\,min}_{q ∈ C} ⟨\operatorname{grad} f(p_k), \log_{p_k}q⟩$ is required, where $p_k$ is a fixed point on the manifold (changed in every iteration).
• The Gradient Projection Method projects the gradient step back onto the feasible set in every iteration.

On the tangent space

• Conjugate Residual a solver for a linear system $\mathcal A[X] + b = 0$ on a tangent space.
• Steihaug-Toint Truncated Conjugate-Gradient Method a solver for a constrained problem defined on a tangent space.

Alphabetical list of algorithms