# A New Hybrid PRPFR Conjugate Gradient Method for Solving Nonlinear Monotone Equations and Image Restoration Problems

Authors: Yingjie Zhou; Yulun Wu; Xiangrong Li
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

A new hybrid PRPFR conjugate gradient method is presented in this paper, which is designed such that it owns sufficient descent property and trust region property. This method can be considered as a convex combination of the PRP method and the FR method while using the hyperplane projection technique. Under accelerated step length, the global convergence property is gained with some appropriate assumptions. Comparing with other methods, the numerical experiments show that the PRPFR method is more competitive for solving nonlinear equations and image restoration problems.


---

## Body

## 1. Introduction

Consider the following nonlinear equation:(1)Fx=0,x∈S,where S is a closed and convex subset. The function F:ℜn⟶ℜn is monotone and continuously differentiable which satisfies(2)Fx1−Fx2,x1−x2≥0,∀x1,x2∈ℜn.This problem of monotone equations has all kinds of applications, such as compressive sensing [1] and chemical equilibrium problems [2]. The conjugate gradient algorithm generates the iteration point via(3)xk+1=xk+αkdk,k=0,1,2,…,where αk is the step size generated from a proper line search and dk is a search direction. There are many methods to find dk, such as the Newton method [3], quasi-Newton method [4], and conjugate gradient method [5–13]. As we all know, the Newton method, the quasi-Newton method, and their related methods are very popular due to their local superlinear convergence property. But, it is expensive for them to compute the Jacobian matrix or the approximate Jacobian matrix in per iteration while the dimensions are very large.Due to the simplicity, less storage, efficiency, and nice convergence property, the conjugate gradient method becomes more and more popular for solving nonlinear equations [14–18]. The search direction of the conjugate gradient method is usually defined as(4)dk=−Fk,ifk=0,−Fk+βkdk−1,ifk≥1,where Fk=Fxk and βk is a parameter. Diverse βk means a diverse CG method. There are some famous CG methods such as the FR method [7], the PRP method [10], the DY method [5], the LS method [9], the HS method [8], and the CD method [6]. The parameter we mentioned is as follows:(5)βkFR=Fk2Fk−12,(6)βkPRP=FKTyk−1Fk−12,(7)βkDY=Fk2dk−1Tyk−1,(8)βkLS=FkTyk−1−Fk−1Tdk−1,(9)βkHS=FkTyk−1dk−1Tyk−1,(10)βkCD=Fk2−gk−1Tyk−1,where yk−1=Fk−Fk−1 and · means the Euclidian norm.In 1990, the first hybrid conjugate gradient method was proposed by Touati-Ahmed and Storey [19], and this method has global convergence while using the strong Wolfe line search. Dai and Yuan [20] proposed a CG method for unconstrained optimization and proved the global convergence of these hybrid computational schemes. Dong and Jiao [21] proposed a convex combination of the PRP and DY methods for solving nonlinear equations. Furthermore, the projection technique proposed by Solodov and Svaiter [22] motivated many scholars to further develop methods for solving (1) [23, 24].Inspired by the convex combination proposed in [25], we proposed a convex combination of a modified PRP and a modified FR method with trust region property which [25] was not present before. We also try to make the algorithm inherit the convergence of the PRP method and excellent performance of the FR method.The main contributions of the hybrid CG method are as follows:(i)
The given direction is designed as a convex combination of PRP and FR methods(ii)
The given direction has the sufficient descent property(iii)
The given direction has the trust region property(iv)
The global convergence of the presented algorithm is proved(v)
Numerical experiments show that the algorithm is more competitive for nonlinear equations and image restoration problemsIn Section2, we introduce the motivation and the PRPFR algorithm. In Section 3, we prove the sufficient property and the trust region property and give the convergence analysis. Section 4 shows the numerical experiment results. The conclusion is reported in the last section.


## 2. Algorithm

Motivated by the convex combination proposed in [25], we proposed a method which is a convex combination of a modified PRP method and a modified FR method for solving problem (1) and image restoration problems. We have recalled the classic PRP and classic FR conjugate gradient parameters in (5) and (6). For global convergence and good numerical performance, we defined the modified parameters as(11)βkMPRP=FkTyk−1maxtdk−1yk−1,Fk−12,(12)βkMFR=Fk2maxtdk−1Fk,Fk−12,where t>0 is a constant.Next, we utilized the global convergence ofβkMPRP and the excellent numerical behavior of βkMFR by defining a new parameter called βkPRPFR. The new parameter is defined as(13)βkPRPFR=1−γkβkMPRP+γkβkMFR,where γk=yk−12/yk−1Ts^k−1, s^k−1=sk−1+max0,−sk−1Tyk−1/yk−12+1yk−1, sk−1=xk−xk−1.The definition ofs^k−1 is by Li and Fukushima [4], and γk is proposed in [26]. We now proposed a hybrid gradient search direction as(14)dk=−Fk,ifk=0,−1+βkPRPFRFkTdk−1Fk2Fk+βkPRPFRdk−1,ifk≥1,where βkPRPFR is defined in (13).Remark 1.
By the definition ofs^k−1 and yk−1, we obtain that(15)yk−1Ts^k−1≥yk−1sk−1+−sk−1Tyk−1yk−12+1yk−1=yk−1Tsk−1−sk−1Tyk−1+yk−12=yk−12>0.
Therefore, we have(16)0<yk−12yk−1Ts^k−1≤1.Remark 2.
By the definition ofβkPRPFR and γk, we have(17)βkPRPFR≤βkMPRP+βkMFR.
Now, we introduce the hyperplane projection method by Solodov and Svaiter [22]. We first give the definition of the projection operator PS·:(18)PSx=argminx−yy∈S,∀x∈ℜn.
There is a fundamental property, that is,(19)PSx1−PSx2≤x1−x2,∀x1,x2∈ℜn.
The hyperplane projection method is as follows: letxk be the current iteration point and zk=xk+αkdk be obtained by line search direction dk such that FzkTxk−zk>0. According to the monotonicity of Fx, we have(20)FzkTx∗−zk≤0,if x∗ is a solution. Then, the hyperplane(21)Hk=x∈ℜnFzkTxk−zk=0strictly separates the current iteration xk from the solution of problem (1). The next iterate can be computed by projecting on it. That is,(22)xk+1=xk−FzkTxk−zkFzkFzk2.
As for the step size, we will use an appropriate line search to make performance better. Andrei [27] presented an acceleration scheme that generates the step size αk in a multiplicative manner to improve the reduction of the function values along the iterations. The step size is defined as follows:(23)α^k=ξkαk,(24)ξk=−φkϕk,φk=αkFkTdk,ϕk=−αkFk−FzkTdk.
Ifϕk>0, let αk=α^k.
Motivated by the above discussions, we proposed a hybrid conjugate gradient algorithm in Algorithm1.Algorithm 1.
PRPFR conjugate gradient algorithm.Step 0: given an initial pointx0∈ℝn and constant 0<ε<1, 0<ρ<1, κ>0, σ>0, and t>0, let k:=0.Step 1: ifFk≤ε, stop. Otherwise, compute dk by (11)–(14).Step 2: choosingαk=maxκρi:i=0,1,2,…, such that(25)−Fxk+αkdkTdk≥σαkdk2.Step 3: computingϕk through (24), if ϕk>0, then αk=α^k by (23).Step 4: settingzk=xk+αkdk, if Fzk≤ε, stop. Otherwise, compute the next iterate xk+1 using (22).Step 5: letk:=k+1, go to Step 2.


## 3. Convergence Analysis

We will establish the convergence of Algorithm1 in this section. First, we give the following assumptions.Assumption 1.
The functionFx is Lipschitz continuous; that is, there exists a positive constant L such that(26)Fx1−Fx2≤Lx1−x2,∀x1,x2∈ℝn.Assumption 2.
The solution set of problem (1) is nonempty.
From Assumption1, there exists a positive constant ω such that(27)Fxk≤ω.Lemma 1.
Letdk be defined by (11)–(14), and then dk satisfies the sufficient descent condition. That is,(28)FkTdk=−Fk2.Proof.
Ifk=0, we have F0Td0=−F02. If k≥1, by (14), we have(29)FkTdk=−1+βkPRPFRFkTdk−1Fk2FkTFk+βkPRPFRFkTdk−1=−Fk2−βkPRPFRFkTdk−1Fk2Fk2+βkPRPFRFkTdk−1=−Fk2−βkPRPFRFkTdk−1+βkPRPFRFkTdk−1=−Fk2.Lemma 2.
Fromdk defined in (11)–(14), dk satisfies the trust region property independent of the line search. That is,(30)Fk≤dk≤1+2tFk.Proof.
According to equality (28) and Cauchy–Schwartz inequality, we have(31)‖Fxk‖≤‖dk‖.
Furthermore, sincemaxtdk−1yk−1,Fk−12≥tdk−1yk−1 and maxtdk−1Fk,Fk−12≥tdk−1Fk, then(32)dk=−1+βkPRPFRFkTdk−1Fk2Fk+βkPRPFRdk−1≤Fk+βkPRPFRFk2dk−1Fk2+βkPRPFRdk−1≤Fk+2βkMPRP+βkMFRdk−1≤Fk+2Fkyk−1maxtdk−1yk−1,Fk−12+Fk2maxtdk−1Fk,Fk−12dk−1≤Fk+2Fkyk−1tdk−1yk−1+Fk2tdk−1Fkdk−1=Fk+2Fkt=1+2tFk.
Then, the proof is complete.Lemma 3.
Ifxk and zk can be generated by the PRPRFR algorithm, then the step size αk satisfies(33)αk≥minκ,ρFk2L+σdk2.Proof.
From the line search (25), supposing αk≠κ, then αk′=αkρ−1 does not satisfy the line search (25). That is,(34)−Fxk+αk′dkTdk<σαk′dk2.
Using the Lipschitz continuous ofFx and (28), we have(35)Fk2=−FkTdk=Fxk+αk′dk−FkTdk−Fxk+αk′dkTdk≤Lαk′dk2+σαk′dk2=αk′L+σdk2.
Therefore,(36)αk≥ρFk2L+σdk2.
The proof is complete.Lemma 4.
(see [22]). Suppose that x∗∈ℝn satisfies Fx∗=0. Let xk be generated by the PRPFR algorithm. Then,(37)xk+1−x∗2≤xk−x∗2−xk+1−xk2.Lemma 5.
Letxk be generated by the PRPFR algorithm, and then(38)limk⟶∞αkdk=0.Proof.
Lemma4 indicates that xk is bounded and(39)limk⟶∞xk+1−xk=0.
From (22) and (25), we have that(40)xk+1−xk=FzkTxk−zkFzkFzk2=−αkFzkTdkFzk≥σαk2dk2≥0.
From the abovementioned, the proof is complete.
Now, we establish the global convergence of the PRPFR algorithm.Theorem 1.
Letxk be generated by the PRPFR algorithm. Then,(41)liminfk⟶∞Fk=0.Proof.
We assume (41) does not hold, and then there exists δ>0 such that ∀k≥0, Fk≥δ. This together with (30) yields(42)dk≥Fk≥δ,∀k≥0.
According to (21)–(26) and (42), we get(43)dk≤Fk+βkPRPFRFk2dk−1Fk2+βkPRPFRdk−1≤Fk+2βkMPRP+βkMFRdk−1≤Fk+2Fkyk−1maxtdk−1yk−1,Fk−12+Fk2maxtdk−1Fk,Fk−12dk−1≤Fk+2Fkyk−1Fk−12+Fk2Fk−12dk−1≤ω+2ωδ−2Lxk−xk−1+ω2δ−2dk−1.
The fourth inequality holds sincemaxtdk−1yk−1,Fk−12≥Fk−12 and maxtdk−1Fk,Fk−12≥Fk−12. The last inequality implies that dk is bounded. By (30), we have(44)dk≤M,where M=1+2/tω. Multiplying both sides of (33) with dk, we obtain that(45)αkdk≥maxκ,ρFk2L+σdk2dk≥maxκδ,ρδ2L+σM>0.
This inequality mentioned above contradicts (38); therefore, (41) holds.


## 4. Numerical Experiments

In this section, we report some numerical experiments to investigate the computational efficiency of the proposed hybrid conjugate gradient algorithm. The numerical experiments will be divided into two sections including normal nonlinear equations and image restoration problems. All tests in this section are written in MATLAB 2018a, run on a PC with AMD Ryzen 7 4800 U with Radeon Graphics 1.80 Hz, 16 GB of SDRAM memory, and Windows 10 system.


### 4.1. Normal Nonlinear Equations

In this section, we test some normal nonlinear equations. The concrete test problems come from [28] and are listed in Table 1. To compare the numerical performance of the PRPFR algorithm, we also do the experiments with the modified PRP algorithm [29] and the FR algorithm [7]. The columns of Tables 2–4 have the following meaning.Table 1
Test problems.
No.Test problems1Exponential function 22Trigonometric function3Singular function4Logarithmic function5Broyden tridiagonal function6Trigexp function7Strictly convex function 18Variable dimensioned function9Tridiagonal system10Five-diagonal system11Extended Freudenstein and Roth function (n is even)12Discrete boundary value problemTable 2
Test results of the PRPFR algorithm.
No.DimPRPFR algorithmNI/NFCPUGN1300013/1350.031258.02E − 06900017/2051.718759.48E − 063000061/80213.0468759.73E − 06900006/912.4218757.17E − 062300014/390.06259.54E − 06900014/390.8281255.50E − 063000013/360.9843756.01E − 069000012/331.218756.18E − 063300019999/2025333.251.46E − 05900019501/19813425.31259.99E − 063000017291/17984783.7968751.00E − 059000019518/214901765.4531251.00E − 054300024/490.06257.65E − 06900025/510.5156256.59E − 063000026/531.06256.00E − 069000027/552.7343755.20E − 065300049/1920.0781256.04E − 06900060/2291.1406259.16E − 063000049/1903.54.52E − 069000046/1795.255.04E − 066300028/1470.1093757.39E − 06900029/1511.18757.66E − 063000029/1543.093757.03E − 069000033/1705.1718753.56E − 067300022/460.0468755.78E − 06900023/480.2343755.00E − 063000023/481.2031259.14E − 069000024/502.2343757.91E − 06830001/30.06253.19E − 0890001/300.00E + 00300001/30.031250.00E + 00900001/30.0781250.00E + 0093000626/33371.968759.89E − 0690001696/1043971.93759.91E − 06300001410/8756150.7656259.98E − 06900001374/8779236.906259.99E − 06103000917/52661.531259.96E − 069000664/347424.8906259.92E − 0630000480/304749.156259.87E − 0690000759/4313119.0156259.87E − 06113000305/18980.6259.96E − 069000276/171411.0781259.69E − 0630000333/206935.93759.91E − 0690000283/175944.6718758.69E − 0612300012/370.0468755.29E − 06900011/340.9531255.99E − 063000010/310.756.52E − 06900009/281.57.52E − 06No: the serial number of the problem. Dim: the dimensions of x. NF: the function evaluation numbers. NI: the iteration numbers. CPU: the calculation time in seconds. GN: the final function norm evaluations when the program is stopped.Initialization: the parameters are chosen as ρ=0.5, κ=1, σ=0.5, t=0.85, and ε=10−5.Stoprule: when Fx≤10−5 or NI≥20000 is satisfied, we stop the process.Table 3
Test results of the modified PRP algorithm.
No.DimModified PRP algorithmNI/NFCPUGN1300038/3890.2343759.84E − 06900021/2501.68759.08E − 063000020/2714.2031259.70E − 069000010/1553.781258.09E − 062300018/470.06259.87E − 06900018/470.68755.67E − 063000017/440.906256.32E − 069000015/391.7031257.76E − 06330009999/1040410.9843752.83E − 0590009999/10873190.1406255.01E − 05300009999/11895435.2968753.15E − 05900009999/13913839.7343754.85E − 054300042/1940.1093755.69E − 09900066/35233.37E − 0630000121/74813.281254.61E − 0790000218/153841.43757.05E − 085300067/2800.18755.90E − 06900090/3933.1718758.05E − 0630000111/5419.4531257.88E − 0690000139/78724.281256.16E − 066300075/5170.2656256.67E − 069000107/8407.2031253.88E − 0630000165/148726.968757.27E − 0690000252/253777.258.93E − 067300039/1380.0468756.65E − 06900056/2452.843756.87E − 063000089/4777.531255.70E − 0690000139/86925.093756.00E − 06830001/20.031250.00E + 0090001/200.00E + 00300001/20.06250.00E + 00900001/20.156250.00E + 00930005544/4387012.7656259.85E − 0690005832/49309347.2031259.84E − 06300006424/60507960.5468759.68E − 06900007445/806621983.5781259.83E − 06103000768/49971.5156259.84E − 069000881/610844.81259.28E − 06300001043/8118121.3593759.89E − 06900001343/11835301.6258.92E − 06113000512/33451.843759.85E − 069000545/364623.9531259.95E − 06300001122/7498119.31259.90E − 06900001229/8722223.1406259.54E − 0612300016/480.0781257.22E − 06900013/390.56258.96E − 063000011/331.3906258.41E − 069000010/301.6718757.92E− 06Table 4
Test results of the FR algorithm.
No.DimFR algorithmNI/NFCPUGN1300029/3710.2031259.84E − 06900021/2942.259.38E − 063000012/1833.9843759.11E − 06900005/802.093756.44E − 062300013/500.0781256.48E − 06900012/460.4843757.47E − 063000011/420.9843758.14E − 069000010/381.4843759.72E − 063300019999/2660781941.12E − 03900019999/2658652918.281251.20E − 033000019999/2653186049.656257.84E − 049000019999/2660128251.8593753.84E − 044300024/720.0468755.59E − 06900024/720.593759.65E − 063000025/751.281258.80E − 069000026/783.2031257.62E − 065300062/3810.218757.73E − 06900069/46239.20E − 0630000101/76712.6093759.75E − 0690000128/121526.906258.22E − 066300026/1650.1093759.06E − 06900021/1270.906256.10E − 063000022/1341.93757.51E − 069000022/1343.3593755.31E − 067300023/700.06255.30E − 06900023/700.406259.17E − 063000024/731.5781258.37E − 069000025/761.906257.25E − 06830001/303.19E − 0890001/30.0781250.00E + 00300001/30.1406250.00E + 00900001/30.031250.00E + 00930001248/153994.468759.91E − 0690001544/19579125.31259.87E − 06300001175/14881203.8281259.96E − 06900001027/13000263.968759.91E − 06103000763/88922.6406259.90E − 069000765/891253.843759.92E − 0630000806/9498127.4218759.65E − 06900001572/20089423.43759.97E − 06113000373/40721.0781259.98E − 069000387/422624.718759.49E − 0630000402/439357.8281259.77E − 0690000415/453797.2968759.44E − 0612300010/360.06257.27E − 0690009/310.218755.83E − 06300006/190.2343757.66E − 06900006/190.7656253.95E − 06According to Tables2–4, it is evident that the three methods can solve most of the test problems with NI≥20000. However, the FR method cannot handle the function 3 with 9000 dimensions, 30000 dimensions, and 90000 dimensions, while the PRPFR can solve the problem with NI≥20000. For more directly knowing the performance of this method, Dolan and Moré [30] introduced a technique to compare the performance of different algorithms. In Figure 1, when τ>1.2, the PRPFR algorithm is obviously better than the FR algorithm and the modified PRP algorithm. In Figure 2, the PRPFR algorithm solves all the problems at approximately τ=4.4, while the FR algorithm solves 90% of the test problems at approximately τ=4.6, and the modified PRP algorithm solves 75% of the test problems at approximately τ=5. In Figure 3, the PRPFR algorithm solves 94% of the problems at approximately τ=3.3. The FR algorithm and the modified PRP algorithm solve 77% and 58% of the test problems at approximately τ=3.3 and τ=4, respectively. From Tables 2–4 and Figures 1–3, it is obvious that the performance of the PRPFR algorithm is better than that of the FR algorithm and the modified PRP algorithm for most problems. Therefore, we conclude that the PRPFR algorithm is competitive to the FR algorithm and the modified PRP algorithm.Figure 1
Performance profiles of the methods (NI).Figure 2
Performance profiles of the methods (NF).Figure 3
Performance profiles of the methods (CPU).Table 5
CPU times of the PRPFR algorithm and the modified PRP algorithm in seconds.
20% noiseLenaBarbaraManTotalPRPFR algorithm2.7193.57812.84419.141Modified PRP algorithm3.2814.56313.12520.96945% noiseLenaBarbaraManTotalPRPFR algorithm5.6727.17229.96942.813Modified PRP algorithm6.1567.79731.60945.56370% noiseLenaBarbaraManTotalPRPFR algorithm14.06317.39161.90693.359Modified PRP algorithm17.07818.79762.45398.328


### 4.2. Image Restoration Problems

Image restoration aims to recover the original image from an image damaged by impulse noise. These problems are significant in optimization fields. The stop rule isFk+1−Fk/Fk<10−3 or xk+1−xk/xk<10−3. The experiments choose Lena (512×512), Barbara (512×512), and Man (1024×1024) as the test images. Meanwhile, we compare the PRPFR algorithm experiments’ performance with that of the modified PRP algorithm, where the step size αk is generated by Step 2 and Step 3 in the PRPFR algorithm. The detailed performance results are shown in Figures 4–6. It can be observed that both the PRPFR algorithm and the modified PRP algorithm are able to restore the blur image of these three images.Figure 4
From left to right: a noisy image with20% salt-and-pepper noise and the restorations obtained with the PRPFR algorithm and the modified PRP algorithm.Figure 5
From left to right: a noisy image with45% salt-and-pepper noise and the restorations obtained with the PRPFR algorithm and the modified PRP algorithm.Figure 6
From left to right: a noisy image with70% salt-and-pepper noise and the restorations obtained with the PRPFR algorithm and the modified PRP algorithm.From Figures4–6, we can easily notice that both algorithms are successful for restoring these noisy images with 20%, 45%, and 70% noise. According to the results in Table 5, we can draw the conclusion that the PRPFR algorithm is more effective than the modified PRP algorithm for 20% noise problems, 45% noise problems, and 70% noise problems.


## 4.1. Normal Nonlinear Equations

In this section, we test some normal nonlinear equations. The concrete test problems come from [28] and are listed in Table 1. To compare the numerical performance of the PRPFR algorithm, we also do the experiments with the modified PRP algorithm [29] and the FR algorithm [7]. The columns of Tables 2–4 have the following meaning.Table 1
Test problems.
No.Test problems1Exponential function 22Trigonometric function3Singular function4Logarithmic function5Broyden tridiagonal function6Trigexp function7Strictly convex function 18Variable dimensioned function9Tridiagonal system10Five-diagonal system11Extended Freudenstein and Roth function (n is even)12Discrete boundary value problemTable 2
Test results of the PRPFR algorithm.
No.DimPRPFR algorithmNI/NFCPUGN1300013/1350.031258.02E − 06900017/2051.718759.48E − 063000061/80213.0468759.73E − 06900006/912.4218757.17E − 062300014/390.06259.54E − 06900014/390.8281255.50E − 063000013/360.9843756.01E − 069000012/331.218756.18E − 063300019999/2025333.251.46E − 05900019501/19813425.31259.99E − 063000017291/17984783.7968751.00E − 059000019518/214901765.4531251.00E − 054300024/490.06257.65E − 06900025/510.5156256.59E − 063000026/531.06256.00E − 069000027/552.7343755.20E − 065300049/1920.0781256.04E − 06900060/2291.1406259.16E − 063000049/1903.54.52E − 069000046/1795.255.04E − 066300028/1470.1093757.39E − 06900029/1511.18757.66E − 063000029/1543.093757.03E − 069000033/1705.1718753.56E − 067300022/460.0468755.78E − 06900023/480.2343755.00E − 063000023/481.2031259.14E − 069000024/502.2343757.91E − 06830001/30.06253.19E − 0890001/300.00E + 00300001/30.031250.00E + 00900001/30.0781250.00E + 0093000626/33371.968759.89E − 0690001696/1043971.93759.91E − 06300001410/8756150.7656259.98E − 06900001374/8779236.906259.99E − 06103000917/52661.531259.96E − 069000664/347424.8906259.92E − 0630000480/304749.156259.87E − 0690000759/4313119.0156259.87E − 06113000305/18980.6259.96E − 069000276/171411.0781259.69E − 0630000333/206935.93759.91E − 0690000283/175944.6718758.69E − 0612300012/370.0468755.29E − 06900011/340.9531255.99E − 063000010/310.756.52E − 06900009/281.57.52E − 06No: the serial number of the problem. Dim: the dimensions of x. NF: the function evaluation numbers. NI: the iteration numbers. CPU: the calculation time in seconds. GN: the final function norm evaluations when the program is stopped.Initialization: the parameters are chosen as ρ=0.5, κ=1, σ=0.5, t=0.85, and ε=10−5.Stoprule: when Fx≤10−5 or NI≥20000 is satisfied, we stop the process.Table 3
Test results of the modified PRP algorithm.
No.DimModified PRP algorithmNI/NFCPUGN1300038/3890.2343759.84E − 06900021/2501.68759.08E − 063000020/2714.2031259.70E − 069000010/1553.781258.09E − 062300018/470.06259.87E − 06900018/470.68755.67E − 063000017/440.906256.32E − 069000015/391.7031257.76E − 06330009999/1040410.9843752.83E − 0590009999/10873190.1406255.01E − 05300009999/11895435.2968753.15E − 05900009999/13913839.7343754.85E − 054300042/1940.1093755.69E − 09900066/35233.37E − 0630000121/74813.281254.61E − 0790000218/153841.43757.05E − 085300067/2800.18755.90E − 06900090/3933.1718758.05E − 0630000111/5419.4531257.88E − 0690000139/78724.281256.16E − 066300075/5170.2656256.67E − 069000107/8407.2031253.88E − 0630000165/148726.968757.27E − 0690000252/253777.258.93E − 067300039/1380.0468756.65E − 06900056/2452.843756.87E − 063000089/4777.531255.70E − 0690000139/86925.093756.00E − 06830001/20.031250.00E + 0090001/200.00E + 00300001/20.06250.00E + 00900001/20.156250.00E + 00930005544/4387012.7656259.85E − 0690005832/49309347.2031259.84E − 06300006424/60507960.5468759.68E − 06900007445/806621983.5781259.83E − 06103000768/49971.5156259.84E − 069000881/610844.81259.28E − 06300001043/8118121.3593759.89E − 06900001343/11835301.6258.92E − 06113000512/33451.843759.85E − 069000545/364623.9531259.95E − 06300001122/7498119.31259.90E − 06900001229/8722223.1406259.54E − 0612300016/480.0781257.22E − 06900013/390.56258.96E − 063000011/331.3906258.41E − 069000010/301.6718757.92E− 06Table 4
Test results of the FR algorithm.
No.DimFR algorithmNI/NFCPUGN1300029/3710.2031259.84E − 06900021/2942.259.38E − 063000012/1833.9843759.11E − 06900005/802.093756.44E − 062300013/500.0781256.48E − 06900012/460.4843757.47E − 063000011/420.9843758.14E − 069000010/381.4843759.72E − 063300019999/2660781941.12E − 03900019999/2658652918.281251.20E − 033000019999/2653186049.656257.84E − 049000019999/2660128251.8593753.84E − 044300024/720.0468755.59E − 06900024/720.593759.65E − 063000025/751.281258.80E − 069000026/783.2031257.62E − 065300062/3810.218757.73E − 06900069/46239.20E − 0630000101/76712.6093759.75E − 0690000128/121526.906258.22E − 066300026/1650.1093759.06E − 06900021/1270.906256.10E − 063000022/1341.93757.51E − 069000022/1343.3593755.31E − 067300023/700.06255.30E − 06900023/700.406259.17E − 063000024/731.5781258.37E − 069000025/761.906257.25E − 06830001/303.19E − 0890001/30.0781250.00E + 00300001/30.1406250.00E + 00900001/30.031250.00E + 00930001248/153994.468759.91E − 0690001544/19579125.31259.87E − 06300001175/14881203.8281259.96E − 06900001027/13000263.968759.91E − 06103000763/88922.6406259.90E − 069000765/891253.843759.92E − 0630000806/9498127.4218759.65E − 06900001572/20089423.43759.97E − 06113000373/40721.0781259.98E − 069000387/422624.718759.49E − 0630000402/439357.8281259.77E − 0690000415/453797.2968759.44E − 0612300010/360.06257.27E − 0690009/310.218755.83E − 06300006/190.2343757.66E − 06900006/190.7656253.95E − 06According to Tables2–4, it is evident that the three methods can solve most of the test problems with NI≥20000. However, the FR method cannot handle the function 3 with 9000 dimensions, 30000 dimensions, and 90000 dimensions, while the PRPFR can solve the problem with NI≥20000. For more directly knowing the performance of this method, Dolan and Moré [30] introduced a technique to compare the performance of different algorithms. In Figure 1, when τ>1.2, the PRPFR algorithm is obviously better than the FR algorithm and the modified PRP algorithm. In Figure 2, the PRPFR algorithm solves all the problems at approximately τ=4.4, while the FR algorithm solves 90% of the test problems at approximately τ=4.6, and the modified PRP algorithm solves 75% of the test problems at approximately τ=5. In Figure 3, the PRPFR algorithm solves 94% of the problems at approximately τ=3.3. The FR algorithm and the modified PRP algorithm solve 77% and 58% of the test problems at approximately τ=3.3 and τ=4, respectively. From Tables 2–4 and Figures 1–3, it is obvious that the performance of the PRPFR algorithm is better than that of the FR algorithm and the modified PRP algorithm for most problems. Therefore, we conclude that the PRPFR algorithm is competitive to the FR algorithm and the modified PRP algorithm.Figure 1
Performance profiles of the methods (NI).Figure 2
Performance profiles of the methods (NF).Figure 3
Performance profiles of the methods (CPU).Table 5
CPU times of the PRPFR algorithm and the modified PRP algorithm in seconds.
20% noiseLenaBarbaraManTotalPRPFR algorithm2.7193.57812.84419.141Modified PRP algorithm3.2814.56313.12520.96945% noiseLenaBarbaraManTotalPRPFR algorithm5.6727.17229.96942.813Modified PRP algorithm6.1567.79731.60945.56370% noiseLenaBarbaraManTotalPRPFR algorithm14.06317.39161.90693.359Modified PRP algorithm17.07818.79762.45398.328


## 4.2. Image Restoration Problems

Image restoration aims to recover the original image from an image damaged by impulse noise. These problems are significant in optimization fields. The stop rule isFk+1−Fk/Fk<10−3 or xk+1−xk/xk<10−3. The experiments choose Lena (512×512), Barbara (512×512), and Man (1024×1024) as the test images. Meanwhile, we compare the PRPFR algorithm experiments’ performance with that of the modified PRP algorithm, where the step size αk is generated by Step 2 and Step 3 in the PRPFR algorithm. The detailed performance results are shown in Figures 4–6. It can be observed that both the PRPFR algorithm and the modified PRP algorithm are able to restore the blur image of these three images.Figure 4
From left to right: a noisy image with20% salt-and-pepper noise and the restorations obtained with the PRPFR algorithm and the modified PRP algorithm.Figure 5
From left to right: a noisy image with45% salt-and-pepper noise and the restorations obtained with the PRPFR algorithm and the modified PRP algorithm.Figure 6
From left to right: a noisy image with70% salt-and-pepper noise and the restorations obtained with the PRPFR algorithm and the modified PRP algorithm.From Figures4–6, we can easily notice that both algorithms are successful for restoring these noisy images with 20%, 45%, and 70% noise. According to the results in Table 5, we can draw the conclusion that the PRPFR algorithm is more effective than the modified PRP algorithm for 20% noise problems, 45% noise problems, and 70% noise problems.


## 5. Conclusion

In this paper, a new hybrid conjugate gradient algorithm that combines the PRP and FR methods is proposed, while using the projection technique. The directiondk has the sufficient descent and trust region properties automatically. Global convergence of the proposed algorithm is established under appropriate assumptions. The numerical experiments show that the proposed algorithm is competitive and efficient for solving nonlinear equations and image restoration problems.For further research, we have some thinking as follows: (i) If the convex combination is applied to the quasi-Newton method, can it have better properties? (ii) Under other line search techniques, can this conjugate gradient method have global convergence? (iii) Can the proposed algorithm be applied to compressive sensing?



---

*Source: 6391321-2020-09-25.xml*