# A HS-PRP-Type Hybrid Conjugate Gradient Method with Sufficient Descent Property

Authors: Xiaodi Wu; Yihan Zhu; Jianghua Yin
Journal: Computational Intelligence and Neuroscience
 (2021)

---

## Abstract

In this paper, based on the HS method and a modified version of the PRP method, a hybrid conjugate gradient (CG) method is proposed for solving large-scale unconstrained optimization problems. The CG parameter generated by the method is always nonnegative. Moreover, the search direction possesses the sufficient descent property independent of line search. Utilizing the standard Wolfe–Powell line search rule to yield the stepsize, the global convergence of the proposed method is shown under the common assumptions. Finally, numerical results show that the proposed method is promising compared with two existing methods.


---

## Body

## 1. Introduction

Consider the problem of minimizingf over Rn:(1)minx∈Rnfx,where f:Rn⟶R is continuously differentiable. Throughout, the gradient of f at x is denoted by gx, i.e., gx:=∇fx. We know that conjugate gradient (CG) methods are very popular and effective for solving unconstrained optimization problems (1), especially for large-scale case by means of their simplicity and low memory requirements. These preferred features greatly promote their applications in various areas such as image deblurring and denoising, neural network, compressed sensing, and others. We refer the interested readers to some recent works [1–3] and references therein for more details. The numerical results reported in [1] reveal that the CG method has great potential in solving image restoration problems.Generally, the iterative formula of the CG method for solving problem (1) can be read as(2)xk+1=xk+αkdk,where αk>0 is called the stepsize computed by some line search. Here, dk is commonly known as the search direction, which is defined as follows:(3)dk=−gk,ifk=1,−gk+βkdk−1,ifk≥2,where βk∈R is the so-called CG parameter and gk is the abbreviation of gxk, i.e., gk:=gxk. The two key factors that affect the numerical performance of the CG method are the stepsize and the CG parameter. First, we outline several well-known line search criteria in the literature.(a)
The exact line search rule: calculate a stepsizeαk satisfying(4)fxk+αkdk=minα≥0fxk+αdk.(b)
The standard (weak) Wolfe–Powell (WWP) line search rule: calculate a stepsizeαk satisfying(5)fxk+αkdk≤fxk+δαkgkTdk,and(6)gxk+αkdkTdk≥σgkTdk,where0<δ<σ<1.(c)
The strong Wolfe–Powell (SWP) line search rule: calculate a stepsizeαk satisfying (5) and(7)gxk+αkdkTdk≤σgkTdk.On the other hand, different CG methods are determined by different CG parameters. The well-known CG methods include the Fletcher–Reeves (FR) [4], Polak–Ribière–Polyak (PRP) [5, 6], Hestenes–Stiefel (HS) [7], Liu–Storey (LS) [8], Fletcher (CD) [9], and Dai–Yuan (DY) [10] methods, and their CG parameters βk are, respectively, given by(8)βkFR=gk2gk−12,βkPRP=gkTyk−1gk−12,βkHS=gkTyk−1dk−1Tyk−1,βkLS=−gkTyk−1gk−1Tdk−1,βkCD=−gk2dk−1Tgk−1,βkDY=gk2dk−1Tyk−1,where yk−1:=gk−gk−1 and ⋅ stands for the Euclidean norm. The methods yielded by the above CG parameters are called the classical CG methods, and their convergence analysis and numerical performance have been extensively studied (see, e.g., [4–12]). It has been shown that the above formulas for the CG parameters are equivalent when fx is convex quadratic and the stepsize αk is obtained by carrying out the exact line search rule (4). However, their numerical performance strongly depends on the CG parameter βk. The FR, CD, and DY methods possess good convergence, but the numerical performance for these methods is somewhat unsatisfactory for solving general unconstrained nonlinear optimization problems [12–14]. On the contrary, it has been shown that the convergence properties of PRP, HS, and LS methods are not so well, but they often possess better computational performance [12–14]. Therefore, in the past few decades, based on the above formulas, plenty of formulas for βk are designed for CG methods that possess both good global convergence properties and promising numerical performance (see [12–16] and references therein).To our knowledge, the first hybrid CG method in the literature was proposed by Touati-Ahmed and Storey [17] (TS method), where βk is computed as(9)βkTS=βkPRP,if0≤βkPRP≤βkFR,βkFR,otherwise.Apparently, the TS method has some good properties of FR and PRP methods sinceβkTS is a hybrid of βkFR and βkPRP. Combined with HS and DY methods, Dai and Yuan [18] proposed another hybrid CG method (hHD method), in which the hybrid CG parameter βk is obtained by(10)βkhHD=max0,minβkHS,βkDY.When the WWP line search rule is used to compute the stepsize, the resulting search direction in [18] is a descent one and the global convergence for the hHD method is proved. Moreover, the numerical experiments reported in [18] illustrated that the hHD method is competitive and practicable. For other closely related works, we refer the readers to [18, 19] and the references therein. It is worth noting that the CG parameters βk defined in [17–19] are restricted to positive values. As explicated in [19], this restriction in turn results in global convergence of the algorithm. In recent years, many hybrid CG methods were proposed on the basis of the methodology of discrete combinations of several CG parameters (see, e.g., [1, 13, 20–23]). The combination parameter is computed by some secant equations [13, 20], the conjugacy condition [21, 22], or by minimizing the least-squares problem consisting of the unknown search direction and an existing one (see [23] and the references therein).In 2016, Wei et al. [24] introduced a modified PRP method, usually called the WYL method, where the corresponding parameter βk is yielded by(11)βkWYL=gk2−gk/gk−1gkTgk−1gk−12.Under the assumption thatdk generated by Wei et al. [24] satisfies the so-called sufficient descent condition (12)gkTdk≤−cgk2,c>0,the WYL method is globally convergent under the WWP line search rule and possesses superior numerical performance. Subsequently, Dai and Wen [25] proposed two improved CG methods with sufficient descent property. The CG parameters βk in [25] are defined as(13)βkDHS=gk2−gk/gk−1gkTgk−1dk−1Tyk−1+μgkTdk−1,βkDPRP=gk2−gk/gk−1gkTgk−1gk−12+μgkTdk−1,where μ>1. Clearly, the search direction yielded by βkDPRP satisfies the sufficient descent condition without depending on any line search. However, the sufficient descent property associated with βkDHS relies on the WWP line search rule.Based on the above observations, it is interesting to design a hybrid CG method such that the CG parameter is nonnegative and the resulting search direction possesses the sufficient descent property independent of line search technique. Motivated by the methods in [24, 25] and considering that the HS method performs best among the classical CG methods, a new formula for the CG parameter βk is given by(14)βkhHPR=minβkHS,gk2−gk/gk−1gkTgk−1gk−12+γgkTdk−1,where γ>2. It is not difficult to see that βkhHPR is a hybrid of βkHS, βkWYL, and βkDPRP. Interestingly, the above parameter βkhHPR is always nonnegative. To see this, let θk be the angle between gk and gk−1. Thus, we know from (14) that(15)βkhHPR≤gk2−gk/gk−1gkTgk−1gk−12+γgkTdk−1=gk21−cosθkgk−12+γgkTdk−1≤2gk2gk−12+γgkTdk−1,which further implies(16)0≤βkhHPR≤2gk2gk−12.Moreover, plugging the CG parameterβk:=βkhHPR into (3), we can show that the resulting search direction possesses the sufficient descent property independent of line search technique (see Lemma 1 below).The structure of this paper is organized as follows. In Section2, our algorithm framework is presented, and the sufficient descent property with respect to the resulting search direction is discussed in detail. Section 3 is devoted to establishing the convergence of the proposed method with the WWP line search rule. In the last section, some preliminary numerical results are reported to verify the efficiency of the presented method.


## 2. The Algorithm

In this section, we first propose the algorithm framework for solving problem (1), in which we do not specify which line search rule generates the stepsize. Subsequently, we analyze the sufficient descent property for the search direction. By inserting the WWP line search rule into the algorithm framework, our hybrid CG method is proposed.The following lemma shows that the direction sequencedk generated by Algorithm 1 possesses the sufficient descent property independent of any line search.Algorithm 1: Algorithm framework.
Step 0: (initialization) given the initial pointx1∈Rn,γ>2, ε>0. Set d1:=−g1 and k:=1.Step 1: stop ifgk≤ε.Step 2: compute the stepsizeαk by an appropriate line search rule.Step 3: generate the new iteration point byxk+1=xk+αkdk and compute βk:=βkhHPR according to (14).Step 4: compute the next directiondk+1 by (3), set k:=k+1, and go to Step 1.Lemma 1.
Letdk be a sequence generated by Algorithm 1. Then, for some constant M∈0,1, it holds that(17)gkTdk≤−Mgk2,∀,k≥1.Proof.
Whenk=1, it follows from the definition of dk in (3) that g1Td1=−g12≤−Mg12. So, the relation in (17) holds when k=1. Now, consider the case k≥2. If gkTdk−1=0, it follows from (3) that(18)gkTdk=−gk2≤−Mgk2.
Suppose thatgkTdk−1≠0 for all k≥2. It then follows from (3), (15), and (16) that(19)gkTdk=−gk2+βkhHPRgkTdk−1≤−gk2+2gk2gk−12+γgkTdk−1gkTdk−1≤−gk2+2gk2γgkTdk−1gkTdk−1≤−1−2γgk2≕−Mgk2,which completes the proof.For convenience, in the following statements, we call the method generated by Algorithm1 with the WWP line search rule as the hHPR CG method.


## 3. Convergence

In this section, we analyze the convergence for the hHPR CG method. For this goal, the following common assumptions are necessary.Assumption 1.
(i)
The level setΩ=x∈Rn|fx≤fx1 is bounded. Here, x1 is the given initial point.(ii)
In some neighborhoodN of the level set Ω, the objective function fx is continuously differentiable, and its gradient gx is Lipschitz continuous, i.e., there exists a constant L>0 such that(20)gx−gy≤Lx−y,∀x,y∈N.The following lemma provides the convergence for the PRP-type CG method, which was originally introduced in [19].Lemma 2.
Consider the general CG method (2) and (3) with the following three properties:(i)
The CG parameter is always nonnegative, i.e.,βk≥0 for all k≥1.(ii)
The line search satisfies (5) and (6) and the sufficient descent condition.(iii)
Property∗ holds. Then,(21)liminfk⟶∞gk=0.Property 1.
∗ Consider a method of forms (2) and (3). Suppose that(22)0<γ≤gk≤γ¯,∀,k≥1.
We say that the method has property∗, if for all k≥1, there exist constants b>1 and λ>0 such that βk≤b, and if sk−1≤λ where sk−1=xk−xk−1, then we have βk≤1/2b.
From (16) and Lemmas 1 and 2, to obtain the global convergence of the hHPR CG method, we only prove that our method owns property ∗.Lemma 3.
Consider the method of forms (2) and (3) in which βk=βkhHPR. If Assumption 1 holds, then βkhHPR satisfies property ∗.Proof.
Considering the method of forms (2) and (3) and using the constants γ and γ¯ in (22), we have from (16) that(23)0≤βkhHPR≤2gk2gk−12≤2γ¯2γ2.
Letb=2γ¯2/γ2≥2 and λ=γ4/8Lγ¯3>0. If sk−1≤λ, we obtain from Assumption 1(ii) and (15) that(24)βkhHPR≤gkTgk−gk/gk−1gk−1gk−12≤gk⋅gk−gk−1+gk−1−gk/gk−1gk−1gk−12≤gk⋅gk−gk−1+gk⋅gk−1−gkgk−12≤2gkgk−gk−1gk−12≤2Lsk−1gkgk−12≤2Lλγ¯γ2=12b.
Therefore, the proof is completed.With (16) and Lemmas 1–3 at hand, one can establish the global convergence of the hHPR CG method.Theorem 1.
Letxk be a sequence generated by the hHPR CG method. If Assumption 1 holds, then liminfk⟶∞gk=0.


## 4. Numerical Experiments

In this section, we verify the efficiency and robustness of the hHPR CG method (hHPR for short) by solving some classical tested problems and compare it with two well-known CG methods: DHS and DPRP in [25].For the tested problems, some of them are from the well-known CUTE library in [26] and the others come from [27]. Moreover, their dimensions range from 2 to 1000000. All codes were written in MATLAB R2016a, and the numerical experiments were conducted on a Dell PC with Intel Core CPU 3.00 GHz and 16.00 GB RAM. For the aforementioned methods, we reset the search direction by taking dk:=−gk once an ascent direction occurs. For the sake of fairness, all the stepsizes αk are yielded by the WWP line search rule following a bisection algorithm proposed in [28], and the corresponding parameters are set to δ=0.01 and σ=0.1. Moreover, we adopt the strategy described in [29] to compute the initial stepsize.Letγ=3 for hHPR, and let μ=2 for DHS and DPRP. Denote the iteration numbers, the CPU time in seconds, and the final value of gk by Itr,Tcpu, and g∗, respectively. If gk≤10−6 or Itr>2000, we stop the program. If the latter requirement holds, i.e., Itr>2000, we use “-” to denote Itr, Tcpu, and g∗.The numerical results are listed in Tables1 and 2, where “TP” denotes the tested problems used in numerical experiments and “Dim” stands for the dimension of the tested problems.Table 1
Numerical results for the three tested methods.
ProblemshHPRDHSDPRPTP/DimItr/Tcpu/g∗Itr/Tcpu/g∗Itr/Tcpu/g∗bdexp/500002/0.157/3.51e − 892/0.136/3.51e − 892/0.138/3.51e − 89bdexp/1000002/0.223/4.58e − 1062/0.223/4.58e − 1062/0.220/4.58e − 106bdexp/10000002/2.857/1.42e − 1702/2.829/1.42e − 1702/2.848/1.42e − 170exdenschnf/5000038/0.260/1.53e − 0730/0.230/9.80e − 0730/0.227/2.39e − 07exdenschnf/10000042/0.496/6.67e − 0725/0.425/8.47e − 0724/0.412/2.50e − 07exdenschnb/500024/0.020/6.69e − 0716/0.011/3.36e − 0819/0.011/3.61e − 07exdenschnb/2000025/0.047/2.79e − 0717/0.043/1.77e − 0722/0.057/4.59e − 07exdenschnb/10000017/0.215/5.21e − 0717/0.182/1.48e − 0717/0.183/1.03e − 07himmelbg/200002/0.029/6.91e − 282/0.022/6.91e − 282/0.021/6.91e − 28himmelbg/1000002/0.095/1.46e − 282/0.094/1.46e − 282/0.095/1.46e − 28genquartic/2000021/0.061/3.91e − 0718/0.052/5.09e − 0713/0.045/5.23e − 07genquartic/10000017/0.231/6.08e − 0718/0.230/4.49e − 0717/0.228/6.68e − 07genquartic/100000028/3.189/1.74e − 0718/2.818/5.34e − 0716/2.469/4.73e − 07biggsb1/2001218/0.064/9.68e − 071607/0.103/9.61e − 071742/0.114/1.00e − 06biggsb1/400———sine/10095/0.013/9.33e − 0729/0.003/5.63e − 0727/0.003/2.45e − 07sinquad/379/0.015/6.74e − 07359/0.022/9.39e − 07224/0.012/5.27e − 07fletcbv3/20101/0.014/4.42e − 07110/0.006/9.01e − 07147/0.008/5.29e − 07fletcbv3/40409/0.024/4.63e − 07485/0.026/7.67e − 07504/0.025/7.84e − 07eg2/100428/0.074/9.04e − 07—1428/0.115/7.75e − 07eg2/1701353/0.395/2.61e − 07——nonscomp/10000———nonscomp/2000050/0.077/7.79e − 0749/0.076/2.55e − 0746/0.073/8.37e − 07nonscomp/5000074/0.251/6.30e − 0769/0.239/6.07e − 0780/0.266/8.04e − 07cosine/100051/0.020/9.66e − 0720/0.009/5.27e − 0721/0.009/6.42e − 07cosine/1000051/0.090/5.31e − 0733/0.072/4.32e − 0721/0.057/1.04e − 07dixmaana/300020/0.132/2.60e − 0722/0.113/4.60e − 0717/0.107/5.22e − 07dixmaanb/300018/0.129/8.63e − 0720/0.107/1.96e − 0714/0.100/3.01e − 07dixmaanc/300017/0.130/3.91e − 0717/0.098/2.62e − 0716/0.126/6.68e − 07dixmaand/300023/0.146/2.23e − 0717/0.106/4.12e − 0717/0.116/3.92e − 07dixmaane/3000428/0.915/8.90e − 07612/1.731/8.10e − 07584/1.676/9.45e − 07dixmaanf/3000287/0.633/9.86e − 07540/1.527/9.46e − 07477/1.364/9.29e − 07dixmaang/3000431/0.951/7.93e − 07553/1.587/9.31e − 07598/1.759/8.21e − 07dixmaanh/3000538/1.292/5.87e − 07960/3.049/7.59e − 07918/2.984/8.35e − 07dixmaanj/3000———dixmaank/3000156/0.387/6.90e − 07——dixmaanl/3000——1199/3.390/9.95e − 07dixon3dq/80876/0.043/8.55e − 07912/0.050/8.66e − 071097/0.062/9.83e − 07dixon3dq/160———dqdrtic/1000067/0.073/4.83e − 07296/0.189/7.98e − 07243/0.160/5.41e − 07dqdrtic/10000085/0.468/9.32e − 07256/1.248/5.90e − 07153/0.819/2.43e − 07dqdrtic/100000070/5.007/6.70e − 07265/14.500/8.11e − 07273/14.436/7.49e − 07dqrtic/20027/0.014/2.68e − 0724/0.008/5.68e − 0726/0.009/5.17e − 08dqrtic/50033/0.021/5.05e − 0734/0.023/6.73e − 0729/0.020/5.84e − 07edensch/100040/0.051/7.37e − 0741/0.056/7.02e − 0736/0.046/8.63e − 07edensch/400073/0.493/8.66e − 0746/0.133/3.62e − 0743/0.204/8.20e − 07edensch/800044/0.620/8.57e − 0768/1.022/5.23e − 0739/0.456/6.70e − 07engval1/630/0.009/8.33e − 0737/0.002/2.36e − 0738/0.002/8.34e − 07errinros/3314/0.028/8.62e − 07——fletchcr/10084/0.022/9.11e − 0782/0.005/4.67e − 0767/0.005/7.99e − 07fletchcr/30045/0.005/8.17e − 07110/0.008/7.13e − 07117/0.007/8.66e − 07freuroth/50263/0.047/8.81e − 07788/0.107/8.23e − 07664/0.054/9.91e − 07genrose/5000———genrose/10000177/0.152/6.78e − 07499/0.433/9.48e − 07776/0.659/8.02e − 07genrose/20000———Table 2
Numerical results for the three tested methods (continued).
ProblemshHPRDHSDPRPTP/DimItr/Tcpu/g∗Itr/Tcpu/g∗Itr/Tcpu/g∗liarwhd/500094/0.066/7.37e − 07——liarwhd/10000138/0.186/8.02e − 07——liarwhd/20000125/0.388/7.88e − 07——nondquar/30534/0.072/8.10e − 07760/0.085/9.19e − 07—penalty1/100030/0.418/2.55e − 0729/0.411/2.65e − 0729/0.390/9.90e − 07penalty1/5000117/39.785/2.62e − 07278/103.383/4.27e − 07203/72.649/1.01e − 07power1/50595/0.029/9.03e − 07743/0.039/9.46e − 07917/0.050/2.82e − 07power1/1001468/0.068/9.91e − 071666/0.101/6.89e − 07—quartc/10023/0.010/6.45e − 0821/0.004/3.28e − 0727/0.006/1.06e − 07quartc/56032/0.023/7.15e − 0729/0.020/7.08e − 0733/0.022/5.70e − 07tridia/100409/0.026/6.30e − 07477/0.030/3.94e − 07681/0.038/9.21e − 07tridia/10001564/0.153/9.39e − 07——raydan1/10077/0.008/9.73e − 07127/0.010/8.52e − 07106/0.005/9.59e − 07raydan1/500210/0.015/9.14e − 07281/0.023/5.80e − 07268/0.022/7.43e − 07raydan2/500012/0.027/9.72e − 0712/0.021/3.54e − 0712/0.023/3.54e − 07raydan2/1000012/0.051/3.75e − 0713/0.052/7.31e − 0813/0.050/7.31e − 08raydan2/5000016/0.239/2.43e − 0816/0.217/8.05e − 0717/0.272/7.70e − 07diagonal1/4061/0.010/7.58e − 0781/0.005/7.52e − 0763/0.004/8.67e − 07diagonal2/10000830/1.082/9.48e − 071398/2.017/9.75e − 071134/1.660/6.18e − 07diagonal2/200001241/3.050/8.03e − 071387/4.025/9.98e − 071879/5.192/8.08e − 07diagonal3/1039/0.007/7.69e − 0737/0.002/4.92e − 0739/0.002/4.59e − 07diagonal3/9091/0.008/7.31e − 07144/0.010/9.04e − 07166/0.016/6.14e − 07bv/1000138/0.447/8.56e − 07117/0.513/8.14e − 07127/0.550/9.09e − 07bv/2000105/1.174/9.03e − 07107/1.476/8.99e − 07130/1.701/9.46e − 07ie/5016/0.051/9.24e − 0711/0.039/2.20e − 0715/0.044/1.83e − 07ie/1014/0.162/7.41e − 0712/0.156/2.72e − 0713/0.167/2.10e − 07singx/100277/0.051/3.49e − 07——singx/1000565/2.397/7.35e − 07—453/1.711/5.18e − 07woods/10000177/0.175/2.74e − 07589/0.492/2.25e − 07814/0.631/8.15e − 07band/319/0.012/2.13e − 0715/0.002/6.71e − 0718/0.002/9.14e − 07bard/3101/0.028/3.00e − 07698/0.097/4.95e − 07811/0.112/8.16e − 07beale/248/0.010/6.38e − 07131/0.007/2.30e − 0796/0.007/8.34e − 07biggs/6———box/374/0.014/5.48e − 07203/0.017/1.45e − 07185/0.015/5.45e − 07froth/292/0.014/6.85e − 07338/0.025/9.02e − 07381/0.026/8.13e − 07gauss/313/0.010/3.75e − 0724/0.004/4.71e − 0721/0.003/3.27e − 07helix/3102/0.019/4.65e − 07361/0.032/9.10e − 07418/0.036/9.20e − 07jensam/239/0.009/2.79e − 07148/0.009/9.70e − 07149/0.009/8.40e − 07kowosb/4224/0.029/9.98e − 071029/0.075/3.25e − 07797/0.056/9.64e − 07lin/10013/0.062/8.86e − 0713/0.054/8.86e − 0713/0.054/8.86e − 07lin/50018/0.418/9.57e − 0718/0.420/9.38e − 0718/0.421/9.38e − 07osb2/11734/0.113/7.42e − 071513/0.259/4.38e − 071174/0.198/7.47e − 07pen1/6078/0.025/4.74e − 07390/0.056/8.20e − 07668/0.079/8.95e − 07pen2/100151/0.074/7.94e − 07162/0.045/5.89e − 07235/0.081/8.49e − 07rose/279/0.011/9.71e − 07584/0.037/9.06e − 07858/0.053/2.86e − 07rosex/100104/0.022/4.68e − 071190/0.132/7.73e − 07705/0.080/8.08e − 07rosex/1000106/0.899/2.49e − 071040/6.318/8.60e − 071374/8.180/2.95e − 07sing/4213/0.023/6.12e − 07—1111/0.070/9.15e − 07trid/10080/0.021/4.41e − 07112/0.022/4.22e − 07128/0.024/6.31e − 07trid/20037/0.015/6.81e − 0746/0.016/7.20e − 0742/0.017/6.19e − 07vardim/828/0.011/4.13e − 0726/0.004/6.51e − 0731/0.004/9.75e − 07watson/61811/0.500/7.74e − 07——wood/4173/0.020/6.93e − 07622/0.047/5.42e − 07966/0.069/9.26e − 07As we all know, the performance profile introduced in [30] is very useful in measuring the performance of numerical algorithms. Figures 1 and 2 plot the performance profiles of hHPR, DHS, and DPRP in terms of Itr and Tcpu, respectively. Based on the left side of Figures 1 and 2, the proposed method is clearly above the other two curves, and this in turn shows that compared with DHS and DPRP, our proposed method is efficient and encouraging. On the other hand, based on the right side of Figures 1 and 2, our proposed method can successfully solve about 90% of the tested problems and clearly outperforms the other two methods.Figure 1
Performance profile on Tcpu.Figure 2
Performance profile on Itr.



---

*Source: 2087438-2021-10-22.xml*