# A Family of Modified Spectral Projection Methods for Nonlinear Monotone Equations with Convex Constraint

Authors: Zhensheng Yu; Lin Li; Peixin Li
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

In this paper, we propose a family of modified spectral projection methods for nonlinear monotone equations with convex constraints, where the spectral parameter is mainly determined by a convex combination of the modified long Barzilai–Borwein stepsize and the modified short Barzilai–Borwein stepsize. We obtain a trial point by the spectral method and then get the iteration point by the projection technique. The algorithm can generate a bounded iterative sequence automatically, and we obtain the global convergence of the proposed method in the sense that every limit point is a solution of the nonlinear equation. The proposed method can be used to resolve the large-scale nonlinear monotone equations with convex constraints including smooth and nonsmooth equations. Numerical results for nonlinear equation problems and theℓ1-norm regularization problem in compressive sensing demonstrate the efficiency and efficacy of our method.


---

## Body

## 1. Introduction

In this paper, we consider the nonlinear monotone equations with constraints as follows:(1)Fx∗=0,x∗∈Ω,where F:Ω⟶Rn is continuous and monotone and Ω⊆Rn is a nonempty closed convex set. A mapping is called monotone if(2)Fx−Fy,x−y≥0,holds, and x,y=xTy denotes the inner product of x,y∈Rn. Problem (1) is derived from various practical problems such as subproblems in generalized proximal algorithms with Bregman distance [1], variational inequality problems [2], chemical equilibrium problems [3], power flow equations [4], and other engineering problems.During the last decades, many numerical approaches have been proposed to solve problem (1), such as Newton-based methods [1, 5–7], the derivative-free methods [8–14], and the gradient-based methods [15–24]. Due to their fast local convergence property [25, 26], the Newton-based methods as well as their variants are extremely popular for solving problem (1). However, Newton-based methods involve the calculation of a Jacobian matrix or an approximation Jacobian at each iteration, which will reduce their efficiency especially in solving large-scale problems.The first-order methods have received much attention in recent years due to their low storage requirement. One of the widely known first-order methods is the spectral gradient method, which was introduced by Barzilai and Borwein in [27] and was extended further by Raydan and La Cruz [15, 16, 28, 29]. Based on the inexact Newton method introduced by Solodov and Svaiter in [6], Zhang and Zhou studied the spectral gradient projection method for the unconstrained monotone equations in [30], and Yu et al. applied it to solve constrained monotone equations in [31], the reported numerical results indicating the excellent performance of these methods.Recently, Dai et al. [32] proposed a family of spectral gradient methods for unconstrained optimization, whose stepsize is determined by a convex combination of the long Barzilai–Borwein (BB) stepsize and the short BB stepsize, and the algorithm presents good numerical performance. The success of the combined method motivates us to extent the algorithm to constrained nonlinear equation problem. Since the constrained nonlinear equation is very different from the unconstrained optimization, our algorithm, without using any merit function, is also distinct from the algorithm in [32] and thus can be used to solve nonsmooth problems. Moreover, our algorithm can be seen as a family of modified spectral gradient projection methods for the nonlinear monotone equations with convex constraints, where the spectral parameter is mainly determined by a convex combination of the modified long BB stepsize and the modified short BB stepsize. We prove that the algorithm generates a bounded iterative sequence automatically and it converges globally in the sense that every limit point of the iterative sequence is a solution of the original problem. The numerical tests show the efficiency of the proposed algorithm.We notice that modified spectral gradient algorithms were proposed in [33, 34] for solving problem (1), but our algorithm is very different from theirs in the following aspects. Firstly, we give a changeable choice for the inexact parameter in the spectral method. Secondly, the relationship between the modified long and short BB stepsize is studied. Moreover, it has been shown that a suitable alteration of long stepsize and short stepsize is more effective than the respective deployment of each of them. We also present several cyclic strategies for the convex combination, which contributes to the efficiency of our algorithm.The remainder of this paper is organized as follows. In Section2, we propose the new algorithm, and some properties of the new method are also discussed. In Section 3, we prove the global convergence of the proposed method under appropriate assumptions. The numerical results are given in Section 4. Application of proposed algorithm in compressive sensing can be found in Section 5, and conclusions are provided in Section 6.


## 2. Algorithm

In this section, we will present a family of modified spectral gradient projection methods for solving (1).Firstly, we introduce the projection operator, which is defined as a mapping fromRn to a closed convex set Ω:(3)PΩν=argminνu−ν,u∈Ω,ν∈Rn,and it has been equipped with a distinct nonexpansive feature:(4)PΩu−PΩν≤u−ν,u,ν∈Rn.Next, we recall the idea of the spectral gradient method developed by Barzilai and Borwein [27] for unconstrained optimization:(5)minx∈Rnfx,where f is continuously differentiable with gradient g.Given anxk∈Rn, the next iteration point generated by the BB method is defined as follows: xk+1=xk−αkgk, sk−1=xk−xk−1, and yk−1=gk−gk−1, and we can get αk=⋅αkBB1 by minimizing αsk−1−yk−12 with(6)αkBB1=sk−1,sk−1sk−1,yk−1.By symmetry, we can also getαk=⋅αkBB2 by minimizing sk−1−αyk−12 with(7)αkBB2=sk−1,yk−1yk−1,yk−1.As described in [32], when sk−1,yk−1>0, αkBB1≥αkBB2 always holds, which means αkBB1 is the long BB stepsize and αkBB2 is the short one. Numerical experiments show that the long BB stepsize is superior to the short one, which can be seen in [35, 36]. But in practice, a suitable alternation of long BB stepsize and short BB stepsize works better than using them separately, which can be seen in numerical section.Moreover, we discuss some related problems about the modified long BB stepsize and short BB stepsize and then give the algorithm. Fork>1, given an rk−1>0, define y˜k−1=Fxk−Fxk−1+rk−1sk−1; the corresponding modified stepsizes are defined as follows:(8)α˜kBB1=sk−1,sk−1sk−1,y˜k−1,(9)α˜kBB2=sk−1,y˜k−1y˜k−1,y˜k−1.Ifrk−1=0, it reduces the classical spectral approach for nonlinear equations.Now, we discuss the relationship between the stepsizesαkBB1, αkBB2, α˜kBB1, and α˜kBB2. Note that(10)α˜kBB1=sk−1,sk−1sk−1,y˜k−1=sk−1,sk−1sk−1,yk−1+rk−1sk−1=sk−1,sk−1sk−1,yk−1+rk−1sk−1,sk−1,α˜kBB2=sk−1,y˜k−1y˜k−1,y˜k−1=sk−1,yk−1+rk−1sk−1yk−1+rk−1sk−1,yk−1+rk−1sk−1=sk−1,yk−1+rk−1sk−1,sk−1yk−1,yk−1+2rk−1sk−1,yk−1+rk−12sk−1,sk−1.Settingak−1=sk−1,sk−1, bk−1=sk−1,yk−1, and ck−1=yk−1,yk−1, consequently, we have (11)α˜kBB1=ak−1ak−1rk−1+bk−1,α˜kBB2=ak−1rk−1+bk−1ak−1rk−12+2bk−1rk−1+ck−1.On the one hand, by Cauchy–Schwarz inequalitysk−1,yk−12≤sk−12⋅yk−12, i.e., bk−12≤ak−1ck−1, we can deduce that α˜kBB1≥α˜kBB2. On the other hand, by the monotonicity of F, we have(12)sk−1,y˜k−1=sk−1,yk−1+rk−1sk−1=sk−1,yk−1+rk−1sk−1,sk−1≥sk−1,yk−1,which means αkBB1≥α˜kBB1.Next, we discuss the relationship betweenα˜kBB1 and αkBB2 by updating the parameter rk−1. Denote r^k−1=ak−1ck−1−2bk−12/ak−1bk−1; when rk−1⟶0+ or rk−1⟶r^k−1, then α˜kBB2⟶αkBB2. If r^k−1>0, we can choose rk−1∈0,r^k−1. In this case, we get α˜kBB2≥αkBB2. In fact, the maximum of α˜kBB2 can be worked out by setting(13)φrk−1≔ak−1rk−1+bk−1ak−1rk−12+2bk−1rk−1+ck−1,and we can deduce the extremum of φrk−1 at some point r^^k−1, so we choose parameter rk−1 according to the following rule:(14)rk−1=argmaxφr^k−1,φr^^k−1.However, ifr^k−1≤0, we set rk−1=r0 for a given positive constant. We can also get α˜kBB2≥αkBB2. In conclusion, we can obtain that(15)αkBB1≥α˜kBB1≥α˜kBB2≥αkBB2.Finally, we terminate this section by describing the specific algorithm, which can be viewed as a modified spectral gradient projection method, named as MSGP for short.Remark 1.
(1) In Step 5,y˜k−1 is different from the standard definition.
(2) If Algorithm1 terminates at a finite iteration k and Fxk=0, xk is the solution of (1). However, if Fxk≠0 for k≥1, Algorithm 1 generates an infinite sequence xk. So without loss of generality, we assume that the algorithm generates an infinite sequence.Algorithm 1:MSGP.
Step 0: choose an initial point x1∈Ω and parameters ξ>0, ρ∈0,1, σ∈0,1, α1=1, k=1, and λk=0,1.Step 1: if Fxk=0, then stop.Step 2: compute the search direction dk by dk=−αkFxk.Step 3: find the trial point zk=xk+θkdk, where θk=ξρmk with mk being the smallest non-negative integer m such that −Fxk+θkdkTdk≥σθkdk2.Step 4: compute xk+1=PΩxk−ζkFzk, where ζk=Fzk,xk−zk/Fzk2.Step 5: choose rk−1 and compute sk−1=xk−xk−1, sk−1=xk−xk−1, y˜k−1=Fxk−Fxk−1+rk−1sk−1, and then compute αk=λkα˜kBB1+1−λkα˜kBB2, where α˜kBB1 and α˜kBB2 are defined by (8) and (9).Step 6: set k:=k+1, and go to Step 1.


## 3. Convergence Analysis

To analyze the global convergence of the Algorithm1, we assume that Fx is Lipschitz continuous on the set Ω, i.e., there exists a positive constant L such that(16)Fx−Fy≤Lx−y,∀x,y∈Ω.The following lemmas state that Algorithm1 is well defined.Lemma 1.
Under the assumption listed above, there exists a non-negative numbermk satisfying Algorithm 1 for all k≥1.Proof.
We first give an estimation of the stepsizeαk. For α˜kBB1=sk−1,sk−1/sk−1,y˜k−1, by the monotonicity of Fx, we have that(17)sk−1,y˜k−1=sk−1,yk−1+rk−1sk−1,sk−1≥rk−1sk−1,sk−1.
On the one hand, by the Lipschitz continuity ofFx, we have(18)sk−1,y˜k−1≤L+rk−1sk−1,sk−1.
Hence,(19)1L+rk−1≤α˜kBB1≤1rk−1.
Forα˜kBB2=sk−1,y˜k−1/y˜k−1,y˜k−1, by (17), we get(20)α˜kBB2≥rk−1sk−1,sk−1y˜k−1,y˜k−1.
On the other hand, by the definition ofy˜k−1, we have(21)y˜k−1,y˜k−1=y˜k−1,yk−1+rk−1sk−1=y˜k−1,yk−1+rk−1y˜k−1,sk−1=yk−1+rk−1sk−1,yk−1+rk−1y˜k−1,sk−1=yk−12+rk−1sk−1,yk−1+rk−1y˜k−1,sk−1≤L2+Lrk−1+L+rk−1rk−1sk−1,sk−1=L+rk−12sk−1,sk−1.
Combining this together with (17), we can derive α˜kBB2≥rk−1/L+rk−12. So, by (19) and α˜kBB1≥α˜kBB2, we have(22)rk−1L+rk−12≤α˜kBB2≤1rk−1.
From the definition ofαk, we finally get(23)1L+rk−1≤αk≤1rk−1.
Now we prove the conclusion by contradiction; suppose that there existsk0≥1 such that Algorithm 1 is not satisfied for any non-negative integer m, i.e.,(24)−Fxk0+βmdk0,dk0<σβmdk02,∀m≥0.
Letm⟶∞; we have(25)−Fxk0,dk0≤0.
Nonetheless, by the definition ofdk and (23), we have(26)−Fxk0,dk0=αk0Fxk02≥1L+rk−1Fxk02>0.
This contradicts inequality (25), and hence we get the desired result.
Based on the conclusion of Lemma1, we can get the global convergence of the Algorithm 1.Theorem 1.
Suppose that the sequencesxk and zk are generated by Algorithm 1; then, xk and zk are both bounded and it holds that(27)limk⟶∞xk−zk=limk⟶∞xk+1−xk=0.
Furthermore, the sequencexk converges to some point x∗ such that(28)Fx∗=0.Proof.
We complete this proof from two aspects.
First of all, we give the proof of (27). For this purpose, we assume that the solution set of (1), denoted by S, is nonempty. From Algorithm 1, we have(29)Fzk,xk−zk=−θkFzk,dk≥σθk2dk2=σxk−zk2>0.
Letx∗∈S; from (4) and Algorithm 1, we have(30)xk+1−x∗2=PΩxk−ζkFzk−x∗2≤xk−ζkFzk−x∗2=xk−x∗2−2ζkFzk,xk−x∗+ζk2Fzk2.
By the monotonicity of mappingF and x∗∈S, it holds that(31)Fzk,xk−x∗=Fzk,xk−zk+Fzk,zk−x∗≥Fzk,xk−zk+Fx∗,zk−x∗=Fzk,xk−zk.
From (29)–(31) and Algorithm 1, we have(32)xk+1−x∗2≤xk−x∗2−2ζkFzk,xk−zk+ζk2Fzk2=xk−x∗2−Fzk,xk−zk2Fzk2≤xk−x∗2−σ2xk−zk4Fzk2.
Hence, the sequencexk−x∗ is decreasing and convergent; moreover, the sequence xk is bounded. Using the continuity of F, we know that there exists a constant M>0 such that(33)Fxk≤M,∀k≥1.
By the Cauchy–Schwarz inequality, the monotonicity ofF, and (29), one has(34)Fxk≥Fxk,xk−zkxk−zk≥Fzk,xk−zkxk−zk≥σxk−zk.
From (33) and (34), we obtain that the sequence zk is also bounded.
It follows from (32) and (33) that(35)σ2M2∑k=1∞xk−zk4≤∑k=1∞xk−x∗2−xk+1−x∗2<∞,which implies that(36)limk⟶∞xk−zk=0.
Sincexk∈Ω, using (4) and Algorithm 1 and Cauchy–Schwarz inequality, we obtain that(37)xk+1−xk=PΩxk−ζkFzk−xk≤xk−ζkFzk−xk=ζkFzk=Fzk,xk−zkFzk≤xk−zk.
Thus,(38)limk⟶∞xk+1−xk=0.
The remaining part is the proof of (28). Since zk=xk+θkdk, the following holds from (36) and (38):(39)limk⟶∞θkdk=limk⟶∞xk−zk=0.
From Algorithm1 and (23), we have(40)FxkL+rk−1≤dk≤Fxkrk−1,∀k>1.
By (33), it holds that dk is bounded. And we complete the following proof in two different cases.Case 1:(41)liminfk⟶∞dk=0.By (40), we obtain that(42)liminfk⟶∞Fxk=0.The continuity ofF implies that the sequence xk has some accumulation point x¯ such that Fx¯=0, i.e., x¯∈S. From (32), it holds that xk−x¯ converges, and since x¯ is an accumulation point of xk, it must hold that xk converges to x¯.Case 2:(43)liminfk⟶∞dk>0.From (40), we have(44)liminfk⟶∞Fxk>0.By (39), it holds that(45)limk⟶∞θk=0.From Algorithm1, we have(46)−Fxk+βmk−1dk,dk<σβmk−1dk2.Sincexk, dk are bounded, we can choose a subsequence; let k⟶∞ in (46), and we obtain that(47)−Fx¯,d¯≤0,wherex¯, d¯ are limit points of corresponding subsequence.On the other hand, letk⟶∞ in (26), and we have(48)−Fx¯,d¯>0,which contradicts (47). Hence,(49)liminfk⟶∞Fxk>0,is impossible. This completes the proof.


## 4. Preliminary Numerical Results

In order to observe the performance of the new algorithm, we first discuss the selection of convex combination coefficientsλk and make preparations for the numerical experiments.The simplest scheme is to fixλk for all iterations, i.e., select a constant within the interval 0,1 as the value of λk. Another approach is randomly choosing in the interval 0,1, known as randomly relaxed Cauchy method [37], but the information of the current and former iterations is not utilized. Moreover, numerous cyclic methods have shown that a suitable alternation of short stepsize and long stepsize works better than the separate use of each. For instance, an adaptive truncated cyclic (ATC) scheme is proposed by Dai et al. in [32], where(50)λk=argminλ∈0,1λα˜kBB1+1−λα˜kBB2−αk−1,which yields the following stepsize:(51)αk=α˜kBB2,ifαk−1≤α˜kBB2;α˜kBB1,ifαk−1≥α˜kBB1;αk−1,otherwise.There are three methods that emerged along with different cyclic schemes. The first one is ATC1, i.e.,(52)αkATC1=α˜kBB1,ifmodk,m=0;αk,otherwise.The second one is ATC2, i.e.,(53)αkATC2=α˜kBB2,ifmodk,m=0;αk,otherwise.The last one is ATC3, i.e.,(54)αkATC3=α˜kBB3,ifmodk,m=0;αk,otherwise,where αk is defined in (27) and α˜kBB3=α˜kBB1α˜kBB2=sk−1/y˜k−1. Furthermore, Dai proposed an alternate step method (AS) in [38] and used the steepest descent and the BB steps alternately. This motivates us to consider updating αk as follows:(55)λmk+i=1,i=1,…,m−1;0,i=m,which yields(56)αmk+i=α˜mk+iBB1,i=1,…,m−1;α˜mk+iBB2,i=m.For an in-depth study on the effect ofλk in different situations on the performance of the Algorithm 1, we use two classic examples to test these methods. For the fixed methods, we set λ = 0.1, 0.3, 0.618, and 0.9 for all k, respectively. For ATC and AS methods, we set parameter m=5. In particular, we set σ=0.01 and β=0.5 in Algorithm 1 and stopped the iterative process if Fxk≤10−6 or the number of iterations exceeded 1000. In all methods described here, we use MATLAB (v.9.6.0-R2019a) for the implementation. All codes were carried out on a PC with an Intel Core (TM) i5, 2.39 GHz processor and 4 G memory of RAM. We now list the test examples; the mapping F is taken as Fx=F1x,F2x,…,FnxT.Example 1.
This example originates from [31], i.e.,(57)Fix=xi−sinxi−1,where Ω=R+n and i=1,2,…,n.Example 2.
This example comes from [39], i.e.,(58)Fix=exi−1,where Ω=R+n and i=1,2,…,n.
Obviously, Example1 is nonsmooth and Example 2 is a strict convex function. For different initial points, x1=1,1,…,1T, x2=1/n,2/n,…,1T, and x3=1−1/n,1−2/n,…,0T. Table 1 gives the preliminary numerical results with dimensions from 100 to 10000. Note that Ei denotes experiment on the example i, where i=1,2. xj represents start point of the iteration, where j=1,2,3. In addition, A/B stands for number of iterations and CPU time in seconds. We observed that the noncyclic methods are superior to other methods in the number of iterations and CPU time when λk is very small. For the cyclic schemes, ATC2 is superior to other cyclic methods both in the number of iterations and execution time. Furthermore, we can get the conclusion that ATC2 dominates all methods both in the number of iterations and the elapsed time. Thus, we only apply ATC2 method to Algorithm 1 for the further experiment.
In the rest of this section, to evaluate the efficiency of Algorithm1 in solving nonlinear monotone equations with convex constraints, we compare the MSGP method with PDY method [11] and SGP method [31] through two aspects. So, we set different iteration starting points for each problem. Additionally, we increase the dimensions gradually to study the performance of the new method for large-scale problems.
In our method, we setσ=0.01, β=0.5, m=5, and r0=0.1. Moreover, we employ σ=0.01, β=0.5, and r=0.1 in the SGP method. With regard to the PDY method, we select the parameters ξ=1, ρ=0.5, c=1, and σ=0.01, respectively. In all algorithms, we stop the process when(59)Fxk≤10−6,or the total number of iterations exceeds 20000.
Some test problems are listed as follows. Problem1 is taken from [15], Problem 2 comes from [9], Problem 3 originates from [16], Problem 4 derives from [31], Problem 5 stems from [40], and Problem 6 is presented in [41].Table 1
Experiment results for updating value ofαk in different ways.
EixjDimλk = 0.1λk = 0.3λk = 0.6λk = 0.9RandATC1ATC2ATC3ASE1x110010/0.002517/0.001117/0.001017/0.001111/0.00105/0.00465/0.00065/0.002710/0.00121,00012/0.006718/0.003218/0.003618/0.002612/0.00226/0.00516/0.00146/0.003611/0.003610,00014/0.020120/0.024020/0.028920/0.019114/0.03217/0.00836/0.00587/0.012911/0.0127x210012/0.001821/0.001321/0.001121/0.001121/0.001121/0.00168/0.000521/0.002313/0.0014100014/0.002022/0.004523/0.003823/0.004023/0.002422/0.00378/0.001522/0.012914/0.00221000015/0.015124/0.021424/0.023225/0.025424/0.032724/0.02389/0.008524/0.029316/0.0141x310012/0.000821/0.001221/0.001321/0.001217/0.001121/0.00158/0.000321/0.002213/0.0014100014/0.003922/0.004523/0.010923/0.004719/0.002222/0.00448/0.001722/0.007714/0.00271000015/0.015424/0.020624/0.040825/0.027121/0.030824/0.02649/0.007824/0.022516/0.0168E2x110011/0.000916/0.001216/0.001816/0.001011/0.002016/0.00147/0.001116/0.001510/0.0010100012/0.003218/0.004018/0.004117/0.002412/0.002618/0.00607/0.001418/0.006711/0.00201000014/0.020720/0.033019/0.028819/0.028414/0.019620/0.02898/0.013120/0.028911/0.0165x21008/0.000514/0.000814/0.001115/0.001418/0.00279/0.00109/0.00079/0.000711/0.0007100012/0.002312/0.001714/0.002313/0.001819/0.00519/0.00159/0.00149/0.001711/0.00171000014/0.027815/0.017218/0.023220/0.029921/0.035310/0.011110/0.010210/0.019216/0.0176x310013/0.000913/0.001314/0.000914/0.000817/0.00108/0.00109/0.00068/0.000711/0.0009100012/0.002312/0.002314/0.002213/0.002019/0.00979/0.00179/0.00139/0.001811/0.00131000014/0.185615/0.034518/0.030720/0.054221/0.034110/0.012710/0.103210/0.025116/0.0377Problem 1.
This problem is logarithmic function withΩ=x∈Rn|xi>−1, i.e.,(60)Fix=lnxi+1−xin,where i=1,2,…,n and mapping F is taken as Fx=F1x,F2x,…,FnxT.Problem 2.
This problem is(61)Fix=2xi−sinxi,where i=1,2,…,n and Ω=x∈Rn|xi≥−2 and mapping F is taken as Fx=F1x,F2x,…,FnxT.Problem 3.
This problem is exponential function, i.e.,(62)F1x=ex1−1,Fix=exi+xi−1,where Ω=R+n and i=2,3,…,n.Problem 4.
This problem is a modification of Problem2 in [30].(63)Fix=lnxi−sinxi−2,where Ω=R+n and i=1,2,…,n, and this problem is nonsmooth at x=2.Problem 5.
LetF be defined by(64)Fx=Ax+b,with additional Ω=R+n, where b=−1,−2,…,−nT and(65)A=53253⋱⋱⋱⋱⋱325.Problem 6.
LetF be given by(66)Fx=Ax+gx,with additional Ω=R+n, where gx=ex1−1,ex2−1,…,exn−1T, and(67)A=2−1−12−1⋱⋱⋱⋱⋱−1−12.
We test the robustness of the methods in two ways; for Problems1–3, we compare the performance of algorithms at different initial points once the dimension of the test problem is selected. The results are shown in Tables 2–4, while start points are chosen as(68)x1=1,1,…,1T,x2=12,12,…,12T,x3=110,110,…,110T,x4=1n,2n,…,1T,x5=12,122,…,12nT,x6=1−12,1−122,…,1−12nT.
As for Problems4–6, we increase the dimensions of the problem gradually to test the performance of Algorithm 1 in addressing the large-scale problems. The results are reported in Tables 5–7 where the initial points are set as(69)x1=110,110,…,110T,x2=1,1,…,1T,x3=1n,2n,…,1T.
The detailed results are listed in Tables2–7, where the performance of the MGSP method, SGP method, and PDY method is compared with respect to the total number of iterations (Iter), the number of function evaluations (NF), CPU time in seconds (CPUtime), and the norm of objective function (Norm). Furthermore, Pii=1,2,…,6 denotes the test problem, and the dimension of the test problem is signified by Dim, respectively. We claim that the method fails, using the symbol (—), when the CPU time is greater than or equal to 10.
The performance of the three methods was evaluated using the performance profile which is presented by Dolan and Moré in [42]. We denote the set of methods as M and the set of experiments as E. We claim comparing three methods with the same dimension and start point as one experiment. For each problem, le,m denotes the number of iterations required to execute experiment e by approach m. And the performance ratio is defined as(70)re,m≔le,mminle,m|m∈M.
Obviously,re,m≥1 for all e∈E and m∈M. Furthermore, re,m=R where R is a large positive constant when method m does not solve experiment e, and re,m<R always holds for all e∈R and m∈M. If method m can solve experiment e successfully, we obtain an overall assessment of the performance between these solvers. It can be described as follows:(71)ρmτ≔1nesizee∈E|re,m≤τ,where ne represents the number of elements in set M, ρmτ can be viewed as the probability that method m is superior to the other methods in terms of the total number of iterations, and re,m is within a factor τ∈R of the best possible ratio. In the same way, we can obtain the performance profile with respect to CPU time and the number of function evaluations.
The performance profile of the MSGP method, SGP method, and PDY method is compared in the sense of the number of iterations, CPU time, and number of function evaluations, which are displayed in Figures1–3, respectively. An observation that emerges from Figure 1 is that the MSGP method performs much better than the PDY method and SGP method with respect to the number of iterations. Figure 2 reveals that the MSGP method is faster than the SGP method and PDY method in terms of CPU execution time. Moreover, we perceive that, in Figure 3, our method also precedes other methods with respect to the number of function evaluations. Furthermore, based on the analysis mentioned in the previous section and experiment results, our MSGP method outperforms the SGP method and PDY method in terms of total number of iterations, CPU time, and the number of function evaluations.Table 2
Numerical results for Problem1 with different initial points.
PiDimInitial pointsMSGP methodSGP methodPDY methodIter/NF/CPUtimeNormIter/NF/CPUtimeNormIter/NF/CPUtimeNormP11,000x19/29/0.00193.85E − 0710/38/0.00352.93E − 0714/28/0.00234.71E − 07x28/26/0.00183.71E − 078/29/0.00263.05E − 0714/28/0.00723.81E − 07x36/20/0.00245.14E − 075/17/0.00212.81E − 079/18/0.00374.33E − 07x49/29/0.00253.29E − 0710/36/0.00302.76E − 0714/28/0.00576.84E − 07x57/23/0.00235.38E − 078/29/0.00434.75E − 0712/24/0.00295.80E − 07x69/29/0.00293.26E − 0710/38/0.02262.93E − 0714/28/0.00384.71E − 075,000x19/29/0.00928.59E − 0710/38/0.01567.59E − 0715/30/0.00843.81E − 07x28/26/0.00658.27E − 078/29/0.01127.90E − 0714/28/0.00878.37E − 07x37/23/0.00721.03E − 075/17/0.00237.21E − 079/18/0.00878.74E − 07x49/29/0.00627.32E − 0710/36/0.00875.80E − 0715/30/0.01565.32E − 07x57/23/0.00565.40E − 078/29/0.00865.08E − 0712/24/0.00715.84E − 07x69/29/0.00297.31E − 0710/38/0.02017.59E − 0715/30/0.01493.81E − 0710,000x110/32/0.01301.10E − 0711/41/0.02012.14E − 0815/30/0.01535.38E − 07x29/29/0.01371.06E − 079/32/0.01492.23E − 0815/30/0.01913.39E − 07x37/23/0.01231.45E − 076/20/0.00212.03E − 0810/20/0.01575.51E − 07x410/32/0.01379.40E − 0810/36/0.01598.15E − 0815/30/0.03217.53E − 07x57/23/0.00885.41E − 078/29/0.01945.13E − 0712/24/0.01165.84E − 07x610/32/0.01499.40E − 0811/41/0.02132.14E − 0815/30/0.03895.38E − 0750,000x110/32/0.06712.47E − 0711/41/0.08754.88E − 0817/36/0.08689.29E − 07x29/29/0.01372.38E − 079/32/0.06735.08E − 0815/30/0.08047.56E − 07x37/23/0.06393.23E − 076/20/0.04214.62E − 0811/22/0.05961.08E − 07x410/32/0.06682.10E − 0710/36/0.08111.81E − 0716/32/0.09333.93E − 07x57/23/0.04525.41E − 078/29/0.05135.16E − 0712/24/0.07545.85E − 07x610/32/0.07702.10E − 0711/41/0.10574.88E − 0817/36/0.15589.29E − 07100,000x110/32/0.14553.49E − 0711/41/0.19596.92E − 0819/44/0.25575.50E − 07x29/29/0.13653.36E − 079/32/0.15707.20E − 086/13/0.08665.16E − 10x37/23/0.14514.56E − 076/20/0.05826.55E − 0811/22/0.14131.53E − 07x410/32/0.14052.97E − 0710/36/0.12532.56E − 0717/36/0.23566.78E − 07x57/23/0.09645.41E − 078/29/0.11835.17E − 0712/24/0.15485.85E − 07x610/32/0.16792.97E − 0711/41/0.12266.92E − 0819/44/0.29715.49E − 07Table 3
Numerical results for Problem2 with different initial points.
PiDimInitial pointsMSGP methodSGP methodPDY methodIter/NF/CPUtimeNormIter/NF/CPUtimeNormIter/NF/CPUtimeNormP21,000x19/29/0.00192.19E − 077/23/0.00219.49E − 0812/25/0.00362.41E − 07x28/26/0.00263.71E − 076/20/0.00173.23E − 078/17/0.00181.95E − 07x37/23/0.00325.14E − 075/17/0.00233.14E − 074/9/0.00128.55E − 07x49/29/0.00191.01E − 077/23/0.00252.71E − 0811/23/0.01305.06E − 07x57/23/0.00352.44E − 075/17/0.00164.70E − 078/17/0.00197.06E − 07x69/29/0.00212.18E − 077/23/0.00299.47E − 0812/25/0.00852.40E − 075,000x19/29/0.00544.89E − 077/23/0.00592.12E − 0712/25/0.01805.39E − 07x29/29/0.00568.27E − 076/20/0.00597.22E − 078/17/0.01738.81E − 07x38/26/0.00734.89E − 075/17/0.00547.01E − 075/11/0.00109.55E − 07x49/29/0.00422.26E − 077/23/0.00926.05E − 0812/25/0.01297.46E − 08x57/23/0.00432.44E − 075/17/0.00554.70E − 078/17/0.00807.06E − 07x69/29/0.00784.89E − 077/23/0.00712.12E − 0712/25/0.00685.39E − 0710,000x110/32/0.00756.91E − 077/23/0.01013.00E − 0712/25/0.02307.63E − 07x29/29/0.00741.06E − 077/23/0.01382.01E − 089/19/0.02036.07E − 07x38/26/0.00626.91E − 075/17/0.00609.92E − 076/13/0.00111.41E − 09x49/29/0.00713.19E − 077/23/0.00978.56E − 0812/25/0.01761.05E − 07x57/23/0.00902.44E − 075/17/0.01354.70E − 078/17/0.00897.06E − 07x69/29/0.01056.91E − 077/23/0.01273.00E − 0712/25/0.01737.62E − 0750,000x110/32/0.03971.40E − 077/23/0.05086.71E − 0717/37/0.06474.90E − 07x29/29/0.03832.38E − 077/23/0.04174.50E − 0810/21/0.02933.52E − 08x38/26/0.04771.40E − 076/20/0.04174.37E − 086/13/0.01823.15E − 09x49/29/0.03347.14E − 077/23/0.04531.91E − 0712/25/0.02762.36E − 07x57/23/0.03602.44E − 075/17/0.04964.70E − 078/17/0.04567.06E − 07x610/32/0.05511.40E − 077/23/0.06576.71E − 0717/37/0.06394.90E − 07100,000x110/32/0.08401.99E − 077/23/0.12049.49E − 0716/37/0.14151.95E − 07x29/29/0.08433.36E − 077/23/0.09386.36E − 0810/21/0.08354.97E − 08x38/26/0.08011.99E − 076/20/0.09316.18E − 086/13/0.02564.45E − 09x410/32/0.08519.18E − 087/23/0.11312.71E − 0717/37/0.15444.10E − 07x57/23/0.07912.44E − 075/17/0.09434.70E − 078/17/0.09467.06E − 07x610/32/0.11271.99E − 077/23/0.15479.49E − 0716/37/0.16371.95E − 07Table 4
Numerical results for Problem3 with different initial points.
PiDimInitial pointsMSGP methodSGP methodPDY methodIter/NF/CPUtimeNormIter/NF/CPUtimeNormIter/NF/CPUtimeNormP31,000x18/26/0.00172.71E − 0727/84/0.00895.06E − 0714/43/0.00374.60E − 07x28/26/0.00202.78E − 0726/81/0.00535.18E − 0711/34/0.00468.86E − 07x37/23/0.00162.71E − 0722/69/0.02257.29E − 0713/40/0.02093.75E − 07x48/26/0.00122.71E − 0727/84/0.00796.34E − 0712/37/0.02313.44E − 07x510/32/0.00391.84E − 0718/57/0.00359.76E − 0714/43/0.00415.48E − 07x68/26/0.00362.69E − 0727/85/0.00479.67E − 0714/43/0.00394.53E − 075,000x18/26/0.00676.03E − 0729/91/0.03155.40E − 0715/46/0.03173.95E − 07x28/26/0.00666.22E − 0727/84/0.03019.75E − 0711/34/0.01026.43E − 07x37/23/0.00576.03E − 0725/78/0.03782.17E − 0714/43/0.03435.55E − 07x48/26/0.00776.03E − 0728/87/0.02177.15E − 0712/37/0.02707.68E − 07x510/32/0.00981.84E − 0718/57/0.01519.76E − 0714/43/0.06225.48E − 07x68/26/0.00976.02E − 0728/87/0.02679.86E − 0715/46/0.05573.94E − 0710,000x18/26/0.01018.52E − 0729/90/0.03952.33E − 0715/46/0.04695.58E − 07x28/26/0.01288.80E − 0727/84/0.10194.99E − 0711/34/0.05107.66E − 07x37/23/0.01218.52E − 0725/78/0.06429.02E − 0713/40/0.05376.29E − 07x48/26/0.01448.52E − 0729/90/0.04745.10E − 0713/40/0.03614.80E − 07x510/32/0.01441.84E − 0718/57/0.02419.76E − 0714/43/0.05755.48E − 07x68/26/0.01888.51E − 0729/90/0.05037.21E − 0715/46/0.05205.58E − 0750,000x19/29/0.05169.06E − 0830/93/0.20237.87E − 0717/54/0.13388.71E − 07x28/26/0.06411.20E − 0729/90/0.23347.72E − 0712/37/0.06768.74E − 08x37/23/0.05289.06E − 0826/81/0.29658.56E − 0710/31/0.08961.96E − 07x49/27/0.05279.06E − 0830/93/0.27305.76E − 0714/43/0.08801.11E − 07x510/32/0.06321.84E − 0718/57/0.09469.76E − 0714/43/0.17665.48E − 07x69/29/0.06619.06E − 0830/93/0.24108.79E − 0717/54/0.15668.70E − 07100,000x19/29/0.35671.69E − 0731/96/0.59605.72E − 0716/55/0.40287.67E − 07x28/26/0.14071.69E − 0730/93/0.40485.13E − 0712/37/0.25451.21E − 07x37/23/0.19241.69E − 0727/84/0.36376.26E − 079/28/0.14288.50E − 07x49/29/0.22361.69E − 0730/93/0.41658.15E − 0717/54/0.23107.76E − 07x510/32/0.21901.84E − 0718/57/0.22669.76E − 0714/43/0.26185.48E − 07x69/29/0.26351.28E − 0731/96/0.45566.31E − 0716/55/0.29937.66E − 07Table 5
Numerical results for Problem4 with different dimensions.
PiInitial pointsDimMSGP methodSGP methodPDY methodIter/NF/CPUtimeNormIter/NF/CPUtimeNormIter/NF/CPUtimeNormP4x1108/26/0.00106.72E − 0817/54/0.00195.66E − 0718/55/0.00158.28E − 07508/26/0.00071.50E − 0718/57/0.00144.57E − 0719/58/0.00133.33E − 071008/26/0.00382.13E − 0718/57/0.00396.47E − 0719/58/0.01665.13E − 075008/26/0.00234.75E − 0719/60/0.00535.23E − 0720/61/0.01644.33E − 071,0008/26/0.00236.72E − 0719/60/0.03217.39E − 0721/64/0.02013.75E − 075,0009/29/0.01349.13E − 0820/63/0.03115.97E − 0722/67/0.04375.55E − 0710,0009/29/0.01721.29E − 0720/63/0.04488.44E − 0722/67/0.04116.29E − 0750,0009/29/0.06822.89E − 0721/66/0.21766.82E − 0724/75/0.08251.96E − 07x2106/20/0.00124.58E − 0715/47/0.00103.88E − 0716/48/0.00087.64E − 07507/23/0.00076.22E − 0815/47/0.00158.67E − 0717/51/0.00146.70E − 071007/23/0.00698.80E − 0816/50/0.00664.43E − 0718/54/0.01878.57E − 075007/23/0.00271.97E − 0716/50/0.00459.91E − 0719/57/0.00373.29E − 071,0007/23/0.00172.78E − 0717/53/0.00425.06E − 0719/57/0.00454.60E − 075,0007/23/0.00646.22E − 0718/56/0.01844.09E − 0720/60/0.04503.95E − 0710,0007/23/0.01228.80E − 0718/56/0.08515.78E − 0720/60/0.07865.58E − 0750,0008/26/0.08371.20E − 0719/59/0.25004.67E − 0721/63/0.28298.71E − 07x3106/13/0.00114.58E − 07—/—/———/—/——507/15/0.00126.22E − 08—/—/———/—/——1007/15/0.00068.80E − 08—/—/———/—/——5007/15/0.00151.97E − 07—/—/———/—/——1,0007/15/0.00252.78E − 07—/—/———/—/——5,0007/15/0.01616.22E − 07—/—/———/—/——10,0007/15/0.01948.80E − 07—/—/———/—/——50,0008/17/0.07291.20E − 07—/—/———/—/——Table 6
Numerical results for Problem5 with different dimensions.
PiInitial pointsDimMSGP methodSGP methodPDY methodIter/NF/CPUtimeNormIter/NF/CPUtimeNormIter/NF/CPUtimeNormP5x1233/101/0.00168.80E − 0766/202/0.00228.96E − 0718/91/0.00126.05E − 074130/392/0.00469.81E − 07169/538/0.03419.01E − 07219/1123/0.02078.50E − 0716941/2825/0.02869.98E − 071178/3908/0.03859.42E − 071500/7688/0.08657.39E − 07321638/4916/0.05708.73E − 071962/6558/0.03279.76E − 072558/13110/0.13607.69E − 07642633/7901/0.06179.82E − 073144/10531/0.06349.96E − 073926/20121/0.18667.51E − 071284217/12653/0.14109.92E − 074916/16302/0.13539.95E − 076124/31392/0.30117.60E − 072566666/20000/0.29019.93E − 078214/27435/0.34819.89E − 0710012/51336/0.49917.58E − 0751211696/35090/0.75999.82E − 0714560/48682/0.86851.00E − 0617200/88207/1.15477.65E − 071,02420903/62711/2.42189.73E − 0727051/90306/2.92909.96E − 0730772/157825/2.94957.68E − 07x2229/89/0.00328.80E − 0764/197/0.00197.90E − 0723/115/0.00174.89E − 07442/128/0.13709.81E − 07128/412/0.00369.09E − 07207/242/0.00476.61E − 0716931/2795/0.03369.98E − 071264/4117/0.02139.63E − 071420/7282/0.03397.76E − 07321616/4850/0.03768.73E − 071985/6599/0.03449.96E − 072472/12675/0.08877.63E − 07642580/7742/0.06169.98E − 073025/10086/0.06349.92E − 073801/19490/0.18617.77E − 071283953/11861/0.11609.92E − 075001/16674/0.13669.90E − 076021/30871/0.31257.63E − 072566508/19526/0.27189.93E − 078090/26812/0.29879.96E − 0710011/51323/0.53747.60E − 0751211443/34331/0.74699.82E − 0714158/47251/0.83949.79E − 0727409/89240/1.12247.67E − 071,02420911/62735/2.42029.73E − 0725447/84850/2.83899.96E − 0731399/160940/2.69507.72E − 07x3237/113/0.00619.53E − 0782/250/0.01738.78E − 0716/81/0.00116.78E − 074132/398/0.02169.72E − 07197/619/0.01809.74E − 07122/629/0.00386.95E − 0716949/2849/0.01709.63E − 071223/4034/0.03509.66E − 071427/7319/0.07547.61E − 07321672/5018/0.03119.24E − 072028/6770/0.06349.90E − 072480/12719/0.13817.53E − 07642540/7622/0.05819.98E − 073182/10562/0.06829.99E − 073798/19476/0.21697.74E − 071283963/11891/0.12499.90E − 074938/16418/0.14239.76E − 076015/30843/0.32767.54E − 072566579/19739/0.28259.69E − 078193/27161/0.36739.91E − 0710001/51274/0.64967.60E − 0751211567/34703/0.74999.73E − 0714206/47314/0.85639.97E − 0727405/89221/0.95937.68E − 071,02420759/62279/2.38349.96E − 0725433/84882/2.85999.85E − 0731407/160982/3.23087.63E − 07Table 7
Numerical results for Problem6 with different dimensions.
PiInitial pointsDimMSGP methodSGP methodPDY methodIter/NF/CPUtimeNormIter/NF/CPUtimeNormIter/NF/CPUtimeNormP6x11054/164/0.00227.15E − 0763/216/0.00238.97E − 0767/288/0.00344.58E − 075056/170/0.00428.34E − 0769/246/0.00369.12E − 0773/316/0.00487.80E − 0710063/191/0.00619.51E − 0777/276/0.00439.19E − 0782/353/0.00756.58E − 0750062/188/0.01238.89E − 0782/305/0.00368.02E − 0794/402/0.01755.98E − 071,00070/212/0.01717.01E − 0779/306/0.01338.70E − 07103/438/0.01266.53E − 075,00080/242/0.08259.04E − 0784/312/0.08559.93E − 07115/487/0.10905.84E − 0710,00067/203/0.15829.79E − 0786/331/0.16479.19E − 07217/495/0.22666.38E − 0750,00074/224/0.86289.31E − 0797/351/0.77287.10E − 07328/539/1.00955.68E − 07x21058/176/0.00228.77E − 0771/250/0.00367.98E − 0771/308/0.00327.53E − 075075/227/0.00437.63E − 0789/322/0.00666.81E − 0794/407/0.00695.70E − 0710070/212/0.00559.39E − 0795/337/0.00589.06E − 0787/379/0.00806.28E − 0750079/239/0.01166.74E − 07330/1052/0.03918.72E − 07107/468/0.01056.44E − 071,00078/236/0.01656.36E − 07577/1795/0.13819.76E − 07114/499/0.03797.23E − 075,00078/236/0.07868.91E − 07603/1869/0.58579.57E − 07122/537/0.12856.03E − 0710,00082/248/0.16907.47E − 07316/1010/0.56988.81E − 07229/572/0.28236.19E − 0750,00098/296/0.086076.39E − 07275/900/1.98678.51E − 07342/631/1.11207.44E − 07x31063/191/0.00248.77E − 0771/242/0.00249.00E − 0768/298/0.00316.22E − 075079/239/0.00307.63E − 0791/314/0.00499.83E − 0792/398/0.00305.52E − 0710062/188/0.00779.39E − 0787/317/0.00518.45E − 0786/373/0.02734.97E − 0750068/206/0.00946.74E − 0791/335/0.01279.98E − 07104/443/0.01455.87E − 071,00078/236/0.02036.36E − 07100/362/0.01578.83E − 07107/464/0.03977.24E − 075,00085/257/0.07948.91E − 07118/419/0.11548.67E − 07120/524/0.13147.99E − 0710,00095/287/0.16507.47E − 07125/443/0.24468.32E − 07233/592/0.26136.15E − 0750,00099/299/0.77486.39E − 07337/1083/7.02989.28E − 07312/625/1.27297.20E − 07Figure 1
Performance profile with respect to number of iterations.Figure 2
Performance profile with respect to CPU time.Figure 3
Performance profile with respect to number of function evaluations.


## 5. Application in Compressive Sensing

In this section, we considerℓ1-norm regularization problem in compressive sensing which involves finding sparse solutions to underdetermined or ill-conditioned linear systems of equations. A popular approach is minimizing an objective function which can be expressed as follows:(72)minx12y−Ax22+τx1,where x∈Rn, y∈Rk is an observation, and A∈Rk×nk≪n is a linear operator. Moreover, τ is a non-negative parameter. x2 and x1 denote the Euclidean norm and the ℓ1-norm of x, respectively. Obviously, problem (72) is a convex unconstrained optimization problem which has become a research hotspot, particularly in compressive sensing if the original signal is sparse or approximately sparse in some orthogonal basis. Consequently, an exact restoration can be obtained by solving problem (72).In recent decades, different approaches have been proposed to solve (72). In [43], these methods are divided into four categories including greedy strategy approximation, homotopy algorithm, proximate algorithm, and constrained optimization (see [44–47] in order).The gradient-based method is very popular among these methods, and one of the most earliest gradient projection methods for sparse reconstruction (GPSR) was presented in [47]. We now briefly review this approach; the first key step of GPSR approach is to express (72) as a quadratic program. For any x∈Rn, split it into its positive and negative parts, and then x can be formulated in the following form:(73)x=u−v,u≥0,v≥0.These relationships are satisfied byui=xi+ and vi=−xi+ for all i=1,2,…,n, where ⋅+ denotes the positive part operator defined as x+=max0,x. Thus, we have x1=enTu+enTv, where enT=1,1,…,1T is the vector consisting of n ones. Furthermore, (72) can be rewritten as the following bound-constrained quadratic program (BCQP):(74)minu,v12y−Au−v22+τenTu+τenTv,s.t.u≥0,v≥0.Moreover, as in [47], (72) can be written in more standard BCQP form:(75)minz12zTBz+cTz,s.t.z≥0,where z=uv, c=τe2n+−bb, b=ATy, and B=ATA−ATA−ATAATA. Since B is a positive semidefinite matrix, obviously, (75) is a convex quadratic program problem.Recently, Xiao et al. [48] translated (75) into a linear variable inequality problem (VIP) and pointed out that this VIP is equivalent to the linear complementary problem, i.e., find a vector z∈Rn such that(76)z≥0,Hz+c≥0,zTHz+c=0.They also claimed thatz is a solution of (76) if and only if it satisfies(77)Fz=minz,Hz+c=0.The mappingF is monotone and Lipschitz continuous, and relevant proofs are listed in literature [48, 49], respectively. Therefore, we can utilize our MSGP method to solve (77).In what follows, we design an experiment to reconstruct a sparse signal of lengthn from k observations. The quality of restoration is determined by the mean of squared error (MSE) to the original signal x¯:(78)MSE≔1nx¯−x∗2,where x∗ is recovered signal. In our experiment, the size of signal is selected with n=212 and k=210, and original signal contains 27 random nonzero elements. Under MATLAB R2019a environment, we use command randnm,n to generate the Gaussian matrix A. In addition, the measurement y is distributed with noise, i.e., y=Ax¯+ξ, where ξ is the Gaussian noise distributed as N0,10−4.In order to illustrate good performance of proposed method, we compare it with two different gradient methods. The first one is the conjugate gradient descent (CGD) method [50] which is more efficient than the spectral gradient (SGCS) method [48] in compressive sensing field. The second is a projection method (PCG) [51] which can be viewed as an extension of the CGD method. The parameters for three algorithms are taken as follows:(i)
CGD method:ξ=10, σ=0.0001, and ρ=0.5.(ii)
PCG method:ξ=10, σ=0.0001, ρ=0.5, and r=0.2.(iii)
MSGP method:ξ=1, σ=0.0001, ρ=0.5, and r0=0.01.We usefx=1/2y−Ax22+τx1 as the merit function. For a fair comparison, we use the same continuation technique on parameter τ which is forced to decrease as the measure in [47]. In addition, each algorithm starts at the same initial point.The iterative process starts at the measurement image, i.e.,x0=ATy, and terminates when the relative change between successive iterates falls below 10−5, i.e.,(79)fk−fk−1fk−1<10−5,where fk denotes the function evaluation at xk.Numerical results including the original signal, the measurement, and the recovered signal by related approaches are reported in Figure4. Moreover, we plot four figures to demonstrate their convergence behavior from the trends of MSE and objective function values along with increasing number of iterations and CPU time (see Figures 5–8).Figure 4
From top to bottom: the original signal, the measurement, and the recovered signals by CGD, PCG, and MSGP methods.Figure 5
The relationship between MSE and number of iterations.Figure 6
The relationship between MSE and computing time.Figure 7
The relationship between objective function values and number of iterations.Figure 8
The relationship between objective function values and computing time.In Figure4, we can observe that CGD, PCG, and MSGP methods recovered the original signal almost exactly. However, our method requires less number of iterations and less CPU time (in seconds) to achieve similar quality restoration. This can also be seen in Figures 5–8 where the objective function values and MSE obtained by MSGP method decrease faster than other methods throughout the whole iteration process. Furthermore, the experiment is repeated for 10 different noise samples, and the average of 10 results is also given (see Table 8). We can clearly see that in Table 8, the MSGP method outperforms the CGD method and PCG method in terms of MSE, the number of iterations, and CPU time for most cases.Table 8
The experiment results and average result ofℓ1-norm regularization problem via three methods.
Original signalCGD methodPCG methodMSGP methodMSEIterCPUtimeMSEIterCPUtimeMSEIterCPUtime12.69E − 051987.175.17E − 041235.382.72E − 04975.0629.84E − 051927.231.73E − 041556.053.61E − 05803.8431.33E − 051947.755.14E − 041164.173.26E − 05884.4742.48E − 051976.385.89E − 041113.693.52E − 05844.4153.52E − 042147.331.35E − 041315.553.78E − 05913.6464.16E − 051826.531.79E − 041224.364.14E − 05985.0875.50E − 052108.386.48E − 051459.221.94E − 051236.2584.61E − 052238.131.78E − 041877.691.40E − 051446.9291.82E − 041374.631.16E − 031043.501.55E − 05813.86105.65E − 052227.941.25E − 041515.483.42E − 05884.45Average8.97E − 05196.907.153.63E − 04134.505.515.38E − 0597.404.80


## 6. Conclusion

In this paper, we proposed a family of modified spectral projection methods for solving nonlinear monotone equations with convex constraints, where the spectral parameter is mainly determined by a convex combination of two modified BB stepsizes. We also introduced several schemes to update the spectral parameter. Under the specific assumptions, we proved the global convergence of new algorithm. Thanks to its low memory requirement, our method is suitable for resolving the large-scale nonlinear monotone equations as well as theℓ1-norm regularization problem in compressive sensing. How to analyze the local convergence and the iterative complexity of the proposed method is worthy of further study.



---

*Source: 2018243-2020-10-28.xml*