# The Ball-Relaxed Gradient-Projection Algorithm for Split Feasibility Problem

Authors: Xiaochun Li; Xiaoxiao Liu; Fugen Gao
Journal: Journal of Function Spaces
 (2022)

---

## Abstract

In this paper, we concern with the split feasibility problem (SFP) whenever the convex sets involved are composed of level sets. By applying Gradient-projection algorithm which is used to solve constrained convex minimization problem of a real valued convex function, we construct two new algorithms for the split feasibility problem and prove that both of them are convergent weakly to a solution of the feasibility problem. In the end, as an application, we obtain a new algorithm for solving the split equality problem.


---

## Body

## 1. Introduction

The split feasibility problem (SFP) was first introduced by Censor and Elfving [1]. And it is formulated as finding a point x satisfying the property:
(1)x∈CandAx∈Q,where C and Q are nonempty, closed, and convex subsets of real Hilbert spaces H1 and H2, respectively, and A is a bounded linear operator from H1 to H2.Many inverse problems arising from real world can be summarized as SFP. So, the SFP has attracted many scholars to study it. Of course, various algorithms by far have been invented to solve the SFP (see, e.g., [2–9]). And one of the most famous methods for solving the SFP is CQ algorithm which is introduced by Byrne. Take an initial guess x0∈H1 and define a recursively equation as
(2)xn+1=PCI−αA∗I−PQAxn,where 0<α<2/L and L denotes the largest eigenvalue of the matrix ATA. Later, Byrne introduced another recursively equation as
(3)xn+1=PCI−αnA∗I−PQAxn,where 0<αn<2/∥A∥2. Byrne has shown that the sequence xn produced by (2) or (3) is convergent weakly to a solution of the SFP (1). From (2) and (3), we know that we have first to compute or estimate the largest eigenvalue of the matrix ATA and the operator norm ∥A∥2 before implementing algorithms. However, computing or estimating the matrix norm is in general not an easy work in practice. So the conditions that Byrne put on his proposed two algorithms seem restrictive. Recently, Lopez et al. [10] proposed a novel way to construct another stepsize which has no connection with eigenvalue and matrix norm. And Lopez et al. suggested the following stepsize:
(4)αn=∥I−PQAxn∥2∥A∗I−PQAxn∥2,and showed the weak convergence of the CQ algorithm (3).In this paper, we consider the SFP whenever bothC and Q are level sets for given strongly convex function, that is,
(5)C=x∈H1cx≤0,(6)Q=y∈H2qy≤0,where c:H1⟶−∞,+∞ is an α-strongly convex lower semicontinuous function and q:H2⟶−∞,+∞ is a β-strongly convex lower semicontinuous function. However, in general, computing the orthogonal projections onto C and Q is not an easy task. To overcome this difficulty, Yu et al. [11] have considered the case when Cn and Qn are two sequences of balls defined, respectively, by
(7)Cn=x∈H1cxn≤ξn,xn−x−α2x−xn2,ξn∈∂cxn,(8)Qn=y∈H2qAxn≤ηn,Axn−y−β2y−Axn2,ηn∈∂qAxn,where c and q are strongly convex functions with constant α and β, respectively. Yu et al. [11] have shown that Cn is a ball whose centre is xn−1/αξn and radius is 1/α2ξn2−2/αcxn. And Qn is also a ball whose centre is Axn−1/βηn and radius is 1/β2ηn2−2/βqAxn. It is easy to see that C⊆Cn and Q⊆Qn for any n≥0. Since Cn and Qn are balls, the associated projections can be easily calculated.The rest of this paper is organized as follows. In Section2, we review some basic definitions and lemmas that we will use in the remaining sections. In Section 3, we introduce two new ball-relaxed gradient-projection algorithms for solving the SFP and prove the weak convergence of our algorithms. In Section 4, according to the algorithms that we suggest in Section 3, we obtain a new iterative algorithm for solving the split equality problem and establish its weak convergence.


## 2. Preliminaries

Throughout this paper, we always assume thatHii=1,2 is a real Hilbert space with the inner product ⋅,⋅ and norm ∥⋅∥. We denote by I the identity operator on Hii=1,2 and by wwxn the set of all cluster points of xn. The notation “⟶”stands for strong convergence, and “⇀” stands for weak convergence.Definition 1 ([12]).
LetD be a nonempty subset of H1, and let T:D⟶H1. Then, T is
(1)
Nonexpansive if it is Lipschitz continuous with constant 1, i.e.,(9)∥Tx−Ty∥≤∥x−y∥,∀x,y∈D.(2)
Firmly nonexpansive if(10)∥Tx−Ty∥2+∥I−Tx−I−Ty∥2≤∥x−y∥2,∀x∈D,y∈D.(3)
v-inverse strongly monotone (v-ism, v>0) if(11)Tx−Ty,x−y≥v∥Tx−Ty∥2,∀x∈D,y∈D.Definition 2.
LetC be a nonempty closed convex subset of H1. Then, an orthogonal projection PC:H1⟶C is defined by
(12)PCx=argminy∈C∥x−y∥2,x∈H1.Lemma 3.
LetC be a nonempty closed convex subset of H1; then,
(1)
For everyx and p in H1(13)p=PCx⇔p∈Cand∀y∈Cx−p,y−p≤0.(2)
PC and I−PC both are nonexpansiveDefinition 4 (see [12]).
Letλ∈0,1 and f:H1⟶−∞,+∞ be a proper function.
(1)
f is convex if(14)fλx+1−λy≤λfx+1−λfy,∀x,y∈H1.(2)
f is strongly convex with constant α where α>0 if(15)fλx+1−λy+α2λ1−λx−y2≤λfx+1−λfy,∀x,y∈H1.(3)
A vectoru∈H1 is a subgradient of a point x if(16)y−x,u+fx≤fy,∀y∈H1.(4)
The subdifferential off is the set-valued operator(17)∂f:H⟶2H:x⟶u∈H∀y∈Hy−x,u+fx≤fy.(5)
f is subdifferentiable at x∈H if ∂fx≠∅; the elements of ∂fx are the subgradients f at xDefinition 5.
Letf:H1⟶−∞,+∞ be a proper function; then, we can obtain the following:
(1)
f is lower semicontinuous at a point x if xn⟶x implies(18)fx≤liminfn⟶∞fxn.(2)
f is weakly lower semicontinuous at a point x if xn⇀x implies(19)fx≤liminfn⟶∞fxn.(3)
f is lower semicontinuous on H1 if it is lower semicontinuous at any point x∈H1(4)
f is weakly lower semicontinuous on H1 if it is weakly lower semicontinuous at any point x∈H1Lemma 6 (see [12]).
Assume thatf:H1⟶−∞,+∞ is a proper convex function; then, f is a lower semicontinuous function if and only if it is a weakly lower semicontinuous function.Definition 7.
LetC be a nonempty closed convex subset in H1, and xn is a sequence in H1, if for any n≥0 and z∈C, we have
(20)∥xn+1−z∥≤∥xn−z∥,and then, we say that the sequence xn is Fejér-monotone with respect to C.Lemma 8 (see [12]).
Assume that a sequencexn in H1 is Fejér-monotone with respect to C which is a nonempty closed convex subset of H1; then, xn is weakly convergent to a point of C if and only if its any weak cluster point belongs to C.


## 3. The Algorithm Proposed and Proved

In this section, we still concern with the case the involved subsets are composed of level sets, that is, the case wheneverC and Q are given by (5) and (6). In this case, we shall assume that problem (1) is consistent, namely, its solution set, denoted by S, is nonempty. Besides, we need to assume that ∂c and ∂q are bounded on bounded sets.We know that, inH1, when consider the constrained convex minimization problem of a real valued convex function f:C⟶R, one of the most famous methods is the gradient projection algorithm (GPA) that generates a sequence xn according to the recursive formula
(21)xn+1=PCxn−αn∇fxn,n≥0,where the parameter αn is a sequence of positive real numbers. And if ∇f is Lipschitz continuous with constant L≥0 and the parameter sequence αn satisfies 0<liminfn⟶∞αn≤limsupn⟶∞αn<2/L, Xu [13] showed that the sequence xn generated by the GPA converges weakly to a minimizer of f.We know that the solution of the SFP amounts to unconstrained minimization of(22)fx=12∥I−PCx∥2+12∥I−PQAx∥2,and ∇f=I−PC+A∗I−PQA. By a simple calculation, we have ∇f is Lipschitz continuous with 2+∥A∥2. In this case, method (21) is reduced to
(23)xn+1=PCxn−αnI−PCxn+A∗I−PQAxn.From the above equation, we know that the implementation of the above iterative algorithm needs to calculate the projections ontoC and Q first. Since C and Q are both level sets defined by (5) and (6), it is very difficult to calculate the projection onto the level set at each step. To facilitate the computation of the projection onto C and Q, we will compute the projections onto Cn and Qn which were defined by (7) and (8) instead of C and Q. Now, we give our ball-relaxed gradient-projection algorithm for solving the SFP (1).Algorithm 1.
Letx0 be arbitrary, and generate xn according to the following iterative formula.
(24)xn+1=PCnxn−αnI−PCnxn+A∗I−PQnAxn,where Cn and Qn are defined by (7) and (8), and the parameter sequence αn satisfies 0<a≤αn≤b<2/L, where a and b are two positive real numbers and L=2+∥A∥2.Theorem 9.
Letxn be the sequence generated by Algorithm 1; then, xn converges weakly to a solution of the SFP (1).Proof.
On the one hand, we will show that the sequencexn is Fejér-monotone with respect to S.
Now, denotedI−PCnxn+A∗I−PQnAxn by un; then, (24) is equivalent to xn+1=PCnxn−αnun. For any z∈S, that is, z∈C⊆Cn, and Az∈Q⊆Qn, we have
(25)∥xn+1−z∥2=∥PCnxn−αnun−z∥2≤∥xn−z−αnun∥2=∥xn−z∥2−2αnxn−z,un+αn2∥un∥2.
From Lemma3, we obtain
(26)xn−z,un=xn−z,I−PCnxn+A∗I−PQnAxn=xn−z,xn−PCnxn+Axn−Az,Axn−PQnAxn≥∥xn−PCnxn∥2+∥Axn−PQnAxn∥2.
Besides,(27)∥un∥2=∥xn−PCnxn+A∗I−PQnAxn∥2≤1+∥A∥2∥xn−PCnxn∥2+1+1∥A∥2∥A∗I−PQnAxn∥2≤1+∥A∥2∥xn−PCnxn∥2+∥I−PQnAxn∥2.
Substituting (26) and (27) into (25), we have
(28)∥xn+1−z∥2≤∥xn−z∥2−2αn∥xn−PCnxn∥2+∥I−PQnAxn∥2+αn21+∥A∥2∥xn−PCnxn∥2+∥I−PQnAxn∥2=∥xn−z∥2−αn2−αn1+∥A∥2∥xn−PCnxn∥2+∥I−PQnAxn∥2.
Since0<a≤αn≤b<2/2+∥A∥2, we can obtain αn2−αn1+∥A∥2>0. The above inequality (28) implies that xn is Fejér-monotone with respect to S.
On the other hand, we will show that any weak cluster point of the sequencexn belongs to the solution set S, i.e., wwxn⊆S.
The inequality (28) implies that the sequence ∥xn−z∥ is bounded and converges to some finite limit. Passing to the limit in (28), we have
(29)limn⟶∞∥xn−PCnxn∥2+∥Axn−PQnAxn∥2=0,that is,
(30)limn⟶∞∥xn−PCnxn∥=0,limn⟶∞∥Axn−PQnAxn∥=0.
Besides, since the sequencexn is Fejér-monotone with respect to S, it is bounded, and so is the sequence Axn. Then, there exists a subsequence xnk of xn convergent weakly to x¯x¯∈wwxn. What is more, due to ∂c and ∂q are bounded on bounded sets, there are two constants β>0 and δ>0, such that ∥ξn∥≤β and ∥ζn∥≤δ for all ξn∈∂cxn, ζn∈∂qAxn with n≥0.
From (7) and the fact that PCnkxnk∈Cnk, we obtain
(31)cxnk≤ξnk,xnk−PCnkxnk−α2∥xnk−PCnkxnk∥2≤ξnk,xnk−PCnkxnk≤∥ξnk∥⋅∥xnk−PCnkxnk∥≤β∥xnk−PCnkxnk∥⟶0,k⟶∞.
Sincec is convex and lower semicontinuous, then it is also weakly lower semicontinuous by Lemma 6. This together with (31) implies that
(32)cx¯≤liminfn⟶∞cxnk≤0.
It turns out thatx¯∈C.
Similarly, from (8) and the fact that PQnkAxnk∈Qnk, we obtain
(33)qAxnk≤ηnk,Axnk−PQnkAxnk−β2∥Axnk−PQnkAxnk∥2≤ηnk,Axnk−PQnkAxnk≤∥ηnk∥⋅∥Axnk−PQnkAxnk∥≤δ∥Axnk−PQnkAxnk∥⟶0,k⟶∞.
Sinceq is convex and lower semicontinuous, then it is also weakly lower semicontinuous by Lemma 6. This together with (33) implies that
(34)qAx¯≤liminfn⟶∞qAxnk≤0.
It turns out thatAx¯∈Q. Then, x¯∈S which implies that wwxn⊆S. From Lemma 8, we can get xn converges weakly to x¯ as n⟶∞. This completes the proof.From Algorithm1, we know that we have first to estimate the operator norm ∥A∥2 so that we can select appropriate parameters to implement Algorithm 1. However, computing or estimating the matrix norm ∥A∥2 is not an easy work in practice. To overcome this difficulty, we construct a variable stepsize that does not require the matrix norm.Algorithm 2.
Letx0 be arbitrary, and generate xn according to the following iterative formula.
(35)xn+1=PCnxn−αnI−PCnxn+A∗I−PQnAxn,where Cn and Qn are defined by (7) and (8), and the parameter sequence αn is given by
(36)αn=λna∥I−PCnxn∥2+∥I−PQnAxn∥2∥I−PCnxn+A∗I−PQnAxn∥2,where λn is a sequence of positive real numbers and a is any positive real number.Theorem 10.
Letxn be the sequence generated by Algorithm 2; if 0<ε≤λn≤2a−ε, then xn converges weakly to a solution of the SFP (1).Proof.
For anyz∈S, that is, z∈C⊆Cn, and Az∈Q⊆Qn, we have
(37)∥xn+1−z∥2=∥PCnxn−αnun−z∥2≤∥xn−z−αnun∥2=∥xn−z∥2−2αnxn−z,un+αn2∥un∥2.
From Lemma8, we obtain
(38)xn−z,un=xn−z,I−PCnxn+A∗I−PQnAxn=xn−z,xn−PCnxn+Axn−Az,Axn−PQnAxn≥∥xn−PCnxn∥2+∥Axn−PQnAxn∥2.
Substituting (36) and (38) into (37), we have
(39)∥xn+1−z∥2≤∥xn−z∥2−λna2−λna∥xn−PCnxn∥2+∥Axn−PQnAxn∥22∥xn−PCnxn+A∗I−PQnAxn∥2≤∥xn−z∥2−ε2a2∥xn−PCnxn∥2+∥Axn−PQnAxn∥22∥xn−PCnxn+A∗I−PQnAxn∥2.
The above inequality (39) implies that xn is Fejér-monotone with respect to S.
Nextly, we show that any weak cluster point of the sequencexn belongs to the solution set S, i.e., wwxn⊆S. The inequality (39) implies that the sequence ∥xn−z∥ is bounded and converges to some finite limit. Passing to the limit in (39), we have
(40)limn⟶∞∥xn−PCnxn∥2+∥Axn−PQnAxn∥2∥xn−PCnxn+A∗I−PQnAxn∥=0,
while(41)limn⟶∞∥xn−PCnxn∥2+∥Axn−PQnAxn∥2=limn⟶∞∥xn−PCnxn∥2+∥Axn−PQnAxn∥2∥xn−PCnxn+A∗I−PQnAxn∥⋅∥xn−PCnxn+A∗I−PQnAxn∥=0,so, we obtain
(42)limn⟶∞∥xn−PCnxn∥=0,limn⟶∞∥Axn−PQnAxn∥=0.
The rest proof is similar to Theorem9.Remark 11.
Recently, there are some new results about SFP, such as Shehu and Gibali introduced a relaxedCQ method with alternated inertial step for solving SFP in [14]; Shehu et al. introduced some new computational technique for solving proximal SFP by using a modified proximal split feasibility algorithm in [15–17]. Our computational techniques are different from theirs.


## 4. Application in the Split Equality Problem

The split equality (SEP) is an inverse problem that requests to finding(43)x,y∈C×Q,s.t.Ax=By,where A:H1⟶H3 and B:H2⟶H3 are two linear bounded operators, and C⊂H1 and Q⊂H2 are two nonempty closed convex subsets.We know that, for anyX=x1,x2 and Y=y1,y2 in H1×H2, if we defined
(44)X,Y=x1,y1+x2,y2,∥X∥2=∥x1∥2+∥x2∥2,AX=Ax1−Bx2,where A and B are defined as the same to (43). Then, it has been proved that A is a bounded linear operator [11], and the SEP can be regarded as a special SFP: find X=x,y∈H1×H2, such that
(45)X∈C,AX∈Q,where C=C×Q, Q=0. Motivated by (35), we can propose a new method for solving the SEP (43).Algorithm 3.
For any arbitrary initial guessx0,y0, define xn,yn recursively by the following.
(46)xn+1=PCnxn−αnxn−PCnxn+A∗Axn−Byn,yn+1=PQnyn−αnyn−PQnyn−B∗Axn−Byn,where Cn and Qn are, respectively, given by (7) and (8), and parameter sequence αn is chosen as
(47)αn=λna∥xn−PCnxn∥2+∥yn−PQnyn∥2+∥Axn−Byn∥2∥xn−PCnxn+A∗Axn−Byn∥2+∥yn−PQnyn−B∗Axn−Byn∥2,where λn is a sequence of positive real numbers, and a is any positive real number.Theorem 11.
Letxn,yn be the sequence generated by Algorithm 3, and if 0<ε≤λn≤2a−ε, then xn,yn converges weakly to a solution of the SEP (43).Proof.
LetXn=xn,yn, and A:H1×H2⟶H3 is a bounded linear operator which is defined by AX=Ax−By; then, Algorithm 3 can be rewritten as
(48)Xn+1=PCnXn−αnXn−PCnXn+A∗I−P0AXn,where Cn=Cn×Qn. Hence, by applying Theorem 10, we can conclude that Xn converges weakly to a solution of the SEP (43).



---

*Source: 9991466-2022-04-12.xml*