# Nonlinear Conjugate Gradient Coefficients with Exact and Strong Wolfe Line Searches Techniques

Authors: Awad Abdelrahman; Mogtaba Mohammed; Osman O. O. Yousif; Murtada K. Elbashir
Journal: Journal of Mathematics
 (2022)

---

## Abstract

Nonlinear conjugate gradient (CG) methods are very important for solving unconstrained optimization problems. These methods have been subjected to extensive researches in terms of enhancing them. Exact and strong Wolfe line search techniques are usually used in practice for the analysis and implementation of conjugate gradient methods. For better results, several studies have been carried out to modify classical CG methods. The method of Fletcher and Reeves (FR) is one of the most well-known CG methods. It has strong convergence properties, but it gives poor numerical results in practice. The main goal of this paper is to enhance this method in terms of numerical performance via a convexity type of modification on its coefficientβk. We ensure that with this modification, the method is still achieving the sufficient descent condition and global convergence via both exact and strong Wolfe line searches. The numerical results show that this modified FR is more robust and effective.


---

## Body

## 1. Introduction

An unconstrained optimization problem is solved using the nonlinear conjugate gradient method to obtain the minimal value of a given function. The CG technique is usually expressed as follows:(1)minx∈Rnfx,such that f:Rn⟶R, f∈C1R, and gx are given function denoting its gradient. To apply CG methods in solving (1), we start with an initial point x1∈Rn and use the iterative form
(2)xk+1=xk+αkdk,k=1,2,3,⋯,such that xk is the current iterative point, αk>0 is a step-size determined by some line searches, and dk is the search direction defined by
(3)dk=−gk,ifk=0,−gk+βkdk−1,ifk≥1,where gk=∇fxk and βk are scalar.Different choices of the scalarβk relate to different conjugate gradient algorithms. Over the years, several versions of this approach have been presented, some of which are now extensively utilized. βk has at least six well-known formulas, which are listed below (Dai and Yaxiang [1], Conjugate descent [2], Fletcher and Colin [3], Liu and Storey [4], Hestenes and Stiefel [5], and Polak and Ribiere-Polyak [6]):
(4)βkHS=gkTgk−gk−1gk−gk−1Tdk−1,(5)βkFR=gkTgkgk−1Tgk−1,(6)βkPRP=gkTgk−gk−1gk−1Tgk−1,(7)βkCD=−gkTgkdk−1Tgk−1,(8)βkLS=−gkTgk−gk−1dk−1Tgk−1,(9)βkDY=gkTgkgk−gk−1Tdk−1.Many authors have examined the behavior of global convergence for theβk’s formulas with several line search for several years (see, for example, [1–4, 7–18]). When the objective function is a strongly convex quadratic and the line search is exact, these methods are identical, since the gradients are mutually orthogonal, and the scalars βk in these methods are equal. When applied for general nonlinear functions with inexact line searches, the behavior of these methods is clearly distinct (see [11, 17, 19–21]). One of the most important properties of the CG methods is global convergence. Zoutendijk [22] proved the global convergence of the FR method via the exact line search. Although FR, DY, and CD methods have strong convergence properties, they may not perform well in practice [14]. The CD and DY methods were proved to have a global convergence under strong Wolfe line search [3, 15]. Moreover, under the exact and strong Wolfe line searches, up to our knowledge, the global convergence and sufficient descent property of some CG methods such as the PRP and the HS have not been established [2, 14]. Andrei [9] classified the CG into groups, these are scaled CG method, classical CG method, and hybrid and parameterized CG methods.Formulas (4) to (9) are in the classical group. One of the most important among them is the FR method, in which when a bad direction and a little step from xk−1 to xk are generated, the next search direction and the next step sk=xk−xk−1=αk−1dk−1 will be delayed unless a rest along the gradient direction is performed. Despite this defect, it is well known that the FR method is globally convergent for general nonlinear functions with exact or inexact line search [18].Al-Baali [7] proved the global convergence of the FR method if the strong Wolfe line search is used and the parameter σ is restricted in 0,1/2. Also, Liu and Li [17] extended Al-Baali’s result to the case that σ=1/2. Moreover, Gilbert and Jorge [14] investigated global convergence properties of the dependent FR conjugate gradient method with βk satisfying βk≤βkFR, provided that the line search satisfies the strong Wolfe line search. If βk satisfies βk≤cβkFR (where c>1), they have given an example to indicate that even exact line search cannot guarantee the global convergence property of the dependent FR conjugate gradient method. Nosratipour and Keyvan [23] proved that the dependent FR conjugate gradient method is globally convergent with the strong Wolfe line search if βk satisfies
(10)σβkβkFR≤σ¯,gk2∑j=1k∏i=jk−1li≤ck,where 0<σ<1, 0<σ¯<1/2, li=βi/βiFR, and c>0.Zhang and Donghui [24] proposed a modified FR method (called MFR) in which the direction dk is defined by
(11)dk=−gk,k=0,−dk−1yk−1gk−12gk+βkFRdk−1,k>0,which is a descent direction independent of the line search.Competitive numerical and global convergence results are obtained by newly introduced or modified techniques; see for instance [10] and the references therein.This paper is organized as follows: Section2 is devoted obtain the modification and introduce the algorithm for the modified FR method. In Section 3, we have determined sufficient descent and global convergence properties under exact and strong Wolfe line searches. Section 4 provides preliminary numerical results and considerations. Section 5 shows the conclusions.


## 2. Motivation and Properties

Several authors have attempted to modify classical CG methods such as FR, PRP, HS, and LS in order to produce new modifications with sufficient descent and global convergence properties. In addition to that, the new modifications are expected to have an efficient numerical performance. It is well known that the FR method has poor numerical performance but has strong convergence properties. The main aim from this paper is to overcome this flaw, using the following modification to the FR formula:(12)βkNMFR=gk21−θdk−12+θgk−12,where 0<θ<1,θ is a scalar parameter, which is to be determined later. Note that if θ=1, then βkNMFR=βkFR and if θ=0, then βkNMFR=gk2/dk−12. On the other hand, if 0<θ<1, then βkNMFR is the modification of βkFR, where . means the norm in R. (12) satisfies the following inequalities:
(13)βkNMFR≤gk2θgk−12.Algorithm 1.
Step 1. Initialization. Givenx0∈Rn, d0=−g0, ε>0 is tolerance, k=0, when g0=0 stop.
Step 2. Evaluateβk according to (12).
Step 3. Evaluatedk according to (3); if gk≤ε, then stop; otherwise, go to the next step.
Step 4. Evaluate anαk>0 using exact line search, i.e., αk that satisfies
(14)fxk+αkdk=minα≥0fxk+αdk,
and inexact line searches, i.e.,αk that satisfies
(15)fxk+αkdk≤fxk+δαkgkTdk,(16)gxk+αkdkTdk≤−σgkTdk,where 0<δ<σ<1.
Step 5. Renew the point according to (2), if gk≤ε, then stop
Step 6. Setk=k+1, and go to step 2.The ideal method to choose the step length is via exact line search. But since it is too expensive to choose it via exact line search in practice, some approximation methods called inexact line search such as strong Wolfe are used to define the step length that give suitable reductions in the objective function with minimal cost. However, the convergence properties of some CG methods such as FR, RMIL, and RMIL+ have been established under exact line search (see [3, 6, 25]).


## 3. Convergent Analysis

In this section, we will examine the convergence properties ofβkNMFR. The main feature of Algorithm 1 is achieving sufficient descent conditions and global convergence properties according exact and strong Wolfe line searches.


### 3.1. Convergent Analysis via the Exact Line Search

In this subsection, we show that our modification (12) will possess sufficient descent condition and global convergence properties according to the exact line search.Theorem 1.
Assume that (2) and (3) be generated by Algorithm 1 and αk be determined by the exact line search (14), where βk=βkNMFR is given as (12); there exists c>0, such that
(17)gkTdk≤−cgk2∀k≥0.
The proof of this Theorem1 is obvious, from (3), and multiply by gk+1; then,
(18)gk+1Tdk+1=gk+1T−gk+1+βk+1dk=−gk+12+βk+1gk+1Tdk.When gk+1Tdk=0, then (17) holds true for all k≥1 and becomes
(19)gkTdk=−gk2.


#### 3.1.1. Global Convergence Properties

In this subsection, we show that our modified (12) coefficient satisfies global convergence according to the exact line search.Assumption 2.
(i)
There exists some positive constantc such that c≥fx for all x∈Rn and f∈C1N for some neighborhood N of Γ=x∈Rnfx≤fx0. Also, assume that there exists a positive constant C0 such that(20)x−y≤C0,foranyx,y∈N(ii)
There exists positive constantC_1(21)gx−gy≤C1x−y,forallx,yϵN
From the above assumption, we can easily see that(22)gx≤C2foranyx∈ΓandsomepositiveconstantC2.The following lemma will be used in our analysis (see Zoutendijk [22]).Lemma 3.
Assume that Assumption2 holds, for any conjugate gradient method as in (2), such that dk is a descent search direction and αk satisfies the exact line search. Then,
(23)∑k=1∞gk4dk2<∞.Theorem 4.
Assume that Assumption2 holds, for conjugate gradient method as in (2) and (3) such that αk is achieved via exact line search. Furthermore, assume that the sufficient descent condition is satisfied. Then,
(24)limk⟶∞gk=0,or∑k=1∞gk4dk2<∞.Proof.
The proof will be conducted by contradiction argument. So, assume that the statement of Theorem4 is false. Thus, there exists some positive constant c, where
(25)gk≥c.
We rewrite (3) as
(26)dk+1+gk+1=βk+1dk.
Taking the square on both sides of above equation, we get(27)dk+12=−gk+12−2gk+1Tdk+1+βk+12dk2.
Dividing both sides of (27) by gk+14, we obtain
(28)dk+12gk+14=−1gk+12−2gk+1Tdk+1gk+14+βk+12dk2gk+14.From (19) and (13), we obtain
(29)dk+12gk+14=−1gk+12+βk+12dk2gk+14≤dk2θ2gk4,(30)dk+12gk+14≤dk2θ2gk4.
Recursively using (29) and noticing that d12=−g1Td1=g12, we get
(31)dk+12gk+14≤1θ2∑i=0k+11gi2.
Hence,(32)dk+12gk+14≤kθ2c2,(33)gk+14dk+12≥θ2c2k.
As a result of (32) and (25), it is clear that
(34)∑k=0∞gk+14dk+12=∞,which contradicts Lemma 3’s Zoutendijk condition; hence, the proof is completed.


### 3.2. Convergent Analysis according to Strong Wolf Line Searches

In this subsection, we show that our modified (12) coefficient satisfies sufficient descent condition and global convergence according to strong Wolfe line search (15) and (16).


#### 3.2.1. Sufficient Descent Condition

Theorem 5.
Let Assumption1 hold true, for σ<1/2 and θ=0.3. Then, Algorithm 1 assures the sufficient descent condition (17) such that
(35)c=2−θθ−σ.Proof.
Multiplying (3) by gk+1 and (13) and taking the absolute value of the second term in (36), we obtain
(36)gk+1Tdk+1=−gk+12+βk+1gk+1Tdk≤−gk+12+gk+12θgk2gk+1Tdk.From (16) and the Cauchy-Schwartz inequality, we get
(37)gk+1Tdk+1≤−gk+12+gk+12θgk2gk+1Tdk≤−gk+12+gk+12θgk2−σgkTdk≤−gk+12+gk+12θgk2−σgkTdk,gk+1Tdk+1≤−gk+12+σgk+12θgk2gkdk=−gk+12+σθgk+12dkgk.Dividing both sides in the above inequality by gk+12, we obtain
(38)gk+1Tdk+1gk+12≤−1+σθdkgk.
By repeating this process and the fact thatd1=g1, we get
(39)gk+1Tdk+1gk+12≤−1+σθdkgk,(40)gk+1Tdk+1gk+12≤−2+∑i=0∞σθi=−2+11−σ/θ=−2+θθ−σ,(41)gk+1Tdk+1gk+12≤−c.
Therefore, from (39), we can deduce that (17) holds for k≥0. The proof is completed.


#### 3.2.2. Global Convergence

This subsection is devoted to the global convergence in the case of inexact line search technique. The following lemma is collected from [22].Lemma 6.
Let Assumption1 and let any conjugate gradient method be in the form (2), where the descent direction is dk+1 and αk satisfies the strong Wolfe line search (15) and (16).
(42)∑k=1∞gk4dk2<∞.Theorem 7.
Let Assumption2 hold. Then, Algorithm 1 is convergent, that is,
(43)limk⟶∞gk=0,or∑k=1∞gk4dk2<∞.Proof.
The proof will be conducted by contradiction argument. So, assume that the statement of Theorem7 is not true; then, there exists a constant ϵ>0, such that
(44)gk≥ϵ.
Equation (3) can be written as
(45)dk+1=−gk+1+βk+1dk,and multiplying (45) on both sides by dk+1, we obtain
(46)dk+12=−gk+1Tdk+1+βk+1dk+1Tdk.
Dividing both sides of (46) by gk+14 with the help of (13), we get
(47)dk+12gk+14≤−gk+1Tdk+1gk+14+gk+12θgk2dk+1Tdkgk+14≤−gk+1Tdk+1gk+14+gk+12θgk2dk+1Tdkgk+14.
From Cauchy-Schwartz inequality, we get(48)dk+12gk+14≤gk+1dk+1gk+14+dkθgk2dk+1gk+12,≤gk+1dk+1gk+14−12dkθgk2−dk+1gk+122+12dk2θ2gk4+12dk+12gk+14,≤gk+1dk+1gk+14+12dk2θ2gk4+12dk+12gk+14.
So we come to(49)dk+12gk+1412−gk+1dk+1≤12dk2θ2gk4.
Referring to (39), using Cauchy-Schwartz inequality, we get
(50)cgk+12≤−gk+1Tdk+1≤gk+1dk+1.Then,
(51)gk+1dk+1≤1c.
Substituting (51) into (49), we get
(52)dk+12gk+14≤12dk2γθ2gk4,
whereγ=1/2−1/c.
Recursively using (52) and noticing that d12=g12, we have
(53)dk+12gk+14≤121γθ2∑i=0k1gi2,(54)dk+12gk+14≤121γθ2kϵ2=k2ϵ2θ2γ,(55)gk+14dk+12≥2γθ2ϵ2k.
As a result of (53) and (44), it can be concluded that
(56)∑k=0∞gk+14dk+12=∞,which contradicts (43); hence, the proof is completed.


## 3.1. Convergent Analysis via the Exact Line Search

In this subsection, we show that our modification (12) will possess sufficient descent condition and global convergence properties according to the exact line search.Theorem 1.
Assume that (2) and (3) be generated by Algorithm 1 and αk be determined by the exact line search (14), where βk=βkNMFR is given as (12); there exists c>0, such that
(17)gkTdk≤−cgk2∀k≥0.
The proof of this Theorem1 is obvious, from (3), and multiply by gk+1; then,
(18)gk+1Tdk+1=gk+1T−gk+1+βk+1dk=−gk+12+βk+1gk+1Tdk.When gk+1Tdk=0, then (17) holds true for all k≥1 and becomes
(19)gkTdk=−gk2.


### 3.1.1. Global Convergence Properties

In this subsection, we show that our modified (12) coefficient satisfies global convergence according to the exact line search.Assumption 2.
(i)
There exists some positive constantc such that c≥fx for all x∈Rn and f∈C1N for some neighborhood N of Γ=x∈Rnfx≤fx0. Also, assume that there exists a positive constant C0 such that(20)x−y≤C0,foranyx,y∈N(ii)
There exists positive constantC_1(21)gx−gy≤C1x−y,forallx,yϵN
From the above assumption, we can easily see that(22)gx≤C2foranyx∈ΓandsomepositiveconstantC2.The following lemma will be used in our analysis (see Zoutendijk [22]).Lemma 3.
Assume that Assumption2 holds, for any conjugate gradient method as in (2), such that dk is a descent search direction and αk satisfies the exact line search. Then,
(23)∑k=1∞gk4dk2<∞.Theorem 4.
Assume that Assumption2 holds, for conjugate gradient method as in (2) and (3) such that αk is achieved via exact line search. Furthermore, assume that the sufficient descent condition is satisfied. Then,
(24)limk⟶∞gk=0,or∑k=1∞gk4dk2<∞.Proof.
The proof will be conducted by contradiction argument. So, assume that the statement of Theorem4 is false. Thus, there exists some positive constant c, where
(25)gk≥c.
We rewrite (3) as
(26)dk+1+gk+1=βk+1dk.
Taking the square on both sides of above equation, we get(27)dk+12=−gk+12−2gk+1Tdk+1+βk+12dk2.
Dividing both sides of (27) by gk+14, we obtain
(28)dk+12gk+14=−1gk+12−2gk+1Tdk+1gk+14+βk+12dk2gk+14.From (19) and (13), we obtain
(29)dk+12gk+14=−1gk+12+βk+12dk2gk+14≤dk2θ2gk4,(30)dk+12gk+14≤dk2θ2gk4.
Recursively using (29) and noticing that d12=−g1Td1=g12, we get
(31)dk+12gk+14≤1θ2∑i=0k+11gi2.
Hence,(32)dk+12gk+14≤kθ2c2,(33)gk+14dk+12≥θ2c2k.
As a result of (32) and (25), it is clear that
(34)∑k=0∞gk+14dk+12=∞,which contradicts Lemma 3’s Zoutendijk condition; hence, the proof is completed.


## 3.1.1. Global Convergence Properties

In this subsection, we show that our modified (12) coefficient satisfies global convergence according to the exact line search.Assumption 2.
(i)
There exists some positive constantc such that c≥fx for all x∈Rn and f∈C1N for some neighborhood N of Γ=x∈Rnfx≤fx0. Also, assume that there exists a positive constant C0 such that(20)x−y≤C0,foranyx,y∈N(ii)
There exists positive constantC_1(21)gx−gy≤C1x−y,forallx,yϵN
From the above assumption, we can easily see that(22)gx≤C2foranyx∈ΓandsomepositiveconstantC2.The following lemma will be used in our analysis (see Zoutendijk [22]).Lemma 3.
Assume that Assumption2 holds, for any conjugate gradient method as in (2), such that dk is a descent search direction and αk satisfies the exact line search. Then,
(23)∑k=1∞gk4dk2<∞.Theorem 4.
Assume that Assumption2 holds, for conjugate gradient method as in (2) and (3) such that αk is achieved via exact line search. Furthermore, assume that the sufficient descent condition is satisfied. Then,
(24)limk⟶∞gk=0,or∑k=1∞gk4dk2<∞.Proof.
The proof will be conducted by contradiction argument. So, assume that the statement of Theorem4 is false. Thus, there exists some positive constant c, where
(25)gk≥c.
We rewrite (3) as
(26)dk+1+gk+1=βk+1dk.
Taking the square on both sides of above equation, we get(27)dk+12=−gk+12−2gk+1Tdk+1+βk+12dk2.
Dividing both sides of (27) by gk+14, we obtain
(28)dk+12gk+14=−1gk+12−2gk+1Tdk+1gk+14+βk+12dk2gk+14.From (19) and (13), we obtain
(29)dk+12gk+14=−1gk+12+βk+12dk2gk+14≤dk2θ2gk4,(30)dk+12gk+14≤dk2θ2gk4.
Recursively using (29) and noticing that d12=−g1Td1=g12, we get
(31)dk+12gk+14≤1θ2∑i=0k+11gi2.
Hence,(32)dk+12gk+14≤kθ2c2,(33)gk+14dk+12≥θ2c2k.
As a result of (32) and (25), it is clear that
(34)∑k=0∞gk+14dk+12=∞,which contradicts Lemma 3’s Zoutendijk condition; hence, the proof is completed.


## 3.2. Convergent Analysis according to Strong Wolf Line Searches

In this subsection, we show that our modified (12) coefficient satisfies sufficient descent condition and global convergence according to strong Wolfe line search (15) and (16).


### 3.2.1. Sufficient Descent Condition

Theorem 5.
Let Assumption1 hold true, for σ<1/2 and θ=0.3. Then, Algorithm 1 assures the sufficient descent condition (17) such that
(35)c=2−θθ−σ.Proof.
Multiplying (3) by gk+1 and (13) and taking the absolute value of the second term in (36), we obtain
(36)gk+1Tdk+1=−gk+12+βk+1gk+1Tdk≤−gk+12+gk+12θgk2gk+1Tdk.From (16) and the Cauchy-Schwartz inequality, we get
(37)gk+1Tdk+1≤−gk+12+gk+12θgk2gk+1Tdk≤−gk+12+gk+12θgk2−σgkTdk≤−gk+12+gk+12θgk2−σgkTdk,gk+1Tdk+1≤−gk+12+σgk+12θgk2gkdk=−gk+12+σθgk+12dkgk.Dividing both sides in the above inequality by gk+12, we obtain
(38)gk+1Tdk+1gk+12≤−1+σθdkgk.
By repeating this process and the fact thatd1=g1, we get
(39)gk+1Tdk+1gk+12≤−1+σθdkgk,(40)gk+1Tdk+1gk+12≤−2+∑i=0∞σθi=−2+11−σ/θ=−2+θθ−σ,(41)gk+1Tdk+1gk+12≤−c.
Therefore, from (39), we can deduce that (17) holds for k≥0. The proof is completed.


### 3.2.2. Global Convergence

This subsection is devoted to the global convergence in the case of inexact line search technique. The following lemma is collected from [22].Lemma 6.
Let Assumption1 and let any conjugate gradient method be in the form (2), where the descent direction is dk+1 and αk satisfies the strong Wolfe line search (15) and (16).
(42)∑k=1∞gk4dk2<∞.Theorem 7.
Let Assumption2 hold. Then, Algorithm 1 is convergent, that is,
(43)limk⟶∞gk=0,or∑k=1∞gk4dk2<∞.Proof.
The proof will be conducted by contradiction argument. So, assume that the statement of Theorem7 is not true; then, there exists a constant ϵ>0, such that
(44)gk≥ϵ.
Equation (3) can be written as
(45)dk+1=−gk+1+βk+1dk,and multiplying (45) on both sides by dk+1, we obtain
(46)dk+12=−gk+1Tdk+1+βk+1dk+1Tdk.
Dividing both sides of (46) by gk+14 with the help of (13), we get
(47)dk+12gk+14≤−gk+1Tdk+1gk+14+gk+12θgk2dk+1Tdkgk+14≤−gk+1Tdk+1gk+14+gk+12θgk2dk+1Tdkgk+14.
From Cauchy-Schwartz inequality, we get(48)dk+12gk+14≤gk+1dk+1gk+14+dkθgk2dk+1gk+12,≤gk+1dk+1gk+14−12dkθgk2−dk+1gk+122+12dk2θ2gk4+12dk+12gk+14,≤gk+1dk+1gk+14+12dk2θ2gk4+12dk+12gk+14.
So we come to(49)dk+12gk+1412−gk+1dk+1≤12dk2θ2gk4.
Referring to (39), using Cauchy-Schwartz inequality, we get
(50)cgk+12≤−gk+1Tdk+1≤gk+1dk+1.Then,
(51)gk+1dk+1≤1c.
Substituting (51) into (49), we get
(52)dk+12gk+14≤12dk2γθ2gk4,
whereγ=1/2−1/c.
Recursively using (52) and noticing that d12=g12, we have
(53)dk+12gk+14≤121γθ2∑i=0k1gi2,(54)dk+12gk+14≤121γθ2kϵ2=k2ϵ2θ2γ,(55)gk+14dk+12≥2γθ2ϵ2k.
As a result of (53) and (44), it can be concluded that
(56)∑k=0∞gk+14dk+12=∞,which contradicts (43); hence, the proof is completed.


## 3.2.1. Sufficient Descent Condition

Theorem 5.
Let Assumption1 hold true, for σ<1/2 and θ=0.3. Then, Algorithm 1 assures the sufficient descent condition (17) such that
(35)c=2−θθ−σ.Proof.
Multiplying (3) by gk+1 and (13) and taking the absolute value of the second term in (36), we obtain
(36)gk+1Tdk+1=−gk+12+βk+1gk+1Tdk≤−gk+12+gk+12θgk2gk+1Tdk.From (16) and the Cauchy-Schwartz inequality, we get
(37)gk+1Tdk+1≤−gk+12+gk+12θgk2gk+1Tdk≤−gk+12+gk+12θgk2−σgkTdk≤−gk+12+gk+12θgk2−σgkTdk,gk+1Tdk+1≤−gk+12+σgk+12θgk2gkdk=−gk+12+σθgk+12dkgk.Dividing both sides in the above inequality by gk+12, we obtain
(38)gk+1Tdk+1gk+12≤−1+σθdkgk.
By repeating this process and the fact thatd1=g1, we get
(39)gk+1Tdk+1gk+12≤−1+σθdkgk,(40)gk+1Tdk+1gk+12≤−2+∑i=0∞σθi=−2+11−σ/θ=−2+θθ−σ,(41)gk+1Tdk+1gk+12≤−c.
Therefore, from (39), we can deduce that (17) holds for k≥0. The proof is completed.


## 3.2.2. Global Convergence

This subsection is devoted to the global convergence in the case of inexact line search technique. The following lemma is collected from [22].Lemma 6.
Let Assumption1 and let any conjugate gradient method be in the form (2), where the descent direction is dk+1 and αk satisfies the strong Wolfe line search (15) and (16).
(42)∑k=1∞gk4dk2<∞.Theorem 7.
Let Assumption2 hold. Then, Algorithm 1 is convergent, that is,
(43)limk⟶∞gk=0,or∑k=1∞gk4dk2<∞.Proof.
The proof will be conducted by contradiction argument. So, assume that the statement of Theorem7 is not true; then, there exists a constant ϵ>0, such that
(44)gk≥ϵ.
Equation (3) can be written as
(45)dk+1=−gk+1+βk+1dk,and multiplying (45) on both sides by dk+1, we obtain
(46)dk+12=−gk+1Tdk+1+βk+1dk+1Tdk.
Dividing both sides of (46) by gk+14 with the help of (13), we get
(47)dk+12gk+14≤−gk+1Tdk+1gk+14+gk+12θgk2dk+1Tdkgk+14≤−gk+1Tdk+1gk+14+gk+12θgk2dk+1Tdkgk+14.
From Cauchy-Schwartz inequality, we get(48)dk+12gk+14≤gk+1dk+1gk+14+dkθgk2dk+1gk+12,≤gk+1dk+1gk+14−12dkθgk2−dk+1gk+122+12dk2θ2gk4+12dk+12gk+14,≤gk+1dk+1gk+14+12dk2θ2gk4+12dk+12gk+14.
So we come to(49)dk+12gk+1412−gk+1dk+1≤12dk2θ2gk4.
Referring to (39), using Cauchy-Schwartz inequality, we get
(50)cgk+12≤−gk+1Tdk+1≤gk+1dk+1.Then,
(51)gk+1dk+1≤1c.
Substituting (51) into (49), we get
(52)dk+12gk+14≤12dk2γθ2gk4,
whereγ=1/2−1/c.
Recursively using (52) and noticing that d12=g12, we have
(53)dk+12gk+14≤121γθ2∑i=0k1gi2,(54)dk+12gk+14≤121γθ2kϵ2=k2ϵ2θ2γ,(55)gk+14dk+12≥2γθ2ϵ2k.
As a result of (53) and (44), it can be concluded that
(56)∑k=0∞gk+14dk+12=∞,which contradicts (43); hence, the proof is completed.


## 4. Numerical Results and Discussion

Most of the test problems used in this study are taken from Andrei [8], and they are used to evaluate the efficiency of the NMFR method to that of FR and PRP under exact line search and to that of FR, PRP, and CD under strong Wolfe line search. The step-size is computed using the exact and strong Wolfe line search techniques, and numerical results are compared based on the number of iterations and CPU time. For all test problems, the stopping criteria are set to be gk≤ϵ, where ϵ=10−6; for each test problem, various starting points are used, as suggested by Hillstrom [26]. All runs are performed on a PC ACER (Intel® Core™ i3-3217u CPU @ 1.8 GHZ, with 4.00 GB RAMS, Windows 7 Ultimate). Every problem mentioned in Table 1 is solved using Matlab10 subroutine programming. The performance results are shown in Figures 1–4, respectively, using a performance profile introduced by Dolan and Jorge [13].Table 1
A list of test problem functions.
No.FunctionDIMFRIN/CPUPRPIN/CPUCDIN/CPUNMFRIN/CPU1Extended White & Holst10631/4.44911/0.106341/2.47328/0.246100177/2.31220/0.292308/4.01217/0.2462Extended Rosenbrock4205/1.36830/0.226341/2.30026/0.202100204/1.62930/0.278316/2.55426/0.2423Extended Freudenstein & Roth10F/FF/F57/0.44534/0.269100117/1.114F/F42/0.44659/0.5734Extended Beale466/0.5668/0.08366/0.57127/0.243100019/1.6379/0.77619/1.64110/0.8595Raydan11052/0.46924/0.22052/0.47026/0.24710190/2.244104/1.257186/2.210131/1.5636Extended Tridiagonal110025/0.39914/0.22725/0.40642/0.656100048/3.76014/1.10448/3.76376/5.9487Diagonal410005/0.1244/0.0995/0.1225/0.118100005/0.6464/0.5255/0.6585/0.6448Extended Himmelblau100008/1.5096/1.1248/1.5018/1.488500008/7.1656/5.3718/7.1578/7.1579FLETCHCR1019/0.17919/0.17919/0.18619/0.17310024/0.26524/0.26425/0.27424/0.26010Diagonal2410/0.11812/0.13210/0.11710/0.11410148/1.41430/0.303147/1.40530/0.30011NONSCOMP234/0.3098/0.08634/0.30910/0.10441725/14.289344/2.9721726/14.316546/4.73012Extended DENSCHNB411/0.1129/0.10211/0.1179/0.09110011/0.1359/0.10911/0.13510/0.12213Extended Penalty1010/0.1187/0.09310/0.1138/0.09310029/0.357F/F49/0.56917/0.20914Hager1014/0.15513/0.14214/0.15313/0.14210099/1.38636/0.52194/1.33536/0.52115ARWHEAD46/0.0707/0.0866/0.0846/0.070107/0.0867/0.0827/0.0957/0.08216Extended Maratos428/0.26718/0.18228/0.26726/0.246100159/1.543F/F37/0.41552/0.57917Six hump24/0.0654/0.0664/0.0614/0.05618Three hump26/0.0857/0.1236/0.0847/0.08319Booth23/0.0493/0.0423/0.0513/0.03920Trecanni25/0.0685/0.0675/0.0765/0.06621Zettl216/0.1699/0.10916/0.1739/0.10922Shallow1026/0.2897/0.09226/0.3049/0.11810001216/30.11914/0.3691171/28.96918/0.47923Generalized Quartic1006/0.0926/0.0956/0.0916/0.088100006/1.2116/1.2176/1.19036/1.17724Quadratic QF210875/8.86731/0.341746/7.47635/0.382140/100401/4.48987/1.042359/3.9711.68325Leon21681/14.02643/0.399557/4.69736/0.34326Generalized Tridiagonal 11027/0.32623/0.27427/0.32123/0.274100151/2.33925/0.40326/0.42224/0.37727Generalized Tridiagonal 21042/0.47336/0.41142/0.48533/0.37828POWER1020/0.20721/0.21820/0.217131/1.29629Quadratic QF11010/0.12710/0.12510/0.11925/0.28530Extended quadratic penalty QP21000F/F41/2.460122/9.48673/3.67931Extended quadratic penalty QP1100314/3.803F/F14/0.20914/0.20732Quartic4223/2.513615/6.911223/2.510260/2.96033Colville434/0.36974/0.77534/0.366159/0.62634Dixon and Price1074/0.90642/0.53374/0.89742/0.531100F/F432/5.639F/F998/12.97835Extended Wood4F/F267/2.979F/F208/2.350Figure 1
Performance profile according to the iterations number based on exact line search.Figure 2
Performance profile based on the CPU time based on exact line search.Figure 3
Performance profile according to the iterations number based on strong Wolfe line search.Figure 4
Performance profile based on the CPU time based on strong Wolfe line search.In the list of problem functions,IN indicates the number of iterations, and CPU indicates the CPU time as shown in Table 1. F indicates that the test problem function is failing. Also, in some cases, it means that the computation came to a halt when a line search failed to locate a positive step-size, and it was deemed a failure.We offer the concept of a way of evaluating and examine the effectiveness of set solverss on a test set p using the performance profile. Assuming there are ns solvers and np problems; they characterized tp,s as the computing time (computational time, CPU time, or other factors) needed to tackle problems p by solver s. They used the performance ratio rp,s=tp,s/mintp,s:s∈S to compare solver s performance on problem p to the best performance by any solver on this problem.We letrM≥rp,s for each chosen p and s such that rp,s=rM, whenever s is not a solution of problem p. The solution for performance s of presented problems has to be reliable, and we wish to have the entire evaluation of solution for performance s. Thus, we define Pts=1/npsizep∈P:rp,s≤t, where Pts stands for the probability of solution for performance s∈S and Ps is a cumulative distribution function for rp,s. The value P1s is the probability that the solver will win over the rest of the solvers. In all, a solver with high values of Pts or at the top right of the figures is preferable or represents robust solver.Clearly from Figures1 and 2, we see that NMFR has better performance, since it solved all the test problems and reached 100% percentage. These CG coefficients could also be divided into three categories: the first category of which consists of NMFR, while the second consists of FR, and the third consists of PRP. It is easy to see that their performance is much better. Although the performance of the third category seems to be much better than NMFR, it could only solve 86% of the problems, whereas the performance of the second category only reached 89%. Hence, we considered NMFR as an efficient performance and robust method with the others because it can solve all the problems.Also, Figures3 and 4 show that the curve of NMFR is higher than that of PRP, CD, and FR. This implies that the NMFR approach outperforms the other three methods significantly. Furthermore, the NMFR approach solves all problems; meanwhile, the PRP method solves about 86 percent of problems, and the CD and FR methods solve about 89 percent. As a result, we can infer that NMFR is the preferred approach because it has the highest curve and solves all problems.


## 5. Conclusion

In this article, we have proposed a new and simple modification forβkFR that is easy to implement, known as βkNMFR . Numerical results show that βkNMFR has efficient performance compared to other standard CG methods. In contrast to βkFR, we have seen that βkNMFR shows good numerical performance at each step. We have also proved that βkNMFR converges globally based on the exact and strong Wolfe line searches.



---

*Source: 1383129-2022-11-22.xml*