Riemannian Convexity in Programming (II)

Constantin Udrişte

Abstract

The book [7] emphasizes three relevant aspects: first, the fact that the notion of convexity is strongly metric-dependent either through geodesics or through the Riemannian connection; second that Riemannian convexity of functions is a coordinate-free concept, and consequently it can be easily connected with symbolic computation; third, that the Riemannian structure is involved essentially in formulating and solving programs by means of induced distance, geodesics, Riemannian connection, sectional curvature, etc.

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.

§1 shows that some difficulties appearing in the free-minimization problems belong to a wrong understanding of the suitable Riemannian structure of the space. §2 deals with Newton algorithm on Riemannian manifolds for finding zeros of a C^{∞} vector field or generally for a C^{∞} tensor field. §3 describes the path of centers attached to a convex program on a Riemannian manifold and analysis the monotonicity of the objective function along this curve. §4 gives theorems regarding the Newton method near the path of centers of a convex program (one unit Newton step stays inside the feasible set, quadratic convergence results, upper bound for the difference of two Huard distance function values, etc), using simultaneously the original Riemannian metric and a Hessian Riemannian metric. §5 gives upper bounds for the total number of outer iterations and inner iterations needed by the center algorithm on a Riemannian manifold.

The theorems in §3-5 have their origin in the Euclidean variants exposed in [1], [2] and in the Riemannian point of view about convex programming developed in [7].

1991 Mathematics Subject Classification: 49M45, 49M15 Key words: Objective functions, Newton method, Riemannian convexity, path of centers, complexity analysis

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

1 Commentary on test objective functions

The test functions used in the numerical free minimization have been constructed in such a way as to present various computational difficulties when we look for the finding of a critical point. A list of some of more frequently used test functions on (R^{n}, δ_{ij}), together with an initial estimate x_{1} of the minimizer (critical point) x_{∗}, and a brief description of the computational difficulties presented by the optimization problem is given for example in [11].

For some of such functions we shall point out that some difficulties 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.

Let (M, g) be a complete n-dimensional Riemannian manifold, let ∇ be the Riemannian connection and γ(t) = exp_{x}(tX), t ∈ [0, 1] be the geodesic determined by the initial conditions γ(0) = x ∈ M, γ̇(0) = X ∈ T_{x}M.

If f : M → R is of class C^{∞}, and x_{∗} is a minimum point (critical point) of f, then the general descent algorithm for finding x_{∗} is:

Let x_{1} be an estimate of x_{∗}.

1) Set i = 1.

2) Compute a vector X_{i} such that df(X_{i}) < 0.

3) Compute a number t_{i} such that f(exp_{x_{i}}(t_{i}X_{i})) < f(x_{i}).

4) Compute x_{i+1} from x_{i+1} = exp_{x_{i}}(t_{i}X_{i}).

5) If x_{i+1} satisfies the given convergence criteria, then stop.

6) Set i = i + 1 and go to 2).

The Newton algorithm is the variant of the general descent algorithm with X = −H^{−1}df, where the Hessian H = ∇(∇f) is supposed to be nondegenerate.

For details, see [7] and the explanations in §2.

1. Rosenbrock banana function (1960)

f : R^{2} → R, f(x) = 100(x_{2} − x_{1}^{2})^{2} + (1 − x_{1})^{2}, x = (x_{1}, x_{2})

e = (−1 · 2; 1 · 0), x_{∗} = (1, 1), f(x_{∗}) = 0.

Difficulties. The graph of this function looks like a steep-sided sharply curving valley, the bottom of which follows the parabola x_{2} = x_{1}^{2}. An Euclidean descent method must in general take a very short steps in order to negociate the sharp bend near (0,0) and must therefore provide new search directions very frecvently.

Let us show that there exists a Riemannian metric on R^{2} which produces the convexity of Rosenbrock banana function [7].

Denote by

(R^{2}, g_{0} = ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ))

the Euclidean plane. The function

F : R^{2} → R, F (y) = 100y_{2}^{2} + y_{1}^{2}, y = (y_{1}, y_{2})

is convex with respect to g_{0}.

Now we consider the nonlinear coordinate transformation

y_{1} = 1 − x_{1}, y_{2} = x_{2} − x_{1}^{2}.

The Riemannian manifold (R^{2}, g_{0}) is changed into

(R^{2}, g(x) = ( \begin{matrix}4x_{1}^{2} + 1 & −2x_{1} \\ −2x_{1} & 1 \end{matrix} )) , x = (x_{1}, x_{2})

and F is changed into Rosenbrock banana function f which is convex with respect to g.

The geodesics of (R^{2}, g_{0}) are straight lines, y_{1} = at + b, y_{2} = ct + d, t ∈ R. The geodesics of (R^{2}, g(x)) are parabolas, x_{1} = et + f, x_{2} = e^{2}t^{2} + gt + h, t ∈ R.

Consequently, in order to minimize f is suitable to use the descent algorithms with respect to the Riemannian metric g(x), and not those with respect to the Euclidean structure g_{0}. Then all the above difficulties dissapear.

2. Powell function (1966)

f : R^{2} → R, f(x) = x_{1}^{4} + x_{1}x_{2} + (1 + x_{2})^{2}, x = (x_{1}, x_{2})
e = (0, 0), x_{∗} = (?,?)

Difficulty. For this problem

min_{t} f(e − tH^{−1}df(e)) = f(e)

so that no progress can be made beyond the estimate e of x_{∗} using Euclidean Newton method together with an exact straight line search. Indeed,

df = (4x_{1}^{3} + x_{2}, x_{1} + 2(1 + x_{2})), df(0, 0) = (0, 2)

H = ( \begin{matrix}12x_{1}^{2} & 1 \\ 1 & 2 \end{matrix} ) , H(0, 0) = ( \begin{matrix}0 & 1 \\ 1 & 2 \end{matrix} ) ,

H(0, 0)^{−1} = ( \begin{matrix}−2 & 1 \\ 1 & 0 \end{matrix} ) , H^{−1}df(0, 0) = ( \begin{matrix}2 \\ 0 \end{matrix} ) ,

φ(t) = f(−2t, 0) = 2^{4}t^{4} + 1, t = 0 is critical point,

min φ(t) = φ(0) = 1 = f(e).

The Riemannian structure which exceeds the preceding difficulty is those whose geodesics are parabolas. Indeed, let x_{1} = 2t, x_{2} = −bt^{2}, t ∈ R, be a geodesic passing through the point (0,0) with the direction (2,0) at the moment t = 0. We obtain

φ(t) = f(x_{1}(t), x_{2}(t)) = 2^{4}t^{4} − 2bt^{3} + (1 − bt^{2})^{2}.

Imposing φ′(t) = 0, i.e., (32 + 2b^{2})t^{2} − 3bt − 2b = 0 we obtain two real roots t_{1}, t_{2}. Hence the Riemannian Newton method works. Remark. Some recent papers [3] suggest that sometimes the changing of coordinates (which imply the changing of the Riemannian metric) can be benefic for a concrete optimization problem. But, of course, this idea is included in our general idea [4]-[9] that is enough to change conveniently the Riemannian metric in order to obtain a desired result.

2 Newton method on Riemannian manifolds

Let (M, g) be a complete n-dimensional Riemannian manifold and ∇ be the Riemannian connection determined by the metric g. The completeness implies the fact that any two points of M can be joined by a minimal geodesic.

Let X be a C^{∞} vector field on M. Using the mathematical apparatus (M, g, ∇), we want to formulate a numerical algorithm for finding zeros of X. For these we need the Riemannian version of Taylor theorem together the generalizations of numerical techniques on Euclidean space to a Riemannian manifold. These are realized via an intrinsic approach which leads one from the extrinsic idea of vector addition to the exponential map and parallel translation, from the search along straight lines to search along geodesics, and from partial differentiation to covariant differentiation.

Let γ : [0, 1] → M, γ(t) = exp_{x}(tY) be the geodesic fixed by the initial conditions γ(0) = x ∈ M, γ̇(0) = Y ∈ T_{x}M. 2.1. Meanvalue theorem. Let W_{x} be a normal neighborhood of the point x ∈ M, let Ȳ be a vector field on W_{x} adapted to Y ∈ T_{x}M, and X be a C^{∞} vector field on W_{x}. Denote τ_{b} the parallel translation with respect to exp_{x}(tY) for t ∈ [0, b], and x_{b} = exp_{x}(bY). Then there exists ϵ > 0 such that for every b ∈ [0, ϵ), there is a ∈ [0, b] satisfying

τ_{b}^{−1}X_{x_{b}} = X_{x} + b(∇Ȳ X)_{x_{a}} ∘ τ_{a}.

2.2. Taylor theorem. Same hypothesis as in theorem 2.1. Then there exists ϵ > 0 such that for every b ∈ [0, ϵ), there is a ∈ [0, b] satisfying

τ_{b}^{−1}X_{x_{b}} = X_{x} + b(∇Ȳ X)_{x} + … + \frac{b^{n−1}}{(n − 1)!}(∇n−1 ; ȲX)_{x} + \frac{b^{n}}{n!} (∇n ; Ȳ X)_{x_{a}} ∘ τ_{a}.

Let x_{∗} = x_{b} be a zero of the C^{∞} vector field X and x be an estimate of x_{∗}. If x is sufficiently close to x_{∗}, we have

τ_{b}^{−1}X_{x_{b}} = X_{x} + b(∇Ȳ X)_{x} + \frac{b^{2}}{2} (∇2 ; Ȳ X)_{x_{a}} ∘ τ_{a}

and the term (∇2 ; Ȳ X)_{x_{a}} can be neglected. Consequently X(x_{∗}) = 0 is replaced by

b(∇Ȳ X)_{x} ≈ −X_{x}.

If (∇X)_{x} : T_{x}M → T_{x}M is nondegenerate, then we obtain

bȲ_{x} ≈ −(∇X)_{x}^{−1} ∘ X_{x}

and hence

x_{∗} ≈ exp_{x}(−(∇X)_{x}^{−1} ∘ X_{x}).

Consequently the most suitable direction and sense of moving from the point x towards the point x_{∗} is given by the Newton vector

N_{x} = −(∇X)_{x}^{−1} ∘ X_{x}.

Of course zeros of X are global minimum points, and hence critical points, of the energy f = \frac{1}{2}g(X, X). Also, if X(x) ≠ 0, then N_{x} gives a descent direction and sense for the energy f at x since df(N_{x}) = −2f(x) < 0.

The preceding considerations suggest that, given an initial estimate x_{1} of x_{∗}, we could estimate x_{∗} with arbitrary accuracy by generating the sequence {x_{i}} from

x_{i+1} = exp_{x_{i}} N_{i}, N_{i} = −(∇X)_{x_{i}}^{−1} ∘ X_{x_{i}}.

This procedure is the Newton method for estimating a zero of X, and is embodied in the following 2.3. Newton algorithm. Let x_{1} be an initial estimate of x_{∗}. Suppose that ∇X is nondegenerate.

1) Set i = 1.

2) Compute the Newton vector N_{i} = −(∇X)_{x_{i}}^{−1} ∘ X_{x_{i}}.

3) Compute x_{i+1} from x_{i+1} = exp_{x_{i}} N_{i}.

4) Set i = i + 1 and go to 2).

Under certain conditions, the sequence {x_{i}} generated by the Newton algorithm 2.3 converges to the zero x_{∗} of X. In this sense the following theorems holds for general vector fields, though they are formulated for X = gradf = g^{−1} ∘ df, where g is the Riemannian metric on M and f : M → R is a C^{∞} function. Of course, in the theory appears also the (1,1) tensor field H(f) = ∇(gradf) = g^{−1} ∘ ∇(df), which is symmetric with respect to the Riemannian metric, i.e., g(H(f)Y, Z) = g(Y, H(f)Z) for any C^{∞} vector fields Y, Z on M. The tensor field H(f) is called (positive or negative) definite if the associated (0,2) tensor field H(f) = g ∘H(f) is (positive or negative) definite. The tensor field H(f) is called the Hessian of the function f. If x_{∗} is a critical point of f (i.e.,gradf(x_{∗}) = 0), and H(f)(x_{∗}) is nondegenerate, then the critical point x_{∗} is called nondegenerate. 2.4. Theorem. If x_{∗} is a nondegenerate critical point of the function f ∈ C^{∞}(M), then there exists a neighborhood U of x_{∗} such that for any x_{1} ∈ U, the iterates of the Newton algorithm 2.3, for X = gradf, are well defined and converge quadratically to x_{∗}. 2.5. Corollary. If H(f)(x_{∗}) is positive (negative) definite and the sequence generate by the Newton algorithm 2.3 converges to x_{∗}, then the sequence converges quadratically to a local minimum (maximum) of f. Remark. 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 extended Riemannian-Newton method, can be used to find zeros of any tensor field.

3 Path of centers of a convex program

Let (M, g) be a Riemannian manifold and

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

be a convex program, i.e., 1) the interior F^{0} of the feasible region F is nonempty and bounded,

2) 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}. Let z be a lower bound for the optimal value z_{∗}, and q be a given positive

integer. To the program (P) we attach the Huard distance function

ϕ(α, z) = −q ln(f_{0}(x) − z) − ∑_{α=1}^{m} ln(−f_{α}(x)).

Suppose that ϕ has positive definite Hessian. Then ϕ achieves the minimal value in its domain (for fixed z) at a unique point x(z), called center. The center x(z) satisfies

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

Also this point satisfies the Karush-Kuhn-Tucker conditions

f_{α}(x) = 0

∑_{α=1}^{m} y_{α} grad df_{α}(x) = grad df_{0}(x), y_{α} ≥ 0

f_{α}(x)y_{α} = \frac{f_{0}(x) − z}{q} , α = 1, …, m.

The set {x(z)} is called the path of centers. The method of centers for solving the program (P) works as follows. Given z, we try to reach the vicinity of the center x(z). Then we increase the lower bound z, and we try to reach the vicinity of the new center, etc. To find (an iterate close to) the center, which is in fact equivalent to minimizing ϕ, we use Newton method with approximate geodesic search procedures [1], [5]-[9], [11]. Denoting −f_{α}(x) = f_{0}(x) − z for α = m + 1, …, m + q, the function ϕ is transcribed as

ϕ(x, z) = − ∑_{α=1}^{m+q} ln(−f_{α}(x)),

and appear a bounded totally convex set F_{z} = {x | f_{α}(x) ≤ 0, α = 1, …, m + q} whose interior will be denoted F_{z}^{0}. Also, for Newton method we need

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

H(x, z) = H(ϕ)(x, z) = ∑_{α=1}^{m+q} [\frac{H(f_{α})(x)}{−f_{α}(x)} + \frac{df_{α}(x) ⊗ df_{α}(x)}{f_{α}^{2}(x)}],

where

gradϕ = g^{−1} ∘ dϕ,

and the Hessian H(ϕ) are built using the Riemannian metric g. Because H(ϕ) is positive definite (by hypothesis), it can be used like a new Riemannian metric.

Differentiating and manipulating the relations defining x(z) and y_{α}(z) we can prove the following theorem about the monotonicity along the path of centers. 3.1. Theorem. The primal objective f_{0}(x(z)) is monotonically increasing, the dual objective f_{0}(x(z))−∑_{α=1}^{m} y_{α}(z)f_{α}(x(z)) and f_{0}(x(z))−z are monotonically decreasing if z increases.

Also we can obtain an upper bound for the gap z_{∗} - z. 3.2. Lemma. One has

z_{∗} − z ≤ (1 + \frac{m}{q})(f_{0}(x(z)) − z).

Proof. The center x(z) minimizes ϕ(x, z), the necessary and sufficient conditions being those of Karush - Kuhn - Tucker. It follows that (x(z), y(z)) is dual feasible, and we know that dual objective value is always greater than or equal to the optimal value, i.e.,

z_{∗} ≤ f_{0}(x(z)) − ∑_{α=1}^{m} y_{α}(z)f_{α}(x(z)).

Hence

z_{∗} − f_{0}(x(z)) ≤ − ∑_{α=1}^{m} y_{α}(z)f_{α}(x(z)) = \frac{m}{q}(f_{0}(x(z)) − z).

Consequently

(z_{∗} − z) − (f_{0}(x(z)) − z ≤ \frac{m}{q}(f_{0}(x(z)) − z)

or

z_{∗} − z ≤ (1 + \frac{m}{q})(f_{0}(x(z)) − z).

4 Properties near the path of centers

Suppose that ϕ is k-self-concordance with k ≥ 1. The boundedness of F^{0} and the self-concordance of ϕ imply the strict convexity of ϕ, i.e., H(ϕ)(x, z) > 0. In order to prove some properties of approximately centered points, we shall use simultaneously [1], [2], [8], [9] the Riemannian metric g and the Riemannian metric H(ϕ) = H.

In the center method, the program (P) is replaced by a sequence of minimizing ϕ(x, z) using Newton method with (approximate) geodesic search procedures. Of course, the Newton vector field is N = −H^{−1}dϕ, and, if we use H like a Riemannian metric, N = −gradϕ. Note that ∥ N ∥_{H}= 0 iff x = x(z). 4.1. Theorem. Let x ∈ F_{z}^{0}, X ∈ T_{x}M and γ(t) = exp_{x}(tX), t ∈ [0, 1] be the geodesic determined by γ(0) = x, γ̇(0) = X. If ∥ X ∥_{H(x,z)}< \frac{1}{k} , then γ(1) ∈ F_{z}^{0} ⊂ F^{0}.

4.2. Theorem. Let γ(t) = exp_{x}(tN) be the geodesic γ : [0, 1] → M which verifies the initial conditions γ(0) = x, γ̇(0) = N.

If ∥ N ∥_{H(x,z)}< \frac{1}{k}, then x_{+} = γ(1) ∈ F_{z}^{0}, and

∥ N(x_{+}, z) ∥_{H(x_{+},z)}≤ \frac{k}{(1 − k ∥ N ∥_{H})^{2}} ∥ N ∥_{H}^{2} .

For ∥ N ∥_{H} < \frac{3−\sqrt{5}}{2k}, we find

∥ N(x_{+}, z) ∥_{H(x_{+},z)}<∥ N ∥_{H}

and so the Newton algorithm is convergent. For ∥ N ∥_{H} ≤ \frac{1}{3k}, we obtain

∥ N(x_{+}, z) ∥_{H(x_{+},z)}≤ \frac{9}{4}k ∥ N ∥_{H}^{2} .

4.3. Theorem. If ∥ N ∥_{H}≤ \frac{1}{3k} and x is an approximation of the exact center x(z), then

ϕ(x, z) − ϕ(x(z), z) ≤ \frac{∥ N ∥_{H}^{2}}{1 − (\frac{9}{4}k ∥ N ∥_{H})^{2}} .

4.4. Theorem. If ∥ N ∥_{H}≤ \frac{1}{3k} and q ≥ \frac{\sqrt{m}}{k} , then

f_{0}(x(z)) − z ≤ (1 + \frac{2\sqrt{m}}{q} \frac{∥ N ∥_{H}}{1 − \frac{9}{4}k ∥ N ∥_{H}} )(f_{0}(x) − z).

Proof. We have dϕ(N) = − ∥ N ∥_{H}^{2} . Since

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

it follows

df_{0}(x)(N) = \frac{f_{0}(x) − z}{q} (∥ N ∥_{H}^{2} + ∑_{α=1}^{m} \frac{df_{α}(x)(N)}{−f_{α}(x)}).

On the other hand [1], [9]

| ∑_{α=1}^{m} \frac{df_{α}(x)(N)}{−f_{α}(x)} | ≤ \sqrt{m} ∥ N ∥_{H} .

Consequently

df_{0}(x)(N) ≤ \frac{f_{0}(x) − z}{q} (∥ N ∥_{H}^{2} +\sqrt{m} ∥ N ∥_{H}) ≤ 2 ∥ N ∥_{H} \frac{f_{0}(x) − z}{q} \sqrt{m}.

If x_{1} = x, and x_{2}, x_{3}, … is the Newton sequence starting at x_{1}, then

∥ N(x_{i}, z) ∥_{H(x_{i},z)}≤ \frac{9}{4}k ∥ N(x_{i−1}, z) ∥_{H(x_{i−1},z)}^{2}
⋮
≤ (\frac{9}{4}k)^{2^{i}−1}∥ N(x_{1}, z) ∥_{H(x_{1},x)}^{2^{i}}

and hence

lim_{k→∞} ∥ N(x_{i}, z) ∥_{H(x_{i},z)}= 0.

Since {x_{i}} is included in a bounded region, and ∥ N(x, z) ∥_{H(x,z)}= 0 iff x = x(z), all limit points of the sequence are x(z). In other words, the Newton sequence converges to x(z).

Using the inequalities and the convexity of −f_{0}(x) we obtain

f_{0}(x_{i+1}) − z = f_{0}(x_{i}) − z + f_{0}(x_{i+1}) − f_{0}(x_{i}) ≤

≤ f_{0}(x_{i+1}) − z + df_{0}(x_{i})(N(x_{i}, z)) ≤

≤ (1 + 2 ∥ N(x_{i}, z) ∥_{H(x_{i},z)} \frac{\sqrt{m}}{q})(f_{0}(x_{i}) − z)

and hence

f_{0}(x_{i+1}) − z ≤ (f_{0}(x_{1}) − z)Π_{j=1}^{i}(1 + 2 ∥ N(x_{j}, z) ∥_{H(x_{j},z)} \frac{\sqrt{m}}{q}) ≤

≤ (f_{0}(x_{1}) − z)Π_{j=1}^{i}(1 + 2 (\frac{9}{4}k)^{2^{j}−1} ∥ N ∥_{H}^{2^{j}} \frac{\sqrt{m}}{q}).

If q ≥ \frac{\sqrt{m}}{k} , we obtain [1]

f_{0}(x(z)) − z ≤ (f_{0}(x_{1}) − z)Π_{j=1}^{i}(1 + 2 (\frac{9}{4}k)^{2^{j}−1} ∥ N ∥_{H}^{2^{j}} \frac{\sqrt{m}}{q}) ≤

≤ (1 + \frac{2\sqrt{m}}{q} \frac{∥ N ∥_{H}}{1 − \frac{9}{4}k ∥ N ∥_{H}} )(f_{0}(x_{1}) − z).

5 Complexity analysis

Using the results in the preceding paragraph, we can find upper bounds for the total number of outer iterations and inner iterations needed by the Center algorithm stated in [1], [8].

The analysis refers to long-, medium-, and short-step variants with τ = \frac{1}{3k} . The proofs of the propositions are similar to those in [1], [9].

5.1. Theorem. The Center algorithm ends up with an ϵ-optimal solution for (P) after at most

\frac{4}{θ}(1 + \frac{m}{q}) ln \frac{4 (1 + \frac{m}{q}) (z_{∗} − z_{1})}{ϵ}

outer iterations. 5.2. Lemma. If γ(t) = exp_{x}(tN), t ∈ [0, 1] and t̄= \frac{1}{1+k∥N∥_{H}}, then

ϕ(x, z) − θ(γ(t̄), z) ≥ \frac{1}{k^{2}} (k ∥ N ∥_{H} − ln(1 + k ∥ N ∥_{H})).

5.3. Theorem. The total number of inner iterations during an arbitrary outer iteration is at most

\frac{22}{3} + 22qk^{2}θ(\frac{θ}{1 − θ} + \frac{3\sqrt{m}}{qk + 3\sqrt{m}}).

Combining theorems 5.1 and 5.3, we obtain the total number of iterations. 5.4. Theorem. An upper bound for the total number of Newton iterations is given by

88 (1 + \frac{m}{q}) (\frac{1}{3θ} + qk^{2} (\frac{θ}{1 − θ} + \frac{3\sqrt{m}}{qk + 3\sqrt{m}})) ln \frac{4 (1 + \frac{m}{q}) (z_{∗} − z_{1})}{ϵ}.

Consequently, to obtain an ϵ-optimal solution and setting q = θ(m), the algorithms needs

−O(k^{2}m ln \frac{z_{∗}−z_{1}}{ϵ} ) Newton iterations for the long-step variant (0 < θ < 1); −O(k^{2}\sqrt{m} ln \frac{z_{∗}−z_{1}}{ϵ} ) Newton iterations for the medium-step variant for θ =

\frac{ν}{\sqrt{m}} > 0; −O(k\sqrt{m} ln \frac{z_{∗}−z_{1}}{ϵ} ) Newton iterations for θ = \frac{ν}{k\sqrt{m}} > 0. For the short-step variant we states how the norm changes when z is in-

creased. 5.5. Lemma. If z_{+} = z + θ(f_{0}(x) − z), then

∥ N(x, z_{+}) ∥_{H(x,z_{+})}≤∥ N ∥_{H} +\frac{θ}{1 − θ} \sqrt{q}.

5.6. Lemma. Let x_{+} = γ(1) and z_{+} = θ(f_{0}(x) − z), where θ = \frac{1}{22k\sqrt{q}}. If

∥ N(x, z) ∥_{H(x,z)}≤ \frac{1}{3k} ,

then

∥ N(x_{+}, z_{+}) ∥_{H(x_{+},z_{+})}≤ \frac{1}{3k} .

Consequently, if θ is enough small, then one unit Newton step is sufficient to reach the vicinity of x(z_{+}). By theorem 5.1, a short-step algorithm requires O(k\sqrt{m} ln \frac{z_{1}−z_{0}}{6} ) Newton iterations, using q = θ(m).

Aknowledgements. A version of this paper was presented at The Second International Workshop on Differential Geometry and Its Applications, Ovidius University of Constantza, Romania, Sept.25-28, 1995.

Many thanks to all the participants at my oral presentation, especially for comments and suggestions.

References

[1] D.den Hertog, Interior point approach to linear, quadratic and convex programming, Mathematics and Its Applications, 277, Kluwer Academic Publishers, 1994.

[2] Y.Nesterov, A.Nemirovsky, Interior-point polynomial algorithms in convex programming, Siam, 1994.

[3] T.Rapcsak, T.Csendes, Nonlinear coordinate transformations for unconstrained optimization, Journal of Global Optimization, 3(1993), 359-375.

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

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

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

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

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

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

[10] C.Udrişte, Riemannian convexity, The Second International Workshop on Differential Geometry and Its Applications, Ovidius University of Constantza, Romania, Sept.25-28, 1995; this Journal pp.111-116.

[11] Ph.Wolfe, Numerical methods for unconstrained optimization, Van Nostrand Reinhold Company, 1987.

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