# Modified Three-Term Liu–Storey Conjugate Gradient Method for Solving Unconstrained Optimization Problems and Image Restoration Problems

Authors: Yulun Wu; Mengxiang Zhang; Yan Li
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

A new three-term conjugate gradient method is proposed in this article. The new method was able to solve unconstrained optimization problems, image restoration problems, and compressed sensing problems. The method is the convex combination of the steepest descent method and the classical LS method. Without any linear search, the new method has sufficient descent property and trust region property. Unlike previous methods, the information for the functionfx is assigned to dk. Next, we make some reasonable assumptions and establish the global convergence of this method under the condition of using the modified Armijo line search. The results of subsequent numerical experiments prove that the new algorithm is more competitive than other algorithms and has a good application prospect.


---

## Body

## 1. Introduction

Consider the following unconstrained optimization:(1)minfx|x∈ℜn,f:ℜn⟶ℜ.According to the research of other scholars, there are abounding effective forms to solve unconstrained optimization problems. For example, there are the steepest descent method, Newton method, and conjugate gradient method [1–8]. The nonlinear conjugate gradient method is a very effective method for solving large-scale unconstrained optimization problems. The conjugate gradient method has attracted more and more attention [9–14] because it is easy to calculate and has low memory requirement and application in many fields [15–18]. The conjugate gradient iteration formula of (1) is defined as(2)xk+1=xk+αkdk,k=0,1,2,…,where αk is the step size of the k th iteration obtained by a certain line search rule and dk is search direction of step k, which are two important factors for solving unconstrained optimization problems. Among them, dk is defined as(3)dk≔−gk,ifk=0,−gk+βkdk−1,ifk≥1,where the parameter βk called the CG parameter is a scalar and gk=gxk=▽fxk. The method of calculating the CG parameters will affect the performance and stability of the whole algorithm, so CG parameters play an utterly significant part. Among the nonlinear conjugate gradient method, we set yk=gk−gk−1 and let · represent the Euclidean norm. Then, the classical methods include the following:HS method [19] (the parameter βkHS=gkTyk/−dk−1Tyk)FR method [20] (the parameter βkFR=gk2/gk−12)PRP method [21, 22] (the parameter βkPRP=gkTyk/gk−12)LS method [23] (the parameter βkLS=gkTyk/−dk−1Tgk−1)CD method [24] (the parameter βkCD=gk2/−dk−1Tgk−1)DY method [25] the parameter (βkDY=gk2/−dk−1Tyk)This paper mainly studies the Liu–Storey method. At the earliest, Liu and Storey proposed a conjugate gradient method to solve the optimization problem in [9]. In this paper, they demonstrate the convergence of the method when using Wolfe line search. The experimental results show that the algorithm is feasible. Later, it was called the LS method. The LS method is the same as the PRP method with exact linear search. Therefore, the LS method and the PRP method have similar forms. As is known to all, the HS method and the PRP method are supposed be the most effective two methods in practical calculation, and a lot of results have been obtained. Consequently, we hope that the theories and analysis techniques to the PRP method can also be applied to the LS method. However, the LS method does not have the nature of automatic descent. In order to surmount the disadvantage, Li [26] proposed an improved Liu–Storey method using Crippo-Lucide search technology, where the direction of search dk is computed as(4)dk≔−gk,k=0,−gk+βkNLSdk−1+θkyk−sk,k≥1,where yk=gk−gk−1, sk=xk−xk−1 and(5)βkNLS=gkTyk−dk−1Tgk=yLk2gkTdk−1dk−1Tgk2,θk=gkTdk−1dk−1Tgk.Nevertheless, this method assumes a minimum step size, and the main reason is the lack of direction of the trust zone. Therefore, a number of scholars have considered the combination of conjugate gradient method and trust region property. The three-term conjugate gradient algorithm is easy to converge because it automatically has sufficient descent. Therefore, this kind of method has been concerned by many scholars. The conjugate gradient method with three terms was first proposed by Zhang et al. [27]; they defined dk as(6)dk≔−gk,k=0,−gk+gkTykdk−1−dk−1Tgkykgk−12,k≥1.Recently, a three-term conjugate gradient algorithm was proposed in Yuan’s paper [28]. The search direction dk of this algorithm is a based on LS method and the gradient descent method. On the basis of Yuan’s research, a modified three-term conjugate gradient method is proposed, which has more functional information than the original method, where dk is computed by(7)dk≔−gk,k=0,−θkgk+1−θkgkTyk∗dk−1−dk−1Tgkyk∗max2λdk−1yk∗,−dk−1Tgk−1,k≥1,where yk=gk−gk−1, sk=xk−xk−1, constant λ∈0,1, and(8)θk=yk2ykTsk∗,sk∗≔sk+max0,−skTykyk2yk+yk,yk∗=yk+νksk,νk=max0,gxk+1+gxkTsk+2fxk−fxk+1sk2.The vectoryk∗ not only has gradient information but also has functional information, with good theoretical results and numerical performance (see [29]). One might think that the resulting method is indeed better than the original one; that is why we use yk∗ instead of yk.According to the meaning ofyk∗ and sk∗, the following inequality is obtained:(9)ykTsk∗≥ykTsk−skTykyk2yk2+yk2=yk−12>0.Therefore,(10)θk≔yk2ykTsk∗∈0,1.In [28], Yuan et al. used modified Armijo linear search, which selects the largest αk as the step size in set αk|αk=αk¯ρ1l,l∈1,2,3,… such that(11)fxk+αkdk≤fxk+δαk2gkTdk,where αk¯ is the trial step length, which is often set to 1, and ρ1∈0,1,δ∈0,1 are given constants. As is known to all, Armijo line search technology is a basic and the cheapest method. It is used in various algorithms [30–32]. Basically, a number of other methods of line search can be regarded as a modification of Armijo line search. In an unpublished article by Yuan, a new modification of Armijo linear search was designed based on [16, 33], which is defined as(12)fxk+αkdk≤fk+γαkgkTdk+αkmin−γ1gkTdk,γαk2dk2,where γ∈0,1, γ1∈0,γ, and αk=maxρi|i=0,1,2,3,… satisfying (12). The modification of Armijo linear search is verified to be effective in improving the efficiency of the algorithm.The following is an introduction to the paper: In the second section, we propose an improvement algorithm and establish two important properties (sufficient descent property and trust region property) of the algorithm without using linear search. Then, some other properties of the algorithm are given, and the global convergence of the algorithm is proved under appropriate assumptions. The third section gives numerical experiments on normal unconstrained optimization problems, image restoration problems, and compressive sensing problems. In the last section, the conclusion of this paper is given.


## 2. Conjugate Gradient Algorithm and Convergence Analysis

This section will give a new modified Liu–Storey method combining (7) and (12), as shown below:Lemma 1.
dk is generated by formula (7); then, it clears that(13)gkTdk≤−gk2,(14)gk≤dk≤λ∗gk.Proof.
Whenk=0, it is obvious that g0Td0=−g02 and d0=g0.
Whenk>0, we have(15)gkTdk=gkT−θkgk+1−θkgkTyk∗dk−1−dk−1Tgkyk∗max2λdk−1yk∗,−dk−1Tgk−1=−θkgk2+1−θkgkTyk∗gkTdk−1−dk−1TgkgkTyk∗max2λdk−1yk∗,−dk−1Tgk−1=−θkgk2.
Using (10), we have gkTdk<−gk2, and then, (13) holds. Also,(16)max2λdk−1yk∗,−dk−1Tgk−1≥2λdk−1yk∗.
Then, we have(17)dk=−θkgk+1−θkgkTyk∗dk−1−dk−1Tgkyk∗max2λdk−1yk∗,−dk−1Tgk−1≤θkgk+1−θkgkyk∗dk−1+dk−1gkyk∗max2λdk−1yk∗,−dk−1Tgk−1≤θkgk+1−θkgkyk∗dk−1+dk−1gkyk∗2λdk−1yk∗≤θk+1−θkλgk.
Settingλ∗=θk+1−θk/λ, we get the right half of inequality (14). By Cauchy–Schwartz inequality and (13), we obviously get the left half of inequality (14). So, we get the results we want to prove.
Then, we will focus on the global convergence of the algorithm. In order to achieve this goal, we have to make the following assumptions.Assumption 1.
(a)
The level setL0=x|fx<fx0 is bounded(b)
Function:fx:ℜ⟶ℜ is continuously differentiable and the gradient gxk is Lipschitz continuous, and there exists a constant (Lipschitz constant) L>0 such that(18)gx−gy≤Lx−y,∀x,y∈ℜn.Theorem 1.
Assumption1 is kept true, and then, there is a positive constant α, which satisfies (12) in Algorithm 1.Algorithm1: Three-term modified Liu–Storey conjugate gradient (TTMLS) algorithm.
Input: input parameters ε∈0,1, γ∈0,1, γ1∈0,γ and ρ∈0,1.Output: xk,fk.(1)
For an initial solutionx0∈ℜn compute d0=−gx0; set k=0;(2)
whilegk>εdo(3)
Findαk=maxρi|i=0,1,2,3,… satisfying (12).(4)
Setxk+1=xk+αkdk.(5)
Computedk by (7).(6)
k≔k+1.(7)
EndProof.
We construct such a function(19)φα=fxk+αdk−fk−δαgkTdk−αmin−δ1gkTdk,δα2dk2.
From Assumption1, fxk+αdk and fk are bounded, note that 0<δ1<δ<1, and from (13), we have gkTdk≤0. Obviously, φ0=0 holds. Now, we discuss the following two scenarios:Case 1: ifmin−δ1gkTdk,δα/2dk2=−δ1gkTdk, then φα=fxk+αdk−fk−δαgkTdk+αδ1gkTdkFor all positiveα that are small enough, we can obtain the following inequalities:(20)φα=fxk+αdk−fk−δαgkTdk+αδ1gkTdk=α1−δ+δ1gkTdk+°α<0.Case 2: ifmin−δ1gkTdk,δα/2dk2=δα/2dk2, then φα=fxk+αdk−fk−δαgkTdk−δα2/2dk2
Same as Case 1, we have(21)φα=fxk+αdk−fk−δαgkTdk−δα22dk2=α1−δgkTdk−δα22dk2+°α<0.
So, from (20) and (21), there exists, at least, a positive constant ω such that φω<0, which also implies that there must be, at least, one local minimum point α∗∈0,ω such that(22)φα∗=fxk+α∗dk−fk−δα∗gkTdk−α∗min−δ1gkTdk,δα∗2dk2<0,that is,(23)fxk+α∗dk<fk+δα∗gkTdk+α∗min−δ1gkTdk,δα∗2dk2.
Thus,α∗ satisfies (12). The proof is completed. So, quite evidently, Algorithm 1 is well defined.Theorem 2.
Let Assumption1 be satisfied and the iterative sequence xk,αk,dk,gk be generated by Algorithm 1. After that, we obtain(24)limk⟶∞gk=0.Proof.
We will use the contradiction to draw this conclusion. When (24) is not correct, there exists a constant ε0>0 such that(25)gk≥ε0,∀k>0.
From the third step of the Algorithm (12), we have(26)fxk+αkdk−fk≤γαkgkTdk+αkmin−γ1gkTdk,γαk2dk2≤γ−γ1αkgkTdk,namely, (27)γ1−γα0g0Td0≤f0−f1,γ1−γα1g1Td1≤f1−f2,…γ1−γαkgkTdk≤fk−fk+1,…,and summing up the two sides of the abovementioned inequalities and from Assumption 1 (ii), it is obtained that(28)γ−γ1∑k=0∞αkgk2≤γ1−γ∑k=0∞αkgkTdk≤f0−f∞<+∞.
Thus, from (28), we have(29)αkgk2⟶0,k⟶∞.
Now, our certificates are divided into the following two cases:Case 1: the step sizeαk>0 as k⟶∞. From (29), it is obvious that gk⟶0 as k⟶∞. This contradicts (24).Case 2: the step sizeαk⟶0 as k⟶∞.
From Algorithm1, for the obtained step size αk, it is clear that αk/ρ does not satisfy (12), and by (13) and (14),(30)fxk+αkρdk−fxk>γαkρgkTdk+αkρmin−γ1gkTdk,γαk2ρdk2>−γαkρgk2+αkρminγ1gk2,γαk2ρdk2>γ0−γαkρgk2,where γ0=minγ1,γαk/2ρ; then, according to the mean value theorem, there exists an ζk∈0,1 such that(31)fxk+αkρdk−fxk=αkρgxk+ζkαkρdkTdk=αkρgxk+ζkαkρdkTdk−αkρgxkTdk+αkρgxkTdk≤αkρ2Lζkdk2+αkρgxkTdk≤Lαkρ2dk2−αkρgk2.
Combined with (30)–(32), we have(32)αk>ρ1+γ0−γgk2Ldk2≥ρ1+γ0−γLλ∗2.
So, we get the contradiction. Thus, result (24) is true, and this completes the proof.


## 3. Numerical Experiments

In this section, we have designed three experiments to study the computational efficiency and performance of the proposed algorithm. The first subsection is normal unconstrained optimization problems, the second subsection is the image restoration problem, and the third subsection is compressive sensing problems. All the programs are compiled with Matlab R2017a and implemented on an Intel(R) Core (TM) i7-4710MQ CPU @ 2.50 GHz, RAM 8.0 GB, and the Windows 10 operating system.


### 3.1. Normal Unconstrained Optimization Problems

In order to test the numerical performance of the TTMLS algorithm, the NLS algorithm [28], LS method with the normal WWP line search (LS-WWP), and PRP method with the normal WWP line search (PRP-WWP) are also experimented as the comparison group. The results can be seen in Tables 1–4. The data used in the experiment are as follows:Dimension: we choose 3000 dimensions, 6000 dimensions, and 9000 dimensions to test.Parameters: all the algorithms run withγ=0.6, γ1=0.3, ρ=0.9, γ=0.7, and ε=10−6.Stop rule (the Himmelblau stop rule [34]): if fxk>e1, let stop1=fxk−fxk+1/fxk; otherwise, let stop1=fxk−fxk+1. If conditions gx<ε or stop1<e2 are satisfied or the iteration number of more than 1000 is satisfied, we stop the process, where e1=e2=10−5.Symbol representation: NI: the iteration number. NFG: the total number of function and gradient evaluations. CPU: the CPU time in seconds.Text problems: we have tested 74 unconstrained optimization problems, and the list of problems can be seen in Yuan’s work [16].Table 1
Test results of the TTMLS algorithm.
NrDimTTMLS algorithmNINFGCPU130005260.203125160005260.109375190005260.23437523000854023.64062526000904266.17187529000914349.125330006320.0625360006320.0625390006320.046875430005260.0625460005260.15625490005260.171875530005260.015625560005260.046875590005260.0625630004200.0625660004200.0625690004200.062573000783420.14062576000803530.23437579000803540.3281258300010400.031258600010400.06258900010400.0625930006200960006200.06259900062001030003140.06251060003140.06251090003140.0625113000100029992.359375116000100029994.625119000100029996.8593751230003140.06251260003140.06251290003140.062513300041701360004170.06251390004200.1093751430007380.251460007380.3751490007380.468751530007380.18751560007380.2656251590007380.39062516300042001660004200.0468751690004200.06251730005260.1251760005260.1406251790005260.25183000100030730.8125186000100030731.421875189000100030731.98437519300010290.062519600010290.062519900010290.1252030007380.06252060007380.06252090007380.1093752130006320.18752160006320.2656252190006320.343752230009500.156252260009500.252290009500.3906252330006320.1252360006320.1252390006320.1718752430002327140.43752460002437470.8906252490002497651.2968752530006320.06252560006320.06252590006320.0625263000414026600041402690004140.0625273000793460.125276000803530.234375279000813580.28125283000526028600052602890005260.0468752930007380.0156252960007380.06252990007380.0625303000763330.0625306000783420.171875309000783440.2031253130005260.0312531600052603190005260.06253230005260.1253260005260.18753290005260.1875333000632033600063203390006320.06253430005260.06253460005260.06253490005260.0468753530006280356000628035900062803630005260.0781253660005260.1253690005260.21875373000823660.078125376000843780.140625379000853820.34375383000526038600052603890005260.06253930005260.06253960005260.06253990005260.06254030005260.1254060005260.156254090005260.25413000733120.0625416000733120.140625419000733120.265625423000372040.1875426000301700.296875429000432380.593754330005260.1406254360005260.254390005260.3593754430005260.18754460005260.254490005260.2656254530005260.1406254560005260.218754590005260.2656254630005260.1254660005260.254690005260.28125473000823683.93754760008538611.296884790008739623.984384830006320.18754860006320.1718754890006320.3125493000783420.0625496000803530.1875499000803540.296875503000783420.9375506000803531.8125509000803542.2343755130007380.1255160007380.281255190007380.3755230004200.06255260004200.1255290004200.0625533000100030320.875536000100030321.609375539000100030332.4375543000526054600052605490005260.04687555300024740.10937555600026800.37555900026800.5563000100030100.90625566000100030101.6875569000100030102.468755730005260.1255760005260.218755790005260.2656255830005260.1255860005260.218755890005260.255930005260.1255960005260.2343755990005260.281256030005260.1256060005260.256090005260.281256130005260.18756160005260.256190005260.31256230005260.18756260005260.256290005260.3593756330005260.18756360005260.256390005260.31256430005260.1406256460005260.256490005260.281256530006320.2031256560006320.31256590006320.281256630006320.0781256660006320.18756690006320.2567300012610.062567600014740.0937567900013690.187568300011620.062568600011620.062568900011620.06256930006320.031256960006320.06256990006320.06257030006320.18757060006320.257090006320.34375713000100030101.015625716000100030101.8125719000100030102.59375723000823684.18757260008638911.515637290008739623.92188733000763330.09375736000783420.15625739000783440.234375743000763330.0625746000783420.125749000783440.21875Table 2
Test results of the NLS algorithm.
NrDimNLS algorithmNINFGCPU130005260.125160005260.140625190005260.2187523000924284.078125260001024727.1562529000974577.84375330006320.0625360006320390006320430005260.0625460005260.109375490005260.109375530005260.0625560005260.0625590005260.0625630004200660004200.0625690004200.062573000833610.12576000853700.2579000863770.3437583000100030462.0781258600010400.06258900010400.0625930006200.0625960006200990006200.0625103000314010600031401090003140.0625113000100029992.8125116000100029995.296875119000100029997.812512300031401260003140.03125129000314013300041701360004170.06251390004200.06251430007380.2031251460007380.3751490007380.4531251530007380.18751560007380.31251590007380.34375163000420016600042001690004200.06251730005260.1251760005260.1406251790005260.234375183000100030750.75186000100030751.234375189000100030752.0468751930001029019600010290.062519900010290.18752030007380.06252060007380.06252090007380.06252130006320.1252160006320.2656252190006320.3752230009500.18752260009500.252290009500.281252330006320.06252360006320.1252390006320.12524300050515351.10937524600052916072.312524900054216463.5156252530006320.062525600063202590006320.04687526300041402660004140.06252690004140273000843650.125276000853700.3125279000853720.3593752830005260.062528600052602890005260.03125293000738029600073802990007380.0625303000833570.0625306000833610.1875309000843660.218753130005260.0625316000526031900052603230005260.1253260005260.1253290005260.1253330006320.062533600063203390006320.06253430005260.062534600052603490005260353000733035600073303590007330.06253630005260.1253660005260.1253690005260.1875373000873840.125376000903980.25379000893960.3906253830005260.062538600052603890005260.06253930005260.062539600052603990005260.0468754030005260.1254060005260.1406254090005260.25413000793340.125416000793340.171875419000793340.25423000462350.25426000392040.4375429000552720.718754330005260.1254360005260.254390005260.31254430005260.1254460005260.156254490005260.281254530005260.1093754560005260.2031254590005260.31254630005260.0781254660005260.218754690005260.375473000883906.0781254760009140619.843754790009241541.734384830006320.1254860006320.18754890006320.234375493000833610.125496000853700.171875499000863770.1875503000833611.125506000853702.0625509000863772.4531255130007380.18755160007380.255190007380.2968755230004200.06255260004200.06255290004200.015625533000100030151.03125536000100030161.8125539000100030162.85937554300052605460005260.0625549000526055300024740.187555600026800.42187555900026800.51562556300078823740.87556600078823741.5937556900078823742.2343755730005260.1255760005260.2031255790005260.281255830005260.1255860005260.218755890005260.343755930005260.1255960005260.255990005260.2343756030005260.1256060005260.2343756090005260.343756130005260.1093756160005260.2031256190005260.281256230005260.1256260005260.256290005260.3593756330005260.1256360005260.256390005260.2656256430005260.18756460005260.256490005260.256530006320.18756560006320.281256590006320.3281256630006320.1256660006320.18756690006320.23437567300022990.12567600014650.12567900021950.23437568300011620.062568600011620.062568900011620.062569300063206960006320.06256990006320.06257030006320.1257060006320.2031257090006320.37571300078823740.812571600078823741.4687571900078823742.265625723000883905.9843757260009140619.343757290009241542.32813733000833570.125736000833610.09375739000843660.203125743000833570.0625746000833610.15625749000843660.203125Table 3
Test results of the LS-WWP algorithm.
NrDimLS-WWPNINFGCPU130001000599820.5625160001000598639.26563190001000598652.9687523000632280.37526000662310.76562529000612231.0468753300032510760.312536000100052061.82812539000100056852.65625430001000593411.5460001000583522.32813490001000584131.6875530001328190.4375560001338260.765625590001348321.20312563000481980.12566000512070.12569000432020.187573000100059941.718757600010005994379000100059944.37583000331360.12586000331360.12589000321300.140625930004190.0625960004190990004190.0625103000290106000290109000290.0625113000100030012.671875116000100030015.046875119000100030017.828125123000181050.125126000191110.25129000191110.359375133000313013600013660.18751390002901430006330.18751460005270.2656251490005270.2812515300010003010191560001000301029.406251590001000301035.8437516300022720.062516600015840.12516900015810.15625173000744321.625176000744322.96875179000744324.0468751830007420.062518600084801890008480.062519300041801960004180.06251990004180.093752030001474020600014740.04687520900014740.0625213000451500.0625216000211110.125219000201110.1718752230001258022600012580.12522900012580.093752330001000595911.546882360001000595922.43752390001000595931.98438243000593130.1875246000622740.31252490007460.062525300033980.0625256000441310.0625259000100030731.921875263000511940.125266000501880.25269000501880.375273000100030131.15625276000100030132.1875279000100030133.140625283000925030.0625286000925030.1875289000925030.1875293000315029600031502990003150303000100059941.28125306000100059942.453125309000100059943.3281253130001051031600012640.062531900012640.062532300010520.0625326000100059355.92187532900010540.0625333000390.0625336000390339000260343000315034600072003490008230.06253530001544035600019560.04687535900021620.06253630001000598817.953133660001000599732.171883690001000599143.54688373000100059912.0625376000100059883.84375379000100059885.421875383000631038600063103890006310393000421250396000441310.125399000461370.093754030001000598225.265634060001000589841.265634090001000586755.25413000100030030.96875416000100030031.640625419000100030032.42187542300062604260006260.06254290007320.06254330008460.254360008460.43754390008460.562544300012680.32812544600011620.4687544900011620.68754530009500.254560009500.3754590009500.5625463000563336716.0625466000708423733.29688469000812486451.1562547300014443511.5937547600029388272.656254790004461341230.6875483000512940.8125486000502881.5489000502882.078125493000100059941.296875496000100059942.328125499000100059943.3593755030001000599417.140635060001000599431.343755090001000599441.5468851300014500.187551600013470.37551900013470.40625523000392080.25526000422240.5529000432270.71875533000100030030.9375536000100030031.609375539000100030032.453125543000100059551.4375546000100059582.59375549000100059553.968755530006320.06255560006320.18755590006320.1875563000100029991.0625566000100029992.0625569000100029992.755730009500.255760009500.3755790009500.578125583000533141.546875586000452662.1875589000412422.7343755930008440.255960008440.3281255990008440.5603000563336716.15625606000710425233.781256090001000301343.109386130009500.256160009500.3906256190009500.531256230006320.1406256260006320.31256290006320.2968756330006320.1256360006320.2656256390005260.2656256430008440.18756460008440.3281256490008440.562565300010460.187565600010460.343756590009430.4531256630001000598916.515636660001000598929.703136690001000598940.28125673000271080.062567600018780.109375679000211120.9375683000451360686000471420.0625689000481450.0625693000361140.046875696000371170.046875699000371170.06257030001000370114.156257060001000312523.609387090001000318831.20313713000100059961.375716000100059962.546875719000100059963.71875723000100030108272600010003010246.328172900010003010519.7656733000100059941.3125736000100059942.46875739000100059943.375743000100059971.25746000100059972.390625749000100059943.21875Table 4
Test results of the PRP-WWP algorithm.
NrDimPRP-WWPNINFGCPU1300011670.31251600022890.6251900021860.7812523000702420.437526000802630.9062529000762551.2187533000331090360007360390006360430007420.1254600010560.254900012710.406255300019880.06255600019880.1093755900019880.1562563000702550.10937566000742740.17187569000853040.29687573000100030441.062576000100030442.0937579000100030442.81258300023970.06258600023970.1258900023970.1562593000525096000525099000525010300029010600029010900029011300066920241.76562511600021860.125119000100030187.54687512300019700.12512600019700.17187512900019700.203125133000313013600010540.1875139000290.06251430006330.1718751460005270.251490005270.359375153000311380.75156000552332.046875159000391771.906251630001042016600021660.12516900022690.1875173000401360.5625176000411391.171875179000441641.7187518300031601860003160189000316019300042101960004210.06251990004210.109375203000331070206000341100.046875209000351130.12521300026950.04687521600019830.12521900019830.1562522300013670.062522600013670.062522900013670.140625233000100030178.9531252360001000302317.3437523900029012088.171875243000652220.125246000832760.34375249000923030.57812525300033980256000431280.0625259000541820.125263000501840.125266000521900.25269000531930.328125273000301570.046875276000352040.109375279000462680.1875283000241080.0625286000241080289000241080.0625293000419029600041902990004220303000100031130.75306000100031161.125309000100031411.9843753130002081031600020810.062531900020810.12532300026880.0625326000441420.1875329000611930.359375333000390336000390339000260.046875343000315034600072003490007200.03125353000144103560001853035900021620.0312536300019880.3125366000271260.7536900017990.75373000100030151.3125376000100032062.53125379000100030983.609375383000740038600052803890005280.0625393000381130.0625396000401190.0625399000411220.1093754030001000313422.754060001000328236.3754090001000314442.73438413000197304160001973041900019730.062542300011430.062542600011460.062542900011460.06254330007400.2031254360008460.43754390008460.4687544300012680.312544600011620.45312544900011620.718754530009500.254560009500.468754590009500.5468754630002608356.0625466000529161318.75469000611185926.6875473000461613.593754760005718113.546884790008434740.0625483000531650.5625486000461440.875489000401260.953125493000100031130.75496000100031161.328125499000100031401.968755030001000324511.328135060001000308619.515635090001000305424.781255130007370.1255160007400.255190007400.4375523000933550.53125526000993731.1718755290001074011.875533000100030220.875536000100030221.671875539000100030222.34375543000472160.0625546000321650.0625549000562720.2031255530005250.06255560005250.1255590005250.1875563000100030120.984375566000100030121.671875569000100030122.56255730009500.18755760009500.3906255790009500.609375583000533141.5625586000452662.234375589000412422.656255930008440.18755960008440.406255990008440.468756030001034382.71875606000330104812.0312560900026591612.734386130009500.256160009500.343756190009500.593756230006320.18756260006320.2031256290006320.3756330006320.1406256360006320.31256390005260.2656256430008440.2031256460008440.43756490008440.45312565300012460.2565600010400.26562565900010400.43756630007270.06256660007270.1256690007270.171875673000241250.5625676000251311.12567900017730.09375683000431300.0625686000451360.046875689000461390.09375693000381250696000391280.046875699000401310.1257030006310.0625706000241100.757090006310.234375713000100030090.875716000100030091.703125719000100030092.3593757230001000310580.312572600010004018228.062572900010003182513.3125733000100030190.875736000100030191.5739000100030192.09375743000100030390.9375746000100030571.359375749000100031732.03125Table 5
CPU times of the TTMLS algorithm and NLS algorithm in seconds.
30% noiseLenaBarbaraManBaboonTotalTTMLS algorithm18.81324.094100.81322.922166.642NLS algorithm19.54726.703108.28125.391179.92245% noiseTTMLS algorithm38.34439.125205.12535.406318.000NLS algorithm42.42141.688218.34439.422341.87560% noiseTTMLS algorithm91.06384.203417.04779.656671.969NLS algorithm97.93888.984438.15687.547712.625Dolan and Moré [35] provided a way to analyze the efficiency of these algorithms. From Figures 1–3, we can see that the 3performance of the TTMLS algorithm, TTMLS algorithm, and NLS algorithm is significantly better than that of the LS-WWP method and PRP-WWP method. Figures 1 and 2 show that the TTMLS algorithm and NLS algorithm can better approximate to the target function than the LS-WWP algorithm and PRP-WWP algorithm; thus, the number of iterations and the total number of function and gradient evaluation are smaller. The reason is that the search direction dk of the TTMLS algorithm contains more function information. Also, the CPU time in Figure 4, TTMLS algorithm is basically the same as the NLS algorithm, which is better than the other two. To sum up, the proposed algorithm has significant advantages.Figure 1
An overview of the performance of these four algorithms (NI).Figure 2
An overview of the performance of these four algorithms (NFG).Figure 3
An overview of the performance of these four algorithms (CPU).Figure 4
From left to right: the images disturbed by 30% salt-and-pepper noise, the images restored by the TTMLS algorithm, and the images restored by the NLS algorithm.


### 3.2. Image Restoration Problems

The image restoration problem is a difficult problem in the field of optimization. We will use the TTMLS algorithm and NLS algorithm to minimizeZ to recover the original image from an image corrupted by impulse noise. Afterwards, we compare the performance of the two algorithms. The data used in the experiment are as follows:Parameters: all the algorithms run withγ=0.6, γ1=0.3, ρ=0.9, and γ=0.7.Stop rule: ifgk+1−gk/gk<10−4 or xk+1−xk/xk<10−4 is satisfied, we stop the process.Symbol representation: CPU: the CPU time in seconds. Total: the total CPU time of the four pictures.The information of noise:30%, 45%, and 60% salt-and-pepper noise.Text problems: we restore the original image from the image destroyed by impulsive noise. The experiments chose Lena512×512, Barbara 512×512, Man 1024×1024, and Baboon 512×512 as the test images.From Figures4–6, we can Table 5 see that both algorithms can recover 30%, 45%, and 60% salt-and-pepper noise images very well. The data show that, for image restoration problems, the TTMLS algorithm has shorter CPU time than the NLS algorithm when the salt-and-pepper noise is 30%, 45%, and 60%. In conclusion, the TTMLS algorithm is promising and competitive.Figure 5
From left to right: the images disturbed by 45% salt-and-pepper noise, the images restored by the TTMLS algorithm, and the images restored by the NLS algorithm.Figure 6
From left to right: the images disturbed by 60% salt-and-pepper noise, the images restored by the TTMLS algorithm, and the images restored by the NLS algorithm.


### 3.3. Compressive Sensing Problems

The main work of this section is to accurately recover the image from a few of random projections by compressive sensing. The experimental method derives from the model proposed by Dai and Sha [36]. Then, the performance of the TTMLS algorithm and LS method with line search (12) is compared.It is noted that the gradientsgk and dk are square matrices in this experiment, and the matrix obtained by gkTdk may appear as a singular matrix, which results in the invalidation of the algorithm. But, when we calculate dk+1, we only need the value of gkTdk without knowing the information of this square matrix, so in this experiment, we set gkTdk=gkTdk∞ in dk+1. The data used in the experiment are as follows:Parameters: all the algorithms run withγ=0.6, γ1=0.3, ρ=0.9, and γ=0.7.Stop rule: ifgkTdk∞<10−3 or the number of iterations exceeds 500 is satisfied, we stop the process.Symbol representation: PSNR: Peak Signal-to-Noise Ratio. It is an objective criterion for image evaluation.Text problems: compressive sensing problems. The experiments chose Camera man256×256, Fruits 256×256, Lena 256×256, and Baboon 256×256 as the test images.From Figure7 and Table 6, we can see that both algorithms are effective in compression sensing problems. Meanwhile, from the experimental data, we can see that the TTMLS algorithm has more advantages than the LS algorithm.Figure 7
From left to right: the original images, the images restored by the TTMLS algorithm, and the images restored by the LS algorithm.Table 6
Peak signal-to-noise ratio (PSNR) of the TTMLS algorithm and LS algorithm.
AlgorithmCamera manFruitsLenaPeppersTotalTTMLS31.92933.05331.99633.075130.053LS30.79231.48631.48931.925125.692


## 3.1. Normal Unconstrained Optimization Problems

In order to test the numerical performance of the TTMLS algorithm, the NLS algorithm [28], LS method with the normal WWP line search (LS-WWP), and PRP method with the normal WWP line search (PRP-WWP) are also experimented as the comparison group. The results can be seen in Tables 1–4. The data used in the experiment are as follows:Dimension: we choose 3000 dimensions, 6000 dimensions, and 9000 dimensions to test.Parameters: all the algorithms run withγ=0.6, γ1=0.3, ρ=0.9, γ=0.7, and ε=10−6.Stop rule (the Himmelblau stop rule [34]): if fxk>e1, let stop1=fxk−fxk+1/fxk; otherwise, let stop1=fxk−fxk+1. If conditions gx<ε or stop1<e2 are satisfied or the iteration number of more than 1000 is satisfied, we stop the process, where e1=e2=10−5.Symbol representation: NI: the iteration number. NFG: the total number of function and gradient evaluations. CPU: the CPU time in seconds.Text problems: we have tested 74 unconstrained optimization problems, and the list of problems can be seen in Yuan’s work [16].Table 1
Test results of the TTMLS algorithm.
NrDimTTMLS algorithmNINFGCPU130005260.203125160005260.109375190005260.23437523000854023.64062526000904266.17187529000914349.125330006320.0625360006320.0625390006320.046875430005260.0625460005260.15625490005260.171875530005260.015625560005260.046875590005260.0625630004200.0625660004200.0625690004200.062573000783420.14062576000803530.23437579000803540.3281258300010400.031258600010400.06258900010400.0625930006200960006200.06259900062001030003140.06251060003140.06251090003140.0625113000100029992.359375116000100029994.625119000100029996.8593751230003140.06251260003140.06251290003140.062513300041701360004170.06251390004200.1093751430007380.251460007380.3751490007380.468751530007380.18751560007380.2656251590007380.39062516300042001660004200.0468751690004200.06251730005260.1251760005260.1406251790005260.25183000100030730.8125186000100030731.421875189000100030731.98437519300010290.062519600010290.062519900010290.1252030007380.06252060007380.06252090007380.1093752130006320.18752160006320.2656252190006320.343752230009500.156252260009500.252290009500.3906252330006320.1252360006320.1252390006320.1718752430002327140.43752460002437470.8906252490002497651.2968752530006320.06252560006320.06252590006320.0625263000414026600041402690004140.0625273000793460.125276000803530.234375279000813580.28125283000526028600052602890005260.0468752930007380.0156252960007380.06252990007380.0625303000763330.0625306000783420.171875309000783440.2031253130005260.0312531600052603190005260.06253230005260.1253260005260.18753290005260.1875333000632033600063203390006320.06253430005260.06253460005260.06253490005260.0468753530006280356000628035900062803630005260.0781253660005260.1253690005260.21875373000823660.078125376000843780.140625379000853820.34375383000526038600052603890005260.06253930005260.06253960005260.06253990005260.06254030005260.1254060005260.156254090005260.25413000733120.0625416000733120.140625419000733120.265625423000372040.1875426000301700.296875429000432380.593754330005260.1406254360005260.254390005260.3593754430005260.18754460005260.254490005260.2656254530005260.1406254560005260.218754590005260.2656254630005260.1254660005260.254690005260.28125473000823683.93754760008538611.296884790008739623.984384830006320.18754860006320.1718754890006320.3125493000783420.0625496000803530.1875499000803540.296875503000783420.9375506000803531.8125509000803542.2343755130007380.1255160007380.281255190007380.3755230004200.06255260004200.1255290004200.0625533000100030320.875536000100030321.609375539000100030332.4375543000526054600052605490005260.04687555300024740.10937555600026800.37555900026800.5563000100030100.90625566000100030101.6875569000100030102.468755730005260.1255760005260.218755790005260.2656255830005260.1255860005260.218755890005260.255930005260.1255960005260.2343755990005260.281256030005260.1256060005260.256090005260.281256130005260.18756160005260.256190005260.31256230005260.18756260005260.256290005260.3593756330005260.18756360005260.256390005260.31256430005260.1406256460005260.256490005260.281256530006320.2031256560006320.31256590006320.281256630006320.0781256660006320.18756690006320.2567300012610.062567600014740.0937567900013690.187568300011620.062568600011620.062568900011620.06256930006320.031256960006320.06256990006320.06257030006320.18757060006320.257090006320.34375713000100030101.015625716000100030101.8125719000100030102.59375723000823684.18757260008638911.515637290008739623.92188733000763330.09375736000783420.15625739000783440.234375743000763330.0625746000783420.125749000783440.21875Table 2
Test results of the NLS algorithm.
NrDimNLS algorithmNINFGCPU130005260.125160005260.140625190005260.2187523000924284.078125260001024727.1562529000974577.84375330006320.0625360006320390006320430005260.0625460005260.109375490005260.109375530005260.0625560005260.0625590005260.0625630004200660004200.0625690004200.062573000833610.12576000853700.2579000863770.3437583000100030462.0781258600010400.06258900010400.0625930006200.0625960006200990006200.0625103000314010600031401090003140.0625113000100029992.8125116000100029995.296875119000100029997.812512300031401260003140.03125129000314013300041701360004170.06251390004200.06251430007380.2031251460007380.3751490007380.4531251530007380.18751560007380.31251590007380.34375163000420016600042001690004200.06251730005260.1251760005260.1406251790005260.234375183000100030750.75186000100030751.234375189000100030752.0468751930001029019600010290.062519900010290.18752030007380.06252060007380.06252090007380.06252130006320.1252160006320.2656252190006320.3752230009500.18752260009500.252290009500.281252330006320.06252360006320.1252390006320.12524300050515351.10937524600052916072.312524900054216463.5156252530006320.062525600063202590006320.04687526300041402660004140.06252690004140273000843650.125276000853700.3125279000853720.3593752830005260.062528600052602890005260.03125293000738029600073802990007380.0625303000833570.0625306000833610.1875309000843660.218753130005260.0625316000526031900052603230005260.1253260005260.1253290005260.1253330006320.062533600063203390006320.06253430005260.062534600052603490005260353000733035600073303590007330.06253630005260.1253660005260.1253690005260.1875373000873840.125376000903980.25379000893960.3906253830005260.062538600052603890005260.06253930005260.062539600052603990005260.0468754030005260.1254060005260.1406254090005260.25413000793340.125416000793340.171875419000793340.25423000462350.25426000392040.4375429000552720.718754330005260.1254360005260.254390005260.31254430005260.1254460005260.156254490005260.281254530005260.1093754560005260.2031254590005260.31254630005260.0781254660005260.218754690005260.375473000883906.0781254760009140619.843754790009241541.734384830006320.1254860006320.18754890006320.234375493000833610.125496000853700.171875499000863770.1875503000833611.125506000853702.0625509000863772.4531255130007380.18755160007380.255190007380.2968755230004200.06255260004200.06255290004200.015625533000100030151.03125536000100030161.8125539000100030162.85937554300052605460005260.0625549000526055300024740.187555600026800.42187555900026800.51562556300078823740.87556600078823741.5937556900078823742.2343755730005260.1255760005260.2031255790005260.281255830005260.1255860005260.218755890005260.343755930005260.1255960005260.255990005260.2343756030005260.1256060005260.2343756090005260.343756130005260.1093756160005260.2031256190005260.281256230005260.1256260005260.256290005260.3593756330005260.1256360005260.256390005260.2656256430005260.18756460005260.256490005260.256530006320.18756560006320.281256590006320.3281256630006320.1256660006320.18756690006320.23437567300022990.12567600014650.12567900021950.23437568300011620.062568600011620.062568900011620.062569300063206960006320.06256990006320.06257030006320.1257060006320.2031257090006320.37571300078823740.812571600078823741.4687571900078823742.265625723000883905.9843757260009140619.343757290009241542.32813733000833570.125736000833610.09375739000843660.203125743000833570.0625746000833610.15625749000843660.203125Table 3
Test results of the LS-WWP algorithm.
NrDimLS-WWPNINFGCPU130001000599820.5625160001000598639.26563190001000598652.9687523000632280.37526000662310.76562529000612231.0468753300032510760.312536000100052061.82812539000100056852.65625430001000593411.5460001000583522.32813490001000584131.6875530001328190.4375560001338260.765625590001348321.20312563000481980.12566000512070.12569000432020.187573000100059941.718757600010005994379000100059944.37583000331360.12586000331360.12589000321300.140625930004190.0625960004190990004190.0625103000290106000290109000290.0625113000100030012.671875116000100030015.046875119000100030017.828125123000181050.125126000191110.25129000191110.359375133000313013600013660.18751390002901430006330.18751460005270.2656251490005270.2812515300010003010191560001000301029.406251590001000301035.8437516300022720.062516600015840.12516900015810.15625173000744321.625176000744322.96875179000744324.0468751830007420.062518600084801890008480.062519300041801960004180.06251990004180.093752030001474020600014740.04687520900014740.0625213000451500.0625216000211110.125219000201110.1718752230001258022600012580.12522900012580.093752330001000595911.546882360001000595922.43752390001000595931.98438243000593130.1875246000622740.31252490007460.062525300033980.0625256000441310.0625259000100030731.921875263000511940.125266000501880.25269000501880.375273000100030131.15625276000100030132.1875279000100030133.140625283000925030.0625286000925030.1875289000925030.1875293000315029600031502990003150303000100059941.28125306000100059942.453125309000100059943.3281253130001051031600012640.062531900012640.062532300010520.0625326000100059355.92187532900010540.0625333000390.0625336000390339000260343000315034600072003490008230.06253530001544035600019560.04687535900021620.06253630001000598817.953133660001000599732.171883690001000599143.54688373000100059912.0625376000100059883.84375379000100059885.421875383000631038600063103890006310393000421250396000441310.125399000461370.093754030001000598225.265634060001000589841.265634090001000586755.25413000100030030.96875416000100030031.640625419000100030032.42187542300062604260006260.06254290007320.06254330008460.254360008460.43754390008460.562544300012680.32812544600011620.4687544900011620.68754530009500.254560009500.3754590009500.5625463000563336716.0625466000708423733.29688469000812486451.1562547300014443511.5937547600029388272.656254790004461341230.6875483000512940.8125486000502881.5489000502882.078125493000100059941.296875496000100059942.328125499000100059943.3593755030001000599417.140635060001000599431.343755090001000599441.5468851300014500.187551600013470.37551900013470.40625523000392080.25526000422240.5529000432270.71875533000100030030.9375536000100030031.609375539000100030032.453125543000100059551.4375546000100059582.59375549000100059553.968755530006320.06255560006320.18755590006320.1875563000100029991.0625566000100029992.0625569000100029992.755730009500.255760009500.3755790009500.578125583000533141.546875586000452662.1875589000412422.7343755930008440.255960008440.3281255990008440.5603000563336716.15625606000710425233.781256090001000301343.109386130009500.256160009500.3906256190009500.531256230006320.1406256260006320.31256290006320.2968756330006320.1256360006320.2656256390005260.2656256430008440.18756460008440.3281256490008440.562565300010460.187565600010460.343756590009430.4531256630001000598916.515636660001000598929.703136690001000598940.28125673000271080.062567600018780.109375679000211120.9375683000451360686000471420.0625689000481450.0625693000361140.046875696000371170.046875699000371170.06257030001000370114.156257060001000312523.609387090001000318831.20313713000100059961.375716000100059962.546875719000100059963.71875723000100030108272600010003010246.328172900010003010519.7656733000100059941.3125736000100059942.46875739000100059943.375743000100059971.25746000100059972.390625749000100059943.21875Table 4
Test results of the PRP-WWP algorithm.
NrDimPRP-WWPNINFGCPU1300011670.31251600022890.6251900021860.7812523000702420.437526000802630.9062529000762551.2187533000331090360007360390006360430007420.1254600010560.254900012710.406255300019880.06255600019880.1093755900019880.1562563000702550.10937566000742740.17187569000853040.29687573000100030441.062576000100030442.0937579000100030442.81258300023970.06258600023970.1258900023970.1562593000525096000525099000525010300029010600029010900029011300066920241.76562511600021860.125119000100030187.54687512300019700.12512600019700.17187512900019700.203125133000313013600010540.1875139000290.06251430006330.1718751460005270.251490005270.359375153000311380.75156000552332.046875159000391771.906251630001042016600021660.12516900022690.1875173000401360.5625176000411391.171875179000441641.7187518300031601860003160189000316019300042101960004210.06251990004210.109375203000331070206000341100.046875209000351130.12521300026950.04687521600019830.12521900019830.1562522300013670.062522600013670.062522900013670.140625233000100030178.9531252360001000302317.3437523900029012088.171875243000652220.125246000832760.34375249000923030.57812525300033980256000431280.0625259000541820.125263000501840.125266000521900.25269000531930.328125273000301570.046875276000352040.109375279000462680.1875283000241080.0625286000241080289000241080.0625293000419029600041902990004220303000100031130.75306000100031161.125309000100031411.9843753130002081031600020810.062531900020810.12532300026880.0625326000441420.1875329000611930.359375333000390336000390339000260.046875343000315034600072003490007200.03125353000144103560001853035900021620.0312536300019880.3125366000271260.7536900017990.75373000100030151.3125376000100032062.53125379000100030983.609375383000740038600052803890005280.0625393000381130.0625396000401190.0625399000411220.1093754030001000313422.754060001000328236.3754090001000314442.73438413000197304160001973041900019730.062542300011430.062542600011460.062542900011460.06254330007400.2031254360008460.43754390008460.4687544300012680.312544600011620.45312544900011620.718754530009500.254560009500.468754590009500.5468754630002608356.0625466000529161318.75469000611185926.6875473000461613.593754760005718113.546884790008434740.0625483000531650.5625486000461440.875489000401260.953125493000100031130.75496000100031161.328125499000100031401.968755030001000324511.328135060001000308619.515635090001000305424.781255130007370.1255160007400.255190007400.4375523000933550.53125526000993731.1718755290001074011.875533000100030220.875536000100030221.671875539000100030222.34375543000472160.0625546000321650.0625549000562720.2031255530005250.06255560005250.1255590005250.1875563000100030120.984375566000100030121.671875569000100030122.56255730009500.18755760009500.3906255790009500.609375583000533141.5625586000452662.234375589000412422.656255930008440.18755960008440.406255990008440.468756030001034382.71875606000330104812.0312560900026591612.734386130009500.256160009500.343756190009500.593756230006320.18756260006320.2031256290006320.3756330006320.1406256360006320.31256390005260.2656256430008440.2031256460008440.43756490008440.45312565300012460.2565600010400.26562565900010400.43756630007270.06256660007270.1256690007270.171875673000241250.5625676000251311.12567900017730.09375683000431300.0625686000451360.046875689000461390.09375693000381250696000391280.046875699000401310.1257030006310.0625706000241100.757090006310.234375713000100030090.875716000100030091.703125719000100030092.3593757230001000310580.312572600010004018228.062572900010003182513.3125733000100030190.875736000100030191.5739000100030192.09375743000100030390.9375746000100030571.359375749000100031732.03125Table 5
CPU times of the TTMLS algorithm and NLS algorithm in seconds.
30% noiseLenaBarbaraManBaboonTotalTTMLS algorithm18.81324.094100.81322.922166.642NLS algorithm19.54726.703108.28125.391179.92245% noiseTTMLS algorithm38.34439.125205.12535.406318.000NLS algorithm42.42141.688218.34439.422341.87560% noiseTTMLS algorithm91.06384.203417.04779.656671.969NLS algorithm97.93888.984438.15687.547712.625Dolan and Moré [35] provided a way to analyze the efficiency of these algorithms. From Figures 1–3, we can see that the 3performance of the TTMLS algorithm, TTMLS algorithm, and NLS algorithm is significantly better than that of the LS-WWP method and PRP-WWP method. Figures 1 and 2 show that the TTMLS algorithm and NLS algorithm can better approximate to the target function than the LS-WWP algorithm and PRP-WWP algorithm; thus, the number of iterations and the total number of function and gradient evaluation are smaller. The reason is that the search direction dk of the TTMLS algorithm contains more function information. Also, the CPU time in Figure 4, TTMLS algorithm is basically the same as the NLS algorithm, which is better than the other two. To sum up, the proposed algorithm has significant advantages.Figure 1
An overview of the performance of these four algorithms (NI).Figure 2
An overview of the performance of these four algorithms (NFG).Figure 3
An overview of the performance of these four algorithms (CPU).Figure 4
From left to right: the images disturbed by 30% salt-and-pepper noise, the images restored by the TTMLS algorithm, and the images restored by the NLS algorithm.


## 3.2. Image Restoration Problems

The image restoration problem is a difficult problem in the field of optimization. We will use the TTMLS algorithm and NLS algorithm to minimizeZ to recover the original image from an image corrupted by impulse noise. Afterwards, we compare the performance of the two algorithms. The data used in the experiment are as follows:Parameters: all the algorithms run withγ=0.6, γ1=0.3, ρ=0.9, and γ=0.7.Stop rule: ifgk+1−gk/gk<10−4 or xk+1−xk/xk<10−4 is satisfied, we stop the process.Symbol representation: CPU: the CPU time in seconds. Total: the total CPU time of the four pictures.The information of noise:30%, 45%, and 60% salt-and-pepper noise.Text problems: we restore the original image from the image destroyed by impulsive noise. The experiments chose Lena512×512, Barbara 512×512, Man 1024×1024, and Baboon 512×512 as the test images.From Figures4–6, we can Table 5 see that both algorithms can recover 30%, 45%, and 60% salt-and-pepper noise images very well. The data show that, for image restoration problems, the TTMLS algorithm has shorter CPU time than the NLS algorithm when the salt-and-pepper noise is 30%, 45%, and 60%. In conclusion, the TTMLS algorithm is promising and competitive.Figure 5
From left to right: the images disturbed by 45% salt-and-pepper noise, the images restored by the TTMLS algorithm, and the images restored by the NLS algorithm.Figure 6
From left to right: the images disturbed by 60% salt-and-pepper noise, the images restored by the TTMLS algorithm, and the images restored by the NLS algorithm.


## 3.3. Compressive Sensing Problems

The main work of this section is to accurately recover the image from a few of random projections by compressive sensing. The experimental method derives from the model proposed by Dai and Sha [36]. Then, the performance of the TTMLS algorithm and LS method with line search (12) is compared.It is noted that the gradientsgk and dk are square matrices in this experiment, and the matrix obtained by gkTdk may appear as a singular matrix, which results in the invalidation of the algorithm. But, when we calculate dk+1, we only need the value of gkTdk without knowing the information of this square matrix, so in this experiment, we set gkTdk=gkTdk∞ in dk+1. The data used in the experiment are as follows:Parameters: all the algorithms run withγ=0.6, γ1=0.3, ρ=0.9, and γ=0.7.Stop rule: ifgkTdk∞<10−3 or the number of iterations exceeds 500 is satisfied, we stop the process.Symbol representation: PSNR: Peak Signal-to-Noise Ratio. It is an objective criterion for image evaluation.Text problems: compressive sensing problems. The experiments chose Camera man256×256, Fruits 256×256, Lena 256×256, and Baboon 256×256 as the test images.From Figure7 and Table 6, we can see that both algorithms are effective in compression sensing problems. Meanwhile, from the experimental data, we can see that the TTMLS algorithm has more advantages than the LS algorithm.Figure 7
From left to right: the original images, the images restored by the TTMLS algorithm, and the images restored by the LS algorithm.Table 6
Peak signal-to-noise ratio (PSNR) of the TTMLS algorithm and LS algorithm.
AlgorithmCamera manFruitsLenaPeppersTotalTTMLS31.92933.05331.99633.075130.053LS30.79231.48631.48931.925125.692


## 4. Conclusions

In this paper, based on the well-known LS method and combined with improved Armijo linear search, this paper presents a three-term conjugate gradient algorithm. Without any linear search, the search direction of the new three-term conjugate algorithm is proved to have two good properties: sufficient descent and trust region properties. Also, the global convergence of the algorithm is established. The numerical results indicate that the new algorithm is effective. The good performance of the algorithm in image restoration problems and compressive sensing problems also proves that the algorithm is competitive.



---

*Source: 7859286-2020-10-19.xml*