Sufficient Decrease Principle on Riemannian Manifolds

Constantin Udrişte

Abstract

Tools from Riemannian geometry (suitable Riemannian metric, exponential map, search along geodesics, covariant differentiation, sectional curvature, etc) are now used in Mathematical Programming to obtain deeply theoretical results and practical algorithms [3]-[11].

§1 lists basic propositions appearing in the numerical finding of a critical point of a real function defined on a Riemannian manifold. 2 – 3 develop the steplength analysis in terms of geodesics and Riemannian version of Taylor formula (which contains the parallel translation along geodesics), insisting on sufficient decrease principle. 4 analyses the strong influence of the sectional curvature on descent algorithms. 5 proves that the central path of a convex program is in fact a minus gradient line with respect to a suitable Riemannian metric.

The main theorems refer to the convergence of the sequence

x_{i+1} = exp_{x_{i}}(ω_{i}t_{i}X_{i}),

produced by a descent method, to a critical point of a function f, the convergence of the sequence

{df(x_{i})(e_{i}) | e_{i} = X_{i}/ ∥ X_{i} ∥}

to zero, and the convergence of the sequence of distances {d(x_{i}, x_{i+1})} to zero.

Mathematics Subject Classification: 49M10, 65K05, 53C21, 53C22, 58C27 Key words: zeros, geodesics, sufficient decrease, forcing functions, reverse modulus, curvature and descent algorithms, central path.

1 Numerical methods for finding zeros of a tensor field

Let (M, g) be a complete finite-dimensional Riemannian manifold. The Riemannian metric g produces:

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

1) the energy (halph of square of the norm) of a tensor field; in particular, for a vector field X we have the energy

f = \frac{1}{2} ∥ X ∥^{2}= \frac{1}{2}g(X, X);

2) the length L(γ) = ∫_{a}^{b} ∥ γ̇(t) ∥ dt of a piecewise C^{1} curve

γ : [a, b] → M;

3) the Riemannian connection ∇, the parallel translation, and the geodesics;

4) the distance

d(x, y) = inf_{γ∈Γ} L(γ),

where Γ is the set of all piecewise C^{1} regular curves γ : [a, b] → M joining the points x, y ∈ M, i.e., γ(a) = x, γ(b) = y;

5) the raising and the lowering of the indices of tensor components;

6) the sectional curvature of the manifold; etc.

The topology induced by the distance d on M coincides with the manifold topology of M. Also (M, d) is a complete metric space. The open ball in (M, d) with center x_{0} and radius r is denoted by B(x_{0}, r).

The completeness of (M, g) implies the fact that any geodesic γ : [0, 1] → M can be extended to a geodesic of type γ : R → M and that any two points of M can be joined by a minimal geodesic.

Let γ : [0, 1] → M be a geodesic joining the points γ(0) = x, γ(1) = y. The parallel translation from x to y along γ will be denoted by τ_{xy}.

Let γ(t) = exp_{x}(tX) be the geodesic which verifies the initial conditions γ(0) = x, γ̇(0) = X ∈ T_{x}M. We know that for any x ∈ M there exists ϵ > 0 such that X ∈ T_{x}M, ∥ X ∥< ϵ imply d(x, exp_{x} X) =∥ X ∥.

Generally, zeros of a C^{∞} vector field or 1–form are global minimum points, and hence critical points, of their energies. The numerical methods used for the finding of such zeros has as base iterative procedures of the type [3]–[11]

(1)  x_{i+1} = exp_{x_{i}}(r_{i}t_{i}X_{i}),

where the vector X_{i} ∈ T_{x_{i}}M indicates the direction and sense of moving from the starting point x_{i}, the number t_{i} determines the steplength on the geodesic which starts from x_{i} tangent to X_{i}, and the number r_{i} is a relaxation parameter. These procedures do not depend on the local coordinate system, but depend on geodesics and the sectional curvature of the manifold.

Let us consider a C^{∞} 1–form ω. If x_{i} is not a zero of the 1–form ω, then we select X_{i} ∈ T_{x_{i}}M by the condition ω(x_{i})(X_{i}) < 0 having in mind at least two reasons:

1) if ω = df, f : D ⊂ M → R, the preceding inequality shows that X_{i} determines a direction and sense of decreasing of f, i.e., df(X_{i}) < 0;

2) if f = \frac{1}{2}g^{−1}(ω, ω) is the energy of ω and ∇ω(x_{i}) is nondegenerate, then the equalities

df(Y_{i}) = g^{−1}(∇_{Y_{i}}ω, ω) = ω(g^{−1}∇_{Y_{i}}ω), X_{i} = g^{−1}∇_{Y_{i}}ω

and the inequality ω(x_{i})(X_{i}) < 0 show that Y_{i} determines a descent direction and sense of the energy f (this idea corresponds to Riemann–Newton method for finding zeros of a 1–form). Remark. The ideas in this paper hold true for general tensor fields, though they are formulated here for 1–forms. Let T be a C^{∞} tensor field on M and f = \frac{1}{2} ∥ T ∥^{2} be its energy. The zeros of T, i.e., the solutions of the algebraic system T (x) = 0, are global minimum points, and hence critical points, of the energy f. Therefore an extended descent method, for example an extendend Riemann–Newton method, can be used to find zeros of any tensor field.

Let x_{∗} be a zero of the 1–form ω. If (∇ω)(x_{∗}) is nondegenerate, then the zero x_{∗} is called nondegenerate. The Riemann–Newton method for finding of the point x_{∗} was studied in, [3]–[11].

In this paper we refer especially to the case ω = df, where f : D ⊂ M → R is a C^{1} function. The solutions of the system df(x) = 0 are called critical points of f. The study of the convergence of the numerical procedure (1) towards the critical point x_{∗} of f, or to a minimizer f_{∗} of f, is based on the following propositions [6]

(2) f(x_{i} + 1) ≤ f(x_{i}), i = 1, 2, …

(3)  lim_{i→∞} x_{i} = x_{∗}, df(x_{∗}) = 0
(4)  lim_{i→∞} df(x_{i})(e_{i}) = 0, where e_{i} = X_{i}/ ∥ X_{i} ∥
(5)  lim_{i→∞} df(x_{i}) = 0

(6) df(x_{i})(X_{i}) ≤ −ε ∥ X_{i} ∥, ϵ > 0, ∀i ≥ i_{0}

(7)  lim_{i→∞} d(x_{i}, x_{i+1}) = 0.

In §2 - §3 we shall analyse especially the basic proposition (4) showing that its validity depends only upon the steplength of the algorithm and on very mild conditions for f itself. In the theorems 2.4, 3.4 appears also the proposition (7).

2 Sufficient decrease principle on Riemannian manifolds

Let (M, g) be a complete, finite–dimensional Riemannian manifold. In this paragraph we shall develop the steplength analysis and we shall prove that proposition (4) is true for certain steplength algorithms and arbitrary X_{i} ≠ 0. The decreasing condition (2) is not usually enough to imply (4), even if the inequality is strict. There exist however decreasing conditions which imply (4). These type of decreasing is called a sufficient decrease and it is usual described using the forcing functions. 2.1. Definition. A function σ : [0, ∞) → [0, ∞) for which the convergence of the sequence {σ(t_{i})} to zero implies the convergence of {t_{i}} to zero, for any sequence {t_{i}}, is called a forcing function. Example. Any function σ : [0, ∞) → [0, ∞) which is increasing and positive definite is a forcing function. 2.2. Theorem (Sufficient decrease principle). If f : D ⊂ M → R, and

1) f is of class C^{1}, 2) f is bounded below on D_{0} ⊂ D,

3) there exists a forcing function σ such that

(8)  f(x_{i+1}) − f(x_{i}) ≤ −σ(| df(x_{i})(e_{i}) |), e_{i} = X_{i}/ ∥ X_{i} ∥,

then the proposition (4) is satisfied. Proof. By (2)–(3), the sequence {f(x_{i})} is convergent as a decreasing bounded sequence. Hence lim_{i→∞}(f(x_{i}) − f(x_{i+1})) = 0, and consequently by (3) the proposition (4) holds true.

In the following we shall look for estimations of type (8), for various steplength algorithms. For these it is necessary to be sure that the sequence generated by (1) remains in D_{0}. Denote D_{1} = {x ∈ D | f(x) ≤ f(x_{1})} and D_{10} the path–connected component of the sublevel set D_{1} containing x_{1}. 2.3. Lemma. If f : D → R, where D ⊂ M is an open set, and

1) f is continuous on D,

2) f is of class C^{1} on the compact set D_{10} for some x_{1} ∈ D, then for any x ∈ D_{10} and X ∈ T_{x}M with df(x)(X) < 0, and γ(t) = exp_{x}(tX), there exists t_{∗} such that f(x) = f(γ(t_{∗})) and γ(t) ∈ D_{10} for any t ∈ (0, t_{∗}].

If s > 0 is a number satisfying f(γ(t)) < f(x), ∀γ(t) ∈ γ([0, s]) ∩ D_{10}, then γ([0, s]) ⊂ D_{10}. Proof. Let

J = {t_{1} > 0 | γ([0, t_{1}]) ⊂ D, f(γ(t)) < f(x), ∀t ∈ (0, t_{1}]}

and t_{∗} = sup J. The number t_{∗} is well–defined since the set J is nonvoid. By compactness of D_{10}, we have t_{∗} < ∞ and γ([0, t_{∗}]) ⊂ D_{10} . Suppose f(γ(t_{∗})) < f(x). Since D is open and f is continuous, we can select δ > 0 such that γ(t) ∈ D and f(γ(t)) < f(x), ∀t ∈ [t_{∗}, t_{∗} + δ], in contradiction with the definition of t_{∗}. It rests f(x) = f(γ(t_{∗})). The last statement is immediate because s < t_{∗}.

Denote by τ_{xy} the parallel translation from x to y along a geodesic joining the points x, y. 2.4. Theorem (Majoration principle). Let f : D → R, where D ⊂ M is open and f is of class C^{1}. Suppose that D_{10} is a compact set and

∥ df(x) − τ_{xy}^{−1}df(y) ∥≤ ad(x, y), ∀x, y ∈ D_{10}.

If the sequence {x_{i}} generated by (1) satisfies the conditions:

- {X_{i}} is a sequence of nonzero vectors, each vector being fixed by the conditions X_{i} ∈ T_{x_{i}}M, df(x_{i})(X_{i}) ≤ 0;

- the steplength t_{i} and the relaxation parameter r_{i} satisfy

t_{i} = −(a ∥ X_{i} ∥)^{−1}df(x_{i})(e_{i}), ϵ ≤ r_{i} ≤ 2 − ϵ, i = 1, 2, ...

with

e_{i} = X_{i}/ ∥ X_{i} ∥, ϵ ∈ (0, 1),

then the sequence {x_{i}} remains in D_{10}, and the propositions (4), (7) are satisfied.

Proof. We use the complete induction. Suppose x_{i} ∈ D_{10}. If df(x_{i})(X_{i}) = 0, then x_{i} = x_{i+1}. Therefore we impose df(x_{i})(X_{i}) < 0.

Let γ_{i}(t) = exp_{x_{i}}(tX_{i}). From

f(γ_{i}(t)) = f(x_{i}) + tdf(x_{i})(X_{i}) + t ∫_{0}^{1}(τ^{−1}df(γ_{i}(st)) − df(x_{i}))(X_{i})ds,

d(x, y) = st ∥ X_{i} ∥,

it follows

f(γ_{i}(t)) − f(x_{i}) ≤ tdf(x_{i})(X_{i}) + \frac{1}{2}at^{2} ∥ X_{i} ∥^{2},

whenever the geodesic γ_{i}(t) is included in D. Also, Lemma 2.3, with s = (2−ϵ)t_{i}, ensures x_{i+1} ∈ D_{10}. We have

f(x_{i}) − f(x_{i+1}) ≥ −r_{i}t_{i}df(x_{i})(X_{i}) − \frac{a}{2}(r_{i}t_{i} ∥ X_{i} ∥)^{2} =

= \frac{r_{i}}{a} (df(x_{i})(e_{i}))^{2} − \frac{r_{i}^{2}}{2} (df(x_{i})(e_{i}))^{2} = \frac{1}{2a} (2r_{i} − r_{i}^{2}) (df(x_{i})(e_{i}))^{2} ≥

≥ \frac{1}{2a}ϵ(2 − ϵ)(df(x_{i})(e_{i}))^{2}

since 2r_{i} − r_{i}^{2} = 1 − (1 − r_{i})^{2} ≥ 1 − (1 − ϵ)^{2} = ϵ(2 − ϵ). We remark that σ(t) = \frac{ϵ}{2a}(2 − ϵ)t^{2} is a forcing function and hence

lim_{i→∞} df(x_{i})(e_{i}) = 0.

Finally, if the selected geodesic is minimal, then

d(x_{i}, x_{i+1}) = r_{i}t_{i} ∥ X_{i} ∥= −r_{i}a^{−1}df(x_{i})(e_{i})

implies

lim_{i→∞} d(x_{i}, x_{i+1}) = 0.

3 Reverse modulus of continuity of a 1–form as forcing function

In the sequel, the forcing function ct^{2} is replaced by a more complex forcing function. In this sense the following ideas hold true for general 1–forms, though they are formulated for ω = df, where f : D ⊂ M → R is a C^{1} function.

Let τ_{xy} be the parallel translation along a geodesic joining x to y. 3.1. Definition. Let f : D ⊂ M → R be a function of class C^{1}. Assume that on some D_{0} ⊂ D we have

s = sup {∥ df(x) − τ_{xy}^{−1}df(y) ∥, x, y ∈ D_{0}} > 0,

and denote

β(t) = inf {d(x, y) | x, y ∈ D_{0}, ∥ df(x) − τ_{xy}^{−1}df(y) ∥≥ t} , t ∈ [0, s).

The function

δ : [o, ∞) → [0, ∞), δ(t) = \{ \begin{matrix}β(t) & for & t ∈ [0, s) \\ lim_{t↗s} β(t) & for & t ∈ [s, ∞) \end{matrix}

is called the reverse modulus of continuity of the 1–form df on D_{0}.

The function δ is increasing and δ(0) = 0. The following lemma shows that δ is a forcing function. 3.2. Lemma. If the 1–form df is uniformly continuous on D_{0} ⊂ D and s is strictly positive, then δ(t) > 0, ∀t > 0. Proof. Suppose δ(t) = 0 for some t > 0. Then, given ϵ > 0, ∃x, y ∈ D_{0} with ∥ df(x) − τ_{xy}^{−1}df(y) ∥≥ t and d(x, y) ≤ ϵ, contradicting the uniform continuity of df.

Let γ(t) = exp_{x_{i}}(tX_{i}), t ∈ [0, 1]. The sufficient decrease principle reduces to the hypotheses that τ_{x_{i}γ(t)}^{−1}df(γ(t))(X_{i}) is sufficiently smaller with respect to df(x_{i})(X_{i}). In other words, for μ ∈ [0, 1), the suitable steplength t_{i} can be defined as

(9)  t_{i} = min {t ≥ 0 | τ_{x_{i}γ(t)}^{−1}df(γ(t))(X_{i}) = μdf(x_{i})(X_{i})} .

3.3. Theorem. Suppose f : D ⊂ M → R is of class C^{1} on the open set D. If D_{10} is compact, μ ∈ [0, 1), ϵ ∈ (0, 1] and the iterative process (1) works under df(x_{i})(X_{i}) ≤ 0, X_{i} ≠ 0, ϵ ≤ r_{i} ≤ 1, and the condition (9), then the sequence {x_{i}} is included in D_{10} , it is strongly downward and the proposition (4) is satisfied. Proof. We use the complete induction. Suppose x_{i} ∈ D_{10}. If df(x_{i})(X_{i}) = 0, then t_{i} = 0 and hence x_{i+1} = x_{i}. Consequently it is necessary df(x_{i})(X_{i}) < 0. Then Lemma 2.3 assures the existence of s_{i} > 0, with the geodesic γ(s) = exp_{x_{i}}(sX_{i}), s ∈ [0, s_{i}] included in D_{10} and f(x_{i}) = f(x_{i+1}). By the meanvalue theorem, there exists ŝ ∈ (0, s_{i}) with τ_{x_{i}γ(ŝ)}^{−1}df(γ(ŝ))(X_{i}) = 0. Using the continuity of df, the equation in (9) has a solution in (0, s_{i}) and df(x_{i})(X_{i}) < 0 implies the existence of t_{i} > 0. Since r_{i} ≤ 1, the point x_{i+1} is well defined and x_{i+1} ∈ D_{10}.

On the other hand

(10)  τ_{x_{i}γ(t)}^{−1}df(γ(t))(X_{i}) = μdf(x_{i})(X_{i}) < 0, ∀t ∈ [0, r_{i}t_{i}),

and hance f(γ(t)) is decreasing on [0, r_{i}t_{i}]. Hence

f(x_{i}) ≥ f (γ_{x_{i}x_{i+1}}(t)) ≥ f(x_{i+1}), ∀t ∈ [0, 1],

i.e., the sequence {x_{i}} is strongly downward in D_{10}.

For the last part suppose μ > 0. Then the meanvalue theorem and (10) give

(11)  f(x_{i}) − f(x_{i+1}) = −r_{i}t_{i}τ_{x_{i}γ(t)}^{−1}df(γ(t))(X_{i}) ≥ −t_{i}ϵμdf(x_{i})(X_{i}).

To avoid the triviality, we suppose that f is nonconstant on D_{10}. Lemma 3.2 shows that the reverse modulus of continuity of the 1–form df is a forcing function on D_{10}. From e_{i} = X_{i}/ ∥ X_{i} ∥,

(μ − 1)df(x_{i})(e_{i}) = τ_{x_{i}γ(t_{i})}^{−1}df(γ(t_{i}))(e_{i}) − df(x_{i})(e_{i}) ≤
≤∥ df(x_{i}) − τ_{x_{i}γ(t_{i})}^{−1}df(γ(t_{i})) ∥

and the definition of δ, we find

t_{i} ∥ X_{i} ∥≥ δ[(μ − 1)df(x_{i})(e_{i})].

Then (11) is continued by

(12)  f(x_{i}) − f(x_{i+1}) ≥ −t_{i} ∥ X_{i} ∥ ϵμdf(x_{i})(e_{i}) ≥ σ(−df(x_{i})(e_{i})),

where

σ(t) = μϵtδ((1 − μ)t), t ≥ 0.

Since σ is a forcing function, the proof is finished for μ > 0.

Let μ = 0. We replace the steplength t_{i} with t̄_{i} given by Theorem 3.3 for μ = \frac{1}{2} . Denoting x̄_{i+1} = γ(t̄_{i}) it follows f(x̄_{i+1}) ≥ f(x_{i+1}). Further the estimation (12) takes place with x̄_{i+1} instead of x_{i+1} for σ(t) = \frac{1}{2}ϵtδ (\frac{t}{2}) and hence

f(x_{i}) − f(x_{i+1}) ≥ f(x_{i}) − f(x̄_{i+1}) ≥ σ(−df(x_{i})(e_{i})).

Since this last idea is very important, it will be punctuated like Comparison principle. Suppose that two different steplength algorithms I, II produce from x_{i} the points x_{i+1}^{I} and xII_{i+1}. If

f(x_{i}) − f (x_{i+1}^{I}) ≥ σ(| df(x_{i})(e_{i}) |), e_{i} = X_{i}/ ∥ X_{i} ∥,

where σ is a forcing function, then it is enough to prove

f (x_{i+1}^{I}) ≥ f (x_{i+1}^{II})

in order to obtain

f(x_{i}) − f (x_{i+1}^{II}) ≥ f(x_{i}) − f (x_{i+1}^{I}) ≥ σ(| df(x_{i})(e_{i}) |).

Remark. The preceding theorem permits only relaxation factors satisfying r_{i} ≤ 1. Results for r_{i} > 1, require stronger conditions on f. 3.4.Theorem. Let D ⊂ M be open and f : D → R be of class C^{2}. Suppose that D_{10} is compact and

a ∥ X_{x} ∥^{2}≤ Hessf(X_{x}, X_{x}) ≤ b ∥ X_{x} ∥^{2}, ∀x ∈ D_{10}, ∀X_{x} ∈ T_{x}M,

where b ≥ a > 0. If μ ∈ [0, 1), ϵ ∈ (0, 1) and the sequence (1) is fixed by df(x_{i})(X_{i}) ≤ 0, X_{i} ≠ 0, with t_{i} in Theorem 3.3 and 1 ≤ r_{i} ≤ r̄ == 1 + (\frac{a}{b})^{\frac{1}{2}} · (1 − ϵ), then the sequence \{x_{i}\} is included in D_{10}, and the propositions (4), (7) are satisfied. Proof. We use the complete induction. Suppose x_{i} ∈ D_{10} and df(x_{i})(X_{i}) < 0. Already we know that t_{i} is well–defined and γ([0, t_{i}]) ⊂ D_{10}, f(x_{i+1}) = f(γ(t_{i})) < f(x_{i}). By the continuity of f, there exists t ∈ (t_{i}, r̄t_{i}] such that γ([0, t]) ⊂ D_{10}. Denoting y_{i+1} = γ(β), β ∈ (0, ϵt_{i}), τ = τ_{x_{i}x_{i+1}}, the Taylor formula with the rest in the integral form implies

f(x_{i}) − f(γ(t)) = (f(x_{i}) − f(y_{i+1})) + (f(y_{i+1}) − f(x_{i+1}))−
−(f(γ(t)) − f(x_{i+1})) = f(x_{i}) − f(y_{i+1}) + (β − t_{i})τ^{−1}df(x_{i+1})(X_{i})+
+(β − t_{i})^{2} ∫_{0}^{1}(1 − s)τ^{−1}Hessf(γ_{x_{i+1}}(s(t_{i} − β)X_{i}))(X_{i}, X_{i})ds−
−(t − t_{i})τ^{−1}df(x_{i+1})(X_{i})−
−(t_{i} − t)^{2} ∫_{0}^{1}(1 − s)τ^{−1}Hessf(γ_{x_{i+1}}(s(t_{i} − t)X_{i}))(X_{i}, X_{i})ds ≥

≥ f(x_{i}) − f(y_{i+1}) + (β − t)τ^{−1}df(x_{i+1})(X_{i})+

+\frac{1}{2}(t_{i} − β)^{2}a ∥ X_{i} ∥^{2} −\frac{1}{2}(t_{i} − t)^{2}b ∥ X_{i} ∥^{2}≥

≥ f(x_{i}) − f(y_{i+1}) + (ϵ − 1)t_{i}τ^{−1}df(x_{i+1})(X_{i})+

+\frac{1}{2}t_{i}^{2} ∥ X_{i} ∥^{2} [(1 − ϵ)^{2}a − \frac{a}{b}(1 − ϵ)^{2}b] =

= f(x_{i}) − f(y_{i+1}) + (ϵ − 1)μt_{i}df(x_{i})(X_{i}) > 0.

Consequently γ([0, r̄t_{i}]) ⊂ D_{10} and particularly x_{i+1} ∈ D_{‘0}.

We remark that

(μ − 1)df(x_{i})(X_{i}) = τ^{−1}df(x_{i+1})(X_{i}) − df(x_{i})(X_{i}) =
= t_{i} ∫_{0}^{1} τ^{−1}Hess(γ(stX_{i}))(X_{i}, X_{i})ds,

and hence

t_{i}b ∥ X_{i} ∥≥ (μ − 1)df(x_{i})(e_{i}) ≥ at_{i} ∥ X_{i} ∥≥ ad(x_{i}, x_{i+1}).

If μ > 0, we find

f(x_{i}) − f(x_{i+1}) ≥ (1 − ϵ)μt_{i} ∥ X_{i} ∥| df(x_{i})(e_{i}) ≥
≥ (1 − ϵ)μ[(1 − μ)/b][df(x_{i})(e_{i})]^{2}

and hence

lim_{i→∞} df(x_{i})(e_{i}) = 0, lim_{i→∞} d(x_{i}, x_{i+1}) = 0.

For μ = 0, we can apply the comparison principle. 3.5. Theorem. Let D ⊂ M be an open set, f : D → R be of class C^{1}, and D_{10} be compact. If the sequence

x_{i+1} = exp_{x_{i}}(t_{i}X_{i}), i = 1, 2, ...

is fixed by X_{i} ≠ 0 and

(13)  f(x_{i+1}) = min_{t}{f(γ(t)) | γ(t) = exp_{x_{i}}(tX_{i}) ∈ D_{10}},

then {x_{i}} is included in D_{10}, {x_{i}} is strongly downward and the proposition (4) is satisfied. Proof. If x_{i} ∈ D_{10}, then the connected part D_{10} of the set D_{i} : f(x) ≤ f(x_{i}), is compact and there exist t_{i} satisfying (13). Hence x_{i+1} ∈ D_{i0}. Suppose df(x_{i})(X_{i}) ≤ 0, and x̄_{i+1} is obtained as in Theorem 3.3 with μ = 0. Then f(x_{i+1}) ≤ f(x̄_{i+1}) and hence

f(x_{i}) − f(x_{i+1}) ≥ f(x_{i}) − f(x̄_{i+1}) ≥ σ(−df(x_{i})(e_{i})), e_{i} = X_{i}/ ∥ X_{i} ∥,

with σ(t) = \frac{1}{2}ϵtδ (\frac{t}{2}). Consequently lim_{i→∞} df(x_{i})(e_{i}) = 0.

As σ([0, t_{i}]) ⊂ D_{i0}, we have

f(x_{i}) ≥ f(γ(t)) ≥ f(x_{i+1}), ∀t ∈ [0, 1],

i.e., the sequence {x_{i}} is strongly downward.

4 Influence of the sectional curvature on descent algorithms

Denote by K the sectional curvature of the Riemannian manifold (M, g). If K > 0, then the adjacent geodesic starting at the some point tend to approximate one each other and consequently we have a liberality in selecting the decrease vector X_{i} and the steplength t_{i} along the corresponding geodesic, without distancing ourselves essentially from the critical point x_{∗} of the function f. If K < 0, then the behaviour of geodesics is contrary, namely, the adjacent geodesics of a given geodesic, all starting at a given point, will go away exponentially from it; consequently, on manifolds with negative curvature we are forced to select carefully the decrease vector X_{i} and the steplength t_{i}(either enough small number or enough great number for each i). 4.1. Topogonov Theorem. Let (M, g) be a complete Riemannian manifold with K ≥ H, and γ_{1}, γ_{2} be segments of normal geodesics in M with γ_{1}(0) = γ_{2}(0). Let ∑(H) be a 2–dimensional manifold with constant curvature H. Suppose that γ_{1} is a minimal geodesic and L(γ_{2}) ≤ \frac{π}{\sqrt{H}}, when H > 0. If γ̄_{1}, γ̄_{2} are two geodesics in ∑(H) satisfying γ̄_{1}(0) = γ̄_{2}(0), L(γ_{i}) = L(γ̄_{i}) = L_{i}, ang(γ̄′_{1}(0), γ̄′_{2}(0)) = ang (γ′_{1}(0), γ′_{2}(0)), then

d(γ_{1}(L_{1}), γ_{2}(L_{2})) ≤ d(γ̄_{1}(L_{1}), γ̄_{2}(L_{2})).

4.2. Corollary. Let (M, g) be a complete Riemannian manifold with K ≥ 0. If γ_{1}(t) = exp_{x}(tX_{1}), γ_{2}(t) = exp_{x}(tX_{2}) are normal geodesics (i.e., ∥ X_{1} ∥=∥ X_{2} ∥= 1), then

d(γ_{1}(t_{1}), γ_{2}(t_{2})) ≤∥ t_{2}X_{2} − t_{1}X_{1} ∥ .

4.3. Lemma. If f : M → R is a C^{1} convex function, {x_{i}} is generated by (1), with X_{i} = −gradf(x_{i}) and K ≥ 0, then

d^{2}(x_{i+1}, y) ≤ d^{2}(x_{i}, y) + t_{i}^{2} + 2\frac{t_{i}}{∥ X_{i} ∥}(f(y) − f(x_{i})), ∀y ∈ M.

Proof. Let γ_{1}(t) = exp_{x_{i}}(tX_{1}) be a minimal geodesic, with

γ_{1}(0) = x_{i}, γ_{1}(t_{1}) = y, t_{1} = d(x_{i}, y)

and let

γ_{2}(t) = exp_{x_{i}}(tX_{2}), df(X_{2}) < 0, X_{2} = X_{i} = − grad f(x_{i}),
γ_{2}(0) = x_{i}, γ_{2}(t_{i}) = x_{i+1}, t_{i} = t_{2}.

From Corollary 4.2 and the convexity of C^{1} functions, i.e.,

f(x_{i}) + t_{1}df(X_{1})(x_{i}) ≤ f(γ_{1}(t_{1})),

it follows

d^{2}(x_{i+1}, y) ≤ ∥t_{i} \frac{X_{i}}{∥ X_{i} ∥} − t_{1}X_{1}∥^{2} = t_{1}^{2} + t_{i}^{2} − 2\frac{t_{i}}{∥ X_{i} ∥}g(X_{i}, t_{1}X_{1}) ≤

≤ d^{2}(x_{i}, y) + t_{i}^{2} + \frac{2t_{i}}{∥ df(x_{i}) ∥}(f(y) − f(x_{i})).

In the hypotheses of Lemma 4.3, we have

d^{2}(x_{i+1}, z) ≤ d^{2}(x, z) + t_{i}^{2}, ∀i ∈ N, ∀z ∈ O,

where O = {z ∈ M | f(z) ≤ inf_{i}f(x_{i})}. 4.4. Theorem. Same hypotheses as in Lemma 4.3. Let O_{∗} be the set of all minimizers of f. If x_{∗} ∈ O_{∗} and x_{i} ∉ O_{∗}, then d(x_{i+1}, x_{∗}) < d(x_{i}, x_{∗}) for all t_{i} satisfying

0 < t_{i} < \frac{2}{∥ df(x_{i}) ∥}(f(x_{i}) − f(x_{∗})).

Proof. Lemma 4.3 with y = x_{∗} gives

d^{2}(x_{i+1}, x_{∗}) ≤ d^{2}(x_{i}, x_{∗}) + t_{i}^{2} + 2\frac{t_{i}}{∥ df(x_{i}) ∥}(f(x_{∗}) − f(x_{i})).

Since x_{i} ≠ x_{∗}, the inequality 0 < t_{i} < \frac{2}{∥df(x_{i})∥}(f(x_{i}) − f(x_{∗})) implies t_{i}^{2} + 2\frac{t_{i}}{∥df(x_{i})∥}(f(x_{∗}) − f(x_{i})) < 0.

In the hypotheses of Lemma 4.3, we can select a suitable steplength t_{i} for which the sequence (1) converges to x_{∗} and the sequence f(x_{i}) has an infimum [3], [8].

5 Central path of a convex program like minus gradient line

Let (M, g) be a complete n–dimensional Riemannian manifold. We consider the convex programming problem

max f_{0}(x) subject to f_{α}(x) ≤ 0, α = 1, ..., m; x ∈ M.

The interior of the feasible region F : f_{α}(x) ≤ 0 is denoted by F^{0}, and we accept the following assumptions: 1) F^{0} is nonemtpy; 2) F^{0} is bounded; 3) the functions −f_{0}, f_{α} are C^{2} convex functions on F^{0}.

The convexity of the functions f_{α} implies the total convexity of the set F^{0}. The logarithmic barrier function associated to the preceding convex program

is defined by

ϕ(x, μ) = −\frac{f_{0}(x)}{μ} − ∑_{α=1}^{m} ln(−f_{α}(x)),

where μ is the barrier strictly positive parameter. The first and the second covariant derivatives of ϕ with respect to the Riemannian connection induced by the metric g are

dϕ(x, μ) = −\frac{df_{0}(x)}{μ} + ∑_{α=1}^{m} \frac{df_{α}(x)}{−f_{α}(x)},

H(x, μ) = Hessϕ(x, μ) = −\frac{Hessf_{0}(x)}{μ} + ∑_{α=1}^{m} [\frac{Hessf_{α}(x)}{−f_{α}(x)} + \frac{df_{α}(x) ⊗ df_{α}(x)}{f_{α}(x)^{2}}] .

The Hessian H is positive semidefinite since ϕ is a convex function.

Suppose H is positive definite, and we use alternatively the Riemannian manifolds (M, g) and (M, H). The function ϕ is strictly convex on F^{0} in (M, g), and takes infinite values on the boundary ∂F. Consequently ϕ achieves the minimal value at a unique critical point x = x(μ), called the μ–center, solution of the system

\frac{−df_{0}(x)}{μ} + ∑_{α=1}^{m} \frac{df_{α}(x)}{−f_{α}(x)} = 0.

5.1.Definition. The set of all μ–centers, when μ runs from ∞ to 0, is called the primal central path. 5.2. Theorem. On the Riemannian manifold (M, g), the primal central path is a reparametrized integral curve of the vector field

−H^{−1}df_{0} = −gradf_{0}.

Proof. Deriving with respect to μ in the system which describes x(μ), via the covariant derivative induced by the Riemannian metric g, we obtain

μ^{2}H(x, μ) (\frac{dx}{dμ}) + df_{0}(x) = 0 or \frac{dx}{dμ} = −μ^{−2}H^{−1} ∘ df_{0}.

Consequently, the central path is a minus gradient line for the Riemannian metric μ^{2}H. By the substitution μ = −\frac{1}{u}, u ∈ (−∞, 0) we find \frac{dx}{du} = −H^{−1} ∘ f_{0}.

In other words, the central path is a reparametrized minus gradient line for the Riemannian metric H.

References

[1] J.Cheeger, D.Ebin, Comparison theorems in Riemannian geometry, North– Holland, Amsterdam, 1975.

[2] M.P.do Carmo, Riemannian geometry, Boston, Birkhauser, 1992.

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

[4] S.T.Smith, Optimization techniques on Riemannian manifolds, Fields Institute Communications, 3(1994), 113–136.

[5] C.Udrişte, Kuhn–Tucker theorem on Riemannian manifolds, Kolloquia Math.Soc. Janos Bolyai, Topics in Diff. Geometry, Debrecen, Hungary (1984), 1247–1259.

[6] C.Udrişte, Convergence of minimization methods on Riemannian manifolds, International Workshop on Differential Geometry and Its Applications, Bucharest, July 25–30, Scientific Bulletin, Politehnica University of Bucharest, 55, 3–4 (1993), 247–254.

[7] C.Udrişte, Minimization algorithms on Riemannian manifolds, Proceedings of the 23–rd Conference on Geometry and Topology, Cluj– Napoca, Romania, 1993, 185–193.

[8] C.Udrişte, Convex functions and optimization methods on Riemannian manifolds, Mathematics and Its Applications, 297, Kluwer Academic Publishers, 1994.

[9] C.Udrişte, Optimization methods on Riemannian manifolds, IRB International Workshop, Monteroduni, Italy, August 8–12, 1995, (to appear).

[10] C.Udrişte, Riemannian convexity in programming (I), The 25-th National Conference on Geometry and Topology, Al.I.Cuza University of Iassy, Romania, September 18–23, 1995; Analele Stiintifice ale Universitatii Al.I.Cuza, Iasi, 42(1996), 123–136.

[11] C.Udrişte, Riemannian convexity in programming (II), The Second International Workshop on Differential Geometry and Its Applications, Ovidius Univ. of Constantza, Romania, Sept. 25–28, 1995; Balkan Journal of Geometry and Its Applications, 1, 1(1996), 99–109.

[12] C.Udrişte, Riemannian convexity, The Second International Workshop on Differential Geometry and Its Applications, Ovidius Univ. of Constantza, Romania, Sept.25–28, 1995; Balkan Journal of Geometry and Its Applications, 1, 1(1996), 111–116.

University Politehnica of Bucharest, Department of Mathematics I, Splaiul Independentei 313, 77206 Bucharest, Romania; e–mail:udriste@mathem.pub.ro; Fax:401/411.53.65