# An Efficient Modified AZPRP Conjugate Gradient Method for Large-Scale Unconstrained Optimization Problem

Authors: Ahmad Alhawarat; Thoi Trung Nguyen; Ramadan Sabra; Zabidin Salleh
Journal: Journal of Mathematics
 (2021)

---

## Abstract

To find a solution of unconstrained optimization problems, we normally use a conjugate gradient (CG) method since it does not cost memory or storage of second derivative like Newton’s method or Broyden–Fletcher–Goldfarb–Shanno (BFGS) method. Recently, a new modification of Polak and Ribiere method was proposed with new restart condition to give a so-call AZPRP method. In this paper, we propose a new modification of AZPRP CG method to solve large-scale unconstrained optimization problems based on a modification of restart condition. The new parameter satisfies the descent property and the global convergence analysis with the strong Wolfe-Powell line search. The numerical results prove that the new CG method is strongly aggressive compared with CG_Descent method. The comparisons are made under a set of more than 140 standard functions from the CUTEst library. The comparison includes number of iterations and CPU time.


---

## Body

## 1. Introduction

The conjugate gradient (CG) method aims to find a solution of optimization problems without constraint. Suppose that the following optimization problem is considered:(1)minfx,x∈ℝn,where f:ℝn⟶ℝ is continuous, the function is differentiable, and the gradient ∇fx is available. The iterative method is given by the following sequence:(2)xk+1=xk+αkdk,k=1,2,…,where xk is the starting point and αk>0 is a step length. The search direction dk of the CG method is defined as follows:(3)dk=−∇fx,ifk=1,−∇fx+βkdk−1,ifk≥2,where ∇fx=gxk and βk is a parameter.To obtain the step length, we normally use the inexact line search, since the exact line search which is defined as follows,(4)fxk+αkdk=minfxk+αdk,α>0,requires many iterations to obtain the step length. Normally, we use the strong version of Wolfe-Powell (SWP) [1, 2] line search which is given by(5)fxk+αkdk≤fxk+δαkgkTdk,(6)∇fxk+αkdkTdk≤σgkTdk,where 0<δ<σ<1.The weak Wolfe-Powell (WWP) line search is defined by (5) and(7)∇fxk+αkdkTdk≥σgkTdk,where ∇f=gk=gxk. The famous parameters of βk are the Hestenes–Stiefel (HS) [3], Fletcher–Reeves (FR) [4], and Polak–Ribière–Polyak (PRP) [5] formulas, which are given by(8)βkHS=gkTykdk−1Tyk,βkFR=gkTgkgk−12,βkPRP=gkTykgk−12,where yk=gk−gk−1.Powell [6] shows that there exists a nonconvex function such that the PRP method does not globally converge. Gilbert and Nocedal [7] show that if βkPRP+=max0,βkPRP with the WWP and the descent property is satisfied, then it is globally convergent.Al-Baali [8] proved that the CG method with FR coefficient is convergent with SWP line search when σ≤1/2. Hager and Zhang [9, 10] presented a new CG parameter with descent property, i.e., gkTdk≤−7/8gk2. This formula is given as follows:(9)βkHZ=maxβkN,ηk,where βkN=1/dkTykyk−2dkyk2/dkTykTgk; ηk=−1/dkminη,gk; and η>0 is a constant. In the numerical experiments, they set η=0.01 in (9). Al-Baali et al. [11] compared βkHZ with a new three-term CG method (G3TCG).Regarding the speed, memory requirements, number of iterations, function evaluations, gradient evaluations, and robustness to solve unconstrained optimization problems which have prompted the development of the CG method, the readers are advised to refer references [10–15] for more information on these new formulas.


## 2. The New Formula and the Algorithm

Alhawarat et al. [15] presented the following simple formula:(10)βkAZPRP=gk2−μkgkTgk−1gk−12,ifgk2>μkgkTgk−1,0,otherwise.Dai and Laio [12] presented the following formula:(11)βkDL+=maxβkHS,0−tgkTsk−1dk−1Tyk−1,where sk−1=xk−xk−1 and t≥0.The new formula is a modification ofβkAZPRP and βkDL+ is defined as follows:(12)βkA=gk2−μkgkTsk−1gk−12,ifgk2>μkgkTsk−1,−tgkTsk−1dk−1Tyk−1,otherwise,where μk=sk−1/yk−1 and t>0.We obtain the following relations (Algorithm1):Algorithm 1: Steps of CG method with new modification to obtain the stationary point of functions.(13)βkA≥0,βkA≤gk2−μkgkTsk−1gk−12≤gk2gk−12=βkFR.


## 3. Convergence Analysis of CoefficientβkA with CG Method

Assumption 1.
(A)
The level setΨ=x|fx≤fx1 is bounded, that is, a positive constant T exists such that(14)x≤T,∀x∈Ψ.(B)
In some neighbourhoodsN of Ψ, f is continuous and the gradient is available and its gradient is Lipschitz continuous; that is, for all x,y∈N, there exists a constant L>0 such that(15)gx−gy≤Lx−y.
This assumption shows that there exists a positive constantB such that(16)gu≤B,∀u∈N.
The descent condition(17)gkTdk≤−gk2,∀k≥1.
(17) plays an important role in the CG method. The sufficient descent condition proposed by Al-Baali [8] is a modification of (17) as follows:(18)gkTdk≤−cgk2,∀k≥1,where c∈0,1. Note that the general form of the sufficient descent condition is (18) with c>0.


### 3.1. Global Convergence forβkA with the SWP Line Search

The following theorem demonstrates thatβkA ensures that the sufficient descent condition (21) is satisfied with the SWP line search.The following theorem shows thatβkA satisfies the descent condition. The proof is similar to that presented in [8].Theorem 1.
Letgk and dk be generated using (2), (3), and βkA=gk2−μkgkTsk−1/gk−12, where αk is computed by the SWP line search (5) and (6). If σ∈0,1/2, then the sufficient descent condition (18) holds.Algorithm1 shows the steps to obtain the solution of optimization problem using strong Wolfe-Powell line search.Descent condition is (18) with c > 0.Proof.
By multiplying () bygkT, we obtain(19)gkTdk=gkT−gkT+βkdk−1=−gk2+βkgkTdk−1.
Divide (19) by gk2; using(20)∇fxk+αkdkTdk≤σgkTdk,and (12), we obtain(21)−1+σgk−1Tdk−1gk−12≤gkTdkgk2≤−1−σgk−1Tdk−1gk−12.
From (3), we obtain g1Td1=−g12. Assume that it is true until k−1, i.e., giTdi<0, for i=1,2,…,k−1. Repeating the process for (21), we obtain(22)−∑j=0k−1σj≤gkTdkgk2≤−2+∑j=0k−1σj.
As(23)∑j=0k−1σj<1−σk1−σ,hence,(24)−1−σk1−σ≤gkTdkgk2≤−2+1−σk1−σ,and when σ≤1/2, we obtain 1−σk/1−σ<2. Let c=2−1−σk/1−σ, then(25)c−2≤gkTdkgk2≤−c.
The proof is complete.Theorem 2.
Letgk and dk be obtained by using (2), (3), and βkA=−tgkTsk−1/dk−1Tyk−1 where αk is computed by SWP line search (5) and (6), then the descent condition holds.Proof.
(26)βkDL−HS=−μkgkTsk−1dk−1Tyk−1.
By multiplying (3) by gkT, and substituting βkA, we obtain
(27)gkTdk=−gk2−μkαk−1gkTdk−1dk−1Tyk−1gkTdk−1=−gk2−μkαk−1gkTdk−12dk−1Tyk−1<0,which completes the proof.
Zoutendijk [16] presented a useful lemma for global convergence property of the CG method. The condition is given as follows.Lemma 1.
Let Assumption1 hold and consider any method in the form of (2) and (3), where αk is obtained by the WWP line search (6) and (7), in which the search direction is descent. Then, the following condition holds: (28)∑k=0∞gkTdk2dk2<∞.Theorem 3.
Suppose Assumption1 holds. Consider any form of equations (2) and (3), with the new formula (12), in which αk is obtained from the SWP line search (5) and (6) with σ≤1/2. Then,(29)liminfk⟶∞gk=0.
The proof is similar to that presented in [8].Proof.
We will prove the theorem by contradiction. Assume that the conclusion is not true, then a constantε>0 exists such that(30)gk≥ε,∀k≥1.
Squaring both sides of equation (3), we obtain(31)dk2=gk2−2βkgkTdk−1+βk2dk−12.
Divide (31) by gk4, we get(32)dk2gk4=1gk2−2βkgkTdk−1gk4+βk2dk−12gk4.
Using (6), (12), and (32), we obtain(33)dk2gk4≤dk−12gk−14+1gk2+2σgk−1Tdk−1gk−12gk2≤dk−12gk−14+1+2σ2−cgk2.
Repeating the process for (33) and using the relationship 1/g1=1/d1 yields(34)dk2gk4≤1+2σ2−c∑i=1k1gi2.
From (33), we obtain(35)gk4dk2≥ε2k1+2σ2−c.
Therefore,(36)∑k=0∞gk4dk2=∞.
This result contradicts (32), thus liminfk⟶∞gk=0. The proof is complete.


## 3.1. Global Convergence forβkA with the SWP Line Search

The following theorem demonstrates thatβkA ensures that the sufficient descent condition (21) is satisfied with the SWP line search.The following theorem shows thatβkA satisfies the descent condition. The proof is similar to that presented in [8].Theorem 1.
Letgk and dk be generated using (2), (3), and βkA=gk2−μkgkTsk−1/gk−12, where αk is computed by the SWP line search (5) and (6). If σ∈0,1/2, then the sufficient descent condition (18) holds.Algorithm1 shows the steps to obtain the solution of optimization problem using strong Wolfe-Powell line search.Descent condition is (18) with c > 0.Proof.
By multiplying () bygkT, we obtain(19)gkTdk=gkT−gkT+βkdk−1=−gk2+βkgkTdk−1.
Divide (19) by gk2; using(20)∇fxk+αkdkTdk≤σgkTdk,and (12), we obtain(21)−1+σgk−1Tdk−1gk−12≤gkTdkgk2≤−1−σgk−1Tdk−1gk−12.
From (3), we obtain g1Td1=−g12. Assume that it is true until k−1, i.e., giTdi<0, for i=1,2,…,k−1. Repeating the process for (21), we obtain(22)−∑j=0k−1σj≤gkTdkgk2≤−2+∑j=0k−1σj.
As(23)∑j=0k−1σj<1−σk1−σ,hence,(24)−1−σk1−σ≤gkTdkgk2≤−2+1−σk1−σ,and when σ≤1/2, we obtain 1−σk/1−σ<2. Let c=2−1−σk/1−σ, then(25)c−2≤gkTdkgk2≤−c.
The proof is complete.Theorem 2.
Letgk and dk be obtained by using (2), (3), and βkA=−tgkTsk−1/dk−1Tyk−1 where αk is computed by SWP line search (5) and (6), then the descent condition holds.Proof.
(26)βkDL−HS=−μkgkTsk−1dk−1Tyk−1.
By multiplying (3) by gkT, and substituting βkA, we obtain
(27)gkTdk=−gk2−μkαk−1gkTdk−1dk−1Tyk−1gkTdk−1=−gk2−μkαk−1gkTdk−12dk−1Tyk−1<0,which completes the proof.
Zoutendijk [16] presented a useful lemma for global convergence property of the CG method. The condition is given as follows.Lemma 1.
Let Assumption1 hold and consider any method in the form of (2) and (3), where αk is obtained by the WWP line search (6) and (7), in which the search direction is descent. Then, the following condition holds: (28)∑k=0∞gkTdk2dk2<∞.Theorem 3.
Suppose Assumption1 holds. Consider any form of equations (2) and (3), with the new formula (12), in which αk is obtained from the SWP line search (5) and (6) with σ≤1/2. Then,(29)liminfk⟶∞gk=0.
The proof is similar to that presented in [8].Proof.
We will prove the theorem by contradiction. Assume that the conclusion is not true, then a constantε>0 exists such that(30)gk≥ε,∀k≥1.
Squaring both sides of equation (3), we obtain(31)dk2=gk2−2βkgkTdk−1+βk2dk−12.
Divide (31) by gk4, we get(32)dk2gk4=1gk2−2βkgkTdk−1gk4+βk2dk−12gk4.
Using (6), (12), and (32), we obtain(33)dk2gk4≤dk−12gk−14+1gk2+2σgk−1Tdk−1gk−12gk2≤dk−12gk−14+1+2σ2−cgk2.
Repeating the process for (33) and using the relationship 1/g1=1/d1 yields(34)dk2gk4≤1+2σ2−c∑i=1k1gi2.
From (33), we obtain(35)gk4dk2≥ε2k1+2σ2−c.
Therefore,(36)∑k=0∞gk4dk2=∞.
This result contradicts (32), thus liminfk⟶∞gk=0. The proof is complete.


## 4. Numerical Results

To investigate the effectiveness of the new parameter, several test problems in Table1 from CUTEst [17] are chosen. We performed a comparison with the CG_Descent 5.3 based on the CPU time and the number of iterations. We employed the SWP line search with the line as mentioned in [1, 2] with δ=0.01 and σ=0.1. The modified CG_Descent 6.8 where the memory (mem) equals zero is employed to obtain all results. The code can be downloaded from Hager web pagehttp://users.clas.ufl.edu/hager/papers/Software/.Table 1
The test functions.
CG_Descent 5.3βkAFunctionDimensionNumber of iterationsCPU timeNumber of iterationsCPU timeAKIVA2100.0280.02ALLINITU4120.0290.02ARGLINA20010.0210.02ARGLINB20050.0260.11ARWHEAD500070.0260.03BARD3160.02120.02BDQRTIC50001360.581610.75BEALE2150.02110.02BIGGS66270.02240.02BOX33110.02100.02BOX100080.0870.08BRKMCC250.0250.02BROWNAL20090.0290.02BROWNBS2130.02100.02BROWNDEN4160.02160.02BROYDN7D500014115.47640.37BRYBND5000850.38390.22CHAINWOO40003180.8663791.08CHNROSNB502870.023400.02CLIFF2180.02100.02COSINE10000110.19140.26CRAGGLVY50001030.451040.48CUBE2320.02170.02CURLY101000047808173.742454145.16CURLY201000066587383.9467279366.03CURLY301000079030639.6374375509.59DECONVU634002.00E − 022270.02DENSCHNA290.0260.02DENSCHNB270.0260.02DENSCHNC2120.02110.02DENSCHND3470.02140.02DENSCHNE3180.02120.02DENSCHNF280.0290.02DIXMAANA300070.0260.02DIXMAANB300060.0260.02DIXMAANC300060.0260.02DIXMAAND300070.0280.02DIXMAANE30002220.332180.33DIXMAANF30001610.131160.09DIXMAANG30001570.121730.14DIXMAANH30001730.221900.2DIXMAANI300038564.2531603.34DIXMAANJ30003270.363600.39DIXMAANK30002830.284160.36DIXMAANL30002370.23990.36DIXON3DQ100001000019.121000019.12DJTL2820.02750.02DQDRTIC500050.0250.02DQRTIC5000170.03150.03EDENSCH2000260.03320.05EG2100050.0230.02EIGENALS255010083178.367247133.4EIGENBLS25501530123718846290.3EIGENCLS265210136174.1911152186.86ENGVAL15000270.06230.12ENGVAL23260.02260.02ERRINROS503800.02955042.36EXPFIT2130.0290.02EXTROSNB100038081.2523700.87FLETCBV2500010.0210.02FLETCHCR10001520.05840.05FMINSRF256253461.09E + 004851.4FMINSURF56254731.515421.64FREUROTH5000250.11290.19GENROSE50010780.1720980.45GROWTHLS31560.021090.02GULF3370.02330.02HAIRY2360.02170.02HATFLDD3200.02170.02HATFLDE3300.02130.02HATFLDFL3390.02210.02HEART6LS66840.023750.02HEART8LS82490.022530.02HELIX3230.02230.02HIELOW3140.02130.05HILBERTA220.0220.02HILBERTB1040.0240.02HIMMELBB2100.0240.02HIMMELBF4260.02230.02HIMMELBG280.0270.02HIMMELBH270.0250.02HUMPS2520.02450.02JENSMP2150.02120.02JIMACK3544983141182.2572971030.3KOWOSB4170.02160LIARWHD5000210.03150.05LOGHAIRY2270.02260.02MANCINO100110.08110.08MARATOSB211450.025890.02MEXHAT2200.02140.02MOREBV50001610.411610.38MSQRTALS102429058.6427889.08MSQRTBLS102422806.9121816.84NCB20B500203546.36418170.16NCB20501087911.8395913NONCVXU25000661015.89637915.92NONDIA500070.0370.03NONDQUAR500019422.4530583.88OSBORNEA5940.02820.02OSBORNEB11620.02570.02PALMER1C8110.02120.02PALMER1D7110.02100.02PALMER2C8110.02110.02PALMER3C8110.02110.02PALMER4C8110.02110.02PALMER5C660.0260.02PALMER6C8110.02110.02PALMER7C8110.02110.02PALMER8C8110.02110.02PARKCH1567229.4582339.39PENALTY11000280.02410.02PENALTY22001910.052000.03PENALTY3200991.78881.98POWELLSG5000260.02270.05POWER100003720.765431.2QUARTC5000170.03150.02ROSENBR2340.02280.02S308280.0270.02SCHMVETT5000430.23400.27SENSORS100210.25500.8SINEVAL2640.02460.02SINQUAD5000140.09150.08SISSER260.0250.02SNAIL21000.02610.02SPARSINE500018358732132883SPARSQUR10000280.31350.98SPMSRTLS49992030.592190.61SROSENBR5000110.0290.03STRATEC1046219.981706.23TESTQUAD500015771.52E + 0015731.42TOINTGOR501350.021200.02TOINTGSS500040.0250.02TOINTPSP501430.021570.02TOINTQOR50290.02290.02TQUARTIC5000140.03110.03TRIDIA50007820.847831.11VAREIGVL230.02240.02VIBRBEAM501380.02980.02WATSON8490.02610.02WOODS12220.06220.03YFITU4000840.02680.02ZANGWIL2310.0210.02The CG_Descent 5.3 results are obtained by run CG_Descent 6.8 with memory which equals zero. The host computer is an AMD A4-7210 with RAM 4 GB. The results are shown in Figures1 and 2 in which a performance measure introduced by Dolan and More [18] was employed. As shown in Figure 1, formula A strongly outperforms over CG_Descent in number of iterations. In Figure 2, we notice that the new CG formula A is strongly competitive with CG_Descent.Figure 1
Performance measure based on the number of iterations.Figure 2
Performance measure based on the CPU time.


### 4.1. Multimodal Function with Its Graph

In this section, we present six-hump camel back function, which is a multimodal function to test the efficiency of the optimization algorithm. The function is defined as follows:(37)functions:⋅fx=4−2.1x12+x143x12+x1x2+−4+4x22x22.The number of variables (n) equals 2. This function has six local minima, with two of them being global. Thus, this function is a multimodal function usually used to test global minima. Global minima are x1∗=−0.0898,0.7126 and x2∗=0.0898,−0.7126. The function value is fx∗=−1.0316. As its name describes, this function looks like the back of an upside down camel with six humps (see Figure 3 for a three-dimensional graph); for more information about two-dimensional functions, the reader can refer to [19].Figure 3
Six-hump camel back function in 3D.Finally, note that CG method can be applied in image restoration problems and neural network and others. For more information, the reader can refer to [20, 21].


## 4.1. Multimodal Function with Its Graph

In this section, we present six-hump camel back function, which is a multimodal function to test the efficiency of the optimization algorithm. The function is defined as follows:(37)functions:⋅fx=4−2.1x12+x143x12+x1x2+−4+4x22x22.The number of variables (n) equals 2. This function has six local minima, with two of them being global. Thus, this function is a multimodal function usually used to test global minima. Global minima are x1∗=−0.0898,0.7126 and x2∗=0.0898,−0.7126. The function value is fx∗=−1.0316. As its name describes, this function looks like the back of an upside down camel with six humps (see Figure 3 for a three-dimensional graph); for more information about two-dimensional functions, the reader can refer to [19].Figure 3
Six-hump camel back function in 3D.Finally, note that CG method can be applied in image restoration problems and neural network and others. For more information, the reader can refer to [20, 21].


## 5. Conclusions

In this study, a modified version of the CG algorithm (A) is suggested and its performance is investigated. The modified formula is restarted based on the value of the Lipchitz constant. The global convergence is established by using SWP line search. Our numerical results show that the new coefficient produces efficient and competitive results compared with other methods, such as CG_Descent 5.3. In the future, an application of the new version of CG method will be combined with feed-forward neural network (back-propagation (BP) algorithm) to improve the training process and produce fast training multilayer algorithm. This will help in reducing time needed to train neural network when the training samples are massive.



---

*Source: 6692024-2021-04-26.xml*