Convergence of the descent Dai–Yuan conjugate gradient method for unconstrained optimization

Abstract

The conjugate gradient method is one of the most useful and the earliest-discovered techniques for solving large-scale nonlinear optimization problems. Many variants of this method have been proposed, and some are widely used in practice. In this article, we study the descent Dai–Yuan conjugate gradient method which guarantees the sufficient descent condition for any line search. With exact line search, the introduced conjugate gradient method reduces to the Dai–Yuan conjugate gradient method. Finally, a global convergence result is established when the line search fulfils the Goldstein conditions.

Keywords

Conjugate gradient method descent condition global convergence Goldstein conditions line search unconstrained optimization

1. Introduction

Conjugate gradient methods are very important tools for solving nonlinear optimization problems, especially for large-scale problems. In fact, the conjugate gradient methods are not among the faster or more robust optimization algorithms for nonlinear problems available today, but are very popular for engineers and mathematicians who are interested in solving large-scale problems (Nocedal, 1992; Polak, 1997). We consider the unconstrained optimization problem

(1)

where f : ℝⁿ → ℝ is a smooth function and its gradient ∇f is available and we use g(x) to denote the gradient of f(x). We are concerned with the conjugate gradient methods for solving (1). In general, these methods have the following form:

(2)

(3)

where the step-length α_k is obtained by carrying out some line searches, d_k is the search direction, and β_k is a parameter. For general functions, different formulae for scalar β_k result in distinct nonlinear conjugate gradient methods (Dai and Yuan, 1999; Dai, 2003; Dai and Yuan, 2003). Several famous formulae for β_k result in the Polak–Ribiére–Polyal (PRP) method (Polyak, 1969), the Fletcher–Reeves (FR) method (Fletcher and Reeves, 1964), the Liu–Storey (LS) method (Liu and Storey, 1992), the Hestenes–Stiefel (HS) method (Hestenes and Stiefel, 1952), the conjugate descent (CD) method (Fletcher, 1997) and the Dai–Yuan (DY) method (Dai and Yuan, 2000). They are specified by

(4)

(5)

(6)

where g_k is the abbreviation of g(x_k) and ‖ · ‖ denotes the Euclidean norm of vectors. In the FR method, if a bad direction and a tiny step from x_k−1 to x_k are generated, the next direction d_k and next step s_k = x_k − x_k−1 are also likely to be poor unless a restart along the gradient direction is performed (Yabe, 2004). In spite of such a defect, Zoutendijk (1970) proved that the FR method with exact line search is globally convergent. Al-Baali (1985) extended this result to inexact line searches. On the other hand, the PRP and HS methods perform similarly in terms of theoretical property. Both methods are preferred to the FR method in its numerical performance, because the methods essentially perform a restart after they encounter a bad direction. Nevertheless, Powell (1984) showed that the PRP and HS methods can cycle infinitely without approaching a solution, which implies that they do not have global convergence. The CD method was proved to have global convergence property under strong Wolfe line search with a strong restriction on the parameters (Dai and Yuan, 1996) and the DY method has global convergence under weak Wolfe line search (Dai and Yuan, 2000). Recently, Shi and Shen (2007) proposed a new line search procedure and investigated the global convergence of the original LS method. Andrei (2008) proposed a modification of the DY conjugate gradient algorithm.

In this article, we consider the descent Dai–Yuan conjugate gradient method for solving (1) (Yu et al., 2008) The descent DY conjugate gradient method generates a sequence of iterates by letting

(7)

where the step-length α_k is positive, and the direction d_k is defined by

(8)

(9)

where constant

m >14

, g_k+1 = ∇f(x_k+1) and y_k = g_k+1 − g_k. If f is a quadratic and α_k is chosen to achieve the exact minimum of f in the direction d_k, then

d_{k}^{T} g_{k + 1} = 0

, and the formula (9) for

β_{k}^{DDY}

reduces to the DY method.

The article is organized as follows. In Section 2, we prove that, for any inexact line search the proposed direction satisfies the descent condition $g_{k + 1}^{T} d_{k + 1} \leq - (1 - 1 / 4 m) ‖ g_{k + 1} ‖^{2}$ . By using (8) and (9), we present the descent DY conjugate gradient method, that is Algorithm 1, in Section 3. Then we prove that the proposed conjugate gradient method with Goldstein line search is globally convergent. Finally a brief conclusion ends this article in Section 4.

2. The proof of the sufficient descent condition

An attractive feature of the descent DY conjugate gradient method, which we establish, is that the search directions always yield descent when $y_{k}^{T} d_{k} \neq 0$ . This feature is presented in the following lemma.

Theorem 1.

Let

(10)

where β^DDY given by (9). If

y_{k}^{T} d_{k} \neq 0

, then

(11)

Proof.

By multiplying d₀ = −g₀ by $g_{0}^{T}$ , we obtain $g_{0}^{T} d_{0} = - ‖ g_{0} ‖^{2}$ , which satisfies (11). Now multiplying (10) by $g_{k + 1}^{T}$ , we can write

(12)

Now let

(13)

Substituting (13) in (12) gives us

(14)

Also for arbitrary a and m > ¼, we can write

(15)

It follows from (14) and (15) that

The proof is complete.□

From the above theorem, the introduced direction given by (8) and (9) is a descent direction. In the next section, we present the convergence theorem to the method given by (8) and (9) for a strongly convex function.

3. Convergence of the descent Dai–Yuan conjugate gradient method

In the previous section, it is proved that the direction given by (8) and (9) is a descent direction. In this section, by using (8) and (9), we establish a new convergent method. For this purpose, we need to constrain the choice of α_k to ensure convergence. There are many approaches for finding an available step-length. Among them, the exact line search is ideal, but is costly or even impossible to use for finding the step-length. Also we know that with exact line search, the descent DY conjugate gradient method reduces to the DY conjugate gradient method. Some inexact line searches techniques are useful and effective in practical computation, such as standard Wolfe line search (Nocedal and Wright, 1999), the strong Wolfe line search (Yuan, 1993), the Armijo line search (Armijo, 1966), the new Armijo line search (Shi and Shen, 2007) and Goldstein line search (Fletcher, 1997). Here, we consider the line search that satisfies the Goldstein conditions:

(16)

where

0 {<c}_{2} <12 {<c}_{1} <1,

and α_k > 0 (Hager and Zhang, 2005).

Now applying (8) and (9), we propose the following algorithm.

Algorithm 1

Step 1. Choose x₀ ∈ ℝⁿ, set d₀ = −g₀ and k ≔ 0.

Step 2. If ‖g_k‖ = 0 then stop; otherwise go to Step 3.

Step 3. Set x_k+1 = x_k + α_kd_k where d_k is defined by (8) and (9), and α_k satisfies the Goldstein line search (16).

Step 4. Set k ≔ k + 1 and go to Step 2.

For convenience, we first present the following assumption which has often been used in the literature to analyze the global convergence of conjugate gradient methods with inexact line searches.

Assumption 1.

Suppose that f is strongly convex and Lipschitz continuous on the level set

(17)

and the level set ℒ is bounded. That is, there exist constants L and μ > 0 such that

(18)

and

(19)

for all x and y ∈ ℒ. We assume, without loss of generality, that the constant L > 1.

Under the above assumptions on f, there exists a constant ω such that

Now we establish the global convergence theorem for Algorithm 1 as follows:

Theorem 2.

Suppose that Assumption 1 holds and the sequence {x_k} is generated by Algorithm 1. Then either g_k = 0 for some k, or

(20)

Proof.

We proceed by contradiction, assuming that the theorem is not true. Then g_k ≠ 0 for all k and lim inf_k→∞ ‖g_k‖ ≠ 0. Hence there exists a positive constant γ such that

(21)

From Assumption 1, the Goldstein conditions (16) and the descent condition, we can show that (Hager and Zhang, 2005)

(22)

Also, because of the strong convexity assumption, we have

(23)

Theorem 1 and the assumption g_k ≠ 0 imply d_k ≠ 0. Now from α_k > 0, μ > 0 and d_k ≠ 0, we have

y_{k}^{T} d_{k} >0

. Since f is strongly convex over ℒ, we find that f is bounded from below. After summing over k the upper bound in (16), we conclude that

(24)

Also from Theorem 1 and g_k ≠ 0, we have

g_{k}^{T} d_{k} <0

, then

(25)

Now using (24) and (25), it is not difficult to obtain

(26)

By multiplying (22) by

| g_{k}^{T} d_{k} |

, we obtain

(27)

Thus,

(28)

It follows from (11) and (25) that

(29)

Squaring both sides of the above inequality, gives us

(30)

Dividing both sides by ‖d_k‖², we have

(31)

Therefore, from (21), (28) and (31), we can obtain

(32)

By (29) and the Cauchy–Schwartz inequality, we have

which implies

(33)

By considering the above results, it is not difficult to obtain

(34)

Now let

where M = maximum_x∈ℒ‖∇f(x)‖. By substituting P and Q into (34), we have

(35)

Therefore

(36)

Note that the necessary condition of the series convergence (36) contradicts (32). Hence,

(37)

The proof is complete.□

4. Conclusion

The conjugate gradient methods play a special role for solving large-scale nonlinear optimization due to the simplicity of their iteration and their very low memory requirements. In this article, we have studied the descent DY conjugate gradient method, that is Algorithm 1, for solving unconstrained optimization problems. We have proven that the presented direction satisfies the descent condition $g_{k + 1}^{T} d_{k + 1} \leq - (1 - 1 / 4 m) ‖ g_{k + 1} ‖^{2}$ where constant $m >14$ , is independent of the line search procedure, as long as $y_{k}^{T} d_{k} \neq 0$ . Under the Goldstein line search conditions, we have proven the global convergence of the conjugate gradient method.

Footnotes

Acknowledgments

The authors are very much indebted to the anonymous referees for their valuable comments and careful reading of the manuscript.

Funding

This research received no specific grant from any funding agency in the public, commercial, or not-for-profit sectors.

References

Al-Baali

(1985) Descent property and global convergence of the Fletcher–Reeves method with inexact line search. IMA Journal of Numerical Analysis 5: 121–124.

Andrei

(2008) A Dai–Yuan conjugate gradient algorithm with sufficient descent and conjugacy conditions for unconstrained optimization. Applied Mathematics Letters 21: 165–171.

Armijo

(1966) Minimization of functions having Lipschits continuous partial derivatives. Pacific Journal of Mathematics 16: 1–3.

Dai

(2003) A family of hybrid conjugate gradient methods for unconstrained optimization. Mathematics of Computation 72: 1317–1328.

Dai

Yuan

(1999) A nonlinear conjugate gradient method with a strong global convergence property. SIAM Journal on Optimization 10: 177–182.

Dai

Yuan

(1996) Convergence properties of the conjugate descent method. Advances in Mathematics 25: 552–562.

Dai

Yuan

(2000) A nonlinear conjugate gradient with a strong global convergence properties. SIAM Journal on Optimization 10: 177–182.

Dai

Yuan

(2003) A class of globally convergent conjugate gradient methods. Science in China Series A: Mathematics 46: 251–262.

Fletcher R (1997) Practical Method of Optimization, 2nd edn (Unconstrained Optimization, Vol. I). New York: Wiley.

10.

Fletcher

Reeves

(1964) Function minimization by conjugate gradients. Computer Journal 7: 149–154.

11.

Hager

Zhang

(2005) A new conjugate gradient method with guaranteed descent and an efficient line search. SIAM Journal on Optimization 16: 170–192.

12.

Hestenes

Stiefel

(1952) Method of conjugate gradient for solving linear equations. Journal of Research National Bureau of Standards 49: 409–436.

13.

Liu

Storey

(1992) Efficient generalized conjugate gradient algorithms, part 1: theory. Journal of Optimization Theory and Applications 69: 129–137.

14.

Nocedal

(1992) Theory of algorithms for unconstrained optimazation. Acta Numerica 1: 199–242.

15.

Nocedal

Wright

(1999) Numerical Optimization. New York: Springer-Verlag.

16.

Polak

(1997) Optimazation: Algorithms and Consistent Approximations. New York: Springer-Verlag.

17.

Polyak

(1969) The conjugate gradient method in extreme problems. USSR Computational Mathematics and Mathematical Physics 9: 94–112.

18.

Powell MJD (1984) Nonconvex Minimization Calculations and the Conjugate Gradient Method (Lecture Notes in Mathematics, Vol. 1066). Berlin: Springer-Verlag, pp. 122–141.

19.

Shi

Shen

(2007) Convergence of Liu–Storey conjugate gradient method. European Journal of Operational Research 182: 552–560.

20.

Yabe

(2004) Global convergence properties of nonlinear conjugate gradient methods with modified secant condition. Computational Optimization and Applications 28: 203–225.

21.

Guan

Chen

(2008) Spectral conjugate gradient methods with sufficient descent property for largescale unconstrained optimization. Optimization Methods and Software 23: 275–293.

22.

Yuan

(1993) Numerical Methods for Nonlinear Programming. Shanghai: Shanghai Scientific and Technical Publishers.

23.

Zoutendijk

Abadie

(1970) Nonlinear programming, computational methods. Integer and Nonlinear Programming. Amsterdam: North-Holland.