# An Implicit Algorithm for the Split Fixed Point and Convex Feasibility Problems

Authors: Fengjun Guo; Shin Min Kang; Young Chel Kwun
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

We consider an implicit algorithm for the split fixed point and convex feasibility problems. Strong convergence theorem is obtained.


---

## Body

## 1. Introduction

Due to their broad applicability in many areas, especially in signal processing (e.g., phase retrieval) and image restoration, the split feasibility problems continue to receive great attention; see, for example, [1–6]. The present paper is devoted to this topic. Now we recall that the split feasibility problem originally introduced by Censor and Elfving [7] is to find x† such that
(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. A special case of (1) is when ℚ={b} is singleton, and then (1) is reduced to the convexly constrained linear inverse problem
(2)x†∈ℂ,𝔸x†=b,
which has received considerable attention. We can use projected Landweber algorithm to solve (2). The projected Landweber algorithm generates a sequence {xk} in such a way that
(3)xk+1=projℂ(xk+γ𝔸*(b-𝔸xk)),
where projℂ denotes the nearest point projection from ℍ1 onto ℂ, γ>0 is a parameter such that 0<γ<2/∥𝔸∥2, and 𝔸* is the transpose of 𝔸. When the system (2) is reduced to the unconstrained linear system
(4)𝔸x*=b,
then the projected Landweber algorithm is turned to the Landweber algorithm
(5)xk+1=xk+γ𝔸*(b-𝔸xk).
Note that (1) is equivalent to the fixed point equation
(6)x†=projℂ(I-η𝔸*(I-projℚ)𝔸)x†.
Using this relation, we can suggest the following iterative algorithm:
(7)xk+1=projℂ(xk-ζ𝔸*(I-projℚ)𝔸xk),k∈ℕ,
which is refereed as ℂℚ algorithm and was devised by Byrne [8]. ℂℚ algorithm has been extensively studied; see, for instance, [9–11].Theℂℚ algorithm (7) is proved to converge weakly but fails to converge in norm in general infinite-dimensional Hilbert spaces ℍ1 and ℍ2. Tikhonov's regularization method can solve this problem. First, we define a convex function f by
(8)f(x)=12∥𝔸x-projℚ𝔸x∥2
with its gradient
(9)∇f(x)=𝔸*(I-projℚ)𝔸x
and consider the minimization problem
(10)minx∈ℂf(x).
It is known that x*∈ℂ solves (1) if and only if f(x*). We know that (10) is ill-posed. So regularization is needed. We consider Tikhonov's regularization:
(11)minx∈ℂfα(x):=12∥(I-projℚ)𝔸x∥2+12α∥x∥2,
where α>0 is the regularization parameter. The gradient ∇fα of fα is given by
(12)∇fα(x)=∇f(x)+αx=𝔸*(I-projℚ)𝔸x+αx.
Define a Picard iterates
(13)xαk+1=projℂ(I-δ(𝔸*(I-projℚ)𝔸+αI))xαk,k∈ℕ.
Xu [12] proves that if (1) is solvable, then as k→∞, xαk→xα and consequently the strong limα→0xα exists and is the minimum-norm solution of (1). Note that (13) is a double-step iteration. Xu [12] introduced a single step regularized method:
(14)xk+1=projℂ(I-δk∇fξk)xk=projℂ((1-ξkδk)xk-δk𝔸*(I-projℚ)𝔸xk),k∈ℕ.
It is shown that the sequence {xk} generated by (14) converges to the solution of (1) provided that the parameters {ξk}⊂(0,1) and {δk}⊂(0,ξn/(∥A∥2+ξn)) satisfy
(15)limk→∞ξk=0,∑k=1∞‍ξkδk=∞,limk→∞|δk+1-δk|+δk|ξk+1-ξk|(ξk+1δk+1)2=0.Inspired by (14), Ceng et al. [3] introduced the following relaxed extragradient method:
(16)yk=projℂ(xk-ξk(∇f(xk)+θkxk)),xk+1=βkxk+γkyk+δkprojℂ×(xk-ξk(∇f(yk)+θkyk)),k∈ℕ,
where the sequences {θk}⊂(0,1), {βk}⊂(0,1), {γk}⊂(0,1), {δk}⊂(0,1), and {ξk}⊂(0,θk/(∥A∥2+θk)2) satisfy the conditions
(17)limk→∞θk=limk→∞ξk=limk→∞|ξk+1-ξk|+ξk|θk+1-θk|θk+13ξk+12δk+1=0,∑k=1∞‍θk2ξkδk=∞,2δk∥A∥2+θk≤γkξk
for all k∈ℕ. Ceng et al. proved that the sequence {xk} generated by (16) converges to the solution of (1) which is the the minimum-norm element. Recently, Ceng et al. [13] further introduced another regularization for the split feasibility problem and the fixed point problem:
(18)yk=projℂ(xk-γk(∇f(xk)+θkxk)),xk+1=ϑkxk+(1-ϑk)×Uprojℂ(xk-γk(∇f(yk)+θkyk)),k∈ℕ.
Ceng et al. proved that algorithm (18) has weak convergence.Motivated by the above works, in this paper, our main purpose is to introduce an implicit algorithm for solving the split fixed point and convex feasibility problems. We show that the implicit algorithm converges strongly to the solution of the split fixed point and convex feasibility problems.


## 2. Preliminaries

Letℍ be a real Hilbert space with inner product 〈·,·〉 and norm ∥·∥, respectively. Let ℂ be a nonempty closed convex subset of ℍ.Definition 1.
A mapping𝕌:ℂ→ℂ is called nonexpansive if
(19)∥𝕌p-𝕌q∥≤∥p-q∥
for all p,q∈ℂ.We will useFix(𝕌) to denote the set of fixed points of 𝕌; that is, Fix(𝕌)={x‡∈C:x‡=𝕌x‡}.Definition 2.
A mapping𝒞:ℂ→ℂ is called  contractive if
(20)∥𝒞(p)-𝒞(q)∥≤κ∥p-q∥
for all p,q∈ℂ and for some constant κ∈(0,1). In this case, we call 𝒞 a κ-contraction.Definition 3.
A linear bounded operator𝔹:ℍ→ℍ is called  strongly positive if there exists a constant γ->0 such that
(21)〈𝔹x‡,x‡〉≥γ-∥x‡∥2
for all x‡∈ℍ.Definition 4.
We call thatprojℂ:ℍ→ℂ is the metric projection if for each x‡∈ℍ(22)∥x‡-projℂ(x‡)∥=inf{∥x‡-x∥:x∈ℂ}.It is well known that the metric projectionprojℂ:ℍ→ℂ is characterized by
(23)〈x‡-projℂ(x‡),x-projℂ(x‡)〉≤0
for all x‡∈ℍ, x∈ℂ. From this, we can deduce that projℂ is firmly nonexpansive; that is,
(24)∥projℂ(x‡)-projℂ(x)∥2≤〈x‡-x,projℂ(x‡)-projℂ(x)〉
for all x‡,x∈ℍ. Hence projℂ is nonexpansive.Lemma 5 (see [14]).
Letℂ be a closed convex subset of a real Hilbert space ℍ, and let 𝕌:ℂ→ℂ be a nonexpansive mapping. Then, the mapping I-𝕌 is demiclosed. That is, if {xk} is a sequence in C such that xk→x§ weakly and (I-𝕌)xk→y strongly, then (I-𝕌)x§=y.


## 3. Main Result

In this section, we first introduce our algorithm for solving this problem and consequently we give convergence analysis.Letℍ1 and ℍ2 be two Hilbert spaces and ℂ⊂ℍ1 and ℚ⊂ℍ2 two nonempty closed convex sets. Let 𝔸:ℍ1→ℍ2 be a bounded linear operator with its adjoint 𝔸*. Let 𝔹 be a strongly positive bounded linear operator on ℍ1 with coefficient γ->0. Let 𝒞:ℍ1→ℍ1 be a κ-contraction. Let 𝕍:ℚ→ℚ and 𝕌:ℂ→ℂ be two nonexpansive mappings.In the sequel, our objective is to(25)Findx†∈ℂ∩Fix(𝕌)suchthat𝔸x†∈ℚ∩Fix(𝕍).
We use Ω to denote the solution set of (25); that is,
(26)Ω={x†∣x†∈ℂ∩Fix(𝕌),𝔸x†∈ℚ∩Fix(𝕍)}.Now, we introduce the following implicit algorithm.Algorithm 6.
Define an implicit algorithm{xt} as follows:
(27)xt=tζ𝒞(xt)+(I-t𝔹)𝕌projℂ×(xt-δ𝔸*(I-𝕍projℚ)𝔸xt),t∈(0,1),
where ζ∈(0,γ-/κ) and δ∈(0,1/∥A∥2) are two constants.Remark 7.
{
x
t
} is well-defined. Define a mapping ℝ:ℂ→ℂ as
(28)ℝx=projℂ(x-δ𝔸*(I-𝕍projℚ)𝔸x),∀x∈ℂ.
Then, we have
(29)∥ℝx-ℝy∥2=∥projℂ(x-δ𝔸*(I-𝕍projℚ)𝔸x)-projℂ(y-δ𝔸*(I-𝕍projℚ)𝔸y)∥2≤∥(x-δ𝔸*(I-𝕍projℚ)𝔸x)-(y-δ𝔸*(I-𝕍projℚ)𝔸y)∥2=∥(x-y)+δ𝔸*×[(𝕍projℚ𝔸x-𝔸x)-(𝕍projℚ𝔸y-𝔸y)]×[(𝕍projℚ𝔸x-𝔸x)-(𝕍projℚ𝔸y-𝔸y)]∥2=∥x-y∥2+2δ〈x-y,𝔸*[(𝕍projℚ𝔸x-𝔸x)-(𝕍projℚ𝔸y-𝔸y)]〉+δ2∥𝔸*[(𝕍projℚ𝔸x-𝔸x)-(𝕍projℚ𝔸y-𝔸y)]∥2=∥x-y∥2+2δ〈𝔸(x-y),(𝕍projℚ𝔸x-𝔸x)-(𝕍projℚ𝔸y-𝔸y)〉+δ2∥𝔸*[(𝕍projℚ𝔸x-𝔸x)-(𝕍projℚ𝔸y-𝔸y)]∥2=∥x-y∥2+2δ〈𝕍projℚ𝔸x-𝕍projℚ𝔸y,(𝕍projℚ𝔸x-𝔸x)-(𝕍projℚ𝔸y-𝔸y)〉-2δ∥(𝕍projℚ𝔸x-𝔸x)-(𝕍projℚ𝔸y-𝔸y)∥2+δ2∥𝔸*[(𝕍projℚ𝔸x-𝔸x)-(𝕍projℚ𝔸y-𝔸y)]∥2=∥x-y∥2+δ(∥𝕍projℚ𝔸x-𝕍projℚ𝔸y∥2+∥(𝕍projℚ𝔸x-𝔸x)-(𝕍projℚ𝔸y-𝔸y)∥2-∥𝔸x-𝔸y∥2∥𝕍projℚ𝔸x-𝕍projℚ𝔸y∥2)-2δ∥(𝕍projℚ𝔸x-𝔸x)-(𝕍projℚ𝔸y-𝔸y)∥2+δ2∥𝔸*[(𝕍projℚ𝔸x-𝔸x)-(𝕍projℚ𝔸y-𝔸y)]∥2≤∥x-y∥2-δ∥(𝕍projℚ𝔸x-𝔸x)-(𝕍projℚ𝔸y-𝔸y)∥2+δ2∥𝔸∥2∥(𝕍projℚ𝔸x-𝔸x)-(𝕍projℚ𝔸y-𝔸y)∥2≤∥x-y∥2.
This indicates that R is nonexpansive. Consequently, for fixed t∈(0,1), we have that the mapping tζ𝒞+(I-t𝔹)𝕌R is contractive due to the facts that 𝒞 is a κ-contraction and 𝕌 is nonexpansive. Therefore, {xt} is well-defined.Next, we prove the convergence of (27).Theorem 8.
Suppose thatΩ≠∅. Then the net {xt} generated by algorithm (25) converges strongly to p†=projΩ(ζ𝒞+I-𝔹)p† which solves the following variational inequality:
(30)〈(ζ𝒞-𝔹)x,y-x〉≤0,∀y∈Ω.Proof.
Setrt=projℚ𝔸xt, vt=xt-δ𝔸*(I-𝕍projℚ)𝔸xt, and ut=projℂ(xt-δ𝔸*(I-𝕍projℚ)𝔸xt) for all t∈(0,1). Then ut=projℂvt. It is clear that the solution of (30) is unique. Let p†=projΩ(ζ𝒞+I-𝔹)p†. Then, we have p†∈ℂ∩Fix(𝕌) and 𝔸p†∈ℚ∩Fix(𝕍). First, we easily deduce the following three inequalities:
(31)∥rt-𝔸p†∥=∥projℚ𝔸xt-𝔸p†∥≤∥𝔸xt-𝔸p†∥,(32)∥ut-p†∥=∥projℂvt-p†∥≤∥vt-p†∥,(33)∥𝕍rt-𝔸p†∥2≤∥rt-𝔸p†∥2≤∥𝔸xt-𝔸p†∥2-∥rt-𝔸xt∥2.
From (25), we have
(34)∥xt-p†∥=∥t(ζ𝒞(xt)-𝔹p†)+(I-t𝔹)(𝕌ut-p†)∥≤tζ∥𝒞(xt)-𝒞(p†)∥+t∥ζ𝒞(p†)-𝔹p†∥+(1-tγ-)∥ut-p†∥.
Note that
(35)∥vt-p†∥2=∥xt-p†+δ𝔸*(𝕍rt-𝔸xt)∥2=∥xt-p†∥2+δ2∥𝔸*(𝕍rt-𝔸xt)∥2+2δ〈xt-p†,𝔸*(𝕍rt-𝔸xt)〉.
Since A is a linear operator and 𝔸* is the adjoint of 𝔸, we get
(36)〈xt-p†,𝔸*(𝕍rt-𝔸xt)〉=〈𝔸(xt-p†),𝕍rt-𝔸xt〉=〈𝔸xt-𝔸p†+𝕍rt-𝔸xt-(𝕍rt-𝔸xt),𝕍rt-𝔸xt𝔸xt-𝔸p†〉=〈𝕍rt-𝔸p†,𝕍rt-𝔸xt〉-∥𝕍rt-𝔸xt∥2.
At the same time, we know
(37)〈𝕍rt-𝔸p†,𝕍rt-𝔸xt〉=12(∥𝕍rt-𝔸p†∥2+∥𝕍rt-𝔸xt∥2-∥𝔸xt-𝔸p†∥2).
By (33), (36), and (37), we get
(38)〈xt-p†,𝔸*(𝕍rt-𝔸xt)〉=12(∥𝕍rt-𝔸p†∥2+∥𝕍rt-𝔸xt∥2-∥𝔸xt-𝔸p†∥2)-∥𝕍rt-𝔸xt∥2≤12(∥𝔸xt-𝔸p†∥2-∥rt-𝔸xt∥2+∥𝕍rt-𝔸xt∥2-∥𝔸xt-𝔸p†∥2)-∥𝕍rt-𝔸xt∥2=-12∥rt-𝔸xt∥2-12∥𝕍rt-𝔸xt∥2.
Substituting (38) into (35) to deduce
(39)∥vt-p†∥2≤∥xt-p†∥2+δ2∥𝔸∥2∥𝕍rt-𝔸xt∥2+2δ(-12∥rt-𝔸xt∥2-12∥𝕍rt-𝔸xt∥2)=∥xt-p†∥2+(δ2∥𝔸∥2-δ)∥𝕍rt-𝔸xt∥2-δ∥rt-𝔸xt∥2≤∥xt-p†∥2.
It follows that
(40)∥vt-p†∥≤∥xt-p†∥.
Thus, from (34), we get
(41)∥xt-p†∥≤tζκ∥xt-p†∥+t∥ζ𝒞(p†)-𝔹p†∥+(1-tγ-)∥xt-p†∥=[1-(γ--ζκ)t]∥xt-p†∥+t∥ζ𝒞(p†)-Bp†∥.
So,
(42)∥xt-p†∥≤∥ζ𝒞(p†)-Bp†∥γ--ζκ.
The boundedness of the net {xt} yields.
Sincext-𝕌ut=t(ζ𝒞(xt)-𝔹𝕌ut), we obtain
(43)limt→0∥xt-𝕌ut∥=0.
Using the firmly  nonexpansive necessity of projℂ, we have
(44)∥ut-p†∥2=∥projℂvt-p†∥2≤∥vt-p†∥2-∥projℂvt-vt∥2=∥vt-p†∥2-∥ut-vt∥2.
From (34), we derive that
(45)∥xt-p†∥2=∥t(ζ𝒞(xt)-𝔹p†)+(I-t𝔹)(𝕌ut-p†)∥2≤∥(I-t𝔹)(𝕌ut-p†)∥2+2t〈ζ𝒞(xt)-𝔹p†,xt-p†〉≤[∥I-t𝔹∥∥𝕌ut-p†∥]2+2t∥ζ𝒞(xt)-𝔹p†∥∥xt-p†∥≤(1-tγ-)2∥ut-p†∥2+2t∥ζ𝒞(xt)-𝔹p†∥∥xt-p†∥.
This together with (44) implies that
(46)∥xt-p†∥2≤∥vt-p†∥2-∥ut-vt∥2+2t∥ζ𝒞(xt)-𝔹p†∥∥xt-p†∥≤∥xt-p†∥2-∥ut-vt∥2+2t∥ζ𝒞(xt)-𝔹p†∥∥xt-p†∥.
It follows that
(47)∥ut-vt∥2≤2t∥ζ𝒞(xt)-Bp†∥∥xt-p†∥.
Hence,
(48)limt→0∥ut-vt∥=0.
Returning to (45) and using (39), we have
(49)∥xt-p†∥2≤(1-tγ-)2∥ut-p†∥2+2t∥ζ𝒞(xt)-𝔹p†∥∥xt-p†∥≤∥vt-p†∥2+2t∥ζ𝒞(xt)-𝔹p†∥∥xt-p†∥≤∥xt-p†∥2+(δ2∥𝔸∥2-δ)∥𝕍rt-𝔸xt∥2-δ∥rt-𝔸xt∥2+2t∥ζ𝒞(xt)-𝔹p†∥∥xt-p†∥.
Thus,
(50)(δ-δ2∥𝔸∥2)∥𝕍rt-𝔸xt∥2+δ∥rt-𝔸xt∥2≤2t∥ζ𝒞(xt)-𝔹p†∥∥xt-p†∥,
which implies that
(51)limt→0∥𝕍rt-𝔸xt∥=limt→0∥rt-𝔸xt∥=0.
So,
(52)limt→0∥𝕍rt-rt∥=0.
Note that
(53)∥vt-xt∥=∥δ𝔸*(𝕍projℚ-I)𝔸xt∥≤δ∥𝔸∥∥𝕍rt-𝔸xt∥.
It follows from (51) that
(54)limt→0∥xt-vt∥=0.
From (43), (48), and (54), we get
(55)limt→0∥xt-𝕌xt∥=0.
Next we show that the net {xt} is relatively norm-compact as t→0+. Assume that {tn}⊂(0,1) is such that tn→0+ as n→∞. Put xn:=xtn and vn:=vtn.
From (45), we have
(56)∥xt-p†∥2≤(1-tγ-)2∥ut-p†∥2+2t〈ζ𝒞(xt)-𝔹p†,xt-p†〉≤(1-tγ-)2∥xt-p†∥2+2tζ〈𝒞(xt)-𝒞(p†),xt-p†〉+2t〈ζ𝒞(p†)-Bp†,xt-p†〉≤(1-tγ-)2∥xt-p†∥2+2tζκ∥xt-p†∥2+2t〈ζ𝒞(p†)-𝔹p†,xt-p†〉.
It follows that
(57)∥xt-p†∥2≤1γ--ζκ〈ζ𝒞(p†)-𝔹p†,xt-p†〉+γ-2∥xt-p†∥22(γ--ζκ)t≤1γ--ζκ〈ζ𝒞(p†)-𝔹p†,xt-p†〉+Mt,
where M>0 is a constant satisfying supt∈(0,1)(γ-2∥xt-p†∥2/2(γ--ζκ))≤M. In particular, we have
(58)∥xn-p†∥2≤1γ--ζκ〈ζ𝒞(p†)-𝔹p†,xn-p†〉+Mtn,
since {xn} is bounded, without loss of generality, we may assume that {xn} converges weakly to a point q†∈C. We deduce from the above results that
(59)vn⇀q†,un⇀q†,𝔸xn⇀q†,rn⇀𝔸q†.
By the demiclosed principle of the nonexpansive mappings 𝕍 and 𝕌 (see Lemma 5), we deduce q†∈Fix(𝕌) and 𝔸q†∈Fix(𝕍). Note that uni=projℂvni∈ℂ and rni=projℚ𝔸xni∈ℚ. From (58), we deduce q†∈ℂ and 𝔸q†∈ℚ. To this end, we deduce q†∈ℂ∩Fix(𝕌) and 𝔸q†∈ℚ∩Fix(𝕍). So, q†∈Ω. We substitute p† for q† in (58) to obtain
(60)∥xn-q†∥2≤1γ--ζκ〈ζ𝒞(q†)-𝔹q†,xn-q†〉+Mtn,
since xn weakly converges to q†, we deduce that xn→q† strongly. Therefore, the net {xt} is relatively norm-compact.
In (58), we take the limit as n→∞ to deduce
(61)∥q†-p†∥2≤1γ--ζκ×〈ζ𝒞(p†)-𝔹p†,q†-p†〉,p†∈Ω.
Hence, q† solves the variational inequality
(62)q†∈Ω,〈ζ𝒞(p†)-𝔹p†,q†-p†〉≥0,p†∈Ω,
which is equivalent to its dual variational inequality
(63)q†∈Ω,〈ζ𝒞(q†)-Bq†,q†-p†〉≥0,p†∈Ω.
Therefore,q†=projΩ(ζ𝒞+I-𝔹)q†. That is, q† is the unique solution in VI(ℂ,𝔸) of the contraction projΩ(ζ𝒞+I-𝔹). Clearly this is sufficient to deduce that {xt} converges strongly to q† as t→0+. The proof is completed.



---

*Source: 854893-2013-09-30.xml*