# A Modified Three-Term Type CD Conjugate Gradient Algorithm for Unconstrained Optimization Problems

Authors: Zhan Wang; Pengyuan Li; Xiangrong Li; Hongtruong Pham
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Conjugate gradient methods are well-known methods which are widely applied in many practical fields. CD conjugate gradient method is one of the classical types. In this paper, a modified three-term type CD conjugate gradient algorithm is proposed. Some good features are presented as follows: (i) A modified three-term type CD conjugate gradient formula is presented. (ii) The given algorithm possesses sufficient descent property and trust region property. (iii) The algorithm has global convergence with the modified weak Wolfe–Powell (MWWP) line search technique and projection technique for general function. The new algorithm has made great progress in numerical experiments. It shows that the modified three-term type CD conjugate gradient method is more competitive than the classical CD conjugate gradient method.


---

## Body

## 1. Introduction

Considering the problem(1)minfxx∈ℜn,where f:ℜn⟶ℜ is a continuously differentiable function. This kind of model is often used to solve some problems in applied mathematics, economics, engineering, and so on. Generally, the following iteration formula is used to generate the next iteration point:(2)xk+1=xk+αkdk,k=0,1,2,…,where xk+1 and xk denote the next iteration point and current iteration point, respectively. αk is a step-length and dk is the search direction. The search direction dk generated by Conjugated Gradient (CG) method is defined by the following formula:(3)dk+1=−gk+1,ifk=0,−gk+1+βkdk,ifk≥1,where gk=gxk is the gradient of fx at xk and βk is a parameter. Different βk will generate different CG methods [1–10]. There are six classical forms of βk:(4)βkPRP=gk+1Tykgk2,8,9,βkHS=gk+1TykykTdk,6,βkLS=gk+1Tyk−dkTgk,7,βkFR=gk+12gk2,5,βkCD=gk+12−dkTgk,4,βkDY=gk+12ykTdk,2,where yk=gk+1−gk, and ⋅ is the Euclidean norm. Those formulas can be divided into two categories: One includes PRP method, HS method, and LS method, which have good numerical performance; the other includes FR method, CD method, and DY method, which have good theory convergence. About these methods, many scholars had applied them to solve nonlinear monotone equations and normal optimization problems, and some good results were achieved [11–16].Zhang et al. [17] presented a modified PRP CG formula as follows:(5)dk+1=−gk+1+gk+1Tykdk−dkTgk+1ykgkTgk.They proved that the modified PRP method is globally convergent with Armijo-type line search.Yuan et al. [18] proposed another modified PRP CG formula with(6)dk+1=−γkgk+1+βkPRPdk−dkTgk+1ykgk2,where γk=θk/minη1skTyk,η2θk,θk=skTyk/sk2,sk=xk+1−xk,η1∈0,1. and η2∈0,1. Yuan et al. [18] obtained the global convergence of the modified PRP method with a modified weak Wolfe–Powell (MWWP) line search technique, which was proposed by Yuan et al. [19]:(7)fxk+αkdk≤fk+λαkgkTdk+αkmin−λ1gkTdk,λαk2dk2,(8)gxk+αkdkTdk≥μgkTdk+min−λ1gkTdk,λαkdk2,where λ∈0,1/2, λ1∈0,λ, and μ∈λ,1. Yuan et al. [16] obtained the global convergence of PRP method by using the above modified weak Wolfe–Powell line search technique and a projection technique:(9)xk+1=xk+gψkTψk−xk+χψk−xk2gψk−gxk2gψk−gxk,where ψk=xk+αkdk is the next point and parameter χ>0. With this projection technique, any unsatisfactory iteration points generated by the normal PRP algorithm will be projected onto a surface to overcome the failure to converge.Motivated by the above researches, a modified three-term CD conjugate gradient algorithm is presented with (7), (8), and (9) in this paper. Some good properties are obtained as follows:(i)
A modified three-term type CD conjugate gradient formula is presented(ii)
The given algorithm possesses sufficient descent property and trust region property(iii)
The algorithm has global convergence with the MWWP line search technique and projection technique for general functionThis paper is organized as follows: the next section will introduce the modified CD formula and relative algorithm; section3 gives the proof of the global convergence of the new algorithm; numerical experiments are given in section 4; some conclusions are presented in section 5. Throughout this paper, we use ⋅ to denote the Euclidean norm, gxk and gxk+1 are replaced by gk and gk+1, respectively.


## 2. Motivation and Algorithm

The convergence of CD conjugate gradient method has been proved [4]; however, the numerical results of this method are worse than the PRP method and others. Therefore, it is necessary to propose a new search direction to improve the numerical performance of the CD method. Meanwhile, the sufficient descent property is significant for obtaining the convergence of the conjugate gradient method:(10)gkTdk≤−ηgk2.Then, we also hope that we can propose a new method that possesses this property. Inspired by the above discussion, a modified three-term type CD conjugate gradient formula is designed by the following:(11)dk+1=−gk+1,ifk=0,−γkgk+1+gk+1Tgk+1dkmax−dkTgk,η1gk+1dk−gk+1Tdkgk+1max−dkTgk,η1gk+1dk,ifk≥1,where γk=θk/minη2skTyk,η3θk,θk=sk2,sk=xk+1−xk,yk=gk+1−gk,η1>0, and η2,η3∈0,1. The steps of the given algorithm are listed as follows.


## 3. Convergence Analysis

In this section, we are going to analyse the convergence of the proposed algorithm. The following assumptions are needed.Assumption 1.
(i)
The level setΩ=x∈ℜn:fx≤fx0 is bounded.(ii)
fx is twice continuously differentiable and bounded below, and the gradient function gx is Lipschitz continuous, which means that there exists a constant L>0 such that(12)gx−gy≤Lx−y,for allx,y∈Ω.Lemma 1.
Let the search directiondk be generated by formula (11), then, the following relations hold:(13)gk+1Tdk+1≤−ηgk+12.(14)dk+1≤ξgk+1,where constants η,ξ>0.Proof.
According to the definition ofdk,(15)gk+1Tdk+1=gk+1T−γkgk+1+gk+1Tgk+1dkmax−dkTgk,η1gk+1dk−gk+1Tdkgk+1max−dkTgk,η1gk+1dk=−γkgk+12+gk+12gk+1Tdkmax−dkTgk,η1gk+1dk−gk+1Tdkgk+12max−dkTgk,η1gk+1dk=−γkgk+12.
For the parameterγk, we have the following:(16)γk=θkminη2skTyk,η3θk≥θkη3θk=1η3,then gk+1Tdk+1≤−1/η3gk+12 holds. Letting η=1/η3, the relation (13) is obtained.
Using the definition of the parameterγk, we analyse the value of γk in two cases:Case 1.
minη2skTyk,η3θk=η2skTyk. Similar to Lemma 1 of [20], skTyk≥ρsk2, where ρ>0 is a scalar; then(17)γk=θkminη2skTyk,η3θk=θkη2skTyk≤θkη2ρsk2=sk2η2ρsk2=1η2ρ.Case 2.
minη2skTyk,η3θk=η3θk. Then(18)γk=θkminη2skTyk,η3θk=θkη3θk=1η3.
Lettingξ0=max1/η2ρ,1/η3, we have 0<γk≤ξ0. Thus,(19)dk+1=−γkgk+1+gk+1Tgk+1dkmax−dkTgk,η1gk+1dk−gk+1Tdkgk+1max−dkTgk,η1gk+1dk≤γkgk+1+gk+1gk+1dkmax−dkTgk,η1gk+1dk+gk+1dkgk+1max−dkTgk,η1gk+1dk≤γkgk+1+gk+1gk+1dkη1gk+1dk+gk+1dkgk+1η1gk+1dk≤γkgk+1+2η1gk+1≤ξ0+2η1gk+1.
Letξ=ξ0+2/η1ξ=ξ0+2/η1; then (14) holds. The proof is complete.Remark 1.
The relation (14) shows that the optimization algorithm possesses the trust region feature.
The following theorem is obtained for the global convergence of Algorithm1.Algorithm 1: The modified three-term type CD conjugate gradient algorithm.
Step 1: Given the initial pointx0∈ℜn, constants ϵ∈0,1, 0<λ1<λ/2<λ<1/2, λ<μ<1,η1>0,η2,η3∈0,1, let d0=−g0, k:=0.Step 2: Ifgk≤ε, then, stop; otherwise, proceed to the next step.Step 3: Compute step sizeαk by the line search (7) and (8).Step 4: Letψk=xk+αkdk.Step 5: If−λ1gkTdk>λαkdk2 holds, let xk+1=ψk, yk=gk+1−gk, and go to Step 7; otherwise, go to Step 6.Step 6: Letxk+1 be defined by (9), yk∗=gψk−gxk, and yk=yk∗.Step 7: Ifgk+1≤ε, stop; otherwise, proceed to next step.Step 8: Calculate the search directiondk by (11).Step 9: Letk:=k+1, and go to step 2.Theorem 1.
Assume thatαk,dk and xk are generated by Algorithm 1 and Lemma 1 holds. Then,(20)limk⟶+∞gk=0.Proof.
From the line search (8), we have the following:(21)gxk+αkdkTdk≥μgkTdk+min−λ1gkTdk,λαkdk2≥μgkTdk.
According to (ii) of Assumption1,(22)αkLdk2≥gk+1−gkTdk≥−1−μgkTdk.
Then, we have the following:(23)αk≥−1−μLdk2gkTdk.
Using Lemma1,(24)αk≥−1−μLdk2gkTdk≥1−μηgk2Ldk2≥1−μηLξ2.
From Assumption1, line search (7) and sufficient descent property (13),(25)fxk+αkdk≤fk+λαkgkTdk+αkmin−λ1gkTdk,λαk2dk2≤fk+λ−λ1αkgkTdk≤fk−ηλ−λ1αkgk2≤fk−η2λ−λ11−μLξ2gk2.
Summing these inequalities fromk=0 to +∞,(26)∑k=0∞gk2<f0−f+∞.
From Assumption1, it is easy to know that fx is bounded. Then, gk⟶0. The proof is complete.


## 4. Numerical Results

This section will report the numerical experiments with some classical optimization problems, the nonlinear Muskingum model, and the application in image restoration problems. All the tests are coded in MATLAB R2014a, run on a PC with a 2.50 GHz CPU, and 4.00 GB of memory running the Windows 10 operating system.


### 4.1. Normal Unconstrained Optimization Problems

In this subsection, the numerical experiments would be done with some test problems from [20], and all test problems are listed in Table 1. We compare Algorithm 1 with the classical CD conjugated method (called Algorithm 2) and the classical PRP conjugated method (called Algorithm 3). The detailed experimental data are list in Table 2. Figures 1–3 show the performance of these three algorithms related to CPU, NI, and NFG. Some columns of Tables 1 and 2 and Figures 1–3 have the following meanings:(i)
No: the serial number of the problem.(ii)
Dim: the dimension of the variable x.(iii)
NI: the iteration numbers.(iv)
NFG: the sum of function value and gradient value.(v)
CPU: the calculation time in seconds.(vi)
Dimension: the dimensions are 3000, 9000, and 15000.(vii)
Initialization: the parameters of the algorithms are chosen to be λ=0.1,λ1=0.01,μ=0.9,η1=0.01,η2=0.1,η3=0.1, e1=e2=10−5, and ϵ=10−6, and the initial search direction d0=−g0.(viii)
Stop rules: the following Himmeblau stop rule [21] is used: if fxk>e1, let stop1=fxk−fxk+1/fxk; otherwise, let stop1=fxk−fxk+1. For every problem, if the conditions gxk<ε or stop1<e2 are satisfied, then the program is stopped. This program is also stopped when the number of iterations is greater than one thousand.Table 1
Test problems.
NoTest 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 functionTable 2
The numerical results of Algorithms1–3.
No.DimAlgorithm 1Algorithm 2Algorithm 3NINFGCPU timeNINFGCPU timeNINFGCPU time130007410.48437520730.07812516650.1093751900013890.32812520700.26562516620.281251150007410.203125421440.812520850.56252300016911381.46875832600.328125893610.484375290001083961.34375912860.875892980.8906252150001255902.765625932941.328125953061.453125330009490.031251094150.203125321060.0625390005260.078125913480.2656256290.0156253150005260.015625963710.43759500.07812543000432000.2031251675720.515625291040.1093754900021910.203125512020.515625291090.2187541500021910.359375451760.625431640.625530002140.015625371300.109375883670.687559000411280.296875361250.28125291090.718755150003260.046875381310.421875531710.73437563000923270.1718751133580.156251243910.3125690001043400.3906251334200.406251444530.56256150001163700.656251514740.6406251454660.7656257300042347462.4062596830231.203125100030411.265625790001023730.359375100030752.453125100030623.093757150002729871.5781252147180.921875100030464.2968758300018650.04687523740.0312525790.0468758900017620.07812523740.0937525790.10937581500017620.1562523740.12525790.1718759300019650.031259280.0156253250.03125990003260.0468759280.046875231000.093759150003260.0468759280.03125241100.2343751030002140.0156252140.015625214010900021402140214010150002140.031252140.0156252140.031251130003190.03125752630.14062542101190003190.031251755930.8281256360.062511150003190.14062522880.1406257370.07812512300017570.0312515460.062517550.04687512900016540.12516490.0937517560.1875121500016540.12516490.10937517560.156251330002140231380.0781252140.031251390002140.031253180.046875214013150002140.0156252140.0156252140.062514300018850.56258270.15625371691.06251490007390.7968754140.21875452744.89062514150007411.2968754140.359375503439.7515300017590.484375521771.046875331750.79687515900025831.328125501692.65625331752.359375151500029952.5625411383.578125331753.796875163000316013400.03125401510.1093751690008230.04687517520.062524730.09375161500017590.1562515460.0937527820.1718751730002140.015625401220.1875531640.234375179000361480.578125351070.375471490.54687517150005420.1562527830.546875491551.078125183000361630.078125312038445911.875189000402290.156253120.04687539146753.656251815000513250.359375312039447115.4218751930004300.0156253110.01562521401990004390.07812531102140.01562519150004390.093753110.0468752140.015625203000381340.0937522700.031253180209000401420.1562530940.06253180.0156252015000401370.1875381180.1253180.04687521300021640.046875381210.09375271030.12521900021640.265625381210.21875271030.1875211500021640.1875381210.29687526920.2343752230002140.0156256350.06256280.093752290002140.0468756350.156256280.17187522150002140.093756350.3281256280.515625233000231090.0781251806100.54687520710.09375239000231090.281251906571.5100030037.6252315000231090.3593752067072.7343751000300311.656252430009440.015625501910.1093756680.0156252490009440.125251070.1256690.12524150009440.125311290.256690.15625253000627018530.04687533980.0468752590009350.07812528830.046875511650.17187525150006260.0625341010.0937515690.078125263000862730.28125963050.171875953040.156252690001033510.593751073380.453125943010.406252615000964021.03125983130.671875953040.64062527300024428091.62522940.03125291190.04687527900019522902.40625642560.203125100030043.25271500094637845.984375502110.29687521800.0781252830009460.03125441510.09375361260.0781252890009460.0625501780.15625361230.0937528150009460.078125371240.171875341250.203125293000318042504240.046875299000318042404240.04687529150003180.031254320.031254240.0312530300013513880.609375100030630.921875100030131.12530900059141994.0625100030661.9375100030132.32812530150001073940.421875100030832.609375100030133.359375313000321080.078125401250.0625441390.062531900031980.09375431360.109375451420.1253115000331040.1875441390.21875481510.2532300031940.078125331020.046875501530.07812532900027840.140625641950.328125411280.234375321500029900.265625451400.3125461430.3437533300041304120390339000260.0468752602603315000260260260.0156253430004120.03125411031603490004120.0156255140.0156257200.0312534150004120.0156256170.031259260.093753530003170.0156258230.0312514410.031253590003170.0312512350.0312521620.0937535150005140.0312515440.07812525740.140625363000883441.7520810.3593757380.203125369000351492.12517690.8757380.4531253615000943949331232.7968757380.8437537300038014130.734375100031111.32812523850.04687537900032111831.37534411551.109375100030133.6718753715000100036866.40625100030784.375100030054.90625383000943740.18759300.0156255190.03125389000215858122740.0468754140.03125381500029411732.12517570.0781254140.046875393000618018530.015625381130.0468753990006180.0312519560.03125411220.10937539150006180.062520590.09375431280.1875403000592340.40625100031166.0468753190.0468754090003180.06251000310916.031253170.04687540150003170.0781251000310225.7656253170.07812541300016960.062528980.0312516600.046875419000231390.12523780.062516600.06254115000342420.3437519660.07812516600.0781254230006470.01562542806420.031254290006470.0781254280.0468756420.0312542150007600.1254280.06256420.0625433000211880.29687519600.21875581860.4218754390002140.062520630.359375682161.234375431500024810.76562520630.59375722282.31254430002140.01562527840.203125662160.43754490002140.04687528870.5752411.32812544150002140.07812528870.78125772472.312545300013400.09375431320.28125752280.51562545900013400.328125451380.8125792401.484375451500013400.375461411.34375812462.28125463000866630.96875601940.40625241490.281254690002140.0468751535102.9062517810915.45312546150002140.0781251545194.703125200135510.2031254730007623013.8593757622913.51562520713.718754790005518892.2343753411153.96875114517.125471500082304397.687586276382.312592306416.42187548300012520.0937530970.14062523820.1093754890001196652.71875351150.4375371330.5481500017714858.859375331090.68751263832.54687549300051654222.796875100030930.890625100030131.093754990001535600.5100031711.9375100030132.390625491500048718002.109375100030722.890625100030133.45312550300019416098.406251000302514.7656251000301315.2031255090003203100431695608.4843751000301342.484375501500024188820.4843751000310771.3751000301370.25513000492180.2812516490.07812528850.1255190002140.0312515460.17187528850.2812551150002140.07812515460.23437528850.468755230001494740.4218751735480.468751825750.4531255290001705411.1406251926071.156252066491.2812552150001785652.0468752016362.031252156781.9843755330003260.0312544114870.4531253260.0468755390003270.01562543014441.03125561930.14062553150002140.03125100030783.468752140.01562554300038114030.76562521930.031253180.046875549000481850.203125983540.31253180.031255415000100039787652380.3906253180.01562555300019650.10937514430.0468753250.06255590003260.0937515460.171875231000.39062555150003260.14062515460.34375231040.755630003160100031250.984375100029991.06255690003160.046875100031512.078125100029992.187556150003160.015625100031253.359375100029993.718755730002140.015625712260.513713982.2031255790002140.046875672111.2343751026023.04687557150002140.078125692211.984375210154610.8437558300013400.093751093580.79687558419853.92187558900013400.218751193982.23437522880.453125581500013400.3906251494904.6562522880.68755930003180.015625481700.3437518920383.1406255990003180.09375461630.875239268310.32812559150003180.09375541871.71875256291217.81256030004437711103570.734375804660.8593756090002140.0468751846193.515625977433.45312560150002140.0781251846245.85937510410006.43756130002140.015625732360.51562517518912.8756190002140.046875782551.45312518811935.79687561150002140.109375692292.031251146494.968756230003180.015625862800.625271030.18756290003180.078125712401.281251267023.60937562150003180.078125471601.390625754153.2563300015460.1562513945511576271.187563900015460.2656252528184.734375723091.515625631500015460.4531252217426.953125873633.04687564300018550.140625732220.437524860.187564900018550.34375772341.32812524860.484375641500018550.578125792402.32812524860.8593756530003190.10937531940.515625331020.5781256590003190.51562530911.437531961.565150003190.687530912.48437531962.4843756630006300.2031254210.0781254190.0781256690006300.54210.2343754190.265625661500012047911.0156254210.4531254190.37567300010640.093757690.0312511720.0468756790007420.046875382580.79687511690.156256715000221360.890625241700.7187511670.23437568300024800.07812522670.03125444910.328125689000214023700.0468752140.0312568150002140.062523700.0781252140.031256930005330531630.10937528880.06256990005330.046875511570.2187520710.14062569150005330.046875511570.35937520710.171875703000662771.125431670.67187513700.20312570900010450.521901.0312515770.718757015000682454.968759340.5937525982.031257130003160421330.0468753160.0468757190003160.015625421330.0625316071150003160.015625421330.1253160.04687572300020676541.437516358331.45312515602.78125729000100036941734.984375100030361571.609375156024.1257215000100036114739.8125163568751.625156066.70312573300056261182.67187532010550.28125100030170.984375739000100090698.703125100030481.90625100030172.375731500079856886.53125100030412.71875100030173.078125Figure 1
Performance profiles of these methods (CPU).Figure 2
Performance profiles of these methods (NI).Figure 3
Performance profiles of these methods (NGF).From the detailed experimental data of Table2, it is obvious to see that most of the problems can be solved quickly. For most of the problems, it takes less CPU time to solve those problems with the proposed algorithm. Meanwhile, progress has also been made in NI and NFG. Generally, the algorithm of the proposed method is promising versus the other algorithms. About the numerical results, the algorithm of Dolan and More [22] will be used to more directly show the performance profiles of these algorithms. In Figure 1, the curve of Algorithm 1 is always above the other algorithms. In Figure 2, the curves have the same trend. Algorithm 1 almost solves about 97% of the test problems in τ=30, while Algorithm 2 just solves 89.9% and Algorithm 3 just solves 87% in τ=30. Figure 3 shows a similar trend as Figure 2. All the above pictures show that the modified CD conjugate gradient algorithm is more robust and effective compared with the normal CD method and PRP method. In summary, Algorithm 1 is more competitive versus others.


### 4.2. The Muskingum Model

It is generally known that parameter estimation is a significant task in engineering applications. The nonlinear Muskingum model will be discussed as a common example of such an application in this subsection.The Muskingum Model [23] is defined by the following:(27)minfx1,x2,x3=∑i=1n−11−Δt6x1x2Ii+1+1−x2Qi+1x3−1−Δt6x1x2Ii+1−x2Qix3−Δt2Ii−Qi+Δt21−Δt3Ii+1−Qi+12.Some of the variables have the following meanings:(i)
n: the total time number.(ii)
x1: the storage time constant.(iii)
Ii: the observed inflow discharge.(iv)
x2: the weighting factor.(v)
Qi: the observed outflow discharges.(vi)
x3: an additional parameter.(vii)
Δt: the time step at time tii=1,2,…,n.In the experiment, the observed data of the flood run-off process from Chenggouwan and Linqing of Nanyunhe River in the Haihe Basin, Tianjin, China, are used. We choose the initial pointx=0,1,1T; detailed data about Ii and Qi for the years 1960, 1961, and 1964 were obtained (see [24] in detail). Δt=12h was selected. The results of these three algorithms are listed in Table 3. The performance of the presented algorithm is shown in Figures 4–6.Table 3
Results of the three algorithms.
Algorithmsx1x2x3BFGS [25]10.81560.98261.0219HIWO [23]13.28130.80010.9933Algorithm111.18481.00000.9995Figure 4
Performance of date in 1960.Figure 5
Performance of date in 1961.Figure 6
Performance of date in 1961.Some conclusions are obtained from this experiment: (1) from Figures4–6, we conclude that we can calculate approximations of flood outflows by using Algorithm 1, and Algorithm 1 is effective for the nonlinear Muskingum model; (2) the final points (x1, x2 and x3) of these three algorithms are interesting, and they are competitive with the final points of similar algorithms; and (3) the final points of Algorithm 1 are different from those of the BFGS method and HIWO method, which implies that the nonlinear Muskingum model has different optimum approximation solutions.


### 4.3. Image Restoration Problems

In this subsection, the above algorithms will be applied to image restoration problems. The original images corrupted by impulse noise are treated as objects here. These problems are regarded as one of the most difficult problems in optimization fields. Related parameter settings are similar to the above subsections, and the program will be stopped when the conditionfk+1−fk/fk<10−3 or xk+1−xk/xk<10−3 holds. The following three images are selected as processing objects: Banoon (512×512), Barbara (512×512), and Lena (512×512). The detail performances are shown in Figures 7–9. The CPU time taken to process images is listed in Table 4.Figure 7
Restoration of the Banoon image, Barbara image, and Lena image by Algorithms1–3. From left to right: a noisy image with 30% salt-and-pepper noise, the restorations obtained with Algorithms 1–3.Figure 8
Restoration of the Banoon image, Barbara image, and Lena image by Algorithms1–3. From left to right: a noisy image with 50% salt-and-pepper noise, the restorations obtained with the Algorithms 1–3.Figure 9
Restoration of the Banoon image, Barbara image, and Lena image by Algorithms1–3. From left to right: a noisy image with 70% salt-and-pepper noise, the restorations obtained with the Algorithms 1–3.Table 4
CPU time of those algorithms in seconds.
30% noiseLenaBarbaraBanoonTotalAlgorithm14.4384.3904.65613.484Algorithm 24.5635.2345.40615.203Algorithm 35.1566.3136.78118.25050% noiseLenaBarbaraBanoonTotalAlgorithm18.6097.8918.14124.641Algorithm 29.21910.68810.54730.454Algorithm 311.29714.39114.85940.54770% noiseLenaBarbaraBanoonTotalAlgorithm115.75010.57811.98438.312Algorithm 213.89114.43814.70343.032Algorithm 314.85919.92220.37555.156It is easy to see that all the algorithms are successful for image restoration problems. The results in Table4 reveal that the CPU time of Algorithm 1 is less than that of other algorithms, whether for $30\%$ noise problems, 50% noise problems, or for 70% noise problems.


## 4.1. Normal Unconstrained Optimization Problems

In this subsection, the numerical experiments would be done with some test problems from [20], and all test problems are listed in Table 1. We compare Algorithm 1 with the classical CD conjugated method (called Algorithm 2) and the classical PRP conjugated method (called Algorithm 3). The detailed experimental data are list in Table 2. Figures 1–3 show the performance of these three algorithms related to CPU, NI, and NFG. Some columns of Tables 1 and 2 and Figures 1–3 have the following meanings:(i)
No: the serial number of the problem.(ii)
Dim: the dimension of the variable x.(iii)
NI: the iteration numbers.(iv)
NFG: the sum of function value and gradient value.(v)
CPU: the calculation time in seconds.(vi)
Dimension: the dimensions are 3000, 9000, and 15000.(vii)
Initialization: the parameters of the algorithms are chosen to be λ=0.1,λ1=0.01,μ=0.9,η1=0.01,η2=0.1,η3=0.1, e1=e2=10−5, and ϵ=10−6, and the initial search direction d0=−g0.(viii)
Stop rules: the following Himmeblau stop rule [21] is used: if fxk>e1, let stop1=fxk−fxk+1/fxk; otherwise, let stop1=fxk−fxk+1. For every problem, if the conditions gxk<ε or stop1<e2 are satisfied, then the program is stopped. This program is also stopped when the number of iterations is greater than one thousand.Table 1
Test problems.
NoTest 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 functionTable 2
The numerical results of Algorithms1–3.
No.DimAlgorithm 1Algorithm 2Algorithm 3NINFGCPU timeNINFGCPU timeNINFGCPU time130007410.48437520730.07812516650.1093751900013890.32812520700.26562516620.281251150007410.203125421440.812520850.56252300016911381.46875832600.328125893610.484375290001083961.34375912860.875892980.8906252150001255902.765625932941.328125953061.453125330009490.031251094150.203125321060.0625390005260.078125913480.2656256290.0156253150005260.015625963710.43759500.07812543000432000.2031251675720.515625291040.1093754900021910.203125512020.515625291090.2187541500021910.359375451760.625431640.625530002140.015625371300.109375883670.687559000411280.296875361250.28125291090.718755150003260.046875381310.421875531710.73437563000923270.1718751133580.156251243910.3125690001043400.3906251334200.406251444530.56256150001163700.656251514740.6406251454660.7656257300042347462.4062596830231.203125100030411.265625790001023730.359375100030752.453125100030623.093757150002729871.5781252147180.921875100030464.2968758300018650.04687523740.0312525790.0468758900017620.07812523740.0937525790.10937581500017620.1562523740.12525790.1718759300019650.031259280.0156253250.03125990003260.0468759280.046875231000.093759150003260.0468759280.03125241100.2343751030002140.0156252140.015625214010900021402140214010150002140.031252140.0156252140.031251130003190.03125752630.14062542101190003190.031251755930.8281256360.062511150003190.14062522880.1406257370.07812512300017570.0312515460.062517550.04687512900016540.12516490.0937517560.1875121500016540.12516490.10937517560.156251330002140231380.0781252140.031251390002140.031253180.046875214013150002140.0156252140.0156252140.062514300018850.56258270.15625371691.06251490007390.7968754140.21875452744.89062514150007411.2968754140.359375503439.7515300017590.484375521771.046875331750.79687515900025831.328125501692.65625331752.359375151500029952.5625411383.578125331753.796875163000316013400.03125401510.1093751690008230.04687517520.062524730.09375161500017590.1562515460.0937527820.1718751730002140.015625401220.1875531640.234375179000361480.578125351070.375471490.54687517150005420.1562527830.546875491551.078125183000361630.078125312038445911.875189000402290.156253120.04687539146753.656251815000513250.359375312039447115.4218751930004300.0156253110.01562521401990004390.07812531102140.01562519150004390.093753110.0468752140.015625203000381340.0937522700.031253180209000401420.1562530940.06253180.0156252015000401370.1875381180.1253180.04687521300021640.046875381210.09375271030.12521900021640.265625381210.21875271030.1875211500021640.1875381210.29687526920.2343752230002140.0156256350.06256280.093752290002140.0468756350.156256280.17187522150002140.093756350.3281256280.515625233000231090.0781251806100.54687520710.09375239000231090.281251906571.5100030037.6252315000231090.3593752067072.7343751000300311.656252430009440.015625501910.1093756680.0156252490009440.125251070.1256690.12524150009440.125311290.256690.15625253000627018530.04687533980.0468752590009350.07812528830.046875511650.17187525150006260.0625341010.0937515690.078125263000862730.28125963050.171875953040.156252690001033510.593751073380.453125943010.406252615000964021.03125983130.671875953040.64062527300024428091.62522940.03125291190.04687527900019522902.40625642560.203125100030043.25271500094637845.984375502110.29687521800.0781252830009460.03125441510.09375361260.0781252890009460.0625501780.15625361230.0937528150009460.078125371240.171875341250.203125293000318042504240.046875299000318042404240.04687529150003180.031254320.031254240.0312530300013513880.609375100030630.921875100030131.12530900059141994.0625100030661.9375100030132.32812530150001073940.421875100030832.609375100030133.359375313000321080.078125401250.0625441390.062531900031980.09375431360.109375451420.1253115000331040.1875441390.21875481510.2532300031940.078125331020.046875501530.07812532900027840.140625641950.328125411280.234375321500029900.265625451400.3125461430.3437533300041304120390339000260.0468752602603315000260260260.0156253430004120.03125411031603490004120.0156255140.0156257200.0312534150004120.0156256170.031259260.093753530003170.0156258230.0312514410.031253590003170.0312512350.0312521620.0937535150005140.0312515440.07812525740.140625363000883441.7520810.3593757380.203125369000351492.12517690.8757380.4531253615000943949331232.7968757380.8437537300038014130.734375100031111.32812523850.04687537900032111831.37534411551.109375100030133.6718753715000100036866.40625100030784.375100030054.90625383000943740.18759300.0156255190.03125389000215858122740.0468754140.03125381500029411732.12517570.0781254140.046875393000618018530.015625381130.0468753990006180.0312519560.03125411220.10937539150006180.062520590.09375431280.1875403000592340.40625100031166.0468753190.0468754090003180.06251000310916.031253170.04687540150003170.0781251000310225.7656253170.07812541300016960.062528980.0312516600.046875419000231390.12523780.062516600.06254115000342420.3437519660.07812516600.0781254230006470.01562542806420.031254290006470.0781254280.0468756420.0312542150007600.1254280.06256420.0625433000211880.29687519600.21875581860.4218754390002140.062520630.359375682161.234375431500024810.76562520630.59375722282.31254430002140.01562527840.203125662160.43754490002140.04687528870.5752411.32812544150002140.07812528870.78125772472.312545300013400.09375431320.28125752280.51562545900013400.328125451380.8125792401.484375451500013400.375461411.34375812462.28125463000866630.96875601940.40625241490.281254690002140.0468751535102.9062517810915.45312546150002140.0781251545194.703125200135510.2031254730007623013.8593757622913.51562520713.718754790005518892.2343753411153.96875114517.125471500082304397.687586276382.312592306416.42187548300012520.0937530970.14062523820.1093754890001196652.71875351150.4375371330.5481500017714858.859375331090.68751263832.54687549300051654222.796875100030930.890625100030131.093754990001535600.5100031711.9375100030132.390625491500048718002.109375100030722.890625100030133.45312550300019416098.406251000302514.7656251000301315.2031255090003203100431695608.4843751000301342.484375501500024188820.4843751000310771.3751000301370.25513000492180.2812516490.07812528850.1255190002140.0312515460.17187528850.2812551150002140.07812515460.23437528850.468755230001494740.4218751735480.468751825750.4531255290001705411.1406251926071.156252066491.2812552150001785652.0468752016362.031252156781.9843755330003260.0312544114870.4531253260.0468755390003270.01562543014441.03125561930.14062553150002140.03125100030783.468752140.01562554300038114030.76562521930.031253180.046875549000481850.203125983540.31253180.031255415000100039787652380.3906253180.01562555300019650.10937514430.0468753250.06255590003260.0937515460.171875231000.39062555150003260.14062515460.34375231040.755630003160100031250.984375100029991.06255690003160.046875100031512.078125100029992.187556150003160.015625100031253.359375100029993.718755730002140.015625712260.513713982.2031255790002140.046875672111.2343751026023.04687557150002140.078125692211.984375210154610.8437558300013400.093751093580.79687558419853.92187558900013400.218751193982.23437522880.453125581500013400.3906251494904.6562522880.68755930003180.015625481700.3437518920383.1406255990003180.09375461630.875239268310.32812559150003180.09375541871.71875256291217.81256030004437711103570.734375804660.8593756090002140.0468751846193.515625977433.45312560150002140.0781251846245.85937510410006.43756130002140.015625732360.51562517518912.8756190002140.046875782551.45312518811935.79687561150002140.109375692292.031251146494.968756230003180.015625862800.625271030.18756290003180.078125712401.281251267023.60937562150003180.078125471601.390625754153.2563300015460.1562513945511576271.187563900015460.2656252528184.734375723091.515625631500015460.4531252217426.953125873633.04687564300018550.140625732220.437524860.187564900018550.34375772341.32812524860.484375641500018550.578125792402.32812524860.8593756530003190.10937531940.515625331020.5781256590003190.51562530911.437531961.565150003190.687530912.48437531962.4843756630006300.2031254210.0781254190.0781256690006300.54210.2343754190.265625661500012047911.0156254210.4531254190.37567300010640.093757690.0312511720.0468756790007420.046875382580.79687511690.156256715000221360.890625241700.7187511670.23437568300024800.07812522670.03125444910.328125689000214023700.0468752140.0312568150002140.062523700.0781252140.031256930005330531630.10937528880.06256990005330.046875511570.2187520710.14062569150005330.046875511570.35937520710.171875703000662771.125431670.67187513700.20312570900010450.521901.0312515770.718757015000682454.968759340.5937525982.031257130003160421330.0468753160.0468757190003160.015625421330.0625316071150003160.015625421330.1253160.04687572300020676541.437516358331.45312515602.78125729000100036941734.984375100030361571.609375156024.1257215000100036114739.8125163568751.625156066.70312573300056261182.67187532010550.28125100030170.984375739000100090698.703125100030481.90625100030172.375731500079856886.53125100030412.71875100030173.078125Figure 1
Performance profiles of these methods (CPU).Figure 2
Performance profiles of these methods (NI).Figure 3
Performance profiles of these methods (NGF).From the detailed experimental data of Table2, it is obvious to see that most of the problems can be solved quickly. For most of the problems, it takes less CPU time to solve those problems with the proposed algorithm. Meanwhile, progress has also been made in NI and NFG. Generally, the algorithm of the proposed method is promising versus the other algorithms. About the numerical results, the algorithm of Dolan and More [22] will be used to more directly show the performance profiles of these algorithms. In Figure 1, the curve of Algorithm 1 is always above the other algorithms. In Figure 2, the curves have the same trend. Algorithm 1 almost solves about 97% of the test problems in τ=30, while Algorithm 2 just solves 89.9% and Algorithm 3 just solves 87% in τ=30. Figure 3 shows a similar trend as Figure 2. All the above pictures show that the modified CD conjugate gradient algorithm is more robust and effective compared with the normal CD method and PRP method. In summary, Algorithm 1 is more competitive versus others.


## 4.2. The Muskingum Model

It is generally known that parameter estimation is a significant task in engineering applications. The nonlinear Muskingum model will be discussed as a common example of such an application in this subsection.The Muskingum Model [23] is defined by the following:(27)minfx1,x2,x3=∑i=1n−11−Δt6x1x2Ii+1+1−x2Qi+1x3−1−Δt6x1x2Ii+1−x2Qix3−Δt2Ii−Qi+Δt21−Δt3Ii+1−Qi+12.Some of the variables have the following meanings:(i)
n: the total time number.(ii)
x1: the storage time constant.(iii)
Ii: the observed inflow discharge.(iv)
x2: the weighting factor.(v)
Qi: the observed outflow discharges.(vi)
x3: an additional parameter.(vii)
Δt: the time step at time tii=1,2,…,n.In the experiment, the observed data of the flood run-off process from Chenggouwan and Linqing of Nanyunhe River in the Haihe Basin, Tianjin, China, are used. We choose the initial pointx=0,1,1T; detailed data about Ii and Qi for the years 1960, 1961, and 1964 were obtained (see [24] in detail). Δt=12h was selected. The results of these three algorithms are listed in Table 3. The performance of the presented algorithm is shown in Figures 4–6.Table 3
Results of the three algorithms.
Algorithmsx1x2x3BFGS [25]10.81560.98261.0219HIWO [23]13.28130.80010.9933Algorithm111.18481.00000.9995Figure 4
Performance of date in 1960.Figure 5
Performance of date in 1961.Figure 6
Performance of date in 1961.Some conclusions are obtained from this experiment: (1) from Figures4–6, we conclude that we can calculate approximations of flood outflows by using Algorithm 1, and Algorithm 1 is effective for the nonlinear Muskingum model; (2) the final points (x1, x2 and x3) of these three algorithms are interesting, and they are competitive with the final points of similar algorithms; and (3) the final points of Algorithm 1 are different from those of the BFGS method and HIWO method, which implies that the nonlinear Muskingum model has different optimum approximation solutions.


## 4.3. Image Restoration Problems

In this subsection, the above algorithms will be applied to image restoration problems. The original images corrupted by impulse noise are treated as objects here. These problems are regarded as one of the most difficult problems in optimization fields. Related parameter settings are similar to the above subsections, and the program will be stopped when the conditionfk+1−fk/fk<10−3 or xk+1−xk/xk<10−3 holds. The following three images are selected as processing objects: Banoon (512×512), Barbara (512×512), and Lena (512×512). The detail performances are shown in Figures 7–9. The CPU time taken to process images is listed in Table 4.Figure 7
Restoration of the Banoon image, Barbara image, and Lena image by Algorithms1–3. From left to right: a noisy image with 30% salt-and-pepper noise, the restorations obtained with Algorithms 1–3.Figure 8
Restoration of the Banoon image, Barbara image, and Lena image by Algorithms1–3. From left to right: a noisy image with 50% salt-and-pepper noise, the restorations obtained with the Algorithms 1–3.Figure 9
Restoration of the Banoon image, Barbara image, and Lena image by Algorithms1–3. From left to right: a noisy image with 70% salt-and-pepper noise, the restorations obtained with the Algorithms 1–3.Table 4
CPU time of those algorithms in seconds.
30% noiseLenaBarbaraBanoonTotalAlgorithm14.4384.3904.65613.484Algorithm 24.5635.2345.40615.203Algorithm 35.1566.3136.78118.25050% noiseLenaBarbaraBanoonTotalAlgorithm18.6097.8918.14124.641Algorithm 29.21910.68810.54730.454Algorithm 311.29714.39114.85940.54770% noiseLenaBarbaraBanoonTotalAlgorithm115.75010.57811.98438.312Algorithm 213.89114.43814.70343.032Algorithm 314.85919.92220.37555.156It is easy to see that all the algorithms are successful for image restoration problems. The results in Table4 reveal that the CPU time of Algorithm 1 is less than that of other algorithms, whether for $30\%$ noise problems, 50% noise problems, or for 70% noise problems.


## 5. Conclusion

In this paper, a modified three-term type CD conjugate gradient algorithm is presented. Some good features are also presented: (i) sufficient descent property holds, (ii) trust region feature also holds, (iii) the algorithm has global convergence with the MWWP line search technique and projection technique for general function, and (iv) numerical results reveal that the new algorithm is more competitive than the normal CD algorithm and PRP algorithm.In recent years, there have been considerable researches about other types of CG method, while the study of CD method is not enough, and it should not be ignored. We have many works to do in the future: whether this method is suitable for other line search technique (such as Armijo line search, nonmonotone line search), or whether there exist other better modification methods to improve the numerical results of the CD method. All these are worth studying in the next work.



---

*Source: 4381515-2020-09-04.xml*