# An Accelerated Conjugate Gradient Algorithm for Solving Nonlinear Monotone Equations and Image Restoration Problems

Authors: Haishan Feng; Tingting Li
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Combining the three-term conjugate gradient method of Yuan and Zhang and the acceleration step length of Andrei with the hyperplane projection method of Solodov and Svaiter, we propose an accelerated conjugate gradient algorithm for solving nonlinear monotone equations in this paper. The presented algorithm has the following properties: (i) All search directions generated by the algorithm satisfy the sufficient descent and trust region properties independent of the line search technique. (ii) A derivative-free search technique is proposed along the direction to obtain the step lengthαk. (iii) If ϕk=−αkhk−hwkTdk>0, then an acceleration scheme is used to modify the step length in a multiplicative manner and create a point. (iv) If the point satisfies the given condition, then it is the next point; otherwise, the hyperplane projection technique is used to obtain the next point. (v) The global convergence of the proposed algorithm is established under some suitable conditions. Numerical comparisons with other conjugate gradient algorithms show that the accelerated computing scheme is more competitive. In addition, the presented algorithm can also be applied to image restoration.


---

## Body

## 1. Introduction

In this paper, the following nonlinear equation is considered:(1)hx=0,subject tox∈ℜn,where h:ℜn⟶ℜn is continuous and monotone, and hx satisfies(2)hx−hyTx−y≥0,∀x,y∈ℜn.It is not difficult to show that the solution set of monotone equation (1), unless empty, is convex. This problem has many significant applications in applied mathematics, economics, and engineering. For example, the economic equilibrium problem [1] can be transformed into problem (1). Generally, an iteration formula generates the next iteration point by(3)xk+1=xk+αkdk,where αk is the step length and dk is a search direction, which are two important factors for solving nonlinear equations. Some derivative-free line search techniques [2–5] were proposed to search for step length αk. Li and Li [6] presented a derivative-free line search to find αk=maxρsi:i=0,1,…, such that(4)−hxk+αkdkTdk≥λαkhxk+αkdkdk2,where ρ,λ>0 and s∈0,1. . represents the Euclidean norm. The line search technique (4) is different from other existing derivative-free line search techniques because it does not use a merit function. If dk satisfies hxkTdk<0, the inequality (4) holds for all sufficiently small αk>0. As a result, αk can be obtained by some backtracking processes.Fordk, it is well known that the Newton methods [7, 8], quasi-Newton methods [9–13], spectral gradient methods [14, 15], and conjugate gradient methods [16, 17] can deal with large-scale nonlinear equations. For solving large-scale optimization problems, the conjugate gradient methods are quite effective since they only calculate and store the gradient value of the objective function. Many scholars have applied conjugate gradient theory to solve nonlinear monotone equations and have achieved good results [17–19]. Classical conjugate gradient methods include HS method [20], FR method [21], PRP method [22, 23], LS method [24], CD method [25], and DY method [26]. In particular, the PRP method, as one of the most effective methods, generates a small step near a minimum point; then, the subsequence generated for the search direction dk will automatically approach the negative gradient direction, which avoids continuously generating a small step. However, the global convergence of the PRP method is not established under inexact line search techniques for general functions. Many scholars have performed continuous research and have reached satisfactory conclusions. Zhang [27] proposed the MPRP method, where dk is designed as follows:(5)dk=−hk+βkPRPdk−1−θkyk,ifk≥1,−hk,ifk=0,where hxk=hk, hxk−1=hk−1, yk=hk−hk−1, βkPRP=hkTyk/hk−12, and θk=hkTdk−1/hk−12. It is easy to obtain from (5) that(6)dkThk=−hk2.The above equation indicates thatdk is a descent direction of h at xk. If the exact line search is used, then we have θk=0. Consequently, formula (5) is inferred to be the standard PRP method. Under some mild conditions, the MPRP method is globally convergent under the Armijo-type line search, but global convergence cannot be established under the weak Wolfe–Powell line search. The main reason is that the MPRP method does not satisfy the trust region property. Inspired by the above discussions, Yuan and Zhang [28] proposed a three-term PRP (TTPRP) method in which dk is defined by(7)dk=−hk+hkTykdk−1−hkTdk−1ykmaxκdk−1yk,hk−12,ifk≥1,−hk,ifk=0,where κ>0 is a constant. It is worth noting that the denominator hk−12 in the formula of the MPRP method is adjusted to maxκdk−1yk,hk−12 in the formula of the TTPRP method. The TTPRP method automatically maintains the trust region property. Its global convergence is also established under certain conditions. Numerical results show that the TTPRP method is effective for large-scale nonlinear monotone equations.In addition, the hyperplane projection method [17, 29–32] is the most effective method for solving large-scale nonlinear monotone equations. The concept of projection was first proposed by Goldstein [33] for convex programming in a Hilbert space. Furthermore, Solodov and Svaiter [34] proposed the hyperplane projection method for solving optimization problems. The specific process of the hyperplane projection method is as follows: let xk be the current iteration point, and obtain a point wk=xk+αkdk along a certain line search direction dk such that hwkTxk−wk>0. Due to the monotonicity of hx, for a certain point x¯ that satisfies hx¯=0, it can be deduced that(8)hwkTx¯−wk≤0.Obviously, the hyperplaneHk=x∈ℜnhwk,x−wk=0 strictly separates the current iteration point xk from the solution set of the equation (1). The point xk is projected onto the hyperplane Hk to obtain the next iteration point xk+1, i.e.,(9)xk+1=xk−hwkTxk−wkhwk2hwk.The hyperplane projection method has been proved to possess good theoretical properties and numerical performance for nonlinear monotone equations [6, 34].Furthermore, we know that the search directions tend to be poorly scaled in conjugate gradient methods. Consequently, in the line search, more function evaluations must be carried out to obtain an appropriate step lengthαk. Andrei [35] presented an acceleration scheme that modifies the step length αk in a multiplicative manner to improve the reduction of the function values along the iterations. The step length is defined as follows:(10)α˜k=ξkαk,where ξk=−φk/ϕk. φk=αkhkTdk, ϕk=−αkhk−hwkTdk. If ϕk>0, let αk=α˜k. A numerical comparison with some conjugate gradient algorithms shows that the computational scheme is effective.Inspired by the above discussions, we proposed an accelerated conjugate gradient algorithm that combines the TTPRP method, the acceleration step length, and the hyperplane projection method. The main contributions of the algorithm are as follows:An accelerated conjugate gradient algorithm is introduced for solving nonlinear monotone equationsAll search directions of the algorithm satisfy the sufficient descent conditionAll search directions of the algorithm belong to a trust regionThe global convergence of the presented algorithm is provedThe numerical results show that the proposed algorithm is more effective for nonlinear monotone equationsThe algorithm can be applied to restore an original image from an image damaged by impulse noiseThis paper is organized as follows: in the next section, we discuss the ATTPRP algorithm and global convergence analysis. In Section3, we report the preliminary numerical experiments to show that the algorithm is efficient for nonlinear monotone equations and applicable to image restoration problems. In Section 4, the conclusion regarding the proposed algorithm is given.


## 2. Accelerated Algorithm and Convergence Analysis

In this section, we will propose an accelerated algorithm and prove its global convergence. The steps of the given algorithm are as follows.


### 2.1. Accelerated Three-Term PRP Conjugate Gradient (ATTPRP) Algorithm

Step 0: choose anyx0∈ℜn as the initial point and constants s∈0,1, ρ>0, λ>0, κ>0, and ε∈0,1, let k:=0.Step 1: stop ifhk≤ε. Otherwise, compute dk by using formula (5).Step 2: chooseαk satisfying the inequality (4).Step 3: ifϕk>0, then αk=α˜k.Step 4: let the next iterative value bewk=xk+αkdk.Step 5: ifhwk≤ε, stop and let xk+1=wk. Otherwise, determine xk+1 using formula (9).Step 6: letk:=k+1. Go to Step 1.The following lemma shows that the search directiondk designed by using formula (7) has not only the sufficient descent property but also the trust region property independent of the line search.Lemma 1.
dk is defined by using formula (7); then, we obtain(11)dkThk=−hk2,(12)hk≤dk≤1+2κhk.Proof.
Ifk=0, formulas (7) and (12) are obviously true. If k≥1, we obtain from formula (7) that(13)hkTdk=hkT−hk+hkTykdk−1−hkTdk−1ykmaxκdk−1yk,hk−12=−hk2+hkTykdk−1Thk−hkTdk−1ykThkmaxκdk−1yk,hk−12=−hk2.
In addition, by formula (7), we get dk≥hk and(14)dk=−hk+hkTykdk−1−hkTdk−1ykmaxκdk−1yk,hk−12≤hk+hkykdk−1+hkdk−1ykmaxκdk−1yk,hk−12≤hk+2hkykdkκdkyk=1+2κhk,where maxκdk−1yk,hk−12≥κdkyk. Then, the proof is completed.
The following assumption need to be established in order to study some properties of the ATTPRP algorithm:Assumption 1.
(i)
The solution set of the problem (1) is nonempty.(ii)
The functionhx is Lipschitz continuous on ℜn; that is, there exists a positive constant K satisfying(15)hx−hy≤Kx−y,∀x,y∈ℜn.Remark 1.
Assumption1(ii) implies that hk is bounded; then, there exists a constant φ such that(16)hk≤φ.
In the following paper, if not specifically stated, we always assume that the conditions in Assumption1 hold.Lemma 2.
Letxk and wk be generated by using the ATTPRP algorithm. The step length αk generated by the ATTPRP algorithm satisfies(17)αk≥minρ,sK+λhwk′hk2dk2,where wk′=xk+αk′dk and αk′=αks−1.Proof.
By line search (4), assuming αk≠ρ, let αk′≜αks−1, by the definition αk′, does not satisfy the line search (4). That is,(18)−hwk′Tdk<λαk′hwk′dk2.
Sincehx is Lipschitz continuous and by using formula (11), we have(19)hk2=−hkTdk=hwk′−hk−hwk′Tdk=hwk′−hkTdk−hwk′Tdk≤Kwk′−xkdk+λαk′hwk′dk2=Kαk′dk2+λαk′hwk′dk2=αk′K+λhwk′dk2=αks−1K+λhwk′dk2,namely,(20)αk≥sK+λhwk′hk2dk2.
This leads to the ideal inequality (17). The proof is completed.
The following lemma is similar to Lemma1 in the study of Solodov and Svaiter [34], which also holds for the ATTPRP algorithm. Therefore, we only state it as follows but omit its proof.Lemma 3.
Let the sequencexk be generated by using the ATTPRP algorithm. Suppose that x¯ is a solution of problem (1) with hx¯=0. We obtain(21)xk+1−x¯2≤xk−x¯2−xk+1−xk2.
In particular, the sequencexk is bounded, and(22)∑k=0∞xk+1−xk2<∞.Remark 2.
The above lemma reveals that the distance from the iterative points to the solution set of the problem (1) decreases along iterations. Otherwise, for any k, it is followed from formulas (9) and (4) that(23)xk+1−xk=hwkTxk−wkhwk=−αkhwkTdkhwk≥λαk2dk2.
Particularly, we obtain(24)limk⟶∞αkdk=0.
In the following part, the global convergence and the strong global convergence properties of the ATTPRP algorithm will be proven.Theorem 1.
Letxk be generated by using the ATTPRP algorithm. Then, we have(25)limk⟶∞infhk=0.Proof.
We will prove this theorem by contradiction. Supposing that the equation (25) does not hold, there exists a constant η>0 such that hk≥η holds for all k≥0. From formula (12), we have(26)dk≥hk≥η,∀k≥0.
According to Lemma3 and equation (24), the sequences xk and wk′ are bounded. By formulas (7) and (16), for all k≥1, we obtain(27)dk≤hk+hkTykdk−1−hkTdk−1ykmaxκdk−1yk,hk−12≤hk+hkykdk−1+hkdk−1ykmaxκdk−1yk,hk−12≤hk+hkykdk−1+hkdk−1ykhk−12≤φ+2φη−2Kxk−xk−1dk−1,where maxκdk−1yk,hk−12≥hk−12. Since xk+1−xk converges to zero, the last inequality shows that dk is bounded. By formulas (12) and (16), we obtain(28)dk≤M,where M=1+2/κφ. Thus, from the formulas (16) and (17), we obtain that(29)αkdk≥minρ,sK+λhwk′hk2dk2dk≥minρη,sη2K+λφM>0.
This contradicts with formula (24). Consequently, the proof is completed.
The following theorem indicates the strong global convergence of the ATTPRP algorithm, which is similar to Theorem1 in [6]. We also give a specific proof for convenience of understanding.Theorem 2.
Letxk be generated by using the ATTPRP algorithm. Then, the whole sequence xk converges to a solution of the problem (1).Proof.
Theorem1 shows that there exists a subsequence of xk converging to a solution x¯ of the problem (1). On the other side, it follows from Lemma 3 that the sequence xk+1−x¯ converges. Therefore, the whole sequence xk converges to x¯.


## 2.1. Accelerated Three-Term PRP Conjugate Gradient (ATTPRP) Algorithm

Step 0: choose anyx0∈ℜn as the initial point and constants s∈0,1, ρ>0, λ>0, κ>0, and ε∈0,1, let k:=0.Step 1: stop ifhk≤ε. Otherwise, compute dk by using formula (5).Step 2: chooseαk satisfying the inequality (4).Step 3: ifϕk>0, then αk=α˜k.Step 4: let the next iterative value bewk=xk+αkdk.Step 5: ifhwk≤ε, stop and let xk+1=wk. Otherwise, determine xk+1 using formula (9).Step 6: letk:=k+1. Go to Step 1.The following lemma shows that the search directiondk designed by using formula (7) has not only the sufficient descent property but also the trust region property independent of the line search.Lemma 1.
dk is defined by using formula (7); then, we obtain(11)dkThk=−hk2,(12)hk≤dk≤1+2κhk.Proof.
Ifk=0, formulas (7) and (12) are obviously true. If k≥1, we obtain from formula (7) that(13)hkTdk=hkT−hk+hkTykdk−1−hkTdk−1ykmaxκdk−1yk,hk−12=−hk2+hkTykdk−1Thk−hkTdk−1ykThkmaxκdk−1yk,hk−12=−hk2.
In addition, by formula (7), we get dk≥hk and(14)dk=−hk+hkTykdk−1−hkTdk−1ykmaxκdk−1yk,hk−12≤hk+hkykdk−1+hkdk−1ykmaxκdk−1yk,hk−12≤hk+2hkykdkκdkyk=1+2κhk,where maxκdk−1yk,hk−12≥κdkyk. Then, the proof is completed.
The following assumption need to be established in order to study some properties of the ATTPRP algorithm:Assumption 1.
(i)
The solution set of the problem (1) is nonempty.(ii)
The functionhx is Lipschitz continuous on ℜn; that is, there exists a positive constant K satisfying(15)hx−hy≤Kx−y,∀x,y∈ℜn.Remark 1.
Assumption1(ii) implies that hk is bounded; then, there exists a constant φ such that(16)hk≤φ.
In the following paper, if not specifically stated, we always assume that the conditions in Assumption1 hold.Lemma 2.
Letxk and wk be generated by using the ATTPRP algorithm. The step length αk generated by the ATTPRP algorithm satisfies(17)αk≥minρ,sK+λhwk′hk2dk2,where wk′=xk+αk′dk and αk′=αks−1.Proof.
By line search (4), assuming αk≠ρ, let αk′≜αks−1, by the definition αk′, does not satisfy the line search (4). That is,(18)−hwk′Tdk<λαk′hwk′dk2.
Sincehx is Lipschitz continuous and by using formula (11), we have(19)hk2=−hkTdk=hwk′−hk−hwk′Tdk=hwk′−hkTdk−hwk′Tdk≤Kwk′−xkdk+λαk′hwk′dk2=Kαk′dk2+λαk′hwk′dk2=αk′K+λhwk′dk2=αks−1K+λhwk′dk2,namely,(20)αk≥sK+λhwk′hk2dk2.
This leads to the ideal inequality (17). The proof is completed.
The following lemma is similar to Lemma1 in the study of Solodov and Svaiter [34], which also holds for the ATTPRP algorithm. Therefore, we only state it as follows but omit its proof.Lemma 3.
Let the sequencexk be generated by using the ATTPRP algorithm. Suppose that x¯ is a solution of problem (1) with hx¯=0. We obtain(21)xk+1−x¯2≤xk−x¯2−xk+1−xk2.
In particular, the sequencexk is bounded, and(22)∑k=0∞xk+1−xk2<∞.Remark 2.
The above lemma reveals that the distance from the iterative points to the solution set of the problem (1) decreases along iterations. Otherwise, for any k, it is followed from formulas (9) and (4) that(23)xk+1−xk=hwkTxk−wkhwk=−αkhwkTdkhwk≥λαk2dk2.
Particularly, we obtain(24)limk⟶∞αkdk=0.
In the following part, the global convergence and the strong global convergence properties of the ATTPRP algorithm will be proven.Theorem 1.
Letxk be generated by using the ATTPRP algorithm. Then, we have(25)limk⟶∞infhk=0.Proof.
We will prove this theorem by contradiction. Supposing that the equation (25) does not hold, there exists a constant η>0 such that hk≥η holds for all k≥0. From formula (12), we have(26)dk≥hk≥η,∀k≥0.
According to Lemma3 and equation (24), the sequences xk and wk′ are bounded. By formulas (7) and (16), for all k≥1, we obtain(27)dk≤hk+hkTykdk−1−hkTdk−1ykmaxκdk−1yk,hk−12≤hk+hkykdk−1+hkdk−1ykmaxκdk−1yk,hk−12≤hk+hkykdk−1+hkdk−1ykhk−12≤φ+2φη−2Kxk−xk−1dk−1,where maxκdk−1yk,hk−12≥hk−12. Since xk+1−xk converges to zero, the last inequality shows that dk is bounded. By formulas (12) and (16), we obtain(28)dk≤M,where M=1+2/κφ. Thus, from the formulas (16) and (17), we obtain that(29)αkdk≥minρ,sK+λhwk′hk2dk2dk≥minρη,sη2K+λφM>0.
This contradicts with formula (24). Consequently, the proof is completed.
The following theorem indicates the strong global convergence of the ATTPRP algorithm, which is similar to Theorem1 in [6]. We also give a specific proof for convenience of understanding.Theorem 2.
Letxk be generated by using the ATTPRP algorithm. Then, the whole sequence xk converges to a solution of the problem (1).Proof.
Theorem1 shows that there exists a subsequence of xk converging to a solution x¯ of the problem (1). On the other side, it follows from Lemma 3 that the sequence xk+1−x¯ converges. Therefore, the whole sequence xk converges to x¯.


## 3. Numerical Experiments

In this section, the numerical experiments will be divided into two parts for illustration. The first subsection involves normal nonlinear equations, and the second subsection describes image restoration problems. All tests in this section are coded in MATLAB R2017a, run on a PC with Intel (R) Core (TM) i5-4460 3.20 GHz, 8.00 GB of SDRAM memory, and Windows 7 operating system.


### 3.1. Normal Nonlinear Equations

In this subsection, we perform some numerical experiments to show the effectiveness of the ATTPRP algorithm. Some test problems and their relevant initial points are listed as follows:(30)hx=f1x,f2x,…,fnxT.Function 1.
ExponentialFunction 1:(31)f1x=ex1−1−1,fix=iexi−1−xi,i=2,3,…,n.
Initial guess:x0=n/n−1,n/n−1,…,n/n−1t.Function 2.
ExponentialFunction 2:(32)f1x=ex1−1,fix=iexi+xi−1−110,i=2,3,…,n.
Initial guess:x0=1/n2,1/n2,…,1/n2t.Function 3.
Singular function:(33)f1x=x133+x222,fix=−xi22+i3xi3+xi+122,i=2,3,…,n−1,fnx=−xn22+n3xn3.
Initial guess:x0=1,1,…,1t.Function 4.
Logarithmic function:(34)fix=lnxi+1−xin,i=1,2,…,n.
Initial guess:x0=1,1,…,1t.Function 5.
Broyden tridiagonal function:(35)f1x=3−0.5x1x1−2x2+1,fix=3−0.5xixi−xi−1−2xi+1+1,i=2,3,…,n−1,fnx=3−0.5xnxn−xn−1+1.
Initial guess:x0=−1,−1,…,−1t.Function 6.
Trigexp function:(36)f1x=3x13+2x2−5+sinx1−x2sinx1+x2,fix=−xi−1exi−1−xi+xi4+3xi2+2xi+1+sinxi−xi+1sinxi+xi+1−8,i=2,3,…,n−1,fnx=−xn−1exn−1−xn+4xn−3.
Initial guess:x0=0,0,…,0t.Function 7.
Strictly convexFunction 1:hx is the gradient of fx=∑i=1nexi−xi.(37)fix=exi−1,i=1,2,…,n.
Initial guess:x0=1/n,2/n,…,1t.Function 8.
Variable dimensioned function:(38)fix=xi−1,i=1,2,…,n−2,fn−1x=∑j=1n−2jxj−1,fnx=∑j=1n−2jxj−12.
Initial guess:x0=1−1/n,1−2/n,…,0t.Function 9.
Tridiagonal system:(39)f1x=4x1−x22,fix=8xixi2−xi−1−21−xi+4xi−xi+12,i=2,…,n−1,fnx=8xnxn2−xn−1−21−xn.
Initial guess:x0=12,…,12t.Function 10.
Five-diagonal system:(40)f1x=4x1−x22+x2−x32,f2x=8x2x22−x1−21−x2+4x2−x32+x3−x42,fix=8xixi2−xi−1−21−xi+4xi−xi+12+xi−12−xi−2+xi+1−xi+22,i=3,…,n−2,fn−1x=8xn−1xn−12−xn−2−21−xn−1+4xn−1−xn2+xn−22−xn−3,fnx=8xnxn2−xn−1−21−xn+xn−12−xn−2.
Initial guess:x0=−2,…,−2t.Function 11.
Extended Freudenstein and Roth function (n is even):
Fori = 1, 2, …n/2,(41)f2i−1x=x2i−1+5−x2ix2i−2x2i−13,f2ix=x2i−1+x2i+1x2i−14x2i−29.
Initial guess:x0=6,3,6,3,…,6,3t.Function 12.
Brent problem:(42)f1x=3x1x2−2x1+x22/4,fix=3xixi+1−2xi+xi−1+xi+1−xi−12/4,fori=2,…,n−1,fnx=3xn20−2xn+xn−1+20−xn−12/4.
Initial guess:x0=0,…,0,20,20t.
To test the numerical performances of the ATTPRP algorithm, we also perform the experiments with the LS algorithm and the TTPRP algorithm. The columns of Tables1–3 have the following meanings:NO: the serial number of the problemDim: the variablex dimensionsNI: the number of iterationsNF: the number of iterations of the function valueCPU: the calculation time in secondsGN: the final function norm evaluations when the program is stoppedInitialization: the parameters are chosen asρ=1, s=0.69, λ=0.925, κ=0.0001, and ϵ=10−5Stop rule: when the conditionhx≤10−5 or NI ≥20000 is satisfied, we stop the process
From Tables1–3, it is obvious that the three methods can successfully solve most of the test problems with NI<20000. However, for Function 3 with 9000 and 90000 variables, the TTPRP and LS algorithms cannot handle the function, but the proposed algorithm can do with NI <20000. To more directly show the methods’ performance, Dolan and Moré [36] proposed a drawing tool that can obtain the performance profiles of methods. Therefore, using the drawing tool, we obtain Figures 1–3, which are related to the NI, NF, and CPU in Tables 1–3. In Figure 1, the ATTPRP algorithm solves all test problems at approximately τ=1.8, while the LS algorithm solves 80% of the test problems at approximately τ=1.88, and the TTPRP algorithm solves 92% at approximately τ=19. Thus, we can obtain the result that the ATTPRP algorithm performs slightly better than the other two algorithms. When τ=1.45 in Figure 2, the presented algorithm solves all test problems, the TTPRP algorithm solves 87% of all test problems, and the LS algorithm only solves approximately 70% of the test problems. Thus, it is not difficult to see that the ATTPRP algorithm is more competitive than the other two methods. In Figure 3, the curve of the ATTPRP algorithm is above those of the TTPRP and LS algorithms, which indicates that the proposed algorithm is more robust than the other two algorithms in terms of the CPU. In summary, the enhancement of the presented method is noticeable.Table 1
Test results of the ATTPRP algorithm.
No.DimATTPRP algorithmNI/NFCPUGN13000123/1240.6084049.97E−06900088/890.7332059.86E−063000057/581.0920079.96E−069000038/391.3104089.85E−062300028/5140.6864049.50E−06900018/3861.3728099.22E−063000015/3713.4320229.83E−069000010/2763.9468259.95E−063300014016/20709107.1726871.00E−05900015769/23986331.1589239.99E−063000015609/27514574.099281.00E−059000017136/352081503.0228351.00E−054300063/5581.0296075.24E−079000106/10965.2416348.39E−0730000195/233724.2581551.20E−0790000336/452188.0313642.21E−085300090/6150.7800058.52E−06900096/7592.4648167.76E−0630000130/119411.1540728.62E−0690000176/198429.2501888.82E−066300091/12231.9188128.09E−069000136/20938.8452579.86E−0630000221/390538.2826459.97E−0690000379/7177125.8148079.33E−067300048/3350.4680039.66E−06900071/6362.4804168.57E−0630000122/133913.1352849.31E−0690000203/256243.633488.53E−06830001/20.0000010.00E + 0090001/20.04680.00E + 00300001/20.0000010.00E + 00900001/20.01560.00E + 00930006014/88059100.8858479.93E − 0690006437/103883312.3452029.91E − 06300007345/1371421209.8033559.96E − 06900008950/1960122763.3861149.99E − 061030001811/1967025.6933659.99E − 0690001947/2255476.362499.82E − 06300002202/28399261.6448779.95E − 06900002638/38968577.9837051.00E − 05113000351/42055.3820349.78E − 069000409/519416.6453079.44E − 0630000510/713964.4752139.64E − 0690000683/10789161.3518349.52E − 06123000184/1880.1560019.98E − 069000184/1880.5772049.98E − 0630000184/1881.1076079.98E − 0690000184/1883.073229.98E − 06Table 2
Test results of the TTPRP algorithm.
No.DimTTPRP algorithmNI/NFCPUGN13000129/1300.4368039.97E − 06900089/900.8736069.96E − 063000059/601.2324089.96E − 069000041/421.4352099.73E − 062300046/10551.4352099.99E − 06900010/2670.9516066.76E − 06300009/2782.6676179.83E − 06900008/2794.0404269.00E − 063300017401/18908109.4815029.98E − 06900019999/23227355.0894761.37E − 053000019431/26598612.2415259.99E − 069000019999/344091542.6782892.56E − 054300070/6621.1232073.49E − 069000113/13266.0996392.14E − 0630000196/280928.7665846.47E − 0790000334/5473101.8842533.11E − 065300054/4640.5148033.38E − 06900072/7112.1528143.75E − 0630000100/122510.998077.38E − 0690000160/225631.4030015.61E − 066300084/14172.2464146.94E − 069000127/247310.3116669.41E − 0630000211/466945.3494918.60E − 0690000346/8524141.7737098.53E − 067300045/3660.5460032.67E − 06900068/7292.8080181.23E − 0630000117/155814.6172948.34E − 0790000195/303948.2199097.08E − 07830001/20.06240.00E + 0090001/20.0000010.00E + 00300001/20.06240.00E + 00900001/20.06240.00E + 00930006521/123863139.2776939.81E − 0690006827/141140425.6799299.97E − 06300007711/1822891559.9163999.99E − 06900009107/2511323460.3985829.85E − 061030004904/6531977.7508981.00E − 0590005271/71854229.8206739.73E − 06300005280/75948689.1500189.97E − 06900005655/881051269.3021379.99E − 06123000300/45294.8984319.88E − 069000387/616317.8465149.61E − 0630000472/839772.8368679.83E − 0690000620/12490168.6526819.27E − 06133000193/1980.1248019.99E − 069000193/1980.4056039.99E − 0630000193/1980.8268059.99E − 0690000193/1982.5896179.99E − 06Table 3
Test results of the LS algorithm.
No.DimLS algorithmNI/NFCPUGN13000174/1750.9828069.96E − 06900094/950.6708049.88E − 063000060/611.1076079.93E − 069000041/421.2480089.97E − 062300061/14051.7628119.85E − 06900034/9163.057629.98E − 063000015/4703.9468259.46E − 069000013/4566.8640449.12E − 063300019999/21506125.7212061.43E − 05900019999/23222351.2674521.44E − 053000019999/27153634.0036642.24E − 059000019999/343891582.9421471.76E − 054300075/6661.1856087.17E − 069000118/13316.240046.87E − 0630000202/281330.1861947.82E − 0690000338/546796.1590167.65E − 0653000136/11451.4040098.63E − 069000150/13584.3056289.81E − 0630000171/180616.8013085.69E − 0690000234/286542.089079.58E − 0663000109/16952.6988177.38E − 069000147/269411.2632728.98E − 0630000235/493447.5023058.67E − 0690000364/8724147.0621437.57E − 067300069/4000.5304036.22E − 06900094/7652.9484193.29E − 0630000142/159015.0852971.79E − 0690000217/307050.4507234.55E − 07830001/20.06240.00E + 0090001/20.0000010.00E + 00300001/20.04680.00E + 00900001/20.01560.00E + 00930005643/107964117.4843539.84E − 0690006131/128776373.9343979.86E − 06300006997/1695401461.3237679.99E − 06900008449/2395543276.1302019.88E − 061030004171/5582565.473629.93E − 0690004213/58137183.1139741.00E − 05300004616/67344608.7471029.88E − 06900004965/791661150.0081729.92E − 061130003484/4913252.0731349.92E − 069000371/592116.5049069.85E − 06300003625/52579454.7273159.93E − 06900003802/57077801.0495359.87E − 06123000194/1990.1092019.96E − 069000194/1990.4056039.96E − 0630000194/1990.9984069.96E − 0690000194/1992.7768189.96E − 06Figure 1
Performance profiles of the methods (NI).Figure 2
Performance profiles of the methods (NF).Figure 3
Performance profiles of the methods (CPU).


### 3.2. Image Restoration Problems

The purpose of this subsection is to recover the original image from an image damaged by impulse noise. It has important practical significance in optimization fields. The selection of parameters is similar to that in the above subsection. The stop condition ishk+1−hk/hk<10−3 or xk+1−xk/xk<10−3. For the experiments, Cameraman 256×256, Barbara 512×512, and Man 1024×1024 are chosen as the test images. We also perform experiments to compare the ATTPRP algorithm with the TTPRP algorithm, where the step length αk is generated by Step 2 and Step 3 in the ATTPRP algorithm. More detailed performance results are shown in Figures 4–6. It is not difficult to see that both the ATTPRP and TTPRP algorithms are successful in the image restoration of the three images. The expenditure of the CPU time is listed in Table 4 to compare the ATTPRP algorithm with the TTPRP algorithm.Figure 4
Restoration of the Cameraman, Barbara, and Man images by using the ATTPRP algorithm and TTPRP algorithm. From left to right: a noisy image with 30% salt-and-pepper noise and the restorations obtained with the ATTPRP algorithm and the TTPRP algorithm by minimizingz.Figure 5
Restoration of the Cameraman, Barbara, and Man images by using the ATTPRP algorithm and TTPRP algorithm. From left to right: a noisy image with 50% salt-and-pepper noise and the restorations obtained with the ATTPRP algorithm and TTPRP algorithm by minimizingz.Figure 6
Restoration of the Cameraman, Barbara, and Man images by using the ATTPRP algorithm and TTPRP algorithm. From left to right: a noisy image with 70% salt-and-pepper noise and the restorations obtained with the ATTPRP algorithm and TTPRP algorithm by minimizingz.Table 4
CPU times of the ATTPRP algorithm and TTPRP algorithm in seconds.
30% noiseCameramanBarbaraManTotalATTPRP algorithm2.1844.78920.51427.487TTPRP algorithm2.235.17920.74828.15750% noiseCameramanBarbaraManTotalATTPRP algorithm3.2769.14235.47547.893TTPRP algorithm3.3079.20435.67748.18870% noiseCameramanBarbaraManTotalATTPRP algorithm3.61913.07358.81275.504TTPRP algorithm3.97813.459.24976.627From Figures1–4, we can obviously note that both algorithms can perfectly restore a noisy image with 30%, 50%, and 70% salt-and-pepper noise. In addition, the results in Table 4 show that the ATTPRP algorithm and the TTPRP algorithm are both successful in restoring these images with an approximate CPU time. The presented algorithm is slightly competitive with the TTPRP algorithm for 30% noise problems, 50% noise problems, and 70% noise problems.


## 3.1. Normal Nonlinear Equations

In this subsection, we perform some numerical experiments to show the effectiveness of the ATTPRP algorithm. Some test problems and their relevant initial points are listed as follows:(30)hx=f1x,f2x,…,fnxT.Function 1.
ExponentialFunction 1:(31)f1x=ex1−1−1,fix=iexi−1−xi,i=2,3,…,n.
Initial guess:x0=n/n−1,n/n−1,…,n/n−1t.Function 2.
ExponentialFunction 2:(32)f1x=ex1−1,fix=iexi+xi−1−110,i=2,3,…,n.
Initial guess:x0=1/n2,1/n2,…,1/n2t.Function 3.
Singular function:(33)f1x=x133+x222,fix=−xi22+i3xi3+xi+122,i=2,3,…,n−1,fnx=−xn22+n3xn3.
Initial guess:x0=1,1,…,1t.Function 4.
Logarithmic function:(34)fix=lnxi+1−xin,i=1,2,…,n.
Initial guess:x0=1,1,…,1t.Function 5.
Broyden tridiagonal function:(35)f1x=3−0.5x1x1−2x2+1,fix=3−0.5xixi−xi−1−2xi+1+1,i=2,3,…,n−1,fnx=3−0.5xnxn−xn−1+1.
Initial guess:x0=−1,−1,…,−1t.Function 6.
Trigexp function:(36)f1x=3x13+2x2−5+sinx1−x2sinx1+x2,fix=−xi−1exi−1−xi+xi4+3xi2+2xi+1+sinxi−xi+1sinxi+xi+1−8,i=2,3,…,n−1,fnx=−xn−1exn−1−xn+4xn−3.
Initial guess:x0=0,0,…,0t.Function 7.
Strictly convexFunction 1:hx is the gradient of fx=∑i=1nexi−xi.(37)fix=exi−1,i=1,2,…,n.
Initial guess:x0=1/n,2/n,…,1t.Function 8.
Variable dimensioned function:(38)fix=xi−1,i=1,2,…,n−2,fn−1x=∑j=1n−2jxj−1,fnx=∑j=1n−2jxj−12.
Initial guess:x0=1−1/n,1−2/n,…,0t.Function 9.
Tridiagonal system:(39)f1x=4x1−x22,fix=8xixi2−xi−1−21−xi+4xi−xi+12,i=2,…,n−1,fnx=8xnxn2−xn−1−21−xn.
Initial guess:x0=12,…,12t.Function 10.
Five-diagonal system:(40)f1x=4x1−x22+x2−x32,f2x=8x2x22−x1−21−x2+4x2−x32+x3−x42,fix=8xixi2−xi−1−21−xi+4xi−xi+12+xi−12−xi−2+xi+1−xi+22,i=3,…,n−2,fn−1x=8xn−1xn−12−xn−2−21−xn−1+4xn−1−xn2+xn−22−xn−3,fnx=8xnxn2−xn−1−21−xn+xn−12−xn−2.
Initial guess:x0=−2,…,−2t.Function 11.
Extended Freudenstein and Roth function (n is even):
Fori = 1, 2, …n/2,(41)f2i−1x=x2i−1+5−x2ix2i−2x2i−13,f2ix=x2i−1+x2i+1x2i−14x2i−29.
Initial guess:x0=6,3,6,3,…,6,3t.Function 12.
Brent problem:(42)f1x=3x1x2−2x1+x22/4,fix=3xixi+1−2xi+xi−1+xi+1−xi−12/4,fori=2,…,n−1,fnx=3xn20−2xn+xn−1+20−xn−12/4.
Initial guess:x0=0,…,0,20,20t.
To test the numerical performances of the ATTPRP algorithm, we also perform the experiments with the LS algorithm and the TTPRP algorithm. The columns of Tables1–3 have the following meanings:NO: the serial number of the problemDim: the variablex dimensionsNI: the number of iterationsNF: the number of iterations of the function valueCPU: the calculation time in secondsGN: the final function norm evaluations when the program is stoppedInitialization: the parameters are chosen asρ=1, s=0.69, λ=0.925, κ=0.0001, and ϵ=10−5Stop rule: when the conditionhx≤10−5 or NI ≥20000 is satisfied, we stop the process
From Tables1–3, it is obvious that the three methods can successfully solve most of the test problems with NI<20000. However, for Function 3 with 9000 and 90000 variables, the TTPRP and LS algorithms cannot handle the function, but the proposed algorithm can do with NI <20000. To more directly show the methods’ performance, Dolan and Moré [36] proposed a drawing tool that can obtain the performance profiles of methods. Therefore, using the drawing tool, we obtain Figures 1–3, which are related to the NI, NF, and CPU in Tables 1–3. In Figure 1, the ATTPRP algorithm solves all test problems at approximately τ=1.8, while the LS algorithm solves 80% of the test problems at approximately τ=1.88, and the TTPRP algorithm solves 92% at approximately τ=19. Thus, we can obtain the result that the ATTPRP algorithm performs slightly better than the other two algorithms. When τ=1.45 in Figure 2, the presented algorithm solves all test problems, the TTPRP algorithm solves 87% of all test problems, and the LS algorithm only solves approximately 70% of the test problems. Thus, it is not difficult to see that the ATTPRP algorithm is more competitive than the other two methods. In Figure 3, the curve of the ATTPRP algorithm is above those of the TTPRP and LS algorithms, which indicates that the proposed algorithm is more robust than the other two algorithms in terms of the CPU. In summary, the enhancement of the presented method is noticeable.Table 1
Test results of the ATTPRP algorithm.
No.DimATTPRP algorithmNI/NFCPUGN13000123/1240.6084049.97E−06900088/890.7332059.86E−063000057/581.0920079.96E−069000038/391.3104089.85E−062300028/5140.6864049.50E−06900018/3861.3728099.22E−063000015/3713.4320229.83E−069000010/2763.9468259.95E−063300014016/20709107.1726871.00E−05900015769/23986331.1589239.99E−063000015609/27514574.099281.00E−059000017136/352081503.0228351.00E−054300063/5581.0296075.24E−079000106/10965.2416348.39E−0730000195/233724.2581551.20E−0790000336/452188.0313642.21E−085300090/6150.7800058.52E−06900096/7592.4648167.76E−0630000130/119411.1540728.62E−0690000176/198429.2501888.82E−066300091/12231.9188128.09E−069000136/20938.8452579.86E−0630000221/390538.2826459.97E−0690000379/7177125.8148079.33E−067300048/3350.4680039.66E−06900071/6362.4804168.57E−0630000122/133913.1352849.31E−0690000203/256243.633488.53E−06830001/20.0000010.00E + 0090001/20.04680.00E + 00300001/20.0000010.00E + 00900001/20.01560.00E + 00930006014/88059100.8858479.93E − 0690006437/103883312.3452029.91E − 06300007345/1371421209.8033559.96E − 06900008950/1960122763.3861149.99E − 061030001811/1967025.6933659.99E − 0690001947/2255476.362499.82E − 06300002202/28399261.6448779.95E − 06900002638/38968577.9837051.00E − 05113000351/42055.3820349.78E − 069000409/519416.6453079.44E − 0630000510/713964.4752139.64E − 0690000683/10789161.3518349.52E − 06123000184/1880.1560019.98E − 069000184/1880.5772049.98E − 0630000184/1881.1076079.98E − 0690000184/1883.073229.98E − 06Table 2
Test results of the TTPRP algorithm.
No.DimTTPRP algorithmNI/NFCPUGN13000129/1300.4368039.97E − 06900089/900.8736069.96E − 063000059/601.2324089.96E − 069000041/421.4352099.73E − 062300046/10551.4352099.99E − 06900010/2670.9516066.76E − 06300009/2782.6676179.83E − 06900008/2794.0404269.00E − 063300017401/18908109.4815029.98E − 06900019999/23227355.0894761.37E − 053000019431/26598612.2415259.99E − 069000019999/344091542.6782892.56E − 054300070/6621.1232073.49E − 069000113/13266.0996392.14E − 0630000196/280928.7665846.47E − 0790000334/5473101.8842533.11E − 065300054/4640.5148033.38E − 06900072/7112.1528143.75E − 0630000100/122510.998077.38E − 0690000160/225631.4030015.61E − 066300084/14172.2464146.94E − 069000127/247310.3116669.41E − 0630000211/466945.3494918.60E − 0690000346/8524141.7737098.53E − 067300045/3660.5460032.67E − 06900068/7292.8080181.23E − 0630000117/155814.6172948.34E − 0790000195/303948.2199097.08E − 07830001/20.06240.00E + 0090001/20.0000010.00E + 00300001/20.06240.00E + 00900001/20.06240.00E + 00930006521/123863139.2776939.81E − 0690006827/141140425.6799299.97E − 06300007711/1822891559.9163999.99E − 06900009107/2511323460.3985829.85E − 061030004904/6531977.7508981.00E − 0590005271/71854229.8206739.73E − 06300005280/75948689.1500189.97E − 06900005655/881051269.3021379.99E − 06123000300/45294.8984319.88E − 069000387/616317.8465149.61E − 0630000472/839772.8368679.83E − 0690000620/12490168.6526819.27E − 06133000193/1980.1248019.99E − 069000193/1980.4056039.99E − 0630000193/1980.8268059.99E − 0690000193/1982.5896179.99E − 06Table 3
Test results of the LS algorithm.
No.DimLS algorithmNI/NFCPUGN13000174/1750.9828069.96E − 06900094/950.6708049.88E − 063000060/611.1076079.93E − 069000041/421.2480089.97E − 062300061/14051.7628119.85E − 06900034/9163.057629.98E − 063000015/4703.9468259.46E − 069000013/4566.8640449.12E − 063300019999/21506125.7212061.43E − 05900019999/23222351.2674521.44E − 053000019999/27153634.0036642.24E − 059000019999/343891582.9421471.76E − 054300075/6661.1856087.17E − 069000118/13316.240046.87E − 0630000202/281330.1861947.82E − 0690000338/546796.1590167.65E − 0653000136/11451.4040098.63E − 069000150/13584.3056289.81E − 0630000171/180616.8013085.69E − 0690000234/286542.089079.58E − 0663000109/16952.6988177.38E − 069000147/269411.2632728.98E − 0630000235/493447.5023058.67E − 0690000364/8724147.0621437.57E − 067300069/4000.5304036.22E − 06900094/7652.9484193.29E − 0630000142/159015.0852971.79E − 0690000217/307050.4507234.55E − 07830001/20.06240.00E + 0090001/20.0000010.00E + 00300001/20.04680.00E + 00900001/20.01560.00E + 00930005643/107964117.4843539.84E − 0690006131/128776373.9343979.86E − 06300006997/1695401461.3237679.99E − 06900008449/2395543276.1302019.88E − 061030004171/5582565.473629.93E − 0690004213/58137183.1139741.00E − 05300004616/67344608.7471029.88E − 06900004965/791661150.0081729.92E − 061130003484/4913252.0731349.92E − 069000371/592116.5049069.85E − 06300003625/52579454.7273159.93E − 06900003802/57077801.0495359.87E − 06123000194/1990.1092019.96E − 069000194/1990.4056039.96E − 0630000194/1990.9984069.96E − 0690000194/1992.7768189.96E − 06Figure 1
Performance profiles of the methods (NI).Figure 2
Performance profiles of the methods (NF).Figure 3
Performance profiles of the methods (CPU).


## 3.2. Image Restoration Problems

The purpose of this subsection is to recover the original image from an image damaged by impulse noise. It has important practical significance in optimization fields. The selection of parameters is similar to that in the above subsection. The stop condition ishk+1−hk/hk<10−3 or xk+1−xk/xk<10−3. For the experiments, Cameraman 256×256, Barbara 512×512, and Man 1024×1024 are chosen as the test images. We also perform experiments to compare the ATTPRP algorithm with the TTPRP algorithm, where the step length αk is generated by Step 2 and Step 3 in the ATTPRP algorithm. More detailed performance results are shown in Figures 4–6. It is not difficult to see that both the ATTPRP and TTPRP algorithms are successful in the image restoration of the three images. The expenditure of the CPU time is listed in Table 4 to compare the ATTPRP algorithm with the TTPRP algorithm.Figure 4
Restoration of the Cameraman, Barbara, and Man images by using the ATTPRP algorithm and TTPRP algorithm. From left to right: a noisy image with 30% salt-and-pepper noise and the restorations obtained with the ATTPRP algorithm and the TTPRP algorithm by minimizingz.Figure 5
Restoration of the Cameraman, Barbara, and Man images by using the ATTPRP algorithm and TTPRP algorithm. From left to right: a noisy image with 50% salt-and-pepper noise and the restorations obtained with the ATTPRP algorithm and TTPRP algorithm by minimizingz.Figure 6
Restoration of the Cameraman, Barbara, and Man images by using the ATTPRP algorithm and TTPRP algorithm. From left to right: a noisy image with 70% salt-and-pepper noise and the restorations obtained with the ATTPRP algorithm and TTPRP algorithm by minimizingz.Table 4
CPU times of the ATTPRP algorithm and TTPRP algorithm in seconds.
30% noiseCameramanBarbaraManTotalATTPRP algorithm2.1844.78920.51427.487TTPRP algorithm2.235.17920.74828.15750% noiseCameramanBarbaraManTotalATTPRP algorithm3.2769.14235.47547.893TTPRP algorithm3.3079.20435.67748.18870% noiseCameramanBarbaraManTotalATTPRP algorithm3.61913.07358.81275.504TTPRP algorithm3.97813.459.24976.627From Figures1–4, we can obviously note that both algorithms can perfectly restore a noisy image with 30%, 50%, and 70% salt-and-pepper noise. In addition, the results in Table 4 show that the ATTPRP algorithm and the TTPRP algorithm are both successful in restoring these images with an approximate CPU time. The presented algorithm is slightly competitive with the TTPRP algorithm for 30% noise problems, 50% noise problems, and 70% noise problems.


## 4. Conclusions

In this paper, an accelerated conjugate gradient algorithm that combines the TTPRP method, the acceleration step length, and the hyperplane projection technique is proposed. All search directionsdk generated by using the algorithm automatically have sufficient descent and trust region properties. The global convergence property of the proposed algorithm is established under suitable conditions. The numerical results show that the proposed algorithm is effective. The image restoration problems also demonstrate that the proposed algorithm is successfulFor future research, we have some ideas as follows: (i) If the acceleration system is introduced into the quasi-Newton method, does it have some good properties? (ii) Can the acceleration system be introduced into the trust region method to solve unconstrained optimization problems and nonlinear equations? (iii) Can the proposed algorithm be applied to machine learning?



---

*Source: 7945467-2020-10-05.xml*