On convergence and restart conditions for a nonlinear conjugate

gradient method

Arnold Neumaier

Institut für Mathematik, Universität Wien Strudlhofgasse 4, A-1090 Wien, Austria email: neum@cma.univie.ac.at www: http://solon.cma.univie.ac.at/˜ neum

August 1997

Abstract. A global convergence theorem for unconstrained minimization algorithms with an efficient line search is derived. The theorem applies to a new version of the conjugate gradient method derived here in terms of minimizing the effect of zigzagging. The global convergence condition makes much weaker demands on the line search than previous methods.

Local Q-linear convergence in a neighborhood of a strong local minimizer follows under additional conditions that define natural restart conditions based on line search accuracy and loss of conjugacy of successive gradients.

Keywords: local optimization, global convergence, conjugate gradients, conjugate descent, restart conditions, loss of conjugacy, efficient line search, zigzagging

1991 MSC Classification: 90C30

1 Introduction

We consider the problem of finding a local minimizer of a real valued function f : IR^{n} → IR in n variables. We shall assume that f is continuously differentiable with computable gradients g(x) = f′(x)^{T}. For the discussion of convergence rates, we shall also assume that the gradients are locally Lipschitz continuous, so that in some neighborhood of a minimizer, there is a constant γ such that

∥g(x) − g(x′)∥ ≤ γ∥x − x′∥.  (1)

If n is large and no structural properties of f are available, one often uses conjugate gradient methods (Fletcher & Reeves [2]; cf. the surveys by Powell [11] and Gilbert & Nocedal [4]) or limited memory quasi-Newton methods (e.g., the popular L-BFGS method of Liu & Nocedal [5]) for the minimization. (Alternatively, one may use truncated Newton methods and solve the linear systems by conjugate gradients; see, e.g., Nash [7]. However, truncated Newton methods are unrelated to the present paper.)

These methods use a Hessian approximation B (often diagonal) as a preconditioner, and the search direction may be viewed as a linear combination of the simplified Newton direction

p_{N} = −B^{−1}g  (2)

and a direction from a low-dimensional subspace that is adapted during the iteration. In both nonlinear conjugate gradient methods and limited-memory quasi-Newton methods, the search direction is motivated by conjugacy properties of the gradients for quadratic objective functions, at least in the initial phase of the algorithm. Also in both cases, restart techniques are needed to recover from a deterioration of this low-dimensional subspace by reverting to the simplified Newton direction (2).

In this paper, we shall look at general methods that calculate their search direction as a linear combination of the simplified Newton direction p_{N} and another direction p_{C}, and we discuss conditions on p_{C} that guarantee global convergence, and approximate conjugacy conditions that imply local Q-linear convergence in a neighborhood of a strong local minimizer. Recall that in a neighborhood of a strong local minimizer, f is uniformly convex, i.e., there is a positive constant γ′ such that

γ′∥x − x′∥^{2} ≤ (g(x) − g(x′))^{T} (x − x′).  (3)

The new convergence conditions are derived from a general convergence result discussed in Section 2, and are applied in Section 4 to provide global convergence of a new version of the conjugate gradient method, assuming only that the line search is efficient in the sense of Warth & Werner [12]. Virtually all line search procedures that have been used in provably convergent unconstrained minimization algorithms have this property. Local Q-linear convergence in a neighborhood of a strong local minimizer follows under simple restart conditions similar to those discussed by Powell [10].

Notation. In the following, we consider a sequence x^{l} (l = 0, 1, 2, …) of points in IR^{n} produced by some algorithm designed for local optimization. To simplify the typography and to improve the readability of the formulae we shall write

f_{l} := f(x^{l}), g^{l} := g(x^{l}).

When l is arbitrary or clear from the context, the letters f, x, g denote f_{l}, x^{l}, g^{l}; the symbols f̄, x̄, ḡ denote f_{l+1}, x^{l+1}, g^{l+1}, and the symbols f_{old}, x_{old}, g_{old} denote f_{l−1}, x^{l−1}, g^{l−1}, respectively. Similar conventions will apply for other quantities indexed by l.

We assume that a fixed positive definite matrix B is available that can be considered as a Hessian approximation. Related to B is the norm

∥p∥ := \sqrt{p^{T} Bp}  (4)

and the associated dual norm

∥g∥^{∗} = ∥B^{−1}g∥ = \sqrt{g^{T} B^{−1}g},  (5)

satisfying the Cauchy-Schwarz inequality

|g^{T} p| ≤ ∥g∥^{∗}∥p∥ for all g, p ∈ IR^{n}.  (6)

These norms will be used throughout. In the special case where B = I, both norms reduce to the Euclidean norm, and if desired, the general case could be reduced to this case by a coordinate transform.

2 A global convergence theorem

We consider optimization methods based on linear line searches that find for each x and each descent direction p with g^{T} p < 0 a step s = αp such that f(x + s) < f(x).

We shall call a line search procedure efficient if there is a number δ > 0 such that the generated step always satisfies

f(x + s) ≤ f − δ(g^{T} s)^{2}/∥s∥^{2}.  (7)

Given an efficient linear line search procedure, an optimization method is characterized by the choice of the search direction p at each iteration. The iterate x is modified by adding to x a multiple s = αp (α > 0) of the search direction,

x̄ = x + s = x + αp.

Warth & Werner [12] proved that for functions with Lipschitz continuous gradients, efficient linear line searches together with a uniform bound

\frac{g^{T} p}{∥g∥^{∗}∥p∥} < −δ′ < 0  (8)

on the cosines of the angle between gradient and search direction imply local Q-linear convergence in a neighborhood of a strong local minimizer. Condition (8) is very important in theory, but is hardly ever used in practice since for good performance (acceptance of p = x̂ − x close to a strong local minimizer x̂) the constant δ′ cannot be chosen a priori but must depend on the condition of the problem.

The following theorem provides new sufficient conditions for global convergence and local Q-linear convergence that are readily implementable.

2.1. Theorem. (i) For any optimization method that chooses all its search directions such that, for some positive constant κ,

\frac{p^{T} Bp}{(g^{T} p)^{2}} ≤ \frac{p_{old}^{T}Bp_{old}}{(g_{old}^{T}p_{old})^{2}} + \frac{κ}{g^{T} B^{−1}g}  (9)

and its steps by an efficient linear line search, we have

inf_{l≥0} ∥g^{l}∥ = 0 or inf_{l≥0} f_{l} = −∞.  (10)

(ii) Suppose that, in addition, there are fixed positive constants η, η′ such that

\frac{g^{T} p_{old}}{g_{old}^{T}p_{old}} ≤ η, \frac{g^{T} B^{−1}g_{old}}{g_{old}^{T}B^{−1}g_{old}} ≤ η′ ≤ \frac{1}{2}  (11)

at each step where the simplified Newton direction is not chosen. If f has Lipschitz continuous gradients and the x^{l} converge to a strong local minimizer then convergence is locally Q-linear.

Proof. Without loss of generality we may assume that all search directions are scaled such that

g^{T} p = −1,  (12)

(i) Suppose inf ∥g^{l}∥ = ϵ > 0. Then

ϵ ≤ ∥g∥ = ∥BB^{−1}g∥ ≤ ∥B∥ ∥B^{−1}g∥,

and by (9) and (12),

∥p∥^{2} − ∥p_{old}∥^{2} ≤ κ/∥B^{−1}g∥^{2} ≤ κ∥B∥^{2}/ϵ^{2}.  (13)

Summation over all steps gives

∥p^{l}∥^{2} ≤ (l + 1)κ′, κ′ = max(∥p^{0}∥^{2}, κ∥B∥^{2}/ϵ^{2}).

Since line searches are efficient, (7) implies

f − f̄ ≥ \frac{δ(g^{T} s)^{2}}{∥s∥^{2}} = \frac{δ(g^{T} p)^{2}}{∥p∥^{2}} = \frac{δ}{∥p∥^{2}} ≥ \frac{δ}{κ′} · \frac{1}{l + 1}.

Summation over all steps gives

f_{l} ≤ f_{0} − \frac{δ}{κ′} ∑_{i=1}^{l} \frac{1}{i} → −∞.

(ii) To prove the second part, we only need to verify a bound (8) on the cosines. For simplified Newton steps, this bound holds by (6) for any δ′ < 1. For the other steps we may use (11), which gives

∥B^{−1}(g − g_{old})∥^{2} = (g − g_{old})^{T} B^{−1}(g − g_{old})
= g^{T} B^{−1}g − 2g^{T} B^{−1}g_{old} + g_{old}^{T}B^{−1}g_{old}
≥ g^{T} B^{−1}g.

On the other hand, the Lipschitz condition (1) gives

∥g − g_{old}∥ = ∥g(x^{l}) − g(x^{l−1})∥ ≤ γ∥x^{l} − x^{l−1}∥ = γ∥s_{old}∥,

so that

∥B^{−1}g∥ = \sqrt{g^{T} B^{−1}g} ≤ ∥B^{−1}(g − g_{old})∥
≤ ∥B^{−1}∥∥g − g_{old}∥ ≤ γ∥B^{−1}∥∥s_{old}∥.

Since f is uniformly convex in a neighborhood of a strong local minimizer, we also have

γ′∥s_{old}∥^{2} = γ′∥x^{l} − x^{l−1}∥^{2}
≤ (g(x^{l}) − g(x^{l−1}))^{T} (x^{l} − x^{l−1})
= (g − g_{old})^{T} s_{old}.

If we multiply the last two inequalities, we find

γ′∥s_{old}∥^{2}∥B^{−1}g∥ ≤ γ∥B^{−1}∥∥s_{old}∥(g − g_{old})^{T} s_{old}.

With the constant σ = γ∥B^{−1}∥/γ′, this simplifies to

∥s_{old}∥∥B^{−1}g∥ ≤ σ(g − g_{old})^{T} s_{old}.

By scaling, the same holds with p_{old} in place of s_{old}. Therefore, using (11) and (12), we find

∥p_{old}∥∥B^{−1}g∥ ≤ σ(g − g_{old})^{T} p_{old} ≤ σ(η + 1) = σ_{1}.

If we solve this for ∥p_{old}∥ and use (13) we get

∥p∥^{2} ≤ (σ_{1}^{2} + κ)/∥B^{−1}g∥^{2},

and with (12) we find the cosine bound (8) with δ = \sqrt{σ_{1}^{2} + κ}. Therefore we have local Q-linear convergence. _{□} A major virtue of the theorem is that the violation of condition (11) defines a practical restart criterion which ensures that we will not generate search directions that are much poorer than those obtained by the simplified Newton direction.

The first inequality is a Wolfe-like condition that involves the directional derivative at x in the old search direction and measures the accuracy of the old line search. In particular, the quotient vanishes when the last line search was exact.

In modern line search codes it is customary to use a two-sided Wolfe condition

|\frac{g^{T} p_{old}}{g_{old}^{T}p_{old}} | ≤ η

to terminate the line search. However, satisfying the two-sided Wolfe condition may be very expensive in the following two cases: (i) at starting points where the directional derivative is very small, and (ii) in directions where the function is nearly linear in an extended region and then suddenly becomes very steep. The line search by Moré & Thuente [6], for example, used in many modern optimization codes, returns for such directions the warning “WARNING: INTERVAL TOO SMALL FOR FURTHER PROGRESS”, but only after having spent a huge number of function values to bracket the minimizer along the line very accurately. (Interesting univariate functions to study this poor behavior are x^{2}/(x^{2} + 1), \sqrt{x^{2} + 10^{−4}}, x^{2} + x^{3} + 10^{−6}x^{4} and |x|^{1.1} for large starting values.)

In a subsequent paper (Neumaier [8]) we shall give a robust efficient line search that is free of this defect by not enforcing the Wolfe condition. The above convergence theorem is interesting in this context since, instead of enforcing this condition in the line search, we may use the more liberal line search and regard a failure of this condition (after an initial quadratic interpolation step that is mandatory for conjugate gradient methods) as a sign that the function is so strongly nonquadratic along the search direction that a restart is appropriate.

The second inequality is a measure of deviation from conjugacy; the quotient vanishes for conjugate gradient methods with exact line search on quadratic objective functions. At the same time, the second inequality serves as a measure of lack of progress: it is violated whenever very little progress is made so that x ≈ x_{old}, g ≈ g_{old} and the quotient is nearly 1.

Similar restart procedures were suggested by Powell [10] and Nocedal [9].

3 A minimum deviation principle

In this section we consider what happens when we choose each search direction p as the vector with

g^{T} p = g_{old}^{T}p_{old}  (14)

closest with respect to the norm (4) to some (unnormalized) designed vector p_{C}. This keeps g^{T} p constant throughout the iteration; hence if the first search direction is chosen such that g^{T} p = γ < 0, all search directions will be descent directions.

3.1. Theorem. Among all p ∈ IR^{n} with (14), the distance ∥p − p_{C}∥ becomes minimal for p = p̂, where

p̂ = p_{C} − λB^{−1}g,  (15)
λ = \frac{g^{T} p_{C} − g_{old}^{T}p_{old}}{g^{T} B^{−1}g} .  (16)

Proof. λ is chosen such that the vector (15) satisfies g^{T} p̂ = g_{old}^{T}p_{old}. For an arbitrary vector p with (14), write q = p − p_{C}. Then

g^{T} q = g_{old}^{T}p_{old} − g^{T} p_{C} = −λg^{T} B^{−1}g,

so that

∥p − p̂∥^{2} = ∥q + p_{C} − p̂∥^{2} = ∥q + λB^{−1}g∥^{2}
= (q + λB^{−1}g)^{T} B(q + λB^{−1}g)
= q^{T} Bq + 2λg^{T} q + λ^{2}g^{T} B^{−1}g = ∥q∥^{2} − λ^{2}g^{T} B^{−1}g.

Hence

∥p − p_{C}∥^{2} = ∥p − p̂∥^{2} + λ^{2}g^{T} B^{−1}g

for all p with (14), and this expression is minimal for p = p̂. _{□} Let us call an unconstrained minimization method that uses efficient line searches along search directions defined by (15) a corrected simplified Newton method if, after a line search in direction p, the next search direction is based on a vector p_{C} with

∥p_{C}∥ ≤ ∥p∥.

The two most natural choices are p_{C} = 0 (used at the start and at restarts) and p_{C} = p_{old} (discussed in the next section).

3.2. Algorithm. Corrected simplified Newton method

Purpose: finds local minimizer of f(x) (or a stationary point only)

Input: x (initial guess), B (preconditioner)

start:

f = f(x), g = g(x),

p_{N} = −B^{−1}g, ω = −g^{T} p_{N}

if ω ≤ 0 stop ! x stationary

p_{C} = 0, α = 1, γ = −ω

repeat:

λ = (g^{T} p_{C} − γ)/ω

p = p_{C} + λp_{N}

modify α by an efficient line search f_{old} = f, ω_{old} = ω x = x + αp, f = f(x), g = g(x) p_{N} = −B^{−1}g, ω = −g^{T} p_{N} pick p_{C} such that ∥p_{C}∥ ≤ ∥p∥

until ω ≤ 0 or (f = f_{old} and ω ≥ ω_{old})

A practical implementation must of course use better stopping tests.

3.3. Theorem. Every corrected simplified Newton method satisfies the convergence condition (9) of Theorem 2.1 with κ = 1. In particular, the method is globally convergent, and it converges Q-linearly in a neighborhood of a strong local minimizer if p_{C} = 0 whenever the conditions (11) are violated.

Proof. By (15) and (16) we have

∥p∥^{2} = p^{T} Bp = (p_{C} − λB^{−1}g)^{T} B(p_{C} − λB^{−1}g)
= p_{C}^{T}Bp_{C} − 2λg^{T} p_{C} + λ^{2}g^{T} B^{−1}g
= ∥p_{C}∥^{2} + (γ^{2} − (g^{T} p_{C})^{2})/g^{T} B^{−1}g
≤ ∥p_{C}∥^{2} + γ^{2}/∥B^{−1}g∥^{2}.

Since g^{T} p = g_{old}^{T}p_{old} = −γ < 0 and ∥p_{C}∥ ≤ ∥p_{old}∥ in a corrected simplified Newton method, (9) holds with κ = 1. _{□}

4 A new conjugate gradient method

The oldest and most basic optimization method, steepest descent, exhibits in long steep valleys the phenomenon of zigzagging, a frequent strong change of search direction, that is a main source of inefficiency. In order to reduce the amount of zigzagging we shall choose the search direction p as the vector with g^{T} p = −1 closest with respect to the norm (4) to the previous search direction; thus we use the preceding results with p_{C} = p_{old} and γ = 1.

Surprisingly, the resulting algorithm is a new version of the nonlinear conjugate gradient method. Indeed, the traditional conjugate gradient search directions have the form

p = −B^{−1}g + βp_{old},  (17)

with the original Fletcher-Reeves formula

β = \frac{g^{T} B^{−1}g}{g_{old}^{T}B^{−1}g_{old}}  (18)

(Fletcher & Reeves [2]) or various other formulas for calculating β that are equivalent to (18) for exact line searches and quadratic objective functions. For details see the surveys by Powell [11] and Gilbert & Nocedal [4].

4.1. Theorem. For exact line searches, the corrected simplified Newton method with p_{C} = p_{old} and g^{T} p = −1 is equivalent with the Fletcher-Reeves method.

Proof. Since g^{T} p_{old} = 0 for exact line searches, the expression (16) becomes λ = 1/g^{T} B^{−1}g > 0, and the Fletcher-Reeves formula (18) can be written as β = λ_{old}/λ > 0. Thus the conjugate gradient direction (17) can be scaled to give

λp = βλp_{old} − λB^{−1}g = λ_{old}p_{old} − λB^{−1}g.

A comparison with the corrected simplified Newton method (15) shows that for p_{C} = p_{old}, the search directions (17) and (15) are related by p̂ = λp and point in the same direction since λ > 0. _{□}

However, for inexact line searches, the Fletcher-Reeves direction and other traditional conjugate gradient search directions are descent directions only under stronger assumptions on the line search (Wolfe condition with certain parameter restrictions). The first global convergence result for a conjugate gradient method (indeed for the Fletcher-Reeves method) with a practical line search was obtained by Al-Baali [1], and again a Wolfe condition is needed to guarantee convergence of these versions.

Because of the equivalence with the Fletcher-Reeves method, a restart in the corrected simplified Newton method with p_{C} = p implies finite termination for functions that locally become exactly quadratic, when line searches are done with a forced quadratic interpolation step after the first function evaluation (which is mandatory for all conjugate gradient methods). Indeed, for all conjugate gradient methods with exact line searches on a quadratic function we have

g^{T} p_{old} = g^{T} B^{−1}g_{old} = 0,

so that the no-restart condition (11) is always satisfied.

Conclusion

A new global and local convergence analysis for unconstrained minimization algorithms was discussed. The sufficient conditions for global convergence are readily implementable, and the sufficient conditions for local Q-linear convergence in a neighborhood of a strong local minimizer translate directly into implementable conditions based on line search accuracy and loss of conjugacy of successive gradients.

The efficiency conditions on the line search needed for convergence are the same as those for algorithms with angles between search direction and gradient bounded away from 90^{o}, although no such bound is assumed for the global convergence proof. Thus the conditions are considerably weaker than those for traditional convergence analyses of algorithms based on conjugate directions, which need Wolfe conditions that are hard to satisfy on some classes of problems.

The convergence conditions hold for a large class of algorithms called corrected simplified Newton methods and defined by a minimum deviation principle. In particular, one can apply this principle to minimize the amount of zigzagging. Then one obtains an algorithm that – when exact line searches are used – is equivalent to the preconditioned conjugate gradient method with Fletcher-Reeves search directions.

However, for inexact line searches, the Fletcher-Reeves direction and other traditional conjugate gradient search directions are descent directions only under stronger assumptions on the line search (Wolfe condition with certain parameter restrictions). On the other hand, our new conjugate gradient method always produces descent directions, and global convergence holds assuming only the much weaker efficiency condition for the line search.

References

1. M. Al-Baali, Descent property and global convergence of the Fletcher-Reeves method with inexact line search, IMA J. Numer. Anal., 5 (1985), 121-124.

2. R. Fletcher and C.M. Reeves, Function minimization by conjugate gradients, Computer J. 7 (1964), 149–154.

3. R. Fletcher, Practical Methods of Optimization, Wiley, New York 1987.

4. J.C. Gilbert and J. Nocedal, Global convergence properties of conjugate gradient methods for optimization, SIAM J. Optimization 2 (1992), 21-42.

5. D.C. Liu and J. Nocedal, On the limited memory BFGS method for large scale optimization methods, Math. programming 45 (1989), 503-528.

6. J.J. Moré and D.J. Thuente, Line search algorithms with guaranteed sufficient decrease, ACM Trans. Math. Software, 20 (1994), 286–307.

7. S.G. Nash, Solving nonlinear programming problems using truncated-Newton techniques, pp. 119-136 in: Numerical Optimization 1984 (P.T. Boggs et al., eds.), SIAM, Philadelphia 1985.

8. A. Neumaier, A fast and robust efficient line search. In preparation. (See

http://solon.cma.univie.ac.at/~neum/software/ls/ for Matlab

code.)

9. J. Nocedal, Theory of algorithms for unconstrained opimization, pp. 199-242 in: Acta Numerica 1992 (A. Iserles, ed.), Cambridge Univ. Press, Cambridge 1992.

10. M.J.D. Powell, Restart procedures for the conjugate gradient method, Math. Programming 12 (1977), 241-254.

11. M. J. D. Powell, Convergence properties of algorithmus for nonlinear optimization, SIAM Rev. 28 (1986), 487-500.

12. W. Warth and J. Werner, Effiziente Schrittweitenfunktionen bei unrestringierten Optimierungsaufgaben, Computing 19 (1977), 59-72.