Optimization Techniques on Riemannian Manifolds

Steven Thomas Smith

Source-linked AI summary

Optimization Techniques on Riemannian Manifolds

Steven Thomas Smith

arXiv:1407.5965v1Jul 22, 2014math.OCcs.CGmath.DGmath.DSmath.NA

TL;DR

The paper addresses how to optimize functions on Riemannian manifolds, extending classical Euclidean methods to an intrinsic geometric setting. It develops manifold versions of steepest descent, Newton, and conjugate gradient, proving convergence properties and demonstrating them on eigenvalue and matrix-optimization examples. Newton’s method has quadratic general convergence, while the paper’s examples include cubic convergence; conjugate gradient has superlinear convergence.

Problem
Optimization methods are commonly formulated in Euclidean spaces, but many problems instead lie on non-Euclidean spaces with differentiable-manifold structure.
Method
The paper replaces Euclidean straight lines and ordinary differentiation with geodesics and covariant differentiation to generalize optimization algorithms intrinsically.
Results
The proposed Newton method converges quadratically near nondegenerate critical points, while the conjugate gradient method is analyzed as having superlinear convergence.
Takeaways & Limitations
The framework supports manifold optimization and yields algorithms for eigenvalue computation and matrix problems, including examples with cubic Newton convergence.
Takeaways & Limitations
The paper’s results are local, and completeness may be relaxed only in certain instances.

Abstract

from arXiv · show

The techniques and analysis presented in this paper provide new methods to solve optimization problems posed on Riemannian manifolds. A new point of view is offered for the solution of constrained optimization problems. Some classical optimization techniques on Euclidean space are generalized to Riemannian manifolds. Several algorithms are presented and their convergence properties are analyzed employing the Riemannian structure of the manifold. Specifically, two apparently new algorithms, which can be thought of as Newton's method and the conjugate gradient method on Riemannian manifolds, are presented and shown to possess, respectively, quadratic and superlinear convergence. Examples of each method on certain Riemannian manifolds are given with the results of numerical experiments. Rayleigh's quotient defined on the sphere is one example. It is shown that Newton's method applied to this function converges cubically, and that the Rayleigh quotient iteration is an efficient approximation of Newton's method. The Riemannian version of the conjugate gradient method applied to this function gives a new algorithm for finding the eigenvectors corresponding to the extreme eigenvalues of a symmetric matrix. Another example arises from extremizing the function $\mathop{\rm tr} Θ^{\scriptscriptstyle\rm T}QΘN$ on the special orthogonal group. In a similar example, it is shown that Newton's method applied to the sum of the squares of the off-diagonal entries of a symmetric matrix converges cubically.

1 Introduction

The paper develops intrinsic optimization methods for problems defined on Riemannian manifolds, extending Euclidean techniques while exploiting manifold structure. It presents steepest descent, Newton, and conjugate-gradient methods with convergence analyses and manifold-specific examples.

Many optimization problems involve differentiable manifolds with Riemannian metrics, including eigenvalue computation through Rayleigh’s quotient on the sphere.
The paper seeks to extremize functions on Riemannian manifolds rather than treating them solely as constrained problems in higher-dimensional Euclidean spaces.Every smooth Riemannian manifold can be isometrically embedded in Euclidean space, but intrinsic methods aim to exploit its lower-dimensional structure.
Its intrinsic framework replaces vector addition, straight-line searches, and partial derivatives with exponential maps, geodesics, and covariant differentiation.
The paper analyzes steepest descent, Newton’s method, and conjugate gradient on manifolds, including linear, quadratic, and superlinear convergence results.
Examples include cubic Newton convergence for Rayleigh’s quotient, an approximation by Rayleigh quotient iteration, eigenvector computation, and a cubically convergent Jacobi-like method.

2 Preliminaries

The preliminaries formulate smooth optimization on complete Riemannian manifolds and establish the geometric machinery used by the algorithms. They define connections, geodesics, parallel translation, exponential maps, gradients, and convergence-rate terminology, while noting local scope assumptions.

The optimization problem is posed for a smooth function on a complete Riemannian manifold, with the goal of computing its extrema.
Riemannian optimization generalizes Euclidean algorithms by replacing straight lines and ordinary differentiation with geodesics and covariant differentiation.
A Riemannian metric supplies inner products, norms, distances, and the gradient defined through df_p(X) = ⟨(gradf)_p, X⟩.
An affine connection differentiates vector fields and tensors, while the Levi-Civita connection is torsion-free and preserves the metric under parallel translation.
Geodesics satisfy ∇_X X = 0, and parallel vector fields satisfy ∇_X Y = 0 along a curve; parallel translation maps tangent spaces isomorphically.
The exponential map sends an initial tangent vector to the endpoint of its geodesic, and convergence rates are defined linearly, quadratically, or cubically using manifold distance.
The results are local, so smoothness requirements may be relaxed and manifold completeness may be unnecessary in some instances.

3 Steepest descent on Riemannian manifolds

Steepest descent is generalized to Riemannian manifolds by replacing Euclidean gradient steps and line searches with gradient-based geodesic minimization. The method has linear convergence near suitable local minima, while examples on spheres and special orthogonal groups illustrate its use and computational trade-offs.

Algorithm: Each iteration computes a Riemannian gradient and minimizes the objective along the geodesic determined by that gradient.The algorithm initializes G0 = −(grad f)p0, updates along exponential-map curves, and repeats the process.
Convergence: Steepest descent makes a ninety-degree turn at every step because the new gradient is orthogonal to the parallel transport of the previous search direction.This is identified as the same deficiency found in Euclidean steepest descent.
Convergence: If the method converges to a local minimum, its convergence is linear.The result follows under the theorem’s assumptions near a nondegenerate critical point with positive-definite Hessian.
Examples: On the sphere, maximizing Rayleigh’s quotient by steepest ascent converges to an eigenvector associated with the largest eigenvalue of a symmetric matrix.The corresponding descent direction converges to the eigenvector associated with the smallest eigenvalue, and numerical results are reported for S20.
Examples: On SO(n), geodesics and parallel translation can be computed by matrix exponentiation and translation, while Brockett’s estimate avoids expensive geodesic minimization.Numerical experiments demonstrate steepest descent and ascent in SO(20) using the step-size estimate.

4 Newton’s method on Riemannian manifolds

The paper generalizes Newton’s method to Riemannian manifolds using covariant derivatives, parallel translation, and the exponential map. The resulting method has local quadratic convergence generally, with cubic convergence in several important examples.

Newton’s method on a Riemannian manifold uses the Taylor expansion of the one-form df rather than the function f itself.The construction generalizes constrained Newton methods while incorporating the manifold’s affine connection and curvature.
The method represents the covariant differential (∇µ)_p as a nonsingular map from the tangent space T_p to the cotangent space T*_p.For µ = df, this covariant differential is the Riemannian Hessian ∇²f.
The Newton step is obtained by discarding higher-order terms in the covariant Taylor expansion and solving the resulting linear equation.The next iterate is then computed with the exponential map, retaining the manifold’s intrinsic geometry.
For a nondegenerate critical point, iterates initialized in a sufficiently small neighborhood are well defined and converge quadratically.The same conclusion applies to general one-forms near a nondegenerate zero when the initial point lies in the domain of attraction.
For Rayleigh’s quotient on the sphere, the Riemannian Newton algorithm converges cubically to an eigenvector associated with a distinct eigenvalue.The method is more expensive than, but of the same order as, Rayleigh quotient iteration, which approximates it up to quadratic terms near an eigenvector.
Newton’s method also converges cubically for tr Θ^TQΘN under the stated critical-point condition and for the Jacobi-like off-diagonal minimization problem.In both examples, the relevant third-order covariant derivative vanishes at the critical point.

5 Conjugate gradient on Riemannian manifolds

The paper generalizes conjugate-gradient optimization from Euclidean spaces to Riemannian manifolds using geodesics, parallel translation, and Hessian-based conjugacy. The resulting method has a superlinear convergence guarantee near nondegenerate minima and yields an eigenvector algorithm on the sphere.

Comparison: Conjugate gradient is cheaper per iteration than Newton’s method but generally converges more slowly because Newton requires second covariant differentials and their inverses.The comparison concerns computational complexity and memory requirements as well as convergence speed.
Conjugacy: Conjugacy means that two tangent vectors have zero value under the relevant symmetric bilinear form, here typically the Hessian.For quadratic objectives, the condition reduces to conjugacy with respect to the defining symmetric matrix; nonquadratic problems may use periodic resets.
Algorithm: Riemannian conjugate gradient replaces affine line searches with geodesic minimization and transports directions by parallel translation.The algorithm initializes with the negative gradient, minimizes along geodesics, and updates directions after transporting them between tangent spaces.
Algorithm: The update coefficient γ_i is approximated using gradient information, avoiding the generally expensive second covariant differential.Taylor expansion and metric compatibility produce a relatively inexpensive formula for γ_i.
Convergence: Theorem 5.3 establishes superlinear convergence for sequences generated by the Riemannian conjugate-gradient algorithm approaching a nondegenerate critical point with positive-definite Hessian.Linear convergence is already guaranteed separately, while the proof relates the manifold method to Euclidean conjugate gradient up to third-order terms.
Applications: On the sphere, the method becomes an algorithm for computing eigenvectors associated with the largest or smallest eigenvalues of a real symmetric matrix.Each iteration uses a matrix-vector multiplication, geodesic minimization or quotient evaluation, and a specified flop count in the full experiment description.