# A New Modified Three-Term Hestenes–Stiefel Conjugate Gradient Method with Sufficient Descent Property and Its Global Convergence

Authors: Bakhtawar Baluch; Zabidin Salleh; Ahmad Alhawarat
Journal: Journal of Optimization
 (2018)

---

## Abstract

This paper describes a modified three-term Hestenes–Stiefel (HS) method. The original HS method is the earliest conjugate gradient method. Although the HS method achieves global convergence using an exact line search, this is not guaranteed in the case of an inexact line search. In addition, the HS method does not usually satisfy the descent property. Our modified three-term conjugate gradient method possesses a sufficient descent property regardless of the type of line search and guarantees global convergence using the inexact Wolfe–Powell line search. The numerical efficiency of the modified three-term HS method is checked using 75 standard test functions. It is known that three-term conjugate gradient methods are numerically more efficient than two-term conjugate gradient methods. Importantly, this paper quantifies how much better the three-term performance is compared with two-term methods. Thus, in the numerical results, we compare our new modification with an efficient two-term conjugate gradient method. We also compare our modification with a state-of-the-art three-term HS method. Finally, we conclude that our proposed modification is globally convergent and numerically efficient.


---

## Body

## 1. Introduction

In the field of optimization conjugate gradient methods are a well-known approach for solving large-scale unconstrained optimization problems. The conjugate gradient (CG) methods are simple and have relatively modest storage requirements. This class of methods has a vast number of applications in different areas, especially in the field of engineering [1–3].Consider the unconstrained optimization problem:(1)min⁡fx,x∈Rn,where f:Rn⟶R is continuously differentiable and its gradient is g(x). Normally CG methods generate a sequence (xk) defined by(2)xk+1=xk+αkdk,k=0,1,….In (2), αk>0 is a general line search and dk is a search direction given by (3)dk=-gkifk=0,-gk+βkdk-1ifk≥1,where βk is a parameter of the CG method. The six pioneering forms of βk are defined in [4–10].Line searches may be exact or inexact. Exact line searches are time consuming, computationally expensive, and difficult and require large amounts of storage [11–13]. Thus, inexact line search techniques are often adopted because of their efficiency and global convergence properties. Well-known inexact line search methods include the Wolfe and strong Wolfe techniques, which can be written as (4)fxk+αkdk≤fxk+ραkgkTdk,gxk+αkdkTdk≥σgkTdk,where 0<ρ<σ<1, and(5)fxk+αkdk≤fxk+ραkgkTdk,gxk+αkdkTdk≤σgkTdk.Recently, Alhawarat and Salleh [14], Salleh and Alhawarat [15], and Alhawarat et al. [16, 17] proposed efficient CG and hybrid CG methods that fulfill the required global convergence properties. To improve the existing methods, a three-term CG technique has been introduced. Several different researchers have suggested various modifications to the three-term CG method. For instance, Beale [18] and Nazareth [19] proposed CG methods based on three terms that possess the finite termination property, but these do not perform well in practice [20, 21]. Furthermore, reports by McGuire and Wolfe [22], Deng and Li [23], Zhang et al. [24, 25], Cheng [26], Al-Bayati and Sharif [27], Zhang Xiao and Wei [28], Andrei [29–31], Sugiki et al. [32], Narushima et al. [33], Babaie-Kafaki and Ghanbari [34], Al-Baali et al. [35], Sun and Liu [36], and Baluch et al. [37] discuss the global convergence and numerical results of modified three-term CG methods.In this paper, a modified three-term Hestenes–Stiefel (HS) method is proposed. The general formula of the HS method [4] is (6)βkHS=gkTyk-1dk-1Tyk-1.This is known to be the first of all the CG parameters. This method ensures the global convergence of the exact line search. A nice property of the HS method is that it satisfies the conjugacy condition, regardless of whether the line search is exact or inexact [38]. However, this method does not satisfy the global convergence property when used with an inexact line search.In this paper, the method of Zhang et al. [25] is modified with the help of another efficient CG parameter proposed by Wei et al. [39]. An attractive feature of the new three-term HS method is that it satisfies the sufficient descent condition regardless of the line search used. Furthermore, our modification is globally convergent for both convex and nonconvex functions when using an inexact line search. Numerical experiments show that the new modification is more efficient and robust than the MTTHS algorithm proposed by Zhang et al. [25]. The second aspect of this paper is to quantify the improvement of the three-term CG method over two-term approaches. To do this, we consider the efficient two-term CG method [40] given by(7)βkDHS=gk2-gk/gk-1gkTgk-1μgkTdk-1+dk-1Tyk-1.This DHS [40] method is one of the more efficient CG techniques, as it possesses the sufficient descent property and offers global convergence under Wolfe–Powell line search conditions. The numerical results given by this method are also convincing. Therefore, this two-term CG method is compared with our new modification to quantify the improvement offered by three-term CG methods.The remainder of this paper is organized as follows. In Section2, the motivation for and construction of the three-term HS CG method is discussed, and the general form is presented in Algorithm A. Section 3 is divided into two subsections, with Section 3.1 covering the sufficient descent condition and the global convergence properties for convex and nonconvex functions and Section 3.2 presenting detailed numerical results to evaluate the proposed method. Finally, Section 4 concludes this paper.


## 2. Motivation and Formulas

Zhang et al. [25] proposed the first three-term HS (TTHS) method. This can be written as (8)dk=-gk,ifk=0,-gk+βkHSdk-1-θkHSyk-1,ifk>0,βkHS=gkTyk-1/dk-1Tyk-1 and θkHS=gkTdk-1/dk-1Tyk-1.TTHS satisfies the descent property; if an exact line search is used, then it reduces to the original HS method. Further, to guarantee the global convergence properties of the search direction given by (8), a modified (MTTHS) algorithm was introduced with the search direction: (9)dk=-gk,ifk=0,-gk+βkMHSdk-1-θkMzk-1,ifk>0,where βkMHS=gkTzk-1/dk-1Tzk-1,θkM=gkTdk-1/dk-1Tzk-1 and zk=yk+tg(xk)rsk.As MTTHS was introduced to prove the global convergence properties of the search direction in (8), the question arises as to why (8) is not used to prove the global convergence properties. Instead of ignoring (8), it should be made efficient and globally convergent. Thus, there is room to modify (8) so as to satisfy the global convergence properties. It is expected that such a modification would outperform the MTTHS algorithm numerically.Wei et al. [39] proposed an efficient CG parameter given by(10)βkVFR=μ1gk2μ2gkTdk-1+μ3gk-12,forμ1ϵ0,+∞,μ2ϵμ1+ε1,+∞,μ3ϵ0,+∞.In this parameter, the term μ2gkTdk-1 plays an important role in satisfying the sufficient descent and global convergence properties. Thus, we take μ2gkTdk-1 from the denominator of the above parameter and use it with (8) to construct a new modified three-term HS method. Hence,(11)βkBZA=gkTgk-gk-1dk-1Tyk-1+μgkTdk-1.It is known that the HS method does not converge globally when the objective function is nonconvex. Further, Gilbert and Nocedal [41] showed that the parameter βkHS must be nonnegative to achieve convergence for nonconvex or nonlinear functions, i.e.,(12)βkHS+=maxβkHS,0.Applying the same technique to our parameter βkBZA gives(13)βkBZA+=maxgkTgk-gk-1dk-1Tyk-1+μgkTdk-1,0,(14)θkBZA=gkTdk-1dk-1Tyk-1+μgkTdk-1,where μ>1. If the line search is exact, then the parameters βkBZA, βkBZA+, and θkBZA reduce to the original parameters βkHS [4], βkHS+ [41], and TTHS [25]. The procedure of our proposed three-step CG method is described in Algorithm A.Algorithm A.Step 0. Choose an initial point x0ϵRn,μ>1,0<ρ<σ<1, and set d0=-g0, k≔0.Step 1. For convergence, if gk≤ε (=10-6), then the algorithm terminates; otherwise, go to step 2.Step 2. Compute(15)dk=-gkifk=0,-gk+βkBZAdk-1-θkBZAyk-1ifk≥1.y k - 1 = g k - g k - 1, βkBZA and θkBZA are given in (11) and (14).Step 3. Determine the step size αk>0 by the Wolfe line search (4).Step 4. Compute the new point xk+1.Step 5. Set k=k+1 and go to step 1.


## 3. Results and Discussion

This section contains a theoretical discussion and numerical results. The first subsection considers the global convergence properties of our proposed method and the second presents the results from numerical computations.


### 3.1. Global Convergence Properties

Assumptions(A1) The level setR0=x|f(x)≤f(x0) is bounded.(A2) In some neighborhoodNof R0, the gradient g(x) is Lipschitz continuous on an open convex set E that contains R0, i.e., there exists a positive constant L>0 such that(16)gxk-gxk-1≤Lxk-xk-1for  anyxk,xk-1∈E.Assumptions (A1) and (A2) imply that there exist positive constants γ and b such that(17)gxk≤γ∀xk∈R0,(18)xk-xk-1≤b∀xk,xk-1∈R0.We now prove the sufficient descent condition independent of the line search gkTdk=-gk2 and also gk≤dk. From (15), (11), and (14), we can write(19)dk=-gk+βkBZAdk-1-θkBZAyk-1gkTdk=-gk2+gkTgk-gk-1gkTdk-1dk-1Tyk-1+μgkTdk-1-gkTdk-1gkTgk-gk-1dk-1Tyk-1+μgkTdk-1,that is,(20)gkTdk=-gk2.Hence, the sufficient descent condition holds regardless of the line search. Now, we prove that(21)gk≤dk.As we have gkTdk=-gk2, taking the modulus on both sides gives(22)gkTdk=-gk2=gk2.By the Schwartz inequality, we have(23)gkTdk≤gkdkso(24)gk2≤gkdkor(25)gk≤dk.Hence, we have(26)gkTdk=-gk2,gk≤dk.The HS method is well known for its conjugacy conditions, such as(27)dkTyk-1=0.By [15], CG methods that inherit (27) will be more efficient than other CG parameters that do not inherit this property. Dai and Liao [42] proposed the following conjugacy condition for an inexact line search: (28)dkTyk-1=-tαk-1gkTdk-1,wheret>0.Using the exact line search gkTdk-1=0, (28) reduces to the conjugacy condition in (27).Lemma 1 (see [43]).
Suppose there is an initial pointx0 for which Assumptions (A1) and (A2) hold. Now, consider the method in the form of (2), in which dk is a descent direction and αk satisfies the Wolfe line search condition (4). Then (29)∑k=0∞gkTdk2dk2<+∞.This is known as Zoutendijk’s condition and is used for proving the global convergence of a CG method. This condition together with (26) shows that(30)∑k=0∞gk4dk2<+∞.Definition 2.
The functionf is called uniformly convex [36] on Rn if there exists a positive constant m such that (31)mdk2≤dT∇2fxkd∀x,d∈Rn.We now show the global convergence of Algorithm A for uniformly convex functions.Lemma 3.
Let the sequences(xk) and (dk) be generated by Algorithm A and suppose that (31) holds. Then,(32)z1αkdk2≤-gkTdk,where z1=(1-ρ)-1m/2.Proof.
For details, see Lemma 2.1 of [44].Theorem 4.
Let the conditions in Assumptions (A1) and (A2) hold and the functionf(x) be uniformly convex. Then, (33)limk→∞⁡gk=0.Proof.
As(34)βkBZA=gkTgk-gk-1dk-1Tyk-1+μgkTdk-1,dk-1,yk-1=dk-1,gk-gk-1=dk-1,gk-dk-1,gk-1.Then, using the second Wolfe condition (4) and the sufficient descent condition,(35)gxk+αkdk,dk≥σ1gk,dk,gk,dk=-gk2,we have(36)dk-1,yk-1=dk-1,gk-dk-1,gk-1≥σ1gk-1,dk-1-gk-1,dk-1=-1-σ1gk-1,dk-1=1-σ1gk-12.From (11), (32), and (36) and Assumption (A2),(37)βkBZA≤gkTgk-gk-1dk-1Tyk-1≤gkLxk-xk-11-σ1gk-12=gkLsk-11-σ1-gk-1Tdk-1≤Lgkαk-1dk-11-σ1z1αk-1dk-12=Lgk1-σ1z1dk-1.Let us suppose that 1-σ1z1=z2, where 0<σ1<1 and z1>0 so that z2>0. Thus, (38)βkBZA≤Lgkz2dk-1⟹βkBZAdk-1≤Lgkz2.Now,(39)θkBZA≤gkTdk-1dk-1Tyk-1≤gkdk-11-σ1z1αk-1dk-12θkBZAyk-1≤gkdk-1yk-11-σ1z1αk-1dk-12≤gkdk-1Lsk-1z2αk-1dk-12=gkdk-1Lαk-1dk-1z2αk-1dk-12=Lgkz2.Combining (38) and (39) with (15), we obtain(40)dk≤gk+βkBZAdk-1+θkBZAyk-1≤gk+Lgkz2+Lgkz2=gk+2Lgkz2≤1+2Lz2gk.Now, let C=1+2L/z2 so that(41)dk≤Cgk,and we get dk2≤Cgk2. This implies that(42)1Cgk2≤1dk2gk4gk2≤Cgk4dk2.Hence, by (30), we have(43)limk→∞⁡gk2≤Climk→∞gk4dk2=0.We are now going to prove the global convergence of Algorithm A for nonconvex functions.Lemma 5.
Suppose that Assumptions (A1) and (A2) hold. Let the sequencexk be generated by Algorithm A. If there exists a constant ϵ>0 such that gk≥ϵ for every k≥0, then (44)∑k=0∞uk+1-uk2<+∞,where uk=dk/dk.Proof.
Asgk≤dk and gkTdk=-gk2, and also gk≥ϵ for all k, then dk>0 for all k. Hence, uk is well defined. If(45)rk=-1+θkBZAgkTyk-1/gk2gkdk,δk=βkBZA+dk-1dk,then uk=rk+δkuk-1, where uk and uk-1 are unit vectors. Therefore,(46)rk=δkuk-uk-1=uk-δkuk-1.As δk≥0,(47)uk-uk-1≤1+δkuk-uk-1≤uk-δkuk-1+δkuk-uk-1=2rk.Now, from Assumption (A2), (14), and (18),(48)θkBZAgkTyk-1gk2≤gkTdk-1μgkTdk-1gkTyk-1gk2≤Lxk-xk-1μgk≤Lbμϵ.From (17), (18), and (48), there exists a constant N1≥0 such that(49)-1+θkBZAgkTyk-1gk2gk≤gk+θkBZAgkTyk-1gk2gk≤γ+Lbϵμγ=N1.From (30) and (49), we obtain(50)∑k=0∞rk2≤∑k=0∞N12dk2≤∑k=0∞N12gk4gk4dk2≤N12ϵ4∑k=0∞gk4dk2<+∞.Combining this with (44) completes the proof.Theorem 6.
Let Assumptions (A1) and (A2) hold. Then, the sequence (xk) generated by Algorithm A satisfies(51)limk→∞⁡infgk=0.Proof.
Suppose thatlimk→∞⁡infgk≠0. Then, there exists a constant ϵ>0 such that gk≥ϵ∀k≥0.
The proof has two parts.
Part 1. See Theorem 2.2, step 1 in [36].
Part 2. From (15) and (49), we have (52)dk2≤βkBZA+dk-1+-1+θkBZAgkTyk-1gk2gk2≤βkBZA+dk-1+N12≤2βkBZA+dk-12+2N12≤2gkTgk-gk-1ε2dk-12+2N12≤2gkLsk-1ε2dk-12+2N12≤2γ2L2sk-12ε2dk-12+2N12.In the beginning of the proof, we suppose that limk→∞⁡infgk≠0. Then, there exist a positive constant ϵ and some γ>0 such that gk>γ>0. Thus, (53)∑k=0∞gkTdk2dk2>+∞⟹1dk2>+∞,which contradicts Assumption (A2), (30), and (52). Therefore,(54)limk→∞⁡infgk=0.


### 3.2. Numerical Discussion

We now report the results of several numerical experiments. Zhang et al. [25] demonstrated the superior numerical efficiency of the MTTHS algorithm with respect to PRP+ [41], CG_DESCENT [45], and L-BFGS [46] using the Wolfe line search, while Dai and Wen [40] reported the numerical efficiency of the DHS method. Thus, we compare the efficient three-term HS method proposed in this paper (named the Bakhtawar–Zabidin–Ahmad method, BZA) with MTTHS [25] and DHS [40]. The BZA method was implemented using the Wolfe–Powell line search (4) with ρ=0.1, σ=0.5, and μ=2.All codes were written in MATLAB 7.1 and run on an Intel Core i5 system with 8.0 GB RAM and a 2.60 GHz processor. Table1 lists the numerical results given by BZA, MTTHS, and DHS for a number of test functions. In the Table 1, NI/CT/GE/FE represents number of iterations, CPU time, number of gradient evaluations and number of function evaluations.Table 1
List of test problem functions.
Problem n MTTHS DHS BZA NI/CT/GE/FE NI/CT/GE/FE NI/CT/GE/FE Extended 2 1323/9.3448/4645/3321 1267/10.1753/4756/3488 364/3.1079/1365/1000 Trigonometric -1 50 4533/28.4686/15849/11315 3771/25.5829/14146/10374 2376/18.4341/8910/6533 function 500 11125/67.51/38848/27722 8163/55.0526/30616/22452 5904/46.5577/22140/16235  HIMMELBH(Cute) 2 9/0.4680/77/67 9/0.4538/77/67 9/0.4471/77/67 50 9/0.4572/77/67 9/0.4574/77/67 9/0.4620/77/67 5000 9/2.0529/77/67 9/2.0198/77/67 9/1.9930/77/67  Power function 2 3/0.3968/13/9 2/0.3881/9/6 2/0.3884/9/6 50 212/2.0540/849/636 3431/24.0407/13725/10293 65/0.7751/261/195 1000 4612/33.5261/18449/13836 F/F/F/F 1565/11.567/6261/4695  DENSCHNF 2 11/0.6773/64/52 12/0.5399/67/54 8/0.4719/50/41 50 14/0.5959/78/63 14/0.5260/75/60 9/0.4739/54/44 5000 10/1.7879/56/45 14/2.1633/75/60 9/1.6783/54/44  Sum Squares 2 3/0.4203/13/9 2/0.3861/9/6 2/0.3966/9/6 function 50 47/0.7252/189/141 39/0.6318/157/117 39/0.6162/157/117 1000 229/2.4542/917/687 1333/11.3244/5333/3999 191/1.9552/765/573  TRIDIA(Cute) 2 3/0.4056/13/9 2/0.3980/9/6 2/0.4024/9/6 50 100/1.6029/401/300 193/1.7752/773/579 56/0.7390/225/168 1000 604/5.2318/2417/1812 16019/122.48/64077/48057 349/3.22771397/1047  SINQUAD(Cute) 2 25/0.4804/102/76 1734/12.6402/6076/4341 25/0.5218/101/75 5000 F/F/F/F F/F/F/F 411/198.6198/2837/2425 10000 F/F/F/F F/F/F/F 417/493.6830/2650/2232  Generalized 50 23/0.5659/101/77 25/0.5348/109/83 21/0.5187/94/72 Quartic GQ2 100 23/0.5588/103/79 31/0.5938/133/101 22/0.5233/96/73 function. 5000 26/2.9409/116/89 23/2.6517/103/79 25/2.7548/110/84  Generalized 50 50/0.7767/248/197 43/0.6750/192/148 42/0.6934/198/155 Triagonal-2 500 43/1.5284/206/162 46/1.4306/209/162 38/1.4029/182/143 function 1000 45/2.1144/214/168 47/2.1176/214/166 39/1.8380/181/141  Extended 2 8/0.4315/32/23 9/0.4256/37/27 6/0.4158/25/18 Trigonometric -2 50 33/0.6514/148/114 26/0.5848/124/97 22/0.5586/106/83 function 7000 85/63.5473/626/540 71/44.8822/440/368 33/25.6757/251/217  LIARWHD 100 20/0.5798/136/115 16/0.5065/95/78 14/0.4865/84/69 5000 50/8.8611/390/339 53/8.7426/384/330 24/4.4628/189/164 10000 33/14.6362/245/211 53/19.3591/331/277 23/9.7171/165/141  Generalized 2 6/0.4058/27/20 6/0.4127/27/20 5/0.4008/23/17 Quartic GQ1 6000 11/1.8086/47/35 10/1.6695/43/32 10/1.7246/43/32 function 10000 11/3.4464/47/35 10/3.0683/43/32 10/3.0317/43/32  Extended QP2 2 17/0.8111/98/80 21/0.6076/125/103 16/0.5702/111/94 Quadratic Penalty 5000 226/56.4248/2247/2020 F/F/F/F 82/25.7327/1018/935 function 10000 137/95.8189/1457/1319 F/F/F/F 82/67.1490/1024/941  Extended Maratos 2 20/0.6479/131/110 43/0.8956/225/181 30/0.8305/193/162 function 1000 26/0.8290/176/149 F/F/F/F 30/0.8300/193/162 5000 F/F/F/F 45/5.8526/233/187 32/6.0318/243/210  DENSCHNC 2 6/0.4508/36/29 10/0.4624/51/40 6/0.4486/34/27 50 7/0.4499/38/30 10/0.4590/51/40 6/0.4696/34/27 600 8/0.5625/44/35 15/0.6240/130/114 7/0.5445/38/30  DIXON3DQ (Cute) 2 3/0.4835/13/9 2/0.3904/9/6 2/0.3878/9/6 20 106/1.2286/424/317 262/2.4917/1061/798 90/1.0709/360/269 600 2266/18.9637/9064/6797 F/F/F/F 2185/18.4756/8740/6554  EDENSCH function 50 3094/15.3448/9288/6193 3094/16.4610/9288/6193 3089/15.3239/9273/6183 1000 3094/17.6514/9288/6193 3094/18.4918/9288/6193 3089/17.6263/9273/6183 5000 3094/198.8550/9288/6193 3094/199.0048/9288/6193 3089/198.2240/9273/6183  Diagonal 2 function 50 749/6.8385/2626/1876 495/3.0663/1488/992 490/3.3271/1473/982 1000 16517/126.4914/59593/43075 8569/53.8256/25711/17141 8563/53.3166/25693/17129 10000 F/F/F/F 16484/283.6569/49456/32971 16478/279.44/49438/32959  DQDRTIC(Cute) 50 12/0.4358/49/36 5/0.4070/21/15 5/0.3940/21/15 5000 14/1.6324/57/42 5/0.7966/21/15 5/0.8084/21/15 10000 14/3.7862/57/42 5/1.6205/21/15 5/1.5979/21/15  Perturbed 50 43/0.6470/173/129 38/0.5837/153/114 38/0.6313/153/114 Quadratic function 1000 207/2.1710/829/621 1397/10.8367/5589/4196 187/1.9258/749/561 5000 481/44.4081/1925/1443 5125/435.0973/20501/15375 425/39.4768/1701/1275  Diagonal 4 function 50 4/0.3919/17/12 2/0.4015/9/6 2/0.3963/9/6 1000 5/0.4493/21/15 2/0.4005/9/6 2/0.4039/9/6 5000 5/0.8522/21/15 2/0.5598/9/6 2/0.5698/9/6  Extended Beale 50 15/0.4685/74/58 68/0.8247/281/212 15/0.4890/72/56 function 100 16/0.4739/74/57 68/0.8245/281/212 15/0.4855/72/56 500 16/0.5450/74/57 68/0.8840/281/212 15/0.5050/72/56  DENSCHNA 50 9/0.4336/44/34 24/0.5609/102/77 9/0.4462/44/34 1000 10/0.5912/48/37 26/0.7584/110/83 9/0.5909/44/34 5000 10/1.6387/46/35 26/3.0388/110/83 9/1.4694/44/34  STAIRCASE S1 20 79/0.9390/316/236 202/1.7976/818/615 72/0.8546/290/217 50 215/2.0539/860/644 1117/8.6778/4503/3385 183/1.6893/732/548 100 426/3.4107/1705/1278 3896/29.4293/15737/11840 372/3.0840/1490/1117  NONDQUAR 50 28674/216.605/114767/86092 F/F/F/F 14756/104.86/59098/44341 100 32283/244.026/129157/96873 F/F/F/F 17900/127.16/71670/53769 500 F/F/F/F F/F/F/F 32748/241.1/131043/98294  Extended Wood 500 128/1.5299/605/476 942/8.5789/4143/3200 96/1.4535/551/454 1000 146/1.7443/676/529 946/8.8946/4100/3153 101/1.7151/606/504 10000 213/57.8431/979/765 956/249.5361/4202/3245 89/31.8805/545/455  Extended Penalty 20 33/0.6528/144/110 37/0.7031/158/120 22/0.5670/98/75 300 F/F/F/F F/F/F/F 64/1.2248/365/300 600 F/F/F/F F/F/F/F 28/0.7428/172/143  Sphere function 2 1/0.4750/5/3 1/0.3777/5/3 1/0.3902/5/3 1000 1/0.3904/5/3 1/0.3877/5/3 1/0.3860/5/3 5000 1/0.4687/5/3 1/0.4576/5/3 1/0.4616/5/3  ARGLINB(Cute) 2 1/0.3913/5/3 1/0.3903/5/3 1/0.3840/5/3 50 1/0.3868/5/3 1/0.3941/5/3 1/0.3832/5/3 500 2/0.4279/9/6 2/0.4266/9/6 2/0.4246/9/6  Extended White 2 28/0.7668/192/163 69/1.2885/354/284 21/0.6586/136/114 and Holst function 500 29/0.9337/213/183 102/1.5134/488/385 21/0.6586/136/114 5000 23/4.6845/168/144 125/14.3950/577/451 21/3.8322/136/114  Extended Hiebert 50 2040/33.6457/16304/14263 F/F/F/F 838/21.7040/9977/9138 200 F/F/F/F F/F/F/F 901/23.007/10513/9611 1000 F/F/F/F F/F/F/F F/F/F/F  Quadratic QF1 50 44/0.6479/177/132 38/0.6068/153/114 38/0.6306/153/114 500 147/1.4565/589/441 574/4.7399/2297/1722 131/1.3814/525/393 10000 744/179.6695/2977/2232 F/F/F/F 606/146.3228/2425/1818  Quartic 50 11579/66.6569/34740/23160 11579/66.7991/34740/23160 11574/64.593/34725/23150 500 24975/148.8391/74928/49952 24975/146.0726/74928/49952 24968/142.57/74907/49938 1000 31473/201.6973/94422/62948 31473/218.8475/94422/62948 31466/191.54/94401/62934  Shallow function 1000 10/0.5712/45/34 48/0.7436/200/151 10/0.5557/45/34 5000 11/1.4925/49/37 48/4.9218/200/151 10/1.4117/45/34 10000 12/3.6303/53/40 50/13.2094/209/158 10/3.1569/45/34  VARDIM 50 28/1.1175/322/293 143/4.0110/1604/1460 16/0.8685/221/204 100 20/1.0429/286/265 293/5.9711/2604/2310 17/0.9508/250/232 500 41/2.2545/736/694 1557/25.9389/11724/10166 34/1.8745/645/610  DIXMAANA 6000 8/1.8623/35/26 8/1.8913/35/26 8/1.8504/35/26 6015 8/1.9276/35/26 8/1.8546/35/26 8/1.9200/35/26 6030 8/1.9301/35/26 8/1.9700/35/26 8/1.8819/35/26  DIXMAANB 9 7/0.4044/30/22 7/0.4141/30/22 7/0.4036/30/22 300 7/0.4550/30/22 7/0.4776/30/22 8/0.4415/34/25 6000 8/1.8966/34/25 8/1.8364/34/25 9/2.0362/38/28  DIXMAANC 9 6/0.4033/29/22 6/0.4191/29/22 6/0.4168/29/22 300 7/0.4701/33/25 6/0.4721/29/22 7/0.4707/33/25 6000 7/2.0093/33/25 7/2.0148/33/25 8/2.1736/37/28  DIXMAAND 90 7/0.4450/34/26 8/0.4333/38/29 8/0.4263/38/29 300 8/0.5272/38/29 8/0.5406/38/29 8/0.5418/38/29 6000 9/2.4166/42/32 7/2.0165/34/26 7/2.0556/34/26  DIXMAANE 9 19/0.5080/88/68 23/0.5720/107/83 18/0.4832/84/65 300 84/1.5278/421/336 1211/7.7407/3707/2495 84/2.1712/420/335 6000 331/81.2267/1655/1323 F/F/F/F 333/83.0952/1685/1351  EG2 2 5/0.4912/25/19 8/0.4128/40/31 4/0.4139/20/15 20 160/1.4413/642/481 1958/14.8104/8106/6147 110/1.0755/447/336 50 F/F/F/F 48/0.7452/228/179 656/5.3312/2773/2116  EG3 20 21/0.5445/88/66 25/0.5611/102/76 14/0.4851/60/45 50 25/0.5965/110/84 43/0.7618/207/163 25/0.5236/69/53 100 F/F/F/F F/F/F/F 20/0.5290/88/67  Fletcher function 50 24/0.5879/126/101 23/0.5870/123/99 22/0.5687/118/95 6000 27/5.2874/161/133 28/5.4497/168/139 26/4.7950/152/125 10000 27/10.4312/161/133 27/10.6308/163/135 26/9.8879/155/128  Extended 50 8/0.4229/37/28 11/0.4510/49/37 9/0.4370/41/31 Himmelblau 1000 8/0.4706/39/30 12/0. 5342/53/40 9/0.4775/41/31 function 5000 9/1.4066/43/33 13/1.6584/57/43 9/1.3377/41/31  Extended 2 11/0.5889/75/63 33/0.6806/163/129 10/0.4929/69/58 Freudenstein 50 F/F/F/F 36/0.7871/230/193 10/0.4700/69/58 and Roth function 200 16/0.5442/102/85 37/0.8501/241/203 11/0.4993/73/61  Dixon and Price 20 132/1.6580/615/482 333/3.2018/1409/1075 131/1.5682/603/471 function 50 185/2.5157/1034/848 478/4.7648/2199/1720 165/2.2048/900/734 100 523/6.5773/2938/2414 1243/11.1703/5672/4428 439/5.4568/2422/1982  Raydan 1 function 2 106/1.3363/319/212 105/0.8502/316/210 99/0.8493/298/198 50 59/0.8854/237/177 88/1.0277/364/275 58/0.7714/233/174 100 70/0.9532/282/211 155/1.5252/625/469 70/0.8892/282/211  Raydan 2 function 2 2/0.4129/9/6 2/0.3995/9/6 3/0.3971/13/9 50 2/0.3991/9/6 2/0.3981/9/6 3/0.4176/13/9 100 2/0.4002/9/6 2/0.4123/9/6 3/0.3906/13/9  NONDIA(SHANO- 500 9/0.5483/63/53 11/0.4937/70/58 7/0.4938/55/47 78) 6000 14/2.7799/82/67 46/6.5297/212/165 9/2.3946/70/60 10000 16/6.3412/96/79 74/21.4446/339/264 15/6.2113/92/76  Extended Block 500 30/1.0226/52000/44250 32/0.9386/32250/24000 39/1.1887/44000/34000 Diagonal BD1 1000 39/3.6068/195000/175000 33/1.3795/66500/49500 39/1.6724/88500/68500 function 10000 38/22.3738/1070000/875000 35/14.5725/705000/525000 43/20.1088/965000/745000  SINCOS 2000 F/F/F/F F/F/F/F 8/0.6960/39/30 5000 F/F/F/F F/F/F/F 8/1.2553/39/30 10000 F/F/F/F F/F/F/F 8/2.7535/39/30  DIXMAANH 90 58/0.8867/290/231 388/2.5254/1230/841 57/1.0443/286/228 300 81/1.5051/408/326 1264/7.8924/3872/2607 81/1.3140/408/326 600 126/4.4107/630/503 2407/40.8602/7294/4886 119/4.0122/596/476  Quadratic QF2 50 77/0.9476/330/252 107/1.1580/454/346 68/0.8775/293/224 function 200 183/1.7984/787/603 337/2.9913/1419/1081 139/1.5/610/470 2000 1150/34.4704/4862/3711 2903/85.3362/12110/9206 540/17.4638/2404/1863  Tridiagonal double 20 108/1.1547/438/329 1915/14.1311/7667/5751 101/1.1136/410/308 Bordered 50 407/3.3266/1633/1225 11157/78.2325/44633/33475 355/2.9421/1425/1069 500 6278/48.1130/25119/18840 13470/103.5476/53887/40416 4595/35.3993/18387/13791  Generalized 2 1323/8.3265/4645/3321 1267/8.4042/4756/3488 364/2.6867/1365/1000 Triagonal1 function 50 25/0.5255/103/77 28/0.504/115/86 24/0.5140/99/74 100 24/0.5630/99/74 27/0.6205/111/83 23/0.5242/95/71  Extended QP2 50 9/0.4269/49/39 15/0.4503/71/55 9/0.4190/49/39 Quadratic penalty 200 13/0.4682/70/56 14/0.6931/74/59 12/0.4620/66/53 function 3000 F/F/F/F F/F/F/F 17/1.5340/118/100  Extended 2 5/0.4089/22/16 6/0.4254/26/19 5/0.4095/22/16 DENSCHNB 500 5/0.4222/22/16 7/0.4313/30/22 6/0.4165/26/19 function 10000 5/1.7240/22/16 7/2.1577/30/22 6/1.9461/26/19  Extended three- 2 7/0.4187/30/22 13/0.4386/54/40 7/0.417/30/22 Exponential terms 50 7/0.4211/750/550 14/0.4492/1450/1075 7/0.4255/750/550 100 7/0.4378/1500/1100 14/0.4705/2900/2150 7/0.4183/1500/1100  DIXMAANF 9 23/0.6308/109/85 23/0.5828/109/85 19/0.5129/90/70 90 51/0.8509/256/204 386/2.4637/1229/842 51/1.1421/256/204 300 90/1.4444/451/360 1260/7.8258/3871/2610 90/1.5578/451/360  DIXMAANG 9 19/0.5318/95/75 26/0.5670/127/100 21/0.5403/103/81 90 83/1.2240/424/340 379/2.4949/1221/841 56/0.8767/280/223 300 137/1.8866/643/505 1241/14.5812/3834/2592 569/5.5495/2477/1907  Extended 2 25/0.7100/159/133 24/0.9013/120/95 27/0.7803/163/135 Rosenbrock 1000 14/0.8076/82/67 26/0.6537/128/101 28/0.7818/167/138 function 5000 19/2.8693/109/89 27/3.2102/132/104 30/4.4233/175/144  ARWHEAD 500 F/F/F/F F/F/F/F 10/0.4429/54/43 3000 F/F/F/F F/F/F/F 5/0.7593/38/32 8000 F/F/F/F F/F/F/F 7/2.5096/49/41  Hager function 2 4/0.4001/17/12 6/0.4188/25/18 4/0.4008/17/12 50 20/0.4789/82/61 24/0.5101/98/73 20/0.4738/82/61 100 24/0.5275/98/73 F/F/F/F 24/0.5382/111/86  Extended Powell 1000 4008/108.2/4032500/3030250 F/F/F/F 361/10.5/384000/293500 function 3000 1026/86.1/3124500/2354250 F/F/F/F 108/10.8/379500/297750 5000 2213/330/11330000/8562500 F/F/F/F 306/48/1652500/1268750  BIGGSB1 function 2 1/0.3861/5/3 1/0.3866/5/3 1/0.3895/5/3 20 53/0.7214/213/159 20/0.4869/80/59 20/0.4764/80/59 50 201/1.9444/804/602 867/7.1960/3500/2632 50/0.7281/200/149  Extended Cliff 100 11657/87/2075150/1492250 39907/329/7892000/5896600 1674/12/293750/210000 5000 F/F/F/F F/F/F/F 1009/132/8857500/633250  ENGVAL8 2 7/0.4675/33/25 10/0.4709/45/34 7/0.4756/36/28 20 22/0.5657/99/76 32/0.6306/138/105 20/0.5382/90/69  Trecanni function 2 6/0.4146/26/19 6/0.4212/26/19 4/0.3982/18/13  GENROSEN-2 2 25/0.8096/159/133 24/0.5864/120/95 27/0.6770/163/135  Generalized Quartic function 2 6/0.4068/27/20 6/0.4082/27/20 5/0.4081/23/17  Diagonal 1 function 2 6/0.4015/25/18 7/0.4085/29/21 4/0.4207/18/13  Six Hump function 2 7/0.4112/31/23 7/0.4271/31/23 6/0.4064/27/20  Three Hump function 2 11/0.4441/52/40 11/0.4335/50/38 10/0.4397/47/36  Booth function 2 3/0.3930/13/9 2/0.4043/9/6 2/0.3919/9/6  Zett1 function 2 26/0.5067/105/78 30/0.5581/126/95 24/0.5046/102/77According to Moré et al. [47], the efficiency of any method can be determined by its performance on a number of test functions. The number of test functions should not be too large or too small, with 75 considered ideal for testing the efficiency of any method. The test functions in Table 1 were taken from Andrei’s test function collection [48] with standard initial points and dimensions ranging from 2 to 10000.If the solution had not converged after 500 seconds, the program was terminated. Generally, convergence was achieved within this time limit; functions for which the time limit was exceeded are denoted by “F” for Fail in Table1.The Sigma plotting software was used to graph the data. We adopt the performance profiles given by Dolan and Moré [49]. Thus, MTTHS, DHS, and BZA are compared in terms of NI/CT/GE/FE in Figures 1–4. For each method, we plotted the fraction P of problems that were solved correctly within a factor t of the best time. In the figures, the uppermost curve is the method that solves the most problems within a factor t of the best time. From Table 1 and Figures 1–4, the BZA method outperforms the MTTHS algorithm and DHS method in terms of NI, CT, GE, and FE.Figure 1
Performance profiles based on number of iterations.Figure 2
Performance profiles based on CPU time.Figure 3
Performance profiles based on gradient evaluation.Figure 4
Performance profiles based on function evaluation.The BZA method solves around 99.5% of the problems, and the performance of BZA is 85% better than that of DHS and 77% better than that of MTTHS. We can also conclude that, on average, three-term conjugate gradient methods are 85% better than two-term conjugate gradient methods (DHS).


## 3.1. Global Convergence Properties

Assumptions(A1) The level setR0=x|f(x)≤f(x0) is bounded.(A2) In some neighborhoodNof R0, the gradient g(x) is Lipschitz continuous on an open convex set E that contains R0, i.e., there exists a positive constant L>0 such that(16)gxk-gxk-1≤Lxk-xk-1for  anyxk,xk-1∈E.Assumptions (A1) and (A2) imply that there exist positive constants γ and b such that(17)gxk≤γ∀xk∈R0,(18)xk-xk-1≤b∀xk,xk-1∈R0.We now prove the sufficient descent condition independent of the line search gkTdk=-gk2 and also gk≤dk. From (15), (11), and (14), we can write(19)dk=-gk+βkBZAdk-1-θkBZAyk-1gkTdk=-gk2+gkTgk-gk-1gkTdk-1dk-1Tyk-1+μgkTdk-1-gkTdk-1gkTgk-gk-1dk-1Tyk-1+μgkTdk-1,that is,(20)gkTdk=-gk2.Hence, the sufficient descent condition holds regardless of the line search. Now, we prove that(21)gk≤dk.As we have gkTdk=-gk2, taking the modulus on both sides gives(22)gkTdk=-gk2=gk2.By the Schwartz inequality, we have(23)gkTdk≤gkdkso(24)gk2≤gkdkor(25)gk≤dk.Hence, we have(26)gkTdk=-gk2,gk≤dk.The HS method is well known for its conjugacy conditions, such as(27)dkTyk-1=0.By [15], CG methods that inherit (27) will be more efficient than other CG parameters that do not inherit this property. Dai and Liao [42] proposed the following conjugacy condition for an inexact line search: (28)dkTyk-1=-tαk-1gkTdk-1,wheret>0.Using the exact line search gkTdk-1=0, (28) reduces to the conjugacy condition in (27).Lemma 1 (see [43]).
Suppose there is an initial pointx0 for which Assumptions (A1) and (A2) hold. Now, consider the method in the form of (2), in which dk is a descent direction and αk satisfies the Wolfe line search condition (4). Then (29)∑k=0∞gkTdk2dk2<+∞.This is known as Zoutendijk’s condition and is used for proving the global convergence of a CG method. This condition together with (26) shows that(30)∑k=0∞gk4dk2<+∞.Definition 2.
The functionf is called uniformly convex [36] on Rn if there exists a positive constant m such that (31)mdk2≤dT∇2fxkd∀x,d∈Rn.We now show the global convergence of Algorithm A for uniformly convex functions.Lemma 3.
Let the sequences(xk) and (dk) be generated by Algorithm A and suppose that (31) holds. Then,(32)z1αkdk2≤-gkTdk,where z1=(1-ρ)-1m/2.Proof.
For details, see Lemma 2.1 of [44].Theorem 4.
Let the conditions in Assumptions (A1) and (A2) hold and the functionf(x) be uniformly convex. Then, (33)limk→∞⁡gk=0.Proof.
As(34)βkBZA=gkTgk-gk-1dk-1Tyk-1+μgkTdk-1,dk-1,yk-1=dk-1,gk-gk-1=dk-1,gk-dk-1,gk-1.Then, using the second Wolfe condition (4) and the sufficient descent condition,(35)gxk+αkdk,dk≥σ1gk,dk,gk,dk=-gk2,we have(36)dk-1,yk-1=dk-1,gk-dk-1,gk-1≥σ1gk-1,dk-1-gk-1,dk-1=-1-σ1gk-1,dk-1=1-σ1gk-12.From (11), (32), and (36) and Assumption (A2),(37)βkBZA≤gkTgk-gk-1dk-1Tyk-1≤gkLxk-xk-11-σ1gk-12=gkLsk-11-σ1-gk-1Tdk-1≤Lgkαk-1dk-11-σ1z1αk-1dk-12=Lgk1-σ1z1dk-1.Let us suppose that 1-σ1z1=z2, where 0<σ1<1 and z1>0 so that z2>0. Thus, (38)βkBZA≤Lgkz2dk-1⟹βkBZAdk-1≤Lgkz2.Now,(39)θkBZA≤gkTdk-1dk-1Tyk-1≤gkdk-11-σ1z1αk-1dk-12θkBZAyk-1≤gkdk-1yk-11-σ1z1αk-1dk-12≤gkdk-1Lsk-1z2αk-1dk-12=gkdk-1Lαk-1dk-1z2αk-1dk-12=Lgkz2.Combining (38) and (39) with (15), we obtain(40)dk≤gk+βkBZAdk-1+θkBZAyk-1≤gk+Lgkz2+Lgkz2=gk+2Lgkz2≤1+2Lz2gk.Now, let C=1+2L/z2 so that(41)dk≤Cgk,and we get dk2≤Cgk2. This implies that(42)1Cgk2≤1dk2gk4gk2≤Cgk4dk2.Hence, by (30), we have(43)limk→∞⁡gk2≤Climk→∞gk4dk2=0.We are now going to prove the global convergence of Algorithm A for nonconvex functions.Lemma 5.
Suppose that Assumptions (A1) and (A2) hold. Let the sequencexk be generated by Algorithm A. If there exists a constant ϵ>0 such that gk≥ϵ for every k≥0, then (44)∑k=0∞uk+1-uk2<+∞,where uk=dk/dk.Proof.
Asgk≤dk and gkTdk=-gk2, and also gk≥ϵ for all k, then dk>0 for all k. Hence, uk is well defined. If(45)rk=-1+θkBZAgkTyk-1/gk2gkdk,δk=βkBZA+dk-1dk,then uk=rk+δkuk-1, where uk and uk-1 are unit vectors. Therefore,(46)rk=δkuk-uk-1=uk-δkuk-1.As δk≥0,(47)uk-uk-1≤1+δkuk-uk-1≤uk-δkuk-1+δkuk-uk-1=2rk.Now, from Assumption (A2), (14), and (18),(48)θkBZAgkTyk-1gk2≤gkTdk-1μgkTdk-1gkTyk-1gk2≤Lxk-xk-1μgk≤Lbμϵ.From (17), (18), and (48), there exists a constant N1≥0 such that(49)-1+θkBZAgkTyk-1gk2gk≤gk+θkBZAgkTyk-1gk2gk≤γ+Lbϵμγ=N1.From (30) and (49), we obtain(50)∑k=0∞rk2≤∑k=0∞N12dk2≤∑k=0∞N12gk4gk4dk2≤N12ϵ4∑k=0∞gk4dk2<+∞.Combining this with (44) completes the proof.Theorem 6.
Let Assumptions (A1) and (A2) hold. Then, the sequence (xk) generated by Algorithm A satisfies(51)limk→∞⁡infgk=0.Proof.
Suppose thatlimk→∞⁡infgk≠0. Then, there exists a constant ϵ>0 such that gk≥ϵ∀k≥0.
The proof has two parts.
Part 1. See Theorem 2.2, step 1 in [36].
Part 2. From (15) and (49), we have (52)dk2≤βkBZA+dk-1+-1+θkBZAgkTyk-1gk2gk2≤βkBZA+dk-1+N12≤2βkBZA+dk-12+2N12≤2gkTgk-gk-1ε2dk-12+2N12≤2gkLsk-1ε2dk-12+2N12≤2γ2L2sk-12ε2dk-12+2N12.In the beginning of the proof, we suppose that limk→∞⁡infgk≠0. Then, there exist a positive constant ϵ and some γ>0 such that gk>γ>0. Thus, (53)∑k=0∞gkTdk2dk2>+∞⟹1dk2>+∞,which contradicts Assumption (A2), (30), and (52). Therefore,(54)limk→∞⁡infgk=0.


## 3.2. Numerical Discussion

We now report the results of several numerical experiments. Zhang et al. [25] demonstrated the superior numerical efficiency of the MTTHS algorithm with respect to PRP+ [41], CG_DESCENT [45], and L-BFGS [46] using the Wolfe line search, while Dai and Wen [40] reported the numerical efficiency of the DHS method. Thus, we compare the efficient three-term HS method proposed in this paper (named the Bakhtawar–Zabidin–Ahmad method, BZA) with MTTHS [25] and DHS [40]. The BZA method was implemented using the Wolfe–Powell line search (4) with ρ=0.1, σ=0.5, and μ=2.All codes were written in MATLAB 7.1 and run on an Intel Core i5 system with 8.0 GB RAM and a 2.60 GHz processor. Table1 lists the numerical results given by BZA, MTTHS, and DHS for a number of test functions. In the Table 1, NI/CT/GE/FE represents number of iterations, CPU time, number of gradient evaluations and number of function evaluations.Table 1
List of test problem functions.
Problem n MTTHS DHS BZA NI/CT/GE/FE NI/CT/GE/FE NI/CT/GE/FE Extended 2 1323/9.3448/4645/3321 1267/10.1753/4756/3488 364/3.1079/1365/1000 Trigonometric -1 50 4533/28.4686/15849/11315 3771/25.5829/14146/10374 2376/18.4341/8910/6533 function 500 11125/67.51/38848/27722 8163/55.0526/30616/22452 5904/46.5577/22140/16235  HIMMELBH(Cute) 2 9/0.4680/77/67 9/0.4538/77/67 9/0.4471/77/67 50 9/0.4572/77/67 9/0.4574/77/67 9/0.4620/77/67 5000 9/2.0529/77/67 9/2.0198/77/67 9/1.9930/77/67  Power function 2 3/0.3968/13/9 2/0.3881/9/6 2/0.3884/9/6 50 212/2.0540/849/636 3431/24.0407/13725/10293 65/0.7751/261/195 1000 4612/33.5261/18449/13836 F/F/F/F 1565/11.567/6261/4695  DENSCHNF 2 11/0.6773/64/52 12/0.5399/67/54 8/0.4719/50/41 50 14/0.5959/78/63 14/0.5260/75/60 9/0.4739/54/44 5000 10/1.7879/56/45 14/2.1633/75/60 9/1.6783/54/44  Sum Squares 2 3/0.4203/13/9 2/0.3861/9/6 2/0.3966/9/6 function 50 47/0.7252/189/141 39/0.6318/157/117 39/0.6162/157/117 1000 229/2.4542/917/687 1333/11.3244/5333/3999 191/1.9552/765/573  TRIDIA(Cute) 2 3/0.4056/13/9 2/0.3980/9/6 2/0.4024/9/6 50 100/1.6029/401/300 193/1.7752/773/579 56/0.7390/225/168 1000 604/5.2318/2417/1812 16019/122.48/64077/48057 349/3.22771397/1047  SINQUAD(Cute) 2 25/0.4804/102/76 1734/12.6402/6076/4341 25/0.5218/101/75 5000 F/F/F/F F/F/F/F 411/198.6198/2837/2425 10000 F/F/F/F F/F/F/F 417/493.6830/2650/2232  Generalized 50 23/0.5659/101/77 25/0.5348/109/83 21/0.5187/94/72 Quartic GQ2 100 23/0.5588/103/79 31/0.5938/133/101 22/0.5233/96/73 function. 5000 26/2.9409/116/89 23/2.6517/103/79 25/2.7548/110/84  Generalized 50 50/0.7767/248/197 43/0.6750/192/148 42/0.6934/198/155 Triagonal-2 500 43/1.5284/206/162 46/1.4306/209/162 38/1.4029/182/143 function 1000 45/2.1144/214/168 47/2.1176/214/166 39/1.8380/181/141  Extended 2 8/0.4315/32/23 9/0.4256/37/27 6/0.4158/25/18 Trigonometric -2 50 33/0.6514/148/114 26/0.5848/124/97 22/0.5586/106/83 function 7000 85/63.5473/626/540 71/44.8822/440/368 33/25.6757/251/217  LIARWHD 100 20/0.5798/136/115 16/0.5065/95/78 14/0.4865/84/69 5000 50/8.8611/390/339 53/8.7426/384/330 24/4.4628/189/164 10000 33/14.6362/245/211 53/19.3591/331/277 23/9.7171/165/141  Generalized 2 6/0.4058/27/20 6/0.4127/27/20 5/0.4008/23/17 Quartic GQ1 6000 11/1.8086/47/35 10/1.6695/43/32 10/1.7246/43/32 function 10000 11/3.4464/47/35 10/3.0683/43/32 10/3.0317/43/32  Extended QP2 2 17/0.8111/98/80 21/0.6076/125/103 16/0.5702/111/94 Quadratic Penalty 5000 226/56.4248/2247/2020 F/F/F/F 82/25.7327/1018/935 function 10000 137/95.8189/1457/1319 F/F/F/F 82/67.1490/1024/941  Extended Maratos 2 20/0.6479/131/110 43/0.8956/225/181 30/0.8305/193/162 function 1000 26/0.8290/176/149 F/F/F/F 30/0.8300/193/162 5000 F/F/F/F 45/5.8526/233/187 32/6.0318/243/210  DENSCHNC 2 6/0.4508/36/29 10/0.4624/51/40 6/0.4486/34/27 50 7/0.4499/38/30 10/0.4590/51/40 6/0.4696/34/27 600 8/0.5625/44/35 15/0.6240/130/114 7/0.5445/38/30  DIXON3DQ (Cute) 2 3/0.4835/13/9 2/0.3904/9/6 2/0.3878/9/6 20 106/1.2286/424/317 262/2.4917/1061/798 90/1.0709/360/269 600 2266/18.9637/9064/6797 F/F/F/F 2185/18.4756/8740/6554  EDENSCH function 50 3094/15.3448/9288/6193 3094/16.4610/9288/6193 3089/15.3239/9273/6183 1000 3094/17.6514/9288/6193 3094/18.4918/9288/6193 3089/17.6263/9273/6183 5000 3094/198.8550/9288/6193 3094/199.0048/9288/6193 3089/198.2240/9273/6183  Diagonal 2 function 50 749/6.8385/2626/1876 495/3.0663/1488/992 490/3.3271/1473/982 1000 16517/126.4914/59593/43075 8569/53.8256/25711/17141 8563/53.3166/25693/17129 10000 F/F/F/F 16484/283.6569/49456/32971 16478/279.44/49438/32959  DQDRTIC(Cute) 50 12/0.4358/49/36 5/0.4070/21/15 5/0.3940/21/15 5000 14/1.6324/57/42 5/0.7966/21/15 5/0.8084/21/15 10000 14/3.7862/57/42 5/1.6205/21/15 5/1.5979/21/15  Perturbed 50 43/0.6470/173/129 38/0.5837/153/114 38/0.6313/153/114 Quadratic function 1000 207/2.1710/829/621 1397/10.8367/5589/4196 187/1.9258/749/561 5000 481/44.4081/1925/1443 5125/435.0973/20501/15375 425/39.4768/1701/1275  Diagonal 4 function 50 4/0.3919/17/12 2/0.4015/9/6 2/0.3963/9/6 1000 5/0.4493/21/15 2/0.4005/9/6 2/0.4039/9/6 5000 5/0.8522/21/15 2/0.5598/9/6 2/0.5698/9/6  Extended Beale 50 15/0.4685/74/58 68/0.8247/281/212 15/0.4890/72/56 function 100 16/0.4739/74/57 68/0.8245/281/212 15/0.4855/72/56 500 16/0.5450/74/57 68/0.8840/281/212 15/0.5050/72/56  DENSCHNA 50 9/0.4336/44/34 24/0.5609/102/77 9/0.4462/44/34 1000 10/0.5912/48/37 26/0.7584/110/83 9/0.5909/44/34 5000 10/1.6387/46/35 26/3.0388/110/83 9/1.4694/44/34  STAIRCASE S1 20 79/0.9390/316/236 202/1.7976/818/615 72/0.8546/290/217 50 215/2.0539/860/644 1117/8.6778/4503/3385 183/1.6893/732/548 100 426/3.4107/1705/1278 3896/29.4293/15737/11840 372/3.0840/1490/1117  NONDQUAR 50 28674/216.605/114767/86092 F/F/F/F 14756/104.86/59098/44341 100 32283/244.026/129157/96873 F/F/F/F 17900/127.16/71670/53769 500 F/F/F/F F/F/F/F 32748/241.1/131043/98294  Extended Wood 500 128/1.5299/605/476 942/8.5789/4143/3200 96/1.4535/551/454 1000 146/1.7443/676/529 946/8.8946/4100/3153 101/1.7151/606/504 10000 213/57.8431/979/765 956/249.5361/4202/3245 89/31.8805/545/455  Extended Penalty 20 33/0.6528/144/110 37/0.7031/158/120 22/0.5670/98/75 300 F/F/F/F F/F/F/F 64/1.2248/365/300 600 F/F/F/F F/F/F/F 28/0.7428/172/143  Sphere function 2 1/0.4750/5/3 1/0.3777/5/3 1/0.3902/5/3 1000 1/0.3904/5/3 1/0.3877/5/3 1/0.3860/5/3 5000 1/0.4687/5/3 1/0.4576/5/3 1/0.4616/5/3  ARGLINB(Cute) 2 1/0.3913/5/3 1/0.3903/5/3 1/0.3840/5/3 50 1/0.3868/5/3 1/0.3941/5/3 1/0.3832/5/3 500 2/0.4279/9/6 2/0.4266/9/6 2/0.4246/9/6  Extended White 2 28/0.7668/192/163 69/1.2885/354/284 21/0.6586/136/114 and Holst function 500 29/0.9337/213/183 102/1.5134/488/385 21/0.6586/136/114 5000 23/4.6845/168/144 125/14.3950/577/451 21/3.8322/136/114  Extended Hiebert 50 2040/33.6457/16304/14263 F/F/F/F 838/21.7040/9977/9138 200 F/F/F/F F/F/F/F 901/23.007/10513/9611 1000 F/F/F/F F/F/F/F F/F/F/F  Quadratic QF1 50 44/0.6479/177/132 38/0.6068/153/114 38/0.6306/153/114 500 147/1.4565/589/441 574/4.7399/2297/1722 131/1.3814/525/393 10000 744/179.6695/2977/2232 F/F/F/F 606/146.3228/2425/1818  Quartic 50 11579/66.6569/34740/23160 11579/66.7991/34740/23160 11574/64.593/34725/23150 500 24975/148.8391/74928/49952 24975/146.0726/74928/49952 24968/142.57/74907/49938 1000 31473/201.6973/94422/62948 31473/218.8475/94422/62948 31466/191.54/94401/62934  Shallow function 1000 10/0.5712/45/34 48/0.7436/200/151 10/0.5557/45/34 5000 11/1.4925/49/37 48/4.9218/200/151 10/1.4117/45/34 10000 12/3.6303/53/40 50/13.2094/209/158 10/3.1569/45/34  VARDIM 50 28/1.1175/322/293 143/4.0110/1604/1460 16/0.8685/221/204 100 20/1.0429/286/265 293/5.9711/2604/2310 17/0.9508/250/232 500 41/2.2545/736/694 1557/25.9389/11724/10166 34/1.8745/645/610  DIXMAANA 6000 8/1.8623/35/26 8/1.8913/35/26 8/1.8504/35/26 6015 8/1.9276/35/26 8/1.8546/35/26 8/1.9200/35/26 6030 8/1.9301/35/26 8/1.9700/35/26 8/1.8819/35/26  DIXMAANB 9 7/0.4044/30/22 7/0.4141/30/22 7/0.4036/30/22 300 7/0.4550/30/22 7/0.4776/30/22 8/0.4415/34/25 6000 8/1.8966/34/25 8/1.8364/34/25 9/2.0362/38/28  DIXMAANC 9 6/0.4033/29/22 6/0.4191/29/22 6/0.4168/29/22 300 7/0.4701/33/25 6/0.4721/29/22 7/0.4707/33/25 6000 7/2.0093/33/25 7/2.0148/33/25 8/2.1736/37/28  DIXMAAND 90 7/0.4450/34/26 8/0.4333/38/29 8/0.4263/38/29 300 8/0.5272/38/29 8/0.5406/38/29 8/0.5418/38/29 6000 9/2.4166/42/32 7/2.0165/34/26 7/2.0556/34/26  DIXMAANE 9 19/0.5080/88/68 23/0.5720/107/83 18/0.4832/84/65 300 84/1.5278/421/336 1211/7.7407/3707/2495 84/2.1712/420/335 6000 331/81.2267/1655/1323 F/F/F/F 333/83.0952/1685/1351  EG2 2 5/0.4912/25/19 8/0.4128/40/31 4/0.4139/20/15 20 160/1.4413/642/481 1958/14.8104/8106/6147 110/1.0755/447/336 50 F/F/F/F 48/0.7452/228/179 656/5.3312/2773/2116  EG3 20 21/0.5445/88/66 25/0.5611/102/76 14/0.4851/60/45 50 25/0.5965/110/84 43/0.7618/207/163 25/0.5236/69/53 100 F/F/F/F F/F/F/F 20/0.5290/88/67  Fletcher function 50 24/0.5879/126/101 23/0.5870/123/99 22/0.5687/118/95 6000 27/5.2874/161/133 28/5.4497/168/139 26/4.7950/152/125 10000 27/10.4312/161/133 27/10.6308/163/135 26/9.8879/155/128  Extended 50 8/0.4229/37/28 11/0.4510/49/37 9/0.4370/41/31 Himmelblau 1000 8/0.4706/39/30 12/0. 5342/53/40 9/0.4775/41/31 function 5000 9/1.4066/43/33 13/1.6584/57/43 9/1.3377/41/31  Extended 2 11/0.5889/75/63 33/0.6806/163/129 10/0.4929/69/58 Freudenstein 50 F/F/F/F 36/0.7871/230/193 10/0.4700/69/58 and Roth function 200 16/0.5442/102/85 37/0.8501/241/203 11/0.4993/73/61  Dixon and Price 20 132/1.6580/615/482 333/3.2018/1409/1075 131/1.5682/603/471 function 50 185/2.5157/1034/848 478/4.7648/2199/1720 165/2.2048/900/734 100 523/6.5773/2938/2414 1243/11.1703/5672/4428 439/5.4568/2422/1982  Raydan 1 function 2 106/1.3363/319/212 105/0.8502/316/210 99/0.8493/298/198 50 59/0.8854/237/177 88/1.0277/364/275 58/0.7714/233/174 100 70/0.9532/282/211 155/1.5252/625/469 70/0.8892/282/211  Raydan 2 function 2 2/0.4129/9/6 2/0.3995/9/6 3/0.3971/13/9 50 2/0.3991/9/6 2/0.3981/9/6 3/0.4176/13/9 100 2/0.4002/9/6 2/0.4123/9/6 3/0.3906/13/9  NONDIA(SHANO- 500 9/0.5483/63/53 11/0.4937/70/58 7/0.4938/55/47 78) 6000 14/2.7799/82/67 46/6.5297/212/165 9/2.3946/70/60 10000 16/6.3412/96/79 74/21.4446/339/264 15/6.2113/92/76  Extended Block 500 30/1.0226/52000/44250 32/0.9386/32250/24000 39/1.1887/44000/34000 Diagonal BD1 1000 39/3.6068/195000/175000 33/1.3795/66500/49500 39/1.6724/88500/68500 function 10000 38/22.3738/1070000/875000 35/14.5725/705000/525000 43/20.1088/965000/745000  SINCOS 2000 F/F/F/F F/F/F/F 8/0.6960/39/30 5000 F/F/F/F F/F/F/F 8/1.2553/39/30 10000 F/F/F/F F/F/F/F 8/2.7535/39/30  DIXMAANH 90 58/0.8867/290/231 388/2.5254/1230/841 57/1.0443/286/228 300 81/1.5051/408/326 1264/7.8924/3872/2607 81/1.3140/408/326 600 126/4.4107/630/503 2407/40.8602/7294/4886 119/4.0122/596/476  Quadratic QF2 50 77/0.9476/330/252 107/1.1580/454/346 68/0.8775/293/224 function 200 183/1.7984/787/603 337/2.9913/1419/1081 139/1.5/610/470 2000 1150/34.4704/4862/3711 2903/85.3362/12110/9206 540/17.4638/2404/1863  Tridiagonal double 20 108/1.1547/438/329 1915/14.1311/7667/5751 101/1.1136/410/308 Bordered 50 407/3.3266/1633/1225 11157/78.2325/44633/33475 355/2.9421/1425/1069 500 6278/48.1130/25119/18840 13470/103.5476/53887/40416 4595/35.3993/18387/13791  Generalized 2 1323/8.3265/4645/3321 1267/8.4042/4756/3488 364/2.6867/1365/1000 Triagonal1 function 50 25/0.5255/103/77 28/0.504/115/86 24/0.5140/99/74 100 24/0.5630/99/74 27/0.6205/111/83 23/0.5242/95/71  Extended QP2 50 9/0.4269/49/39 15/0.4503/71/55 9/0.4190/49/39 Quadratic penalty 200 13/0.4682/70/56 14/0.6931/74/59 12/0.4620/66/53 function 3000 F/F/F/F F/F/F/F 17/1.5340/118/100  Extended 2 5/0.4089/22/16 6/0.4254/26/19 5/0.4095/22/16 DENSCHNB 500 5/0.4222/22/16 7/0.4313/30/22 6/0.4165/26/19 function 10000 5/1.7240/22/16 7/2.1577/30/22 6/1.9461/26/19  Extended three- 2 7/0.4187/30/22 13/0.4386/54/40 7/0.417/30/22 Exponential terms 50 7/0.4211/750/550 14/0.4492/1450/1075 7/0.4255/750/550 100 7/0.4378/1500/1100 14/0.4705/2900/2150 7/0.4183/1500/1100  DIXMAANF 9 23/0.6308/109/85 23/0.5828/109/85 19/0.5129/90/70 90 51/0.8509/256/204 386/2.4637/1229/842 51/1.1421/256/204 300 90/1.4444/451/360 1260/7.8258/3871/2610 90/1.5578/451/360  DIXMAANG 9 19/0.5318/95/75 26/0.5670/127/100 21/0.5403/103/81 90 83/1.2240/424/340 379/2.4949/1221/841 56/0.8767/280/223 300 137/1.8866/643/505 1241/14.5812/3834/2592 569/5.5495/2477/1907  Extended 2 25/0.7100/159/133 24/0.9013/120/95 27/0.7803/163/135 Rosenbrock 1000 14/0.8076/82/67 26/0.6537/128/101 28/0.7818/167/138 function 5000 19/2.8693/109/89 27/3.2102/132/104 30/4.4233/175/144  ARWHEAD 500 F/F/F/F F/F/F/F 10/0.4429/54/43 3000 F/F/F/F F/F/F/F 5/0.7593/38/32 8000 F/F/F/F F/F/F/F 7/2.5096/49/41  Hager function 2 4/0.4001/17/12 6/0.4188/25/18 4/0.4008/17/12 50 20/0.4789/82/61 24/0.5101/98/73 20/0.4738/82/61 100 24/0.5275/98/73 F/F/F/F 24/0.5382/111/86  Extended Powell 1000 4008/108.2/4032500/3030250 F/F/F/F 361/10.5/384000/293500 function 3000 1026/86.1/3124500/2354250 F/F/F/F 108/10.8/379500/297750 5000 2213/330/11330000/8562500 F/F/F/F 306/48/1652500/1268750  BIGGSB1 function 2 1/0.3861/5/3 1/0.3866/5/3 1/0.3895/5/3 20 53/0.7214/213/159 20/0.4869/80/59 20/0.4764/80/59 50 201/1.9444/804/602 867/7.1960/3500/2632 50/0.7281/200/149  Extended Cliff 100 11657/87/2075150/1492250 39907/329/7892000/5896600 1674/12/293750/210000 5000 F/F/F/F F/F/F/F 1009/132/8857500/633250  ENGVAL8 2 7/0.4675/33/25 10/0.4709/45/34 7/0.4756/36/28 20 22/0.5657/99/76 32/0.6306/138/105 20/0.5382/90/69  Trecanni function 2 6/0.4146/26/19 6/0.4212/26/19 4/0.3982/18/13  GENROSEN-2 2 25/0.8096/159/133 24/0.5864/120/95 27/0.6770/163/135  Generalized Quartic function 2 6/0.4068/27/20 6/0.4082/27/20 5/0.4081/23/17  Diagonal 1 function 2 6/0.4015/25/18 7/0.4085/29/21 4/0.4207/18/13  Six Hump function 2 7/0.4112/31/23 7/0.4271/31/23 6/0.4064/27/20  Three Hump function 2 11/0.4441/52/40 11/0.4335/50/38 10/0.4397/47/36  Booth function 2 3/0.3930/13/9 2/0.4043/9/6 2/0.3919/9/6  Zett1 function 2 26/0.5067/105/78 30/0.5581/126/95 24/0.5046/102/77According to Moré et al. [47], the efficiency of any method can be determined by its performance on a number of test functions. The number of test functions should not be too large or too small, with 75 considered ideal for testing the efficiency of any method. The test functions in Table 1 were taken from Andrei’s test function collection [48] with standard initial points and dimensions ranging from 2 to 10000.If the solution had not converged after 500 seconds, the program was terminated. Generally, convergence was achieved within this time limit; functions for which the time limit was exceeded are denoted by “F” for Fail in Table1.The Sigma plotting software was used to graph the data. We adopt the performance profiles given by Dolan and Moré [49]. Thus, MTTHS, DHS, and BZA are compared in terms of NI/CT/GE/FE in Figures 1–4. For each method, we plotted the fraction P of problems that were solved correctly within a factor t of the best time. In the figures, the uppermost curve is the method that solves the most problems within a factor t of the best time. From Table 1 and Figures 1–4, the BZA method outperforms the MTTHS algorithm and DHS method in terms of NI, CT, GE, and FE.Figure 1
Performance profiles based on number of iterations.Figure 2
Performance profiles based on CPU time.Figure 3
Performance profiles based on gradient evaluation.Figure 4
Performance profiles based on function evaluation.The BZA method solves around 99.5% of the problems, and the performance of BZA is 85% better than that of DHS and 77% better than that of MTTHS. We can also conclude that, on average, three-term conjugate gradient methods are 85% better than two-term conjugate gradient methods (DHS).


## 4. Conclusion

We have proposed a modified three-term HS conjugate gradient method. An attractive property of the proposed method is that it produces a sufficient descent conditiongkTdk=-gk2, regardless of the line search. The global convergence properties of the proposed method have been established under Wolfe line search conditions. Numerical results show that the proposed method is more efficient and robust than state-of-the-art three term (MTTHS) and two-term (DHS) CG methods.



---

*Source: 5057096-2018-09-27.xml*