# The Split Feasibility Problem and Its Solution Algorithm

Authors: Biao Qu; Binghua Liu
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

The split feasibility problem arises in many fields in the real world, such as signal processing, image reconstruction, and medical care. In this paper, we present a solution algorithm called memory gradient projection method for solving the split feasibility problem, which employs a parameter and two previous iterations to get the next iteration, and its step size can be calculated directly. It not only improves the flexibility of the algorithm, but also avoids computing the largest eigenvalue of the related matrix or estimating the Lipschitz constant in each iteration. Theoretical convergence results are established under some suitable conditions.


---

## Body

## 1. Introduction

The split feasibility problem (SFP) was first put forward in [1] by Censor and Elfving. It requires finding a point in a nonempty closed convex subset in one space such that its image under a certain operator is in another nonempty closed convex subset in the image space. Its precise mathematical formulation is as follows: Given closed convex set C and closed convex sets Q in N- and M-dimensional Euclidean space, respectively, the split feasibility problem is to find a vector x∗ for which (1)x∗∈Csuch  thatAx∗∈Q,where A is a given M×N real matrix.The SFP arises in many fields in the real world, such as signal processing, image reconstruction, and medical care; for details see [1–3] and the references therein. For example, a number of image reconstruction problems can be formulated as split feasibility problems. The vector x represents a vectorized image, with the entries of x, the intensity levels at each voxel or pixel. The set C can be selected to incorporate such features as nonnegativity of the entries of x, while the matrix A can describe linear functional or projection measurements we have made, as well as other linear combinations of entries of x on which we wish to impose constraints. The set Q then can be the product of the vector of measured data with other convex sets, such as nonnegative cones, that serve to describe the constraints to be imposed [4]. Here we give a discretized model of SFP in image reconstruction problem of X-ray tomography [5, 6]. In image reconstruction, we consider a portion of the form of a two-dimensional cross section in which the attenuation intensities of X-ray are not identical for different tissue. This attenuation effect can be seen as a function with nonnegative variable, called the image or images. We hope to get information about the physiological state of the organization by measuring the data. The fundamental model is formulated in the following way: a Cartesian grid of square picture elements, called pixels, is introduced into the region of interest so that it covers the whole picture that has to be reconstructed. The pixels are numbered in some agreed manner, say from 1 (top left corner pixel) to J (bottom right corner pixel) (see Figure 1).Figure 1The X-ray attenuation function is assumed to take a constant valuexj throughout the jth pixel for j=1,2,…,J. Source and detector are assumed to be points and the rays between them (lines). Further, we assumed that the length of intersection of the ith ray with the jth pixel, denoted by aij for all i=1,2,…,I and j=1,2,…,J, represents the weight of the contribution of the jth pixel to the total attenuation along the ith ray. The physical measurement of the total attenuation of the ith ray, denoted by yi, represents the line integral of the unknown attenuation function along the path of the ray. Therefore, in this discretized model, the line integral turns out to be a finite sum and the whole model is described by a system of linear equations (2)∑j=1Jxjaij=yi,i=1,2,…,I.In matrix notation, we write the equations above as (3)Ax=y,where y=(yi)∈RI is the measurement vector, x=(xj)∈RJ is the image vector, and the I×J matrix A=(aij) is the projection matrix. So the model is a special SFP: (4)findx∈RJsuch thatAx=y,x≥0,y≥0.It can also be unified model for many inverse problems, such as intensity-modulated radiation therapy (IMRT) [3].Many well-known iterative algorithms have been established for the SFP (see, e.g., [1, 4, 6–18]). In [1], the authors used their multidistance idea to obtain iterative algorithms for solving the SFP. Their algorithms, as well as others obtained later, involve matrix inverses at each iteration. In [4], Byrne presented a projection method called the CQ algorithm for solving the SFP that does not involve matrix inverses, but they assumed that the metric projections onto C and Q are easily calculated. However, in some cases it is impossible or needs too much work to exactly compute the metric projection. Therefore, if this case appears, the efficiency of projection-type methods, including the CQ algorithm, will be seriously affected. In [16], by using the relaxed projection technology, Yang presented a relaxed CQ algorithm for solving the SFP, where he used two halfspaces Ck and Qk in place of C and Q, respectively, at the kth iteration and the metric projections onto Ck and Qk are easily executed. López et al. [10] introduced a new self-adaptive step size to improve the CQ and the relaxed CQ algorithm. For more effective algorithms and the extensions of the SFP, the readers can see [12, 19, 20] and the survey papers [2, 7]. It is noted that all these algorithms only use the current point to get the next iteration, which did not use the previous iteration points xk-1,xk-2,…, and affect the flexibility. Using some information of previous iterative points will increase the flexibility of the algorithm.In this paper, inspired by the inertial projection algorithms for convex feasibility problem [9], we propose a memory gradient projection algorithm for solving the SFP, which employs xk and xk-1, θk to get the next point xk+1. In this case, it can improve the convergence greatly, since the vector xk-xk-1 is acting as an impulsion term and θk is acting as a speed regulator. Compared with the existing methods for solving the SFP, the algorithm presented in this paper has the following advantages: (1) When the projections PC and PQ are not easily calculated, at each iteration of this algorithm, it only needs to compute the projection onto a halfspace containing the given closed convex set and being related to the current iterative point, which is implemented very easily. (2) At each iteration, the step size can be directly computed which need not compute the largest eigenvalue of the related matrix, estimate the Lipschitz constant, or use some line search scheme. (3) It employs two previous iterations to get the next iteration and hence improves the flexibility of the algorithm.The rest of the paper is organized as follows. In Section2, we present some useful preliminaries. In Section 3, we introduce a memory gradient projection method for solving the SFP and prove its convergence property. Section 4 introduces the relaxed version of the memory gradient projection method proposed in Section 3 for solving the SFP and establishes its convergence property. Section 5 highlights the main conclusions of this paper.


## 2. Preliminaries

In this section, we review some definitions and basic results which will be used in this paper. Throughout the paper,·,· and · denote the usual inner product and norm in Rn.For a given nonempty closed convex subsetΩ in Rn, the metric projection from Rn onto Ω is defined by (5)PΩx=argmin⁡x-y∣y∈Ω,x∈Rn.It has the following well-known properties.Lemma 1 (see [17]).
LetΩ be a nonempty closed convex subset in Rn; then for any x,y∈Rn and z∈Ω,(1)
〈PΩ(x)-x,z-PΩ(x)〉≥0;(2)
PΩ(x)-PΩ(y)2≤〈PΩ(x)-PΩ(y),x-y〉;(3)
PΩ(x)-z2≤x-z2-PΩ(x)-x2.Remark 2.
From part (1) of Lemma1, for any x,y∈Rn and z∈Ω, we have (6)PΩx-x,z-x≥PΩx-x2.
From part (2) of Lemma1, we know that PΩ is a nonexpansive operator; that is, for any x,y∈Rn, (7)PΩx-PΩy≤x-y.
The lemma below will be useful for the convergence analysis of our algorithm.Lemma 3 (see [11]).
Suppose that{ψk}⊂0,∞ and δk⊂0,∞ satisfy(a)
ψk+1-ψk≤θk(ψk-ψk-1)+δk;(b)
∑kδk<∞;(c)
{θk}⊂0,θ, where θ∈0,1.
Then,{φk} is a convergent sequence and ∑k[ψk+1-ψk]+<∞, where [t]+≔max⁡{t,0} (for any t∈RN).The following lemma provides some important properties of the subdifferential.Lemma 4 (see [21]).
Supposeh:Rn→R is a convex function; then it is subdifferentiable everywhere and its subdifferentials are uniformly bounded on any bounded subset of Rn.


## 3. Memory Gradient Projection Algorithm and Its Convergence

In this section, assuming that the projectionsPC and PQ are easily calculated, we first establish a memory gradient projection algorithm for solving the split feasibility problem and then prove that the sequence of the iterative points generated by the algorithm converges to a solution of the SFP.Algorithm 5.
Given anyx0,x1∈RN, for k=1,2,…,
calculate(8)yk=xk+θkxk-xk-1.
Let(9)xk+1=PCyk+λkATPQ-IAyk,where θk⊂[0,θ], θ∈0,1, and λk=(PQ-I)Ayk2/AT(PQ-I)Ayk2.Remark 6.
Evidently, whenθk=0, Algorithm 5 happens to be the Algorithm  3.1 of [14] with ωk=1. At each iteration, the step size λk can be directly computed which avoids computing the largest eigenvalue of the related matrix, estimating the Lipschitz constant, and using some line search scheme as in some existing methods in the literature. Here, the term θk and two iterative points xk-1, xk are employed to get the next iterative point xk+1, hence improving the flexibility of the algorithm.Now we give the convergence analysis of Algorithm5.Theorem 7.
Assuming that the solution set of the SFP is nonempty, choosingθk satisfies the following conditions:(i)
For anyk∈N, θk⊂[0,θ] and θ∈[0,1).(ii)
∑θkxk-xk-12<∞.Then, for anyx0,x1∈RN, the sequence generated by Algorithm 5 converges to a solution of the SFP.Proof.
Letx∗ be any solution of the SFP. Then, x∗∈C and Ax∗∈Q.(10)yk-x∗2=xk+θkxk-xk-1-x∗2=xk-x∗2-2θkxk-x∗,xk-1-xk+θk2xk-1-xk2.It is easy to see that, for any vector a,b∈Rn, we have (11)a,b=12a+b2-12a2-12b2.So, we can rewrite the relation above as (12)2θkxk-x∗,xk-1-xk=θkxk-1-x∗2-xk-x∗2-xk-1-xk2,yk-x∗2=xk-x∗2-θkxk-1-x∗2-xk-x∗2+θk1+θkxk-1-xk2.From Lemma 1, we have(13)yk-x∗,ATI-PQAyk=Ayk-Ax∗,I-PQAyk≥Ayk-PQAyk2.Thus, (14)xk+1-x∗2=PCyk+λkATPQ-IAyk-x∗2≤yk+λkATPQ-IAyk-x∗2=yk-x∗2-2λkyk-x∗,ATI-PQAyk+λk2ATPQ-IAyk2≤yk-x∗2-2λkPQ-IAyk2+λk2ATPQ-IAyk2(15)=yk-x∗2-λk2ATPQ-IAyk2(16)≤yk-x∗2(17)≤xk-x∗2+θkxk-x∗2-xk-1-x∗2+θk1+θkxk-1-xk2(18)≤xk-x∗2+θkxk-x∗2-xk-1-x∗2+2θkxk-1-xk2.Let φk=xk-x∗2. Then from (18), we get (19)φk+1-φk≤θkφk-φk-1+2θkxk-xk-12.Thanks to Lemma 3, we conclude that {φk} is convergent; that is, xk-x∗ is convergent. The proofs above imply that {xk} is bounded. Meanwhile, {yk}, {AT(PQ-I)Ayk} are also bounded. Due to ∑θkxk-xk-12<∞, we have (20)limk→∞⁡θkxk-xk-12=0.Combining with (15), (16), and (18), we obtain that(21)limk→∞⁡λk2ATPQ-IAyk2=0.Because of the boundedness of {AT(PQ-I)Ayk}, (22)limk→∞⁡λk2ATPQ-IAyk4=0.That is, (23)limk→∞⁡PQ-IAyk=0.Let x¯ be any accumulation point of {xk}. Then there exists a subsequence {xki} which converges to x¯. Since C is a closed convex set, x¯∈C.
On the other hand, the construction ofyk and (20) clarify that yki→x¯. By using (23), we can get (24)limki→∞⁡PQ-IAyki=0.Thus, (25)Ax¯=PQAx¯.That is, (26)Ax¯∈Q.Therefore, x¯ is a solution of the SFP.
Thus we may usex¯ in place of x∗ in (18) and obtain that xk-x¯ is convergent. Because there is a subsequence xki-x¯ converging to 0, then xk→x¯ as k→∞. This completes the proof.


## 4. The Relaxed Memory Gradient Projection Algorithm and Its Convergence

In this section, assuming that the projectionsPC and PQ are not easily calculated, we present the relaxed version of the memory gradient projection algorithm presented in Section 3. Carefully speaking, the convex sets C and Q satisfy the following assumptions:(H1) The setC is given by (27)C=x∈RN∣cx≤0,where c:RN→R is a convex (not necessarily differentiable) function and C is nonempty.The setQ is given by (28)Q=y∈RM∣qy≤0,where q:RM→R is a convex (not necessarily differentiable) function and Q is nonempty.(H2) For anyx∈RN, at least one subgradient ξ∈∂c(x) can be calculated, where ∂c(x) is a generalized gradient of c(x) at x and is defined as follows: (29)∂cx=ξ∈RN∣cz≥cx+ξ,z-x∀z∈RN.For any y∈RM, at least one subgradient η∈∂q(y) can be calculated, where (30)∂qy=η∈RM∣qu≥qy+η,u-y∀u∈RM.We now formally state the relaxed version of Algorithm5.Algorithm 8.
Given anyx0,x1∈RN, for k=1,2,…,
calculate(31)yk=xk+θkxk-xk-1.
Let(32)xk+1=PCkyk+λkATPQk-IAyk,where θk⊂[0,θ], θ∈[0,1), λk=PQk-IAyk2/ATPQk-IAyk2, (33)Ck=x∈RN∣cxk+ξk,x-xk≤0,where ξk is an element in ∂c(xk), and (34)Qk=y∈RM∣qAxk+ηk,y-Axk≤0,where ηk is an element in ∂q(Axk).Remark 9.
(
1
) By the definition of subgradient, it is clear that the halfspaces Ck and Qk contain C and Q, respectively. From the expressions of Ck and Qk, the metric projections onto Ck and Qk may be directly calculated (see [22, 23]). (2) Compared with Algorithm 5, when the projections PC and PQ are not easily calculated, it only needs to compute the projection onto a halfspace containing the given closed convex set and being related to the current iterative point at each iteration of Algorithm 8, which is implemented very easily.Now, we establish the global convergence of Algorithm8.Theorem 10.
Suppose that the solution set of the SFP is nonempty. Choosingθk satisfies the following conditions:(1)
For anyk∈N, θk⊂0,θ, and θ∈0,1.(2)
∑θkxk-xk-12<∞.
Then, for anyx0,x1∈RN, the sequence generated by Algorithm 8 converges to a solution of the SFP.Proof.
Letx∗ be any solution of the SFP. Then x∗∈C and Ax∗∈Q. Following the same line as in the proof of Theorem 7, we can also get that (35)xk+1-x∗2≤yk-x∗2-λk2ATPQ-IAyk2(36)≤yk-x∗2(37)≤xk-x∗2+θkxk-x∗2-xk-1-x∗2+2θkxk-1-xk2.Let φk=xk-x∗2. Then, from (37), we get (38)φk+1-φk≤θkφk-φk-1+2θkxk-xk-12.Thanks to Lemma 3, we conclude that {φk} is convergent, that is, xk-x∗ is convergent. The proofs above imply that {xk} is bounded. Meanwhile, {yk}, {AT(PQk-I)Ayk} are also bounded. Due to ∑θkxk-xk-12<∞, we get (39)limk→∞⁡θkxk-xk-12=0.Combining with (35)–(37), we obtain that (40)limk→∞⁡λk2ATPQk-IAyk2=0.Thus(41)limki→∞⁡λki2ATPQki-IAyki2=0.Let x¯ be any accumulation point of {xk}. Then there exists a subsequence {xki}, which converges to x¯. Thanks to the boundedness of {AT(PQk-I)Ayk}, (42)limki→∞⁡λki2ATPQki-IAyki4=0.That is, (43)limki→∞⁡PQki-IAyki=0.Noting that PQki(Ayki)∈Qki, by the definition of Qk, we get (44)qAyki+ηki,PQkiAyki-Ayki≤0.Since (45)yki=xki+θkixki-xki-1,∑θkxk-xk-12<∞,θk⊂0,θ,θ∈0,1,we obtain that yki→x¯ and xki-xki-1→0. From Lemma 4, we know that {ηk} is bounded. Passing onto the limit in (44), we get that q(Ax¯)≤0, which implies that Ax¯∈Q.
On the other hand, becausexki+1∈Cki, by the definition of Ck, we get (46)Cxki+ξki,xki+1-xki≤0.Lemma 4 implies that {ξk} is bounded. Passing onto the limit in (46), we have (47)Cx¯≤0,which implies that x¯∈C.
Thereforex¯ is a solution of the SFP.
Thus we may usex¯ in place of x∗ in (37) and obtain that {xk-x¯} is convergent. Because there is a subsequence {xki-x¯} converging to 0, then xk→x¯ as k→∞. This completes the proof.


## 5. Concluding Remarks

In this paper, we present a memory gradient projection method for solving the split feasibility problem, which employs a parameter and two previous iterations to get the next iteration, and its step size can be calculated directly. It not only improves the convergence and the flexibility greatly of the algorithm, but also avoids computing the largest eigenvalue of the related matrix or estimating the Lipschitz constant in each iteration. Theoretical convergence results are established under some suitable conditions. The main idea of this paper can be extended to design some analogous algorithms for solving some related convex optimization problems, such as the convex feasibility problem [7] and the multiple-sets split feasibility problem [24].



---

*Source: 4123168-2018-01-08.xml*