# A Modified Dai–Liao Conjugate Gradient Method with a New Parameter for Solving Image Restoration Problems

Authors: Junyu Lu; Yong Li; Hongtruong Pham
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

One adaptive choice for the parameter of the Dai–Liao conjugate gradient method is suggested in this paper, which is obtained with modified quasi–Newton equation. So we get a modified Dai–Liao conjugate gradient method. Some interesting features of the proposed method are introduced: (i) The value of parametert of the modified Dai–Liao conjugate gradient method takes both the gradient and function value information. (ii) We establish the global convergence property of the modified Dai–Liao conjugate gradient method under some suitable assumptions. (iii) Numerical results show that the modified DL method is effective in practical computation and the image restoration problems.


---

## Body

## 1. Introduction

In this paper, we consider the following unconstrained optimization problem:(1)minfx,x∈ℜn,where f:ℜn⟶ℜ and f is a continuously differentiable function. Requiring simplicity and low memory storage [1–5], conjugate gradient (CG) methods [6–11] are useful tools for solving large-scale problems. Thus, we consider solving (1) with the conjugate gradient methods. A sequence of iterates is generated from a given x0 with the following simple iteration formula:(2)xk+1=xk+αkdk,k=0,1,2,…,where xk is the k-th iteration point, the step size αk>0 can be usually chosen to satisfy certain line search conditions, and dk is the search direction defined by(3)dk=−gk,ifk=0,−gk+βkdk−1,ifk≥1,where βk is a scalar. Many scholars presented some classical formulas of βk as follows: the corresponding methods are called the Polak–Ribiére–Polyak (PRP) [12, 13], Fletcher–Reeves (FR) [14], Hestense–Stiefel (HS) [15], conjugate descent (CD) [16], Liu–Storey (LS) [17], and Dai–Yuan (DY) [18] CG methods:(4)βkPRP=gkTgk−gk−1gk−12,βkFR=gk2gk−12,βkHS=gkTgk−gk−1dk−1Tgk−gk−1,βkCD=gk2−dk−1Tgk−1,βkLS=gkTgk−gk−1−dk−1Tgk−1,βkDY=gk2gk−gk−1Tdk−1,where gk−1 is the gradient ∇fxk−1 of fx at the point xk−1 and ⋅ is the Euclidean norm. We relatively easily established the global convergence property of the CD method, DY method, and FR method, but numerical results of these methods are not desirable in some computations. Powell [19] explained a major numerical disadvantage of the FR method, such as subsequent steps being very short if a small step is originated away from the solution point. If poor dk occurs in practical computation, the PRP, HS, or LS method will perform a restart, so these three methods perform much better than the above three methods in the numerical test. They are generally regarded as the most efficient conjugate gradient methods. Therefore, in recent year, many scholars try to research some modified formulas for conjugate gradient methods which have global convergence property for general functions and satisfied performance in the numerical test. Among them, Dai and Liao [20] proposed some modified conjugate methods with a new conjugacy condition. Interestingly, their method cited in [20] not only has global convergence for general function, but also has better numerical performance than HS and PR methods.When the CG methods produce a sequence of search directionsdk, the following conjugacy condition holds:(5)dmTHdn=0,where m≠n and H is the Hessian of the objective function. The definition of yk−1 is as follows:(6)yk−1=gk−gk−1.If the general functionf is nonlinear, combining with the knowledge of mean value theorem, we draw a conclusion such that(7)dkTyk=αk−1dkT∇2fxk−1+tαk−1dk−1dk−1,where t∈0,1. By (5) and (7), we have(8)dkTyk−1=0.As we know, Dai and Liao [20] studied (8) in depth based on the quasi–Newton techniques. We have that in the quasi–Newton method, Hk−1 is defined as an approximation matrix of the Hessian ∇2fxk−1, and the new matrix Hk holds the following formula:(9)Hksk−1=yk−1.In the quasi–Newton method, the search directiondk is defined by(10)dk=−Hk−1gk.According to the above two equations, we have(11)dkTyk−1=dkTHksk−1=−gkTsk−1.Based on the above relations, Dai and Liao acquired the following conjugacy condition:(12)dkTyk−1=−tgkTsk−1,where t is a positive parameter. In the case t=0, (12) becomes (8). In the case t=1, (12) becomes (11). Moreover, gkTsk−1=0 holds under the exact line search. It is easily observed that both (11) and (12) coincide with (8). According to the above discussion, (12) can be considered as an extension of (8) and (11). Multiplying the definition of dk with yk−1 and using (12), Dai and Liao introduced the new formula in the DL method as follows:(13)βkDL=gkTyk−1−tgkTsk−1dk−1Tyk−1.In [20], the conjugate gradient method with (13) establishes the global convergence property of uniformly convex functions. Furthermore, in order to ensure general functions also satisfy global convergence, a new formula was presented by Dai and Liao as follows:(14)βkDL+=maxgkTyk−1dk−1Tyk−1,0−tgkTsk−1dk−1Tyk−1.It is easily observed that the values of the first term in (13) are nonnegative. They proved that the modified DL method with (14) satisfies global convergence for general functions under some suitable conditions. In the DL method, different parameter t shows different numerical performance. Based on the singular value study, Hager and Zhang [21] presented the new choices for t:(15)t=2yk2skTyk,and they proved that dk in [21] satisfies the sufficient descent condition. In addition, Babaie-Kafaki and Ghanbari [22] presented a new value for t:(16)t1=sk2yk2skTyk2.In [22], they proved that the DL method with t=t1 has better numerical results than the methods proposed by Dai and Kou [23]. In last several years, some scholars tried to find the new choice for the nonnegative parameter t in (13) [24, 25]. The remainder of this paper is organized as follows: in Section 2, based on the new conjugacy condition, a modified DL gradient method is proposed with a new value for the parameter. We establish the global convergence property of the presented method in Section 3. Finally, we do some numerical experiments in Section 4.


## 2. New DL Conjugate Gradient Method

It is well known that the objective function can be regarded as a quadratic equation, so, if a pointxk is close enough to a local minimizer, a good direction is the Newton direction:(17)dk=−∇2fxk−1gk.Hence, fromdk of CG methods and the formula of βk in (13), we can compute the value of parameter t as follows:(18)−∇2fxk−1gk=−gk+gkTyk−1dk−1Tyk−1dk−1−tgkTsk−1dk−1Tyk−1dk−1.By some algebra, we obtain(19)t=sk−1Tgk−sk−1T∇2fxkgk+gkTyk−1/sk−1Tyk−1sk−1T∇2fxksk−1gkTsk−1/sk−1Tyk−1sk−1T∇2fxksk−1.Thoughtfully, because computing the Hessian matrix∇2fxk is inefficient, a quasi–Newton method is used in this paper. In the quasi–Newton methods [26], the search direction dk is computed by solving unconstrained optimization problems, Bkdk=−gk, where Bk is the approximation matrix of the Hessian ∇2fxk such that the matrix Bk satisfies the following important equation:(20)Bksk−1=yk−1.Theorem 1.
Assume that the functionfx is sufficiently smooth and sk−1 is sufficiently small, and then, we have(21)sk−1T∇2fxksk−1−sk−1Tyk−1=12sk−1TTksk−1sk−1+Osk−14,where Tk is the tensor of f at xk and(22)sk−1TTksk−1sk−1=∑i,j,l=1n∂3fxk∂xi∂xj∂xlskiskjskl.Proof.
Doing Taylor expansion for the objective functionfx, we have(23)fk−1=fk−gkTsk−1+12sk−1T∇2fxksk−1−16sk−1TTksk−1sk−1+Osk−14,gk−1Tsk−1=gkTsk−1−sk−1T∇2fxksk−1+12sk−1TTksk−1sk−1+Osk−14.
By the definitions ofyk−1, we completed the proof.
The BFGS-type methods have been proven to satisfy ideal global convergence of uniformly convex functions, but the methods may fail to establish the convergence property of nonconvex functions. So, a new version of the BFGS method is proposed by Wei et al. [27] to overcome its convergence failure for more general objective function. In their method, the matrix Bk is obtained from the following modified secant equation:(24)Bksk−1=yk−1∗,yk−1∗=yk−1+νk−1sk−1,where νk−1=maxϑk−1,0/sk−12 and ϑ=2fk−1−fk+gk−1+gkTsk−1. In order to get the powerful theoretical and numerical properties of the modified BFGS method, use (24) to simplify (19) and the parameter t is proposed as follows:(25)t2=1−νk−1sk−1Tgk+gkTyk−1/sk−1Tyk−1νk−1sk−12gkTsk−1+gkTsk−1/sk−1Tyk−1νk−1sk−12.
Then, to ensure that the new DL method satisfies the descent condition, we present a modified definition of the value of parametert similar to [28] as follows:(26)t∗=maxt2,θyk−12sk−1Tyk−1,where θ>1/4; it means that we have dk as follows:(27)dk=−gk+βkDL∗dk−1,where βkDL∗=gkTyk−1−t∗gkTsk−1/dk−1Tyk−1. Based on the above discussion, we can collect some of the advantages of these formulas:(i)
The new DL method possesses the information about function values.(ii)
The global convergence for nonconvex functions is established under some assumptions.(iii)
The new formulas are applied to the engineering Muskingum model and image restoration problems. Finally, we end this section by presenting a modified DL algorithm, which is listed in Algorithm1.Algorithm 1: YWLDL algorithm.
Step 0: choose an initial pointx0∈ℜn, δ∈0,1, δ1∈0,δ, σ∈δ,1, ε>0. Set d0=−g0=−∇fx0, k:=0.Step 1: stop ifgk≤ε.Step 2: determine a stepsize satisfying the following line search by [4]: fxk+αkdk≤fk+δαkgkTdk+αkmin−δ1gkTdk,δαk/2dk2,andgxk+αkdkTdk≥σgkTdk+min−δ1gkTdk,δαkdk2whereδ∈0,1/2, δ1∈0,δ, and σ∈δ,1.Step 3: letxk+1=xk+αkdk.Step 4: ifgk+1≤ε, then the modified DL algorithm stops.Step 5: calculate the search direction by (27).Step 6: setk: = k + 1 and go to step 3.


## 3. Convergence Analysis

In the following paper, there are some indispensable assumptions for the global convergence of the algorithm on objective functions.Assumption 1.
(i) The level setY=xfx≤fx0 is bounded.
(ii) In some neighbourhoodΨ of Υ, f is differentiable, and its gradient function g is the Lipschitz continuous, namely,(28)gx−gy≤Lx−y,where L>0 is a constant and any x,y∈Ψ.Remark 1.
Assumption1 implies that there exists a constant η>0 satisfying(29)gx≤η,∀x∈Ψ.Remark 2.
In order to establish the convergence property of new method, we assume the new proposed parameter is bounded. For this purpose, we set(30)t∗≤H,where H is a large positive constant.Lemma 1.
Consider the proposed modified DL method in the form of (27). If the line search procedure guarantees dkTyk≥0, for all k≥0, then, we have(31)gkTdk≤−λgk2,where λ=1−1/4θ.Proof.
Similar to the proof of Theorem 1 [29].Lemma 2.
Suppose that Assumption1 holds. Consider the proposed modified DL method in the form of (27), and the step size αk obtained by the equations in step 2 in Algorithm 1. If f be a nonconvex function on the level set Ψ, then, we have(32)∑k=0gkTdk2dk2<∞.Proof.
From Lemma1, dkTgk<0 holds. By the second equation in Step 2 in Algorithm 1 and (28),(33)αkLdk2≥gk+1−gkTdk≥σ−1gkTdk+min−δ1gkTdk,δαkdk2≥σ−1gkTdk.
So the following equation holds:(34)αk≥σ−1gkTdkLdk2.
From the first equation in Step 2 in Algorithm1, we obtain(35)fxk−fxk+αkdk≥−δαkgkTdk−αkmin−δ1gkTdk,δαk2dk2≥−δ−δ1αkgkTdk.
Summing up both sides of the above inequalities fromk = 0 to ∞, we obtain(36)∑k=0∞−αkgkTdk<∞.
Combining with (34), (32) holds, which completes the proof.Lemma 3.
Suppose that Assumption1 is true and then the sequence xk,dk,αk,gk is generated by Algorithm YWLDL. If(37)gk≥τ,we obtain(38)∑k=0∞1dk2<∞.Proof.
From Lemma1 and (37), we have(39)τ2∑k=0∞1dk2≤∑k=0∞gk4dk2≤∑k=0∞1λ2gkTdk2dk2.
Combining with Lemma2, such that(40)∑k=0∞1dk2<∞.
The proof is complete.Theorem 2.
Suppose that Assumption1 holds. Consider that the proposed modified DL method in the form of (27) and the step size αk obtained the equations in step 2 in Algorithm 1. If f be a nonconvex function on the level set Ψ, then, we obtain(41)limk⟶∞infgk=0.Proof.
First, we suppose that equation (41) is not true. Namely, equation (37) holds. From the equations in step 2 in Algorithm 1, in case 1, −δ1gkTdk≥δαkdk2 holds, combining with (36), we have(42)∑k=0∞sk2=∑k=0∞αkdk2≤∑k=0∞−δ1δαkgkTdk<∞.
And in case 2, similar to the proof of Theorem 3.1 [30], the relation holds as follows:(43)αkdk2≤−δ¯gkTdk,where δ¯>0. From (36) and (43), the following equation holds in case 2:(44)∑k=0∞sk2≤c∑k=0∞αkdk2≤c∑k=0∞−1δ¯αkgkTdk<∞.Thus,(45)sk⟶0,∀k>0.
We have(46)sk<z,where 0<z<1 holds. And from the second equation in Step 2 in Algorithm 1, we obtain(47)ykTdk=gk+1Tdk−gkTdk≥σ−1gkTdk+min−δ1gkTdk,δαkdk2≥σ−1gkTdk.
By (31) and (37), we have(48)ykTdk≥1−σλτ2.
Combining with (30)–(30), (46), and (48), the following equation holds:(49)βkDL∗=gkTyk−1−t∗gkTsk−1dk−1Tyk−1≤L+Hgksk−1dk−1Tyk−1≤L+Hηzdk−1Tyk−1≤L+Hηz1−σλτ2=Z,where Z=L+Hηz/1−σλτ2. From (27), we have(50)dk=−gk+βkDL∗dk−1≤η+Zdk−1≤η1+Z+Z2+⋯+Zk−k0−1+Zk−k0dk0≤η1−Z+dk0.
Letυ=maxd1,d2,…,dk0,η/1−Z+dk0, the following holds:(51)dxk≤υ,∀k≥0.
This contradicts (38), so the proof is completed.


## 4. Numerical Experiments

This section reports some numerical results. We do some numerical experiments in order to investigate the performance of our proposed algorithm and compare it with others. In the next subsections, all the numerical tests were run in a 2.30 GHz CPU and 8.00 GB of memory in a Windows 10 operating system.


### 4.1. Normal Unconstrained Optimization Problems

In this section, we test the effect of some algorithms on numerical problems, and the unconstrained optimization problems are listed in Table1. We will report on various numerical implementations of our presented method (YWLDL algorithm) with the modified Wolfe–Powell line search (YWL) on these problems and compare its performance with the one of the following algorithms: HZ algorithm, the BG algorithm, and the DL+ algorithm, for the problems. The proposed algorithm is listed as follows:HZ algorithm: the DL method with parametert in [21] under the weak Wolfe–Powell line searchBG algorithm: the DL method with parametert in [22] under the weak Wolfe–Powell line searchDL+ algorithm: the DL method with parametert in [20] under the strong Wolfe–Powell line searchTable 1
Test problems.
Nr.Test problems1Extended Freudenstein and Roth function2Extended trigonometric function3Extended Rosenbrock function4Extended white and holst function5Extended beale function6Extended penalty function7Perturbed quadratic function8Raydan 1 function9Raydan 2 function10Diagonal 1 function11Diagonal 2 function12Diagonal 3 function13Hager function14Generalized tridiagonal 1 function15Extended tridiagonal 1 function16Extended three exponential terms function17Generalized tridiagonal 2 function18Diagonal 4 function19Diagonal 5 function20Extended Himmelblau function21Generalized PSC1 function22Extended PSC1 function23Extended Powell function24Extended block diagonal BD1 function25Extended Maratos function26Extended cliff function27Quadratic diagonal perturbed function28Extended wood function29Extended Hiebert function30Quadratic function QF1 function31Extended quadratic penalty QP1 function32Extended quadratic penalty QP2 function33A quadratic function QF2 function34Extended EP1 function35Extended tridiagonal-2 function36BDQRTIC function (CUTE)37TRIDIA function (CUTE)38ARWHEAD function (CUTE)39ARWHEAD Function (CUTE)40NONDQUAR function (CUTE)41DQDRTIC function (CUTE)42EG2 function (CUTE)43DIXMAANA function (CUTE)44DIXMAANB function (CUTE)45DIXMAANC function (CUTE)46DIXMAANE function (CUTE)47Partial perturbed quadratic function48Broyden tridiagonal function49Almost perturbed quadratic function50Tridiagonal perturbed quadratic function51EDENSCH function (CUTE)52VARDIM function (CUTE)53STAIRCASE S1 function54LIARWHD function (CUTE)55DIAGONAL 6 function56DIXON3DQ function (CUTE)57DIXMAANF function (CUTE)58DIXMAANG function (CUTE)59DIXMAANH function (CUTE)60DIXMAANI function (CUTE)61DIXMAANJ function (CUTE)62DIXMAANK function (CUTE)63DIXMAANL function (CUTE)64DIXMAAND function (CUTE)65ENGVAL1 function (CUTE)66FLETCHCR function (CUTE)67COSINE function (CUTE)68Extended DENSCHNB function (CUTE)69DENSCHNF function (CUTE)70SINQUAD function (CUTE)71BIGGSB1 function (CUTE)72Partial perturbed quadratic PPQ2 function73Scaled quadratic SQ1 function74Scaled quadratic SQ2 functionIn this part of the numerical experiment, we introduce the stopping rules, dimensions, and some parameters as follows:Stop rules (the Himmelblau stop rule [31]): if fxk>e1, let stop1=fxk−fxk+1/fxk or stop1=fxk−fxk+1. If the condition gx<ε or stop1<e2 is satisfied, where e1=e2=10−6, ε=10−6. The algorithm will stop if the number of iterations is greater than 1000.Dimension: 3000, 6000, and 9000 variables.Parameters:δ=0.2, δ1=0.05, and σ=0.9.The columns of Table1 have the following meanings:Nr: the number of tested problemsTest problems: the name of problemsThe comparison data can be shown as follows:NI: the number of iterationsNFG: the total of the function and gradient evaluationsCPU: the CPU time of the algorithm spent in secondsWe used the tool presented by Dolan and Moré [32] in these numerical reports, the new tool to show their performance in order to analyse the efficiency of the YWLDL algorithm, HZ algorithm, BG algorithm, and DL+ algorithm, and Figures 1–3 show the profiles relative to the CPU time, NI, and NFG, respectively. Figure 1 presents that YWLDL successfully solves about 35 percent of the test problems with the CPU time in seconds, HZ solves about 18 percent of the test problems, BG solves about 24 percent of the test problems, and DL+ solves about 6 percent of the test problems. We can conclude that YWLDL is more competitive than the HZ algorithm, BG algorithm, and DL+ algorithm since its performance curves corresponding to the CPU time are best. Figures 2 and 3 show that the robustness of YWLDL algorithm is worse than that of the BG algorithm. The YWLDL algorithm can successfully solve most of the test problems. Altogether, it is clear that the YWLDL algorithm is efficient based on the experimental results and the YWLDL algorithm with modified Wolfe–Powell line search is competitive with the other four algorithms for these test problems.Figure 1
Performance profiles of these methods (CPU).Figure 2
Performance profiles of these methods (NI).Figure 3
Performance profiles of these methods (NFG).


### 4.2. Muskingum Model in Engineering Problems

It is well known that some algorithms for solving optimization problems have been reassessed as a major challenge in engineering problems. Many scholars hope to present some effective algorithms to solve these engineering problems. Parameter estimation is one of the important tools for the research of a well-known hydrologic engineering application problem called the nonlinear Muskingum model. The Muskingum model, depending on the water inflow and outflow, is a popular flood routing model defined as follows:The Muskingum model [33] is defined by(52)minfx1,x2,x3=∑i=1n−11−Δt6x1x2Ii+1+1−x2Qi+1x3−1−Δt6x1x2Ii+1−x2Qix3−Δt2Ii−Qi+Δt21−Δt3Ii+1−Qi+12,at time tk, where k=1,2,…,n, n denotes the total number of times; x1,x2, and x3 denote the storage time constant; the weighting factor, and an additional parameter, respectively; Δt denotes the time step; Ii denotes the observed inflow discharge; and Qi denotes the observed outflow discharges. In Chenggouwan and Linqing of Nanyunhe in the Haihe Basin, Tianjin, China, using actual observation data of flood run off process, Δt=12h and the initial point x=0,1,1T are presented. The detailed data for Ii and Qi in 1960, 1961, and 1964 can be found in [34]. The tested results of the final points are listed in Table 2.Table 2
Results of the algorithms.
Algorithmx1x2x3BFGS [35]10.81560.98261.0219HIWO [33]13.28130.80010.9933Algorithm NDL11.19370.99990.9993Figures4–6 can draw at least three conclusions: (i) It is not different from the BFGS method and HIWO method, the presented algorithm provides a good approximation for these data, and the YWLDL algorithm can effectively be used to study this nonlinear Muskingum model. (ii) In the parameter estimation of the Muskingum model, YWLDL Algorithm shows good approximation. (iii) The final points (x1,x2, and x3) are competitive with the final points of similar algorithms.Figure 4
Performance of data in 1960.Figure 5
Performance of data in 1961.Figure 6
Performance of data in 1964.


### 4.3. Image Restoration Problems

In this section, we will use the proposed algorithm to recover the original image from the image destroyed by impulse noise. It has important practical significance in the field of optimization. The selection of parameters is similar to that in the section of Numerical Experiments. The stop condition isfk+1−fk/fk<10−3 or xk+1−xk/xk<10−3 holds. The experiments choose Barbara 512×512, Baboon 512×512, and Lena 512×512 as the test images. The detailed performance results are given in Figures 7–9. It is not difficult to observe that both HZ algorithm, BG algorithm, and DL+ algorithm and YWLDL algorithm are tested in the image restoration of tested images. The expenditure of the CPU time is listed in Table 3 to compare the YWLDL algorithm with the other algorithms.Figure 7
Restoration of the Babara, Baboon, and Lena images by using the HZ algorithm, BG algorithm, DL+ algorithm, and YWLDL algorithm. From left to right: a noisy image with 25% salt-and-pepper noise, restorations obtained by minimizingz with the HZ algorithm, BG algorithm, and DL+ algorithm and YWLDL algorithm.Figure 8
Restoration of the Babara, Baboon, and Lena images by using the HZ algorithm, BG algorithm, DL+ algorithm, and YWLDL algorithm. From left to right: a noisy image with 45% salt-and-pepper noise, restorations obtained by minimizingz with the HZ algorithm, BG algorithm, and DL+ algorithm and YWLDL algorithm.Figure 9
Restoration of the Babara, Baboon, and Lena images by the HZ algorithm, BG algorithm, DL+ algorithm, and YWLDL algorithm. From left to right: a noisy image with 65% salt-and-pepper noise, restorations obtained by minimizingz with the HZ algorithm, BG algorithm, and DL+ algorithm and YWLDL algorithm.Table 3
The CPU time of HZ algorithm, BG algorithm, DL+ algorithm, and YWLDL algorithm in seconds.
25% noiseBarbaraBaboonLenaTotalHZ algorithm0.843751.2187501.0468753.109375BG algorithm1.0000000.9218751.0312502.953125DL+ algorithm1.0156250.9531250.9531252.921875YWLDL algorithm0.9375000.9062500.9375002.7812545% noiseBarbaraBaboonLenaTotalHZ algorithm1.3281251.3125001.3437503.984375BG algorithm1.3593751.2852501.1875003.832125DL+ algorithm1.2500001.2656251.281253.796875YWLDL algorithm1.2031251.1250001.156253.48437565% noiseBarbaraBaboonLenaTotalHZ algorithm1.8125001.9062501.6718755.390625BG algorithm1.9218751.5468751.781505.25025DL+ algorithm1.656251.5781251.7656255.00000YWLDL algorithm1.5468751.5000001.5625004.609375From Table3 and Figures 7–9, we may draw the following conclusions: (i) It pretty obviously takes less time to restore an image with 25% noise than one with 65% noise. (ii) When the salt-and-pepper noise increases, the cost to restore the image increases. (iii) The YWLDL algorithm shows advantage to the HZ algorithm, BG algorithm, and DL+ algorithm in image restoration problems.


## 4.1. Normal Unconstrained Optimization Problems

In this section, we test the effect of some algorithms on numerical problems, and the unconstrained optimization problems are listed in Table1. We will report on various numerical implementations of our presented method (YWLDL algorithm) with the modified Wolfe–Powell line search (YWL) on these problems and compare its performance with the one of the following algorithms: HZ algorithm, the BG algorithm, and the DL+ algorithm, for the problems. The proposed algorithm is listed as follows:HZ algorithm: the DL method with parametert in [21] under the weak Wolfe–Powell line searchBG algorithm: the DL method with parametert in [22] under the weak Wolfe–Powell line searchDL+ algorithm: the DL method with parametert in [20] under the strong Wolfe–Powell line searchTable 1
Test problems.
Nr.Test problems1Extended Freudenstein and Roth function2Extended trigonometric function3Extended Rosenbrock function4Extended white and holst function5Extended beale function6Extended penalty function7Perturbed quadratic function8Raydan 1 function9Raydan 2 function10Diagonal 1 function11Diagonal 2 function12Diagonal 3 function13Hager function14Generalized tridiagonal 1 function15Extended tridiagonal 1 function16Extended three exponential terms function17Generalized tridiagonal 2 function18Diagonal 4 function19Diagonal 5 function20Extended Himmelblau function21Generalized PSC1 function22Extended PSC1 function23Extended Powell function24Extended block diagonal BD1 function25Extended Maratos function26Extended cliff function27Quadratic diagonal perturbed function28Extended wood function29Extended Hiebert function30Quadratic function QF1 function31Extended quadratic penalty QP1 function32Extended quadratic penalty QP2 function33A quadratic function QF2 function34Extended EP1 function35Extended tridiagonal-2 function36BDQRTIC function (CUTE)37TRIDIA function (CUTE)38ARWHEAD function (CUTE)39ARWHEAD Function (CUTE)40NONDQUAR function (CUTE)41DQDRTIC function (CUTE)42EG2 function (CUTE)43DIXMAANA function (CUTE)44DIXMAANB function (CUTE)45DIXMAANC function (CUTE)46DIXMAANE function (CUTE)47Partial perturbed quadratic function48Broyden tridiagonal function49Almost perturbed quadratic function50Tridiagonal perturbed quadratic function51EDENSCH function (CUTE)52VARDIM function (CUTE)53STAIRCASE S1 function54LIARWHD function (CUTE)55DIAGONAL 6 function56DIXON3DQ function (CUTE)57DIXMAANF function (CUTE)58DIXMAANG function (CUTE)59DIXMAANH function (CUTE)60DIXMAANI function (CUTE)61DIXMAANJ function (CUTE)62DIXMAANK function (CUTE)63DIXMAANL function (CUTE)64DIXMAAND function (CUTE)65ENGVAL1 function (CUTE)66FLETCHCR function (CUTE)67COSINE function (CUTE)68Extended DENSCHNB function (CUTE)69DENSCHNF function (CUTE)70SINQUAD function (CUTE)71BIGGSB1 function (CUTE)72Partial perturbed quadratic PPQ2 function73Scaled quadratic SQ1 function74Scaled quadratic SQ2 functionIn this part of the numerical experiment, we introduce the stopping rules, dimensions, and some parameters as follows:Stop rules (the Himmelblau stop rule [31]): if fxk>e1, let stop1=fxk−fxk+1/fxk or stop1=fxk−fxk+1. If the condition gx<ε or stop1<e2 is satisfied, where e1=e2=10−6, ε=10−6. The algorithm will stop if the number of iterations is greater than 1000.Dimension: 3000, 6000, and 9000 variables.Parameters:δ=0.2, δ1=0.05, and σ=0.9.The columns of Table1 have the following meanings:Nr: the number of tested problemsTest problems: the name of problemsThe comparison data can be shown as follows:NI: the number of iterationsNFG: the total of the function and gradient evaluationsCPU: the CPU time of the algorithm spent in secondsWe used the tool presented by Dolan and Moré [32] in these numerical reports, the new tool to show their performance in order to analyse the efficiency of the YWLDL algorithm, HZ algorithm, BG algorithm, and DL+ algorithm, and Figures 1–3 show the profiles relative to the CPU time, NI, and NFG, respectively. Figure 1 presents that YWLDL successfully solves about 35 percent of the test problems with the CPU time in seconds, HZ solves about 18 percent of the test problems, BG solves about 24 percent of the test problems, and DL+ solves about 6 percent of the test problems. We can conclude that YWLDL is more competitive than the HZ algorithm, BG algorithm, and DL+ algorithm since its performance curves corresponding to the CPU time are best. Figures 2 and 3 show that the robustness of YWLDL algorithm is worse than that of the BG algorithm. The YWLDL algorithm can successfully solve most of the test problems. Altogether, it is clear that the YWLDL algorithm is efficient based on the experimental results and the YWLDL algorithm with modified Wolfe–Powell line search is competitive with the other four algorithms for these test problems.Figure 1
Performance profiles of these methods (CPU).Figure 2
Performance profiles of these methods (NI).Figure 3
Performance profiles of these methods (NFG).


## 4.2. Muskingum Model in Engineering Problems

It is well known that some algorithms for solving optimization problems have been reassessed as a major challenge in engineering problems. Many scholars hope to present some effective algorithms to solve these engineering problems. Parameter estimation is one of the important tools for the research of a well-known hydrologic engineering application problem called the nonlinear Muskingum model. The Muskingum model, depending on the water inflow and outflow, is a popular flood routing model defined as follows:The Muskingum model [33] is defined by(52)minfx1,x2,x3=∑i=1n−11−Δt6x1x2Ii+1+1−x2Qi+1x3−1−Δt6x1x2Ii+1−x2Qix3−Δt2Ii−Qi+Δt21−Δt3Ii+1−Qi+12,at time tk, where k=1,2,…,n, n denotes the total number of times; x1,x2, and x3 denote the storage time constant; the weighting factor, and an additional parameter, respectively; Δt denotes the time step; Ii denotes the observed inflow discharge; and Qi denotes the observed outflow discharges. In Chenggouwan and Linqing of Nanyunhe in the Haihe Basin, Tianjin, China, using actual observation data of flood run off process, Δt=12h and the initial point x=0,1,1T are presented. The detailed data for Ii and Qi in 1960, 1961, and 1964 can be found in [34]. The tested results of the final points are listed in Table 2.Table 2
Results of the algorithms.
Algorithmx1x2x3BFGS [35]10.81560.98261.0219HIWO [33]13.28130.80010.9933Algorithm NDL11.19370.99990.9993Figures4–6 can draw at least three conclusions: (i) It is not different from the BFGS method and HIWO method, the presented algorithm provides a good approximation for these data, and the YWLDL algorithm can effectively be used to study this nonlinear Muskingum model. (ii) In the parameter estimation of the Muskingum model, YWLDL Algorithm shows good approximation. (iii) The final points (x1,x2, and x3) are competitive with the final points of similar algorithms.Figure 4
Performance of data in 1960.Figure 5
Performance of data in 1961.Figure 6
Performance of data in 1964.


## 4.3. Image Restoration Problems

In this section, we will use the proposed algorithm to recover the original image from the image destroyed by impulse noise. It has important practical significance in the field of optimization. The selection of parameters is similar to that in the section of Numerical Experiments. The stop condition isfk+1−fk/fk<10−3 or xk+1−xk/xk<10−3 holds. The experiments choose Barbara 512×512, Baboon 512×512, and Lena 512×512 as the test images. The detailed performance results are given in Figures 7–9. It is not difficult to observe that both HZ algorithm, BG algorithm, and DL+ algorithm and YWLDL algorithm are tested in the image restoration of tested images. The expenditure of the CPU time is listed in Table 3 to compare the YWLDL algorithm with the other algorithms.Figure 7
Restoration of the Babara, Baboon, and Lena images by using the HZ algorithm, BG algorithm, DL+ algorithm, and YWLDL algorithm. From left to right: a noisy image with 25% salt-and-pepper noise, restorations obtained by minimizingz with the HZ algorithm, BG algorithm, and DL+ algorithm and YWLDL algorithm.Figure 8
Restoration of the Babara, Baboon, and Lena images by using the HZ algorithm, BG algorithm, DL+ algorithm, and YWLDL algorithm. From left to right: a noisy image with 45% salt-and-pepper noise, restorations obtained by minimizingz with the HZ algorithm, BG algorithm, and DL+ algorithm and YWLDL algorithm.Figure 9
Restoration of the Babara, Baboon, and Lena images by the HZ algorithm, BG algorithm, DL+ algorithm, and YWLDL algorithm. From left to right: a noisy image with 65% salt-and-pepper noise, restorations obtained by minimizingz with the HZ algorithm, BG algorithm, and DL+ algorithm and YWLDL algorithm.Table 3
The CPU time of HZ algorithm, BG algorithm, DL+ algorithm, and YWLDL algorithm in seconds.
25% noiseBarbaraBaboonLenaTotalHZ algorithm0.843751.2187501.0468753.109375BG algorithm1.0000000.9218751.0312502.953125DL+ algorithm1.0156250.9531250.9531252.921875YWLDL algorithm0.9375000.9062500.9375002.7812545% noiseBarbaraBaboonLenaTotalHZ algorithm1.3281251.3125001.3437503.984375BG algorithm1.3593751.2852501.1875003.832125DL+ algorithm1.2500001.2656251.281253.796875YWLDL algorithm1.2031251.1250001.156253.48437565% noiseBarbaraBaboonLenaTotalHZ algorithm1.8125001.9062501.6718755.390625BG algorithm1.9218751.5468751.781505.25025DL+ algorithm1.656251.5781251.7656255.00000YWLDL algorithm1.5468751.5000001.5625004.609375From Table3 and Figures 7–9, we may draw the following conclusions: (i) It pretty obviously takes less time to restore an image with 25% noise than one with 65% noise. (ii) When the salt-and-pepper noise increases, the cost to restore the image increases. (iii) The YWLDL algorithm shows advantage to the HZ algorithm, BG algorithm, and DL+ algorithm in image restoration problems.


## 5. Conclusion

In this paper, the YWLDL conjugate gradient algorithm that combines with the modified WWP line search technique is proposed. The theory of other methods for constructing parametert is one of the interesting works, and we think that some modified DL methods with other parameter t under the modified WWP line search technique can also solve the Muskingum model, and we may do this work in the future.



---

*Source: 6279543-2020-09-18.xml*