Riemannian Convexity

Constantin Udrişte

Abstract

The aim of this report is to describe some recent research in the interdisciplinary area of convex functions and optimization methods on Riemannian manifolds summarizing the papers of C.Udriste, V.Balan, T.Rapcsak, T.Csendes, S.T.Smith, A.Edelman, T.Arias, O.P. Ferreira, P.R.Oliveira. The choice of the topics and references is largely influenced by the author’s own interests and it is no way a complete list, which would be nearly impossible to be made and to be presented in a single exposition.

Mathematics Subject Classification: 49M45, 53C21, 49M15, 65K05, 90C25 Key words: convex functions, descent algorithms, geometry of geodesics, flows, energies, computer programs

1 On some works of C.Udrişte

The book [1] introduces the reader into the fascinating present- day theory of convex functions, geometry, standard dynamical systems, optimization and descent numerical algorithms on Riemannian manifolds, exemplified by appropriate computer experiments. The simplest way to give an idea of the scope of the book which was produced as the first account in about the last twenty years, is to list the main topics by chapters.

The first chapter (Metric properties of Riemannian manifolds) is a brief introducing into Riemannian geometry and minima of functions. The main purpose of the second chapter (First and second variations of the p-energy of a curve) lies in the study of the Hessian of the p-energy of a curve at each critical point and in the geometrical interpretation of Jacobi fields. Also, some information about the distance between a point and a set, and the distance between two sets are given.

The third chapter (Convex functions on Riemannian manifolds) presents the basic concepts and theorems regarding the Riemannian convexity of real functions. A convex function on a Riemannian manifold is a real-valued function whose restriction to every geodesic arc is convex. When we refer to a subset A of a Riemannian manifold (M, g), this definition of the convexity of f : A → R requires a definition of the total convexity of the subset A. Only for a C^{2} function it is possible to give a definition which does not depend directly on geodesics: a C^{2} function f is convex if Hess_{g}f is positive semidefinite.

Balkan Journal of Geometry and Its Applications, Vol.1, No.2, 1996, pp. 111-116 \begin{matrix}c \\ ◯ \end{matrix}Balkan Society of Geometers, Geometry Balkan Press

Within the same chapter, two relevant aspects are emphasized: first, that notion of Riemannian convexity is strongly metric-dependent either through geodesics or through the Riemannian connection; second, that Riemannian convexity of functions is coordinate-free and therefore it can be easily connected with symbolic computation. Basic properties of convex programs, dual-theory problem and the Kuhn-Tucker theorem are then discussed.

The chapter ends with a description of the distance from a point to a closed totally convex set and the distance between two closed totally convex sets when the sectional curvature of the Riemannian manifold is nonpositive.

The fourth chapter (Geometric examples of convex functions) focuses on nontrivial examples of convex functions given by R.L.Bishop, J.Cheeger, R.E.Greene, D.Gromoll, B.O’Neill, K.Shiohama, H.Wu, and analyses some changes of the Riemannian metric preserving the completeness and the convexity.

The fifth chapter (Flows, convexity and energies) begins with some basic properties of the flows generated by vector fields on Riemannian manifolds and main properties of the gradient flow. Here it is shown that a complete Riemannian manifold admitting a nonconstant convex function must have infinite volume and certain topological properties which can be described by means of diffeomorphisms. New information about irrotational, Killing, conformal, affine, projective and torse forming vector fields are obtained analysing the variation of the energies of these vector fields along the orbits and the critical points of the energies, including the cases in which the energies are convex functions. These problems are not only of mathematical interest, but have direct physical interest; e.g., critical points of the energy of a stationary magnetic field which are not zeros of the field are important in Geophysics and in Stability Theory of Plasma and Controlled Thermonuclear Fusion Research, because these points give minimum or saddle energy values with nonvanishing intensity. This paragraphs ends with the Runge-Kutta approximation of an orbit and a T P program designed for plotting such orbits.

The sixth chapter (Semidefinite Hessians and applications) handles the convex functions on Riemannian manifolds to obtain mathematical information about submanifolds, harmonic maps, g-connected domains , conservative dynamical systems,and linear complementarity problem .

The seventh chapter (Minimization of functions on Riemannian manifolds) starts with properties of the minus gradient flow, the Runge- Kutta approximation of a minus gradient line and a computer T C program for plotting such curves. Then numerical approximations of a geodesic are discussed and computer T C programs which plot geodesics are given. There follows a discussion of the descent algorithms on Riemannian manifolds having in mind that we can choose the Riemannian metric according to the nature of specific problems. The Riemannian structure of the manifold is involved in the theory of minimization by means of the Riemannian metric, by the induced distance, by geodesics which are initially tangent to descent directions, by the Riemannian connection, and by the sectional curvature.

Chapter 3 and chapter 7 point out that computational difficulties presented by some optimization problems belong to a wrong understanding of the suitable geometry of the space, which can create or destroy the convexity of classical test objective functions. In fact the Rosenbrock banana function, Powell function, Fletcher and Powell function, etc are Riemannian convex functions.

The appendices (Riemannian convexity of function f : R → R, Descent methods on the Poincare plane, Descent methods on the sphere, Completeness and convexity on Finsler manifolds) constitute an attempt ”to open the eyes” of beginners and to make accessible to all users of this book some basic ideas in Riemannian geometry, optimization theory and computer programs.

The real novelties which distinguish this book come from the following aims of the author:

- to convince the readers that convexity, far from being a dusty classical field, is on the contrary a prodigious source of challenging open problems;

- to describe connections between Riemannian geometry, optimization, dynamical systems, numerical analysis and computer programs.

There are freqvent mentions of major open problems, and interspersed throughout the text is a succession of examples and remarks that illuminate and amplify the core material thoroughly developed in the form of definitiontheorem-proof.

The preceding arguments justify the effort to generalize the optimization theory on Euclidean spaces to the Riemannian manifolds. The generalization is obtained by selecting a suitable Riemannian metric, by passing from vector addition to the exponential map, by changing the search along straight lines with a search along geodesics, and by using covariant differentiation instead of partial differentiation.

The paper [2] presents the Newton method on a Riemannian manifold for finding critical points of a function, describes the general framework of the logarithmic barrier method and of the center method for smooth convex programming on a Riemannian manifold, analyses the monotonicity along the central path showing that the vector fields of interior point algorithms are Riemannian gradients, and gives the Riemannian variants for some lemmas of Nesterov and Nemirovski.

The paper [3] reveals new ideas about Newton algorithm on Riemannian manifold for finding zeros of a differential 1-form, including properties of the Newton method near the central path of a convex program obtained by the original Riemannian metric and a Hessian Riemannian metric, and upper bounds for the total number of outer and inner iterations for the logarithmic barrier algorithm applied to a convex program on a Riemannian manifold.

The paper [4] shows that some difficulties appearing in the free- minimization problems belong to a wrong understanding of the suitable Riemannian structure of the space, which can create or destroy the convexity. Of course in the minima problems we are interested to create the convexity of the objective function because this assures the convergence of the numerical methods of optimization towards a minimum point. Further, this paper deals with Newton algorithm on Riemannian manifolds for finding zeros of a vector field or generally of a tensor field, including theorems regarding the Newton method near the path of centers of a convex program obtained by the original Riemannian metric and a Hessian Riemannian metric, and upper bounds for the total number of outer and inner iterations needed by the center algorithm on a Riemannian manifold. The paper [4] and the present Note were included in the oral communication at The Second International Workshop on Differential Geometry and Its Applications, Ovidius University of Constantza, Romania, September 25-28, 1995.

C.Udriste and V.Balan [5] introduce and describe naturally the properties of the gradient, divergence, Hessian, Laplacian on a vector bundle endowed with a (h, v)-metric and with a suitable connection. Results on convexity and the interpretation of a dual program like a problem on a trivial vector bundle are given. Explicit formulas for special (h, v)- metrics and for particular manifolds (Finsler, Lagrange, etc) are obtained.

2 On some works of T.Rapcsak and his coworkers

T.Rapcsak and his coworkers analyse the structure of nonlinear optimization problems by means of techniques in differential geometry.

In [6],[7], nonlinear coordinate transformations are discussed in order to simplify global unconstrained optimization problems and to test their unimodality based on the analytical structure of the objective functions. If the transformed problems can be quadratic in some or all the variables, then the optimun can be calculated directly without an iterative procedure, or the number of variables to be optimized can be reduced. Otherwise, the analysis of the structure can serve as the first step for solving global unconstrained optimization problems.

Complementarity systems are related to numerous important issues of nonlinear optimization and application areas such as engineering, structural mechanics, elasticity theory, lubrication theory of networks, etc. Using some ideas from the Riemannian convexity, in [8], [9] sufficient conditions are established for the connectedness of nontrivial subsets of the solution set relating to linear and nonlinear complementarity systems with a special structure. Connectedness is important to investigate stability and sensitivity questions, parametric problems and for extending a Lemke-type method to a new class of problems.

In [10] the behaviour of interior point algorithms by using a suitable Riemannian metric is analysed. It is shown that the vector fields of several interior point algorithms for linear programming are the Riemannian gradients of the linear, potential or logarithmic barrier functions. Also, a class of polynomial variable metric algorithms is given for solving the canonical form of linear programming with respect to a wide class of Riemannian metrics.

3 On some works of S.T.Smith and his coworkers

S.T.Smith [11], [12] refers to optimization problems posed on Riemannian manifolds. Newton method and the conjugate gradient method on Riemannian manifolds are introduced and shown to possess quadratic and superlinear convergence, respectively. These methods are applied to several eigenvalue and singular value problems, formulated as constrained optimization problems. New efficient algorithms for the eigenvalue problem are obtained by exploiting the special homogeneous space structure of the constraint manifold. It is shown that Newton method applied to the Rayleigh quotient on a sphere converges cubically, and that the Rayleigh quotient iteration is an efficient approximation of Newton 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. The Riemannian version of the conjugate gradient method applied to a generalized Rayleigh quotient yields a superlinearly convergent algorithm for computing the k eigenvectors corresponding to the extreme eigenvalues of a matrix. Several gradient flows are analyzed that solve eigenvalue and singular value problems. The general theory is applied to the subspace tracking problem found in adaptive signal processing and adaptive control.

A.Edelman, T.Arias and S.T.Smith [13] gave new ideas about minimization problems on the Stiefel and Granssmann manifolds using the Riemannian variants of some numerical algorithms and unifying differential geometry, optimization, and numerical linear algebra with intended applications in computational physics.

4 On the paper of O.P.Ferreira-P.R.Oliveira

O.P.Ferreira, P.R.Oliveira [14] generalize the subgradient method to the context of Riemannian manifolds and suggest the influence of the sectional curvature on the convergence of minimization algorithms.

References

[1] C.Udriste, Convex functions and optimization methods on Riemannian manifolds, Mathematics and Its Applications, 297, Kluwer Academic Publishers, 1994.

[2] C.Udriste, Optimization methods on Riemannian manifolds, Proceedings of IRB International Workshop, Monteroduni, Italy, August 8-12, 1995 (in press).

[3] C.Udriste, Riemannian convexity in programming (I), Proceedings of 25-th National Conference on Geometry and Topology, Al.I.Cuza University of Iassy, Romania, September 18-23, 1995 (in press).

[4] C.Udriste, Riemannian convexity in programming (II), The Second International Workshop on Differential Geometry and Its Applications, Ovidius University of Constantza, Romania, September 25-28, 1995; this Journal pp.99-109.

[5] C.Udriste, V.Balan, Differential operators and convexity on vector bundles endowed with (h, v)-metrics, Proceedings of 25-th National Conference on Geometry and Topology, Al.I.Cuza University of Iassy, Romania, September 18-23, 1995 (in press).

[6] T.Csendes, T.Rapcsak, Nonlinear coordinate transformations for unconstrained optimization. I.Basic transformations, Journal of Global Optimization 3(1993), 213-221.

[7] T.Rapcsak, T.Csentes, Nonlinear coordinate transformations for unconstrained optimization. II. Theoretical background, Journal of Global Optimization 3(1993),359-375.

[8] T.Rapcsak, On the connectedness of the solution set to linear complementarity systems, JOTA 80, 3(1994), 501-512.

[9] T.Rapcsak, On the connectedness of the solution set to nonlinear complementarity systems, JOTA 81, 3(1994), 619-631.

[10] T.Rapcsak, T.T.Thang, A class of polynomial variable metric algorithms for linear programming, LORDS, W P 93-5, 1993, MTA, SZTAKI, Budapest.

[11] S.T.Smith, Geometric optimization methods for adaptive filtering, PhD Thesis, Harvard University, Cambridge, Massachusetts, 1993.

[12] S.T.Smith, Optimization techniques on Riemannian manifolds, Fields Institute Communications, 3, 113-146, Providence, RI, 1994, AMS.

[13] A.Edelman, T.Arias, S.T.Smith, Conjugate gradient on the Stiefel and Grassmann manifolds, manuscript.

[14] O.P.Ferreira, P.R.Oliveira, Subgradient algorithm on Riemannian manifolds, Publicacoes Tecnicas, COPPE, Universidade Federal de Rio de Janeiro, ES-354, 1995.

University Politehnica of Bucharest Department of Mathematics I Splaiul Independenţei 313 77206 Bucharest, ROMANIA Fax: (401)/312.53.65 e-mail:udriste@mathem.pub.ro