Source-linked AI summary
Simple algorithms for optimization on Riemannian manifolds with constraints
Changshuo Liu, Nicolas Boumal
TL;DR
The paper asks whether constrained optimization can benefit from exploiting known Riemannian geometry instead of treating manifold constraints as ordinary Euclidean equalities. It extends augmented Lagrangian and exact penalty methods, with convergence analysis and nonsmooth subproblem solvers, and finds benefits in some high-dimensional applications.
Problem
The paper studies whether exploiting manifold geometry improves constrained optimization when variables satisfy additional equality or inequality constraints.
Method
It extends augmented Lagrangian and exact penalty methods to Riemannian manifolds, including smoothing and subgradient methods for nonsmooth mini-sum-max subproblems.
Results
Across minimum balanced cut, non-negative PCA, and k-means, exploiting manifold structure appears beneficial in high dimensions, while the better Riemannian algorithm varies by application.
Takeaways & Limitations
The results support exploiting manifold structure for some constrained problems, particularly in high-dimensional regimes, but the gains are moderate and method choice is application-dependent.
Takeaways & Limitations
Convergence depends on solving augmented-Lagrangian subproblems within appropriate tolerances, and the reported computational gains are moderate.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper extends classical constrained-optimization methods to problems whose variables lie on Riemannian manifolds, preserving the manifold geometry while handling additional equality and inequality constraints. It studies augmented Lagrangian and exact penalty approaches, convergence, and numerical behavior across several applications.
- The problem class optimizes twice continuously differentiable functions on a Riemannian manifold with additional equality and inequality constraints.
- Existing approaches can treat a manifold embedded in Euclidean space as additional equality constraints, but this may overlook useful manifold structure.
- The paper extends classical Euclidean constrained-optimization methods while preserving and exploiting the smooth geometry of the manifold.
- It studies augmented Lagrangian and exact penalty methods, including subgradient and smoothing algorithms for nonsmooth mini-sum-max subproblems.
- Experiments compare the Riemannian methods with fmincon on non-negative PCA, k-means, and minimum balanced cut problems.
2 Preliminaries and notations
The preliminaries define the Riemannian geometry, constraint qualifications, Lagrangian conditions, and second-order optimality concepts used throughout the paper.
- The paper assumes a complete, smooth, finite-dimensional Riemannian manifold with a metric, tangent-space norms, distances, exponential maps, and parallel transport.
- Riemannian gradients and Hessians can be understood through pullbacks of functions to tangent spaces via the exponential map.
- The active set collects relevant constraints, while LICQ requires gradients of active inequalities and equalities to be linearly independent in the tangent space.
- KKT conditions and the critical cone provide first-order and second-order optimality frameworks for mixed constrained problems.
- Under LICQ, a local minimum satisfies KKT conditions and second-order necessary conditions, while second-order sufficient conditions imply a strict local minimum.
3 Riemannian augmented Lagrangian methods
The Riemannian augmented Lagrangian method restricts the augmented-Lagrangian variable to the manifold and uses unconstrained Riemannian optimization as its subsolver. Its convergence depends on how accurately the subproblems are solved.
- The augmented Lagrangian method alternates between optimizing the primal variable and updating equality and inequality multipliers.
- In the Riemannian extension, the augmented Lagrangian remains continuously differentiable in the manifold variable under the stated assumptions.
- RALM uses optimization algorithms for unconstrained optimization on manifolds as subsolvers.
- Algorithm 1 requires a manifold, twice continuously differentiable objective and constraint functions, starting primal and multiplier values, tolerances, penalty parameters, and update constants.
17 end
The Riemannian augmented Lagrangian method separates manifold optimization from additional constraints and inherits convergence results under increasingly specific subproblem conditions. Its guarantees range from global minimization to first- and second-order stationarity, with convergence depending on subsolver tolerances and regularity assumptions.
- Riemannian ALM: Riemannian ALM solves smooth unconstrained manifold subproblems while handling the remaining constraints through an augmented Lagrangian framework.Subproblems can use standard Riemannian optimization methods, including gradient descent, nonlinear conjugate gradients, and trust regions.
- Riemannian ALM: Penalty-parameter safeguards update ρ only when constraint violations shrink sufficiently fast, helping alleviate ill-conditioning and improve robustness.
- Global convergence: If the subsolver achieves the required global-cost tolerance and the sequence has a limit point, that point is a global minimizer of the original MCP.The result assumes a feasible global minimizer exists.
- First-order convergence: Approximate first-order subproblem solutions yield KKT conditions at any LICQ-feasible limit point of the generated sequence.This result applies with ϵmin = 0.
- Scope and limitations: The second-order analysis excludes inequality constraints because the augmented function may not be twice differentiable there.
- Second-order convergence: For equality-constrained problems, approximate second-order subproblem solutions yield weak second-order necessary conditions at LICQ-feasible limit points.The guarantee concerns WSONC rather than the stronger SONC conditions.
4 Exact penalty method
The exact penalty method replaces constraints with weighted L1 violations, producing a nonsmooth manifold problem. The paper establishes finite-penalty exactness and studies smoothing approaches that make the resulting subproblems continuously differentiable.
- Exact penalty formulation: The exact penalty method adds weighted L1 constraint violations to the objective, yielding a nonsmooth unconstrained optimization problem on the manifold.
- Exactness: A finite penalty weight can enforce exact constraint satisfaction in the Riemannian setting under the stated local-minimum and SOSC assumptions.Specifically, a local minimum satisfying SOSC remains a local minimum of the penalized problem when ρ exceeds the relevant multiplier bound.
- Algorithmic treatment: The penalized objective is a sum of maximum and absolute-value terms, enabling smoothing techniques and specialized nonsmooth Riemannian optimization algorithms.
- Smoothing technique: Log-sum-exp smoothing replaces each two-term maximum with a smooth approximation controlled by parameter u, producing a smooth unconstrained manifold problem.The smoothing parameter u is positive and fixed within the resulting subproblem.
- Smoothing technique: A second strategy smooths absolute values with a pseudo-Huber loss and maxima with a linear-quadratic loss.The resulting approximations are used with fixed penalty and smoothing parameters.
- Practical considerations: The smoothed functions are continuously differentiable, but large penalty weights can cause poor conditioning and slow convergence from poor initial iterates.The exactness threshold is often unknown, motivating adaptive penalty updates in REPMS.
14 end
The paper develops Riemannian exact-penalty methods based on smoothing and subgradient descent, with convergence guarantees under stated conditions. The subgradient variant uses approximate subdifferentials and Riemannian line-search machinery for sums of maximum functions.
- Smoothed exact penalty: REPMS uses a Boolean update flag to cover fixed and dynamically increased penalty parameters.When enabled, the penalty parameter is increased heuristically when the current point is far from feasible.
- Smoothed exact penalty: With zero stopping lower bounds, fixed penalty, a feasible limit point, and LICQ, REPMS yields a point satisfying KKT conditions.The result is stated for the sequence produced by the subsolver.
- Smoothed exact penalty: The convergence proposition likely requires a sufficiently large initial penalty, motivating dynamic penalty updates when that threshold is unknown.The update heuristic raises the penalty when feasibility is poor.
- Subgradient method: The authors propose REPMSD as a robust method, but report poor numerical performance and therefore provide only an overview.Other nonsmooth methods are mentioned but not tested.
- Subgradient method: For sums of maximum functions, the paper constructs explicit subdifferentials from convex hulls of selected gradients and relaxes them using an epsilon-active index set.The approximate set includes functions within epsilon of each maximum.
- Subgradient method: REPMSD computes a minimum-norm vector in the extended convex hull, then uses Wolfe line search and limited-memory Riemannian BFGS.This avoids gradient sampling for the structured nonsmooth subproblem.
5 Numerical experiments and discussion
The experiments model minimum balanced cut, non-negative PCA, and k-means as constrained problems on oblique, spherical, and Stiefel manifolds. Comparisons with fmincon show that Riemannian methods can be advantageous in higher dimensions, although performance depends on the application and method.
- Minimum balanced cut: Minimum balanced cut is relaxed from discrete cluster indicators to matrix factors on an oblique manifold with one quadratic equality constraint.The relaxation ranges from the original problem at k = 1 toward a semidefinite formulation at k = n.
- Non-negative PCA: Non-negative PCA is formulated on the sphere with componentwise non-negativity constraints and evaluated across dimensions, sparsity levels, and signal-to-noise ratios.The experiment contains 144 problems per dimension basket.
- K-means: K-means is reformulated on the Stiefel manifold with equality and non-negativity constraints using cleaned and normalized UCI datasets.The equivalent formulation imposes orthonormal columns, non-negativity, and a row-sum constraint.
- Minimum balanced cut: High-dimensional minimum balanced cut tests cause fmincon to converge to points far from feasible, while exact-penalty methods and RALM remain satisfactory in some cases.Apart from REPMSD, all methods perform well in the low-dimensional case.
- Non-negative PCA: As non-negative PCA dimension increases, RALM and REPMS(Qlqh) outperform fmincon, whereas REPMS(Qlse) is slowed by computing inactive constraint gradients.The observation disfavors REPMS(Qlse) when many inequality constraints are present.
- K-means: For high-dimensional k-means, fmincon performs worse than RALM and REPMS in Maxvio and Cost, while REPMS(Qlqh) achieves the lowest cost.REPMS(Qlqh) and RALM also combine relatively short solving time with lower Maxvio.
6 Conclusion
The paper extends augmented Lagrangian and exact penalty methods to Riemannian manifolds and evaluates them against treating manifold constraints as general constraints. Experiments suggest manifold-aware methods can help in high dimensions, but algorithm rankings vary by application and gains are moderate.
- Augmented Lagrangian and exact penalty methods are extended to Riemannian manifolds with essential convergence results.
- The methods are compared with a baseline that treats the manifold as a set of general constraints on minimum balanced cut, non-negative PCA, and k-means.
- In high dimensions, exploiting manifold structure seems beneficial, while the better Riemannian algorithm varies by application.
- The numerical gains over classical methods are moderate, despite satisfactory performance especially in high dimensions.
A Proof of Proposition 3.2
The proof establishes that a limit point of the algorithm satisfies KKT conditions under LICQ by controlling inactive multipliers, comparing tangent vectors through parallel transport, and handling bounded and unbounded multiplier cases.
- Smoothness of parallel transport is established locally using normal coordinates, radial geodesics, and smooth ODE solutions.
- The auxiliary coordinate variables are constant, allowing the extended ODE system to remain smooth in the base-point choice.
- Inactive inequality constraints eventually receive zero multipliers because their constraint functions remain strictly negative near the limit.
- LICQ preserves linear independence of active constraint gradients near the limit, enabling the bounded-multiplier argument.
- Parallel transport brings tangent vectors at changing iterates into a common tangent space so their limits can be compared.
- If normalized multiplier coefficients were unbounded, their nonzero limit would contradict LICQ; therefore the limit point satisfies KKT conditions.
B Proof of Proposition 3.4
The proof constructs a smooth tangent vector field satisfying the equality-constraint orthogonality conditions by solving for selected coordinates with the implicit function theorem.
- A tangent vector d is required to be orthogonal to every equality-constraint gradient at the KKT point.
- The proof defines a coordinate map F whose values encode inner products between a parameterized vector and equality-constraint gradients.
- The Gram matrix of the Riemannian metric expresses F in coordinates and supports differentiation with respect to the adjustable variables.
- LICQ makes the relevant gradient matrix full rank, so the Jacobian of F with respect to the adjustable coordinates is invertible.
- The implicit function theorem then supplies a continuously differentiable local function selecting coordinates that preserve orthogonality.
- Connection and Hessian identities are used to pass to the limit and derive the required local relation.
C Proof of Proposition 4.1
The proof analyzes the directional behavior of a nonsmooth exact-penalty function near a KKT point. It shows that feasible and infeasible directional cases both contradict the existence of a nearby point with lower penalty value.
- The exact-penalty function is locally simplified by removing inactive constraints near the KKT point.
- Although nonsmooth, the penalty function has directional derivatives in every direction because the composed constraint functions are sufficiently smooth.
- KKT stationarity supplies the first-order relation used to analyze the penalty function along candidate directions.
- A hypothetical nearby point with lower penalty value is represented through the inverse exponential map and a tangent displacement sequence.
- For feasible critical directions, the penalty expansion becomes strictly positive, contradicting the assumed lower value.
- For directions violating an active inequality, the corresponding first-order constraint expansion yields the contradiction needed to exclude a lower nearby penalty value.
D Proof of Proposition 4.2
The proof analyzes coefficient sequences across iterations, establishes limiting behavior for inactive constraints, and uses parallel transport and bounded coefficients to conclude the key norm vanishes.
- The proof defines iteration-dependent coefficients for indices in the inequality and equality constraint sets.
- Under the assumptions, the parameter ρ_k remains constant across all iterations.
- The coefficient sequence λ_i converges to zero for inequality constraints inactive at the feasible limit point.
- After sufficiently many iterations, parallel transport from x_k to x is well defined because the iterates lie within the injectivity radius.
- Bounded coefficients allow the proof to conclude that the limiting vector satisfies ∥v∥ = 0.