# A Descent Four-Term Conjugate Gradient Method with Global Convergence Properties for Large-Scale Unconstrained Optimisation Problems

Authors: Ahmad Alhawarat; Ghaliah Alhamzi; Ibitsam Masmali; Zabidin Salleh
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

The conjugate gradient method is a useful method to solve large-scale unconstrained optimisation problems and to be used in some applications in several fields such as engineering, medical science, image restorations, neural network, and many others. The main benefit of the conjugate gradient method is not using the second derivative or its approximation, such as Newton’s method or its approximation. Moreover, the algorithm of the conjugate gradient method is simple and easy to apply. This study proposes a new modified conjugate gradient method that contains four terms depending on popular two- and three-term conjugate gradient methods. The new algorithm satisfies the descent condition. In addition, the new CG algorithm possesses the convergence property. In the numerical results part, we compare the new algorithm with famous methods such as CG-Descent. We conclude from numerical results that the new algorithm is more efficient than other popular CG methods such as CG-Descent 6.8 in terms of number of function evaluations, number of gradient evaluations, number of iterations, and CPU time.


---

## Body

## 1. Introduction

To solve large-scale unconstrained optimisation problems, we prefer to use conjugate gradient (CG) since it is efficient and robust and does not use the second derivative. Consider the following problem:(1)minfxℝn,where f:ℝn⟶ℝ is a continuous and differentiable function, and the gradient is available. The CG method generates a sequence of xk given by the equation(2)xk+1=xk+αkdk,k=1,2,….The step lengthαk was obtained using line search. dk is a search direction of the CG method defined as follows:(3)dk=−gk,ifk=1,−gk+βkdk−1,ifk≥2,where gk=gxk=∇f and βk is known as the CG formula.To obtain the step length, we use the strong Wolfe-Powell (SWP) [1, 2] line search given by the following equations:(4)fxk+αkdk≤fxk+δαkgkTdk,(5)gxk+αkdkTdk≤σgkTdk,where 0<δ<σ<1.The weak Wolfe–Powell (WWP) line search is given by equation (4) and(6)gxk+αkdkTdk≥σgkTdk.The popular classical formulas of CG methods Hestenses–Stiefel (HS) [3], Polak–Ribiere–Polyak (PRP) [4], Liu–Storey (LS) [5], Fletcher–Reeves (FR) [6], Fletcher (CD) [7], and Dai–Yuan (DY) [8] are as follows:(7)βkHS=gkTyk−1dk−1Tyk−1,βkPRP=gkTyk−1gk−12,βkLS=−gkTyk−1dk−1Tgk−1,βkFR=gk2gk−12,βkCD=−gk2dk−1Tgk−1,βkDY=gk2dk−1Tgk−1,where yk−1=gk−gk−1.Powell [9] proposed an example to show that a function does not satisfy the convergence even if the exact line search is employed with the PRP formula. Gilbert and Nocedal [10] used Powell [9] suggestion for the PRP formula. They proved that if βkPRP+=max0,βkPRP, the WWP line search is employed and the sufficient descent Wolfe-Powell line search condition is satisfied; then βkPRP+ is globally convergent. Moreover, Zoutendijk [11] showed that the FR formula with CG method and the exact line search has convergence analysis. Finally, Al-Baali [12] proved that the CG method with the FR coefficient is globally convergent when σ≤1/2 SWP is employed.In 2006, Wei et al. [13] presented a nonnegative CG formula that can satisfy the descent property and global convergence property as follows:(8)βkWYL=gkTgk−gk/gk−1gk−1gk−12,where yk−1=gk−gk−1. In 2016, Alhawarat et al. [14] presented the following nonnegative CG formula with new restart property:(9)βkAZPRP=gk2−μkgkTgk−1gk−12,ifgk2>μkgkTgk−1,0,otherwise,where ⋅ represents the Euclidean norm and μk is defined as follows:(10)μk=xk−xk−1yk−1.In 2020, Kaelo et al. [15] proposed a nonnegative CG formula and compared the new formula with βkAZPRP. The proposed equation is as follows:(11)βkPKT=gk2−gkTgk−1maxdk−1Tyk−1,−gk−1Tdk−1,if0<gkTgk−1<gk2,gk2maxdk−1Tyk−1,−gk−1Tdk−1,otherwise.In 2001, Dai and Liao [16] proposed the following conjugacy condition:(12)dkTyk−1=−tgkTsk−1,where sk−1=xk−xk−1 and t≥0. In the case of t=0, equation (13) becomes the classical conjugacy condition. By using equations (2) and (12), Dai and Liao[16] proposed the following CG formula:(13)βkDL=gkTyk−1dk−1Tyk−1−tgkTsk−1dk−1Tyk−1=βkHS−tgkTsk−1dk−1Tyk−1.However,βkDL inherits the same problem as βkPRP and βkHS; that is, βkDL is not nonnegative in general. Thus, Gilbert and Nocedal [10] replaced equation (13) by(14)βkDL+=maxβkHS,0−tgkTsk−1dk−1Tyk−1.In 2006, Hager and Zhang [17, 18] presented the following CG formula based on (13):(15)βkHZ=maxβkN,ηk,where βkN=1/dkTykyk−2dkyk2/dkTykTgk, ηk=−1/dkminη,gk, and η>0 is a constant.Note that ift=2yk2/skTyk, then βkN=βkDY.Based on equation (13), Andrei [19, 20] proposed two three-term CG (TTCG) methods in 2013 as follows:(16)dk=−gk+gkTyk−1−tgkTsk−1yk−1Tdk−1dk−1−gkTdk−1yk−1Tdk−1yk−1,t=1+yk−12sk−1Tyk−1,dk=−gk+gkTyk−1−tgkTsk−1yk−1Tdk−1dk−1−gkTdk−1yk−1Tdk−1yk−1,t=1+2yk−12sk−1Tyk−1.Also, based on equation (13), Babaie-Kafaki and Ghanbari [21] proposed the following CG method:(17)dk=−gk+gkTyk−1−tgkTsk−1yk−1Tdk−1dk−1−gkTdk−1yk−1Tdk−1yk−1,t=maxς,1−yk−12sk−1Tyk−1,where ς>0.Similar to [19–21], Deng and Wan [22] in 2015 presented the following CG method:(18)dk=−gk+gkTyk−1−tgkTsk−1yk−1Tdk−1dk−1−gkTdk−1yk−1Tdk−1yk−1,t=max0,1−yk−12sk−1Tyk−1.In 2019, Liu et al. [23] proposed(19)dk=−gk+βkLS−gk−12gkTdk−1dk−1Tgk−12dk−1+gkTdk−1dk−1Tyk−1gk−1,with the following assumption:(20)gkTdk−1dk−1Tgk−1>ν∈0,1.Moreover, Liu et al. [23] proved the sufficient descent condition for no convex functions to solve nonlinear monotone equations. To avoid using the condition gkTdk−1/dk−1Tgk−1>ν∈0,1, Liu et al. [24] constructed the following three-term CG method:(21)dk=−gk+βkLS−gk−12gkTsk−1dk−1Tgk−12dk−1−gkTdk−1dk−1Tyk−1gk−1,and they used it to solve equation (1). Liu et al. [24] proposed wide choices using equation (21) as follows:(22)dkMTTPRP=−gk+βkPRP−gkTsk−1gk−12dk−1+gkTdk−1gk−12gk−1,dkMTTHS=−gk+βkHS−gk−12gkTsk−1dk−1Tyk−12dk−1+gkTdk−1dk−1Tyk−1gk−1,dkADAP=−gk+gkTyk−1tk−1−gk−12gkTsk−1tk−12dk−1+gkTdk−1tk−1gk−1,tk−1=max−dk−1gk−1,gk−12,dk−1Tyk−1.In 2020, Yao et al. [25] proposed three terms of CG with a new choice of t as follows:(23)dk+1=−gk+1+gkTyk−tkgk+1TskykTdkdk+gk+1TdkykTdkyk.Based on the SWP line search, Yao et al. [25] selected tk to satisfy the descent condition as follows:(24)tk>yk2ykTsk.Yao et al. [25] also proposed a theorem stating that if tk is close to yk2/ykTsk, then the search direction results in a zigzag search path. Therefore, they selected the following choice for tk:(25)tk=1+2yk2ykTsk.As an application of the CG method, we can restore actual images from damaged images by minimising thez algorithm with an efficient number of iterations and CPU time. Moreover, we can test the quality using the root mean square error (RMSE) between the actual image (original) and the restored image as follows:(26)rmse=ζ−ζk2ζ.Here,ζ and ζk are the actual image and restored image, accordingly. Moreover, the CG method can be applied in several fields: neural network, image restoration, medical science, machine learning, finance and economics, and many other fields. The reader can refer to [26–36] for more about the CG method and its applications.


## 2. The New Search Direction

In the literature review, we note that the general form of the three-term CG method can be written as follows:(27)dk=−gk+ηkdk−1−θkyk−1,where θk and ηk are CG parameters. Based on equation (13), we extend equation (27) to the following form:(28)dkFTCGHS=−gk+βkHS−tkgkTsk−1dk−1Tyk−1dk−1−gkTdk−1dk−1Tyk−1yk−1+sk−1,where tk=sk/yk−1.In this paper, we assume the following for equation (28):(29)ηk=βkHS−tkgkTsk−1dk−1Tyk−1,θk=gkTdk−1dk−1Tyk−1.Note that equation (28) can be reduced to the HSCG method if we use an exact line search.By using exact line search, we obtain(30)gkTdk−1=0,and since gkTsk−1=αkgkTdk−1, we obtain(31)dkFTCGHS=−gk+βkHSdk−1.Note thatηk is similar to βkDL with different values of tk, where βkDL inherits the conjugacy condition with inexact line search. For θk, it is worth noting that it contains the term gkTdk−1 and is divided by the denominator of the HS method. Meanwhile, for yk−1+sk−1, the direction yk−1 is an essential term in obtaining the descent condition when multiplied by negative gradient. It is also useful in terms of efficiency, i.e., if this term goes to zero, the search direction will restart using the steepest descent method, avoiding equation (28) to cycle without reaching the solution.Figure1 describes the steps of the CG method to obtain the stationary point using SWP line search and equation (28) with stopping criteria of gk≤10−6.Figure 1
The steps of the CG method to obtain the optimum point.


## 3. Global Convergence Analysis of the CG Method with Figure1

The following assumption is crucial to satisfy the convergence analysis of CG methods.Assumption 1.
(A).
The level setΩ=x|fx≤fx1 is bounded; that is, a positive constant ρ exists such that(32)x≤ρ,∀x∈Ω.(B).
In some neighbourhoodQ of Ω, f is continuously differentiable, and its gradient is Lipschitz continuous; that is, for all, x,y∈Q, there exists a constant L>0 such that(33)gx−gy≤Lx−y.
In addition to this assumption, we can conclude that there exists a positive constantB such that(34)gu≤B,∀u∈N.
The descent condition (downhill condition),(35)gkTdk<0,∀k≥1,is useful in studying the CG method and plays an important role in the proof of global convergence analysis. Abaali [12] modified (35) to the following form and used it to prove the FR method:(36)gkTdk≤−cgk2,∀k≥1,where c∈0,1. Equation (36) is the sufficient descent condition. Moreover, using equation (36) is better than equation (35) since we can control the quantity of gkTdk by using gk2.


### 3.1. The Descent Property of the New Search Direction

The following theorem shows that the search direction in equation (28) ensures that the sufficient descent condition (35) is satisfied with the SWP line search.Theorem 1.
Let the sequences generate (1) and (28), computed by SWP line search. Then, the sufficient descent condition holds.Proof.
Multiplying (28) by gkT yields(37)gkTdk=−gk2+gkTyk−1dk−1Tyk−1−tgkTsk−1dk−1Tyk−1gkTdk−1−gkTdk−1dk−1Tyk−1gkTyk−1+sk−1=−gk2+gkTyk−1dk−1Tyk−1gkTdk−1−tgkTsk−1dk−1Tyk−1gkTdk−1−gkTdk−1dk−1Tyk−1gkTyk−1−gkTdk−1dk−1Tyk−1gkTsk−1=−gk2−tαkgkTdk−1dk−1Tyk−1gkTdk−1−αkgkTdk−1dk−1Tyk−1gkTdk−1=−gk2−αkgkTdk−12dk−1Tyk−1t+1.
From Wolfe–Powell search, we obtain(38)dk−1Tyk−1>0,and thus(39)gkTdk≤−gk2.
Zoutendijk [11] presented a useful lemma for analysing the global convergence property of the CG method. The lemma is given as follows.Lemma 1.
Let Assumption1 hold. Consider any CG method in the form of (1) and (2), and αk satisfies the WWP line search of (5) and (6), in which the search direction is descent. Then, the following condition holds:(40)∑k=0∞gkTdk2dk2<∞.


### 3.2. Global Convergence of Figure1 with Convex Functions

Dai and Liao [16] presented a useful theorem to obtain the global convergence theorem of the CG method as follows.Theorem 2.
Suppose that Assumption1 holds. Consider any conjugate gradient method in the form of equations (1) and (2), where dk is a descent direction and αk is obtained from the strong Wolfe line search. If(41)∑k≥1∞1dk2=∞,then(42)liminfk⟶∞gk=0.The following theorem shows that the new search direction strongly satisfies the convergences analysis with convex functions.Theorem 3.
Suppose that Assumption1 holds. Consider the CG method in the forms of equations (2) and (28) and dk as a descent direction, where αk is obtained using equations (3) and (4). If fx is a uniformly convex function, then liminfk⟶∞gk=0.Proof.
Because functionfx is uniformly convex, there exists a positive constant ϖ such that(43)ϖx−y2≤∇fx−∇fyTx−y,for all x,y∈P. Thus,(44)dk−1yk−1≥ϖαk−1dk−12.
By using equation (28) and triangular inequality, we obtain(45)dk≤gk+gkTyk−1dk−1Tyk−1+tgkTsk−1dk−1Tyk−1dk−1+gkTdk−1dk−1Tyk−1yk−1+sk−1.
By using equation (44), we have(46)dk≤gk+gkTyk−1ϖαk−1dk−12+tgkTsk−1ϖαk−1dk−12dk−1+gkTdk−1ϖαk−1dk−12yk−1+sk−1.
Then, using triangular inequality and Assumption1 yields(47)dk≤gk+Lαk−1gkdk−12ϖαk−1dk−12+tαk−1gkdk−12ϖαk−1dk−12+gkdk−12ϖαk−1dk−12Lαk−1+αk−1≤gk+Lgkϖ+tgkϖ+gkϖL+1≤gk+gkϖ2L+t+1.
By using Assumption1, we now have(48)dk≤B+Bϖ2L+t+1.
LetB+B/ϖ2L+t+1=M, where M is constant. Thus, we obtain(49)dk≤M.
By using Theorem2, we now have(50)liminfk⟶∞gk=0.


### 3.3. Global Convergence of Figure1 with General Nonlinear Functions

The following restriction forηk is very important to establish the convergence analysis for our new search direction. The main importance of this restriction is to avoid the CG method multiplayer, which will be nonnegative.(51)ηk+=max0,βkHS−tgkTsk−1dk−1Tyk−1.Thus, equation (28) becomes(52)dk=−gk+ηk+dk−1−θkyk−1+sk−1.Lemma 2.
Assume that Assumption1 holds and the sequences gk and dk are generated using Figure 1, where the step size αk is computed via the SWP line search of (4) and (5) or weak Wolfe–Powell line search of (4) and (6), such that the sufficient descent condition holds. If βk≥0, there exists a constant γ>0, such that gk>γ for all k≥1. Then, dk≠0 and (53)∑k=0∞uk+1−uk2<∞,where uk=dk/dk.Proof.
First, ifdk=0, then, from the sufficient descent condition, we obtain gk=0. Thus, we suppose that dk≠0 and(54)γ¯≥gk≥γ>0,∀k≥1.
We define(55)uk=wk+δkuk−1,where(56)wk=−gk−θkyk−1+sk−1dk,δk=ηk+dk−1dk.
Sinceuk is a unit vector, then(57)wk=uk−δkuk−1=δkuk−uk−1.
Using the triangular inequality andδk≥0, we now have(58)uk−uk−1≤1+δkuk−uk−1=uk−δkuk−1−uk−1−δkuk≤uk−δkuk−1+uk−1−δkuk=2wk.
We define(59)ν=−gk−θkyk−1+sk−1.
Using the triangular inequality, we obtain(60)ν≤gk+θkyk−1+sk−1.
Now, utilising the equations of SWP of (4) and (5), we can conclude the two following inequalities given by(61)dk−1Tyk−1≥σ−1gk−1Tdk−1,θk=gkTdk−1dk−1Tyk−1≤σ1−σ=ξ.
Also, by using weak Wolfe–Powell line search of (4) and (6), we obtain(62)dk−1Tyk−1≥σ−1gk−1Tdk−1.
Suppose thatαk≥1; thus(63)θk=gkTdk−1dk−1Tyk−1≤gkαk−1dk−11−σgk−12=gksk−11−σgk−12≤γ¯ρ1−σγ2=ζ,where ζ is some positive constant. Since θk≤ζ with αk≥1, then θk≤ζ with αk<1. Thus θk≤ζ for all αk>0.
By using the triangular inequality and Assumption1, we obtain(64)yk−1+sk−1≤yk−1+sk−1≤2B+2ρ.
LetM=maxξ,ζ. Thus, the inequality in (60) can be written as follows:(65)ν≤B+M2B+2ρ.
Let(66)T=B+M2B+2ρ,then(67)ν≤T.
From equation (54), we now have(68)uk−uk−1≤2w.
By using equations (53) and (54), we obtain the following:(69)∑k=0∞uk+1−uk2≤4∑k=0∞w2≤4T2∑k=0∞1dk2<∞,which completes the proof.
The following property, which is referred to as Property1, was presented by Gilbert and Nocedal in [10].Property 1.
Consider a method of the form of (2) and (3). Assume that (54) is satisfied for all k≥1. Then, the CG method has Property 1 if there exist constants b>1 and λ>0 such that, for all k≥1, ηk≤b and if sk≤λ, we obtain ηk≤1/2b.Lemma 3.
Consider the CG method of the form of (1) and (2) with ηk+, where the step size satisfies SWP line search of (4) and (5). If equation (54) holds, then ηk+ possesses Property∗. Namely, suppose that (54) holds; then there exist b>1 and λ>0 such that, for all k≥1, we have ηk+≤b and if sk≤λ, we obtain ηk+≤1/2b.Proof.
As a result, setb=2L+tγ¯B/1−σγ2≥1 and λ=1−σcγ2/2bL+tγ¯.
Using SWP of (4) and (5) with equation (54), we obtain(70)ηk+≤gkTyk−1dk−1Tyk−1+tgkTsk−1dk−1Tyk−1≤Lgksk−1+tgksk−11−σγ2≤2L+tγ¯B1−σγ2=b>1.
Also, ifsk≤λ, we obtain(71)ηk+≤gkTyk−1dk−1Tyk−1+tgkTsk−1dk−1Tyk−1≤Lgksk−1+tgksk−11−σγ2≤L+tγ¯λ1−σγ2,where(72)ηk+≤12b.
By using Lemma 4.1 and Lemma 4.2 in [10], we obtain the following result.Theorem 4.
Let the sequencesxk and dk be generated by (2) and (3) with the CG method in equation (28), where the step size satisfies (4) and (5). Then, we obtain the results by using Lemmas 2 and 3, as well as Lemmas 4.1 and 4.2 in [10], where liminfk⟶∞gk=0.


## 3.1. The Descent Property of the New Search Direction

The following theorem shows that the search direction in equation (28) ensures that the sufficient descent condition (35) is satisfied with the SWP line search.Theorem 1.
Let the sequences generate (1) and (28), computed by SWP line search. Then, the sufficient descent condition holds.Proof.
Multiplying (28) by gkT yields(37)gkTdk=−gk2+gkTyk−1dk−1Tyk−1−tgkTsk−1dk−1Tyk−1gkTdk−1−gkTdk−1dk−1Tyk−1gkTyk−1+sk−1=−gk2+gkTyk−1dk−1Tyk−1gkTdk−1−tgkTsk−1dk−1Tyk−1gkTdk−1−gkTdk−1dk−1Tyk−1gkTyk−1−gkTdk−1dk−1Tyk−1gkTsk−1=−gk2−tαkgkTdk−1dk−1Tyk−1gkTdk−1−αkgkTdk−1dk−1Tyk−1gkTdk−1=−gk2−αkgkTdk−12dk−1Tyk−1t+1.
From Wolfe–Powell search, we obtain(38)dk−1Tyk−1>0,and thus(39)gkTdk≤−gk2.
Zoutendijk [11] presented a useful lemma for analysing the global convergence property of the CG method. The lemma is given as follows.Lemma 1.
Let Assumption1 hold. Consider any CG method in the form of (1) and (2), and αk satisfies the WWP line search of (5) and (6), in which the search direction is descent. Then, the following condition holds:(40)∑k=0∞gkTdk2dk2<∞.


## 3.2. Global Convergence of Figure1 with Convex Functions

Dai and Liao [16] presented a useful theorem to obtain the global convergence theorem of the CG method as follows.Theorem 2.
Suppose that Assumption1 holds. Consider any conjugate gradient method in the form of equations (1) and (2), where dk is a descent direction and αk is obtained from the strong Wolfe line search. If(41)∑k≥1∞1dk2=∞,then(42)liminfk⟶∞gk=0.The following theorem shows that the new search direction strongly satisfies the convergences analysis with convex functions.Theorem 3.
Suppose that Assumption1 holds. Consider the CG method in the forms of equations (2) and (28) and dk as a descent direction, where αk is obtained using equations (3) and (4). If fx is a uniformly convex function, then liminfk⟶∞gk=0.Proof.
Because functionfx is uniformly convex, there exists a positive constant ϖ such that(43)ϖx−y2≤∇fx−∇fyTx−y,for all x,y∈P. Thus,(44)dk−1yk−1≥ϖαk−1dk−12.
By using equation (28) and triangular inequality, we obtain(45)dk≤gk+gkTyk−1dk−1Tyk−1+tgkTsk−1dk−1Tyk−1dk−1+gkTdk−1dk−1Tyk−1yk−1+sk−1.
By using equation (44), we have(46)dk≤gk+gkTyk−1ϖαk−1dk−12+tgkTsk−1ϖαk−1dk−12dk−1+gkTdk−1ϖαk−1dk−12yk−1+sk−1.
Then, using triangular inequality and Assumption1 yields(47)dk≤gk+Lαk−1gkdk−12ϖαk−1dk−12+tαk−1gkdk−12ϖαk−1dk−12+gkdk−12ϖαk−1dk−12Lαk−1+αk−1≤gk+Lgkϖ+tgkϖ+gkϖL+1≤gk+gkϖ2L+t+1.
By using Assumption1, we now have(48)dk≤B+Bϖ2L+t+1.
LetB+B/ϖ2L+t+1=M, where M is constant. Thus, we obtain(49)dk≤M.
By using Theorem2, we now have(50)liminfk⟶∞gk=0.


## 3.3. Global Convergence of Figure1 with General Nonlinear Functions

The following restriction forηk is very important to establish the convergence analysis for our new search direction. The main importance of this restriction is to avoid the CG method multiplayer, which will be nonnegative.(51)ηk+=max0,βkHS−tgkTsk−1dk−1Tyk−1.Thus, equation (28) becomes(52)dk=−gk+ηk+dk−1−θkyk−1+sk−1.Lemma 2.
Assume that Assumption1 holds and the sequences gk and dk are generated using Figure 1, where the step size αk is computed via the SWP line search of (4) and (5) or weak Wolfe–Powell line search of (4) and (6), such that the sufficient descent condition holds. If βk≥0, there exists a constant γ>0, such that gk>γ for all k≥1. Then, dk≠0 and (53)∑k=0∞uk+1−uk2<∞,where uk=dk/dk.Proof.
First, ifdk=0, then, from the sufficient descent condition, we obtain gk=0. Thus, we suppose that dk≠0 and(54)γ¯≥gk≥γ>0,∀k≥1.
We define(55)uk=wk+δkuk−1,where(56)wk=−gk−θkyk−1+sk−1dk,δk=ηk+dk−1dk.
Sinceuk is a unit vector, then(57)wk=uk−δkuk−1=δkuk−uk−1.
Using the triangular inequality andδk≥0, we now have(58)uk−uk−1≤1+δkuk−uk−1=uk−δkuk−1−uk−1−δkuk≤uk−δkuk−1+uk−1−δkuk=2wk.
We define(59)ν=−gk−θkyk−1+sk−1.
Using the triangular inequality, we obtain(60)ν≤gk+θkyk−1+sk−1.
Now, utilising the equations of SWP of (4) and (5), we can conclude the two following inequalities given by(61)dk−1Tyk−1≥σ−1gk−1Tdk−1,θk=gkTdk−1dk−1Tyk−1≤σ1−σ=ξ.
Also, by using weak Wolfe–Powell line search of (4) and (6), we obtain(62)dk−1Tyk−1≥σ−1gk−1Tdk−1.
Suppose thatαk≥1; thus(63)θk=gkTdk−1dk−1Tyk−1≤gkαk−1dk−11−σgk−12=gksk−11−σgk−12≤γ¯ρ1−σγ2=ζ,where ζ is some positive constant. Since θk≤ζ with αk≥1, then θk≤ζ with αk<1. Thus θk≤ζ for all αk>0.
By using the triangular inequality and Assumption1, we obtain(64)yk−1+sk−1≤yk−1+sk−1≤2B+2ρ.
LetM=maxξ,ζ. Thus, the inequality in (60) can be written as follows:(65)ν≤B+M2B+2ρ.
Let(66)T=B+M2B+2ρ,then(67)ν≤T.
From equation (54), we now have(68)uk−uk−1≤2w.
By using equations (53) and (54), we obtain the following:(69)∑k=0∞uk+1−uk2≤4∑k=0∞w2≤4T2∑k=0∞1dk2<∞,which completes the proof.
The following property, which is referred to as Property1, was presented by Gilbert and Nocedal in [10].Property 1.
Consider a method of the form of (2) and (3). Assume that (54) is satisfied for all k≥1. Then, the CG method has Property 1 if there exist constants b>1 and λ>0 such that, for all k≥1, ηk≤b and if sk≤λ, we obtain ηk≤1/2b.Lemma 3.
Consider the CG method of the form of (1) and (2) with ηk+, where the step size satisfies SWP line search of (4) and (5). If equation (54) holds, then ηk+ possesses Property∗. Namely, suppose that (54) holds; then there exist b>1 and λ>0 such that, for all k≥1, we have ηk+≤b and if sk≤λ, we obtain ηk+≤1/2b.Proof.
As a result, setb=2L+tγ¯B/1−σγ2≥1 and λ=1−σcγ2/2bL+tγ¯.
Using SWP of (4) and (5) with equation (54), we obtain(70)ηk+≤gkTyk−1dk−1Tyk−1+tgkTsk−1dk−1Tyk−1≤Lgksk−1+tgksk−11−σγ2≤2L+tγ¯B1−σγ2=b>1.
Also, ifsk≤λ, we obtain(71)ηk+≤gkTyk−1dk−1Tyk−1+tgkTsk−1dk−1Tyk−1≤Lgksk−1+tgksk−11−σγ2≤L+tγ¯λ1−σγ2,where(72)ηk+≤12b.
By using Lemma 4.1 and Lemma 4.2 in [10], we obtain the following result.Theorem 4.
Let the sequencesxk and dk be generated by (2) and (3) with the CG method in equation (28), where the step size satisfies (4) and (5). Then, we obtain the results by using Lemmas 2 and 3, as well as Lemmas 4.1 and 4.2 in [10], where liminfk⟶∞gk=0.


## 4. Numerical Results and Discussion

To test the new search direction (28), we selected some test functions in Table 1 from CUTEr [37]. A comparison with other popular and strong CG coefficients is employed. The comparison includes the CG-Descent 6.8 and DL + CG formula based on the CPU time, number of iterations, number of function evaluations, and t number of gradient evaluations. We use the SWP line search to obtain the step length with δ=0.01 and σ=0.1 for all algorithms except CG-Descent 6.8. We use approximate WWP line search as mentioned by the authors. The results of FTCGHS and DL + CG methods are obtained by running the modified code of CG-Descent; the code can be obtained from the Hager web page: https://people.clas.ufl.edu/hager/software/.Table 1
The set of test functions with the numerical results.
FunctionDimFTCGHSCG-DescentDL+No. Iter.No. Fun.EvNo. Grad.EvCPU timeNo. IterNo. Fun.EvNo. Grad.EvCPU timeNo. Iter.No. Fun.EvNo. Grad.EvCPU timeAKIVA2820150.021021110.02820150.02ALLINITU4925180.021229180.02925180.03ARGLINC200298980.08111061100.02579780.06ARWHEAD5000726220.0371580.02616120.02BARD31232220.021633170.021232220.02BDEXP50002770.0251160.022770.02BEALE21133260.021531160.021133260.02BIGGS36792071440.021102311250.02792071440.02BIGGS56792071440.021102311250.02792071440.02BIGGS662464440.022757310.022464440.02BIGGSB150002500250749952.412500250749952.47832883351665110.86BOX231023140.021124130.021023140.02BOX331023140.021124130.021023140.02BOX10000724200.08825190.08725210.09BRKMCC251160.0251160.0251160.02BROWNAL200819120.02925180.021029210.02BROWNDEN41638310.021631190.021638310.02BROYDN7D500054100760.261411281014295.22751381120.36BRYBND50003286620.1585174900.281493171740.55CAMEL62622180.021334220.02622180.02CHNROSNB502995903430.022875642990.021009199811800.01CLIFF21046390.021870540.021046390.01COSINE100001256500.191139320.191252430.2CUBE21748340.023277470.021748340.02CURLY1010000499157057679203175.06478086729476156171.256808788635105434240.64CURLY2010000672759027311160369.846658789245110540377.888068112535142271540.5CURLY3010000737089801412327451479030102516134682635.3693324121387183418712.27DENSCHNA2616120.02919100.02616120.02DENSCHNB2618150.0271580.02618150.02DENSCHNC21136310.021226140.021136310.02DENSCHND31446400.024798510.021446400.02DENSCHNE31243380.021849320.021243380.02DIXMAANA3000819130.0271580.02615110.02DIXMAANB3000191111100.0561370.02615110.02DIXMAAND3000261531480.0871580.02717120.02DIXMAANE30002542864810.282222394290.233944287640.5DIXMAANH30001623341770.141733471740.23326713430.45DIXMAANI30002811289355483.633856392676444.093522362369534.66DIXMAANJ30003156343210.343276553280.254769574860.56DIXMAANK30002755552820.282835672840.224258544320.49DIXON3DQ1000010000100071999520.310000100071999519.4815258152653051137.63DJTL275116311480.02829178800.0275116311480.02DQDRTIC500051160.0251160.021532180.02ECKERLE4LS.SIF32640.023740.022640.02EGGCRATE2615100.02615100.02615100.02EIGENALS2550101971843912170172.55100831802012244172.6795341845018540185.64EIGENBLS2550190303807119044311.06153013060315302225.23225404534024700350.43EIGENCLS265299581837011529179.77101361929211118167.52134502674018450203.45ELATVIDU2832290.021125150.02832290.02ENGVAL150002453460.082750360.062148370.06ENGVAL232673550.022661370.022673550.02ENSOLS92247270.022345260.022247270.02EXTROSNB10002274902800.023808775939821.05718212662106802.39exp2271690.0281790.0271690.02FBRAINLS2927210.031023140.02927210.02FBRAIN2LS4792592040.471183392480.66792592040.47FLETCBV250001110.021110.021110.02FLETCHCR10002274462540.021522901760.051994122170.08GENHUMPS500081071060.37647512964649319.894938147631018025.27GROWTHLS31094313690.021564563190.021094313690.02GULF33395720.023784480.023395720.02HAHN1LS7556530.0237121860.02556530.02HAIRY21782680.023699650.021782680.02HATFLDD31749370.022043241749370.02HATFLDE31337300.023072450.021337300.02HATFLDFL32168540.023992550.022168540.02HEART6LS637511378760.0268415769410.0237511378760.02HIELOW31330210.031430160.021330210.05HILBERTA22530.022530.022530.02HILBERTB104950.024950.024950.02HIMMELBB2418180.021028210.02418180.02HIMMELBG2722170.02820130.02722170.02HIMMELBH251390.0271690.0251390.02HYDCAR6LS.SIF291202421230.021440129028148750.451001202711740.03INDEF50001461470.391461470.441461470.42INTEQNELS.SIF1271580.0261370.0261370.02JIMACK35498332166668334121283141662983151169.41197823971122351732.94JUDGE2924180.021023130.02924180.02KOWOSB41646320.021739230.021646320.02KSSLS1000215150.561025160.58619160.55LANCZOS1LS6611771350.021483251810.02611771350.02LANCZOS2LS6601691250.021693792150.02601691250.02LANCZOS3LS6611641180.021793922190.02611641180.02LIARWHD50001136310.052145250.061541310.03LSC1LS331108890.0236101710.0231108890.02LSC2LS337106860.0254119670.0237106860.02LUKSAN11LS100957195710070.0395519129570.032434535530480.13LUKSAN12LS9844130980.021603022330.022525294070.01LUKSAN13LS98901821680.02841581210.021422792430.02MANCINO1001229180.091123120.061123120.06MARATOSB2589288525850.021145365727790.02589288525850.02MEXHAT21459550.022056390.021459550.02MEYER331976630.021967520.021976630.02MGH09LS42582720.0257137860.022582720.02MGH10LS31082405249680.031134446453570.031082405249680.02MGH10SLS3191121020.031465054010.03191121020.02MGH17LS5843232650.032285643630.02843233650.02MISRA1BLS.SIF2261131010.03351391170.02261131010.02MODBEALE.SIF200002334812544.35171157101013.172244733044.89MOREBV50001611683170.311611683170.421171242290.23MSQRTALS10242795559928068.22905581529118.89895317316958128.81NCB20501058813148017.028791511146311.38110262050515341129.2NONDIA5000717110.01725200.03725190.03NONDQUAR5000692612270.161942388819472.32349478724882.83PALMER1C81227280.021126260.021227280.02PALMER1D71024230.021125250.021024230.02PALMER2C81121220.021121210.021121220.02PALMER3C81121210.021120200.021121210.02PALMER4C81121210.021120200.021121210.02PALMER5C661370.0261370.0261370.02PALMER6C81124240.021124240.021124240.02PALMER7C81120200.021120200.021120200.02PALMER8C81119170.021118170.021119190.02PARKCH15672138511280.02672138511280.0241298261116.02PENALTY11000228280.022869440.021451430.02PENALTY22001912253690.021912213540.033374807580.06PENALTY3200511481100.84992852191.741023462902.19POWELLBSLS2502112340.02612472460.02502112340.02POWER100003557243760.593727543840.583567333910.58POWERSUM441060.5951160.0241060.02QING10067134850.0368135840.0285179960.02RAT43LS.SIF4441561220.0254145970.02441561220.02RECIPELS.SIF31649380.022758320.021649380.02ROSENBR22884650.023477440.022884650.02S3082721170.02819120.02721170.02SCHMVETT50003869520.174373600.0259103880.28SENSORS1002568470.382150340.022471530.47SINQUAD50001443340.081440330.081346380.09SISSER2519190.08618140.02519190.02SROSENBR5000925191.141123120.02923150.02STRATEC101704192836.334621043796191704192836.3STRTCHDV.SIF101238320.021635200.021238320.02TESTQUAD50001580158731551.521577158431491.2820325203614067421.61TOINTGOR501182161540.021352331740.021923482700.02TOINTGSS500041070.024950.024950.02TOINTQOR502936530.022936530.024956930.02TRIDIA500078078715551.03782788915590.894699472194086.38TRIGON1.SIF101941220.022245230.021941220.02VANDANMSLS.SIF22825180.0251270.0251160.02VARDIM2001440.021021110.02920150.02VAREIGVL502760370.022347210.022871510.02VESUVIALS81262195431550.021519231741111.561262195431551.22VESUVIOULS8792111730.02801801310.06792111730.09VIBRBEAM8982551740.021383231990.02982551740.02YATP1CLS1E + 051441315.762353316.131748367.12YATP2CLS1E + 05729242.78823172.09727222.67YFITU3682081670.02841971180.02682081670.03ZANGWIL221320.021320.021320.02The norm of the gradient was employed as the stopping criterion, specificallygk≤10−6 for all algorithms. The host computer is AMD A4-7210 APU Radeon R3 Graphics, where the installed memory is 4 GB with operating system Ubuntu 20.04.2.0 LTS. The results are shown in Figures 2–5, in which a performance measure introduced by Dolan and More [38] was employed. In Table 1, the following notations are used:No. Iter indicates number of iterationsNo. Fun.Ev indicates number of function evaluationsNo. Grad.Ev indicates number of gradient evaluationsFigure 2
Performance measure based on the number of iterations.Figure 3
Performance measure based on the function evaluation.Figure 4
Performance measure based on the CPU time.Figure 5
Performance measure based on the gradient evaluation.Figure2 shows that FTCGHS strongly outperformed all methods in the number of iterations. Meanwhile, Figure 3 presents the number of function evaluations, and we can note that the FTCGHS method also strongly outperforms CG-Descent 6.8 and DL+ methods. From Figures 4 and 5, we can note that FTCGHS method slightly outperforms CG-Descent and DL+, since we use SWP line search. However, let the SWP line search in equation (5) be extended as follows:(73)σ1gkTdk≤gxk+αkdkTdk≤σ2gkTdk,0<δ<σ1≤σ2<1.Then, the results in Figures4 and 5 will be more efficient. For more about equation (73), the reader can refer to [39].In addition, we present an example for two-dimensional three-hump camel back function, which is given by the following formula:(74)fx=2x12−1.05x14+x166−x1x2+x22.Here, we have the following:Number of variables (n): 2Initial points: (1, 1), (5, 5), (10, 10), and (15, 15)This function has three local minima, one of which is global. Therefore, this function is a multimodal function usually used to test global minima. The global minimum isx∗=0,0 and the function value is fx∗=0. This function looks like the back of an upside-down camel. See Figure 6 for the three-dimensional graph.Figure 6
Three-hump camel back function in 3D.


## 5. Conclusions

In this paper, we proposed a new four-term CG method as presented in equation (28) by using the following direction:(75)gk,dk−1,yk−1,sk−1.The search direction inherits the following properties:(1)
It presents four-term CG method(2)
It satisfies the sufficient descent condition(3)
The convergence analyses for convex and nonconvex functions are obtained(4)
The numerical results show that the new modification outperforms popular methods such as CG-Descent and DL+ methods(5)
The new search direction can be developed by using different values oftIn addition, we will attempt to extend the SWP line search in the future by different values of sigma to reduce the number of gradient evolutions and CPU time.



---

*Source: 6219062-2021-08-16.xml*