PaperlayerView exact revision on arXiv

Source-linked AI summary

A Brief Introduction to Manifold Optimization

Jiang Hu, Xin Liu, Zaiwen Wen, Yaxiang Yuan

arXiv:1906.05450v1math.OC

TL;DR

Manifold optimization addresses constrained problems whose nonconvex manifold constraints complicate algorithm design and analysis. The paper uses manifold geometry to organize formulations, optimality conditions, algorithms, applications, and theoretical results. Across the surveyed scope, it reports results including improved efficiency over SCF, convergence-established proximal-gradient methods, and global-optimality guarantees under stated conditions.

  • Problem

    Nonconvex manifold constraints make algorithmic design and theoretical analysis difficult for a broad class of constrained optimization problems.

  • Method

    The paper surveys manifold formulations, intrinsic geometry, optimality conditions, numerical algorithms, applications, and recent theoretical results.

  • Results

    The surveyed results include algorithms often more efficient than SCF, convergence-established proximal-gradient methods, and global optimality under stated Burer–Monteiro conditions.

  • Takeaways & Limitations

    Manifold structure provides a framework for treating applications in imaging, physics, signal recovery, combinatorial optimization, and eigenvalue computation.

  • Takeaways & Limitations

    Effective solutions remain limited largely to relatively simple manifolds such as orthogonal and rank-constrained structures, while metric and retraction choices are unclear for more complicated manifolds.

Abstract

from arXiv · show

Manifold optimization is ubiquitous in computational and applied mathematics, statistics, engineering, machine learning, physics, chemistry and etc. One of the main challenges usually is the non-convexity of the manifold constraints. By utilizing the geometry of manifold, a large class of constrained optimization problems can be viewed as unconstrained optimization problems on manifold. From this perspective, intrinsic structures, optimality conditions and numerical algorithms for manifold optimization are investigated. Some recent progress on the theoretical results of manifold optimization are also presented.

1. Introduction.

Manifold optimization formulates optimization over a Riemannian manifold, including possible additional constraints, while addressing the difficulty that manifold constraints create for algorithms and theory. The paper reviews applications, geometry, optimality conditions, algorithms, and theoretical results.

  • Manifold optimization considers a real-valued, potentially nonsmooth function on a Riemannian manifold.
  • Additional constraints can be incorporated through an indicator function, yielding a general manifold-optimization formulation.
  • Manifold constraints are a main difficulty in algorithmic design and theoretical analysis.
  • The paper surveys applications across computational mathematics, statistics, machine learning, data science, and material science.
  • Its coverage includes manifold geometry, optimality conditions, state-of-the-art algorithms, and theoretical results for selected applications.

2. Applications of manifold optimization.

The paper presents manifold-optimization models across imaging, combinatorial optimization, signal recovery, physics, tensor methods, and eigenvalue computations. These applications exploit sphere, orthogonality, rank, and related manifold structures, alongside algorithms designed for scalability or convergence.

  • 2.1. P-harmonic flow.: Conformal mapping minimizes harmonic energy to map genus-0 surfaces, including irregular surfaces, to simpler parameterized surfaces such as the unit sphere.Stationary points of harmonic energy are harmonic maps; conformal maps to R2 correspond to pairs of harmonic functions.
  • 2.2. Max cut.: Max-cut is modeled by splitting graph vertices into two sets and assigning each vertex a value in {1, −1}, followed by semidefinite and sphere-based relaxations.The factorized relaxation optimizes over multiple spheres with ∥Vi∥2 = 1.
  • 2.4. Phase retrieval.: Phase retrieval jointly optimizes phase and signal variables under modulus constraints and can be generalized from max-cut to complex spheres.For fixed phase u, the signal is represented as x = A†diag{b}u.
  • 2.5. Bose-Einstein condensates.: BEC ground states are obtained by minimizing a total-energy functional under a spherical constraint, with discretization producing a finite-dimensional problem.The real BEC formulation can also be viewed as best rank-1 approximation of a fourth-order tensor.
  • 2.6. Cryo-EM.: Cryo-EM reconstructs a 3-D object from 2-D projections by optimizing over multiple orthogonality constraints for projection directions.The rotations can be compressed to 3-by-2 matrices, and eigenvector and SDP relaxations are also described.
  • 2.7. Linear eigenvalue problem.: Linear eigenvalue and singular-value problems are treated as orthogonality-constrained optimization, with subspace, penalty, Gauss–Newton, and augmented-subspace algorithms addressing large-scale computation.Tensor-train representations reduce storage from O(n^d) dimensions to O(dnr^2) entries when the TT-rank is r.
  • 2.8. Nonlinear eigenvalue problem.: For nonlinear eigenvalue problems, a manifold gradient method is often more efficient than SCF, while proximal-gradient linearization yields an explicit subproblem solution with established convergence.The manifold method has lower per-step complexity than the linear eigenvalue problem and is easy to parallelize.

2.9. Approximation models for integer programming.

The section presents manifold-based formulations for diverse approximation and clustering problems, including integer programming, network analysis, deep learning, dimensionality reduction, matrix completion, blind deconvolution, and k-means.

  • Integer and network optimization: Permutation-matrix constraints are relaxed to doubly stochastic formulations, yielding simpler optimization models and motivating a gradient-type method with negative proximal terms.An asynchronous parallel algorithm is additionally developed for network problems exceeding 10 million dimensions.
  • Integer and network optimization: Community detection is formulated through partition matrices and modularity maximization, with semidefinite and completely positive relaxations over nonnegative spheres.The sparse completely positive relaxation targets a low-rank formulation.
  • Deep learning: Batch normalization gives neural-network optimization a product-manifold structure consisting of spheres for weight vectors and Euclidean factors for remaining parameters.Batch standardization ensures gradient invariance to linear scaling and prevents model explosion with large learning rates.
  • Dimensionality reduction: Sparse PCA adds an ℓ1 term to the Stiefel-manifold formulation, while nonnegativity constraints provide another route to sparse principal eigenvectors.The ℓ1 term promotes sparsity, and setting ρ = 0 recovers traditional PCA.
  • Matrix recovery: Low-rank matrix completion can be solved on a fixed-rank manifold after low-rank decomposition, with robust variants incorporating outlier handling.The formulation can also accommodate Gaussian noise, while the robust problem assumes prior knowledge of the rank.
  • Other applications: Sphere-constrained sparse blind deconvolution uses regularization and extra constraints to address ill-conditioning, whereas k-means admits a Stiefel-manifold formulation with linear and nonnegative constraints.The blind-deconvolution model is posed on a product manifold of a sphere and R^m.

3. Algorithms for manifold optimization.

The paper introduces manifold optimization as a class of optimization problems on Riemannian manifolds and then develops the concepts needed for its algorithms.

  • Algorithms for manifold optimization: The algorithmic discussion begins by framing optimization problems on Riemannian manifolds as its subject.The paper states that it starts from the concepts of manifold optimization.
  • Algorithms for manifold optimization: A manifold is locally homeomorphic to Euclidean space through charts, with smooth transition maps defining a smooth manifold.The definition uses Hausdorff and second-countable topological spaces.
  • Algorithms for manifold optimization: Tangent spaces are introduced through tangent vectors generated by curves on the manifold.The tangent space at a point collects the tangent vectors of curves passing through that point.

3.1. Preliminaries on Riemannian manifold.

The preliminaries define Riemannian geometry and survey standard manifolds, their tangent or horizontal spaces, projections, and differential operators used in optimization.

  • Geometric preliminaries: A Riemannian manifold equips each tangent space with a smoothly varying inner product, enabling definitions of Riemannian gradients and Hessians.The gradient is the unique tangent vector representing directional derivatives under the metric.
  • Typical manifolds: The sphere, Stiefel, and oblique manifolds encode unit-norm, orthonormal-column, and unit-row-norm constraints, respectively.The paper gives tangent-space and projection constructions for these manifolds.
  • Typical manifolds: The Grassmann manifold represents p-dimensional subspaces as a quotient of the Stiefel manifold under right orthogonal transformations.Horizontal spaces provide unique tangent-vector representatives for the quotient geometry.
  • Typical manifolds: The fixed-rank manifold is represented by SVD factors involving Stiefel matrices and positive singular values, with corresponding tangent and projection operators.Its geometry supports manifold optimization for rank-constrained matrix problems.
  • Typical manifolds: The paper also describes SPD and rank-r positive-semidefinite manifolds, including quotient representations and projections based on a Sylvester equation.The positive-semidefinite representation uses X = YY^⊤ with a rank condition on Y.
  • Differential structure: Optimality analysis is formulated using Riemannian connections, gradients, Hessians, and projections onto manifold tangent structures.These preliminaries prepare the subsequent first- and second-order conditions.

3.2. Optimality conditions.

The paper extends KKT and second-order optimality conditions to manifold-constrained problems, using tangent-space constraint qualifications and Riemannian derivatives.

  • First-order conditions: For equality- and inequality-constrained manifold problems, LICQ requires the active constraint gradients to be linearly independent on the tangent space.The active set includes all equality constraints and active inequalities.
  • First-order conditions: Under LICQ, a local minimizer admits Lagrange multipliers satisfying the manifold KKT conditions.The theorem states first-order necessary optimality conditions for the constrained problem.
  • Second-order conditions: Second-order necessary conditions test the Riemannian Hessian of the Lagrangian on the critical cone associated with a KKT point.The section introduces the critical cone before stating second-order conditions.
  • Second-order conditions: Second-order sufficient conditions imply that a KKT point is a strict local minimum when the required Hessian condition holds.The result is stated for constrained problems under the preceding KKT framework.
  • Manifold-only conditions: With only manifold constraints, first- and second-order stationarity conditions take a form analogous to unconstrained Euclidean optimization.A second-order stationary point satisfying the stated condition is a strict local minimum.
  • Algorithmic context: Manifold-aware algorithms use intrinsic structures such as geodesics and parallel translation because Euclidean constrained methods may be ineffective in practice.The paper cites globally convergent geodesic gradient descent and Riemannian conjugate-gradient methods.

3.3. First-order type algorithms.

First-order manifold methods adapt Euclidean descent through retractions, vector transports, and manifold line searches. Their convergence is established under differentiability assumptions, while retraction and transport choices affect computational cost and iteration efficiency.

  • Geometric ingredients: Retraction maps tangent-space steps back onto the manifold, providing the principal geometric difference from Euclidean gradient descent.The retraction is smooth, locally well-posed under suitable conditions, and satisfies identity and first-derivative properties at the zero tangent vector.
  • Geometric ingredients: Vector transport moves tangent vectors between tangent spaces and generalizes parallel translation for conjugate-gradient and related methods.Projection- and parallelization-based transports can use tangent-basis representations to reduce computational cost.
  • First-order schemes: Armijo and nonmonotone curvilinear searches select step sizes, with Barzilai-Borwein initialization generalized using vector transport between iterates.The nonmonotone reference value is updated as a convex combination of the previous reference value and the new objective value.
  • Retraction choices: Retraction choices trade computational cost against approximation quality: polar decomposition is cheaper than Cayley transform, while Cayley better approximates the exponential map.The polar-decomposition approach may require more iterations than the Cayley transform.
  • Convergence: Every accumulation point of the Riemannian gradient method is stationary when the objective is continuously differentiable on the manifold.The result applies to the sequence generated with the stated nonmonotone line search.
  • Limitations: Gradient-type methods are often fast initially but may slow or stagnate near an optimum, motivating second-order methods when high accuracy is required.This limitation concerns behavior close to an optimal solution rather than the method’s early iterations.

3.4. Second-order type algorithms.

Second-order manifold algorithms use Hessian information through trust-region, Newton, and adaptive regularization frameworks. Under stated smoothness, boundedness, and retraction assumptions, they provide global stationarity guarantees and, locally, superlinear convergence.

  • Riemannian trust-region method: Riemannian trust-region methods solve a tangent-space Taylor-model subproblem, then accept or reject a retracted trial point using actual-to-predicted reduction.Truncated conjugate gradients provide a relatively cheap subproblem solver and can produce directions satisfying Cauchy decrease.
  • Riemannian trust-region method: Under Assumptions 4 and 5, the Riemannian trust-region sequence has global convergence to a stationary point.Additional Lipschitz-gradient and isometric-retraction conditions establish convergence of the whole sequence, with locally superlinear rates available under further assumptions.
  • Adaptive regularized Newton method: Adaptive regularized Newton methods construct Euclidean second-order models with regularization while retaining the manifold constraint.Successful or unsuccessful trial steps adjust the regularization parameter through prescribed update factors.
  • Adaptive regularized Newton method: Under Assumptions 4 and 7, adaptive regularized Newton iterations achieve global convergence to a stationary point.The analysis uses conditions including Lipschitz continuity and bounded gradients and Hessians.
  • Adaptive regularized Newton method: With Assumptions 9 satisfied, the adaptive regularized Newton sequence converges q-superlinearly to the limit point.The assumptions include convergence of the iterates, positive-definite limiting Riemannian Hessian, and increasingly accurate Hessian approximations.
  • Quasi-Newton methods: Ambient-space quasi-Newton approximations can avoid vector transport, and structured approximations may be more reliable when they inherit the exact Hessian spectrum.A Nyström approximation is investigated for the ambient-space correction, while the structured approximation retains spectral information from the exact form.

3.5. Stochastic algorithms.

Stochastic manifold methods generalize Euclidean stochastic optimization by combining random gradients with tangent-space projection and retraction. Riemannian SVRG reduces variance before taking feasible manifold steps.

  • Stochastic manifold methods: Euclidean stochastic algorithms such as Adam, Adagrad, RMSProp, Adelta, and SVRG can be generalized to manifold constraints using retractions and vector transport.Implementation choices vary because the computational costs of the constituent operations differ.
  • Riemannian SVRG: Riemannian SVRG computes a full gradient, samples an index, and constructs a reduced-variance stochastic gradient.The method then projects the stochastic gradient onto the tangent space before applying a retraction step.
  • Riemannian SVRG: The Riemannian SVRG procedure iteratively updates feasible points across inner iterations and carries the final inner iterate to the next outer epoch.The algorithm includes random Euclidean-gradient calculation followed by manifold-aware updating.

3.6. Algorithms for Riemannian non-smooth optimization.

Non-smooth manifold optimization combines manifold geometry with subgradient, gradient-sampling, trust-region, proximal, and stochastic techniques. Proximal methods solve convex tangent-space subproblems, while complexity results quantify stationarity guarantees for several algorithm classes.

  • Problem setting: Non-smooth manifold problems may combine a smooth term with a non-smooth term, motivating subgradient, gradient-sampling, trust-region, and proximal approaches.Convergence analyses use tools including Kurdyka-Lojasiewicz inequalities and local Lipschitz assumptions.
  • Proximal gradient method: The proximal gradient method linearizes the smooth term on a tangent space and adds a proximal treatment of the convex non-smooth term.A retraction interprets the tangent-space subproblem as a first-order approximation on the manifold.
  • Proximal gradient method: The tangent-space proximal subproblem is convex with linear constraints, so KKT conditions characterize global optimality.A monotone nonlinear equation is solved with a semismooth Newton method, followed by curvilinear search and retraction.
  • Complexity: Riemannian gradient methods reach ∥gradf(x)∥≤ε within O(1/ε^2) steps, while cubic regularization reaches first- and second-order criteria in O(1/ε^1.5).The trust-region bound under the stated mild assumptions is O(max{1/ε^1.5, 1/ε^2.5}), and multi-block nonsmooth ADMM has complexity O(1/ε^4).

4. Analysis for manifold optimization.

The paper analyzes how manifold geometry supports optimality theory and convergence guarantees across several nonconvex optimization applications. Results include global-optimality characterizations, approximation guarantees, and convergence under stated structural assumptions.

  • Geodesic convexity: Geodesic convexity extends convexity to functions that are convex along manifold geodesics, making every local minimum global.The paper notes that a function such as (log x)^2 can be nonconvex in Euclidean space yet geodesically convex under a suitable metric.
  • Geodesic convexity: A suitable Riemannian metric is important for recognizing geodesic convexity, but proving that such a metric exists is generally difficult.Any function with a non-global local minimum cannot be geodesically convex under any metric.
  • Electronic structure calculations: Under a spectral-gap assumption and bounded second derivatives, suitably stepped SCF iterations converge to a KS solution with an explicit rate bound.The step size must satisfy 0 < α < 2/(2 − b1), and the rate is no worse than |1 − α| + α(1 − b1).
  • Burer-Monteiro factorizations: For almost any cost matrix, first- and second-order stationary points of the factored semidefinite problem are globally optimal when p(p+1)/2 exceeds rank A.Under the stated assumptions, the lifted solution X = YY⊤ is globally optimal for the original problem.
  • Little Grothendieck problem: The survey identifies a constant approximation ratio for an orthogonality-constrained solution that recovers the classical 2/π guarantee for the little Grothendieck problem.The result is stated for vectors obtained from the described projection-based construction.
Loading 1906.05450v1…