# A Convex Combination between Two Different Search Directions of Conjugate Gradient Method and Application in Image Restoration

Authors: Ahmad Alhawarat; Zabidin Salleh; Ibtisam A. Masmali
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

The conjugate gradient is a useful tool in solving large- and small-scale unconstrained optimization problems. In addition, the conjugate gradient method can be applied in many fields, such as engineering, medical research, and computer science. In this paper, a convex combination of two different search directions is proposed. The new combination satisfies the sufficient descent condition and the convergence analysis. Moreover, a new conjugate gradient formula is proposed. The new formula satisfies the convergence properties with the descent property related to Hestenes–Stiefel conjugate gradient formula. The numerical results show that the new search direction outperforms both two search directions, making it convex between them. The numerical result includes the number of iterations, function evaluations, and central processing unit time. Finally, we present some examples about image restoration as an application of the proposed conjugate gradient method.


---

## Body

## 1. Introduction

The conjugate gradient (CG) method is widely used to solve large-scale unconstrained optimization problem. Moreover, it can be applied in many fields, such as neural network, medical science, engineering, and image restoration. We consider the following problem:(1)minfx,x∈ℝn,where f:ℝn⟶ℝ is continuous, and its derivative is available. A sequence of iterations xk generated by the CG method is given as follows:(2)xk+1=xk+αkdk,k=1,2,…,where xk is the current point and αk>0 is a step size offered by a line search. The search direction dk is given by the following equation:(3)dk=−gk,ifk=1,−gk+βkdk−1,ifk≥2,where gk=gxk and βk is known as the CG formula.To find the step sizeαk, we usually employ Wolfe or strong Wolfe-Powell line search [1, 2], where the latter is defined as follows:(4)fxk+αkdk≤fxk+δαkgkTdk,and(5)gxk+αkdkTdk≤σgkTdk,with 0<δ<σ<1.The weak Wolfe-Powell (WWP) line search is defined by equation (4) and the following equation:(6)gxk+αkdkTdk≥σgkTdk.The most well-known formulas forβk methods, for example, Hestenes–Stiefel (HS) [3], Polak–Ribiere–Polyak (PRP) [4], Liu and Storey (LS) [5], Fletcher–Reeves (FR) [6], Fletcher (CD) [7], and Dai and Yuan (DY) [8], are given as follows, respectively:(7)βkHS=gkTyk−1dk−1Tyk−1,βkPRP=gkTyk−1gk−12,βkLS=−gkTyk−1dk−1Tgk−1,βkFR=gk2gk−12,βkCD=−gk2dk−1Tgk−1,βkDY=gk2dk−1Tgk−1,where gk=gxk and yk−1=gxk−gxk−1.The global convergence properties of the FR method were investigated by [9]. The global convergence of the PRP method for convex objective function under exact line search was proved by [4]. Later, Powell [10] gave a counterexample showing the existence of a nonconvex function in which PRP and HS can cycle infinitely without getting a solution. Powell suggested the importance to achieve the global convergence of the PRP and HS methods, which should not be negative. Moreover, Gilbert and Nocedal [11] proved that nonnegative PRP, i.e., βk=maxβkPRP,0, is globally convergent under complicated line searches.Besides, Hager and Zhang [12] suggested a new CG parameter satisfying the descent property (refer to equation (43)) for any inexact line search with gkTdk≤−7/8gk2. This new CG parameter satisfies the global convergence properties when the Wolfe or approximate Wolfe line search is employed. This formula is given as follows:(8)βkHZ=maxβkN,ηk,where βkN=1/dkTykyk−2dkyk2/dkTykTgk, ηk=−1/dkminη,gk, and η>0 is a constant. In the numerical experiments, η=0.01 was fixed in equation (8). Note that equation (8) is known as CG-Descent 5.3. Al-Baali et al. [13] compared between βkHZ and the (G3TCG) method using extensive choices of CG parameters.Apart from that, Wei et al. [14] proposed a nonnegative formula referred to as the WYL coefficient defined as follows:(9)βkWYL=gk2−gk/gk−1gkTgk−1gk−12.This parameter is similar to the PRP coefficient, possesses global convergence with both an exact line and inexact line searches, and provides a sufficient descent condition. Many modifications of the WYL coefficient have been suggested, including(10)βkVHS=gk2−gk/gk−1gkTgk−1dk−1Tgk−gk−1,βkNPRP=gk2−gk/gk−1gkTgk−1gk−12,which were presented in [15, 16], respectively.In addition, Alhawarat et al. [17] presented the following simple formula:(11)βkAZPRP=gk2−μkgkTgk−1gk−12,ifgk2>μkgkTgk−1,0,otherwise,where ⋅ represents the Euclidean norm, while μk is defined as follows:(12)μk=xk−xk−1yk.Using the quasi-Newton method, the BFGS method, the limited memory (LBFGS) method, and equation (3), Dai and Liao [18] proposed the following conjugacy condition:(13)dkTyk−1=−tgkTsk−1,where sk−1=xk−xk−1and t≥0. In the case of t=0, equation (13) becomes the classical conjugacy condition. Moreover, using equations (3) and (13), Dai and Liao [18] proposed the following CG formula, given by(14)βkDL=gkTyk−1dk−1Tyk−1−tgkTsk−1dk−1Tyk−1.However,βkDL is not a nonnegative parameter. Dai and Liao [18] expressed βkDL as follows:(15)βkDL+=max0,gkTyk−1dk−1Tyk−1−tgkTsk−1dk−1Tyk−1.Also, Dai and Liao proposed the CG formula as follows:(16)βkZPRP=gkTyk−1maxμdk−1yk−1,gk−12,where μ>0.Andrei [19] proposed a useful book about nonlinear conjugate gradient methods for unconstrained optimization problems. The main chapters are linear conjugate gradient methods, standard conjugate gradient methods, acceleration of conjugate gradient methods, hybrid, modifications of the standard scheme, memoryless BFGS preconditioned, and three-term. Mishra et al. [20] presented a q-Polak–Ribière–Polyak conjugate gradient algorithm for unconstrained optimization problems. A transformation of the accelerated double step size model for unconstrained optimization, which supports our idea in Section 2, was presented in [21, 22]. Petrović et al. [23] presented a note on the hybridization process applied on transformed double step size model based on one specific accelerated gradient iteration. Alhawarat et al. [24] presented very useful hybrid conjugate gradient method with the strong Wolfe-Powell line search. Finally, Ahmad et al. [25] presented a developed version from βkAZPRP for large-scale unconstrained optimization problem.The paper is organized as follows. Section2 describes the search direction and the algorithm, while Section 3 introduces the convergence analysis of the CG algorithm with the new coefficientβk1. Moreover, Section 4 describes numerical results and discussion for some results with application in image restoration.


## 2. The New Search Direction and the Algorithm

The motivation to propose equation (17) is to use direction determination as a convex combination of two directions, leading to the advantages of using both directions in convergence analysis and numerical experiments. Based on Assumption 1, we proposed a convex combination between two different search directions, where every search direction has its own CG formula. The new search direction is defined as follows:(17)dk=λdk1+1−λdk2,where(18)0≤λ≤1,dk1=−gk,ifk=1,−gk+βk1dk−11,ifk≥2,and(19)dk2=−gk,ifk=1,−gk+βk2dk−12,ifk≥2.We chooseβk1 and βk2 for equations (18) and (19) as follows:(20)βk1=gk2−μkgkTgk−1dk−1T1yk−1,ifgk2>μkgkTgk−1,−tgkTsk−1dk−1T1yk−1,otherwise,and(21)βk2=βkCG−DESCENT5.3,where ⋅ represents the Euclidean norm. Note that μk is defined as follows:(22)μk=xk−xk−1yk.We chooseβkCG−DESCENT5.3 because it is a well-known CG formula satisfying the decent condition without any line search with gkTdk2≤−7/8gk2. This will be portrayed later in Theorem 3. Note that the reader can use any CG formula that satisfies the convergence properties descent condition. In addition, we can extend dk=λdk1+1−λdk2to the following form given by(23)dk=λ1dk1+λ2dk2+⋯+λndkn,where∑i=1nλi=1.The following lemma corresponds to Lemma 3.1 in [17]; thus, we omit the proof.Lemma 1.
Let Assumption1 holds, and the Beale-Powell restart condition is violated for a nonrestart search direction; then, gk2>μkgkTgk−1 holds.
The following algorithm (Figure1) illustrates the steps of the CG method using equation (17) to obtain the solution of an optimization problem.
In Figure1, note that, after the step k=k+1, the iterates xk=xk+1 takes place after every iteration. The other iterations are updated in a similar manner as xk.Figure 1
The algorithm of CG method.


## 3. The Convergence Analysis of the CG Algorithm with the New Coefficientβk1 and New Search Direction

Assumption 1.
(a)
The level setΩ=x|fx≤fx1 is bounded, implying that a positive constant M exists such that x≤M, ∀x∈Ω.(b)
In some neighbourhoodNof Ω, fis continuous and the derivative is available. In addition, its gradient is Lipschitz continuous, implying for all x,y∈N, and there exists a constant L>0 such that(24)gx−gy≤Lx−y.This assumption implies that there exists a positive constantB such that(25)gu≤B,∀u∈N.The descent condition(26)gkTdk≤−gk2,∀k≥1,plays an important role in the CG method. Al-Baali [9] modified inequality (26) to the following form and used it to prove the FR method:(27)gkTdk≤−cgk2,∀k≥1,wherec∈0,1. Equation (27) is the sufficient descent condition. Note that the general form of the sufficient descent condition is given by inequality (27) with c>0.Lemma 2.
Suppose the sequencesxk and dk are proposed by using equations (2) and (18), where αk is computed by the SWP line search in equations (4) and (5). Then, βk1≥0, and βk1≤gk2/dk−1T1yk−1.Proof.
Sinceβk1=gk2−μkgkTgk−1/dk−1T1yk−1,ifgk2>μkgkTgk−1 and by using equation (5), we obtain dk−1T1yk−1≥0. Thus, βk1≥0. On the contrary, it is clear to note that βk1≤gk2/dk−1T1yk−1 since gk2>μkgkTgk−1.
The next theorem demonstrates that the CG method withβk1 has a sufficient descent condition.Theorem 1.
Suppose the sequencesxk and dk are proposed by using equations (2) and (18), where αk is computed by the SWP line search in equations (4) and (5). If σ∈0,1/2, then the sufficient descent condition in equation (27) holds with βk1.Proof.
By multiplying equation (18) with gkT, we obtain(28)gkTdk1=gkT−gkT+βk1dk−1T1=−gk2+βk1gkTdk−1T1.Case 1
(29)gkTdk−1T1≤0.Using Lemma2, we obtain(30)gkTdk−1T1=gkT−gkT+βk1dk−1T1=−gk2+βk1gkTdk−1T1<0.Thus, the descent condition is satisfied.Case 2
(31)gkTdk−1T1>0.We then divide both sides of equation (28) by gk2. Now, using Lemma 2 to substitute βk1≤gk2/dk−1T1yk−1,and by using equation (5), we obtain(32)gkTdk−11gk2≤−1+gk2dk−1T1gk−gk−1gkTdk−11gk2≤−1+σgk−1Tdk−11dk−1T1gk−gk−1≤−1+σgk−1Tdk−111−σgk−1Tdk−11=−1+σ1−σ.Let(33)c=1−σ1−σ,then(34)gkTdkT1≤−cgk2.
Then, we have the following two cases.Theorem 2.
Let sequencesxk and dk be obtained by using equations (2) and (18), which is computed by SWP line search in equations (4) and (5); then, the descent condition holds for dk with βk1=−tgkTsk−1/dk−1T1yk−1.Proof.
By multiplying equation (3) with gkTand by substituting with βk1, we obtain(35)gkTdk1=−gk2−tgkTsk−1dk−1T1yk−1gkTdk−11=−gk2−tαkgkTdk−1T12dk−1T1yk−1≤−gk2.
Letc=1, and we obtain(36)gkTdk1≤−cgk2,
which completes the proof.Theorem 3.
Suppose the sequencesxk and dk are generated using equations (2) and (17), where αk is generated by the SWP line search in equations (4) and (5) or any line search. If gkTdk1 and gkTdk2 are descent, then the sufficient descent condition (27) holds with equation (17).Proof.
Multiplying equation (17) by gkT yields(37)gkTdk=λgkTdk1+1−λgkTdk2.
From Theorem1, we obtain(38)gkTdk1≤−cgk2,
and from [12], we obtain(39)gkTdk2≤−78gk2.
Using equation (37), we now have(40)gkTdk≤−cλgk2+−1+λ78gk2≤−78gk2+λ78gk2−cλgk2.
Since(41)0≤λ≤1,
we obtain(42)gkTdk≤−cgk2.
The following lemma, which is referred to as the Zoutendijk condition [24], is useful for analyzing the global convergence property of the CG method.Lemma 3.
Let Assumption1 holds. Consider any method in the form of equations (2) and (3), where αk satisfies the WWP line search, and the search direction is descent. Then, the following condition holds:(43)∑k=0∞gkTdk2dk2<∞.
In addition, equation (43) holds for the exact and SWP line searches. The proof is shown in [24]. From (43), we conclude that the Zoutendijk condition (43) implies the following form:(44)∑k=0∞gk4dk2<∞.
Dai et al. [18] presented the following theorem, which is also useful to prove the global convergence properties of the CG method.Theorem 4.
Suppose that Assumption1 holds. Consider any conjugate gradient method in the form of equations (2) and (3), where dk is a descent direction and αk is obtained from the strong Wolfe line search. If(45)∑k≥1∞1dk2=∞,then(46)liminfk⟶∞gk=0.
The following property, called Property1, is presented by [26]. This property is useful to obtain the convergence property of the CG method.Property 1.
(47)0<γ≤gk≤γ¯,for all k≥1. Then, the CG method has Property 1 if there exist constants b>1 and λ>0, such that, for all k, whereby, for βk≤b and sk≤λ, we obtainβk≤1/2b.(48)zk+vk≤Lwk+vk,where(49)vk=1Lgk−gk−1,zk=gk−1Lgk−1.
Suppose the method of forms (2) and (3). Also, suppose that
The following lemma shows thatβk1 satisfies Property 1 if μk≥1. Otherwise, μk should be sufficiently small to obtain a sufficiently large Lthat satisfies the following inequality:Lemma 4.
Consider the CG method of forms (2) and (18) with the new formula βk1. If Lemma 1 holds with L in Case 1 (refer to [14]) satisfying equation (48), then βk1 has Property 1.Proof.
Setb=2γ¯2/c1−σγ2≥1 and λ≤c1−σγ2/2LL+1γ¯b. Using equations (20) and (47), we obtain(50)βk1=gk2−μkgkTgk−1dk−1T1gk−gk−1≤gk2+gkTgk−1dk−1T1gk−gk−1≤gkgk+gk−1c1−σgk−12≤2γ¯2c1−σγ2=b>1.Case 1
μk<1.By using Assumption1, the restart criteria in (20) can be written as follows:(51)gk2>1LgkTgk−1.Thus, we can write(52)βk1≤gk2−μkgkTgk−1dk−1T1gk−gk−1≤gk2−1/LgkTgk−1dk−1T1gk−gk−1≤gkgk−1/Lgk−1dk−1T1gk−gk−1.Also, using equation (48) in [14], we obtain(53)gk−1Lgk−1≤Lgk−1Lgk−1+1Lgk−gk−1.Since(54)≤L+1gk−gk−1,we now have1/L≤μk<1.Using (52) and (54), we obtain(55)βk1≤L+1gkgk−gk−1dk−1T1gk−gk−1.Using Assumption1 and the definition of λ, we obtain(56)βk1≤LL+1λγ¯c1−σγ2=12b.Case 2
μk≥1.By using Assumption1 and equation (19), we obtain(57)βk1≤gk2−μkgkTgk−1dk−1T1gk−gk−1≤gk2−gkTgk−1dk−1T1gk−gk−1≤gkgk−gk−1dk−1T1gk−gk−1≤Lλγ¯c1−σγ2.Thus, in all cases,(58)βk1≤Lλγ¯c1−σγ2≤LL+1λγ¯c1−σγ2≤12b.The proof is complete.
To obtainβk1≤1/2b, we consider the following cases:Lemma 5.
Consider the CG method of forms (2) and (18) with βk1=−tgkTsk−1/dk−1T1yk−1. Then, βk1 satisfiesProperty 2.Proof.
Setλ=1−σcγ2/2tγ¯b and b=tBγ¯/1−σcγ2. Then, βk1=−tgkTsk−1/dk−1T1yk−1, equation (47), and Assumption 1 yield(59)βk1≤tgkTsk−1dk−1T1yk−1≤tMγ¯1−σcγ2=b>1.
Ifsk≤λ, we obtain the following:(60)βk1≤tgkTsk−1dk−1T1yk−1≤tλγ¯1−σcγ2=12b.
The following lemmas correspond to Lemma 4.1 and Lemma 4.2 in [11].Lemma 6.
Let Assumption1 holds. Let the sequences xk and dk be generated by Figure 1 with equation (18), where αk is computed by the WWP line search holding the sufficient descent condition (27). We assume that the method has Property 2. Suppose that equation (47) holds. Then, there exists λ>0 such that, for any Δ∈N and any index k0, there exists an index k>k0 satisfying(61)κk,Δλ>λ2,where κk,Δλ=i∈N:k≤i≤k+Δ−1,si>λ, N denotes the set of positive integers, and κk,Δλ denotes the number of elements inκk,Δλ.Lemma 7.
Let Assumption1 holds. Let the sequences xk and dk be generated by Figure 1 with equation (18), where αk is computed by the SWP line search holding the sufficient descent condition (43). If βk≥0 and (47) hold, then dk≠0 and(62)∑k=0∞uk+1−uk2<∞,where uk=dk/dk.
By Lemmas4–7, the global convergence of Figure 1 with equation (18) and SWP line search can be established similar to that of Theorem 4.3 in [10]. Therefore, the proof of the following theorem is omitted.Theorem 5.
Let the sequencesgk and dk be generated by (2) and (18) with the CG formula βk1 and the step size satisfying (4) and (5). If Lemmas 4–7 are true, then(63)liminfk⟶∞gk=0.Theorem 6.
Let the sequencesxk and dk be generated using (2) and (17), where αk is computed by the SWP line search (4) and (5) or any line search. If the CG method with dk1 and dk2 obtains the result liminfk⟶∞gk=0, then(64)dk=λdk1+1−λdk2,yields the same result given by liminfk⟶∞gk=0.Proof.
If the CG method withdk1obtains the result liminfk⟶∞gk=0, then λdk1 yields the result liminfk⟶∞gk=0 since λis a constant. A similar approach is applied on dk2. Thus, dk in (17) yields the result liminfk⟶∞gk=0.


## 4. Numerical Results and Discussion

To discuss the efficiency of the proposed method, we employ standard test functions in Table1 similar to that used in CG_Descent 6.8, giving a strong comparison for the proposed method. The test functions can be obtained from the CUTEST library [27]. The numerical results of dk2 (CG_Descent 5.3) are obtained by executing the code in [28] without any change of default parameters and line search (Wolfe or approximate Wolfe line search). The numerical results of dk1 in equation (18) are obtained by modified CG_Descent code via SWP line search with σ=0.1 and δ=0.01. The numerical results of dk in equation (17) are obtained by executing the modified code of [28]. This was performed with memory equal to zero, change of search direction to be convex of dk1 and dk2, and SWP line search with σ=0.1 and δ=0.01. Here, λ = 0.5 since we want to use both search directions dk1 and dk2 in equal form. Note that the proposed method is limited with SWP line search between σ∈0,1/2.Table 1
The test functions.
A3 CG methodA2 CG methodA1 CG methodFunctionNo. of iterationsNo. of function evaluationsNo. of gradient evaluationsCPU timeNo. of iterationsNo. of function evaluationsNo. of gradient evaluationsCPU timeNo. of iterationsNo. of function evaluationsNo. of gradient evaluationsCPU timeAKIVA820150.021021110.02820150.02ALLINITU1128200.021229180.02925180.02ARGLINA1320.021320.021320.02ARWHEAD716120.0271580.02617140.02BARD1436250.021633170.021232220.02BEALE1230220.021531160.021133260.02BIGGS62355370.022757310.022464440.02BOX31023140.021124130.021023140.02BOX724200.08825190.08725210.11BRKMCC51160.0251160.0251160.02BROWNAL925190.02925180.021153460.02BROWNBS1227190.021326150.021024180.02BROWNDEN1638310.021631190.021638310.02BROYDN7D58107810.311411281014295.471081891500.48CHNROSNB3025883410.022875642990.02871991280.02CLIFF943360.021870540.021046390.02COSINE2068570.221139320.191769650.31CRAGGLVY1152532040.591031971470.451202672160.52CUBE1743300.023277470.021748340.02CURLY10508617183680781182.51478086729476156173.7558617500085000183CURLY206325985788104016341.946658789245110540383.946779290378113052395.24CURLY3076889100941129855583.5879030102516134682639.6380000105941134855650DENSCHNA616120.02919100.02616120.02DENSCHNB618150.0271580.02618150.02DENSCHNC1136310.021226140.021136310.02DENSCHND1745340.024798510.021446400.02DENSCHNE1444360.021849320.021243380.02DENSCHNF928230.0281790.02931260.02DIXMAANA615110.0271580.02615110.02DIXMAANB616120.0261370.02616120.02DIXMAANC61490.0261370.0261490.02DIXMAAND615110.0271580.02717120.02DIXMAANE2532804870.32222394290.332192464210.34DIXMAANF1172391250.091613231620.131282611360.12DIXMAANG1693431770.141573151580.121693431770.14DIXMAANH1743541830.161733471740.221873791950.19DIXMAANI3045314060033.273856392676444.253278336764773.63DIXMAANJ3266573340.263276553280.363466973540.31DIXMAANK2865762930.232835672840.284018074090.33DIXMAANL2535122620.312374752380.24148354250.37DIXON3DQ10000100071999519.1210000100071999519.1210000100071999520.22DJTL82120311760.02829178800.0275116311480.02DQDRTIC51160.0251160.0251160.02DQRTIC1532180.021737210.031532180.02EDENSCH2761530.052652380.033980780.05EG2727220.0251160.023850.02EIGENALS7730136069602138.91100831802012244178.36130862417415135222EIGENBLS199473990419963308153013060315302237240004400023000277EIGENCLS98881895510716168.91101361929211118174.19140002200014000200ENGVAL12143360.112750360.062346390.06ENGVAL22464480.022661370.022673550.02ERRINROS1046220591117520.333807734250.021072691860.02EXPFIT1027210.021329160.02929220.02EXTROSNB4482932750251.313808775939821.254482932750251.25FLETCBV21110.021110.021110.02FLETCHCR1442781660.061522901760.051442781660.05FMINSRF24128272928.90E-013466933471.09E + 001803364618494.75FMINSURF4128274171.344739474741.511327270513844.06FREUROTH2762580.132551380.111851370.06GENHUMPS529911805692419.61647512964649320.11529911805692420.11GENROSE1101220211430.191078216711010.171101220211430.17GROWTHLS1134133470.021564563190.021094313690.02GULF3794650.023784480.023395720.02HAIRY819110.023699650.021782680.02HATFLDD1543350.022043240.021749370.02HATFLDE1232250.023072450.021337300.02HATFLDFL762231680.023992550.022168540.02HEART6LS39110968220.0268415769410.0237511378760.02HEART8LS2365703780.022495242780.022536574400.02HELIX2659370.022349270.022360420.02HIELOW1331210.051430160.021330210.02HILBERTA2530.022530.022530.02HILBERTB4950.024950.024950.02HIMMELBB418180.021028210.02418180.02HIMMELBF2256400.022660360.022359460.02HIMMELBG823170.02820130.02722170.02HIMMELBH51390.0271690.0251390.02HUMPS853713190.02521861.44E + 020.02452232020.02JENSMP1552460.021533220.021247410.02JIMACK83491669983501176.3683141662983151182.2587191744087211223.9KOWOSB1744320.021739230.021646320.02LIARWHD1751410.052145250.031645310.06LOGHAIRY431551270.022781580.02261961790.02MANCINO1123120.061123120.081123120.06MARATOSB779326428570.021145365727790.02589288525850.02MEXHAT14545002056390.021459550.02MOREBV1611683170.31611683170.411611683170.31MSQRTALS2875575728858.832905581529118.642771555227848.7MSQRTBLS2421484724277.172280452523266.912153431421666.91NCB20B28534475608146.5920354694600646.3630005000700050NCB2074716339758.58791511146311.839001700100015NONCVXU2624912625644814.44661012833699915.896543122716691715.17NONDIA925170.02725200.03725190.03NONDQUAR2484236090.331942388819472.451343652710.23OSBORNEA671671150.02942131240.02822301740.02OSBORNEB58132820.0262127650.0257134840.02OSCIPATH2969507123334633382.063109906709533673252.082950297817295344252.3PALMER1C1227280.021126260.021227280.02PALMER1D1024230.021125250.021024230.02PALMER2C1121220.021121210.021121220.02PALMER3C1121210.021120200.021121210.02PALMER4C1121210.021120200.021121210.02PALMER5C61370.0261370.0261370.02PALMER6C1124240.021124240.021124240.02PALMER7C1120200.021120200.021120200.02PALMER8C1119190.021118170.021119190.02PARKCH6481378106627.566721385112829.456721385112829.45PENALTY12273590.022869440.02411641440.02PENALTY21862213550.031912213540.051912213540.05PENALTY3852782311.8992852191.78521811441.13POWELLSG2865430.032653270.022764420.02POWER3197044000.563727543840.763027004220.81QUARTC1532180.051737210.031532180.03ROSENBR2877580.023477440.022884650.02S308721170.02819120.02721170.02SCHMVETT4070520.194373600.234171580.19SENSORS2460410.342150340.25771821641.24SINEVAL521451050.0264144880.02461811530.02SINQUAD1341370.081440330.091445370.06SISSER519190.02618140.02519190.02SNAIL1747330.021002301320.02612512110.02SPARSINE271842746254094103.531835818647364317321689219804309784.55SPARSQUR541771550.722861350.31572011790.97SPMSRTLS2034052180.52034122100.592174342370.48SROSENBR921130.021123120.02921150.02STRATEC1663742395.42462104379619.981704192836.22TESTQUAD1586159331671.28E + 001577158431491.52E + 001582158931591.3TOINTGOR1392381830.021352331740.021392381830.02TOINTGSS61280.024950.024950.02TOINTPSP1142431760.021432791820.021142431760.02TOINTQOR2936530.022936530.022936530.02TQUARTIC1240310.021440270.031137290.03TRIDIA78178815570.8678278915590.8478278915591.22VARDIM1026200.021125160.021024170.02VAREIGVL2656330.022347240.022349280.02VIBRBEAM1353372670.021383231990.02982551740.02WATSON58125720.0249102540.0258125720.02WOODS2354350.0222513.00E + 010.062154360.06YFITU692001570.02841971180.02682081670.02ZANGWIL21320.021320.021320.02The comparisons are made based on the number of iterations that the algorithm require to obtain the stationary point, the CPU time required for every algorithm to obtain the solution, and the number of function evaluation, i.e., how many times the algorithm uses the function. Note that the number of function evaluation and gradient evaluations are strongly related to the line search. For a fair comparison between the proposed methods and CG_Descent 5.3, we use the same test functions for all algorithms similar to that used by CG_Descent 5.3. Moreover, we use approximate line search with CG_Descent 5.3 as introduced by authors to obtain the results. In addition, the minimum time was 0.2 for all algorithms. Also, we use Ubuntu 20.04 as an operating system to run the code for all algorithms, which is more accurate than windows for scientific calculations.The results are shown in Figures2–4, representing a performance measure introduced by [29]. This performance measure was introduced to compare a set of solvers S on a set of problems ρ. Assuming ns solvers and np problems in S and ρ, respectively, the measure tp,s is defined as the computation time (e.g., the number of iterations or the CPU time) required for the solver s to solve the problem p.Figure 2
Performance measure based on the number of iterations.Figure 3
Performance measure based on the CPU time.Figure 4
Performance measure based on the function evaluation.To create a baseline for comparison, the performance of the solvers on the problem p is scaled by the best performance of any solver in S on the problem using the ratio(65)rp,s=tp,smintp,s:s∈S.Let that the parameterrM≥rp,s for all selected p,s. Also, assume that rp,s=rM if and only if the solver s does not solve the problem p. Since we would like to obtain an overall assessment of the performance of a solver, we define the measure as follows:(66)Pst=1npsizep∈ρ:rp,s≤t.Thus,Pst is the probability for a solver s∈S that the performance ratio rp,s is within a factor t∈R of the best possible ratio. Suppose we define the function ps as the cumulative distribution function for the performance ratio. In that case, the performance measure ℝ for a solver is nondecreasing and piecewise continuous from the right. The value of ps1 is the probability that the solver achieves the best performance of all of the solvers. In general, a solver with high values of Pst, which would appear in the upper right corner of the figure, is preferable.In all figures, we see that the convex search direction outperforms both search directions in terms of iteration number, function evaluation, and CPU time. In all figures, we rename the methods as follows:A1 means the CG method with search directiondk1A2 means the CG method with search directiondk2A3 means the CG method with search directiondk in equation (17).We note from Figure2 that method A3 slightly outperforms method A1and A2 in the number of iterations, where A1 outperforms A2. Figure 3 shows that the new method A3 strongly outperforms method A1 and slightly outperforms method A2 in CPU time, where A1 is strongly comptetive with A2. Moreover, from Figure 4, we can indicate that method A3 outperforms A1 and A2 methods in the number of function evaluation where A1 and A2 are strongly comptetive. It is worth to note that the functions with large dimension, i.e., large unconstrained optimization problems cost more CPU time, number of iterations, and gradient evalutions. Thus, we advice the readers to use very high quality of computers such as work station computer with the Ubuntu operating system.


### 4.1. Image Restoration

In this section, we will use Figure1 to restore the destroyed image. We use well-known images such as Cameraman, Boat, Coins, Moon, and Baboon. We added noise by using Gaussian noise with a standard deviation equal to 25% to original images. We then restore these images by βkDL+ CG algorithm and Figure 1. Note that we use(67)βkDL+=max0,gkTyk−1dk−1Tyk−1−tgkTsk−1dk−1Tyk−1 if the descent condition holds, otherwise, we restart the algorithm by using the steepest descent method. This procedure is similar to that used by Dai and Liao [18] when they obtained the numerical results. For both algorithms, we use the SWP line to obtain the step size with σ=0.1 and δ=0.01.To evaluate the quality of the restored image, we use the root-mean-square error (rmse) between the true image (original) and the restored image as follows:(68)rmse=ζ−ζk2ζ.Here,ζand ζk are the true image and restored images. The restored image quality depends on the value of rmse, i.e., good quality with small rmse. The stopping criterion is(69)xk+1−xk2xk2<ω.Here,ω=10−3. Note that if ω=10−4 or ω=10−6, then rmse has the same value, i.e., more iterations with fixed rmse.Table2 presents a comparison between the DL + CG algorithm and Figure 1 using some numerical experiments as mentioned before. The comparison includes the number of iterations, CPU time, and rmse. We can observe that the new method (A1) is better than DL+ in rmse measure, CPU time, and iterations for most experimental tests. The simulations are performed in Matlab (R2010a), where the host computer is an AMD A4-7210 with RAM 2 GB. Thus, the CPU time becomes more than usual. We note that our new algorithm is efficient for restoring images based on rmse, number of iteration, and CPU time. It is worth to note that if we increase the Gaussian noise, the cost to restore image will increase. In addition, the image with large size needs more CPU time than images with small size.Table 2
Numerical results of images with DL + CG method and Figure1 and Gaussian noise with standard deviation of 25% to original images.
ImageAlgorithmNumber of iterationsCPU time in secondsrmseMoon (128 × 128)DL+1711.189e + 0010.0654Algorithm 11721.083e + 0010.0651Baboon (128 × 128)DL+1561.198e + 0010.1492Algorithm 11561.220e + 0010.1481Cameraman (128 × 128)DL+1621.217e + 0010.1146Algorithm 11581.163e + 0010.1143Coins (128 × 128)DL+1329.422e + 0000.0834Algorithm 11359.391e + 0000.0835Boat (128 × 128)DL+1391.002e + 0010.1129Algorithm 11371.081e + 0010.1137Moon (256 × 256)DL+1675.497e + 0010.0351Algorithm 11675.745e + 0010.0350Baboon (256 × 256)DL+1691.453e + 0020.1058Algorithm 11631.396e + 0020.1058Cameraman (256 × 256)DL+1649.627e + 0010.0889Algorithm 11619.170e + 0010.0886Coins (256 × 256)DL+1285.845e + 0010.0504Algorithm 11275.750e + 0010.0505Boat (256 × 256)DL+948.258e + 0010.0651Algorithm 1948.363e + 0010.0650Moon (512 × 512)DL+1552.071e + 0020.0183Algorithm 11542.007e + 0020.0180Baboon (512 × 512)DL+1738.931e + 0020.1070Algorithm 11799.215e + 0020.1061Cameraman (512 × 512)DL+1463.931e + 0020.0534Algorithm 11453.707e + 0020.0532Coins (512 × 512)DL+1292.964e + 0020.0326Algorithm 11272.779e + 0020.0324Boat (512 ×  512),DL+764.241e + 0020.0461Algorithm 1734.091e + 0020.0460Moon (1024 × 1024)DL+1517.440e + 0020.0080Algorithm 11477.307e + 0020.0079Cameraman (1024 × 1024)DL+1261.210e + 0030.0028Algorithm 11241.143e + 0030.0026Coins (1024 × 1024)DL+1209.912e + 0020.0017Algorithm 11149.612e + 0020.0015In Table3, we present some numerical results of Figure 1 to restore destroyed images using Gaussian noise with a standard deviation of 25%. We note that Figure 1 is an efficient method to restore destroyed images.Table 3
Restoration of the Coins, Moon, Boat, Cameraman, and Baboon by minimizingzusing Figure 1.
ImageOriginal imageImage with noiseRestored imageCoins (1024 × 1024)Moon (1024 × 1024)Boat (512 ×  512)Cameraman (512 × 512)Coins (256 × 256)Baboon (256 × 256)Moon (128 × 128)Cameraman (128 × 128)


## 4.1. Image Restoration

In this section, we will use Figure1 to restore the destroyed image. We use well-known images such as Cameraman, Boat, Coins, Moon, and Baboon. We added noise by using Gaussian noise with a standard deviation equal to 25% to original images. We then restore these images by βkDL+ CG algorithm and Figure 1. Note that we use(67)βkDL+=max0,gkTyk−1dk−1Tyk−1−tgkTsk−1dk−1Tyk−1 if the descent condition holds, otherwise, we restart the algorithm by using the steepest descent method. This procedure is similar to that used by Dai and Liao [18] when they obtained the numerical results. For both algorithms, we use the SWP line to obtain the step size with σ=0.1 and δ=0.01.To evaluate the quality of the restored image, we use the root-mean-square error (rmse) between the true image (original) and the restored image as follows:(68)rmse=ζ−ζk2ζ.Here,ζand ζk are the true image and restored images. The restored image quality depends on the value of rmse, i.e., good quality with small rmse. The stopping criterion is(69)xk+1−xk2xk2<ω.Here,ω=10−3. Note that if ω=10−4 or ω=10−6, then rmse has the same value, i.e., more iterations with fixed rmse.Table2 presents a comparison between the DL + CG algorithm and Figure 1 using some numerical experiments as mentioned before. The comparison includes the number of iterations, CPU time, and rmse. We can observe that the new method (A1) is better than DL+ in rmse measure, CPU time, and iterations for most experimental tests. The simulations are performed in Matlab (R2010a), where the host computer is an AMD A4-7210 with RAM 2 GB. Thus, the CPU time becomes more than usual. We note that our new algorithm is efficient for restoring images based on rmse, number of iteration, and CPU time. It is worth to note that if we increase the Gaussian noise, the cost to restore image will increase. In addition, the image with large size needs more CPU time than images with small size.Table 2
Numerical results of images with DL + CG method and Figure1 and Gaussian noise with standard deviation of 25% to original images.
ImageAlgorithmNumber of iterationsCPU time in secondsrmseMoon (128 × 128)DL+1711.189e + 0010.0654Algorithm 11721.083e + 0010.0651Baboon (128 × 128)DL+1561.198e + 0010.1492Algorithm 11561.220e + 0010.1481Cameraman (128 × 128)DL+1621.217e + 0010.1146Algorithm 11581.163e + 0010.1143Coins (128 × 128)DL+1329.422e + 0000.0834Algorithm 11359.391e + 0000.0835Boat (128 × 128)DL+1391.002e + 0010.1129Algorithm 11371.081e + 0010.1137Moon (256 × 256)DL+1675.497e + 0010.0351Algorithm 11675.745e + 0010.0350Baboon (256 × 256)DL+1691.453e + 0020.1058Algorithm 11631.396e + 0020.1058Cameraman (256 × 256)DL+1649.627e + 0010.0889Algorithm 11619.170e + 0010.0886Coins (256 × 256)DL+1285.845e + 0010.0504Algorithm 11275.750e + 0010.0505Boat (256 × 256)DL+948.258e + 0010.0651Algorithm 1948.363e + 0010.0650Moon (512 × 512)DL+1552.071e + 0020.0183Algorithm 11542.007e + 0020.0180Baboon (512 × 512)DL+1738.931e + 0020.1070Algorithm 11799.215e + 0020.1061Cameraman (512 × 512)DL+1463.931e + 0020.0534Algorithm 11453.707e + 0020.0532Coins (512 × 512)DL+1292.964e + 0020.0326Algorithm 11272.779e + 0020.0324Boat (512 ×  512),DL+764.241e + 0020.0461Algorithm 1734.091e + 0020.0460Moon (1024 × 1024)DL+1517.440e + 0020.0080Algorithm 11477.307e + 0020.0079Cameraman (1024 × 1024)DL+1261.210e + 0030.0028Algorithm 11241.143e + 0030.0026Coins (1024 × 1024)DL+1209.912e + 0020.0017Algorithm 11149.612e + 0020.0015In Table3, we present some numerical results of Figure 1 to restore destroyed images using Gaussian noise with a standard deviation of 25%. We note that Figure 1 is an efficient method to restore destroyed images.Table 3
Restoration of the Coins, Moon, Boat, Cameraman, and Baboon by minimizingzusing Figure 1.
ImageOriginal imageImage with noiseRestored imageCoins (1024 × 1024)Moon (1024 × 1024)Boat (512 ×  512)Cameraman (512 × 512)Coins (256 × 256)Baboon (256 × 256)Moon (128 × 128)Cameraman (128 × 128)


## 5. Conclusions

In this study, we investigated a convex between two different search directions. The new combination satisfies the global convergence and descent property. Our numerical results show that the new combination produces efficient results better than both search directions and is sometimes competitive. In addition, we propose a new CG method satisfying descent property and convergence analysis. Finally, we present an example of image restoration using the new algorithm.



---

*Source: 9941757-2021-07-13.xml*