A Proximal Regularization of the Steepest Descent Method in Riemannian Manifold

J.X. da Cruz Neto, O.P.Ferreira and L.R.Lucambio Perez

Abstract We extend the steepest descent method to solve optimization problems in Riemannian manifolds. Same proof’s techniques used in R^{n} can be modified to prove the existence of cluster points, that such cluster points are critical points and that if the manifold has non-negative sectional curvature and the function is convex then the generated sequence is convergent.

Mathematics Subject Classification: 49M10, 90C30, 53C21 Key words: Convex programming, steepest descent method, Riemannian manifolds.

1 Introduction

The steepest descent method is one of the oldest and simplest procedures for minimization of a real function defined on R^{n}. It is also the departure point for many other more sophisticated optimization algorithms. Despite its simplicity and notoriety was only in 1995 that its convergence theory was completed - see [8] and [2] -. In [8] the stepsize t_{k} is calculated by means the addition of a term of proximal regularization at the one-dimensional search. In [2] other two different way for the calculus of the stepsize were introduced. For the first one it is necessary that Lipschitz constant for the gradient of the objective function be known, which may possible to take t_{k} from a given sequence satisfying some related constraints. The second way is an Armijo-type search. With respect to minimize a convex function over a convex subset of R^{n} it is known the so called projected subgradient method. Its completed analysis of convergence can be found in [1]. Actually, in [1], the authors proved the convergence of the generated sequence to a solution point for problems in Hilbert spaces.

From another point of view, an extended class of non- convex constrained minimization problems can be seen as minimization problems in Riemannian manifolds. The study of the extension of known optimization methods to solve minimization problems over Riemannian manifolds was the subject of various works -see [4], [5], [7], [10], [11] and their references.

The gradient method as defined in [2] was modified in [4], [5] and [10] in order to use it in the solution of optimization problems in Riemannian manifolds. By means of these modifications, the authors of [4], [5] and [10] obtained the same convergence results as in [2] when the sectional curvature of the Riemannian manifold is nonnegative.

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

The extension of the subgradient method to solve optimization problems in Riemannian manifolds is studied in [7]. The authors obtain the same convergence results as in [3] when the Riemannian manifolds is complete and with non-negative sectional curvature.

In this paper we modify the gradient method with proximal regularization in the one-dimensional search of the stepsize, i.e., as defined in [8], aiming its use in the solution of optimization problems in Riemannian manifolds. We will obtain the same results of convergence, namely, if the problem has solution, the objective function is convex and sectional curvature is non-negative, then the sequence generated by our method converges to a solution.

2 Basic concepts

In this section, we introduce some fundamental properties and notations of Riemannian manifolds. Throughout this paper, all manifolds are smooth and connected. All functions and vector fields are also assumed to be smooth. These basic facts can be find in any introductory book on Riemannian Geometry for example [6] and [9].

Given a manifold M, denote by X (M) the space of vector fields over M and by T_{x}M the tangent space of M at x and by F(M) the ring of functions over M. Let M be endowed with a Riemannian metric ⟨, ⟩, with corresponding norm denoted by | |, so that M is now a Riemannian manifold. Recall that the metric can be used to define the length of piecewise smooth curves γ : [a, b] → M joining points x and y in

M, i.e., such that γ(a) = x and γ(b) = y, by l(γ) = ∫_{a}^{b} |γ′(t)|dt, and, moreover, by

minimizing this length functional over the set of all such curves we obtain a distance d(p, q) which induces the original topology on M. Also, the metric induces a map f ∈ F(M) ↦ grad f ∈ X (M) which associates to each f its gradient via the rule ⟨grad f, X⟩ = df(X), X ∈ X (M). The chain rule generalizes to this setting in the usual way: (f ∘ γ)′(t) = ⟨grad f(γ(t)), γ′(t)⟩ . In particular, if f assumes either a maximum or a minimum value at a point x ∈ M, then grad f(x) = 0. More generally, points where grad f vanishes are called critical points of f.

Let ∇ be the Levi-Civita connection associated to (M, ⟨, ⟩). If γ is a curve joining points x and y in M, then, for each t ∈ [a, b], ∇ induces an isometry (relative to ⟨, ⟩) P_{γ}(t) : T_{x}M → T_{γ(t)}M, the so-called parallel transport along γ from x to γ(t). When the reference to a curve joining x and y is not necessary, we use the notation P_{xy}. A vector field V along γ is said to be parallel if ∇_{γ′}V = 0. If γ′ itself is parallel we say that γ is a geodesic. The geodesic equation ∇ _{γ′}γ′ = 0 is a second order nonlinear ordinary differential equation, hence γ is determined by its position and velocity at one point as far as it is defined. It is easy to check that |γ′| is constant. We say that γ is normalized if |γ′| = 1. The restriction of a geodesic to a closed bounded interval is called a goedesic segment. A geodesic segment joining p and q in M is said to be minimal if its length equals d(p, q).

A Riemannian manifold is complete if geodesics are defined for any values of t. Hopf-Rinow’s theorem asserts that if this is the case then any pair of points, say x and y, in M can be joined by a (not necessarily unique) minimal geodesic segment. Moreover, (M, d) is a complete metric space, and bounded and closed subsets are compact. In this paper, all manifolds are assumed to be complete. The exponential map exp_{x} : T_{x}M → M is defined by exp_{x}v = γ_{v}(1, x), where γ(.) = γ_{v}(., x) is the geodesic by it position x and velocity v at one point as far as it is defined. In this case, we can prove that, exp_{x}tv = γ_{v}(t, x) for any values of t.

One of the fundamental objects of Riemannian manifolds is the curvature tensor R defined for X, Y, Z ∈ X (M) by

R(X, Y)Z = ∇_{X}∇_{Y} Z − ∇_{Y} ∇_{X}Z − ∇_{[X,Y]}Z,

where [ , ] is the Lie bracket. Clearly, R is a tensor of type (3,1). Given x ∈ M and a plane σ ⊂ T_{x}M, the quantity

K(u, v) = ⟨R(u, v)v, u⟩/(||u||^{2}||v||^{2} − ⟨u, v ⟩^{2})

does not depend on the basis {u, v} ⊂ σ. Hence, K(u, v) = K( σ) depends only on σ and is called the sectional curvature of σ at x. In the section 4.2 of this paper, we will be mainly interested in Riemannian manifolds for which K(σ) ≥ 0 for any σ. Such manifolds are referred to as manifolds with nonnegative curvature. A fundamental geometric property of this class of manifolds is that the distance between geodesics issuing from one point is, at least locally, bounded from above by the distance between the corresponding rays in the tangent space. A global formulation of this general principle is the law of cosines that we now pass to describe.

A geodesic hinge in M is a pair of normalized geodesics segment γ_{1} and γ_{2} such that γ_{1}(0) = γ_{2}(0) and at least one of them, say γ_{1}, is minimal. From now on l_{1} = l(γ_{1}), l_{2} = l(γ_{2}), l_{3} = d(γ_{1}(l_{1}), γ_{2}(l_{2})) and α =<)(γ′_{1}(0), γ′_{2}(0)).

Theorem 2.1 (Law of cosines) In a complete Riemannian manifold with nonnegative curvature, with the notation introduced above, we have

(1)  l_{3}^{2} ≤ l_{1}^{2} + l_{2}^{2} − 2l_{1}l_{2} cos α.

Proof. see [4] and [5]. □

We say that f : M → R is convex if, for each geodesic γ : R → M, f ∘ γ : R → R is convex as a real function, namely,

f(γ((1 − λ)a + λb)) ≤ (1 − λ)f(γ(a)) + λf(γ(b)),

for any λ ∈ [0, 1]. We state now a necessary and sufficient conditions for convexity.

Theorem 2.2 A function f : M → R is convex if and only if, for any p ∈ M and any geodesic γ : [0, +∞) → R such that γ(0) = p, we have

(2)  f(γ(t)) − f(p) ≥ t⟨grad f(p), γ′(0)⟩.

Proof. See, for example, [5] and [11] .

□

Perhaps the most important consequence of this theorem is the following.

Corollary 1 If f : M → R is convex then all its critical points are global minimum points.

Proof. Immediately.

□

3 The Proximal regularization

Let M be a complete Riemannian manifold. We will consider the optimization problem

(3)  min_{x∈M} f(x),

where f: M → R is a continuously differentiable function. The steepest descent method for the problem (3) is given bellow. Algorithm 1 (Classical steepest descent Method).

Take x_{0} ∈ M.

For k = 0, 1, … define

t_{k} = argmin_{t≥0}f(exp_{x_{k}}(−t grad f(x_{k}))),
x_{k+1} = exp_{x_{k}}(−t_{k}grad f(x_{k})).

Therefore t_{k} is a minimizer of the restriction of the f on the geodesic starting at x_{k} with tangent vector −grad f(x_{k}) . By introduction of a proximal regularization in the search of the stepsize t_{k} we modify the steepest descent method and replace it by the following algorithm: Algorithm 2 (Regularized steepest descent Method).

Our Algorithm 2 requires an exogenous sequence, {λ_{k}}, of real numbers, such that, for all k, λ′ ≤ λ_{k} ≤ λ′′, where 0 < λ′ ≤ λ′′. Initialization Step. Take x_{0} ∈ M. Iterative Step. For k = 0, 1, … define

(4)  φ_{k}(t) = f(exp_{x_{k}}(−tgrad f(x_{k}))) + t^{2}λ_{k}||grad f(x_{k})||^{2},

calculate

(5)  t_{k} = argmin_{t≥0} φ_{k}(t)

and set

(6)  x_{k+1} = exp_{x_{k}}(−t_{k}grad f(x_{k})).

We assume that problem (3) has solutions. Set f^{∗} = min_{x∈M} f(x).

Proposition 1. Let {x_{k}} given by the Algorithm 2. The sequence {x_{k}} is well defined and, for all k

(7)  ⟨ grad f(x_{k+1}) , P_{x_{k} x_{k+1}}grad f(x_{k}) ⟩ = 2λ_{k} t_{k}||grad f(x_{k})||^{2},

where P_{x_{k} x_{k+1}} is the parallel transport along exp_{x_{k}}(−tgrad f(x_{k})) from x_{k} to x_{k+1}. Proof. By induction, suppose that x_{k} is known. We have two cases. In the first case grad f(x_{k}) = 0. In this case φ_{k}(t) = f(x_{k}), for all t, and therefore any t ≥ 0 is solution of (5) and by (6) holds x_{k+1} = x_{k}. In second case grad f(x_{k}) ≠ 0. In this case

(8)  φ_{k}(t) ≥ f^{∗} + t^{2}λ_{k}||grad f(x_{k})||^{2}

for all t ≥ 0. Taking limit in (8) we get lim_{t→∞} φ_{k}(t) = ∞, then (5) has solution and x_{k+1} is defined. Since φ′_{k}(t_{k}) = 0 , from chain rule and (6), the equality (7) holds. □

From now on {x_{k}} and {t_{k}} refers to the sequences generated by Algorithm 2.

4 Convergence analysis

With our results, which we present next, we show that the techniques to solve optimization problems in R^{n} from [8] can be extended to solve problems in Riemannian manifolds.

4.1 Weak convergence

Without hypothesis concerning the curvature of Riemannian manifold M and convexity of f, we will prove that if x_{0} belongs to a bounded level set of f, then {x_{k}} converges weakly, namely, it is bounded, the distance between consecutive iterates goes to zero and all its cluster points are critical points.

Theorem 4.1 For all k,

(9)  f(x_{k+1}) ≤ f(x_{k}) − λ_{k}t_{k}^{2}||grad f(x_{k})||^{2}.

Furthermore,

i) The sequence {f(x_{k})} is decreasing and convergent. In particular, if level set M^{0} = {x ∈ M ; f(x) ≤ f(x_{0})} is bounded, then the sequence {x_{k}} ⊂ M^{0} is bounded too.

ii) ∑_{k=0}^{∞} t_{k}^{2}||grad f(x_{k})||^{2} < ∞. Moreover, lim_{k→∞} d(x_{k}, x_{k+1}) = 0.

iii) If \overline{x} is a cluster point of the sequence \{x_{k}\}, then grad f(\overline{x}) = 0.

Proof. Definition of t_{k} at (5) implies (9). Item (i) is an immediate consequence of (9).

To prove item (ii) observe that

\begin{aligned}∑_{k=0}^{n} t_{k}^{2}||grad f(x_{k})||^{2} & ≤ & \frac{1}{λ′} (f(x_{0}) − f(x_{k+1})) \\ & ≤ & \frac{1}{λ′} (f(x_{0}) − f^{∗}), \end{aligned}

and that d(x_{k}, x_{k+1}) ≤ t_{k}||grad f(x_{k})||.

Now, let x̄ a cluster point of sequence {x_{k}} and {x_{k_{j}}} the subsequence of {x_{k}} which converges to x̄. From item (ii) the sequence {x_{k_{j}+1}} converges also to x̄.

From Proposition 1,

(10)  ⟨grad f(x_{k_{j}+1}), P_{x_{k_{j}} x_{k_{j} +1}}grad f(x_{k_{j}})⟩ = 2λ_{k_{j}}t_{k_{j}}||grad f(x_{k_{j}})||^{2}.

The Riemannian metric, the parallel transport and gradient field are continuous, and then

(11)  lim_{j→∞} ⟨ grad f(x_{k_{j}+1}) , P_{x_{k_{j}} x_{k_{j} +1}}grad f(x_{k_{j}}) ⟩ = ||grad f(x̄)||^{2}.

Theorem 4.1 item (ii) implies that lim_{j→∞} t_{k_{j}}||grad f(x_{k_{j}})|| = 0. Then

(12)  lim_{j→∞} 2λ_{k_{j}} t_{k_{j}}||grad f(x_{k_{j}})||^{2} = 0

because {λ_{k_{j}}} is bounded.

From (10), (11) and (12) it follows that grad f(x̄) = 0 and item (iii) is proved. □

4.2 Full convergence

To achieve the full convergence of {x_{k}} we need convexity of f and the nonnegativity of the sectional curvature of M, but we don’t need the existence of bounded level set of f. Proposition 2. Let M be a Riemannian manifold with nonnegative curvature. Let f: M → R be a convex function. Then, for any y ∈ M we have

(13)  d^{2}(x_{k+1}, y) ≤ d^{2}(x_{k}, y) + t_{k}^{2}||grad f(x_{k})||^{2} + 2t_{k}(f(y) − f(x_{k}))

for all k. Proof. See, for example, [4], [5], [10].

Lemma 1 Let (M , d) be a complete metric space. If the sequence {y_{k}} ⊂ M has a cluster point \overline{y} satisfying

(14)  d^{2}(y_{k+1} , \overline{y}) ≤ d^{2}(y_{k}, \overline{y}) + ϵ_{k},

for some sequence \{ϵ_{k}\}, such that ϵ_{k} ≥ 0 and ∑_{k=0}^{∞} ϵ_{k} < ∞, then lim_{k→∞} y_{k} = \overline{y}.

Proof. See [5].

Consider the set O = {z ∈ M : f(z) ≤ inf_{k→∞} f(x^{k})}. Because we are assuming

that problem (3) has solutions, then O is nonempty and, by item (i) of Theorem 4.1 and continuity of f any cluster point of {x_{k}} is in O.

Theorem 4.2 Let M be a Riemannian manifold with non-negative curvature. Let f: M → R be a convex function. Then the sequence {x_{k}} converges to a minimizer point of f .

Proof. Take y in O. From Proposition 2 we have

(15)  d^{2}(x_{k+1} , y) ≤ d^{2}(x_{k} , y) + t_{k}^{2}||grad f(x_{k})||^{2}

for all k. The least inequality implies

(16)  d^{2}(x_{k+1} , y) ≤ d^{2}(x_{0} , y) + ∑_{j=0}^{k} t_{k}^{2}||grad f(x_{k})||^{2}

for all k. From Proposition 4.1 item (ii) it follows that the sequence {x_{k}} is bounded. Take \overline{x} a cluster point of \{x_{k}\} and observe that the equation (16) holds for y = \overline{x}. By equation (16) and setting ϵ_{k} = t_{k}^{2}||grad f(x_{k})||^{2} in the Lemma 1 we have lim_{k→∞} x_{k} = \overline{x}.

Therefore, from Theorem 4.1 item (iii), convexity of function f and Corollary 1 it follows that \overline{x} its minimizer.

□

5 Final remarks

The algorithm proposed in [8] solves unconstrained convex problem in R^{n}. Our algorithm 2 solves constrained non-convex problem in R^{n} when the constraint set is a Riemannian manifold. Then, we can say that algorithm 2 generalizes, in a certain sense, the algorithm presented in [8], namely, if the Riemannian manifold is the Euclidean space R^{n} then both algorithms are the same. The algorithm in [1] solves constrained convex problems in Hilbert spaces, in particular, in the R^{n}. While the problems solved by [1] have to be convex , the problems solved by our algorithm are convex in the Riemannian sense, but they may be non-convex in the usual sense. We remark that the techniques used in the full convergence proof impose restrictions about the manifold, that is, we need non-negative curvature of the Riemannian manifold. It remains to remove this hypothesis.

References

[1] Alber, Y. I., Iusem, A. N. and Solodov, M. V., On the projected subgradient method for nonsmooth convex optimization in a Hilbert space, Mathematical Programming 81 (1998) pp 25-35.

[2] Burachik, R. S., Graña Drummond, L. M., Iusem, A. N. and Svaiter, B. F., Full convergence of the steepest descent method with inexact line searches, Optimization 32 (1995) pp 137-146.

[3] Correa, R. and Lemaréchal, C., Convergence of Some Algorithms for Convex Minimization, Mathematical Programming, Vol. 62 (1993) pp. 267–275.

[4] da Cruz Neto, J. X. and Oliveira, P. R., Geodesic Methods in Riemannian Manifolds, Universidade Federal do Rio de Janeiro, Research Report 95–10 PESC/COPPE (1995).

[5] da Cruz Neto, J. X., Lima, L. L. and Oliveira, P. R., Geodesic Algorithm in Riemannian Manifolds, Balkan Journal of Geometry and Its Applications, Vol. 3, 2 (1998) pp. 89 - 100.

[6] do Carmo, M. P., Riemannian Geometry, Boston, Birkhauser (1992).

[7] Ferreira, O. P. and Oliveira, P. R., Subgradient Algorithm on Riemannian Manifolds, Journal of Optimization Theory and Applications, 97,1 (1998), pp 93-104.

[8] Iusem, A. N. and Svaiter, B. F., A Proximal Regularization of the Steepest Descent Method, Recherche opérationnelle/Operations Research 29,2 (1995) pp 123-130.

[9] Sakai, T., Riemannian Geometry, Translations of Mathematical Monographs, vol. 149, American Mathematical Society, Providence, R.I. (1996).

[10] Udrişte, C., Convex Functions and Optimization Methods on Riemannian Manifolds, Mathematics and its Applications, Vol. 297, Kluwer Academic Publishers [11] Udrişte, C., Sufficient Decrease Principle on Riemannian Manifolds, Balkan

Journal of Geometry and Its Applications, 1,2 (1996), pp 111-123.

J.X. da Cruz Neto, DM/CCN/ Universidade Federal do Piauí, Campus da Ininga, 64.049-550, Teresina, PI, Brazil, e-mail: jxavier@ufpi.br ,

O.P. Ferreira, IME/Universidade Federal de Goiás, Campus Samambaia, Caixa Postal 131, CEP 74001-970, Goiânia, GO, Brazil, e-mail: orizon@mat.ufg.br.

L.R.Lucambio Perez, IME/Universidade Federal de Goiás, Campus Samambaia, Caixa Postal 131, CEP 74001-970, Goiânia, GO, Brazil, e-mail:lrlp@mat.ufg.br