# A Perturbed Projection Algorithm with Inertial Technique for Split Feasibility Problem

Authors: Yazheng Dang; Yan Gao; Yanli Han
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

This paper deals with the split feasibility problem that requires to find a point closest to a closed convex set in one space such that its image under a linear transformation will be closest to another closed convex set in the image space. By combining perturbed strategy with inertial technique, we construct an inertial perturbed projection algorithm for solving the split feasibility problem. Under some suitable conditions, we show the asymptotic convergence. The results improve and extend the algorithms presented in Byrne (2002) and in Zhao and Yang (2005) and the related convergence theorem.


---

## Body

## 1. Introduction

LetC⊂Rn and Q⊂Rm be nonempty closed convex sets, and let A be an m×n real matrix. The split feasibility problem (SFP) is to find a point(1.1)x∈CsuchthatAx∈Q.This problem was first presented and analyzed by Censor and Elfving [1] and appeared in signal processing, image reconstruction [2], and so on. Many well-known iterative algorithms for solving (1.1) were established, see the papers [3–5]. Denoted by PS, the orthogonal projection operator onto convex set S, that is(1.2)PS(x)=arg⁡min⁡⁡‖c-x‖,c∈S,
where ∥·∥ indicates the 2-norm. The CQ algorithm proposed by Byrne in [6] has the following iterative process:
(1.3)xk+1=PC(xk+γAT(PQ-I)Axk),k≥0,
where γ∈(0,2/L), L denotes the largest eigenvalue of the matrix ATA, and I is the identity operator.In some cases, it is difficult or even impossible to compute orthogonal projection; to avoid computing projection, Zhao and Yang in [7] proposed the perturbed projections algorithm for the SFP. This development was based on results of Santos and Scheimberg [8] who suggested replacing each nonempty closed convex set of the convex feasibility problem by a convergent sequence of supersets. If such supersets can be constructed with reasonable efforts and projecting onto them is simpler than projecting onto the original convex sets, then a perturbed algorithm is favorable. The concrete iterative process of perturbed CQ algorithm [7] is as follows:(1.4)xk+1=(1-αk)xk+αkPCk(xk+γAT(PQk-I)(Axk)),
where αk∈[0,1], γ∈(0,2/L), L, I defined as in algorithm (1.3), and Ck→MC and Qk→MQ (see the definitions in the Section 2), while the perturbed projections algorithm sometime converges slowly by reason of using only the current point to get the next iterative point.Many papers have studied the inertial-type extrapolation recently, see [9–12], which uses the term θk and the two previous iterative points xk-1, xk to get the next iterative point xk+1. As an acceleration process, it can considerably improve the speed of convergence for the following causes: one is that the vector xk-xk-1 acts as an impulsion term, the other is that the parameter θk acts as a speed regulator.To the best of our knowledge, no publications deal with perturbed projection algorithm and inertial process simultaneously. In this paper, we apply the inertial technique to the perturbed projection algorithm to get a perturbed inertial projection algorithm for the split feasibility problem. The results improve and extend the algorithms presented in [6] and in [7] and the related convergence theorem.The paper is organized as follows. In Section2, some preliminaries are given. The inertial perturbed algorithm and the corresponding convergence theorem for the split feasibility problem are presented in Section 3.


## 2. Preliminaries

Throughout the rest of the paper,I denotes the identity operator, Fix(T) denotes the fixed points of an operator T, that is, Fix(T)∶={x∣x=T(x)}.An operatorT is said to be nonexpansive (ne) if(2.1)‖T(x)-T(y)‖≤‖x-y‖.
It is well known that the projection operator is nonexpansive.Recall the following notions of the convergence andρ-distance.Definition 2.1.
LetN be an operator on a Hilbert space H; let Nk,k=0,1,2,… be a family of operators on a Hilbert space. {Nk} is said to be convergent to N if ∥Nk(x)-N(x)∥→0 as k→+∞ for all x∈H.Definition 2.2.
Theρ-distance (ρ≥0) for operators N1 and N2 on H is given by
(2.2)Dρ(N1,N2)=sup⁡‖x‖≤ρ⁡‖N1(x)-N2(x)‖.Now we introduce the Mosco-convergence for sequences of sets in a reflexive Banach space.Definition 2.3 (see [13]).
LetX be a reflexive Banach space and C and {Ck}k∈N (N is a set of natural numbers) a sequence of subsets of X. The sequence {Ck}k∈N is Mosco-convergent to C, denoted by Ck→MC, if
(2.3)(1)∀x∈C,∃{xk}k∈Nwithxk∈Ck(k∈N)suchthatxk⟶Xsx,(2)∀{kj}j∈N,∀{xj}j∈N,xj∈Ckj(j∈N),xj⟶Xwx⟹x∈C,
where Xs and Xw denote the strong and weak topologies, respectively. In particular, if {Ck} and C are in Rn, then Ck→MC is equivalent to
(2.4)(1)∀x∈C,∃{xk}k∈N,xk∈Ck(k∈N)suchthatxk⟶x,(2)∀{kj}j∈N,∀{xj}j∈N,xj∈Ckj(j∈N),xj⟶x⟹x∈C.Using the notation NCCS(Rn) for the family of nonempty closed convex subsets of Rn, let C and Ck be sets in NCCS(Rn), for k=0,1,…. It is easy to verify that if the sequence {Ck} converges to C in the Mosco sense, then the operator sequence {PCk} converges to PC.Definition 2.4.
LetC1 and C2 be elements in NCCS(Rn). The ρ-distance is defined by
(2.5)dρ(C1,C2)=sup⁡‖x‖2≤ρ⁡‖PC1(x)-PC2(x)‖2.
LetC and Ck be sets in NCCS(Rn), then Ck→MC if and only if dρ(Ck,C)→0 for all ρ≥0.The following lemmas will be used in convergence analysis later on.Lemma 2.5 (see [14]).
Let{δk} and {γk} be nonnegative sequences satisfying ∑kδk<+∞ and γk+1≤γk+δk, k=0,1,…. Then, {γk} is a convergent sequence.Lemma 2.6 (see [10]).
Letϕk∈[0,∞), k=1,2,…, and δk∈[0,∞), k=1,2,… satisfying(1)
ϕk+1-ϕk≤θk(ϕk-ϕk-1)+δk,(2)
∑kδk<∞,(3)
θk∈[0,θ], k=1,2,…, where θ∈[0,1).Then, {ϕk} is a converging sequence and ∑k(ϕk+1-ϕk)+<∞, where (t)+∶=max{t,0} for any t∈R.Lemma 2.7 (Opial [15]).
LetH be a Hilbert space, and let {xk} be a sequence in H such that there exists a nonempty set S⊂H satisfying:(1)
for everyx*∈S,limk∥xk-x*∥ exists,(2)
any weak cluster point of{xk} belongs to S.Then, there exists x¯*∈S such that {xk} weakly converges to x¯*.Lemma 2.8 (see [15]).
LetH be a Hilbert space, T:H→H a nonexpansive operator, and y a weak cluster point of a sequence {xk}, and let ∥T(xk)-xk∥→0. Then y∈Fix(T).


## 3. The Inertial Perturbed Algorithm and the Asymptotic Convergence for the SPF

LetC and Ck be sets in NCCS(Rn), and let Q and Qk be sets in NCCS(Rm), for k=0,1,…, with Ck→MC and Qk→MQ. Then dρ(Ck,C)→0 and dρ(Qk,Q)→0 for all ρ>0. We denote
(3.1)N=PCU,U=I-γAT(I-PQ)A,Nk=PCkUk,Uk=I-γAT(I-PQk)A.
From Lemma  3.1 in [5], we know that x* solves the SFP (1.1) if and only if x*∈Fix(N).It is well known that the operatorAT(I-PQ)A is λ-Lipschitz continuous with λ=ρ(ATA). The same is true for the operators AT(I-PQk)A for k=0,1,…; it is easy to obtain the following conclusion.Lemma 3.1 (see [7]).
LetC and Ck be sets in NCCS(Rn), and let Q and Qk be sets in NCCS(Rm), for k=0,1,…, with Ck→MC and Qk→MQ. Then, the operators N and Nk defined in (3.1) are nonexpansive operators for γ∈(0,2/λ). Moreover, the operator sequence {Nk} converges to N.Now we give the perturbed inertial KM-type algorithm for SFP.Algorithm 3.2.
Given arbitrary elements inRn for k=0,1,…, let
(3.2)xk+1=[(1-αk)I+αkNk](yk),yk=xk+θk(xk-xk-1),
where Nk=PCk[(I-γAT(I-PQk)A), αk∈(0,1), for any k and γ∈(0,2/λ) with λ=ρ(ATA), {θk}⊂[0,θ], θ∈[0.1).The following theorem is necessary for the convergence analysis of Algorithm3.2.Theorem 3.3.
LetN and Nk for k=0,1,2,… be nonexpansive (ne) operators in finite-dimensional Hilbert space, with Nk→N, and let {αk} be a sequence in (0,1) satisfying
(3.3)∑k=0+∞αk(1-αk)=+∞,(3.4)∑k=0+∞αkDρ(Nk,N)<+∞
for all ρ>0. Then, the sequence {xk} defined by the iterative step
(3.5)xk+1=(1-αk)yk+αkNk(yk),(3.6)yk=xk+θk(xk-xk-1)
converges to a fixed point of N provided that we choose parameter θk satisfying
(3.7){θk}⊂[0,θ̅k],withθ̅k∶=min⁡⁡{θ,1max⁡⁡{k2‖xk-xk-1‖2,k2‖xk-xk-1‖}},θ∈[0,1),
whenever such fixed points exist.Proof.
We first prove that the sequence{xk} is bounded and {∥xk-z∥} is convergent for all z∈Fix(N), where Fix(N) denotes the set of the fixed points of the operator N, that is, N(z)=z. Since N and Nk are ne operators, we have
(3.8)‖xk+1-z‖=‖(1-αk)yk+αkNk(yk)-(1-αk)z-αkN(z)‖≤(1-αk)‖yk-z‖+αk‖Nk(yk)-N(z)‖≤(1-αk)‖yk-z‖+αk‖Nk(yk)-Nk(z)‖+αk‖Nk(z)-N(z)‖≤‖yk-z‖+αkDρ¯(Nk,N)=‖xk+θk(xk-xk-1)-z‖+αkDρ¯(Nk,N)≤‖xk-z‖+θk‖xk-xk-1‖+αkDρ¯(Nk,N),
where ρ¯≥∥z∥. From the selection of parameter θk, we have
(3.9)θk‖xk-xk-1‖≤‖xk-xk-1‖max⁡⁡{k2‖xk-xk-1‖2,k2‖xk-xk-1‖}≤1k2.
It is easy to get
(3.10)∑k≥0‖xk-xk-1‖<∞.
By (3.4), (3.8)-(3.10), we obtain from Lemma 2.5 that the sequence {∥xk-z∥} is convergent and hence the sequence {xk} is bounded.
We next prove thatliminfk→∞∥yk-N(yk)∥=0. Let ek=Nk(yk)-N(yk) and notice the fact that
(3.11)‖λx+(1-λ)y‖2=λ‖x‖2+(1-λ)‖y‖2-λ(1-λ)‖x-y‖2.
Then, we have
(3.12)‖xk+1-z‖2=‖(1-αk)(yk-z)+αk(Nk(yk)-N(yk))+αk(N(yk)-N(z))‖2=‖(1-αk)(yk-z+αkek)+αk(N(yk)-N(z)+αkek)‖2=(1-αk)‖yk-z+αkek‖2+αk‖N(yk)-N(z)+αkek‖2-αk(1-αk)‖yk-N(yk)‖2≤(1-αk)[‖yk-z‖2+2αk‖yk-z‖‖ek‖+αk2‖ek‖2]+αk[‖N(yk)-N(z)‖2+2αk‖N(yk)-N(z)‖‖ek‖+αk2‖ek‖2]-αk(1-αk)‖yk-N(yk)‖2≤‖yk-z‖2+2αk‖yk-z‖‖ek‖+αk2‖ek‖2-αk(1-αk)‖yk-N(yk)‖2.
From (3.6), we obtain
(3.13)‖yk-z‖2=‖(xk-z)-θk(xk-1-xk)‖2=‖xk-z‖2-2θk〈xk-z,xk-1-xk〉+θk2‖xk-1-xk‖2.
By (3.12) and observing that θk2≤θk (since θk∈[0,1]), we have
(3.14)‖xk+1-z‖2≤‖xk-z‖2-2θk〈xk-z,xk-1-xk〉+θk‖xk-1-xk‖2+2αk‖yk-z‖‖ek‖+αk2‖ek‖2-αk(1-αk)‖yk-N(yk)‖2.
Combining 〈a,b〉=-(1/2)∥a-b∥2+(1/2)∥a∥2+(1/2)∥b∥2 with (3.14), we get
(3.15)‖xk+1-z‖2-‖xk-z‖2≤θk(‖xk-z‖2-‖xk-1-z‖2)+2θk‖xk-1-xk‖2+2αk‖yk-z‖‖ek‖+αk2‖ek‖2-αk(1-αk)‖yk-N(yk)‖2≤θk(‖xk-z‖2-‖xk-1-z‖2)+2θk‖xk-1-xk‖2+2αk(‖xk-z‖+θk‖xk-1-xk‖)‖ek‖+αk2‖ek‖2-αk(1-αk)‖yk-N(yk)‖2.
We have known that the sequence {xk} is bounded and {∥xk-z∥} is convergent; hence, there exist ρ≥ρ¯>0 and G>0 such that ∥xk∥≤ρ and ∥xk-z∥≤G for all k.
Thus(3.16)‖ek‖=‖Nk(yk)-N(yk)‖≤Dρ(Nk,N).
Moreover, one has that
(3.17)‖xk+1-z‖2-‖xk-z‖2≤θk(‖xk-z‖2-‖xk-1-z‖2)+2θk‖xk-1-xk‖2+2αkGDρ(Nk,N)+2αkθk‖xk-1-xk‖Dρ(Nk,N)+αk2Dρ(Nk,N)2-αk(1-αk)‖yk-N(yk)‖2.
Denoting
(3.18)σk=2θk‖xk-1-xk‖2+2αkGDρ(Nk,N)+2αkθk‖xk-1-xk‖Dρ(Nk,N)+αk2Dρ(Nk,N)2,
we get
(3.19)‖xk+1-z‖2-‖xk-z‖2≤θk(‖xk-z‖2-‖xk-1-z‖2)+σk.
Similarly, from the selection of parameter θk, we have
(3.20)θk‖xk-xk-1‖2≤‖xk-xk-1‖2max⁡⁡{k2‖xk-xk-1‖2,k2‖xk-xk-1‖}≤1k2.
It is easy to get
(3.21)∑k≥0‖xk-xk-1‖2<∞.
Both (3.10) and (3.21) manifest
(3.22)∑k≥0αkθk‖xk-1-xk‖Dρ(Nk,N)<∞.
Then, from (3.4), (3.21), and (3.22), we get
(3.23)∑k=0+∞σk<+∞.
According to Lemma 2.6, we obtain ∑k≥0[∥xk-z∥2-∥xk-1-z∥2]+<∞.
From (3.17), it follows that
(3.24)∑k=0+∞αk(1-αk)‖yk-N(yk)‖2<+∞.
Because of (3.3) ∑k=0+∞αk(1-αk)=+∞, we conclude that liminfk→∞∥yk-N(yk)∥=0.
Finally, we prove that{xk} converges to a fixed point of N. From the above computation, we know that the sequence {yk} is also bounded; hence there exist x* and a subsequence of {yk} (denoted {ykl}) such that
(3.25)lim⁡l→∞⁡‖ykl-x*‖=0,lim⁡l→∞⁡‖ykl-N(ykl)‖=lim⁡inf⁡k→∞⁡‖yk-N(yk)‖=0.
From Lemmas 2.7 and 2.8, we have x*∈Fix(N). It is easy to obtain that liml→∞∥xkl-x*∥=0, because ∥yk-xk∥=θk∥xk-xk-1∥→0 by (3.10). Since {∥xk-x*∥} is convergent, it follows that limk→∞∥xk-x*∥=liml→∞∥xkl-x*∥=0. The proof is completed.Remark 1.
Since the current value of∥xk-xk-1∥ is known when choosing the parameter θk, then θk is well defined in Theorem 3.3. In fact, from the process of proof for the Theorem 3.3, we can get the following assert: the convergence result of Theorem 3.3 always holds provided that we select θk∈[0,θ], θ∈[0,1), forallk≥0 with
(3.26)∑k≥0‖xk-xk-1‖<∞,∑k≥0‖xk-xk-1‖2<∞.Now let us return to the convergence analysis of Algorithm3.2.Theorem 3.4.
Let the hypotheses in Lemma3.1 be satisfied. Then the sequence {xk} generated by (3.2) converges to a fixed point of N if
(3.27)∑k=0+∞αk(1-αk)=+∞,∑k=0+∞αk(dρ¯(Ck,C)+2λ-1/2dρ¯(Qk,Q))<+∞,ρ¯>0,
where parameter θk is satisfying (3.10) and (3.21).Proof.
For anyy∈Rn, ∥y∥≤ρ, by reason of the nonexpansive properties of projection, we have
(3.28)‖Nk(y)-N(y)‖=‖PCk(y-γAT(I-PQk)Ay)-PC(y-γAT(I-PQ)Ay)‖≤‖PCk(y-γAT(I-PQk)Ay)-PCk(y-γAT(I-PQ)Ay)‖+‖PCk(y-γAT(I-PQ)Ay)-PC(y-γAT(I-PQ)Ay)‖≤γ‖AT(I-PQk)Ay-AT(I-PQ)Ay‖+‖PCk(y-γAT(I-PQ)Ay)-PC(y-γAT(I-PQ)Ay)‖≤γλ1/2‖PQk(Ay)-PQ(Ay)‖+‖PCk(y-γAT(I-PQ)Ay)-PC(y-γAT(I-PQ)Ay)‖≤2λ-1/2‖PQk(Ay)-PQ(Ay)‖+‖PCk(y-γAT(I-PQ)Ay)-PC(y-γAT(I-PQ)Ay)‖.
Obviously,
(3.29)Dρ(Nk,N)≤dρ̅(Ck,C)+2λ-1/2dρ̅(Qk,Q),
where ρ̅≥max{∥Ay∥,∥y-γAT(I-PQ)Ay∥}.
Since∑k=0+∞αk(dρ¯(Ck,C)+2λ-1/2dρ¯(Qk,Q))<+∞ for any given ρ¯>0, the result of this theorem can be obtained using Theorem 3.3.



---

*Source: 207323-2012-05-29.xml*