# A Modified Nonlinear Conjugate Gradient Method with the Armijo Line Search and Its Application

Authors: Mengxiang Zhang; Yingjie Zhou; Songhua Wang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

In this article, a modified Polak-Ribière-Polyak (PRP) conjugate gradient method is proposed for image restoration. The presented method can generate sufficient descent directions without any line search conditions. Under some mild conditions, this method is globally convergent with the Armijo line search. Moreover, the linear convergence rate of the modified PRP method is established. The experimental results of unconstrained optimization, image restoration, and compressive sensing show that the proposed method is promising and competitive with other conjugate gradient methods.


---

## Body

## 1. Introduction

Consider the following unconstrained optimization problem:(1)minx∈ℜnfx,where fx:ℜn⟶ℜ is a continuously differentiable function. The iteration formula is determined by(2)xk+1=xk+αkdk,k=0,1,2,…,where αk is stepsize obtained by some kind of line search and dk is search direction.It is well known that there are many methods ([1–4] etc.) for solving optimization problem (1), where the conjugate gradient method is a powerful method because of its simplicity, and this method can avoid the computation and storage of some matrices associated with the Hessian of objective functions; then its memory requirements are very low. Large-scale calculations are usually required in the process of image processing; therefore, the conjugate gradient algorithm has excellent application prospects in this aspect. The search direction dk of the conjugate gradient methods is given by(3)dk=−gk,ifk=0,−gk+βkdk−1,ifk≥1,where βk∈ℜ is a scalar and gk=gxk is the gradient of objective function fx at the point xk. The choice of βk determines different conjugate gradient methods. Classical conjugate gradient methods include PRP conjugate gradient method [5, 6], HS conjugate gradient method [7], LS conjugate gradient method [8], DY conjugate gradient method [9], FR conjugate gradient method [10], and CD conjugate gradient method [11]. The parameters βk of these methods are specified as follows:(4)βkPRP=gkTyk−1gk−12,βkHS=gkTyk−1dk−1Tyk−1,βkLS=gkTyk−1−dk−1Tgk−1,βkDY=gk2dk−1Tyk−1,βkFR=gk2gk−12,βkCD=gk2−dk−1Tgk−1,where yk−1=gk−gk−1, and ‖⋅‖ stands the Euclidean norm. There has been much research on convergence properties of these methods ([12–15] etc.) and applications ([16–23] etc.).In this paper, the focus is mainly on the PRP method. The PRP method is generally believed to have the best numerical performance in classical conjugate gradient methods, but there is much room for discussion in terms of convergence. When the exact line search was used, the global convergence of the PRP conjugate gradient method has been proved by Polak and Ribière [5] for convex objective functions. However, Powell [24] proposed a counter example that the PRP conjugate gradient method may fail for nonconvex functions even if the exact line search is used. Gilbert and Nocedal [14] showed a modified PRP conjugate gradient method that the modified PRP method is globally convergent if βkPRP is restricted to be not less than zero and αk is determined by a line search step satisfying the sufficient descent condition:(5)−gkTdk≥cgk2,in addition to the following weak Wolfe-Powell conditions, i.e.,(6)fxk+αkdk≤fk+σαkgkTdk,gxk+αkdkTdk≥φgkTdk,where 0<σ<φ<1. Meanwhile, Gilbert and Nocedal [14] pointed out that even if the objective function is guaranteed to be uniformly convex, βk may be negative. With the strong Wolfe-Powell line search, Dai [25] gave an example showing that even though the objective function is uniformly convex, the PRP method cannot guarantee that the search direction is always the descent direction.Through the above observations and [14, 24, 26–28], the sufficient descent condition (5) and the condition βk≥0 play key roles in establishing the global convergence of the conjugate gradient methods. However, in the case where Armijo line search or Wolfe line search is used, the descent property of dk determined by (3) is in general not guaranteed.In order to obtain the generated sufficient descent direction, Hager and Zhang [29] showed a new conjugate gradient method (CG-C) obtained by modifying the HS method, which generates sufficient descent directions at each step, without relying on any line search. The scalar βk in CG-C method is determined by(7)βkNHS=maxβkN,μk,where(8)βkN=gkTyk−1dk−1Tyk−1−2yk−12dk−1Tyk−12gk−1Tdk−1,μk=1dk−1mingk−1,μ,and μ>0 is a constant. With the weak Wolfe-Powell line search, Hager and Zhang [29] established a global convergence result for (7) when the objective function fx is general nonlinear function.Along this line, Yu and Guan [30, 31] extended the CG-C method to the PRP, LS, DY, FR, and CD methods. The parameter βk in the modified PRP method (DPRP) is as follows:(9)βkDPRP=gkTyk−1gk−12+ηyk−12gk−14gkTdk−1,where η>1/4 is a constant. The performance of the above methods is better than other conjugate gradient in practice. In addition, because Armijo line search is very simple, compared with Wolfe line search, it is more widely used in image restoration and compressed sensing problems. Therefore, it is necessary to explore the performance of the above methods under Armijo line search. However, the above methods cannot obtain global convergence with Armijo line search, i.e., to find a stepsize αk=maxρii=0,1,2,… satisfying(10)fxk+αkdk≤fxk+δαkgkTdk,where 0<δ,ρ<1 are given constants. In order to overcome this defect, scholars have done a lot of related work ([32–34] etc). In order to overcome the defect of PRP, HS and LS conjugate gradient methods cannot globally converge with the Armijo line search, Li and Qu [33] proposed a series of modified conjugate gradient methods based on (3) and (4) as follows:(11)dk=−gk,ifk=0,−gk−βkgkTdk−1gk2gk+βkdk−1,ifk≥1,(12)βk=gkTyk−1zk−1,where zk−1 is a scalar to be specified. The parameter zk−1 is maxtdk−1,gk−12 in the modified PRP method (APRP). And the results of global convergence are established when the Armijo line search is used.Motivated by the idea of [31, 33] and taking into account the excellent numerical performance, we propose a new modified PRP method. The parameter βk is computed as(13)βkNPRP=gkTyk−1zk−1+ηyk−12zk−12gkTdk−1,where zk−1=maxtdk-1,gk−12, t>0 and η>1/4 are two constants. And the search direction dk is determined by the classical two-term conjugate gradient method (3).In the next section, the proposed algorithm is stated. In Section3, the properties and the convergent results of the new method are given. This method enjoys linear convergence under suitable conditions in Section 4. Numerical results and conclusion are presented in Section 5 and in Section 6, respectively.


## 2. Algorithm

This section will give algorithm of the new modified PRP method in association with the Armijo line search technique (10) for (1). The algorithm is stated as follows.Remark 1.
Without any line search method, the NPRP method can get sufficient descent properties.Lemma 1.
Letxk and dk be generated by the NPRP method. If zk−1≠0, for all k, then(14)gkTdk≤−1−14ηgk2,η>14.Proof.
Case (i)k=0. From (3), we get(15)g0Td0=−g02≤−1−14ηgk2,η>14.Hence (14) is satisfied.Case (ii)k≥1. From (3) and (13), we have(16)gkTdk=gkT−gk+βkNPRPdk−1,=−gk2+gkTyk−1zk−1+ηyk−12zk−12gkTdk−1gkTdk−1,=−gk2+zk−1gkTdk−1gkTyk−1+ηyk−12gkTdk−1gkTdk−1zk−12.
Define(17)uk=12ηzk−1gk,vk=2ηgkTdk−1yk−1.
By the above equation, we get(18)gkTdk=−gk2+ukTvk−1/2vk2zk−12,=−1−14ηgk2+ukTvk−1/2uk2+vk2zk−12,≤−1−14ηgk2,where η>1/4. Thus, (14) is satisfied.


## 3. Properties and Convergence Analysis

The following few suitable assumptions are often utilized in global convergence analysis for conjugate gradient algorithms.Assumption 1.
(i)
The level setΩ=x∈ℜn|fx≤fx0 is bounded.(ii)
Functionf:ℜn⟶ℜ is continuously differentiable and its gradient is Lipschitz continuous on an open convex set Ω1 containing Ω, i.e., there exists a constant L>0 such that(19)gx−gy≤Lx−y,∀x,y∈Ω1.
It follows directly from Assumption1 that there is a positive constant A, such that(20)x≤A,∀x∈Ω1.Lemma 2.
If Assumptions1 holds, xk, αk, dk, and gk be generated by Algorithm 1. There exists a constant B>1 such that the following inequality holds for all k, then(21)dk≤Bgk.Algorithm 1: NPRP method with Armijo line search.
Step 0: Choose an initial pointx0∈ℜn, constants δ,ρ∈0,1. Compute. g0=∇fx0. Set k=0.Step 1: Ifgk≤ϵ, then stop the iterations. Otherwise, continue with step 2.Step 2: Compute the system of equations (3) to get dk, where βk is obtained by (13).Step 3: Determine a step sizeαk by the Armijo line search (10).Step 4: Computexk+1=xk+αkdk, gk+1=∇fxk+1.Step 5: Letk=k+1 and go to Step 1.Proof.
Whenk=0, from (3), we can obtain(22)‖dk‖=‖gk‖,then (21) holds.
Whenk≥1, from (3) and (20), we have(23)βkNPRP=gkTyk−1zk−1+ηyk+12zk−12gkTdk−1,≤gkyk−1tdk−1+ηyk−12t2dk−12gkdk−1,≤gkyk−1tdk−1+ηyk−12t2dk−12gkdk−1,≤Lαkdk−1gktdk−1+ηLαkdk−12t2dk−12gkdk−1,≤2LBgktdk−1+η2LA2gkt2dk−12,=2LAt+4ηLA2t2gkdk−1.
Together with (3) and the above formula implies(24)dk≤gk+βkNPRPdk−1≤Bgk,letting(25)B=1+2LAt+4ηLA2t2.
Thus (21) is satisfied.Lemma 3.
If the stepsizeαk is obtained by Armijo line search, there exists a constant C>0 such that the following inequality holds for all k, then(26)αk≥C−gkTdkdk2.Proof.
Case (i)αk=1. From (14) and (26), we get(27)−gkTdk≥1−14ηgk2,−gkTdk≤dk2C.Then we need to satisfy(28)dk2C≥1−14ηgk2.From Lemma2, we have(29)C≤4η4η−1dk2gk2≤4η4η−1N2,N>1.Case (ii)αk<1. By the Armijo line search condition, ρ−1αk does not satisfy inequality (10). This means(30)fxk+ρ−1αkdk−fxk>δρ−1αkgkTdk.
By the mean-value theorem and inequality (19), there is a pk∈0,1 such as xk+pkρ−1αkdk∈Ω1 and(31)fxk+ρ−1αkdk−fxk=ρ−1αkgxk+pkρ−1αkdkTdk,=ρ−1αkgxkTdk+ρ−1αkgxk+pkρ−1αkdk−gxkTdk,≤ρ−1αkgxkTdk+Lpkρ−2αk2dk2,≤ρ−1αkgxkTdk+Lρ−2αk2dk2.
Observing the last inequality and (30), we have(32)αk≥1−δρ−gkTdkLdk2,letting(33)C=min4η4η−1,1−δρL.
Thus (26) is satisfied.Lemma 4.
Let the sequencexk, dk and gk be generated by Algorithm 1, and suppose that Assumption 1 holds, then,(34)∑k=0∞gkTdk2dk2<∞.Proof.
We have from (10) and Assumption 1 that(35)∑k=0∞−δαkgkTdk<∞.
Substituting (26) into the above formula, we have(36)∑k=0∞C−gkTdk2dk2δgkTdk≤∑k=0∞−δαkgkTdk<∞,where C and δ are two constants. Therefore, (34) holds.
Equation (34) is usually called the Zoutendijk condition [35], and it is very important for establishing global convergence.Theorem 1.
Suppose the conditions in Assumption1 hold. Let xk be generated by the NPRP method with Armijo line search, then either gk=0 for some k or limk⟶∞gk=0.Proof.
By Lemma2 and Lemma 4, we have(37)∑k=0∞gk4dk2<∞.
Together with (21), the above formula implies(38)∑k=0∞gk2≤B2∑k=0∞gk4dk2<∞,where B=1+2LA/t+4ηLA2/t2.
From the above inequality, we can obtainlimk⟶∞gk=0.Remark 2.
From the proof of Theorem1, with the Wolfe line search, the NPRP method can also establish global convergence without requirement of truncation and convexity of the objective function.


## 4. Linear Convergence Rate

When discussing the linear convergence rate for conjugate gradient methods, the following assumptions are often established on the basis of Assumption1.Assumption 2.
(i)
Objective functionf is twice continuously differentiable in Ω1(ii)
∇2fx is a symmetric positive definite matrix in Ω1, i.e., there exist positive constants M≥m>0 such that(39)m2d2≤dT∇2fxd≤M2d2,∀x∈Ω1,d∈ℜn.Lemma 5.
Suppose that Assumption2 holds and the sequence xk generated by the NPRP method converges with the Armijo line search. Then the sequence xk converges to the unique minimal point x∗.Proof.
If Assumption2 holds, then Assumption 1 holds, and objective function f is uniformly convex. By the Armijo line search (10) and Lemma 1, it can be deduced that fxk is a decreasing sequence.
Therefore, by the conclusion of Theorem1, the sequence xk converges to the unique minimal point x∗.Lemma 6.
Suppose that Assumption2 holds. The problem (1) has a unique solution x∗ and(40)12mx−x∗2≤fx−fx∗≤12Mx−x∗2,∀x∈Ω1,(41)mx−x∗≤gx≤Mx−x∗,∀x∈Ω1,(42)mx−y≤gx−gyTx−y≤Mx−y,∀x,y∈Ω1,(43)gx−gy≤Mx−y,∀x,y∈Ω1.Theorem 2.
Suppose Assumption2 holds. Let x∗ be the unique solution of problem (1) and the sequence xk be generated by the NPRP method with the Armijo line search. Then there are constants a>0 and r∈0,1 such that for all k, then(44)xk−x∗≤ark,that is, xk converges to x∗ at least R-linearly.Proof.
If Assumption2 holds, then Assumption 1 holds. By (14), (21), and (26), it is easy to prove that(45)αk≥C−gkTdkdk2≥CB2−gkTdkgk2≥CB21−14η.
We get from (14), (40), (41), (45), and the Armijo condition (10)(46)fxk+1−fx∗≤fxk−fx∗+δαkgkTdk,≤fxk−fx∗−δ1−14ηαkgk2,≤fxk−fx∗−δCB21−14ηm2xk−x∗2,≤fxk−fx∗−δCm2B21−14η22Mfxk−fx∗,=1−δ2Cm2MB21−14η2fxk−fx∗.
Lettingr=1−δ2Cm2/MB21−1/4η2, we have(47)fxk−fx∗≤r2fxk−1−fx∗≤⋯≤r2kfx0−fx∗.
Combing (40), we obtain(48)xk−x∗≤2mfxk−fx∗≤2mfx0−fx∗rk.
Hence (44) holds, where a=2/mfx0−fx∗. The proof is completed.Remark 3.
From the proof of Theorem2, with the Wolfe line search, the NPRP method can also establish that xk converges to x∗ at least R-linearly.


## 5. Numerical Experiments

In this section, we report some numerical results of Algorithm1 and compare the performance of some methods previously detailed in this paper. The following methods were compared:NPRP:βkNPRP is computed by (13), dk is determined by (3), the Armijo line search (10)).DPRP [30, 31]: βkDPRP is computed by (9), dk is determined by (3), the weak Wolfe-Powell line search (6).APRP [33]: βkAPRP is computed by (12), dk is determined by (11) the Armijo line search (10).All programs are written in MATLAB R2019a and run on a PC with an AMD Ryzen 5 3550 H with Radeon Vega Mobile Gfx CPU @2.10 GHz, 16 GB (14.9 GB available) of RAM and the Windows 10 operating system.


### 5.1. General Unconstrained Optimization Problems

#### 5.1.1. Contrast Algorithm

This experiment tests three algorithms, NPRP, DPRP and APRP.


#### 5.1.2. Tested Problems

A number of 74 unconstrained optimization test problems are described in Table1 [36, 37].Table 1
Test problem.
No.Test problem1Extended 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)39NONDIA 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)69Extended DENSCHNF function (CUTE)70SINQUAD function (CUTE)71BIGGSB1 function (CUTE)72Partial perturbed quadratic PPQ2 function73Scaled quadratic SQ1 function74Scaled quadratic SQ2 function


#### 5.1.3. Dimensionality

Problem instances with 3000, 9000, and 27000 variables are considered.


#### 5.1.4. Parameters

All the algorithms run witht=1, η=1, δ=0.1, ρ=0.9, σ=0.2, and φ=0.85.


#### 5.1.5. Termination Rule

Ifgk<10−6 or if the number of iterations exceeds 103.


#### 5.1.6. Symbol Representation

No: the test problem number, CPUTime: the CPU time in seconds, NI: the number of iterations, NFG: the total number of function and gradient evaluations.


#### 5.1.7. Image Description

Figures1–3 show the performance profiles of CPU Time, NI, and NFG of the three methods.Figure 1
Performance profiles of these methods (CPU Time).Figure 2
Performance profiles of these methods (NI).Figure 3
Performance profiles of these methods (NFG).From Table2 and Figures 1–3, we can see the performance of NPRP method and APRP method is significantly better than that of DPRP method. The reason is that the Armijo line search is more convenient than the Wolfe line search to obtain stepsize αk. Meanwhile, we can get that the performance of NPRP method is slightly better than that of APRP method.Table 2
Numerical results for the total CPU Time, NI and NFG.
AlgorithmCPU timeNINFGNPRP165.551019916383DPRP463.531252172448264APRP556.656251039939369


### 5.2. Image Restoration Problems

This subsection is done to recover the original image from an image corrupted by impulse noise.


#### 5.2.1. Contrast Algorithm

This experiment tests two algorithms, NPRP and APRP.


#### 5.2.2. Tested Problems

Restore the original image from the image destroyed by impulsive noise. The experiments chose Boat (256× 256), Lena (512 × 512), and Man (1024 × 1024) are the test images.


#### 5.2.3. Noise Level

Different algorithms perform for 25%, 50%, and 75% noise problems.


#### 5.2.4. Parameters

All the algorithms run witht=1, η=1, δ=0.1, and ρ=0.9.


#### 5.2.5. Termination Rule

Ifgk+1−gk/gk<10−6 or xk+1−xk/xk<10−6, the algorithm is terminated.


#### 5.2.6. Symbol Representation

CPU Time: the CPU time in seconds.


#### 5.2.7. Image Description

Figures4 and 5 show the recovery of different algorithms with different noise levels. Restoration of the Boat, Lena, and Man images is done by the NPRP method and APRP method. From left to right: a noise image with different percentages of salt-and-pepper noise, restorations with NPRP method, and restorations with APRP method.Figure 4
From left to right: 25% noise, NPRP method, APRP method.
(a)(b)(c)(d)(e)(f)(g)(h)(i)Figure 5
From left to right: 50% noise, NPRP method, APRP method.
(a)(b)(c)(d)(e)(f)(g)(h)(i)The results in Table3 and Figures 4–6 show us at least two conclusions: (i) NPRP method and APRP method are successful for restoring these images with suitable CPU time; (ii) NPRP method is promising and competitive to the APRP method for 25% noise problem, 50% noise problem, and 75% noise problem.Table 3
CPU times of the NPRP method and the APRP method in seconds.
BoatLenaManTotal25% noiseNPRP6.640613.859478.281398.7813APRP7.156315.156380.3281102.640750% noiseNPRP11.609445.8281204.1406261.5781APRP12.828149.3125212.4844274.625075% noiseNPRP20.984488.2188414.4375523.6407APRP21.656395.7344435.8438553.2345Figure 6
From left to right: 75% noise, NPRP method, APRP method.
(a)(b)(c)(d)(e)(f)(g)(h)(i)


### 5.3. Compressive Sensing Problems

The purpose of this section is to accurately recover the image from a few random projections by compressive sensing (CG), based on the gradient recovery algorithms. The experimental method comes from the model proposed by Dai and Sha [38].


#### 5.3.1. Contrast Algorithm

This experiment tests two algorithms, NPRP and APRP.


#### 5.3.2. Tested Problems

Recover the image accurately from a few of random projections. The experiments chose Phantom (256× 256), Fruits (256 × 256), and Peppers (256 × 256) as the test images.


#### 5.3.3. Parameters

All the algorithms run witht=0.3, η=1/3, δ=0.1, and ρ=0.4.


#### 5.3.4. Termination Rule

If the square root of the sum of the diagonal elements ofgkTgk is less than 10−3 or if the number of iterations exceeds 500.


#### 5.3.5. Symbol Representation

PSNR: peak signal to noise ratio. The greater the PSNR, the better the effect.


#### 5.3.6. Image Description

Figure7 shows the recovery of images after random measurement in Fourier domain. Restoration of the Phantom, Fruits, and Peppers images by NPRP method and APRP method. From left to right: original image, restorations with NPRP method, restorations with APRP method.Figure 7
From left to right: original image, NPRP method, APRP method.
(a)(b)(c)(d)(e)(f)(g)(h)(i)The results in Table4 and Figure 7 show us at least two conclusions: (i) NPRP method and APRP method are successful for restoring these images with suitable PSNR; (ii) NPRP method is promising and competitive to APRP method for compressive sensing problems.Table 4
Peak signal to noise ratio (PNSR).
AlgorithmPhantomFruitsPeppersTotalNPRP42.596234.303833.7987110.6987APRP42.403831.964633.3072107.6746From the above numerical experiment results, we can see that the performance of the NPRP method is more competitive than the APRP method and the DPRP method. The reasons are as follows. (i) Hager and Zhang pointed out in the survey paper [39] that the common molecule gkTyk−1 of the PRP, HS, and LS methods possess a built-in restart feature that addresses the jamming problem: the factor yk−1=gk−gk−1 in the numerator of βk tends to zero when the step sk−1=xk−xk−1 is too small. In addition, βk becomes smaller, and the new search direction dk is closer to the steepest descent direction gk. Meanwhile, NPRP method is similar in form to CG-C and PRP methods and therefore inherits their good performance. (ii) The Armijo line search is more convenient than the Wolfe line search to obtain stepsize αk.


## 5.1. General Unconstrained Optimization Problems

### 5.1.1. Contrast Algorithm

This experiment tests three algorithms, NPRP, DPRP and APRP.


### 5.1.2. Tested Problems

A number of 74 unconstrained optimization test problems are described in Table1 [36, 37].Table 1
Test problem.
No.Test problem1Extended 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)39NONDIA 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)69Extended DENSCHNF function (CUTE)70SINQUAD function (CUTE)71BIGGSB1 function (CUTE)72Partial perturbed quadratic PPQ2 function73Scaled quadratic SQ1 function74Scaled quadratic SQ2 function


### 5.1.3. Dimensionality

Problem instances with 3000, 9000, and 27000 variables are considered.


### 5.1.4. Parameters

All the algorithms run witht=1, η=1, δ=0.1, ρ=0.9, σ=0.2, and φ=0.85.


### 5.1.5. Termination Rule

Ifgk<10−6 or if the number of iterations exceeds 103.


### 5.1.6. Symbol Representation

No: the test problem number, CPUTime: the CPU time in seconds, NI: the number of iterations, NFG: the total number of function and gradient evaluations.


### 5.1.7. Image Description

Figures1–3 show the performance profiles of CPU Time, NI, and NFG of the three methods.Figure 1
Performance profiles of these methods (CPU Time).Figure 2
Performance profiles of these methods (NI).Figure 3
Performance profiles of these methods (NFG).From Table2 and Figures 1–3, we can see the performance of NPRP method and APRP method is significantly better than that of DPRP method. The reason is that the Armijo line search is more convenient than the Wolfe line search to obtain stepsize αk. Meanwhile, we can get that the performance of NPRP method is slightly better than that of APRP method.Table 2
Numerical results for the total CPU Time, NI and NFG.
AlgorithmCPU timeNINFGNPRP165.551019916383DPRP463.531252172448264APRP556.656251039939369


## 5.1.1. Contrast Algorithm

This experiment tests three algorithms, NPRP, DPRP and APRP.


## 5.1.2. Tested Problems

A number of 74 unconstrained optimization test problems are described in Table1 [36, 37].Table 1
Test problem.
No.Test problem1Extended 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)39NONDIA 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)69Extended DENSCHNF function (CUTE)70SINQUAD function (CUTE)71BIGGSB1 function (CUTE)72Partial perturbed quadratic PPQ2 function73Scaled quadratic SQ1 function74Scaled quadratic SQ2 function


## 5.1.3. Dimensionality

Problem instances with 3000, 9000, and 27000 variables are considered.


## 5.1.4. Parameters

All the algorithms run witht=1, η=1, δ=0.1, ρ=0.9, σ=0.2, and φ=0.85.


## 5.1.5. Termination Rule

Ifgk<10−6 or if the number of iterations exceeds 103.


## 5.1.6. Symbol Representation

No: the test problem number, CPUTime: the CPU time in seconds, NI: the number of iterations, NFG: the total number of function and gradient evaluations.


## 5.1.7. Image Description

Figures1–3 show the performance profiles of CPU Time, NI, and NFG of the three methods.Figure 1
Performance profiles of these methods (CPU Time).Figure 2
Performance profiles of these methods (NI).Figure 3
Performance profiles of these methods (NFG).From Table2 and Figures 1–3, we can see the performance of NPRP method and APRP method is significantly better than that of DPRP method. The reason is that the Armijo line search is more convenient than the Wolfe line search to obtain stepsize αk. Meanwhile, we can get that the performance of NPRP method is slightly better than that of APRP method.Table 2
Numerical results for the total CPU Time, NI and NFG.
AlgorithmCPU timeNINFGNPRP165.551019916383DPRP463.531252172448264APRP556.656251039939369


## 5.2. Image Restoration Problems

This subsection is done to recover the original image from an image corrupted by impulse noise.


### 5.2.1. Contrast Algorithm

This experiment tests two algorithms, NPRP and APRP.


### 5.2.2. Tested Problems

Restore the original image from the image destroyed by impulsive noise. The experiments chose Boat (256× 256), Lena (512 × 512), and Man (1024 × 1024) are the test images.


### 5.2.3. Noise Level

Different algorithms perform for 25%, 50%, and 75% noise problems.


### 5.2.4. Parameters

All the algorithms run witht=1, η=1, δ=0.1, and ρ=0.9.


### 5.2.5. Termination Rule

Ifgk+1−gk/gk<10−6 or xk+1−xk/xk<10−6, the algorithm is terminated.


### 5.2.6. Symbol Representation

CPU Time: the CPU time in seconds.


### 5.2.7. Image Description

Figures4 and 5 show the recovery of different algorithms with different noise levels. Restoration of the Boat, Lena, and Man images is done by the NPRP method and APRP method. From left to right: a noise image with different percentages of salt-and-pepper noise, restorations with NPRP method, and restorations with APRP method.Figure 4
From left to right: 25% noise, NPRP method, APRP method.
(a)(b)(c)(d)(e)(f)(g)(h)(i)Figure 5
From left to right: 50% noise, NPRP method, APRP method.
(a)(b)(c)(d)(e)(f)(g)(h)(i)The results in Table3 and Figures 4–6 show us at least two conclusions: (i) NPRP method and APRP method are successful for restoring these images with suitable CPU time; (ii) NPRP method is promising and competitive to the APRP method for 25% noise problem, 50% noise problem, and 75% noise problem.Table 3
CPU times of the NPRP method and the APRP method in seconds.
BoatLenaManTotal25% noiseNPRP6.640613.859478.281398.7813APRP7.156315.156380.3281102.640750% noiseNPRP11.609445.8281204.1406261.5781APRP12.828149.3125212.4844274.625075% noiseNPRP20.984488.2188414.4375523.6407APRP21.656395.7344435.8438553.2345Figure 6
From left to right: 75% noise, NPRP method, APRP method.
(a)(b)(c)(d)(e)(f)(g)(h)(i)


## 5.2.1. Contrast Algorithm

This experiment tests two algorithms, NPRP and APRP.


## 5.2.2. Tested Problems

Restore the original image from the image destroyed by impulsive noise. The experiments chose Boat (256× 256), Lena (512 × 512), and Man (1024 × 1024) are the test images.


## 5.2.3. Noise Level

Different algorithms perform for 25%, 50%, and 75% noise problems.


## 5.2.4. Parameters

All the algorithms run witht=1, η=1, δ=0.1, and ρ=0.9.


## 5.2.5. Termination Rule

Ifgk+1−gk/gk<10−6 or xk+1−xk/xk<10−6, the algorithm is terminated.


## 5.2.6. Symbol Representation

CPU Time: the CPU time in seconds.


## 5.2.7. Image Description

Figures4 and 5 show the recovery of different algorithms with different noise levels. Restoration of the Boat, Lena, and Man images is done by the NPRP method and APRP method. From left to right: a noise image with different percentages of salt-and-pepper noise, restorations with NPRP method, and restorations with APRP method.Figure 4
From left to right: 25% noise, NPRP method, APRP method.
(a)(b)(c)(d)(e)(f)(g)(h)(i)Figure 5
From left to right: 50% noise, NPRP method, APRP method.
(a)(b)(c)(d)(e)(f)(g)(h)(i)The results in Table3 and Figures 4–6 show us at least two conclusions: (i) NPRP method and APRP method are successful for restoring these images with suitable CPU time; (ii) NPRP method is promising and competitive to the APRP method for 25% noise problem, 50% noise problem, and 75% noise problem.Table 3
CPU times of the NPRP method and the APRP method in seconds.
BoatLenaManTotal25% noiseNPRP6.640613.859478.281398.7813APRP7.156315.156380.3281102.640750% noiseNPRP11.609445.8281204.1406261.5781APRP12.828149.3125212.4844274.625075% noiseNPRP20.984488.2188414.4375523.6407APRP21.656395.7344435.8438553.2345Figure 6
From left to right: 75% noise, NPRP method, APRP method.
(a)(b)(c)(d)(e)(f)(g)(h)(i)


## 5.3. Compressive Sensing Problems

The purpose of this section is to accurately recover the image from a few random projections by compressive sensing (CG), based on the gradient recovery algorithms. The experimental method comes from the model proposed by Dai and Sha [38].


### 5.3.1. Contrast Algorithm

This experiment tests two algorithms, NPRP and APRP.


### 5.3.2. Tested Problems

Recover the image accurately from a few of random projections. The experiments chose Phantom (256× 256), Fruits (256 × 256), and Peppers (256 × 256) as the test images.


### 5.3.3. Parameters

All the algorithms run witht=0.3, η=1/3, δ=0.1, and ρ=0.4.


### 5.3.4. Termination Rule

If the square root of the sum of the diagonal elements ofgkTgk is less than 10−3 or if the number of iterations exceeds 500.


### 5.3.5. Symbol Representation

PSNR: peak signal to noise ratio. The greater the PSNR, the better the effect.


### 5.3.6. Image Description

Figure7 shows the recovery of images after random measurement in Fourier domain. Restoration of the Phantom, Fruits, and Peppers images by NPRP method and APRP method. From left to right: original image, restorations with NPRP method, restorations with APRP method.Figure 7
From left to right: original image, NPRP method, APRP method.
(a)(b)(c)(d)(e)(f)(g)(h)(i)The results in Table4 and Figure 7 show us at least two conclusions: (i) NPRP method and APRP method are successful for restoring these images with suitable PSNR; (ii) NPRP method is promising and competitive to APRP method for compressive sensing problems.Table 4
Peak signal to noise ratio (PNSR).
AlgorithmPhantomFruitsPeppersTotalNPRP42.596234.303833.7987110.6987APRP42.403831.964633.3072107.6746From the above numerical experiment results, we can see that the performance of the NPRP method is more competitive than the APRP method and the DPRP method. The reasons are as follows. (i) Hager and Zhang pointed out in the survey paper [39] that the common molecule gkTyk−1 of the PRP, HS, and LS methods possess a built-in restart feature that addresses the jamming problem: the factor yk−1=gk−gk−1 in the numerator of βk tends to zero when the step sk−1=xk−xk−1 is too small. In addition, βk becomes smaller, and the new search direction dk is closer to the steepest descent direction gk. Meanwhile, NPRP method is similar in form to CG-C and PRP methods and therefore inherits their good performance. (ii) The Armijo line search is more convenient than the Wolfe line search to obtain stepsize αk.


## 5.3.1. Contrast Algorithm

This experiment tests two algorithms, NPRP and APRP.


## 5.3.2. Tested Problems

Recover the image accurately from a few of random projections. The experiments chose Phantom (256× 256), Fruits (256 × 256), and Peppers (256 × 256) as the test images.


## 5.3.3. Parameters

All the algorithms run witht=0.3, η=1/3, δ=0.1, and ρ=0.4.


## 5.3.4. Termination Rule

If the square root of the sum of the diagonal elements ofgkTgk is less than 10−3 or if the number of iterations exceeds 500.


## 5.3.5. Symbol Representation

PSNR: peak signal to noise ratio. The greater the PSNR, the better the effect.


## 5.3.6. Image Description

Figure7 shows the recovery of images after random measurement in Fourier domain. Restoration of the Phantom, Fruits, and Peppers images by NPRP method and APRP method. From left to right: original image, restorations with NPRP method, restorations with APRP method.Figure 7
From left to right: original image, NPRP method, APRP method.
(a)(b)(c)(d)(e)(f)(g)(h)(i)The results in Table4 and Figure 7 show us at least two conclusions: (i) NPRP method and APRP method are successful for restoring these images with suitable PSNR; (ii) NPRP method is promising and competitive to APRP method for compressive sensing problems.Table 4
Peak signal to noise ratio (PNSR).
AlgorithmPhantomFruitsPeppersTotalNPRP42.596234.303833.7987110.6987APRP42.403831.964633.3072107.6746From the above numerical experiment results, we can see that the performance of the NPRP method is more competitive than the APRP method and the DPRP method. The reasons are as follows. (i) Hager and Zhang pointed out in the survey paper [39] that the common molecule gkTyk−1 of the PRP, HS, and LS methods possess a built-in restart feature that addresses the jamming problem: the factor yk−1=gk−gk−1 in the numerator of βk tends to zero when the step sk−1=xk−xk−1 is too small. In addition, βk becomes smaller, and the new search direction dk is closer to the steepest descent direction gk. Meanwhile, NPRP method is similar in form to CG-C and PRP methods and therefore inherits their good performance. (ii) The Armijo line search is more convenient than the Wolfe line search to obtain stepsize αk.


## 6. Conclusion

In this paper, a modified PRP conjugate gradient method was proposed to solve image restoration and compression sensing problems, based on the well-known CG-C method [29]. With the Armijo line search, the global convergence and liner convergence rate of the algorithm is established under some suitable conditions. The sufficient descent property of the algorithm has been proved without the use of any line search method. The numerical results indicate that the algorithm is effective and competitive for solving unconstrained optimization problems, image restoration problems, and compressive sensing problems.



---

*Source: 6210965-2020-08-28.xml*