# New Inertial RelaxedCQ Algorithms for Solving Split Feasibility Problems in Hilbert Spaces

Authors: Haiying Li; Yulian Wu; Fenghui Wang
Journal: Journal of Mathematics
 (2021)

---

## Abstract

The split feasibility problemSFP has received much attention due to its various applications in signal processing and image reconstruction. In this paper, we propose two inertial relaxed CQ algorithms for solving the split feasibility problem in real Hilbert spaces according to the previous experience of applying inertial technology to the algorithm. These algorithms involve metric projections onto half-spaces, and we construct new variable step size, which has an exact form and does not need to know a prior information norm of bounded linear operators. Furthermore, we also establish weak and strong convergence of the proposed algorithms under certain mild conditions and present a numerical experiment to illustrate the performance of the proposed algorithms.


---

## Body

## 1. Introduction

The split feasibility problem in finite-dimensional Hilbert spaces was first introduced by Censor and Elfving [1] in 1994, for modeling inverse problem that arises from the phase retrievals and in medical image reconstruction [2]. The split feasibility problem can also be used to model the intensity-modulated radiation therapy [3].LetH1 and H2 be two real Hilbert spaces with the inner product ⋅,⋅ and the induced norm ⋅. C and Q are nonempty closed and convex subsets of real Hilbert spaces H1 and H2, respectively, and A is a linear bounded operator from H1 into H2. The split feasibility problem SFP is formulated as follows: find a point x∈H1 satisfying(1)x∈C,Ax∈Q.The solution set of the problemSFP (1) is denoted by S; that is,(2)S≔x∈C:Ax∈Q.A very successful method that solves theSFP seems to be the CQ algorithm of Byrne [4], which generates xn by the iterative procedure: for any initial guess x1∈H,(3)xn+1=PCxn−γA∗I−PQAxn,∀n≥1,where PC and PQ are the metric projections onto C and Q, respectively. A∗ is the adjoint operator of the linear operator A, and the step size γ is chosen in the open interval 0,2/A2. The step size selection depends on the operator norm (or the largest eigenvalue of A∗A), which also is not a simple work.TheCQ algorithm (3) for solving the problem SFP (1) can be obtained from optimization. If we introduce the convex objective function(4)fx≔12I−PQAx2,x∈H1,then the CQ algorithm (3) comes immediately as a special case of the gradient-projection algorithm GPA, since the convex objective function f is differentiable and has a Lipschitz gradient given by(5)∇fx=A∗I−PQAx.To overcome the computational difficulties, many authors have constructed the variable step size that does not require the normA; see, for example, [5–12]. In particular, Lopez et al. [7] introduced a new choice of the variable step size sequence τn as follows:(6)τn≔ρnfxn∇fxn2,∀n≥1,where ρn is a sequence of positive real numbers, take zero for the lower bound and four for the upper bound. The advantage of the choice (6) of step size is that there is neither prior information about the matrix norm A nor any other conditions on Q and A.Now let us consider the case whenC and Q are level subsets of convex functions, where C and Q are, respectively, given by(7)C=x∈H1:cx≤0,Q=y∈H2:qy≤0,where c:H1⟶−∞,+∞ and q:H2⟶−∞,+∞ are two lower semicontinuous convex functions, and ∂c and ∂q are bounded operators. But the associated projections PC and PQ do not have closed-form expressions, and the CQ algorithm is that the iterative process cannot be performed. In order to keep it going, Yang [13] made improvements to these two-level subsets; here is how they are defined:(8)Cn˜=x∈H1:cxn+ξn,x−xn≤0,with ξn∈∂cxn, and(9)Qn˜=y∈H2:qAxn+ζn,y−Axn≤0,with ζn∈∂qAxn.It is easy to see thatCn˜ and Qn˜ are both half-spaces, and the projections PCn˜ and PQn˜ have closed-form expressions. In what follows, for each n≥1, define(10)fnx≔12I−PQn˜Ax2,∇fnx=A∗I−PQn˜Ax.Since these projections are easy to calculate, the algorithm is very practical.Afterwards, the inertial technique was developed by Alvarez and Attouch in order to improve the performance of proximal point algorithms [14]. Dang et al. [15] proposed an inertial relaxed CQ algorithm xn for solving the problem SFP in a real Hilbert space, which is generated as follows: for any x0,x1∈H, (11)wn=xn+θnxn−xn−1,xn+1=PCn¯wn−γATI−PQn¯Awn,where 0<γ<2/A2, and 0≤θn≤θn¯ with(12)θn¯=minθ,1maxn2xn−xn−12,n2xn−xn−12,∀n≥1,θ∈0,1,Cn¯=x∈H1|cwn+ξn,x−wn≤0,with ξn∈∂cwn, and(13)Qn¯=y∈H2|qAwn+ζn,y−Awn≤0,with ζn∈∂qAwn. The algorithm xn converges weakly to a point of a solution set of the problem SFP, where step size also depends on the matrix norm A. It is obvious that the calculation of operator norm is more complicated, so Gibali et al. [16] has changed the step size of (11).(14)λn=ρnfnwnηn2,ηn=max1,∇fnwn,0≤θn≤θn¯,where(15)θn¯=minθ,εnxn−xn−12,ifxn≠xn−1,θ,otherwise.If∑n=1∞θnxn−xn−12<∞, then the sequence xn generated by (11) with step size λn converges weakly to a point of a solution set of the problem SFP. For recent results on inertial algorithms (see [17–24]).On the other hand, theCQ algorithm is the gradient-projection method for the variational inequality problem. In [25], Xu gave weak convergence in the setting of Hilbert spaces. Wang and Xu [26] proposed the following algorithm:(16)xn+1=PC1−αnxn−γ∇fxn,where γ∈0,2/A2. Under some conditions, it is proved that the sequence generated by the algorithm (16) strongly converges to the minimum-norm solution of the SFP. Motivated and inspired by the work of [7, 27–29], the authors of [30] introduced a self-adaptive CQ-type algorithm for finding a solution of the SFP in the setting of infinite-dimensional real Hilbert spaces; the advantage of this algorithm lies in the fact that step sizes are dynamically chosen and do not depend on the operator norm. This algorithm can be formulated as follows:(17)xn+1=PCn1−βnxn−λn∇fnxn,where λn=ρnfnxn/∇fnxn2. It is also proved that the sequence generated by the algorithm (17) strongly converges to the minimum-norm solution of the SFP under some conditions.Inspired by the works mentioned above, we propose a new relaxedCQ algorithm to solve the SFP in a real Hilbert space by using inertial technology. The new step size proposed in this algorithm is independent of the operator norm in this paper, and we also establish weak convergence theorem of the proposed algorithms under some mild conditions in [31]. We add the inertial term on the basis of the algorithm in [30] to construct a new iterative process, so that the new algorithm strongly converges to a point in the solution set under some conditions.The remainder of the paper is organized as follows. Some useful definitions and results are collected in Section2 for the convergence analysis of the proposed algorithm. In Section 3, new inertial algorithms of weak and strong convergence for solving SFP are proposed, followed by the convergence analysis. In Section 4, we provide a numerical experiment to illustrate the performance of the proposed algorithms. Finally, we end the paper with some conclusion.


## 2. Preliminaries

LetH be a Hilbert space and let C be a nonempty closed convex subset in H. The strong (weak) convergence of a sequence xn to x is denoted by xn⟶xxn⇀x, respectively. For any sequence xn⊂H, ωwxn denotes the weak ω−limit set of xn; that is,(18)ωwxn≔x∈H:xnj⇀x,for  some subsequencenjofn.Definition 1.
An operatorT:C⟶H is called the following:(i)
Nonexpansive if(19)Tx−Ty≤x−y,∀x,y∈C.(ii)
Firmly nonexpansive if(20)Tx−Ty2≤x−y2−I−Tx−I−Ty2,∀x,y∈C.(iii)
ν-inverse strongly monotone (ν-ism) if there is ν>0 such that(21)Tx−Ty,x−y≥νTx−Ty2,∀x,y∈C.
For every elementx∈H, there exists a unique nearest point in C denoted by PCx, such that(22)x−PCx=minx−y|y∈C.
Then operatorPC is called the metric projection from H onto C.
The projection has the following well-known properties.Lemma 1 (see [32, 33]).
For allx,y∈H and z∈C, we have(1)
x−PCx,z−PCx≤0(2)
PCx−PCy≤x−y(3)
PCx−PCy2≤x−y,PCx−PCy(4)
PCx−z2≤x−z2−I−PCx2Lemma 2.
LetH be a real Hilbert space and x,y,z∈H, t∈R; then(1)
1−tx+ty2=1−tx2+ty2−t1−tx−y2;(2)
x−y2=y−z2−x−z2+2x−y,x−z.Definition 2 (see [34]).
LetH be a real Hilbert space and let f:H⟶−∞,∞ be a convex function. An element v∈H is called the subgradient of f at x¯∈H if(23)v,x−x¯≤fx−fx¯,∀x∈H.
The collection of all the subgradients off at x¯ is called the subdifferential of the function f at this point, which is denoted by ∂fx¯; that is,(24)∂fx¯=v∈H:v,x−x¯≤fx−fx¯,∀x∈H.Definition 3.
Letf:H⟶−∞,+∞ be a proper function.(i)
f is lower semicontinuous at x if xn⟶x implies(25)fx≤liminfn⟶∞fxn.(ii)
f is weakly lower semicontinuous at x if xn⇀x implies(26)fx≤liminfn⟶∞fxn.(iii)
f is lower semicontinuous on H if it is lower semicontinuous at every point x∈H; f is weakly lower semicontinuous on H if it is weakly lower semicontinuous at every point x∈H.(iv)
f is lower semicontinuous if and only if it is weakly lower semicontinuous.Lemma 3 (see [34]).
Letf:H⟶−∞,+∞ be an α-strongly convex function. Then, for all x,y∈H,(27)fy≥fx+ξ,y−x+α2y−x2,ξ∈∂fx.Lemma 4 (see [25]).
Lett>0 and x∗∈H. Then the following statements are equivalent:(1)
The pointx∗ solves the problem SFP.(2)
The pointx∗ solves the fixed-point equation(28)x∗=PCx∗−tA∗I−PQAx∗.(3)
The pointx∗ solves the variational inequality problem with respect to the gradient of f; that is, find a point x∈C such that(29)∇fx,y−x≥0,∀y∈C.Lemma 5 (see [16]).
LetH be a real Hilbert space and let xn be a sequence in H such that there exists a nonempty closed and convex subset S of H satisfying the following conditions:(i)
For allz∈S, limn⟶∞xn−z exists(ii)
Any weak cluster point ofxn belongs to S
Then there existsx∗∈S such that xn converges weakly to x∗.Lemma 6 (see [35]).
Letϕn⊂0,∞ and δn⊂0,∞ be two nonnegative real sequences satisfying the following conditions:(1)
ϕn+1−ϕn≤θnϕn−ϕn−1+δn(2)
∑n=1∞δn<∞(3)
θn⊂0,θ, where θ∈0,1
Then,ϕn is a converging sequence and ∑n=1∞ϕn+1−ϕn+<∞, where t+=maxt,0 for any t∈R.Lemma 7 (see [36, 37]).
Letann=0∞ and γnn=0∞ be sequences of nonnegative real numbers such that(30)an+1≤1−βnan+δn+γn,n≥1,where βnn=0∞ is a sequence in 0,1 and δnn=0∞ is a real sequence. Assume ∑n=1∞γn<∞. Then the following results hold:(1)
Ifδn≤βnM for some M≥0, then ann=0∞ is a bounded sequence(2)
If∑n=1∞βn=∞ and limsupn⟶∞δn/βn≤0, then limn⟶∞an=0Lemma 8 (see [38]).
Assume thatsn is a sequence of nonnegative real numbers such that(31)sn+1≤1−αnsn+αnδn,n≥1,sn+1≤sn−λn+γn,n≥1,where αn is a sequence in 0,1, λn is a sequence of nonnegative real numbers, and δn and γn are two sequences in ℜ such that(1)
∑n=1∞αn=∞(2)
limn⟶∞γn=0(3)
limk⟶∞λnk=0 implies limsupk⟶∞δnk≤0 for any subsequence nk of n
Thenlimn⟶∞sn=0.


## 3. Convergence Analysis

In this section, we consider theSFP in which C is given by(32)C=x∈H1|cx≤0,where c:H1⟶−∞,+∞ is an α-strongly convex function; the set Q is given by(33)Q=y∈H2|qy≤0,where q:H2⟶−∞,+∞ is a β-strongly convex function. We assume that the solution set S of the SFP is nonempty, and c and q are lower semicontinuous convex functions; furthermore, we also assume that ∂c and ∂q are bounded operators (i.e., bounded on bounded sets).We agree to build the following sets in our algorithms according to [39]; that is, given the n-th iterative point wn, we construct Cn as(34)Cn=x∈H1|cwn+ξn,x−wn+α2x−wn2≤0,​​where ξn∈∂cwn.(35)Qn=y∈H2|qAwn+ζn,y−Awn+β2y−Awn2≤0,​​where ζn∈∂qAwn.Ifα=0 and β=0, then Cn and Qn are reduced to the half-spaces Cn¯ and Qn¯, respectively. If α>0 and β>0 , then Cn and Qn are nonempty closed ball of radius 1/αξn2−2αcwn centred at wn−1/αξn and 1/βζn2−2βqAwn centred at Awn−1/βζn, respectively.In addition, for eachn≥0, we define the following functions:(36)fnx=12I−PQnAx2,∇fnx=A∗I−PQnAx,where Qn is given as in (35), fn is weakly lower semicontinuous, convex, and differentiable, and its gradient ∇fn is Lipschitz continuous. Now we propose new relaxed CQ algorithms for solving the SFP.Next, two inertial relaxed CQ algorithms will be introduced. The weak convergence of Algorithm1 and the strong convergence of Algorithm 2 will be proved under different step sizes.Algorithm 1.
Choose positive sequenceεn satisfying ∑n=0∞εn<∞.
Letx0,x1∈C be arbitrary. Given xn, xn−1, update the next iteration via(37)wn=xn+θnxn−xn−1,xn+1=PCnwn−τn∇fnwn,where 0≤θn<θn¯, and(38)θn¯=minθ,εnmaxxn−xn−12,xn−xn−1,ifxn≠xn−1,θ,ifxn=xn−1,and Cn and Qn are given as in (34) and (35).(39)τn=σn∇fnwn,if∇fnwn≠0,0,if∇fnwn=0,where ∑n=1∞σn=∞, ∑n=1∞σn2<∞.
Ifxn+1=wn, then stop; otherwise, set n:=n+1 and go to the next iteration.
By assumingθn¯, we know(40)∑n=1∞θnxn−xn−12<∞,∑n=1∞θnxn−xn−1<∞,which means(41)limn⟶∞θnxn−xn−12=0,limn⟶∞θnxn−xn−1=0.
Fromξn∈∂cwn, applying Lemma 3, we get C⊆Cn; and a similar way is used to get Q⊆Qn.
Now let us show that our proposed algorithm has a very important property: ifxn+1=wn for some n>0, then wn is a solution of SFP. Indeed, xn+1∈Cn, so that wn∈Cn as wn=xn+1 by assumption. So we get cwn≤0 from (34), that is, wn∈C. On the other hand, according to the algorithm, we have wn=PCnwn−τnA∗I−PQnAwn, which together with Lemma 4 implies that Awn∈Qn. It also implies that qAwn≤0 from (35); then Awn∈Q. The conclusion is tenable.Lemma 9.
Letxn and wn be the sequences generated by Algorithm 1. Then, for any z∈S, it follows that(42)xn+1−z2≤wn−z2+σn2−4σnfnwn∇fnwn.Proof.
Forz∈S, we have z∈C,Az∈Q; and we have z=PCz=PCnz,Az=PQAz=PQnAz.
It follows from Lemma1 that(43)xn+1−z2=PCnwn−τn∇fnwn−z2≤wn−z−τn∇fnwn2−wn−xn+1−τn∇fnwn2=wn−z2−wn−xn+12−2τn∇fnwn,wn−z+2τn∇fnwn,wn−xn+1,where(44)2τn∇fnwn,wn−z=2τnI−PQnAwn−I−PQnAz,Awn−Az≥2τnI−PQnAwn2=4τnfnwn,2τn∇fnwn,wn−xn+1≤2τn∇fnwn⋅wn−xn+1≤wn−xn+12+τn2∇fnwn2.
Hence, we have(45)xn+1−z2≤wn−z2−wn−xn+12−4τnfnwn+wn−xn+12+τn2∇fnwn2.
If∇fnwn=0, then τn=0, so that(46)xn+1−z2≤wn−z2.
If∇fnwn≠0, we have(47)xn+1−z2≤wn−z2+τn2∇fnwn2−4τnfnwn=wn−z2+σn2−4σnfnwn∇fnwn.
The proof is complete.Theorem 1.
Assume thatθn satisfies the assumption. Then there exists a subsequent xnj of xn generated by Algorithm 1 which weakly converges to a solution of SFP.Proof.
We first show that, for anyz∈S, the limit of xn−z exists. By applying Lemma 9, we have(48)xn+1−z2≤wn−z2+σn2−4σnfnwn∇fnwn.
From the construction ofwn and Lemma 2, we have(49)wn−z2=1+θnxn−z−θnxn−1−z2=1+θnxn−z2−θnxn−1−z2+θn1+θnxn−xn−12,(50)≤1+θnxn−z2−θnxn−1−z2+2θnxn−xn−12.
Combining (48) and (50) immediately, we get(51)xn+1−z2≤1+θnxn−z2−θnxn−1−z2+2θnxn−xn−12+σn2.
Denoteϕn=xn−z2; from (51), we have(52)ϕn+1−ϕn≤θnϕn−ϕn−1+2θnxn−xn−12+σn2,where(53)∑n=1∞θnxn−xn−12<∞,∑n=1∞σn2<∞.
Using Lemma6, the limit of ϕn exists, and ∑n=1∞xn+1−z2−xn−z2+<∞, which implies that ∑n=1∞xn+1−z2−xn−z2<∞, xn+1−z2−xn−z2+=maxxn+1−z2−xn−z2,0. This also implies that the sequence xn is bounded, so wn is bounded.
We next show thatωwxn⊂S. Since wn is bounded, from the Lipschitz continuity of ∇fn, we get that ∇fnwn is bounded. From (48) and (50), we get(54)4σnfnwn∇fnwn≤xn−z2−xn+1−z2+θnxn−z2−xn−1−z2+2θnxn−xn−12+σn2,where ∑n=1∞xn+1−z2−xn−z2<∞, ∑n=1∞θnxn−xn−12<∞, and ∑n=1∞σn2<∞, so we have(55)∑n=1∞4σnfnwn∇fnwn<∞.
But∑n=1∞σn=∞, so(56)liminfn⟶∞fnwn=0,i.e.,liminfn⟶∞I−PQnAwn2=0.
On the other hand, sincexn is bounded, the set ωwxn is nonempty. Let x∗∈ωwxn; then there exists a subsequence xnk of xn such that xnk⇀x∗. Furthermore,(57)wn−xn2=θn2xn−xn−12≤θnxn−xn−12⟶0.
Letwnj be a subsequence of the sequence wn such that(58)liminfn⟶∞I−PQnAwn2=limj⟶∞I−PQnjAwnj2=0.
Sincewnj is bounded, there exists a subsequence wnjm of wnj, which converges weakly to x∗. Without loss of generality, we can assume that wnj⇀x∗, and A is a bounded linear operator, so Awnj⇀Ax∗.
From Lemma1, we conclude that(59)wn−τn∇fnwn−xn+1,z−xn+1≤0.
Sinceτn⟶0 and ∇fnwn is bounded, we have τn∇fnwn⟶0. Hence, we get(60)xn+1−wn,xn+1−z≤τn∇fnwn,z−xn+1⟶0.
Since∑n=1∞xn+1−z2−xn−z2<∞ and ∑n=1∞θnxn−xn−12<∞, from (50), we obtain(61)xn+1−wn2=wn−z2−xn+1−z2+2xn+1−wn,xn+1−z≤xn−z2−xn+1−z2+θnxn−z2−xn−1−z2+2θnxn−xn−12+2xn+1−wn,xn+1−z⟶0.
Thus,(62)xn+1−xn≤xn+1−wn+wn−xn⟶0.
SincePQnjAwnj∈Qnj, by the definition of Qnj,(63)qAwnj+ζnj,PQnjAwnj−Awnj+β2PQnjAwnj−Awnj2≤0,where ζnj∈∂qAwnj. From the boundedness assumption of ∂q and limj⟶∞I−PQnjAwnj2=0, we have(64)qAwnj≤ζnj⋅I−PQnjAwnj−β2I−PQnjAwnj2⟶0.
From the weak lower semicontinuity of the convex functionq, it follows that(65)qAx∗≤liminfj⟶∞qAwnj≤0,which means that Ax∗∈Q.
Furthermore,xnj+1∈Cnj, and, by the definition of Cnj,(66)cwnj+ξnj,xnj+1−wnj+α2xnj+1−wnj2≤0,where ξnj∈∂cwnj. From the boundedness assumption of ∂c and xnj+1−wnj⟶0, we have(67)cwnj≤ξnj⋅wnj−xnj+1−α2xnj+1−wnj2⟶0.
From the weak lower semicontinuity of the convex functionc, it follows that(68)cx∗≤liminfj⟶∞cwnj≤0,which means that x∗∈C. Therefore, xnj⇀x∗∈S. The proof is complete.Algorithm 2.
Choose positive sequenceεn satisfying ∑n=0∞εn<∞.
Letx0,x1∈C be arbitrary. Given xn, xn−1, update the next iteration via(69)wn=xn+θnxn−xn−1,xn+1=βnu+PCn1−βnwn−τn∇fnwn,τn=ρnfnwn∇fnwn2,where 0≤θn<θn¯, and(70)θn¯=minθ,εnmaxxn−xn−12,xn−xn−1,ifxn≠xn−1,θ,ifxn=xn−1,and Cn and Qn are given as in (34) and (35), βn⊂0,1, limn⟶∞βn=0, ∑n=1∞βn=∞, and infnρn4−ρn>0.
Ifxn+1=wn, then stop; otherwise, set n:=n+1 and go to the next iteration.Theorem 2.
Assume thatinfnρn4−ρn>0 and εn=oβn. Then the sequence xn generated by Algorithm 2 converges strongly to z=PSu.Proof.
First, we show that, for anyz∈S, the sequence xn is bounded. From the construction of wn, we have(71)wn−z=xn+θnxn−xn−1−z≤xn−z+θnxn−xn−1,(72)wn−τn∇fnwn−z2=wn−z2+τn2∇fnwn2−2τn∇fnwn,wn−z≤wn−z2+τn2∇fnwn2−4τnfnwn=wn−z2+ρn2fn2wn∇fnwn2−4ρnfn2wn∇fnwn2=wn−z2−ρn4−ρnfn2wn∇fnwn2≤wn−z2.
So, combining (71) and (72), we get(73)xn+1−z=βnu+PCn1−βnwn−τn∇fnwn−z=PCn1−βnwn−τn∇fnwn−1−βnz+βnu−z≤PCn1−βnwn−τn∇fnwn−1−βnz+βnu−z≤1−βnwn−τn∇fnwn−1−βnz+βnu−z≤1−βnwn−τn∇fnwn−z+βnu−z≤1−βnwn−z+βnu−z≤1−βnxn−z+θnxn−xn−1+βnu−z≤1−βnxn−z+βnσn+u−z,where σn=1−βnθn/βnxn−xn−1. According to hypothesis θn¯,(74)θn≤εnxn−xn−1⇒θnβnxn−xn−1≤εnβn⟶0.
Note that(75)limn⟶∞σn=limn⟶∞1−βnθnβnxn−xn−1=0,which implies that the sequence σn is bounded. Setting(76)M=maxsupn∈Nσn,u−z,as well as using Lemma 7, we conclude that the sequence xn−z is bounded. This shows that the sequence xn is bounded and so is wn.
Sincexn−z is bounded, assume that there exists a constant M1 such that xn−z≤M1. Thus,(77)wn−z2≤xn−z+θnxn−xn−12=xn−z2+θn2xn−xn−12+2θnxn−xn−1⋅xn−z≤xn−z2+θnxn−xn−12+2M1⋅θnxn−xn−1,and we get(78)xn+1−z2=βnu+PCn1−βnwn−τn∇fnwn−z2=PCn1−βnwn−τn∇fnwn−1−βnz+βnu−z2≤PCn1−βnwn−τn∇fnwn−1−βnz2+2βnu−z,xn+1−z≤1−βnwn−τn∇fnwn−1−βnz2+2βnu−z,xn+1−z≤1−βnwn−z2−ρn4−ρnfn2wn∇fnwn2+2βnu−z,xn+1−z≤1−βnxn−z2+θnxn−xn−12+2M1⋅θnxn−xn−1−ρn4−ρnfn2wn∇fnwn2+2βnu−z,xn+1−z.
From (78),(79)xn+1−z2≤1−βnxn−z2+βnθnβnxn−xn−12+2M1⋅θnβnxn−xn−1+2u−z,xn+1−z,xn+1−z2≤xn−z2−ρn4−ρnfn2wn∇fnwn2+θnxn−xn−12+2M1⋅θnxn−xn−1+2βnu−z,xn+1−z.
Let(80)sn=xn−z2;δn=θnβnxn−xn−12+2M1⋅θnβnxn−xn−1+2u−z,xn+1−z;ηn=ρn4−ρnfn2wn∇fnwn2;γn=θnxn−xn−12+2M1⋅θnxn−xn−1+2βnu−z,xn+1−z.
Then (78) can reduce to the inequalities(81)sn+1≤1−βnsn+βnδn,n≥1,sn+1≤sn−ηn+γn.
Furthermore, we know that(82)∑n=0∞βn=∞,(83)limn⟶∞γn=limn⟶∞θnxn−xn−12+2M1⋅θnxn−xn−1+2βnu−z,xn+1−z=0.
Letnk be a subsequence of n and suppose that(84)limk⟶∞ηnk=0.
Then, we have(85)limk⟶∞ρnk4−ρnkfnk2wnk∇fnkwnk2=0,which implies, by our assumption, that(86)fnk2wnk∇fnkwnk2⟶0,ask⟶∞.
Since∇fnkwnk is bounded, it follows that fnkwnk⟶0 as k⟶∞, so we get limk⟶∞I−PQnkAwnk=0.
We next show thatωwxn⊂S. Since xn is bounded, the set ωwxn is nonempty. Let x∗∈ωwxn; then there exists a subsequence xnk of xn such that xnk⇀x∗.(87)wn−xn=xn+θnxn−xn−1−xn=θnxn−xn−1⟶0,and then wnj⇀x∗, and A is a bounded linear operator, so Awnj⇀Ax∗.
SincePQnjAwnj∈Qnj, we have(88)qAwnj+ζnj,PQnjAwnj−Awnj+β2PQnjAwnj−Awnj2≤0,where ζnj∈∂qAwnj, and, by the boundedness of ∂q, we get(89)qAwnj≤ζnj⋅I−PQnjAwnj−β2I−PQnjAwnj2⟶0,and, using the weak lower semicontinuity of q,(90)qAx∗≤liminfj⟶∞qAwnj≤0.
Thus,Ax∗∈Q.
On the other hand,(91)xn+1−wn≤1−βnwn−τn∇fnwn−wn+βnu−z=1−βn⋅ρnfnwn∇fnwn+βnu−z⟶0.
Sincexnj+1−βnju∈Cnj, we have(92)cwnj+ξnj,xnj+1−βnju−wnj+α2xnj+1−βnju−wnj2≤0,where ξnj∈∂cwnj, and, by the boundedness of ∂c, we get(93)cwnj≤ξnj⋅wnj−xnj+1+βnju−α2xnj+1−wnj−βnju2≤ξnj⋅wnj−xnj+1+βnju−α2xnj+1−wnj2+βnj2u2−2xnj+1−wnj,βnju⟶0,and, using the weak lower semicontinuity of c,(94)cx∗≤liminfj⟶∞cwnj≤0.
Thus,x∗∈C; then x∗∈S, that is, ωwxn⊂S.
Next, we have(95)xn+1−xn≤1−βnwn−τn∇fnwn−xn+βnu−xn≤1−βnwn−xn+τn∇fnwn+βnxn−u≤wn−xn+ρnfnwn∇fnwn+βnxn−u⟶0.
Forz=PSu and xnk⇀x∗∈S, using Lemma 1, u−z,x∗−z≤0, so(96)limsupn⟶∞u−z,xn−z=limsupk⟶∞u−z,xnk−z=u−z,x∗−z≤0,and then(97)limsupn⟶∞u−z,xn+1−z=limsupn⟶∞u−z,xn+1−xn+u−z,xn−z≤0,and thus(98)limsupkδnk=limsupkθnkβnkxnk−xnk−12+2M1⋅θnkβnkxnk−xnk−1+2u−z,xnk+1−z≤0.
From (82), (83), (98), and Lemma 8, we conclude that the sequence xn converges strongly to z=PSu. The proof is complete.


## 4. Numerical Experiments

In this section, we present a numerical experiment to illustrate the performance of the proposed algorithms. Our numerical experiments are coded in MATLAB R2007 running on personal computer with 3.50 GHz Intel Core i3 and 4 GB RAM. In what follows, we apply our algorithms to solve the problem of least absolute shrinkage and selection operator, which requires solving a convex optimization problem as(99)minx∈ℝn,12Ax−y2,s.t.,x1≤t0,where A∈ℝm×n, y∈ℝm, and t0>0 are given elements. In our experiment, we first generate an m×n matrix A randomly by a standardized normal distribution, and x is a sparse signal with n elements, only K of which is nonzero, which is also generated randomly. The observation y is generated as y=Ax. The parameters in this experiment are set with n=512,m=256,ε=10−4, and t0=K. In this situation, it is readily seen that C=x∈ℝn:cx≤0 with cx=x1−t0 and Q=y, which in turn implies that(100)Cn=x∈ℝn:ξn,x≤ξn,wn−wn1+t0,where ξn is defined by(101)ξni=1,ifξni>0;−1,1,ifξni=0;−1,ifξni<0,standing for the subdifferential of ⋅1. As a half-space, the associated projection onto Cn takes the following form:(102)PCnx=x+ξn,wn−x−wn1+t0ξn2ξn,ifx∉Cnx,ifx∈Cn.To show the efficiency of our algorithm, we compare it with the algorithm proposed in [40]. The only difference of these two algorithms is that there are no inertial terms in the algorithm proposed in [40]. For the convenience, we denote Algorithm 1 by Algo. I and the algorithm in [40] by Algo. II, respectively. In Algorithm 1, we set(103)θn=min0.8,1n2xn−xn−12,ifxn≠xn−1,0.8,ifxn=xn−1,τn=1nA∗Awn−y,ifA∗Awn−y≠0,0,ifA∗Awn−y=0.In Algo. II, we setθn≡0 and τn is chosen the same as above. The stopping criterion is that xk+1−xk<ε. The initial points are x0=0,0,…,0T and x1=1001,1,…,1T. The numerical results of these two algorithms with different choices of the sparsity number K are listed in Figures 1–4. It is easy to see that Algo. I converges faster than Algo. II does, which indicates that our modified algorithm indeed accelerates the convergence of the original algorithm.Figure 1
Iterative results withK=50.Figure 2
Iterative results withK=40.Figure 3
Iterative results withK=30.Figure 4
Iterative results withK=20.


## 5. Conclusions

In this paper, we present two inertial relaxedCQ algorithms for solving split feasibility problems in Hilbert spaces by adopting variable step size. These algorithms adopt the new convex subset form, and it is easy to calculate the projections onto these sets. Furthermore, step size selection in the algorithms does not depend on the operator norm. The convergence theorems are established under some mild conditions and a numerical experiment is given to illustrate the performance of the proposed algorithms.



---

*Source: 6624509-2021-02-16.xml*