# A New Conjugate Gradient Algorithm with Sufficient Descent Property for Unconstrained Optimization

Authors: XiaoPing Wu; LiYing Liu; FengJie Xie; YongFei Li
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

A new nonlinear conjugate gradient formula, which satisfies the sufficient descent condition, for solving unconstrained optimization problem is proposed. The global convergence of the algorithm is established under weak Wolfe line search. Some numerical experiments show that this new WWPNPRP+ algorithm is competitive to the SWPPRP+ algorithm, the SWPHS+ algorithm, and the WWPDYHS+ algorithm.


---

## Body

## 1. Introduction

In this paper, we consider the following unconstrained optimization problem:(1)min⁡fx∣x∈Rn,where f(x):Rn→R is a twice continuously differentiable function whose gradient is denoted by g(x):Rn→Rn. Its iterative formula is given by(2)xk+1=xk+tkdk,where(3)dk=-gkifk=1,-gk+βkdk-1ifk≥2,and tk is a step size which is computed by carrying out a line search, βk is a scalar, and gk denotes g(xk). There are at least six famous formulas for βk, which are given below:(4)βkHS=gkTgk-gk-1gk-gk-1Tdk-1,βkFR=gkTgkgk-1Tgk-1,βkPRP=gkTgk-gk-1gk-1Tgk-1,βkCD=-gkTgkdk-1Tgk-1,βkLS=-gkTgk-gk-1dk-1Tgk-1,βkDY=gkTgkgk-gk-1Tdk-1.To establish the global convergence results of the above conjugate gradient (CG) methods, it is usually required that the step sizetk should satisfy some line search conditions, such as the weak Wolfe-Powell (WWP) line search(5)fxk+tkdk-fxk≤δtkgkTdk,(6)gxk+tkdkTdk≥σgkTdk,where δ∈(0,1/2) and σ∈(δ,1), and strong Wolfe-Powell (SWP) line search (5) and(7)gxk+tkdkTdk≤-σgkTdk,where δ∈(0,1/2) and σ∈(δ,1). Wolfe-Powell is referred to as Wolfe.Considerable attentions have been made on the global convergence behaviors for the above methods. Zoutendijk [1] proved that the FR method with exact line search is globally convergent. Al-Baali [2] extended this result to the strong Wolfe line search conditions. In [3], Dai and Yuan proposed the DY method which produces a descent search direction at every iteration and converges globally provided that the line search satisfies the weak Wolfe conditions. In [4], Wei et al. discussed the global convergence of the PRP conjugate gradient method (CGM) with inexact line search for nonconvex unconstrained optimization. Recently, based on [5–7], Jiang et al. [8] proposed a hybrid CGM with(8)βkJHJ=gk2-max⁡0,gk/dk-1gkTdk-1,gk/gk-1gkTgk-1dk-1Tgk-gk-1.Under the Wolfe line search, the method possesses global convergence and efficient numerical performance.On some studies of the conjugate gradient methods, the sufficient descent condition(9)gkTdk≤-cgk2,c>0is often used to analyze the global convergence of the nonlinear conjugate gradient method with the inexact line search techniques. For instance, Touati-Ahmed and Storey [9], Al-Baali [2], Gilbert and Nocedal [10], and Hu and Storey [11] hinted that the sufficient descent condition may be crucial for conjugate gradient methods. Unfortunately, this condition is hard to hold. It has been showed that the PRP method with the strong Wolfe Powell line search does not ensure this condition at each iteration. So, Grippo and Lucidi [12] managed to find some line searches which ensure the sufficient descent condition, and they presented a new line search which ensures this condition. The convergence of the PRP method with this line search had been established. Yu et al. [13] analyzed the global convergence of modified PRP CGM with sufficient descent property. Gilbert and Nocedal [10] gave another way to discuss the global convergence of the PRP method with the weak Wolfe line search. By using a complicated line search, they were able to establish the global convergence result of the PRP and HS methods by restricting the parameter βk in (3), not allowed to be negative; that is,(10)βk+=max⁡0,βkPRP,which yields a globally convergent CG method, being also computationally efficient [14]. In spite of the numerical efficiency of the PRP method, as an important defect, the method lacks the following descent property:(11)gkTdk≤0,∀k≥0,even for uniformly convex objective functions [15]. This motivated the researchers to pay much attention to finding some extensions of the PRP method with descent property. In this context, Yu et al. [16] proposed a modified form of βkPRP as follows:(12)βkDPRP=βkPRP-Cyk2gk4gk+1Tdk,with a constant C≥1/4, leading to a CG method with the sufficient descent property. Dai and Kou [17] propose a family of conjugate gradient methods and an improved Wolfe line search; meanwhile, to accelerate the algorithm, an adaptive restart along negative gradients method is introduced. Jiang and Jian [18] proposed two modified CGMs with disturbance factors based on a variant of PRP method; the two proposed methods not only generate sufficient descent direction at each iteration but also converge globally for nonconvex minimization if the strong Wolfe line search is used. A new hybrid conjugate gradient method was presented for unconstrained optimization. The proposed method can generate decent directions at every iteration; moreover, this property is independent of the steplength line search. Under the Wolfe line search, the proposed method possesses global convergence [19].The main purpose of this paper is to design an efficient algorithm which possesses the properties of global convergence, sufficient descent, and good numerical results. In next section, we present a new CG formula and give its properties. In Section3, the new algorithm and its global convergence result will be established. To test and compare the numerical performance of the proposed method, in the last part of this work, a large amount of medium-scale numerical experiments are reported by tables and performance profiles.


## 2. The Formula and Its Property

Because sufficient descent condition (9) is a very nice and important property to analyze the global convergence of the CG methods, we hope to find βk such that dk satisfies (9). In the following, we propose a sequence {βk} and prove that it has such property. Firstly, we give a definition of adescent sequence (or asufficient descent sequence): a sequence {βk} is called adescent sequence (or asufficient descent sequence) for the CG methods if there exists a constant τ∈(0,1) (or τ∈[0,1)) such that, for all k≥2,(13)βkgkTdk-1≤τgk2.By using (3), we have, for all k≥2,(14)gkTdk=-gk2+βkgkTdk-1.From the above discussion, we require that(15)-gk2+βkgkTdk-1≤0.The above inequality implies (13).In [20], the authors proposed a variation of the FR formula:(16)βkVFRμ=μ1gk2μ2gkTdk-1+μ3gk-12,where μ1∈(0,+∞), μ2∈[μ1+ϵ1,+∞), μ3∈(0,+∞), and ϵ1 is any given positive constant. It is easy to prove that {βkVFR} is a descent sequence (with τ=μ1/μ2) for CG methds if gkTdk≤0. Formula (16) possesses the sufficient descent property and proved that there exist some nonlinear conjugate gradient formulae possessing the sufficient descent property without any line searches, where(17)βkWYL=gkTgk-gk/gk-1gk-1Tgk-1.By restricting the parameter σ≤1/4 under the SWP line search condition, the WYL method possessed the sufficient descent condition [21].In [22], the authors designed the following variation of the PRP formula which possesses the sufficient descent property without any line searches:(18)βkNμ=gk2-gkTdk-1μgkTdk-1+gk-12ifgk2≥gkTdk-1,0Otherwise,in which μ≥1.Motivated by the ideas in [20, 22] without any line search and sufficient descent, and taking into account the good convergence properties of [10] and the good numerical performance in [14], we propose a class new formula about βk as follows:(19)βkNPRP=λμ1gk2+1-λμ1gk2-gkTgk-1μ2gkTdk-1+μ1gk-12,where the definitions of μ1,μ2 are the same as those in formula (16); λ∈(0,1).In order to ensure the nonnegative of the parameterβk, we define(20)βkNPRP+=max⁡0,βkNPRP.Thus if a negative of βkNPRP occurs, this strategy will restart the iteration along the steepest direction.The following two propositions show that the{βkNPRP+} is a descent sequence, so that dk can make sufficient descent condition (9) hold.Proposition 1.
Suppose thatβk is defined by (19)-(20); then one has that(21)βkNPRP+≤σ^gk2gkTdk-1,where 0<σ^=μ1/μ2<1.Proof.
It is clear that inequality (21) holds when βkNPRP+=0. Now we consider the case where βkNPRP+=βkNPRP. So we have(22)βkNPRP+=λμ1gk2+1-λμ1gk2-gkTgk-1μ2gkTdk-1+μ1gk-12≤λμ1gk2+1-λμ1gk2μ2gkTdk-1≤μ1μ2gk2gkTdk-1=σ^gk2gkTdk-1.Hence βkNPRP+ can make (21) hold. Furthermore {βkNPRP+} is a descent sequence without any line search.Proposition 2.
Suppose thatβk is defined by (19)-(20); then dk satisfies the sufficient descent condition (9) for all k≥1, where c=λ(1-μ1/μ2).Proof.
For anyk>1, suppose that gk-1Tdk-1<0.
IfβkNPRP+=0, then dk=-gk. So we have(23)gkTdk=-gk2≤-cgk2,where c=λ(1-μ1/μ2).
Otherwise, from the definition ofβkNPRP+, we can obtain (24)gkTdk=gkT-gk+λμ1gk2+1-λμ1gk2-gkTgk-1μ2gkTdk-1+μ1gk-12dk-1≤-gk2+λμ1gk2μ2gk-1Tdk-1gkTdk-1+1-λμ1gk2μ2gkTdk-1gkTdk-1≤-gk2+λμ1μ2gk2+gk2-λgk2≤-λgk2+λμ1μ2gk2≤-λ1-μ1μ2gk2=-cgk2.For g1Td1=-g12<0, we can deduce that dk can make sufficient descent condition (9) hold for all k≥1.By the proof of Proposition2, we can know that the formula μ1/μ2<1 is necessary; otherwise, the sufficient descent condition can not be held.


## 3. Global Convergence

In this section, we propose an algorithm related toβkNPRP+ and then we study the global convergence property of this algorithm. Firstly, we make the following two assumptions, which have been widely used in the literature to analyze the global convergence of the CG methods with the inexact line searches.Assumption A.
The level set(25)Ω=x∈Rn∣fx≤fx1is bounded.Assumption B.
The gradientg(x) is Lipschitz continuous; that is, there exists a constant L>0 such that, for any x,y∈Ω, (26)gx-gy≤Lx-y.Now we give the algorithm.Algorithm 3.
Step 0. Given x1∈Rn, set d1=-g1; k=1. If g1=0, then stop. Otherwise go to Step 1.
Step 1. Find tk>0 satisfying weak Wolfe conditions (5) and (6).
Step 2. Let xk+1=xk+tkdk and gk+1=g(xk+1). If gk+1=0, then stop. Otherwise go to Step 3.
Step 3. Compute βk+1NPRP+ by formula (19) and (20). Then generate dk+1 by (3).
Step 4. Set k=:k+1; go to Step 0.
Since{f(xk)} is decreasing sequence, it is clear that the sequence {xk} is contained in Ω, and there exists a constant f∗, such that(27)limk→∞⁡fxk=f∗.By using Assumptions A and B, we can deduce that there exists M>0 such that(28)gk≤M∀x∈Ω.The following important result was obtained by Zoutendijk [1] and Wolfe [23, 24].Lemma 4.
Supposef(x) is bounded below, and g(x) satisfies the Lipschitz condition. Consider any iteration method of formula (2), where dk satisfies dkTgk<0 and tk is obtained by the weak Wolf line search. Then(29)∑k=1∞gkTdk2dk2<+∞.The following lemma was obtained by Dai and Yuan [25].Lemma 5.
Assume that a positive series{ai} satisfies the following inequality for all k:(30)∑i=1kai≥lk+c,where l>0 and c are constant. Then one has(31)∑i≥1ai2i=+∞,∑k≥1ak2∑i=1kai=+∞.Theorem 6.
Suppose that Assumptions A and B hold;{xk} is a sequence generated by Algorithm 3. Then one has(32)liminfk→∞⁡gk=0.Proof.
Equation (3) indicates that, for all k≥2,(33)dk+gk=βkdk-1.Squaring both sides of (33), we obtain(34)dk2=-gk2-2gkTdk+βk2dk-12.Suppose that βkNPRP+=βkNPRP in (20). Then, (35)dk2=-gk2-2gkTdk+βkNPRP+2dk-12=-gk2-2gkTdk+λμ1gk2+1-λμ1gk2-gkTgk-1μ2gkTdk-1+μ1gk-122dk-12≤-gk2-2gkTdk+gk4dk-12gk-14.We have(36)hk≤hk-1-1gk2+2γkgk2,where hk=dk2/gk4 and γk=-gkTdk/gk2.
Note thath1=1/g12 and γ1=1. It follows from (36) that(37)hk≤-∑i=1k1gi2+2∑i=1kγigi2.Suppose that conclusion (32) does not hold. Then, there exists a positive scalar ϵ such that, for all k≥1,(38)gk≥ϵ.Thus, it follows from (28) and (38) that(39)hk≤-kM2+2ϵ2∑i=1kγi.Further, we have(40)hk≤2ϵ2∑i=1kγi.On the other hand, using hk≥0, relation (39) implies that(41)∑i=1kγi≥ϵ2k2M.Using Lemma 5 and (40), it follows that(42)∑k≥1gkTdk2dk2=∑k≥1γk2hk=+∞,which contradicts to Zoutendijk condition (29). This shows that (32) holds. The proof of the theorem is complete.From the proof of the above theorem, we can conclude that any conjugate gradient method with the formulaβkNPRP+ and some certain step size technique which ensures that Zoutendijk condition (29) holds is globally convergent. In particular, the formula βkNPRP+ with the weak Wolfe conditions can generate a globally convergent result.


## 4. Numerical Results

All methods above are tested on 56 test problems, where the former test problems 1–48 (from arwhead to woods) in Table1 are taken from the CUTE library in Bongartz et al. [26] and the others are taken from Moré et al. [27]; (43)DYHS:βk=max⁡0,min⁡βkHS,βkDYis generated by Grippo and Lucidi [12].Table 1
Numerical test report.
Name/n
SWPHS+
SWPPRP+
WWPNPRP+
WWPDYHS
Itr/NF/NG/Tcpu
Itr/NF/NG/Tcpu
Itr/NF/NG/Tcpu
Itr/NF/NG/Tcpu
arwhead 1000
10/293/98/0.078
204/5484/1606/1.462
6/92/6/0.026
23/275/32/0.073
arwhead 2000
16/441/139/0.184
261/6824/1825/2.753
6/97/6/0.035
23/325/43/0.135
arwhead 10000
31/952/301/1.554
366/11324/3139/17.892
8/154/13/0.219
8/138/12/0.206
chainwoo 1000
11/329/91/0.058
128/3745/1170/0.632
26/305/43/0.053
32/373/44/0.062
chnrosnb 20
3/72/13/0.004
3/72/13/0.004
3/72/17/0.004
3/72/13/0.004
chnrosnb 50
6/149/37/0.009
8/188/58/0.013
5/89/14/0.005
5/92/12/0.006
cosine 1000
13/368/153/0.236
3/113/38/0.159
30/121/32/0.048
1400/12416/1534/3.743
cragglvy 5000
1/1/2/0.026
1/1/2/0.026
1/1/2/0.026
1/1/2/0.026
cragglvy 10000
1/1/2/0.027
1/1/2/0.027
1/1/2/0.026
1/1/2/0.026
dixmaana 3000
1348/42287/19153/185.754
5/131/41/0.535
12/19/13/0.128
16/14/16/0.145
dixmaanb 3000
13/47/23/0.253
5/70/15/0.272
7/10/7/0.066
6/9/6/0.058
dixmaanc 3000
14/49/31/0.288
5/71/18/0.286
8/12/8/0.077
9/11/9/0.086
dixmaand 3000
144/4122/1686/17.815
5/72/21/0.289
11/16/11/0.109
12/13/12/0.116
dixmaani 3000
F/F/F/F
4/98/33/0.403
F/F/F/F
F/F/F/F
dixmaanj 3000
F/F/F/F
6/69/23/0.305
1086/602/1676/12.069
1522/1420/2937/18.554
dixmaanl 3000
13/355/134/1.506
3/71/18/0.272
F/F/F/F
F/F/F/F
dqdrtic 1000
F/F/F/F
1804/55951/22587/6.841
205/1470/205/0.205
71/484/71/0.064
dqdrtic 3000
F/F/F/F
1805/56040/22893/13.054
182/1301/182/0.334
96/648/96/0.165
dqdrtic 5000
F/F/F/F
1805/56078/23060/19.535
142/1029/142/0.390
79/530/79/0.204
dqrtic 6000
1/63/19/0.237
1/63/19/0.238
1/27/2/0.085
1/27/2/0.085
dqrtic 15000
1/30/2/0.234
1/30/2/0.235
1/30/2/0.234
1/30/2/0.235
dqrtic 20000
1/31/2/0.325
1/31/2/0.323
1/31/2/0.325
1/31/2/0.324
edensch 1000
1297/39852/18321/35.054
1202/37104/17643/21.938
34/181/39/0.171
58/263/77/0.265
engval1 3000
4/100/33/0.033
608/18698/7376/6.380
6/54/7/0.018
17/112/33/0.042
engval1 10000
4/100/28/0.092
580/17809/6994/17.446
7/58/10/0.056
19/146/45/0.155
engval1 20000
4/100/29/0.184
565/17366/6871/33.912
7/58/10/0.111
20/152/28/0.304
errinros 50
149/4029/1445/0.321
413/12363/4708/0.986
F/F/F/F
F/F/F/F
genhumps 2000
32/566/245/0.408
22/291/119/0.237
11/102/30/0.071
12/97/25/0.085
genhumps 15000
8/178/61/1.183
14/282/112/1.767
22/117/37/0.615
13/187/56/1.229
genhumps 20000
4/78/23/0.691
5/102/36/0.928
26/188/73/1.218
4/37/10/0.275
genrose 10000
1209/36119/12775/35.424
2/63/14/0.056
789/7297/792/7.213
263/2365/265/2.333
genrose 20000
1971/60100/21284/117.729
2/64/17/0.119
513/4754/515/9.346
297/2676/298/5.283
nondia 10000
1/41/10/0.028
1/41/10/0.028
1/21/2/0.015
1/21/2/0.013
nondia 15000
1/41/10/0.053
1/41/10/0.044
1/22/2/0.026
1/22/2/0.021
nondia 20000
1/42/9/0.063
1/42/9/0.061
1/22/2/0.029
1/22/2/0.029
nondquar 3000
2/63/11/0.208
140/4041/1715/17.728
472/896/660/6.186
662/956/1045/8.098
nondquar 15000
2/65/8/1.025
57/1419/507/29.773
196/630/301/16.855
822/1496/1395/55.029
penalty1 100
17/439/318/0.241
6/146/49/0.063
86/26/86/0.072
18/21/18/0.018
penalty1 1000
19/750/517/7.833
12/328/99/2.655
11/49/14/0.438
24/65/29/0.712
power1 10000
1/28/2/0.011
1/28/2/0.012
1/28/2/0.012
1/28/2/0.012
power1 15000
1/53/12/0.035
1/53/12/0.036
1/29/2/0.017
1/29/2/0.018
power1 20000
1/30/2/0.025
1/30/2/0.025
1/30/2/0.025
1/30/2/0.025
quartc 1000
1/54/17/0.038
1/54/17/0.037
1/22/2/0.013
1/22/2/0.013
quartc 6000
1/63/19/0.236
1/63/19/0.237
1/27/2/0.087
1/27/2/0.085
quartc 10000
1/29/2/0.152
1/29/2/0.152
1/29/2/0.152
1/29/2/0.151
srosenbr 5000
3/94/22/0.032
190/5870/2002/2.140
39/354/41/0.131
7/81/8/0.028
tridia 100
F/F/F/F
F/F/F/F
553/5057/553/0.372
348/3098/348/0.223
tridia 1000
F/F/F/F
F/F/F/F
1932/24283/1932/3.235
1443/17580/1443/2.335
bv 2000
16/358/161/20.822
434/13397/5234/752.704
4/11/4/0.636
707/2120/707/140.003
lin0 10000
1/90/16/86.643
1/90/16/86.659
1/65/2/58.180
1/65/2/58.186
lin1 3000
1/84/11/9.126
1/84/11/9.109
1/60/2/6.184
1/60/2/6.197
lin1 20000
1/93/18/122.849
1/93/18/122.946
1/68/2/82.817
1/68/2/82.707
pen1 1000
1/31/2/0.780
1/31/2/0.770
1/31/2/0.768
1/31/2/0.771
pen1 5000
1/38/2/17.416
1/38/2/17.415
1/38/2/17.425
1/38/2/17.415
vardim 1000
1/68/2/0.716
1/68/2/0.685
1/68/2/0.689
1/68/2/0.687
vardim 5000
1/84/2/19.569
1/84/2/20.066
1/84/2/19.628
1/84/2/19.720All codes were written in Matlab 7.5 and run on a HP with 1.87 GB RAM and Windows XP operating system. The parameters areσ=0.1, δ=0.01, u1=1, u2=2, and λ=0.3. Stop the iteration if criterion gk≤ϵ=10-6 is satisfied.In Table1, “Name” denotes the abbreviation of the test problems, “n” denotes the dimension of the test problems, “Itr/NF/NG” denote the number of iteration, function evaluations, and gradient evaluations, respectively, and “Tcpu” denotes the computing time of CPU for computing a test problem (units: second).On the other hand, to show the performance difference clearly between the hJHJ, hAN, hDY, and hHuS method, we adopt the performance profiles given by Dolan and Moré [28] to compare the performance according to Itr, NF, NG, and Tcpu, respectively. Benchmark results are generated by running a solver on a set P of problems and recording information of interest such as NF and Tcpu. Let S be the set of solvers in comparison. Assume that S consists of ns solvers and P consists of np problems. For each problem p∈P and solver s∈S, denote tp,s by the computing time (or the number of function evaluation, etc.) required to solve problem p∈P by solver s∈S, and the comparison between different solvers is based on the performance ratio defined by (44)rp,s=tp,smin⁡tp,s:s∈S.Assume that a large enough parameterrM≥rp,s for all p,s is chosen, and rp,s=rM if and only if solvers s do not solve problem p. Define (45)ρsτ=1npsizep∈P:log⁡rp,s≤τ,where size A means the number of elements in set A; then ρs(τ) is the probability for solver s∈S that a performance ratio rp,s is within a factor τ∈Rn. The ρs is the (cumulative) distribution function for the performance ratio. The value of ρs(1) is the probability that the solver will win over the rest of the solvers.Based on the theory of the performance profile above, four performance figures, that is, Figures1–4, can be generated according to Table 1. From the four figures, we can see that the NPRP is superior to the other three CGMs on the testing problems.Figure 1
Performance profiles on Tpu.Figure 2
Performance profile on NF.Figure 3
Performance profile on NG.Figure 4
Performance profile on Itr.


## 5. Conclusion

In this paper, we carefully studied the combination of the variations of the formulasβkFR and βkPRP. We have found that the new formula possesses the following features: (1) βkNPRP+ is a descent sequence without any line search; (2) the new method possesses the sufficient descent property and converge globally; (3) the strategy will restart the iteration automatically along the steepest descent direction if a negative value of βkNPRP occurs; (4) the initial numerical results are promising.



---

*Source: 352524-2015-10-26.xml*