# A Modified Hybrid Conjugate Gradient Method for Unconstrained Optimization

Authors: Minglei Fang; Min Wang; Min Sun; Rong Chen
Journal: Journal of Mathematics
 (2021)

---

## Abstract

The nonlinear conjugate gradient algorithms are a very effective way in solving large-scale unconstrained optimization problems. Based on some famous previous conjugate gradient methods, a modified hybrid conjugate gradient method was proposed. The proposed method can generate decent directions at every iteration independent of any line search. Under the Wolfe line search, the proposed method possesses global convergence. Numerical results show that the modified method is efficient and robust.


---

## Body

## 1. Introduction

Consider the following unconstrained optimization problem:(1)minx∈Rnfx,where x∈Rn is a real vector with n≥1 component and f:Rn⟶R is a smooth function and its gradient gx≜∇fx is available. Unconstrained problem is an important problem with a broad range of scientific and operational applications.During the last decade, the conjugate gradient methods constitute an active choice for efficiently solving the above optimization problem, especially when the dimensionn is large, characterized by the simplicity of their iteration, their low memory requirement, and their excellent numerical performance. The general procedure of the iterative computational scheme is as follows.When applied to solve problem (1), starting from an initial guess x1∈Rn, the conjugate gradient method usually generates a sequence xk as(2)xk+1=xk+αkdk,where xk is the current iterate, αk>0 is called a step size determined by some suitable line search, and dk is the search direction defined by(3)dk=−gk,k=1,−gk+βkdk−1,k≥2,where gk=∇fxk and βk is an important scalar parameter.Generally inexact line search is used in order to get the global convergence of conjugate gradient method, such as the Wolfe line search or the strong Wolfe line search. That is, the step lengthαk is usually computed by the Wolfe line search:(4)fxk−fxk+αkdk≥−δαkgkTdk,gxk+αkdkTdk≥σgkTdk,or the strong Wolfe line search:(5)fxk−fxk+αkdk≥−δαkgkTdk,gxk+αkdkTdk≤σgkTdk,where 0<δ<σ<1 are some fixed parameters.Different conjugate gradient methods correspond to different values of the scalar parameterβk. The well-known conjugate gradient methods include the Fletcher–Reeves (FR) method [1], the Polak–Ribière–Polyak (PRP) method [2, 3], the Hestenes–Stiefel (HS) method [4], the Dai–Yuan (DY) method [5], the conjugate-descent method (CD) [6], and the Liu–Storey method (LS) [7]. The parameters βk in these conjugate gradient methods are specified as follows:(6)βkFR=gk2gk−12,βkPRP=gkTgk−gk−1gk−12,βkHS=gkTgk−gk−1dk−1Tgk−gk−1,βkDY=gk2dk−1Tgk−gk−1,βkCD=−gk2gk−1Tdk−1,βkLS=−gkTgk−gk−1dk−1Tgk−1,where ⋅ stands for the Euclidean norm. These methods are identical when fx is a strongly convex quadratic function and the line search is exact, since the gradients are mutually orthogonal, and the parameters βk in these methods are equal. When applied to general nonlinear functions with inexact line searches, the behavior of these methods is marked different.It is well known that FR, DY, and CD methods have strong convergent properties, but they may not perform well in practice due to jamming. Moreover, although PRP, HS, and LS methods may not converge in general, they often perform better. Naturally, people try to devise some new methods, which have the advantages of these two kinds of methods. So far, various hybrid methods have been proposed (see [8–20]).In [14], Wei et al. gave a variant of the PRP method, WYL method for short, where the parameter βk is yielded by(7)βkWYL=gk2−gk/gk−1gkTgk−1gk−12.The above WYL method can be considered as the modification of the PRP method. It inherits the good properties of the PRP method, such as excellent numerical effect. Furthermore, Huang et al. [15] proved that the WYL method satisfies the sufficient descent condition and converges globally under the strong Wolfe line search (5) if the parameter satisfies σ<1/4.Yao et al. [16] gave a modification of the HS conjugate gradient method as follows:(8)βkMHS=gk2−gk/gk−1gkTgk−1dk−1Tgk−gk−1.Under the strong Wolfe line search (5) with the parameter σ<1/3, it has been shown that the MHS method can generate sufficient descent directions and converges globally for general objective functions.Jiang et al. [17] proposed a hybrid conjugate gradient method with(9)βkJHJ=gk2−max0,gk/dk−1gkTdk−1,gk/gk−1gkTgk−1dk−1Tgk−gk−1.Under the Wolfe line search (4), the method possesses global convergence and efficient numerical performance.In [18], Jiang et al. proposed a hybrid conjugate gradient method with(10)βkMDY=gk2maxμgkTdk−1,dk−1Tgk−gk−1.Under the parameterμ>1, it has been shown that the MDY method can generate sufficient descent directions and converges globally for general objective functions.In [19], Jiang et al. proposed a hybrid conjugate gradient method, denote it by JHS with(11)βkJHS=gk2−gk/gk−1gkTgk−1maxμgkTdk−1,dk−1Tgk−gk−1.Under the parameterμ>2, it has been shown that the JHS method can generate sufficient descent directions and converges globally for general objective functions.In this paper, we introduce a new hybrid choice for parameterβk. This motivation mainly comes from [18, 19]. For convenience, we call the iteration method a FW method as follows:(12)βkFW=gk2−max0,gk/gk−1gkTgk−1maxμgkTdk−1,dk−1Tgk−gk−1,where μ>1.It is easy to know thatβkFW=βkDY or βkFW=βkMDY or βkFW=βkJHS or βkFW=βkMHS, so βkFW is one of the hybrids of βkDY, βkMDY, βkJHS, and βkMHS. The proposed method has attractive property of satisfying the sufficient descent condition independent of any line search and attains global convergence if the step length is yielded by the Wolfe line search (4).This paper is organized as follows. In Section2, we give the details of our algorithm and discuss its sufficient descent property. In Section 3, we prove the global convergence of the proposed method with Wolfe line search (4). A number of numerical experiments comparing the proposed method with other conjugate gradient methods are given in Section 4. Finally, conclusion is given in Section 5.


## 2. Algorithm and Its Property

In this section, first, based on the discussed above, we describe our algorithm framework (Algorithm1) without fixed line search as follows.Algorithm 1: FW
Initialization. Given constants ε≥0,δ∈0,1, σ∈δ,1,μ>1 and 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 a suitable line search.Step 3. Let xk+1=xk+αkdk and compute gk+1=gxk+1 and βk+1FW by (12).Step 4. Let dk+1=−gk+1+βk+1FWdk. Set k:=k+1; go to Step 1.The following lemma states that the search direction in Algorithm1 is always sufficient descent depending on no line search.Lemma 1.
If the objective functionfx is continuously differentiable, let dk be generated by Algorithm 1. Then, gkTdk<0 holds for each k≥1.Proof.
We prove this lemma by induction. Fork=1, it is easy to know that g1Td1=g1T−g1=−g12<0. Assume that gk−1Tdk−1<0 holds for k−1 and k>2. Now we prove that gkTdk<0 holds for k.
IfgkTdk−1=0, then βkFW=gk2−max0,gk/gk−1gkTgk−1/−dk−1Tgk−1; furthermore, we have(13)gkTdk=gkT−gk+βkFWdk−1=−gk2+βkFWgkTdk−1=−gk2<0.
IfgkTdk−1≠0, we divide the proof into four following cases.(i)
IfgkTgk−1≤0 and μgkTdk−1≤dk−1Tgk−gk−1, then βkFW=gk2/dk−1Tgk−gk−1=βkDY by the definition of βkFW. Noticing that μgkTdk−1>0, dk−1Tgk−gk−1>0 holds.From (3) and (12), we have(14)gkTdk=gkT−gk+βkFWdk−1=−gk2+gk2dk−1Tgk−gk−1gkTdk−1=gk2dk−1Tgk−gk−1gk−1Tdk−1<0.(ii)
IfgkTgk−1≤0, μgkTdk−1>dk−1Tgk−gk−1, then from (12), one has βkFW=gk2/μgkTdk−1.Therefore, we obtain(15)gkTdk=gkT−gk+βkFWdk−1=−gk2+gk2μgkTdk−1gkTdk−1≤−gk2+gk2μgkTdk−1gkTdk−1=−1−1μgk2<0.(iii)
IfgkTgk−1>0 and μgkTdk−1≤dk−1Tgk−gk−1, then from (12), one knows(16)βkFW=gk2−gk/gk−1gkTgk−1dk−1Tgk−gk−1=βkMHS.NoticinggkTgk−1>0, we have 0<cosθk<1, where θk is the angle between gk and gk−1.Furthermore, we obtain(17)gkTdk=gkT−gk+βkFWdk−1=−gk2+gk2−gk/gk−1gkTgk−1dk−1TgkT−gk−1gkTdk−1=−gk2+gk2gkTdk−1−gk2cosθkgkTdk−1dk−1TgkT−gk−1=gk2gk−1Tdk−1−gk2cosθkgkTdk−1dk−1TgkT−gk−1<gk2gk−1Tdk−1−gk2cosθkgk−1Tdk−1dk−1TgkT−gk−1=gk21−cosθkgk−1Tdk−1dk−1TgkT−gk−1<0.(iv)
IfgkTgk−1>0 and μgkTdk−1>dk−1Tgk−gk−1, then from (12), one gets(18)βkFW=gk2−gk/gk−1gkTgk−1μgkTdk−1.
As in the case of (iii), we have(19)gkTdk=gkT−gk+βkFWdk−1=−gk2+gk2−gk/gk−1gkTgk−1μgkTdk−1gkTdk−1=−gk2+gk2−gk2cosθkμgkTdk−1gkTdk−1≤−gk2+gk21−cosθkμgkTdk−1gkTdk−1=−1−1−cosθkμgk2<0.
Therefore,gkTdk<0 holds for all k≥1.Lemma 2.
Letxk be generated by Algorithm 1. Then, for any k≥1, we can obtain the following relations:(20)0≤βkFW≤gkTdkgk−1Tdk−1.Proof.
From formula (12), it is easy to see that(21)βkFW=gk2−max0,gk/gk−1gkTgk−1maxμgkTdk−1,dk−1Tgk−gk−1≥0.
Now we are ready to proveβkFW≤gkTdk/gk−1Tdk−1 by considering the following four cases.(i)
IfgkTgk−1≤0 and μgkTdk−1≤dk−1Tgk−gk−1, then βkFW=gk2/dk−1Tgk−gk−1=βkDY.In view of Lemma1 and (14), we have(22)βkFW=gk2dk−1Tgk−gk−1=gkTdkgk−1Tdk−1.(ii)
IfgkTgk−1≤0, μgkTdk−1>dk−1Tgk−gk−1, then βkFW=gk2/μgkTdk−1.IfgkTdk−1>0, by the recurrence formula, we have(23)βkFW=gk2μgkTdk−1,1−μgkTdk−1<gk−1Tdk−1.Therefore, one gets(24)gkTdk=gkT−gk+βkFWdk−1=−gk2+gk2μgkTdk−1gkTdk−1=1−μgk2μgkTdk−1gkTdk−1<gk2μgkTdk−1gkTdk−1=βkFWgk−1Tdk−1.Dividing both sides of (24) by gk−1Tdk−1, it follows that(25)βkFW≤gkTdkgk−1Tdk−1.IfgkTdk−1<0, similarly, we can get that(26)βkFW=gk2−μgkTdk−1,1+μgkTdk−1<gk−1Tdk−1,gkTdk=gkT−gk+βkFWdk−1=−gk2+gk2−μgkTdk−1gkTdk−1=1+μgk2−μgkTdk−1gkTdk−1<gk2−μgkTdk−1gkTdk−1=βkFWgk−1Tdk−1.Dividing both sides of (26) by gk−1Tdk−1, one has(27)βkFW≤gkTdkgk−1Tdk−1.(iii)
IfgkTgk−1>0 and μgkTdk−1≤dk−1Tgk−gk−1, then βkFW=gk2−gk/gk−1gkTgk−1/dk−1Tgk−gk−1=βkMHS.From the above formula, we have(28)βkFW=gk2−gk/gk−1gkTgk−1dk−1Tgk−gk−1=gk21−cosθkdk−1Tgk−gk−1.Combining with (17), we get(29)βkFW≤gkTdkgk−1Tdk−1.(iv)
IfgkTgk−1>0 and μgkTdk−1>dk−1Tgk−gk−1, then βkFW=gk2−gk/gk−1gkTgk−1/μgkTdk−1.
Noticing thatgkTdk−1<μgkTdk−1+gk−1Tdk−1, we have from the above formula that(30)βkFW=gk21−cosθkμgkTdk−1.
So,(31)gkTdk=gkT−gk+βkFWdk−1=−gk2+gk21−cosθkμgkTdk−1gkTdk−1<−gk2+gk21−cosθkμgkTdk−1μgkTdk−1+gk−1Tdk−1=−cosθkgk2+gk21−cosθkμgkTdk−1gk−1Tdk−1<gk21−cosθkμgk−1Tdk−1gk−1Tdk−1=βkFWgk−1Tdk−1.
Dividing both sides of (31) by gk−1Tdk−1, we have(32)βkFW≤gkTdkgk−1Tdk−1.
The proof is complete.


## 3. Global Convergence of Algorithm

This section is devoted to the global convergence of algorithm framework under the Wolfe line search condition, i.e., the step lengthαk is yielded by condition (4). For this goal, we make the following basic assumptions in subsequent discussions.H 3.1fx is bounded from below on the level set Ω=x∈Rn|fx≤fx1, where x1 is the initial point.H 3.2 In some neighborhoodΩ1 of the level set Ω, fx is continuous differentiable, and its gradient gx is Lipschitz continuous, that is to say, for all x,y∈Ω1, there exists a constant L>0 such that(33)gx−gy≤Lx−y.Lemma 3.
Suppose that assumptions (H 3.1) and (H 3.2) hold. Letxk be generated by Algorithm 1, where the step length αk satisfies the Wolfe line search (4). Then, ∑k≥1gkTdk2/dk2<+∞.Proof.
In view of (4) and (33), we have(34)σ−1gkTdk≤dkTgk+1−gk≤αkLdk2.
Therefore, we get(35)αk≥σ−1LgkTdkdk2.
Combining (4) and (20), we can get that(36)fk−fk+1≥−δαkgkTdk≥−δσ−1LgkTdk2dk2=δ1−σLgkTdk2dk2.
Let us sum up the inequalities (36) for k=1,…. We obtain(37)∑k≥1fk−fk+1=f1−limk⟶∞fk≥∑k≥1δ1−σLgkTdk2dk2.
This inequality along with the assumption (H3.1) results in(38)∑k≥1gkTdk2dk2<+∞.
Therefore, Lemma3 holds.Theorem 1.
Suppose that Assumptions (H 3.1) and (H 3.2) hold. Consider iteratexk+1=xk+αkdk by Algorithm 1; if the direction dk is a descent direction and the step length αk satisfies the Wolfe line search (4), then limk⟶∞infgk=0.Proof.
We prove this theorem by contradiction. Iflimk⟶∞infgk≠0, in view of gk>0, there exists a constant c>0 such that gk≥c,∀k≥1. Again, from (3), it follows that dk+gk=βkFWdk−1. Squaring both sides of above equality, we have(39)dk2=βkFW2dk−12−2gkTdk−gk2.
Dividing both sides of (39) by gkTdk2 and in view of (20), it follows that(40)dk2gkTdk2=βkFW2dk−12gkTdk2−2gkTdk−gk2gkTdk2≤dk−12gk−1Tdk−12−2gkTdk−gk2gkTdk2=dk−12gk−1Tdk−12+1gk2−1gk2+gk2gkTdk22≤dk−12gk−1Tdk−12+1gk2.
Combining with (40), by a recurrence of relation gk≥c and d1=−g1, we have(41)dk2gkTdk2≤d12g1Td12+∑i=2k1gi2=∑i=1k1gi2.
Therefore, we have(42)gkTdk2dk2≥c2k.
Hence, by recurrence formula (42), we obtain(43)∑k≥1gkTdk2dk2≥∑k≥1c2k=+∞.
This is a contradiction to Lemma3. The proof is completed.


## 4. Numerical Results

In this part of the paper, we report some numerical experiments that indicate the efficiency of the proposed algorithm. To test and compare the computation effect of the proposed FW, a large number of testing problems from Morè et al. [21] are solved by the FW, MHS [16], MDY [18], and JHS [19]. In all conjugate gradient methods, the step length αk is yielded by the Wolfe line search (4). All codes were written in Matlab 7.5 and run on Dell with 2.90 GHz CPU processor, 8 GB RAM memory, and Windows 10 operating system. The parameters are set as follows: σ=0.2,δ=0.02, μ=10.75, and ε=10−6. We stop the iteration if one of the following conditions is satisfied: (1) gk≤ε=10−6; (2) the number of iteration Itr >1000. If condition (2) occurs, the method is deemed to fail for solving the corresponding test problem and denote it by F. The simulation results of the proposed method were efficient and robust as compared with hybrid conjugate gradient methods (FW, MHS, MDY, and JHS). The hybrid conjugate gradient methods are listed in Table 1. Here P denotes the abbreviation of the test problems, n denotes the dimension of the test problems, and Itr, NF, and NG denote the number of iteration, function evaluations, and gradient evaluations, respectively. TCpu denotes the computing time of CPU for computing the corresponding test problem (unit: seconds). To visualize the whole behaviour of the algorithms, we use the performance profiles proposed by Dolan and Morè [22] to compare the performance based on the CPU time, the number of function evaluation, the number of gradient evaluation, and the number of iteration, respectively. For each method, we plot the fraction P/τ of the problems for which the method is within a factor τ of the best time. The left side of the figure gives the percentage of the test problems for which a method is the fastest. Based on the theory of the performance profile above, four performance figures, i.e., Figures 1–4, can be generated according to Table 1. From the four figures, we can see that our methods perform effectively on the testing problems.Table 1
Test results of the FW method, MDY method, JHS method, and MHS method.
pnFWMDYJHSMHSINFNGTCpuINFNGTCpuINFNGTCpuINFNGTCpubadscp235850.018935850.014435850.108135850.0116beale21757290.02902162340.00942379400.01401960310.0239jensam225230.005425230.007925230.009125230.0098helix3634652450.0855796483390.12651137564010.2044704672260.1752bard33799580.0214861991220.090949161710.05384794610.0454gauss34950.01444950.03884950.01544950.0138meyer335650.018735650.015635650.017635650.0230gulf325240.011525240.013825240.016225240.0188box315120.016615120.014715120.016815120.0214wood41113351660.0865852451360.077414146900.0657852501350.0567kowosb41533322120.0452151801260.082115147950.05561053171820.0747osb1515120.010215120.011015120.014215120.0188biggs6865100.0210869120.00661295220.00871189200.0075osb2111789230.014728117400.01781693240.0136766100.0143pen11025870.015625870.014925870.021125870.0194pen1100210130.0132210130.0216735180.1244525160.0487pen120015120.011915120.025615120.021315120.0244pen1100015120.919215120.996415120.990215120.9578pen1150015122.066715122.276615122.079015122.1576pen1200015123.642115124.083615123.725015123.7133pen1300015128.271215129.209515128.197915128.5341pen15000151223.0663151225.5505151222.1556151223.6629pen21025230.016025230.017125230.015625230.0180pen25015120.016525230.026615120.021015120.0197vardim2427100.0024430110.0035525100.0034525100.0033vardim10015120.011915120.021815120.013115120.0116vardim50015120.077615120.102415120.098215120.1105vardim100015120.290815120.344115120.395115120.3326vardim200015120.995515121.040115121.059115121.0676vardim300015121.916215122.106915121.920415122.0107vardim400015123.111415123.484315123.301615123.3019vardim500015124.617515125.217515124.825715124.9972trig104280500.01304070450.01694173460.01824894600.0153trig5056101640.029449108650.053851112670.043652114680.0482trig15062110710.145154112690.196261113730.1620811851130.2364trig20054103650.228060124770.307267176850.3789682301020.3682ie1071580.023161370.039871580.031471580.0287ie100918100.192871690.205171480.13321121120.2035ie500818102.8779818103.2010818102.9477818102.9802ie10008181011.3304716911.25708181012.07978181011.9909ie20008181045.40758181050.2927716940.4006716942.0180ie400082111200.134482111216.910771910179.251771910195.2297trid1003674400.03503269360.05623369370.05443878430.0438trid5003374390.30263270380.30453271380.31253590470.3451band102158260.02292566310.00721856230.00842063270.0074band50015120.393015120.469215120.452315120.4562band5000151232.4417151237.1887151232.5321151233.9574lin21430.00611430.00911430.00471430.0046lin501430.00581430.00471430.00531430.0084lin5001430.04321430.06461430.05221430.0632lin10001430.22131430.21701430.19971430.1960lin15001430.42531430.46491430.36511430.3824lin20001430.69771430.86111430.71801430.8242lin30001431.61271431.97491431.66811431.6817lin50001434.77301435.38961434.81421434.8166lin122430.00862430.00182430.01342430.0096lin1101430.00291430.00341430.00421430.0065lin110066290.058066290.040866290.053066290.0598lin150035670.576835670.644035670.592135670.6223lin1100035652.146635652.559635652.194335652.3149lin1200035659.0047356510.909435659.049935659.8109lin13000356525.2678563830.5328563825.2772563827.4500lin042430.01112430.00962430.01422430.0138lin050035860.747935860.777935860.760435860.6715lin080035651.823235652.161435651.962835651.8111lin0100076293.362076293.695876293.640576493.3911lin02000356511.8533356514.5539356512.0432356512.2544lin02500356519.5770356523.3801356519.6448356522.1141lin03000357528.9680357533.4278357528.9657357530.2009Figure 1
Performance profiles with respect to CPU time (FW versus MDY, JHS, and MHS).Figure 2
Performance profile on the number of gradient evaluation (FW versus MDY, JHS, and MHS).Figure 3
Performance profile on the number of function evaluation (FW versus MDY, JHS, and MHS).Figure 4
Performance profile on the number of iteration (FW versus MDY, JHS, and MHS).


## 5. Conclusion

In this paper, we proposed a new hybrid conjugate gradient method for solving unconstrained optimization problems. The proposed method satisfied sufficient descent condition irrespective of the line searches condition. Moreover, the global convergence of the proposed method has been established under the Wolfe line search (4). Numerical experiments show the efficiency and robustness of the new algorithm in solving a collection of unconstrained optimization problems from [21].



---

*Source: 5597863-2021-02-23.xml*