# Relaxed Extragradient Algorithms for  the Split Feasibility Problem

Authors: Youli Yu; Shin Min Kang; Young Chel Kwun
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

The purpose of this paper is to introduce a new relaxed extragradient algorithms for the split feasibility problem. Our relaxed extragradient algorithm is new and it generalized some results for solving the split feasibility problem.


---

## Body

## 1. Introduction

The split feasibility problem has received much attention due to its applications in image denoising, signal processing, and image reconstruction, with particular progress in intensity modulated therapy; see, for instance [1–4]. In this paper, we continue to study the split feasibility problem and its approximation algorithms.To begin with, let us first recall the notation of the split feasibility problem and some existing algorithms in the literature. Recall that the split feasibility problem introduced by Censor and Elfving [4] can be formulated as finding a point x† with the property
(1)x†∈ℂ,𝔸x†∈ℚ,
where ℂ and ℚ are two closed convex subsets of two Hilbert spaces ℍ1 and ℍ2, respectively, and 𝔸:ℍ1→ℍ2 is a bounded linear operator. The original algorithm introduced in [4] involves the computation of the inverse 𝔸-1:
(2)xk+1=𝔸-1projℚ(proj𝔸(ℂ)(𝔸xk)),k≥0,
where ℂ, ℚ⊂ℝn are closed convex sets and 𝔸 is a full rank n×n matrix. It is an interesting problem to construct iterative algorithms for the split feasibility problem to the bounded linear operator.We useΞ to denote the solution set of the split feasibility problem; that is,
(3)Ξ≔{x†∈ℂ:𝔸x†∈ℚ}.
In the sequel, we assume that the split feasibility problem is consistent. Let ϖ>0 and assume that x†∈Ξ. Thus, 𝔸x†∈ℚ. It follows that projℚ𝔸x†=𝔸x† which implies ϖ𝔸*(I-projℚ)𝔸x†=0. Hence, we deduce that the fixed point equation (I-ϖ𝔸*(I-projℚ)𝔸)x†=x† holds. Note that x†∈ℂ. It is obvious that
(4)projℂ(I-ϖ𝔸*(I-projℚ)𝔸)x†=x†.
By using (4), Byrne [5] presented a more popular CQ algorithm:
(5)xk+1=projℂ(xk-ϖ𝔸*(I-projℚ)𝔸xk),n∈ℕ.
The CQ algorithm only needs to compute the projections projℂ and projℚ. It is therefore implementable when projℂ and projℚ have closed-form expressions. Consequently, CQ algorithm has received so much attention; see [6–17]. In particular, in [14], Xu proposed an averaged CQ algorithm and he obtained the weak convergence result.On the other hand, we note thatx∈Ξ; then there exists x†∈ℚ such that 𝔸x-x†=0. Thus, we consider the distance function d(𝔸x,x†)=∥𝔸x-x†∥ and the minimization problem
(6)min⁡x∈ℂ,x†∈ℚ12∥𝔸x-x†∥2.
Since x†∈ℚ, we then consider the minimization
(7)min⁡x∈ℂφ(x)≔12∥𝔸x-projℚ𝔸x∥2.
However, (7) is, in general, ill-posed. We import the well-known Tikhonov’s regularization method
(8)min⁡x∈ℂφα≔12∥(I-projℚ)𝔸x∥2+12α∥x∥2,
where α>0 is the regularization parameter. Note that the gradient ∇φα of φα is
(9)∇φα=∇φ(x)+αI=𝔸*(I-projℚ)𝔸+αI.
Using (9), some regularized methods have been suggested. For example, Xu [14] suggested the following regularized method:
(10)xk+1=projℂ(I-ϖk∇φαk)xk=projℂ((1-αkϖk)xk-ϖkA*(I-projℚ)𝔸xk).
He proved that the sequence {xk} generated by (10) converges to the solution of the split feasibility problem. Ceng et al. [7] presented the following extragradient method:
(11)x0=x∈ℍ1chosenarbitrarily,yk=projℂ(xk-ϖk∇φαk(xk)),xk+1=βkxk+(1-βk)projℂ(xk-ϖk∇φαk(yk)),hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhn≥0.
and proved that the sequence {xk} generated by (11) converges weakly to the solution of the split feasibility problem. Motivated by the above results, in this paper, we construct a new extragradient algorithm for solving the split feasibility problem. Strong convergence result is demonstrated.


## 2. Preliminaries

Letℂ be a nonempty closed convex subset of a real Hilbert space ℍ. A mapping Θ:ℂ→ℂ is called nonexpansive if
(12)∥Θu-Θv∥≤∥u-v∥,∀u,v∈ℂ.
A mapping W:ℂ→ℂ is said to be ν-inverse strong monotone, if there exists a constant ν>0 such that
(13)〈u-v,Wu-Wv〉≥ν∥Wu-Wv∥2,∀u,v∈ℂ.
Recall that the metric projection from ℍ onto ℂ denoted by projℂ means that
(14)∥x⋆-projℂ(x⋆)∥=inf⁡⁡{∥x⋆-x∥:x∈ℂ}.projℂ can be characterized by
(15)〈u-v,projℂ(u)-projℂ(v)〉≥∥projℂ(u)-projℂ(v)∥2,
for all u,v∈H. Hence, it is nonexpansive. It is also known that 2projℂ-I is nonexpansive.Letφ:ℂ→ℍ be a monotone mapping. The variational inequality problem is to find x†∈ℂ such that
(16)〈φ(x†),x-x†〉≥0,∀x∈ℂ.
The solution set of the variational inequality is denoted by VI⁡(ℂ,φ). It is well known that x♯∈VI⁡(ℂ,φ) if and only if x♯=projℂ(x♯-λφ(x♯)), ∀λ>0. A set-valued mapping R:ℍ→2ℍ is called monotone if, for each u∈ℍ, f∈Ru, and g∈Rv, we have
(17)〈u-v,f-g〉≥0.
A monotone mapping R:ℍ→2ℍ is called maximal if its graph G(R) is not properly contained in the graph of any other monotone mappings. It is known that a monotone mapping R is maximal if and only if for each pair (x,f)∈ℍ×ℍ with 〈u-v,f-g〉≥0 for every (v,g)∈G(R); then we have f∈Ru. Let R:ℂ→ℍ be a monotone and k-Lipschitz continuous mapping and let Nℂv be the normal cone to ℂ at v∈ℂ; that is,
(18)NKv={w∈ℍ:〈v-u,w〉≥0,∀u∈ℂ}.
Define
(19)Wv={Rv+Nℂv,ifv∈ℂ,∅,ifv∉ℂ.
Then, W is maximal monotone and 0∈Wv if and only if v∈VI⁡(ℂ,R); see [18] for more details.Lemma 1 (see [14]).
One knows the following properties:(i)
𝔸*(I-projℚ)𝔸 is Lipschitz continuous with Lipschitz constant ∥𝔸∥2;(ii)
𝔸*(I-projℚ)𝔸 is 1/∥𝔸∥2 inverse strong monotone;(iii)
I-ϖ𝔸*(I-projℚ)A is nonexpansive for all ϖ∈(0,2/∥𝔸∥2).Lemma 2 (see [19]).
Letℂ be a nonempty closed convex subset of a real Hilbert space ℍ. Let the mapping Φ:ℂ→ℍ be ζ-inverse strong monotone and let ϱ>0 be a constant. Then, we have
(20)∥(I-ϱΦ)x†-(I-ϱΦ)x‡∥2≤∥x†-x‡∥2+ϱ(ϱ-2ζ)∥Φ(x†)-Φ(x‡)∥2,hhhhhhhhhhhhhhhhhhhhhhhhhhhhh∀x†,x‡∈C.
In particular, if 0≤ϱ≤2ζ, then I-ϱΦ is nonexpansive.Lemma 3 (see [20]).
Let{ιk} and {σk} be bounded sequences in a Banach space X and let {βk} be a sequence in [0,1] with 0<liminf⁡n→∞βk≤limsup⁡n→∞βk<1. Suppose that
(21)ιk+1=(1-βk)σk+βkιk
for all n≥0 and
(22)limsup⁡n→∞(∥σk+1-σk∥-∥ιk+1-ιk∥)≤0.
Then, lim⁡n→∞∥σk-ιk∥=0.Lemma 4 (see [21]).
Assume that{ξk} is a sequence of nonnegative real numbers such that
(23)ξk+1≤(1-γk)ξk+ϑk,
where {γk} is a sequence in (0,1) and {ϑk} is a sequence such that(1)
∑n=1∞‍γk=∞;(2)
limsup⁡n→∞(ϑk/γk)≤0 or ∑n=1∞|ϑk|<∞.Then, lim⁡n→∞ξk=0.


## 3. Main Results

Letℍ1 and ℍ2 be two Hilbert spaces and let ℂ, ℚ be two nonempty closed and convex subsets of ℍ1 and ℍ2, respectively. Suppose that 𝔸:ℍ1→ℍ2 is a bounded linear operator and 𝔽:ℂ→ℍ1 is a ι-contraction. We will state and prove our main results in this paper and at the end of this paper we will give an example to show that our results improve the works in the literature.Algorithm 5.
Letx0∈ℂ. Let {xk} be a sequence generated by
(24)yk=projℂ[xk-δk𝔸*(I-projℚ)𝔸xk+αk(𝔽xk-xk)],xk+1=projℂ[xk-λk𝔸*(I-projℚ)𝔸yk+μk(yk-xk)],xk-λk𝔸*(I-projℚ)𝔸yk+μk(yk-xk)μkμkμkiin≥ℕ,
where {αk}⊂(0,1) is a sequence; δk,λk∈[a,b]⊂(0,2/∥𝔸∥2) and μk∈(0,1) are sequences satisfying λk≤2μk/∥𝔸∥2.Theorem 6.
Suppose thatΞ≠∅. Assume lim⁡n→∞αk=0, lim⁡n→∞(λk+1-λk)=0, lim⁡n→∞(δk+1-δk)=0, lim⁡n→∞(μk+1-μk)=0, and ∑n=1∞‍αk=∞. Then the sequence {xk} generated by (24) converges strongly to ν~=PΞ(𝔽)ν~.Proof.
From the assumptionslim⁡n→∞αk=0 and δk∈(0,2/∥𝔸∥2), we can choose αk such that αk<1-(δk∥𝔸∥2/2) when n is sufficiently large. For the convenience and without loss of generality, we assume that αk<1-(δk∥𝔸∥2/2) for all n∈ℕ. Then, we deduce δk/(1-αk)∈(0,2/∥𝔸∥2) for all n∈ℕ.
Letx†∈Ξ. In the first section, we know that x†=projℂ[x†-ξ𝔸*(I-projℚ)𝔸x†] for any ξ>0. Since δk/(1-αk)∈(0,2/∥𝔸∥2) and λk/μk∈(0,2/∥𝔸∥2), we have
(25)x†=projℂ[x†-δk𝔸*(I-projℚ)𝔸x†(1-αk)]=projℂ[(x†-δk𝔸*(I-projℚ)𝔸x†1-αk)]αkx†+(1-αk)hhhhhhh×(x†-δk𝔸*(I-projℚ)𝔸x†(1-αk))],∀n≥ℕ,(26)x†=projℂ[x†-λkμk𝔸*(I-projℚ)Ax†]=projℂ[×(x†-λkμk𝔸*(I-projℚ)𝔸x†)]αkx†+(1-αk)hhhhhhh×(x†-λkμk𝔸*(I-projℚ)𝔸x†)],∀n≥ℕ.
From (24) and (25), we have
(27)∥yk-x†∥=∥projℂ[δk𝔸*(I-projℚ)𝔸xk]αk𝔽xk+(1-αk)xkhhhhhhhh-δk𝔸*(I-projℚ)𝔸xk]-x†∥=∥projℂ[xk-δk𝔸*(I-projℚ)𝔸xk1-αkαk𝔽xk+(1-αk)hhhhhhhh×(xk-δk𝔸*(I-projℚ)𝔸xk(1-αk))]-projℂ[(x†-δk𝔸*(I-projℚ)𝔸x†1-αk)]αkx†+(1-αk)hhhhhhhhhh×(x†-δk𝔸*(I-projℚ)𝔸x†(1-αk))]∥≤∥-(x†-δk𝔸*(I-projℚ)𝔸x†(1-αk))∥αk(𝔽xk-x†)+(1-αk)×[(xk-δk𝔸*(I-projℚ)𝔸xk(1-αk))hhhhhh-(x†-δk𝔸*(I-projℚ)𝔸x†(1-αk))]∥.
From Lemma 1, we know that I-δk𝔸*(I-projℚ)𝔸/(1-αk) and I-λk/μk𝔸*(I-projℚ)𝔸 are nonexpansive. It follows that
(28)∥yk-x†∥≤(1-αk)∥(I-δk(1-αk)𝔸*(I-projℚ)𝔸)xk-(I-δk(1-αk)𝔸*(I-projℚ)𝔸)x†∥+αk∥𝔽xk-𝔽x†∥+αk∥𝔽x†-x†∥≤αkι∥xk-x†∥+αk∥𝔽x†-x†∥+(1-αk)∥xk-x†∥=[1-(1-ι)αk]∥xk-x†∥+αk∥𝔽x†-x†∥.
Thus,
(29)∥xk+1-x†∥=∥projℂ[xk-λk𝔸*(I-projℚ)𝔸ykprojccc+μk(yk-xk)[xk-λk𝔸*(I-projℚ)𝔸yk]-x†∥=∥projℂ[(yk-λkμk𝔸*(I-projℚ)𝔸yk)](1-μk)xkhhhhhhhhhh+μk(yk-λkμk𝔸*(I-projℚ)𝔸yk)]-projℂ[(x†-λkμk𝔸*(I-projℚ)𝔸x†)](1-μk)x†hhhhhhhhhh+μk(x†-λkμk𝔸*(I-projℚ)𝔸x†)]∥≤(1-μk)∥xk-x†∥+μk∥(yk-λkμk𝔸*(I-projℚ)𝔸yk)hhhhhhhh-(x†-λkμk𝔸*(I-projℚ)𝔸x†)∥≤(1-μk)∥xk-x†∥+μk∥yk-x†∥≤(1-μk)∥xk-x†∥+μkαk∥𝔽x†-x†∥+μk[1-(1-ι)αk]∥xk-x†∥=(1-(1-ι)μkαk)∥xk-x†∥+μkαk∥𝔽x†-x†∥≤max⁡⁡{∥𝔽x†-x†∥1-ι,∥x0-x†∥}.
Hence, {xk} is bounded. It follows from (28) that the sequence {yk} is also bounded.
Set𝕊=2projℂ-I. Note that S is nonexpansive. Thus, we can rewrite xk+1 in (24) as
(30)xk+1=I+𝕊2[(1-μk)xk+μk(yk-λkμk𝔸*(I-projℚ)𝔸yk)]=1-μk2xk+μk2(yk-λkμk𝔸*(I-projℚ)𝔸yk)+12𝕊((1-μk)xk+μk(yk-λkμk𝔸*(I-projℚ)𝔸yk))=1-μk2xk+1+μk2zk,
where
(31)zk=[𝕊((1-μk)xk+μk(yk-λkμk𝔸*(I-projℚ)𝔸yk))]μk(yk-λkμk𝔸*(I-projℚ)𝔸yk)+𝕊((1-μk)xk+μk(yk-λkμk𝔸*(I-projℚ)𝔸yk))]×(1+μk)-1.
It follows that
(32)zk+1-zk=μk+1[(yk+1-λk+1μk+1𝔸*(I-projℚ)𝔸yk+1)+𝕊(μk+1(yk+1-λk+1μk+1𝔸*(I-projℚ)𝔸yk+1))(1-μk+1)xk+1+μk+1×(yk+1-λk+1μk+1𝔸*(I-projℚ)𝔸yk+1))]×(1+μk+1)-1-μk[(yk-λkμk𝔸*(I-projℚ)𝔸yk))](yk-λkμkA*(I-projℚ)Ayk)+𝕊((yk-λkμk𝔸*(I-projℚ)𝔸yk))(1-μk)xk+μk(yk-λkμk𝔸*(I-projℚ)𝔸yk))]×(1+μk)-1.
So,
(33)∥zk+1-zk∥≤μk+11+μk+1∥(yk+1-λk+1μk+1𝔸*(I-projℚ)𝔸yk+1)-(yk-λkμk𝔸*(I-projℚ)𝔸yk)∥+|μk+11+μk+1-uk1+μk|×∥yk-λkμk𝔸*(I-projℚ)𝔸yk∥+11+μk+1×∥S((1-μk)xk+μk(yk-λkμk𝔸*(I-projℚ)𝔸yk))∥𝕊[(yk+1-λk+1μk+1𝔸*(I-projℚ)𝔸yk+1)](1-μk+1)xk+1+μk+1×(yk+1-λk+1μk+1𝔸*(I-projℚ)𝔸yk+1)]-S((yk-λkμk𝔸*(I-projℚ)𝔸yk))(1-μk)xk+μk×(yk-λkμk𝔸*(I-projℚ)𝔸yk))∥+|11+μk+1-11+μk|×∥μk(yk-λkμk𝔸*(I-projℚ)𝔸yk))∥𝕊(μk(yk-λkμk𝔸*(I-projℚ)𝔸yk))(1-μk)xk+μk(yk-λkμk𝔸*(I-projℚ)𝔸yk))∥≤μk+11+μk+1∥(I-λk+1μk+1A*(I-projℚ)𝔸)yk+1-(I-λk+1μk+1𝔸*(I-projℚ)𝔸)yk∥+μk+11+μk+1|λk+1μk+1-λkμk|∥𝔸yk∥+|μk+11+μk+1-uk1+μk|×∥yk-λkμk𝔸*(I-projℚ)𝔸yk∥+11+μk+1∥μk(yk-λkμk𝔸*(I-projℚ)𝔸yk)∥(1-μk+1)xk+1+μk+1×(yk+1-λk+1μk+1𝔸*(I-projℚ)𝔸yk+1)-(1-μk)xk-μk(yk-λkμk𝔸*(I-projℚ)𝔸yk)∥+|11+μk+1-11+μk|×∥𝕊(μk(yk-λkμk𝔸*(I-projℚ)𝔸yk))(1-μk)xk+μk(yk-λkμk𝔸*(I-projℚ)𝔸yk))∥.
It follows that
(34)∥zk+1-zk∥≤μk+11+μk+1∥yk+1-yk∥+μk+11+μk+1|λk+1μk+1-λkμk|∥𝔸yk∥+|μk+11+μk+1-uk1+μk|×∥yk-λkμk𝔸*(I-projℚ)𝔸yk∥+11+μk+1×∥-(I-λk+1μk+1𝔸*(I-projℚ)𝔸)yk](1-μk+1)(xk+1-xk)+(μk-μk+1)(xk-yk)+μk+1[(I-λk+1μk+1𝔸*(I-projℚ)𝔸)yk+1-(I-λk+1μk+1𝔸*(I-projℚ)𝔸)yk]+(λk-λk+1)𝔸*(I-projℚ)𝔸yk-(I-λk+1μk+1𝔸*(I-projℚ)𝔸)yk]∥+|11+μk+1-11+μk|×∥𝕊(μk(yk-λkμk𝔸*(I-projℚ)𝔸yk))(1-μk)xk+μk(yk-λkμk𝔸*(I-projℚ)𝔸yk))∥≤2μk+11+μk+1∥yk+1-yk∥+1-μk+11+μk+1∥xk+1-xk∥+μk+11+μk+1|λk+1μk+1-λkμk|∥𝔸yk∥+|μk-μk+1|1+μk+1∥xk-yk∥+|μk+11+μk+1-uk1+μk|×∥yk-λkμk𝔸*(I-projℚ)𝔸yk∥+|11+μk+1-11+μk|×∥𝕊(μk(yk-λkμk𝔸*(I-projℚ)𝔸yk))(1-μk)xk+μk(yk-λkμk𝔸*(I-projℚ)𝔸yk))∥+|λk-λk+1|1+μk+1∥𝔸*(I-projℚ)𝔸yk∥.
From (24), we have
(35)∥yk+1-yk∥=∥projℂ[δk+1𝔸*(I-projℚ)𝔸xk+1]αk+1𝔽xk+1+(1-αk+1)xk+1-δk+1𝔸*(I-projℚ)𝔸xk+1]-projℂ[δk𝔸*(I-projℚ)𝔸xk]αk𝔽xk+(1-αk)xk-δk𝔸*(I-projℚ)𝔸xk]∥≤∥[δk+1𝔸*(I-projℚ)𝔸xk+1]αk+1𝔽xk+1+(1-αk+1)xk+1-δk+1𝔸*(I-projℚ)𝔸xk+1]-[αk𝔽xk+(1-αk)xk-δk𝔸*(I-projℚ)𝔸xk]∥≤∥(I-δk+1𝔸*(I-projℚ)𝔸)xk+1-(I-δk+1𝔸*(I-projℚ)𝔸)xk∥+αk+1∥𝔽xk+1-xk+1∥+|δk+1-δk|×∥𝔸*(I-projℚ)𝔸xk∥+αk∥𝔽xk-xk∥≤∥xk+1-xk∥+|δk+1-δk|∥𝔸*(I-projℚ)𝔸xk∥+αk+1∥𝔽xk+1-xk+1∥+αk∥𝔽xk-xk∥.
Hence, we deduce
(36)∥zk+1-zk∥≤∥xk+1-xk∥+|δk+1-δk|∥𝔸*(I-projℚ)𝔸xk∥+αk+1∥𝔽xk+1-xk+1∥+αk∥𝔽xk-xk∥+μk+11+μk+1|λk+1μk+1-λkμk|∥𝔸yk∥+|μk+11+μk+1-uk1+μk|∥yk-λkμk𝔸*(I-projℚ)𝔸yk∥+|μk-μk+1|1+μk+1∥xk-yk∥+|11+μk+1-11+μk|×∥𝕊((1-μk)xk+μk(yk-λkμk𝔸*(I-projℚ)𝔸yk))∥+|λk-λk+1|1+μk+1∥𝔸*(I-projℚ)𝔸yk∥.
Since lim⁡n→∞αk=0, lim⁡n→∞(λk+1-λk)=0, lim⁡n→∞(δk+1-δk)=0, and lim⁡n→∞(μk+1-μk)=0, we derive that
(37)limsup⁡n→∞(∥zk+1-zk∥-∥xk+1-xk∥)≤0.
By Lemma 3, we obtain
(38)lim⁡n→∞∥zk-xk∥=0.
Hence,
(39)lim⁡n→∞∥xk+1-xk∥=lim⁡n→∞1+μk2∥zk-xk∥=0.
By Lemma 1, Lemma 2, and (29), we get
(40)∥xk+1-x†∥2≤(1-μk)∥xk-x†∥2+μk∥yk-x†∥2≤(1-μk)∥xk-x†∥2+μk∥(x†-δk1-αk𝔸*(I-projℚ)𝔸x†)]∥αk(𝔽xk-x†)+(1-αk)×[(xk-δk(1-αk)𝔸*(I-projℚ)𝔸xk)-(x†-δk(1-αk)𝔸*(I-projℚ)𝔸x†)]∥2≤μk[(I-δk1-αk𝔸*(I-projℚ)𝔸)x†∥2]αk∥𝔽xk-x†∥2+(1-αk)×∥(I-δk(1-αk)𝔸*(I-projℚ)𝔸)xk-(I-δk(1-αk)𝔸*(I-projℚ)𝔸)x†∥2]+(1-μk)∥xk-x†∥2≤μkδk(δk1-αk-2∥𝔸∥2)×∥𝔸*(I-projℚ)𝔸xk-𝔸*(I-projℚ)𝔸x†∥2+(1-αk)μk∥xk-x†∥2+(1-μk)∥xk-x†∥2+αkμk∥𝔽xk-x†∥2≤μka(b1-αk-2∥𝔸∥2)×∥𝔸*(I-projℚ)𝔸xk-𝔸*(I-projℚ)𝔸x†∥2+αk∥𝔽xk-x†∥2+∥xk-x†∥2.
Therefore, we have
(41)μka(2∥𝔸∥2-b(1-αk))×∥𝔸*(I-projℚ)𝔸xk-A*(I-projℚ)𝔸x†∥2≤αk∥𝔽xk-x†∥2+∥xk-x†∥2-∥xk+1-x†∥2≤αk∥𝔽xk-x†∥2+(∥xn-x†∥+∥xk+1-x†∥)×∥xk-xk+1∥.
Noting that 0<a<λk<2μk/∥𝔸∥2, we get liminf⁡n→∞μk>0. Since lim⁡n→∞αk=0 and b<2/∥𝔸∥2, we obtain liminf⁡n→∞μka(2/∥𝔸∥2-b/(1-αk))>0. Thus, we have
(42)lim⁡n→∞∥𝔸*(I-projℚ)𝔸xk-𝔸*(I-projℚ)𝔸x†∥=0.
Using (15), we have
(43)∥yk-x†∥2=∥projℂ[αk𝔽xk+(1-αk)xk-δk𝔸*(I-projℚ)𝔸xk]-projℂ[x†-δk𝔸*(I-projℚ)𝔸x†]∥2≤〈αk𝔽xk+(1-αk)xk-δk𝔸*(I-projℚ)𝔸xk-(x†-δk𝔸*(I-projℚ)𝔸x†),yk-x†〉=12{(yk-x†)∥2}∥xk-δk𝔸*(I-projℚ)𝔸xk-(x†-δk𝔸*(I-projℚ)𝔸x†)+αk(𝔽xk-xk)∥2+∥yk-x†∥2-∥αk𝔽xk+(1-αk)xk-δk𝔸*(I-projℚ)𝔸xk-(x†-δk𝔸*(I-projℚ)𝔸x†)-(yk-x†)∥2}≤12{αk(Fxk-xk)∥2}∥(xk-δk𝔸*(I-projℚ)𝔸xk)-(x†-δk𝔸*(I-projℚ)𝔸x†)∥2+2αk∥𝔽xk-xk∥×∥xk-δk𝔸*(I-projℚ)𝔸xk-(x†-δk𝔸*(I-projℚ)𝔸x†)+αk(𝔽xk-xk)∥+∥yk-x†∥2-∥(xk-yk)-δk(𝔸*(I-projℚ)𝔸xk-𝔸*(I-projℚ)𝔸x†)+αk(Fxk-xk)∥2}≤12{𝔸*(I-projℚ)𝔸x†)+αk(𝔽xk-xk)∥2}αk(𝔽xk-xk)∥2}∥(xk-δk𝔸*(I-projℚ)𝔸xk)-(x†-δk𝔸*(I-projℚ)𝔸x†)∥2+αkM+∥yk-x†∥2-∥(xk-yk)-δk(𝔸*(I-projℚ)𝔸xk-𝔸*(I-projℚ)𝔸x†)+αk(𝔽xk-xk)∥2}≤12{αk(𝔽xk-xk)∥2}∥xk-x†∥2+αkM+∥yk-x†∥2-∥xk-yk∥2+2αk〈xk,xk-yk〉+2δk〈xk-yk,𝔸*(I-projℚ)𝔸xk-𝔸*(I-projℚ)𝔸x†〉-∥δk(𝔸*(I-projℚ)𝔸xk-𝔸*(I-projℚ)𝔸x†)-αk(𝔽xk-xk)∥2}≤12{∥xk-x†∥2+αkM+∥yk-x†∥2-∥xk-yk∥2+2αk∥𝔽xk-xk∥∥xk-yk∥+2δk∥xk-yk∥×∥𝔸*(I-projℚ)𝔸xk-𝔸*(I-projℚ)𝔸x†∥{∥xk-x†∥2+αkM+∥yk-x†∥2},
where M>0 is some constant such that
(44)sup⁡k{αk(𝔽xk-xk)∥}2∥xk∥∥xk-δk𝔸*(I-projℚ)𝔸xkhhhhhhhhhh-(x†-δk𝔸*(I-projℚ)𝔸x†)hhhhhhhhhh+αk(𝔽xk-xk)∥}≤M.
It follows that
(45)∥yk-x†∥2≤∥xk-x†∥2+αkM-∥xk-yk∥2+2αk∥𝔽xk-xk∥∥xk-yk∥+2δk∥xk-yk∥×∥𝔸*(I-projℚ)𝔸xk-𝔸*(I-projℚ)𝔸x†∥,
and hence
(46)∥xk+1-x†∥2≤(1-μk)∥xk-x†∥2+μk∥yk-x†∥2≤∥xk-x†∥2+αkM-μk∥xk-yk∥2+2αk∥𝔽xk-xk∥∥xk-yk∥+2δk∥xk-yk∥×∥𝔸*(I-projℚ)𝔸xk-𝔸*(I-projℚ)𝔸x†∥
which implies that
(47)μk∥xk-yk∥2≤(∥xk-x†∥+∥xk+1-x†∥)∥xk+1-xk∥+αkM+2αk∥𝔽xk-xk∥∥xk-yk∥+2δk∥xk-yk∥×∥𝔸*(I-projℚ)𝔸xk-𝔸*(I-projℚ)𝔸x†∥.
Since αk→0,∥xn-xk+1∥→0 and ∥𝔸*(I-projℚ)𝔸xk-𝔸*(I-projℚ)𝔸x†∥→0, we derive
(48)lim⁡n→∞∥xk-yk∥=0.
Next we show that(49)limsup⁡n→∞〈ν~-𝔽ν~,ν~-yk〉≤0,
where ν~=PΞ(𝔽ν~). To show it, we choose a subsequence {yni} of {yk} such that
(50)lim⁡sup⁡n→∞〈ν~-𝔽ν~,ν~-yk〉=lim⁡i→∞〈ν~-𝔽ν~,ν~-yni〉.
Since {yk} is bounded and {yni} is then bounded, we have the fact that a subsequence {ynij} of {yni} converges weakly to z.
Next we show thatz∈Ξ. We define a mapping W by
(51)Wv={𝔸*(I-projℚ)𝔸v+Nℂv,v∈ℂ,∅,v∉ℂ.
Then W is maximal monotone. Let (v,w)∈G(W). Since w-𝔸*(I-projℚ)𝔸v∈Nℂv and yk∈ℂ, we get
(52)〈v-yk,w-𝔸*(I-projℚ)𝔸v〉≥0.
On the other hand, from yk=projℂ[αk𝔽xk+(1-αk)xk-δk𝔸*(I-projℚ)𝔸xk], we have
(53)〈v-yk,yk-αk𝔽xk-(1-αk)xk+δk𝔸*(I-projℚ)𝔸xk〉≥0.
That is,
(54)〈v-yk,(yk-xk)δk+𝔸*(I-projℚ)𝔸xk+αkδk(xk-𝔽xk)(yk-xk)δk〉≥0.
Therefore, we have
(55)〈v-yni,w〉≥〈v-yni,𝔸v〉≥〈v-yni,𝔸*(I-projℚ)𝔸v〉-〈v-yni,(yni-xni)δni+𝔸*(I-projℚ)𝔸xni+αniδni(I-𝔽)xni(yk-xk)δk〉=〈(yk-xk)δkv-yni,𝔸*(I-projℚ)𝔸v-𝔸*(I-projℚ)𝔸xni-(yni-xni)δni-αniδni(I-𝔽)xni(yk-xk)δk〉=〈v-yni,𝔸*(I-projℚ)𝔸v-𝔸*(I-projℚ)𝔸yni〉-〈v-yni,(yni-xni)δni+αniδni(I-𝔽)xni〉+〈v-yni,𝔸*(I-projℚ)𝔸yni-𝔸*(I-projℚ)𝔸xni〉≥〈v-yni,𝔸*(I-projℚ)𝔸yni-𝔸*(I-projℚ)𝔸xni〉-〈v-yni,(yni-xni)δni+αniδni(I-𝔽)xni〉.
Noting that αni→0, ∥yni-xni∥→0 and 𝔸*(I-projℚ)𝔸 is Lipschitz continuous, we deduce from above
(56)〈v-z,w〉≥0.
Since W is maximal monotone, we have z∈W-1(0) and hence
(57)z∈VI⁡(ℂ,𝔸*(I-projℚ)𝔸)=Ξ.
Therefore,
(58)limsup⁡n→∞〈ν~-𝔽ν~,ν~-yk〉=lim⁡i→∞〈ν~-𝔽ν~,ν~-yni〉=〈ν~-𝔽ν~,ν~-z〉≤0.
Again from (15), we have
(59)∥yk-ν~∥2=∥projℂ[(xk-δk1-αk𝔸*(I-projℚ)𝔸xk)]αk𝔽xk+(1-αk)×(xk-δk(1-αk)𝔸*(I-projℚ)𝔸xk)]-projℂ[(ν~-δk1-αk𝔸*(I-projℚ)𝔸ν~)]αkν~+(1-αk)×(ν~-δk(1-αk)𝔸*(I-projℚ)𝔸ν~)]∥2≤〈(ν~-δk1-αk𝔸*(I-projℚ)𝔸ν~)],yk-ν~〉αk(𝔽xk-ν~)+(1-αk)×[(xk-δk(1-αk)𝔸*(I-projℚ)𝔸xk)-(ν~-δk(1-αk)𝔸*(I-projℚ)𝔸ν~)],yk-ν~〉≤αk〈ν~-𝔽xk,ν~-yk〉+(1-αk)×∥(xk-δk(1-αk)𝔸*(I-projℚ)𝔸xk)-(ν~-δk(1-αk)𝔸*(I-projℚ)𝔸ν~)∥∥yk-ν~∥≤αk〈ν~-𝔽ν~,ν~-yk〉+αk〈𝔽ν~-𝔽xk,ν~-yk〉+(1-αk)∥xk-ν~∥∥yk-ν~∥≤αk〈ν~-𝔽ν~,ν~-yk〉+αk∥𝔽ν~-𝔽xk∥×∥ν~-yk∥+(1-αk)∥xk-ν~∥∥yk-ν~∥≤αk〈ν~-𝔽ν~,ν~-yk〉+[1-(1-ι)αk]∥xk-ν~∥∥yk-ν~∥≤αk〈ν~-𝔽ν~,ν~-yk〉+1-(1-ι)αk2∥xk-ν~∥2+12∥yk-ν~∥2.
Hence,
(60)∥yk-ν~∥2≤[1-(1-ι)αk]∥xk-ν~∥2+2αk〈ν~-𝔽ν~,ν~-yk〉.
Therefore,
(61)∥xk+1-ν~∥2≤(1-μk)∥xk-ν~∥2+μk∥yk-ν~∥2≤[1-μk(1-ι)αk]∥xk-ν~∥2+2μkαk〈ν~-𝔽ν~,ν~-yk〉.
We apply Lemma 4 to the last inequality to deduce that xk→ν~. This completes the proof.



---

*Source: 468079-2014-03-27.xml*