# Two New Conjugate Gradient Methods for Unconstrained Optimization

Authors: Meixing Liu; Guodong Ma; Jianghua Yin
Journal: Complexity
 (2020)

---

## Abstract

The conjugate gradient method is very effective in solving large-scale unconstrained optimal problems. In this paper, on the basis of the conjugate parameter of the conjugate descent (CD) method and the second inequality in the strong Wolfe line search, two new conjugate parameters are devised. Using the strong Wolfe line search to obtain the step lengths, two modified conjugate gradient methods are proposed for general unconstrained optimization. Under the standard assumptions, the two presented methods are proved to be sufficient descent and globally convergent. Finally, preliminary numerical results are reported to show that the proposed methods are promising.


---

## Body

## 1. Introduction

The conjugate gradient method (CGM for short) plays an important role in obtaining the numerical solution of the optimal control problem for nonlinear dynamic systems and other mathematical models [1, 2]. In this paper, we study the nonlinear CGM for the following unconstrained optimization problem:(1)minfxx∈Rn,where f:Rn⟶R is smooth and its gradient gx=∇fx is available.The iterates of the classic CGMs for solving problem (1) are generated by xk+1=xk+αkdk. First, the step length αk>0 is usually yielded by a suitable inexact line search along the search direction dk, such as the Wolfe line search(2)fxk+αkdk≤fxk+δαkgkTdk,gxk+αkdkTdk≥σgkTdk,or the strong Wolfe line search(3)fxk+αkdk≤fxk+δαkgkTdk,gxk+αkdkTdk≤σgkTdk,where parameters δ and σ satisfy 0<δ<σ<1. Second, the search direction dk is computed by(4)dk=−gk,k=1,−gk+βkdk−1,k≥2,where gk=gxk and βk is the conjugate parameter. To the best of our knowledge, different choices for the scalar βk lead to different CGMs works. In particular, the well-known formulas for βk include the Hestenes–Stiefel (HS) [3], Fletcher–Reeves (FR) [4], Polak–Ribiere (PRP) [5], Conjugate Descent (CD) [6], Liu–Story (LS) [7], and Dai–Yuan (DY) [8] formulas, and they are specified as follows:(5)βkHS=gkTgk−gk−1dk−1Tgk−gk−1,βkFR=gk2gk−12,βkPRP=gkTgk−gk−1gk−12,βkCD=gk2−dk−1Tgk−1,βkLS=gkTgk−gk−1−dk−1Tgk−1,βkDY=gk2dk−1Tgk−gk−1,where ⋅ stands for the Euclidean norm. A great number of CGMs with good convergence properties and effective numerical performance are deuterogenic by the six methods above, see e.g., [9–15]. As we know, Jiang et al. [12] studied a CGM work called JMJ method, where the parameter βk is correspondingly specified by(6)βkJMJ=gkTgk−gk/dk−1dk−1dk−1Tgk−gk−1,ifgkTdk−1>0,gkTgk+gk/dk−1dk−1dk−1Tgk−gk−1,otherwise.This further can be integrated and rewritten asβkJMJ=gk2−gk/dk−1gkTdk−1/dk−1Tgk−gk−1. It is obvious that the abovementioned formula reduces to the DY formula under the exact line search. Moreover, the JMJ method keeps the descent property at each iteration and converges globally for general nonconvex functions under the Wolfe line search.In this paper, we focus our attention on the ideas of the JMJ and CD methods as well as the strong Wolfe line search. In particular, by the second inequality of the strong Wolfe line search, it follows thatgkTdk−1/−dk−1Tgk−1≤σ if dk−1Tgk−1<0. Thus, based on the formula βkJMJ, making full use of the characteristics of the JMJ and CD methods, and to ensure that our proposed methods possess nice convergent properties and to improve the numerical performance, two new formulas for βk are constructed in this paper. The first one is generated by replacing the term gk/dk−1 in βkJMJ with the CD formula βkCD, namely,(7)βkLMYCD1=gk2−βkCDgkTdk−1dk−1Tgk−gk−1.On the contrary, replacing the denominator inβkLMYCD1 with gk−12, the second one is presented with(8)βkLMYCD2=gk2−βkCDgkTdk−1gk−12.From (7) and (8), it is not difficult to know that the former formula βkLMYCD1 reduces to the DY formula when the exact line search is used, and accordingly, in the same condition, the later one βkLMYCD2 reduces to the FR formula.The rest of the paper is organized as follows. In Section2, two modified methods and the sufficient descent properties are presented. Global convergence properties of the proposed methods are analyzed in Section 3. Some numerical results are reported in Section 4. Finally, we draw a conclusion in Section 5.


## 2. Methods and Sufficient Descent Properties

In this section, we first describe the details of the two proposed methods, which for convenience are called the LMYCD1 and LMYCD2 methods in Algorithm1 and Algorithm 2, respectively.Algorithm 1: (LMYCD1 method).
Initialization. Given constants ϵ>0 and 0<δ<σ<1, as well as x1∈Rn. Let d1=−g1, k:=1.
Step 1. If gk≤ϵ, then stop. Otherwise, go to Step 2.
Step 2. Determine a step length αk by the strong Wolfe line search (3).
Step 3. Let xk+1:=xk+αkdk, compute gk+1=gxk+1 and βk+1=βk+1LMYCD1.
Step 4. Compute dk+1=−gk+1+βk+1dk. Set k:=k+1, and go back to Step 1.Algorithm 2: (LMYCD2 method).
Initialization. Given constants ϵ>0, 0<δ<σ<1/2 and x1∈Rn. Let d1=−g1, k:=1.
Step 1 and Step 2 are the same as the step 1 and step 2 of LMYCD1 method.
Step 3. Let xk+1:=xk+αkdk, compute gk+1=gxk+1 and βk+1=βk+1LMYCD2.
Step 4 is the same as the step 4 of LMYCD1 method.


### 2.1. Sufficient Descent Condition

If there exists a constantc>0 such that gkTdk≤−cgk2,∀k≥1, then, we say that the search direction dk of the method satisfies the sufficient descent condition, which is often used to analyze the convergence properties of CGMs for this kind of problem (1) under inexact line search, see e.g., [10–14].The next lemmas show that the search directions yielded by the two proposed methods always satisfy the sufficient descent condition.Lemma 1.
Suppose thatdk is generated by the LMYCD1 method and 0<σ<1. Then,(9)gkTdk≤−1σ+1gk2.Proof.
We prove (9) by induction. For k=1, it is easy to know from 0<σ<1 that g1Td1=−g12<−1/σ+1g12. Suppose that (9) is satisfied for k−1, namely, gk−1Tdk−1≤−1/σ+1gk−12,then obviously βkCD>0 holds by its definition. Furthermore, from the strong Wolfe line search, we have(10)0<−1−σgk−1Tdk−1≤dk−1Tgk−gk−1≤−1+σgk−1Tdk−1,and 0≤βkCDgkTdk−1≤βkCD−σdk−1Tgk−1=σgk2. This, together with βkLMYCD1 and relation (10), further implies that(11)0<1−σgk2dk−1Tgk−gk−1≤βkLMYCD1≤gk2dk−1Tgk−gk−1.
Now, we prove that (9) holds for k via the following three cases:(i)
IfgkTdk−1=0, then, by the definition of dk in Algorithm 1, we have(12)gkTdk=−gk2+βkLMYCD1gkTdk−1=−gk2<−1σ+1gk2.(ii)
IfgkTdk−1>0, then, similarly from definitions of dk and βkLMYCD1, taking βkCD>0, gk−1Tdk−1<0 and (10), we obtain(13)gkTdk=−gk2+βkLMYCD1gkTdk−1=−gk2+gk2−βkCDgkTdk−1dk−1Tgk−gk−1gkTdk−1=gk2gk−1Tdk−1−βkCDgkTdk−12dk−1Tgk−gk−1<gk2gk−1Tdk−1dk−1Tgk−gk−1≤gk2gk−1Tdk−1−1+σgk−1Tdk−1=−1σ+1gk2.(iii)
IfgkTdk−1<0, then, using dk and βkLMYCD1>0, we also obtain(14)gkTdk=−gk2+βkLMYCD1gkTdk−1<−gk2<−1σ+1gk2.
Therefore, the assertion is satisfied for allk≥1.Lemma 2.
Let the search directiondk be yielded by the LMYCD2 method and 0<σ<1/2. Then,(15)−11−σ≤gkTdkgk2≤−1−2σ1−σ.
Moreover, relation0<βkLMYCD2≤βkFR holds.Proof.
Fork=1, one has g1Td1/g12=−1, so (15) clearly holds. Suppose that relation (15) is satisfied for k−1. Now, we continue to prove that (15) holds for k. By the strong Wolfe line search and gk−1Tdk−1<0, it is clear that 0≤gkTdk−1≤−σgk−1Tdk−1, and hence(16)0<1−σ≤1−gkTdk−1−gk−1Tdk−1≤1.
Thus, usingβkLMYCD2, we obtain(17)0<1−σ‖gk‖2‖gk−1‖2≤βkLMYCD2=gk21−gkTdk−1/−gk−1Tdk−1gk2≤gk2gk−12=βkFR.
Furthermore, recallingdk in Algorithm 2, βkCD and βkLMYCD2, one has(18)gkTdkgk2=−1+gk2−gk2/−dk−1Tgk−1gkTdk−1gk−12gkTdk−1gk2=−1+1−gkTdk−1−dk−1Tgk−1gkTdk−1gk−12.
This together with the right-hand side of (16) further shows that(19)−1−gkTdk−1gk−12≤gkTdkgk2≤−1+gkTdk−1gk−12.
Next, based on the strong Wolfe line search, from the left-hand side of (19) and assertion (15) for k−1, we have(20)gkTdkgk2≥−1+σgk−1Tdk−1gk−12≥−1−σ1−σ=−11−σ.
Similarly, from the right-hand side of (19), we also obtain(21)gkTdkgk2≤−1−σgk−1Tdk−1gk−12≤−1+σ1−σ=−1−2σ1−σ.
Thus, the proof is completed.


## 2.1. Sufficient Descent Condition

If there exists a constantc>0 such that gkTdk≤−cgk2,∀k≥1, then, we say that the search direction dk of the method satisfies the sufficient descent condition, which is often used to analyze the convergence properties of CGMs for this kind of problem (1) under inexact line search, see e.g., [10–14].The next lemmas show that the search directions yielded by the two proposed methods always satisfy the sufficient descent condition.Lemma 1.
Suppose thatdk is generated by the LMYCD1 method and 0<σ<1. Then,(9)gkTdk≤−1σ+1gk2.Proof.
We prove (9) by induction. For k=1, it is easy to know from 0<σ<1 that g1Td1=−g12<−1/σ+1g12. Suppose that (9) is satisfied for k−1, namely, gk−1Tdk−1≤−1/σ+1gk−12,then obviously βkCD>0 holds by its definition. Furthermore, from the strong Wolfe line search, we have(10)0<−1−σgk−1Tdk−1≤dk−1Tgk−gk−1≤−1+σgk−1Tdk−1,and 0≤βkCDgkTdk−1≤βkCD−σdk−1Tgk−1=σgk2. This, together with βkLMYCD1 and relation (10), further implies that(11)0<1−σgk2dk−1Tgk−gk−1≤βkLMYCD1≤gk2dk−1Tgk−gk−1.
Now, we prove that (9) holds for k via the following three cases:(i)
IfgkTdk−1=0, then, by the definition of dk in Algorithm 1, we have(12)gkTdk=−gk2+βkLMYCD1gkTdk−1=−gk2<−1σ+1gk2.(ii)
IfgkTdk−1>0, then, similarly from definitions of dk and βkLMYCD1, taking βkCD>0, gk−1Tdk−1<0 and (10), we obtain(13)gkTdk=−gk2+βkLMYCD1gkTdk−1=−gk2+gk2−βkCDgkTdk−1dk−1Tgk−gk−1gkTdk−1=gk2gk−1Tdk−1−βkCDgkTdk−12dk−1Tgk−gk−1<gk2gk−1Tdk−1dk−1Tgk−gk−1≤gk2gk−1Tdk−1−1+σgk−1Tdk−1=−1σ+1gk2.(iii)
IfgkTdk−1<0, then, using dk and βkLMYCD1>0, we also obtain(14)gkTdk=−gk2+βkLMYCD1gkTdk−1<−gk2<−1σ+1gk2.
Therefore, the assertion is satisfied for allk≥1.Lemma 2.
Let the search directiondk be yielded by the LMYCD2 method and 0<σ<1/2. Then,(15)−11−σ≤gkTdkgk2≤−1−2σ1−σ.
Moreover, relation0<βkLMYCD2≤βkFR holds.Proof.
Fork=1, one has g1Td1/g12=−1, so (15) clearly holds. Suppose that relation (15) is satisfied for k−1. Now, we continue to prove that (15) holds for k. By the strong Wolfe line search and gk−1Tdk−1<0, it is clear that 0≤gkTdk−1≤−σgk−1Tdk−1, and hence(16)0<1−σ≤1−gkTdk−1−gk−1Tdk−1≤1.
Thus, usingβkLMYCD2, we obtain(17)0<1−σ‖gk‖2‖gk−1‖2≤βkLMYCD2=gk21−gkTdk−1/−gk−1Tdk−1gk2≤gk2gk−12=βkFR.
Furthermore, recallingdk in Algorithm 2, βkCD and βkLMYCD2, one has(18)gkTdkgk2=−1+gk2−gk2/−dk−1Tgk−1gkTdk−1gk−12gkTdk−1gk2=−1+1−gkTdk−1−dk−1Tgk−1gkTdk−1gk−12.
This together with the right-hand side of (16) further shows that(19)−1−gkTdk−1gk−12≤gkTdkgk2≤−1+gkTdk−1gk−12.
Next, based on the strong Wolfe line search, from the left-hand side of (19) and assertion (15) for k−1, we have(20)gkTdkgk2≥−1+σgk−1Tdk−1gk−12≥−1−σ1−σ=−11−σ.
Similarly, from the right-hand side of (19), we also obtain(21)gkTdkgk2≤−1−σgk−1Tdk−1gk−12≤−1+σ1−σ=−1−2σ1−σ.
Thus, the proof is completed.


## 3. Convergence Results

Throughout this paper, we make the following elementary assumptions for the objective function:(H1)
The level setΛ=x∈Rnfx≤fx1 is bounded(H2)
In a neighborhoodU of Λ, fx is differentiable and its gradient gx is Lipschitz continuous, namely, there exists a constant L>0 such that gx−gy≤Lx−y,∀x,y∈UTo proceed, the well-known Zoutendijk condition [16] is reviewed in the following.


### 3.1. Zoutendijk Condition

Suppose that assumptions (H1)–(H2) hold, the search directiondk is a descent direction and the step length αk satisfies the Wolfe line search condition, then we have ∑k=1∞gkTdk2/dk2<∞. In particular, if the sufficient descent condition is satisfied, then ∑k=1∞gk4/dk2<+∞.Now, before establishing the global convergence of the LMYCD1 method, we show that the LMYCD1 method has similar properties to that of the DY method, which is very important to analyze the global convergence property of the method.Lemma 3.
Let the sequencexk be generated by the LMYCD1 method, then 0<βkLMYCD1≤gkTdk/gk−1Tdk−1 always hold for k≥1.Proof.
From relation (11), it is clear that βkLMYCD1>0. If gkTdk−1=0, then using relation (10), one hasβkLMYCD1=gk2/−gk−1Tdk−1=gkTdk/gk−1Tdk−1. In the case that gkTdk−1≠0, we prove βkLMYCD1≤gkTdk/gk−1Tdk−1 by the following two cases:(i)
IfgkTdk−1>0, from relation (13), we have gkTdk<gk2gk−1Tdk−1/dk−1Tgk−gk−1. Then, dividing this inequality by the negative term gk−1Tdk−1, it follows that gk2/dk−1Tgk−gk−1<gkTdk/gk−1Tdk−1, then combining with (11), we have βkLMYCD1<gkTdk/gk−1Tdk−1.(ii)
IfgkTdk−1<0, from definitions of dk and βkLMYCD1, by the strong Wolfe line search, we have(22)gkTdk=−gk2+βkLMYCD1gkTdk−1=gk2gk−1Tdk−1−βkCDgkTdk−1gkTdk−1dk−1Tgk−gk−1≤gk2gk−1Tdk−1−σβkCDgkTdk−1gk−1Tdk−1dk−1Tgk−gk−1=gk2−σβkCDgkTdk−1gk−1Tdk−1dk−1Tgk−gk−1,and hence gkTdk/gk−1Tdk−1≥gk2−σβkCDgkTdk−1/dk−1Tgk−gk−1 since gk−1Tdk−1<0. Again, from 0<σ<1, we have(23)βkLMYCD1=gk2−βkCDgkTdk−1dk−1Tgk−gk−1≤gk2−σβkCDgkTdk−1dk−1Tgk−gk−1.
This implies thatβkLMYCD1≤gkTdk/gk−1Tdk−1, and the proof is completed.Subsequently, based on Lemma1 and Lemma 3, we can prove the global convergence of the LMYCD1 method.Theorem 1.
Suppose that Assumptions (H1)–(H2) hold. Let the sequencexk be generated by the LMYCD1 method, then the LMYCD1 method is globally convergent by the way of liminfk⟶∞gk=0.Proof.
By contradiction, we suppose that the conclusion is not true, then there exists a constantγ>0 such that gk2≥γ,∀k≥1. Since dk+gk=βkLMYCD1dk−1, it follows from Lemma 3 that(24)dk2=βkLMYCD12dk−12−2gkTdk−gk2≤gkTdkgk−1Tdk−12dk−12−2gkTdk−gk2.
Dividing this bygkTdk2, it is easy to get that(25)dk2gkTdk2≤dk−12gk−1Tdk−12−2gkTdk−gk2gkTdk2=dk−12gk−1Tdk−12−1gk+gkgkTdk2+1gk2≤dk−12gk−1Tdk−12+1gk2.
Notice thatd12/g1Td12=1/g12, using the abovementioned formula, we have(26)dk2gkTdk2≤dk−12gk−1Tdk−12+1gk2≤dk−22gk−2Tdk−22+1gk−12+1gk2≤⋯≤∑i=1k1gi2≤kγ.
Thus,gkTdk2/dk2≥γ/k, which further implies that ∑k=1∞gkTdk2/dk2=∞. It contradicts the Zoutendijk condition, and it follows that liminfk⟶∞gk=0.Next, based on Lemma2 and the Zoutendijk condition, we also obtain the global convergence for the LMYCD2 method.Theorem 2.
Suppose that Assumptions (H1)–(H2) hold. Let the sequencexk be generated by the LMYCD2 method, then the LMYCD2 method is globally convergent by the way of liminfk⟶∞gk=0.Proof.
Suppose by contradiction that assertion is not true, then there exists a constantγ>0 such that gk≥γ,∀k≥1. Squaring both sides of dk, one gets dk2=gk2−2βkLMYCD2gkTdk−1+βkLMYCD22dk−12. From Lemma 2 and the strong Wolfe line search, we have(27)−2βkLMYCD2gkTdk−1≤−2βkLMYCD2gkTdk−1≤2βkFRgkTdk−1≤2gk2gk−12σgk−1Tdk−1≤2σgk21−σ.
Thus, we obtaindk2≤1+σ/1−σgk2+gk4/gk−14dk−12. Again, dividing this inequality by gk4, we have dk2/gk4≤1+σ/1−σ1/gk2+dk−12/gk−14. Taking d12=g12 and gk≥γ, utilizing the abovementioned formula, one has(28)dk2gk4≤1+σ1−σ∑i=1k1gi2≤1+σ1−σkγ2.
This implies thatgk4/dk2≥1−σγ2/1+σ1/k; thus, ∑k=1∞gk4/gk2=∞, which also contradicts the Zoutendijk condition. Therefore, we can conclude that the LMYCD2 method is globally convergent by the way of liminfk⟶∞gk=0.


## 3.1. Zoutendijk Condition

Suppose that assumptions (H1)–(H2) hold, the search directiondk is a descent direction and the step length αk satisfies the Wolfe line search condition, then we have ∑k=1∞gkTdk2/dk2<∞. In particular, if the sufficient descent condition is satisfied, then ∑k=1∞gk4/dk2<+∞.Now, before establishing the global convergence of the LMYCD1 method, we show that the LMYCD1 method has similar properties to that of the DY method, which is very important to analyze the global convergence property of the method.Lemma 3.
Let the sequencexk be generated by the LMYCD1 method, then 0<βkLMYCD1≤gkTdk/gk−1Tdk−1 always hold for k≥1.Proof.
From relation (11), it is clear that βkLMYCD1>0. If gkTdk−1=0, then using relation (10), one hasβkLMYCD1=gk2/−gk−1Tdk−1=gkTdk/gk−1Tdk−1. In the case that gkTdk−1≠0, we prove βkLMYCD1≤gkTdk/gk−1Tdk−1 by the following two cases:(i)
IfgkTdk−1>0, from relation (13), we have gkTdk<gk2gk−1Tdk−1/dk−1Tgk−gk−1. Then, dividing this inequality by the negative term gk−1Tdk−1, it follows that gk2/dk−1Tgk−gk−1<gkTdk/gk−1Tdk−1, then combining with (11), we have βkLMYCD1<gkTdk/gk−1Tdk−1.(ii)
IfgkTdk−1<0, from definitions of dk and βkLMYCD1, by the strong Wolfe line search, we have(22)gkTdk=−gk2+βkLMYCD1gkTdk−1=gk2gk−1Tdk−1−βkCDgkTdk−1gkTdk−1dk−1Tgk−gk−1≤gk2gk−1Tdk−1−σβkCDgkTdk−1gk−1Tdk−1dk−1Tgk−gk−1=gk2−σβkCDgkTdk−1gk−1Tdk−1dk−1Tgk−gk−1,and hence gkTdk/gk−1Tdk−1≥gk2−σβkCDgkTdk−1/dk−1Tgk−gk−1 since gk−1Tdk−1<0. Again, from 0<σ<1, we have(23)βkLMYCD1=gk2−βkCDgkTdk−1dk−1Tgk−gk−1≤gk2−σβkCDgkTdk−1dk−1Tgk−gk−1.
This implies thatβkLMYCD1≤gkTdk/gk−1Tdk−1, and the proof is completed.Subsequently, based on Lemma1 and Lemma 3, we can prove the global convergence of the LMYCD1 method.Theorem 1.
Suppose that Assumptions (H1)–(H2) hold. Let the sequencexk be generated by the LMYCD1 method, then the LMYCD1 method is globally convergent by the way of liminfk⟶∞gk=0.Proof.
By contradiction, we suppose that the conclusion is not true, then there exists a constantγ>0 such that gk2≥γ,∀k≥1. Since dk+gk=βkLMYCD1dk−1, it follows from Lemma 3 that(24)dk2=βkLMYCD12dk−12−2gkTdk−gk2≤gkTdkgk−1Tdk−12dk−12−2gkTdk−gk2.
Dividing this bygkTdk2, it is easy to get that(25)dk2gkTdk2≤dk−12gk−1Tdk−12−2gkTdk−gk2gkTdk2=dk−12gk−1Tdk−12−1gk+gkgkTdk2+1gk2≤dk−12gk−1Tdk−12+1gk2.
Notice thatd12/g1Td12=1/g12, using the abovementioned formula, we have(26)dk2gkTdk2≤dk−12gk−1Tdk−12+1gk2≤dk−22gk−2Tdk−22+1gk−12+1gk2≤⋯≤∑i=1k1gi2≤kγ.
Thus,gkTdk2/dk2≥γ/k, which further implies that ∑k=1∞gkTdk2/dk2=∞. It contradicts the Zoutendijk condition, and it follows that liminfk⟶∞gk=0.Next, based on Lemma2 and the Zoutendijk condition, we also obtain the global convergence for the LMYCD2 method.Theorem 2.
Suppose that Assumptions (H1)–(H2) hold. Let the sequencexk be generated by the LMYCD2 method, then the LMYCD2 method is globally convergent by the way of liminfk⟶∞gk=0.Proof.
Suppose by contradiction that assertion is not true, then there exists a constantγ>0 such that gk≥γ,∀k≥1. Squaring both sides of dk, one gets dk2=gk2−2βkLMYCD2gkTdk−1+βkLMYCD22dk−12. From Lemma 2 and the strong Wolfe line search, we have(27)−2βkLMYCD2gkTdk−1≤−2βkLMYCD2gkTdk−1≤2βkFRgkTdk−1≤2gk2gk−12σgk−1Tdk−1≤2σgk21−σ.
Thus, we obtaindk2≤1+σ/1−σgk2+gk4/gk−14dk−12. Again, dividing this inequality by gk4, we have dk2/gk4≤1+σ/1−σ1/gk2+dk−12/gk−14. Taking d12=g12 and gk≥γ, utilizing the abovementioned formula, one has(28)dk2gk4≤1+σ1−σ∑i=1k1gi2≤1+σ1−σkγ2.
This implies thatgk4/dk2≥1−σγ2/1+σ1/k; thus, ∑k=1∞gk4/gk2=∞, which also contradicts the Zoutendijk condition. Therefore, we can conclude that the LMYCD2 method is globally convergent by the way of liminfk⟶∞gk=0.


## 4. Numerical Results

In this section, we study the computational efficiency of the LMYCD1 and LMYCD2 methods, in contrast to the NHS [11], NPRP [11], JMJ [12] methods, the hybrid Dai-Yuan (hDY) method with βk=max0,minβkHS,βkDY [10], and a family of modified Dai-Liao CGMs [17] including MDL1, MDL2, MDL3, and MDL4. The 171 test problems in all are the unconstrained problems with dimensions ranging from 2 to 1500000, in which some are obtained from the CUTEr library [18] including test examples 1–46 in Table 1 and 1–49 in Table2and others from [19,20]. Moreover, the step length αk is yielded by using the strong Wolfe line search. All the considered methods were coded in Matlab R2016a and ran on a PC with 3.6 GHz CPU processor and 8 GB RAM and Windows 10 operating system. We terminated the iteration when one of the following conditions was satisfied: (i) ‖gk‖≤10−6 and (ii) the total number of iterations Itr>2000. If condition (ii) occurs, the method is deemed to fail for solving the corresponding test problem and denote it by “NaN.”Table 1
Numerical results for the first group methods.
No.
Problems
LMYCD1
hDY
NHS
JMJ
MDL1
MDL2
Name/n
Itr/NF/NG/Tcpu
Itr/NF/NG/Tcpu
Itr/NF/NG/Tcpu
Itr/NF/NG/Tcpu
Itr/NF/NG/Tcpu
Itr/NF/NG/Tcpu
1
cosine 200
16/168/98/0.035
103/1624/853/0.140
23/266/141/0.037
23/267/146/0.023
21/298/154/0.022
21/263/140/0.020
2
cosine 1000
19/198/103/0.037
NaN/NaN/NaN/NaN
25/362/180/0.086
24/327/168/0.075
21/264/151/0.051
24/329/166/0.062
3
cosine 10000
20/198/109/0.333
NaN/NaN/NaN/NaN
25/396/196/0.586
27/393/219/0.634
20/201/106/0.284
22/165/84/0.251
4
cosine 100000
20/198/109/2.425
NaN/NaN/NaN/NaN
55/1352/651/16.743
27/365/193/4.301
21/164/94/2.135
25/202/110/2.653
5
dixmaanj 3000
712/8825/4742/24.677
753/10019/5290/27.130
819/10004/5376/27.108
588/8189/4271/21.668
NaN/NaN/NaN/NaN
750/9567/5102/25.574
6
dixmaank 3000
558/8089/4042/21.231
706/9188/4868/24.756
869/11340/6028/30.712
533/6368/3414/17.636
1146/17072/8887/45.486
792/9774/5205/26.502
7
dixmaanl 3000
533/6689/3598/18.359
513/7035/3766/19.059
836/10716/5808/29.109
466/5473/2934/14.674
679/11438/5517/29.298
478/5633/3035/15.046
8
dixon3dq 20
200/2293/1258/0.157
171/2270/1204/0.117
236/2750/1492/0.134
213/2865/1493/0.134
189/2710/1434/0.138
172/2280/1184/0.122
9
dixon3dq 100
1013/12988/6889/0.665
1088/13497/7144/0.655
NaN/NaN/NaN/NaN
975/12564/6605/0.603
1168/16229/8469/0.788
1265/16115/8600/0.792
10
dqrtic 10
12/29/32/0.002
12/29/32/0.002
12/29/32/0.002
12/29/32/0.003
11/28/30/0.002
12/29/32/0.002
11
dqdrtic 10000
60/695/345/0.421
100/1409/717/0.692
61/723/395/0.385
90/1231/666/0.605
74/841/438/0.494
77/1206/632/0.568
12
dqdrtic 100000
68/713/392/2.755
73/954/491/3.383
86/970/527/3.722
80/996/517/3.817
NaN/NaN/NaN/NaN
69/1068/527/3.768
13
dqdrtic 1000000
58/618/358/25.828
87/1409/727/54.533
110/2431/1025/89.848
107/1590/815/63.473
83/1038/534/41.895
68/916/463/38.205
14
edensch 50
29/275/160/0.019
48/697/341/0.043
27/213/128/0.021
31/303/169/0.020
43/660/331/0.041
31/310/160/0.024
15
edensch 1000
37/531/270/0.268
37/467/254/0.260
33/435/239/0.277
28/274/146/0.138
37/410/225/0.240
37/564/281/0.295
16
edensch 10000
33/370/214/1.936
51/815/412/3.951
35/441/250/2.182
36/483/265/2.438
42/607/313/2.902
30/312/151/1.647
17
fletchcr 110
36/491/251/0.024
39/364/205/0.018
49/581/320/0.028
49/680/313/0.033
44/580/304/0.031
NaN/NaN/NaN/NaN
18
freuroth 5
121/1831/964/0.074
NaN/NaN/NaN/NaN
335/7995/3349/0.436
145/2101/1145/0.101
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
19
genrose 1400
196/2510/1309/0.266
204/2531/1337/0.342
210/2563/1370/0.348
NaN/NaN/NaN/NaN
147/2332/1195/0.246
175/2517/1319/0.337
20
genrose 500000
97/1198/625/37.852
98/1320/693/41.850
215/2405/1318/78.872
158/1644/909/53.339
112/1162/621/40.218
108/1185/648/38.429
21
genrose 1000000
122/1639/881/105.302
156/2310/1194/144.932
154/2264/1202/140.419
NaN/NaN/NaN/NaN
133/1882/989/117.067
NaN/NaN/NaN/NaN
22
genrose 1500000
127/1299/702/127.953
151/1740/932/170.937
186/2209/1182/209.864
NaN/NaN/NaN/NaN
101/1438/751/132.774
106/1259/685/118.715
23
himmelbg 50
8/21/28/0.003
8/23/30/0.002
8/23/30/0.002
8/23/30/0.002
8/22/29/0.002
8/23/30/0.002
24
himmelbg 5000
9/25/33/0.025
9/26/34/0.026
9/26/34/0.026
9/26/34/0.033
9/25/33/0.032
9/26/34/0.036
25
himmelbg 20000
9/25/33/0.112
9/26/34/0.112
9/26/34/0.108
9/26/34/0.115
9/25/33/0.097
9/26/34/0.122
26
himmelbg 500000
10/28/37/2.707
10/29/38/2.792
10/29/38/2.970
10/29/38/3.071
10/28/37/2.961
10/29/38/2.881
27
mccormak 2
18/167/85/0.010
NaN/NaN/NaN/NaN
18/189/96/0.012
NaN/NaN/NaN/NaN
28/232/127/0.017
NaN/NaN/NaN/NaN
28
nondquar 5
70/725/406/0.070
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
29
nonscomp 2
34/445/227/0.026
43/682/343/0.030
61/1032/475/0.051
53/940/497/0.043
47/833/413/0.036
NaN/NaN/NaN/NaN
30
penalty1 10
9/10/13/0.006
6/10/10/0.001
6/10/10/0.001
6/10/10/0.001
6/9/9/0.001
6/10/10/0.001
31
penalty1 500
7/22/17/0.032
6/22/16/0.037
5/22/15/0.031
5/22/15/0.032
5/21/14/0.027
5/22/15/0.027
32
penalty1 1500
8/24/19/0.232
11/24/22/0.274
10/24/21/0.262
10/24/21/0.241
10/23/20/0.226
10/24/21/0.256
33
penalty1 2500
10/26/22/0.708
10/26/22/0.739
10/26/22/0.768
10/26/22/0.744
10/25/21/0.701
10/26/22/0.768
34
penalty1 10000
10/30/24/12.546
11/30/25/12.838
11/30/25/12.769
11/30/25/12.932
11/29/24/12.570
11/30/25/12.808
35
power1 4
34/307/171/0.014
45/776/398/0.040
34/343/191/0.014
49/697/380/0.027
82/1971/655/0.073
34/405/201/0.021
36
quartc 50
14/40/40/0.005
15/40/41/0.004
15/40/41/0.004
15/40/41/0.008
16/40/42/0.007
15/40/41/0.004
37
quartc 300
16/51/48/0.011
18/51/50/0.013
18/51/50/0.013
18/51/50/0.012
21/119/80/0.029
18/51/50/0.012
38
quartc 450
18/52/50/0.019
19/53/52/0.022
19/53/52/0.018
19/53/52/0.019
33/164/110/0.050
19/53/52/0.020
39
sine 1200
22/181/105/0.053
NaN/NaN/NaN/NaN
21/296/164/0.062
25/363/195/0.065
31/491/255/0.087
17/171/95/0.033
40
sine 50000
19/179/88/1.320
NaN/NaN/NaN/NaN
29/552/277/4.156
19/171/95/1.344
26/358/174/2.532
42/937/438/6.981
41
sine 1000000
19/239/114/31.308
51/1197/560/178.174
754/23822/9561/3300.832
NaN/NaN/NaN/NaN
27/299/171/41.517
NaN/NaN/NaN/NaN
42
tridia 5
58/669/354/0.033
69/887/447/0.041
66/687/354/0.037
51/546/284/0.026
53/669/341/0.030
50/597/314/0.031
43
tridia 100
397/4862/2584/0.280
429/5999/3112/0.389
405/5843/3057/0.350
328/4146/2239/0.207
453/7170/3542/0.465
353/4357/2305/0.309
44
tridia 150
480/6130/3248/0.331
528/7801/4061/0.537
540/6307/3390/0.337
463/5441/2963/0.348
481/7390/3906/0.507
552/7319/3783/0.427
45
tridia 1150
1428/19793/9820/2.478
1595/21705/11472/2.759
NaN/NaN/NaN/NaN
1247/15946/8435/1.875
NaN/NaN/NaN/NaN
1894/26206/13791/2.954
46
tridia 5000
1944/29689/13110/12.150
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
47
bdexp 10000
10/23/32/0.176
12/24/35/0.210
12/24/35/0.203
12/24/35/0.207
12/23/34/0.200
12/24/35/0.197
48
bdexp 100000
10/23/32/1.414
12/24/35/1.668
12/24/35/1.611
12/24/35/1.674
12/23/34/1.633
12/24/35/1.587
49
bdexp 1000000
11/27/37/16.882
13/26/38/17.484
13/26/38/17.751
13/26/38/17.919
13/25/37/17.563
13/26/38/17.759
50
beale 2
41/349/195/0.032
52/658/349/0.046
49/578/289/0.050
44/773/372/0.053
NaN/NaN/NaN/NaN
28/365/189/0.020
51
biggsb1 10
45/486/261/0.028
78/1240/626/0.058
50/575/318/0.025
62/931/489/0.042
60/721/390/0.034
52/796/408/0.038
52
biggsb1 50
205/2667/1419/0.119
213/2723/1468/0.131
379/4896/2556/0.316
196/2531/1355/0.191
244/3237/1670/0.191
199/2645/1352/0.115
53
bv 4
36/353/203/0.037
57/781/407/0.044
45/682/361/0.049
42/509/264/0.039
58/1084/487/0.072
53/802/409/0.054
54
bv 500
100/1371/714/2.532
267/3700/1928/6.837
148/2007/1067/3.837
253/3310/1727/6.161
115/2026/970/3.662
337/4193/2179/7.834
55
bv 1000
22/272/151/1.317
41/617/315/2.804
24/269/138/1.273
40/561/291/2.672
17/232/118/1.067
40/616/312/2.830
56
diagonal1 10
28/245/123/0.025
28/239/151/0.023
29/275/159/0.013
27/366/184/0.017
42/783/389/0.039
29/400/206/0.023
57
diagonal2 50
49/426/238/0.023
58/769/401/0.039
52/518/280/0.033
49/343/216/0.018
62/775/434/0.065
52/648/345/0.048
58
diagonal2 200
114/1235/697/0.135
107/1653/889/0.128
113/1482/799/0.116
98/1141/610/0.090
111/1257/717/0.087
99/1311/741/0.083
59
diagonal3 10
31/215/118/0.014
38/440/214/0.020
32/374/188/0.021
36/560/292/0.025
28/207/117/0.012
32/306/158/0.017
60
diagonal3 50
66/588/329/0.050
NaN/NaN/NaN/NaN
69/1158/574/0.087
75/1027/529/0.085
NaN/NaN/NaN/NaN
73/739/438/0.046
61
exdenschnb 100000
15/71/44/0.360
3/4/4/0.021
15/75/45/0.356
16/138/79/0.616
21/205/107/0.918
15/108/66/0.491
62
exdenschnf 5000
21/115/70/0.083
36/496/249/0.274
30/407/214/0.211
24/179/96/0.091
38/633/310/0.388
28/308/174/0.186
63
exdenschnf 50000
23/148/88/0.860
36/496/249/2.362
31/408/216/2.017
25/180/98/0.932
40/698/329/3.275
29/309/176/1.572
64
exdenschnf 100000
23/148/87/1.574
37/496/251/4.593
31/408/216/3.835
26/213/116/1.992
41/700/321/6.019
29/309/172/2.878
65
genquartic 50000
21/123/79/0.411
48/664/334/1.991
23/305/165/0.954
29/442/228/1.419
18/140/74/0.413
28/372/202/1.187
66
genquartic 100000
29/327/172/2.023
67/858/482/5.113
24/280/134/1.684
24/215/117/1.324
22/268/135/1.546
27/277/151/1.605
67
ie 3
12/99/56/0.011
12/65/36/0.005
12/132/68/0.009
12/132/70/0.008
13/101/59/0.006
11/99/56/0.012
68
ie 10
12/99/59/0.010
12/65/41/0.008
12/132/66/0.019
12/132/63/0.016
13/103/54/0.012
11/99/47/0.010
69
ie 50
13/99/57/0.140
12/65/41/0.101
12/132/75/0.187
12/132/76/0.185
15/166/85/0.197
11/99/56/0.116
70
ie 150
13/99/60/1.252
13/65/43/0.870
12/132/74/1.550
12/132/76/1.509
15/166/81/1.874
12/99/55/1.145
71
ie 200
13/99/60/2.073
13/65/43/1.516
13/132/73/2.618
13/132/75/2.685
15/166/91/3.305
12/99/58/2.059
72
ie 800
13/99/56/31.879
13/65/45/23.171
13/132/74/40.877
13/132/77/41.227
16/166/88/51.090
12/99/58/32.305
73
ie 1000
14/99/57/51.186
13/65/45/35.255
13/132/74/65.817
13/132/80/65.400
16/166/89/81.337
13/99/56/50.446
74
ie 2000
14/99/57/203.034
13/65/44/144.064
13/132/71/251.499
14/165/93/320.752
16/166/86/319.077
13/99/58/202.787
75
lin 50
2/2/2/0.006
2/2/2/0.002
2/2/2/0.002
2/2/2/0.003
2/2/2/0.002
2/2/2/0.002
76
lin 100
2/2/2/0.004
2/2/2/0.004
2/2/2/0.004
2/2/2/0.006
2/2/2/0.006
2/2/2/0.007
77
lin 300
2/2/2/0.016
2/2/2/0.014
2/2/2/0.016
2/2/2/0.016
2/2/2/0.012
2/2/2/0.023
78
lin 500
2/2/2/0.022
2/2/2/0.022
2/2/2/0.022
2/2/2/0.026
2/2/2/0.025
2/2/2/0.036
79
lin 1000
9/5/9/8.799
3/5/3/3.406
11/5/11/10.082
11/5/11/10.456
11/6/11/10.495
11/5/11/10.403
80
lin 2000
14/129/45/1399.218
3/32/16/340.750
12/33/25/497.186
12/33/25/501.923
12/34/25/510.829
12/33/25/508.992
81
lin 3000
7/9/7/645.228
10/9/10/828.686
10/9/10/831.544
10/9/10/825.478
10/10/10/850.265
10/9/10/819.908
82
pen1 50
195/2534/1365/0.222
109/1676/850/0.123
202/3459/1695/0.253
374/3067/1653/0.245
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
83
raydan1 100
90/1064/555/0.055
91/1122/661/0.058
99/1283/709/0.069
86/1168/616/0.065
98/1466/700/0.088
90/733/439/0.039
84
raydan1 550
211/2880/1399/0.220
230/3337/1658/0.263
221/3130/1638/0.228
213/2560/1313/0.208
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
85
raydan1 850
353/5182/2719/0.479
427/6444/3162/0.617
426/6577/3383/0.540
NaN/NaN/NaN/NaN
331/5592/2799/0.492
292/4371/2299/0.443
86
raydan1 1550
406/5155/2639/0.608
539/8573/4322/1.068
515/7443/3835/0.928
411/5995/3045/0.730
NaN/NaN/NaN/NaN
561/8552/4439/1.044
87
raydan2 8000
16/258/126/0.216
17/269/151/0.191
15/226/127/0.186
16/289/157/0.250
15/225/134/0.192
16/258/144/0.215
88
raydan2 10000
17/324/158/0.343
NaN/NaN/NaN/NaN
14/194/113/0.225
14/194/113/0.216
15/225/129/0.237
14/194/113/0.218
89
trid 40
40/438/242/0.054
89/1164/627/0.155
41/566/308/0.062
39/335/184/0.031
51/851/431/0.070
42/470/275/0.043
90
trid 150
85/1024/521/0.250
97/1372/703/0.376
91/1003/530/0.288
79/757/403/0.184
83/814/442/0.206
86/1100/599/0.285
91
trid 200
84/1033/553/0.362
92/1216/640/0.359
97/1480/767/0.466
88/1044/533/0.305
94/1791/855/0.509
93/1173/642/0.390
92
trid 400
86/971/534/1.345
112/1479/771/1.978
100/1264/677/1.717
89/885/499/1.248
92/1382/717/1.844
101/1207/639/1.629
93
trid 900
75/947/459/3.721
95/1377/712/5.347
86/1096/564/4.310
97/1181/620/4.736
164/3703/1426/13.257
76/994/546/3.986
94
trid 1500
86/807/438/7.548
88/1168/614/10.417
93/1347/727/12.063
82/982/512/8.789
101/1462/737/12.781
77/771/429/7.194
95
trid 2000
75/828/446/12.334
94/1344/668/19.059
91/842/461/12.558
84/950/530/14.230
100/1365/711/19.965
84/811/419/11.853
96
trid 2500
89/973/529/21.609
106/1285/681/28.453
97/1151/599/25.250
84/848/466/19.354
130/2409/1039/49.331
111/1719/891/39.398
97
trid 5000
83/1099/555/90.581
107/1555/791/124.931
95/1227/658/100.214
84/1023/569/84.970
106/1540/776/123.150
85/1038/572/85.971
98
vardim 2
10/11/13/0.006
12/11/15/0.002
12/11/15/0.001
12/11/15/0.001
12/10/14/0.001
12/11/15/0.001
99
vardim 8
9/30/19/0.002
11/30/21/0.002
11/30/21/0.002
11/30/21/0.004
11/29/20/0.004
11/30/21/0.003
100
watson 2
14/75/44/0.012
15/136/79/0.014
18/175/107/0.025
14/109/64/0.016
17/144/83/0.012
19/146/82/0.013Table 2
Numerical results for the second group methods.
No.
Problems
LMYCD2
NPRP
JMJ
MDL3
MDL4
Name/n
Itr/NF/NG/Tcpu
Itr/NF/NG/Tcpu
Itr/NF/NG/Tcpu
Itr/NF/NG/Tcpu
Itr/NF/NG/Tcpu
1
dixmaana 3000
11/99/60/0.320
14/133/76/0.335
15/232/127/0.717
14/165/100/0.424
15/166/88/0.480
2
dixmaanb 3000
8/8/11/0.037
7/8/10/0.031
7/8/10/0.033
7/8/10/0.047
7/8/10/0.044
3
dixmaanc 3000
8/10/12/0.046
8/10/12/0.043
8/10/12/0.042
8/10/12/0.044
8/10/12/0.042
4
dixmaand 3000
10/12/15/0.060
9/12/14/0.062
9/12/14/0.096
9/12/14/0.070
9/12/14/0.061
5
dixon3dq 5
68/1458/731/0.074
72/1681/797/0.076
127/3187/1608/0.132
NaN/NaN/NaN/NaN
148/3488/1696/0.143
6
dixon3dq 20
224/4410/2262/0.225
219/5179/2654/0.230
318/7695/3847/0.377
265/6633/3359/0.281
295/7536/3776/0.424
7
dixon3dq 40
245/4791/2482/0.265
846/20327/10219/0.936
510/12183/6010/0.488
559/13660/6924/0.597
494/12236/6183/0.565
8
dqrtic 5
8/24/26/0.003
7/20/21/0.002
7/20/21/0.002
7/24/25/0.001
7/24/25/0.002
9
dqrtic 50
13/68/51/0.006
15/143/89/0.010
22/317/177/0.036
16/143/98/0.010
16/142/86/0.010
10
dqrtic 100
15/74/57/0.008
21/305/173/0.034
20/312/174/0.039
23/408/215/0.039
22/303/168/0.043
11
dqdrtic 10000
64/1478/694/0.695
99/2453/1192/1.243
165/4184/2065/2.130
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
12
dqdrtic 20000
108/2547/1218/2.358
95/2065/1022/1.882
270/6666/3372/6.113
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
13
dqdrtic 30000
69/1587/794/1.940
94/2074/1000/2.469
244/5875/2919/7.362
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
14
dqdrtic 100000
107/2563/1232/9.380
81/1746/863/6.361
154/3576/1787/12.649
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
15
dqdrtic 500000
87/1837/926/36.856
103/2266/1173/46.490
218/5514/2774/112.655
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
16
dqdrtic 800000
85/1889/856/59.337
64/1507/716/49.550
186/4379/2200/141.928
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
17
edensch 5
45/1033/536/0.070
51/1190/584/0.070
41/925/463/0.051
38/833/396/0.038
38/863/435/0.044
18
edensch 50
40/782/380/0.069
38/833/401/0.053
47/1034/556/0.064
43/931/467/0.058
53/1223/608/0.080
19
edensch 1000
43/849/449/0.436
44/935/494/0.470
52/1105/575/0.583
NaN/NaN/NaN/NaN
50/1180/570/0.592
20
fletcbv3 5
8/220/134/0.027
10/221/126/0.009
11/285/147/0.012
9/225/136/0.009
10/283/142/0.014
21
fletchcr 5
66/1439/715/0.067
73/1728/791/0.064
76/1875/916/0.072
NaN/NaN/NaN/NaN
152/4088/2046/0.184
22
fletchcr 50
68/1359/738/0.064
NaN/NaN/NaN/NaN
122/3233/1547/0.186
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
23
fletchcr 100
78/1762/920/0.096
72/1500/716/0.094
56/1447/704/0.064
102/2460/1229/0.109
NaN/NaN/NaN/NaN
24
himmelbg 50
5/21/25/0.010
6/23/28/0.001
6/23/28/0.002
6/23/28/0.002
6/23/28/0.002
25
himmelbg 2000
6/26/31/0.013
6/23/28/0.010
6/23/28/0.009
6/23/28/0.008
6/23/28/0.010
26
himmelbg 15000
6/26/31/0.078
7/28/34/0.085
7/28/34/0.090
7/28/34/0.095
7/28/34/0.092
27
himmelbg 20000
6/26/31/0.098
7/28/34/0.112
7/28/34/0.101
7/28/34/0.094
7/28/34/0.096
28
himmelbg 30000
6/26/31/0.138
7/28/34/0.169
7/28/34/0.171
7/28/34/0.166
7/28/34/0.159
29
himmelbg 500000
6/26/31/2.252
7/28/34/2.493
7/28/34/2.519
7/28/34/2.544
7/28/34/2.572
30
liarwhd 5
35/733/351/0.037
61/1368/708/0.070
84/1961/971/0.110
98/2487/1264/0.134
69/1741/877/0.103
31
liarwhd 40
51/1121/552/0.051
54/1124/578/0.051
96/2329/1152/0.126
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
32
liarwhd 150
259/7393/3614/0.455
138/3644/1756/0.245
414/10287/5102/0.579
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
33
liarwhd 250
186/5054/2460/0.383
NaN/NaN/NaN/NaN
254/6022/3047/0.404
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
34
liarwhd 550
201/4502/2328/0.447
160/4340/2127/0.400
331/8852/4412/0.870
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
35
liarwhd 850
240/5864/2800/0.562
NaN/NaN/NaN/NaN
449/12111/6085/1.253
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
36
liarwhd 2300
873/24662/12176/3.795
NaN/NaN/NaN/NaN
882/25260/12572/4.251
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
37
mccormak 2
20/420/201/0.019
25/517/257/0.020
19/386/181/0.015
25/545/275/0.021
22/482/215/0.018
38
nonscomp 5
724/17084/8691/0.916
NaN/NaN/NaN/NaN
456/11568/5816/0.598
285/7081/3493/0.324
NaN/NaN/NaN/NaN
39
penalty1 50
1233/39330/14712/4.998
1828/58058/23959/7.366
1828/58058/23940/6.867
1828/58058/24001/6.467
1828/58058/24020/7.298
40
penalty1 100
1700/54044/21008/10.701
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
41
penalty1 2500
10/159/87/3.184
651/20314/10086/398.089
651/20314/10086/386.162
651/20314/10086/395.460
651/20314/10086/388.435
42
power1 4
46/860/433/0.036
60/1301/650/0.049
69/1588/816/0.076
79/1846/932/0.079
48/1089/553/0.050
43
power1 10
106/2007/1047/0.088
117/2787/1344/0.117
131/3061/1526/0.132
131/3162/1558/0.123
169/4132/2048/0.153
44
quartc 50
13/68/51/0.008
15/143/89/0.010
22/317/177/0.039
16/143/98/0.022
16/142/86/0.017
45
quartc 100
15/74/57/0.008
21/305/173/0.041
20/312/174/0.050
23/408/215/0.033
22/303/168/0.026
46
quartc 350
15/83/61/0.019
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
47
quartc 450
29/427/209/0.093
34/482/259/0.152
27/299/159/0.070
34/570/305/0.138
39/672/358/0.151
48
tridia 2
43/932/474/0.057
66/1580/790/0.062
67/1560/789/0.060
60/1521/747/0.081
55/1447/696/0.062
49
tridia 10
94/1741/903/0.110
107/2639/1302/0.159
125/2848/1423/0.120
NaN/NaN/NaN/NaN
147/3800/1940/0.155
50
band 3
44/1112/547/0.056
15/100/55/0.006
68/1839/916/0.113
103/2955/1482/0.150
95/2699/1310/0.156
51
band 200
52/1080/540/1.946
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
52
bdexp 40
6/18/23/0.006
6/18/23/0.001
6/18/23/0.001
6/18/23/0.001
6/18/23/0.002
53
bdexp 100
6/19/24/0.002
7/22/28/0.002
7/22/28/0.003
7/22/28/0.003
7/22/28/0.002
54
bdexp 80000
7/23/29/1.047
8/26/33/1.162
8/26/33/1.184
8/26/33/1.211
8/26/33/1.117
55
bdexp 100000
7/23/29/1.294
8/26/33/1.420
8/26/33/1.461
8/26/33/1.473
8/26/33/1.489
56
bdexp 150000
7/23/29/1.898
8/26/33/2.114
8/26/33/2.196
8/26/33/2.130
8/26/33/2.137
57
bdexp 500000
7/23/29/6.325
8/26/33/7.023
8/26/33/7.239
8/26/33/7.340
8/26/33/7.407
58
biggsb1 5
38/735/382/0.031
78/1795/911/0.068
85/1980/1010/0.087
42/1007/497/0.039
80/1991/1004/0.078
59
biggsb1 35
231/4623/2331/0.283
191/4598/2337/0.184
353/8190/4155/0.385
329/8469/4176/0.355
280/7123/3669/0.347
60
bv 4
57/1140/574/0.065
66/1622/769/0.085
77/1726/899/0.096
75/1631/853/0.090
91/2076/1077/0.120
61
bv 800
34/704/350/2.273
52/1200/595/3.867
51/1220/644/4.078
50/1275/646/4.103
74/1798/900/5.769
62
bv 1000
19/370/184/1.624
16/356/179/1.579
45/1061/538/4.735
50/1275/665/5.684
42/995/492/4.393
63
bv 2000
3/34/14/0.457
10/222/108/3.075
6/126/62/1.866
5/64/34/0.908
8/188/89/2.599
64
diagonal1 5
28/621/314/0.026
261/8131/4025/0.540
261/8131/4004/0.338
261/8131/4007/0.390
261/8131/4011/0.479
65
diagonal3 10
43/833/424/0.036
180/5424/2703/0.248
180/5424/2753/0.235
182/5487/2701/0.291
58/1349/666/0.095
66
exdenschnf 60
27/494/251/0.027
NaN/NaN/NaN/NaN
22/330/172/0.015
42/921/430/0.038
595/18392/9084/0.905
67
exdenschnf 1000
28/528/262/0.057
NaN/NaN/NaN/NaN
25/426/213/0.044
43/925/458/0.095
599/18519/9115/2.072
68
exdenschnf 6000
28/530/260/0.342
NaN/NaN/NaN/NaN
24/365/183/0.223
390/11922/5923/7.245
601/18552/9140/11.358
69
exdenschnf 10000
28/532/273/0.522
NaN/NaN/NaN/NaN
25/397/210/0.452
26/433/226/0.453
599/18495/9176/19.247
70
exdenschnf 100000
32/631/324/5.064
NaN/NaN/NaN/NaN
27/463/244/3.952
27/441/231/3.796
601/18545/9144/144.960
71
gauss 3
18/404/202/0.037
12/232/110/0.024
27/589/279/0.060
28/691/353/0.049
NaN/NaN/NaN/NaN
72
genquartic 50
27/563/284/0.033
NaN/NaN/NaN/NaN
30/561/270/0.023
35/771/375/0.031
27/523/242/0.021
73
genquartic 100
23/337/178/0.015
NaN/NaN/NaN/NaN
44/972/479/0.041
39/839/447/0.036
24/459/245/0.020
74
lin 5
2/2/2/0.002
2/2/2/0.001
2/2/2/0.002
2/2/2/0.002
2/2/2/0.002
75
lin 50
2/2/2/0.002
2/2/2/0.001
2/2/2/0.001
2/2/2/0.002
2/2/2/0.002
76
lin 100
2/2/2/0.005
2/2/2/0.004
2/2/2/0.003
2/2/2/0.004
2/2/2/0.004
77
lin 200
2/2/2/0.007
2/2/2/0.007
2/2/2/0.007
2/2/2/0.008
2/2/2/0.007
78
lin 500
2/2/2/0.021
2/2/2/0.023
2/2/2/0.022
2/2/2/0.021
2/2/2/0.021
79
lin 600
6/65/27/3.352
7/97/20/4.558
7/97/20/4.527
7/97/20/4.534
7/97/20/4.511
80
lin 750
2/4/2/0.617
2/4/2/0.583
2/4/2/0.552
2/4/2/0.603
2/4/2/0.591
81
pen2 10000
1/1/2/1.408
1/1/2/0.584
1/1/2/0.550
1/1/2/0.586
1/1/2/0.556
82
pen2 15000
1/1/2/3.110
1/1/2/3.683
1/1/2/2.083
1/1/2/1.249
1/1/2/1.312
83
pen2 20000
1/1/2/4.952
1/1/2/9.870
1/1/2/4.941
1/1/2/8.111
1/1/2/8.627
84
raydan2 2
28/669/328/2.864
130/3942/1958/0.311
130/3942/1958/0.162
130/3942/1958/0.301
130/3942/1958/0.171
85
raydan2 50
28/669/328/0.032
130/3942/1958/0.167
130/3942/1958/0.163
130/3942/1958/0.165
130/3942/1958/0.165
86
raydan2 500
29/669/329/0.048
130/3942/1958/0.366
130/3942/1958/0.360
130/3942/1958/0.377
130/3942/1958/0.311
87
raydan2 1000
29/669/329/0.075
131/3942/1959/0.509
131/3942/1959/0.498
131/3942/1959/0.605
131/3942/1959/0.528
88
raydan2 5000
29/669/329/0.479
131/3942/1959/2.392
131/3942/1959/2.376
131/3942/1959/2.521
131/3942/1959/2.373
89
raydan2 8000
29/669/329/0.750
131/3942/1959/3.662
131/3942/1959/3.759
131/3942/1959/3.784
131/3942/1959/3.751
90
raydan2 10000
29/669/329/0.683
131/3942/1959/4.793
131/3942/1959/4.801
131/3942/1959/4.822
131/3942/1959/4.823
91
raydan2 20000
29/669/330/1.181
131/3942/1959/8.871
131/3942/1959/8.928
131/3942/1959/8.911
131/3942/1959/8.855
92
raydan2 100000
30/669/336/5.506
131/3942/1959/40.716
131/3942/1959/40.606
131/3942/1959/40.753
131/3942/1959/40.791
93
raydan2 1000000
30/669/319/54.549
131/3942/1966/405.365
131/3942/1966/409.842
131/3942/1966/414.512
131/3942/1966/414.930
94
vardim 2
6/45/23/0.016
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
NaN/NaN/NaN/NaN
95
vardim 8
7/96/49/0.010
1685/53792/6599/2.492
1685/53792/6600/2.695
1685/53792/6600/2.551
1685/53792/6600/2.507
96
watson 4
107/2152/1072/0.250
115/2723/1368/0.409
135/3144/1554/0.375
NaN/NaN/NaN/NaN
122/2824/1397/0.357Table1 lists the detailed numerical results of the first group methods, which contain the LMYCD1, hDY, NHS, JMJ, MDL1, and MDL2 methods. Here, parameters σ=0.25 and δ=0.1. Notice that “n/Itr/NF/NG/Tcpu” denote the dimension of the test problems, the total number of iterations, function evaluations, gradient evaluations, and the CPU time in seconds, respectively. For the second group methods consisting of the LMYCD2, NPRP, JMJ, MDL3, and MDL4 methods, the corresponding numerical results are reported in Table 2. Here, parameters σ=0.1 and δ=0.001.In addition, we make use of the performance profiles of Dolan and Moré in [21] to compare the performance of the tested methods listed above, and readers refer to this literature for details about the introduction of the performance profiles. It is worth noting that the left side of each performance profile figure indicates the percentage of the test problems, which is the fastest among these methods, whereas the right side gives the percentage of the test problems that are successfully solved by each method. The top curve means that the corresponding method implements best in contrast to other methods.Figures1 and 2 illustrate the performance profiles for the LMYCD1, hDY, NHS, JMJ, MDL1, and MDL2 methods, by the total number of iterations, function evaluations, gradient evaluations, and the CPU time (s), respectively. In Figures 3 and 4, the performance profiles of the LMYCD2, NPRP, JMJ, MDL3, and MDL4 methods are described.Figure 1
Performance profiles of Itr (a) and NF (b) for the first group methods.
(a)
(b)Figure 2
Performance profiles of NG (a) and Tcpu (b) for the first group methods.
(a)
(b)Figure 3
Performance profiles of Itr (a) and NF (b) for the second group methods.
(a)
(b)Figure 4
Performance profiles of NG (a) and Tcpu (b) for the second group methods.
(a)
(b)Observing from all Figures1–4, the LMYCD1 and LMYCD2 methods, are competitive and both of them outperform the tested methods in each group, with respect to the characteristics Itr, NF, NG, and Tcpu, respectively. In addition, the two proposed methods in this paper ultimately solve 100% of the respective test problems successfully. All numerical results show that the efficiency of the LMYCD1 and LMYCD2 methods is encouraging.


## 5. Conclusion

In this paper, we construct two new formulas for setting parameterβk by using substantially the information of the JMJ and CD formulas as well as the second inequality in the strong Wolfe line search (3). Under the usual assumptions, the presented methods are proved to be sufficient descent and globally convergent. Elementary numerical experiments demonstrate that the two proposed methods perform effectively.



---

*Source: 9720653-2020-04-22.xml*