Optimization techniques on Riemannian manifolds

Abstract. The techniques and analysis presented in this paper provide new meth-ods 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 em-ploying 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 Rieman-nian 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 effi-cient approximation of Newton’s method. The Riemannian version of the conjugate gradient method applied to this function gives a new algorithm for finding the eigen-vectors corresponding to the extreme eigenvalues of a symmetric matrix. Another example arises from extremizing the function tr ΘTQΘ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.