# The Global Convergence of a New Mixed Conjugate Gradient Method for Unconstrained Optimization

Authors: Yang Yueting; Cao Mingyuan
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

We propose and generalize a new nonlinear conjugate gradient method for unconstrained optimization. The global convergence is proved with the Wolfe line
search. Numerical experiments are reported which support the theoretical analyses and show the presented methods outperforming CGDESCENT method.


---

## Body

## 1. Introduction

This paper is concerned with conjugate gradient methods for unconstrained optimization(1.1)minf(x),x∈ℜn,
where f(x):ℜn→ℜ is continuously differentiable and bounded from below. Starting from an initial point x1, a nonlinear conjugate gradient method generates sequences {xk} and {dk} by the below iteration
(1.2)xk+1=xk+αkdk,k≥1,
where αk is a step length which is determined by a line search and the direction dk is generated as
(1.3)dk={-gk,ifk=1,-gk+βkdk-1,ifk≥2,
where gk=∇f(xk) is the gradient of f(x) at xk and βk is a scalar.Different conjugate gradient algorithms correspond to different choices for the scale parameterβk. The well-known formulae of βk are given by
(1.4)βkFR=∥gk∥2∥gk-1∥2,βkPR=gkT(gk-gk-1)∥gk-1∥2,βkDY=∥gk∥2dk-1T(gk-gk-1),βkHS=gkT(gk-gk-1)dk-1T(gk-gk-1),
which are called Fletcher-Reeves [1] (FR), Polak-Ribière-Polyak [2] (PRP), Dai-Yuan [3] (DY), and Hestenes-Stiefel [4] (HS), respectively. Though FR and DY have strong convergence properties, they may have modest practical performance. While PRP and HS often have better computational performance, but they may not generally be convergent.These motivate us to derive some efficient algorithms. In this paper, we focus on mixed conjugate gradient methods. These methods are combinations of different conjugate gradient methods. The aim of this paper is to propose the new methods that possess both convergence and well numerical results.The line search in the conjugate gradient algorithms is often based on the Wolfe inexact line search(1.5)f(xk+αkdk)≤f(xk)+δαkgkTdk,(1.6)g(xk+αkdk)Tdk≥σgkTdk,
where 0<δ<σ<1.Many research on the parameterβk have been concerned [5–7]. Such as Al-Baali [8] proved that FR global convergent with inexact line search in which σ<1/2. Liu et al. [9] spread the results of [8] to the case of σ=1/2. Dai and Yuan [10] gave an example when σ>1/2, FR may produce a rise direction.PRP is famous as the best performance of all conjugate gradient methods which is the restart method in nature. When the directiondk-1 is small and the factor gk-gk-1 in the numerator of βkPRP tends to zero, the search direction dk is close to -gk. Gilbert and Nocedal [11] proposed PRP+ which is the most successful modified method, that is,
(1.7)βkPRP+=max{βkPRP,0}.
Dai and Yuan [12] presented DY method and proved the global convergence when the line search satisfies the Wolfe conditions. Zheng et al. [13] derived
(1.8)βknew=gkT(gk-dk-1)dk-1T(gk-gk-1),βk={βknew,if0<gkTdk-1<min(2,1σ)∥gk∥2,βkDY,otherwise,
and discussed the properties of the new formulas.HS is similar to PRP. It is equal to PRP when using the precision line search. HS satisfies the conjugate condition which is different from other methods.Touati-Ahmed and Storey [14] gave
(1.9)βkTS={βkPRP,if0≤βkPRP≤βkFR,βkFR,otherwise.
Dai and Chen [15] proposed
(1.10)βk={βkHS,if0<gkTgk-1<min(2,1σ)∥gk∥2,βkDY,otherwise.
Dai and Ni [16] derived
(1.11)βk={-bβkDY,ifβkHS<-bβkDY,βkHS,if-bβkDY≤βkHS≤βkDY,βkDY,ifβkHS>βkDY.
Throughout the paper, ∥·∥ stands for the Euclidean norm.Hager and Zhang (CGDESCENT) [17] proposed a conjugate gradient method with guaranteed descent which corresponds to the following choice for the update parameters: β-kN=max{βkN,ηk}, where
(1.12)ηk=-1∥dk∥min{η,∥gk∥},βkN=1dkTyk(yk-2dk∥yk∥2dkTyk)Tgk+1.
Here, η>0 is a constant. The extensive numerical tests and comparisons with other methods showed that this method has advantage in some aspects.Zhang et al. (ZZL) [18] derived a descent modified PRP conjugate method, the direction dk is generated by
(1.13)dk={-gk,ifk=1,-gk+βkPRPdk-θkyk-1,ifk≥2.
The numerical results suggested that the efficiency of the MPRP method is encouraging.Consider the above mixed techniques and the properties of the classical conjugate gradient methods, the new mixed methods will be presented. The main difference between the new methods and the existed methods are the choice ofβk and giving the generalization of the new method. Moreover, the direction generated by the new methods are descent directions of the objective function under mild conditions. In the numerical results, the method’s overall performance will be given.Firstly, we present a new formula(1.14)βknew=gkTgkμ|gkTdk-1|+dk-1T(gk-gk-1).The rest of the paper is organized as follows. In Section2, we give a new mixed conjugate gradient algorithm and convergence analysis. Section 3 is devoted to a generalization of the new mixed method. In the last section, numerical results and comparisons with the CGDESCENT and ZZL methods on test problems are reported and show the advantage of the new methods.


## 2. A New Algorithm and Convergence Analysis

We discuss a new mixed conjugate gradient method(2.1)βk*={βknew,if∥gk∥2≥|gkTgk-1|,0,otherwise,
where μ≥1.Algorithm 2.1.
Step1. Give x1∈ℜn, ε>0, d1=-g1; k:=1.
Step2. If ∥gk∥<ε, stop, else go to Step 3.
Step3. Find αk satisfying Wolfe conditions (1.5) and (1.6).
Step4. Compute new iterative xk+1 by xk+1=xk+αkdk.
Step5. Compute βk by (2.1), dk+1=-gk+1+βk+1dk, k:=k+1, go to Step 2.In order to derive the global convergence of the algorithm, we use the following assumptions.H 2.1
The objective functionf(x) is bounded in the level set as below
(2.2)L1={x∈ℜn∣f(x)≤f(x1)},
where x1 is the starting point.H 2.2
f(x) is continuously differentiable in a neighborhood N of L1 and its gradient g(x) is Lipschitz continuous, there exists a constant L>0 such that
(2.3)∥g(x)-g(y)∥≤L∥x-y∥,∀x,y∈N.Lemma 2.2 (see Zoutendijk condition [19]).
Suppose that H 2.1 and H 2.2 hold. If the conjugate gradient method satisfiesgkTdk<0, then
(2.4)∑k=1∞‍(gkTdk)2∥dk∥2<+∞.Theorem 2.3.
Suppose that H 2.1 and H 2.2 hold. Let{xk} and {dk} be generated by (1.2) and (1.3), where βk is computed by (2.1), αk satisfies Wolfe line search conditions, then gkTdk<0 holds for all k≥1.Proof.
The conclusion can be proved by induction. Whenk=1, we have g1Td1=-∥g1∥2<0. Suppose that gk-1Tdk-1<0 hold for k. From (1.3), we have
(2.5)gkTdk=-∥gk∥2+βkgkTdk-1≤-∥gk∥2+|βk||gkTdk-1|.
Whenβk*=0, it is obvious that
(2.6)gkTdk≤-∥gk∥2<0.
Whenβk=βknew, from (1.6) we have
(2.7)dk-1T(gk-gk-1)=gkTdk-1-gk-1Tdk-1≥σgk-1Tdk-1-gk-1Tdk-1=(σ-1)gk-1Tdk-1>0.
Then,
(2.8)gkTdk≤-∥gk∥2+∥gk∥2μ|gkTdk-1|+dk-1T(gk-gk-1)|gkTdk-1|≤-∥gk∥2+∥gk∥2μ|gkTdk-1||gkTdk-1|=(-1+1μ)∥gk∥2,
from μ≥1, then we can deduce that gkTdk<0 holds for all k≥1.
Thus, the theorem is proved.Theorem 2.4.
Suppose that H 2.1 and H 2.2 hold. Consider Algorithm2.1, where βk is determined by (2.1), if gk≠0 holds for any k, then,
(2.9)liminfk→∞∥gk∥=0.Proof.
By contradiction, assume that (2.9) does not hold. Then there exists a constant ε>0, such that
(2.10)∥gk∥>ε,∀k≥1.
From (2.1),
(2.11)0≤βk*≤∥gk∥2dk-1T(gk-gk-1)=βkDY.
By (1.3), if βk=βkDY, we derive
(2.12)gkTdk=-∥gk∥2+∥gk∥2dk-1T(gk-gk-1)gkTdk-1=βkDYgk-1Tdk-1.
Then,(2.13)βkDY=gkTdkgk-1Tdk-1.
So,(2.14)|βk*|≤|βkDY|=|gkTdkgk-1Tdk-1|.
From (1.3), we have
(2.15)dk+gk=βkdk-1.
By squaring the two sides of (2.15) and transferring and trimming, we get
(2.16)∥dk∥2=-∥gk∥2-2gkTdk+βk2∥dk-1∥2.
Then,
(2.17)∥dk∥2≤-∥gk∥2-2gkTdk+(gkTdk)2(gk-1Tdk-1)2∥dk-1∥2,∥dk∥2(gkTdk)2≤-2gkTdk+∥dk-1∥2(gk-1Tdk-1)2-∥gk∥2(gkTdk)2≤∥dk-1∥2(gk-1Tdk-1)2+1∥gk∥2.
Since,
(2.18)∥d1∥2(g1Td1)2=∥g1∥2(-g1Tg1)2=1∥gk∥2,∥dk∥2(gkTdk)2≤∑i≥1‍1∥gi∥2.
From (2.10), we have
(2.19)∑i≥1‍1∥gi∥2≤kε2.
Therefore,
(2.20)(gkTdk)2∥dk∥2≥ε2k,∑k≥1‍(gkTdk)2∥dk∥2=+∞.
This is a contradiction to Lemma 2.2, the global convergence is got.


## 3. Generalization of the New Method and Convergence

The generalization of the new mixed method is as follows:(3.1)βk**={λβknew,if∥gk∥2≥|gkTgk-1|,0,otherwise,
where βknew=gkTgk/(μ|gkTdk-1|+dk-1T(gk-gk-1)), μ>1>λ>0.Algorithm 3.1.
Step1–Step4 are the same as that of Algorithm 2.1.
Step5. Compute βk by (3.1), dk+1=-gk+1+βk+1dk, k:=k+1, go to Step 2.Theorem 3.2.
Suppose that H 2.1 and H 2.2 hold. Let{xk} and {dk} be generated by (1.2) and (1.3), where βk is computed by (3.1), αk satisfies Wolfe line search conditions, then gkTdk<0 holds for all k≥1.Proof.
The conclusion can be proved by induction. Whenk=1, we have g1Td1=-∥g1∥2<0. Suppose that gk-1Tdk-1<0 holds. For k, it is obvious that if βk**=0, then
(3.2)gkTdk≤-∥gk∥2<0.
Whenβk=λβknew, from (2.5) and (3.1), we have
(3.3)gkTdk≤-∥gk∥2+λ(gkTgk)μ|gkTdk-1|+dk-1T(gk-gk-1)|gkTdk-1|≤-∥gk∥2+λ∥gk∥2μ|gkTdk-1||gkTdk-1|≤-∥gk∥2+λμ∥gk∥2=∥gk∥2(λμ-1)<0.
To sum up, the theorem is proved.Theorem 3.3.
Suppose that H 2.1 and H 2.2 hold. Consider Algorithm3.1, where βk is determined by (3.1), if gk≠0 holds for any k, then,
(3.4)liminfk→∞∥gk∥=0.Proof.
By contradiction, assume that (3.4) does not hold. Then there exists a constant γ>0 such that
(3.5)∥gk∥>γ,∀k≥1.
From (3.1)
(3.6)0≤βk**≤λ∥gk∥2dk-1T(gk-gk-1)≤∥gk∥2dk-1T(gk-gk-1)=βkDY.
By (1.3), we have
(3.7)dk+gk=βkdk-1.
Then,(3.8)∥dk∥2=-∥gk∥2-2gkTdk+βk2∥dk-1∥2.
From (3.6),
(3.9)∥dk∥2≤-∥gk∥2-2gkTdk+(gkTdk)2(gk-1Tdk-1)2∥dk-1∥2,∥dk∥2(gkTdk)2≤-2gkTdk+∥dk-1∥2(gk-1Tdk-1)2-∥gk∥2(gkTdk)2≤∥dk-1∥2(gk-1Tdk-1)2+1∥gk∥2,∥dk∥2(gkTdk)2≤∑i≥1‍1∥gi∥2.
By (3.5), we have
(3.10)(gkTdk)2∥dk∥2≥γ2k,∑k≥1‍(gkTdk)2∥dk∥2=+∞.
This is a contradiction to Lemma 2.2, and the global convergence is proved.


## 4. Numerical Results

This section is devoted to test the implementation of the new methods. We compare the performance of the new methods with the CGDESCENT and ZZL methods.All tests in this paper are implemented on a PC with 1.8 MHz Pentium IV and 256 MB SDRAM using MATLAB 6.5. Ifε=10-6 then stop. Some classical test functions with standard starting points are selected to test the methods. These functions are widely used in the literature to test unconstrained optimization algorithms [20].In the table, the four reported data(k/nf/ng/t) are iteration numbers/function evaluations/gradient evaluations/CPU time(s), and ∥gk∥2 stands for the square of the gradient at the final iterate. When we set μ=1, λ=0.5, η=0.01, δ=0.01, σ=0.8, the numerical results of the NEW1 and NEW2 are listed in Table 1 and the CGDESCENT and ZZL (NEW3) are listed in Table 2. When we set μ=1.5, λ=0.1, η=10, δ=0.1, σ=0.9, the numerical results of the NEW 1 (NEW4) and NEW 2 (NEW5) are listed in Table 3 and the CGDESCENT (NEW6) and ZZL (NEW7) are listed in Table 4. It can be observed from Tables 1–4 that for the most of problems, the implementation of the new methods are superior to other methods from the iteration numbers, the calls of function, and gradient evaluations.Table 1
Numerical results of the NEW1 and NEW2.
Number
Prob.
dim
k
/
nf
/
ng
/
t(NEW1)∥gk∥2 (NEW1)
k
/
nf
/
ng
/
t(NEW2)∥gk∥2 (NEW2)
1
Powell badly scaled
2
6
/
20
/
9
/
0.0010
9
/
25
/
11
/
0.0010
0.2511
0.2709
2
Brown badly scaled
2
9
/
26
/
12
/
0.0010
9
/
26
/
11
/
0.0010
0
9.1712
e
-
005
3
Trigonometric function
10
11
/
48
/
29
/
0.0010
13
/
58
/
37
/
0.0020
0.0056
0.0061
4
Chebyquad
100
30
/
42
/
33
/
0.3594
61
/
72
/
65
/
0.4375
0.0258
0.0207
5
Penalty functionI
100
5
/
20
/
12
/
0.0313
5
/
20
/
12
/
0.0313
5.4750
e
-
005
6.8047
e
-
005
500
11
/
36
/
23
/
0.0010
10
/
34
/
20
/
0.0010
1.5626
e
-
004
3.9363
e
-
004
6
Allgower
500
4
/
32
/
8
/
0.0156
4
/
32
/
8
/
0.0313
0.0147
0.0215
7
Variable dimension
500
12
/
50
/
14
/
0.0625
12
/
50
/
14
/
0.0313
5.9262
e
-
006
5.9262
e
-
006
1000
16
/
54
/
16
/
0.0313
16
/
54
/
16
/
0.0313
1.1473
e
-
004
1.1473
e
-
004
5
Penalty functionI
1000
19
/
44
/
26
/
0.0313
22
/
48
/
30
/
0.0156
0.0010
3.8348
e
-
004
8
Integral equation
1000
2
/
24
/
2
/
0.0010
2
/
24
/
2
/
0.0020
0.0032
0.0058
9
Separable cubic
1000
9
/
12
/
11
/
0.3594
9
/
13
/
11
/
0.4219
6.1814
e
-
004
4.0438
e
-
005
3000
10
/
14
/
13
/
2.5469
9
/
13
/
12
/
2.4063
7.2599
e
-
005
2.0012
e
-
004Table 2
Numerical results of the CGDESCENT and NEW3.
Number
Prob.
dim
k
/
nf
/
ng
/
t(CGDESCENT) ∥gk∥2 (CGDESCENT)
k
/
nf
/
ng
/
t(NEW3) ∥gk∥2 (NEW3)
1
Powell badly scaled
2
6
/
16
/
7
/
0.0851
13
/
38
/
20
/
0.0313
0.2704
0.4305
2
Brown badly scaled
2
13
/
33
/
14
/
0.0010
20
/
82
/
44
/
0.0313
0
0.9525
3
Trigonometric function
10
12
/
56
/
33
/
0.0010
11
/
44
/
27
/
0.0313
0.0075
0.0598
4
Chebyquad
100
64
/
75
/
67
/
0.4219
38
/
58
/
44
/
0.2344
0.0178
0.0175
5
Penalty functionI
100
5
/
20
/
12
/
0.0313
10
/
37
/
10
/
0.0313
5.4750
e
-
005
3.4737
e
-
004
500
10
/
34
/
20
/
0.0313
9
/
27
/
15
/
0.0010
3.8011
e
-
005
2.5130
e
-
004
6
Allgower
500
4
/
32
/
8
/
0.1256
4
/
32
/
8
/
0.1250
0.0259
0.0089
7
Variable dimension
500
12
/
50
/
14
/
0.0528
12
/
50
/
14
/
0.0313
5.9262
e
-
006
5.9269
e
-
004
1000
16
/
54
/
16
/
0.0313
16
/
53
/
16
/
0.0010
1.1473
e
-
004
5.6730
e
-
005
5
Penalty functionI
1000
22
/
49
/
31
/
0.0313
21
/
50
/
30
/
0.0625
3.1604
e
-
004
3.4038
e
-
004
8
Integral equation
1000
2
/
24
/
2
/
0.0010
2
/
24
/
2
/
0.0010
0.0028
0.0156
9
Separable cubic
1000
13
/
16
/
14
/
0.5469
16
/
20
/
20
/
0.5000
2.5196
e
-
004
2.1274
e
-
004
3000
10
/
14
/
13
/
2.5469
10
/
14
/
13
/
2.5469
7.6877
e
-
005
2.2646
e
-
004Table 3
Numerical results of the NEW4 and NEW5.
Number
Prob.
dim
k
/
nf
/
ng
/
t(NEW4) ∥gk∥2 (NEW4)
k
/
nf
/
ng
/
t(NEW5) ∥gk∥2 (NEW5)
1
Powell badly scaled
2
12
/
25
/
13
/
0.0010
9
/
21
/
10
/
0.0010
0.3511
0.3709
2
Brown badly scaled
2
14
/
36
/
15
/
0.0010
9
/
26
/
10
/
0.0313
7.6024
e
-
005
1.1840
3
Trigonometric function
10
11
/
45
/
27
/
0.0010
13
/
51
/
33
/
0.0020
0.0026
0.0017
4
Chebyquad
44
/
58
/
47
/
0.3281
72
/
82
/
73
/
0.3750
0.0430
0.0251
5
Penalty functionI
100
5
/
20
/
12
/
0.0313
5
/
20
/
12
/
0.0313
5.4750
e
-
005
5.4750
e
-
005
500
9
/
27
/
16
/
0.0156
9
/
27
/
16
/
0.0313
7.0807
e
-
004
7.4979
e
-
004
6
Allgower
500
4
/
32
/
8
/
0.0010
4
/
32
/
8
/
0.0020
0.0026
0.0017
7
Variable dimension
500
17
/
53
/
19
/
0.0313
19
/
53
/
19
/
0.0313
3.9292
e
-
008
2.8061
e
-
008
1000
16
/
54
/
16
/
0.0313
16
/
54
/
16
/
0.0010
1.1473
e
-
004
1.1473
e
-
004
5
Penalty functionI
1000
11
/
31
/
13
/
0.0313
11
/
31
/
13
/
0.0313
0.0041
0.0036
8
Integral equation
1000
2
/
24
/
2
/
0.0020
2
/
24
/
2
/
0.0625
0.0041
0.0936
9
Separable cubic
1000
15
/
17
/
16
/
0.4531
10
/
12
/
11
/
0.2969
3.8684
e
-
004
7.7732
e
-
004
3000
16
/
20
/
20
/
4.3750
14
/
16
/
15
/
3.3438
1.3230
e
-
005
7.4737
e
-
006Table 4
Numerical results of the NEW6 and NEW7.
Number
Prob.
dim
k
/
nf
/
ng
/
t(NEW6) ∥gk∥2(NEW6)
k
/
nf
/
ng
/
t(NEW7) ∥gk∥2(NEW7)
1
Powell badly scaled
2
14
/
29
/
15
/
0.0313
19
/
54
/
30
/
0.0313
0.4181
0.7893
2
Brown badly scaled
2
3
/
22
/
3
/
0.0156
41
/
111
/
69
/
0.0010
1.0000
e
+
006
3.8332
e
+
004
3
Trigonometric function
10
2
/
26
/
2
/
0.0010
15
/
63
/
40
/
0.0010
0.0059
0.7360
4
Chebyquad
4
/
14
/
5
/
0.0625
36
/
56
/
41
/
0.2344
1.5078
0.0188
5
Penalty functionI
100
5
/
20
/
12
/
0.0313
10
/
37
/
10
/
0.0313
5.4750
e
-
005
3.4737
e
-
004
500
9
/
27
/
15
/
0.0313
9
/
27
/
15
/
0.0010
7.1267
e
-
004
2.5130
e
-
004
6
Allgower
500
4
/
32
/
8
/
0.0010
4
/
32
/
8
/
0.0938
0.0059
0.0563
7
Variable dimension
500
17
/
53
/
19
/
0.0313
19
/
55
/
20
/
0.0010
2.8061
e
-
008
2.4868
e
-
006
1000
16
/
54
/
16
/
0.0313
16
/
53
/
16
/
0.0010
1.1473
e
-
004
5.6730
e
-
005
5
Penalty functionI
1000
11
/
31
/
13
/
0.0416
11
/
31
/
13
/
0.0010
0.0010
0.0010
8
Integral equation
1000
2
/
24
/
2
/
0.0020
2
/
24
/
2
/
0.0625
0.0041
0.0936
9
Separable cubic
1000
9
/
12
/
11
/
0.4063
16
/
18
/
17
/
0.3906
6.5318
e
-
004
7.9504
e
-
004
3000
12
/
16
/
14
/
3.2969
20
/
22
/
22
/
4.3438
1.7672
e
-
005
5.7872
e
-
004Compared with the CGDESCENT method, the new methods are effective (see Table5).Table 5
γ
total (CGDESCENT)
1
γ
total (NEW1)
0.9220
γ
total (NEW2)
0.9270
γ
total (NEW3)
1.1347
γ
total (NEW4)
0.9895
γ
total (NEW5)
0.9415
γ
total (NEW6)
1.1595
γ
total (NEW7)
1.2164Using the formulaNtotal=nf+l*ng, where l is fixed constant, let l=3. By
(4.1)γi(NEW(j))=Ntotal(NEW(j))Ntotal(CGDESCET),
where j=1,2,…,7; i∈S, S is the whole of classical problems’ order. If γi(NEW(j))>1, then CGDESCENT method is regarded as better performance; if γi(NEW(j))=1, the methods have the same performances and if γi(NEW(j))<1, the new methods are performed better.We use(4.2)γtotal(NEW(j))=(Πi∈Sγi(NEW(j)))1/|S|
as a measure to compare the performance of CGDESCENT method and the new methods, where |S| is the number of S. If γtotal(NEW(j))<1, then NEW(j) method outperforms CGDESCENT method. The computational results are listed in Table 5.It is obvious thatγtotal(NEW(j))<1, where j=1,2,4,5, so we can deduce that the new methods outperform CGDESCENT method.



---

*Source: 932980-2012-10-16.xml*