Volume 2010, Article ID 102085,13pages doi:10.1155/2010/102085
Research Article
Approximating Curve and Strong Convergence of the CQ Algorithm for the Split Feasibility Problem
Fenghui Wang
1, 2and Hong-Kun Xu
31Department of Mathematics, East China University of Science and Technology, Shanghai 200237, China
2Department of Mathematics, Luoyang Normal University, Luoyang 471022, China
3Department of Applied Mathematics, National Sun Yat-Sen University, Kaohsiung 80424, Taiwan
Correspondence should be addressed to Hong-Kun Xu,[email protected] Received 14 December 2009; Accepted 14 January 2010
Academic Editor: Yeol Je Cho
Copyrightq2010 F. Wang and H.-K. Xu. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Using the idea of Tikhonov’s regularization, we present properties of the approximating curve for the split feasibility problemSFPand obtain the minimum-norm solution of SFP as the strong limit of the approximating curve. It is known that in the infinite-dimensional setting, Byrne’s CQ algorithmByrne, 2002has only weak convergence. We introduce a modification of Byrne’s CQ algorithm in such a way that strong convergence is guaranteed and the limit is also the minimum- norm solution of SFP.
1. Introduction
Let C and Q be nonempty closed convex subsets of real Hilbert spaces H1 and H2, respectively. The problem under consideration in this article is formulated as finding a point xsatisfying the property:
x∈C, Ax∈Q, 1.1
whereA:H1 → H2is a bounded linear operator. Problem1.1, referred to by Censor and Elfving1as the split feasibility problemSFP, attracts many authors’ attention due to its application in signal processing1. Various algorithms have been invented to solve itsee 2–7and reference therein.
In particular, Byrne2introduced the so-calledCQalgorithm. Take an initial guess x0∈ H1arbitrarily, and definexnn≥0recursively as
xn1PC
I−γA∗ I−PQ
A
xn, 1.2
where 0 < γ < 2/ρA∗A and where PC denotes the projector onto C and ρA∗A is the spectral radius of the self-adjoint operatorA∗A.Then the sequencexnn≥0generated by1.2 converges strongly to a solution of SFP whenever H1 is finite-dimensional and whenever there exists a solution to SFP1.1.
However, theCQalgorithm need not necessarily converge strongly in the case when H1 is infinite dimensional. Let us mention that the CQ algorithm can be regarded as a special case of the well-known Krasnosel’skii-Mann algorithm for approximating fixed points of nonexpansive mappings 3. This iterative method is introduced in 8 and defined as follows. Take an initial guessx0 ∈Carbitrarily, and definexnn≥0recursively as
xn1 αnxn 1−αnTxn, 1.3
whereαn∈0,1satisfying∞
n0αn1−αn ∞.IfT is nonexpansive with a nonempty fixed point set, then the sequencexnn≥0generated by1.3converges weakly to a fixed point of T. It is known that Krasnosel’skii-Mann algorithm is in general not strongly convergentsee 9,10for counterexamplesand neither is theCQalgorithm.
It is therefore the aim of this paper to construct a new algorithm so that strong convergence is guaranteed. The paper is organized as follows. In the next section, some useful lemmas are given. InSection 3, we define the concept of the minimal norm solution of SFP1.1. Using Tikhonov’s regularization, we obtain a continuous curve for approximating such minimal norm solution. Together with some properties of this approximating curve, we introduce, inSection 4, a modification of Byrne’sCQalgorithm so that strong convergence is guaranteed and its limit is the minimum-norm solution of SFP1.1.
2. Preliminaries
Throughout the rest of this paper,Idenotes the identity operator onH1, FixTthe set of the fixed points of an operatorTand∇fthe gradient of the functionalf:H1 → R.The notation
“→” denotes strong convergence and “” weak convergence.
Recall that an operatorT fromH1into itself is called nonexpansive if
Tx−Ty≤x−y, x, y∈ H1; 2.1
contractive if there exists 0< α <1 such that
Tx−Ty≤αx−y, x, y∈ H1; 2.2
monotone if
Tx−Ty, x−y
≥0, x, y∈ H1. 2.3
Obviously, contractions are nonexpansive, and ifT is nonexpansive, thenI−T is monotone see11.
LetPCdenote the projection fromH1onto a nonempty closed convex subsetCofH1; that is,
PCxargmin
y∈C
x−y, x∈ H1. 2.4
It is well known thatPCxis characterized by the inequality
x−PCx, c−PCx ≤0, c∈C. 2.5 Consequently,PCis nonexpansive.
The lemma below is referred to as the demiclosedness principle for nonexpansive mappingssee12.
Lemma 2.1 demiclosedness principle. LetC be a nonempty closed convex subset of H1 and T :C → Ca nonexpansive mapping with FixT/∅.Ifxnn≥1is a sequence inCweakly converging toxand if the sequenceI−Txnconverges strongly toy, thenI−Txy.In particular, ify0, thenx∈FixT.
Letf:H1 → Rbe a a functional. Recall that ifis convex if
f
λx 1−λy
≤λfx 1−λf y
, ∀0< λ <1, ∀x, y∈ H1; 2.6 iif is strictly convex if the strict less than inequality in2.6 holds for all distinct
x, y∈ H1.
iiifis strongly convex if there exists a constantα >0 such that f
λx 1−λy
≤λfx 1−λf y
−αx−y2, ∀0< λ <1, ∀x, y∈ H1; 2.7 ivfis coercive iffx → ∞wheneverx → ∞.It is easily seen that iffis strongly
convex, then it is coercive. See13for more details about convex functions.
The following lemma gives the optimality condition for the minimizer of a convex functional over a closed convex subset.
Lemma 2.2see14. Letfbe a convex and differentiable functional and letCbe a closed convex subset ofH1. Thenx∈Cis a solution of the problem
minimize
x∈C fx 2.8
if and only ifx∈Csatisfies the following optimality condition:
∇fx, v−x ≥0, ∀v∈C. 2.9 Moreover, iffis, in addition, strictly convex and coercive, then problem2.8has a unique solution.
The following is a sufficient condition for a real sequence to converge to zero.
Lemma 2.3see15. Letann≥0be a nonnegative real sequence satisfying
an1≤1−rnanrnμn, 2.10
where the sequencesrnn≥0⊂0,1andμnn≥0satisfy the conditions:
1∞
n0rn∞;
2limn→ ∞rn0;
3either∞
n0|rnμn|<∞or lim supn→ ∞μn≤0.
Then limn→ ∞an0.
3. Approximating Curves
The convexly constrained linear problem requires to solve the constrained linear systemcf.
16,17
Axb,
x∈C, 3.1
whereb ∈ H2. A classical way to deal with such a possibly ill-posed problem is the well- known Tikhonov regularization, which approximates a solution of problem 3.1 by the unique minimizer of the regularized problem
minx∈CAx−b2αx2, 3.2
whereα >0 is known as the regularization parameter.
We now try to transfer this idea of Tikhonov’s regularization method for solving the constrained linear inverse problem3.1to the case of SFP1.1.
It is not hard to find that SFP1.1is equivalent to the minimization problem minx∈CI−PQ
Ax. 3.3
Motivated by Tikhonov’s regularization, we consider the minimization problem
minx∈CI−PQAx2αx2, 3.4
whereα >0 is the regularization parameter. Denote byxαthe unique solution of3.4; namely, xα:argmin
x∈C
I−PQ
Ax2αx2 . 3.5
Proposition 3.1. For anyα >0,the minimizerxαgiven by3.5is uniquely defined. Moreover,xα
is characterized by the inequality A∗
I−PQ
Axααxα, c−xα
≥0, c∈C. 3.6
Proof. Let
fx I−PQ
Ax2, fαx fx αx2. 3.7
Sincefis convex and differentiable with gradientsee13
∇fx 2A∗ I−PQ
Ax, 3.8
fαis strictly convex, coercive, and differentiable with gradient
∇fαx 2A∗ I−PQ
Ax2αx. 3.9
Thus, applyingLemma 2.2gets the assertion3.6, as desired.
The next result collects some useful properties ofxαα>0. Proposition 3.2. The following assertions hold.
axαis decreasing forα∈0,∞.
bI−PQAxαis increasing forα∈0,∞.
cα→xαdefines a continuous curve from0,∞toH1.
Proof. Let α > β > 0 be fixed. Since xα and xβ are theunique minimizers of fα and fβ, respectively, we get
I−PQAxα2αxα2≤I−PQAxβ2αxβ2, 3.10 I−PQAxβ2βxβ2≤I−PQAxα2βxα2. 3.11
Adding up3.10and3.11yields
αxα2βxβ2≤αxβ2βxα2, 3.12 which implies thatxα ≤ xβ. Henceaholds.
It follows from3.11that
I−PQAxβ2≤I−PQAxα2β
xα2−xβ2
, 3.13
which together withaimplies I−PQ
Axβ≤I−PQ
Axα, 3.14
and thereforebholds.
ByProposition 3.1, we have that A∗
I−PQ
Axααxα, xβ−xα
≥0, 3.15
and also that
A∗ I−PQ
Axββxβ, xα−xβ
≥0. 3.16
Adding up3.15and3.16, we get αxα−βxβ, xα−xβ
≤ I−PQ
Axα− I−PQ
Axβ, Axβ−Axα
. 3.17
SinceI−PQis monotone, we obtain from the last relation αxα−xβ2 ≤
β−α
xβ, xα−xβ
. 3.18
It turns out that
xα−xβ≤ α−β
α xβ. 3.19
Thuscholds.
LetFC∩A−1Q, whereA−1Q {x∈ H1:Ax∈Q}. In what follows, we assume thatF/∅; that is, the solution set of SFP1.1is nonempty. The fact thatFis nonempty closed convex set thus allows us to introduce the concept of minimum-norm solution of SFP1.1.
Definition 3.3. An element x ∈ F is said to be the minimal norm solution of SFP 1.1 if x infx∈Fx. In other words,xis the projection of the origin onto the solution setFof SFP 1.1. Thus the minimum-norm solutionxfor SFP1.1exists and is unique.
Theorem 3.4. Letxαbe given as3.5. Thenxαconverges strongly asα → 0 to the minimum-norm solutionxof SFP1.1.
Proof. We first show that the inequality
xα ≤ x 3.20
holds for any 0< α <∞. To this end, observe that
I−PQAxα2αxα2≤I−PQAx2αx 2. 3.21
Sincex∈C∩A−1Q,I−PQAx0. It follows from3.21that
xα2≤ x 2−I−PQ Axα2
α ≤ x 2, 3.22
and3.20is proven.
Let nowαnn≥0be a sequence such thatαn → 0 asn → ∞and letxαnbe abbreviated asxn.All we need to prove is thatxnn≥0 contains a subsequence converging strongly to
x.Sincexnn≥0is bounded and sinceCis bounded convex, by passing to a subsequence if necessary, we may assume thatxnn≥0converges weakly to a pointw∈C.ByProposition 3.1, we deduce that
A∗ I−PQ
Axnαnxn,x−xn
≥0. 3.23
It turns out that
I−PQ
Axn, Ax−xn
≥αn xn, xn−x. 3.24
SinceAx∈Q,the characterizing inequality2.5gives I−PQ
Axn, Ax−PQAxn
≤0, 3.25
and this implies that
I−PQAxn2≤ I−PQ
Axn, Axn−x. 3.26
Now by combining3.26and3.24, we get
I−PQAxn2≤αn xn,x−xn ≤2αnx2, 3.27
where the last inequality follows from3.20. Consequently, we get
nlim→ ∞I−PQ
Axn0. 3.28
Note thatAis also weakly continuous and henceAxn Aw. Now due to3.28, we can use the demiclosedness principleLemma 2.1to conclude thatI−PQAw0. That is,Aw∈Q orw∈A−1Q; therefore,w∈ F.We next prove thatwxand this finishes the proof. To see this, we have that the weak convergence towof{xn}together with3.20implies that
w ≤lim inf
n→ ∞ xn ≤ xmin{x:x∈ F}. 3.29
This shows thatwis also a point inFwhich assumes minimum norm. Due to uniqueness of minimum-norm element, we must havewx.
Remark 3.5. The above argument shows that if the solution setFof SFP1.1is empty, then the net of norms,xα, diverges to∞asα → 0.
4. A Modified CQ Algorithm
It is a standard way to use contractions to approximate nonexpansive mappings. We follow this idea and use contractions to approximate the nonexpansive mappingI−γA∗I−PQA in order to modify Byrne’s CQ algorithm. More precisely, we introduce the following algorithm which is viewed as a modification of Byrne’sCQalgorithm. The purpose for such a modification lies in the hope of strong convergence.
Algorithm 4.1. For an arbitrary guessx0, the sequencexnn≥0 is generated by the iterative algorithm
xn1PC
1−αn
I−γA∗ I−PQ
A
xn, 4.1
whereαnn≥0is a sequence in0,1such that 1limn→ ∞αn0;
2∞
n0αn∞;
3either∞
n0|αn1−αn|<∞or limn→ ∞|αn1−αn|/αn0.
Note that a prototype ofαnisαn 1n−1for alln≥0.
To prove the convergence of algorithm 4.1 see Theorem 4.3 below, we need a lemma below.
Lemma 4.2. SetUI−γA∗I−PQA, where 0< γ <2/ρA∗AwithρA∗Abeing the spectral radius of the self-adjoint operatorA∗A.
iUis an averaged mapping; namely,U 1−βIβV, whereβ∈0,1is a constant and V is a nonexpansive mapping fromH1into itself.
iiFixU A−1Q; consequently, FixPCU FixPC∩FixU FC∩A−1Q.
Proof. iThatUwhich is averaged is actually proved in3.
To see ii, we first observe that the inclusion A−1Q ⊂ FixU holds trivially. It remains to prove the implication: x Ux ⇒ Ax ∈ Q. To see this, we notice that the relationxUxis equivalent to the relationxx−γA∗I−PQAx. It turns out that
A∗ I−PQ
Ax0. 4.2
Since the solution setFC∩A−1Q/∅, we can takez∈ F. Now sinceAz∈Q, we have by 2.5,
I−PQ
Ax, Az−PQAx
≤0. 4.3
It follows from4.2and4.3that I−PQAx2
I−PQ
Ax, Ax−Az I−PQ
Ax, Az−PQAx
≤ I−PQ
Ax, Ax−Az A∗
I−PQ
Ax, x−z 0.
4.4
This shows thatAxPQAx∈Q; that is,x∈A−1Q.
Finally, since FixPC∩FixU C∩A−1Q F/∅, and bothPCandUare averaged, we have FixPCU FixPC∩FixU F.
Theorem 4.3. The sequence xnn≥0 generated by algorithm 4.1 converges strongly to the minimum-norm solutionxof SFP1.1.
Proof. Define operatorsTnandTonH1by Tnx:PC
1−αn
I−γA∗ I−PQ
A
xPC1−αnUx, x∈ H1, Tx:PC
I−γA∗ I−PQ
A
xPCUx, x∈ H1, 4.5
whereUI−γA∗I−PQAis averaged byLemma 4.2.
It is readily seen thatTnis a contraction with contractive constant 1−αn. Namely, Tnx−Tny≤1−αnx−y, x, y∈ H1. 4.6
Also we may rewrite algorithm4.1as
xn1TnxnPC1−αnUxn. 4.7
We first prove thatxnis a bounded sequence. Indeed, sinceF/∅, we can take anyx ∈ F thusxUxbyLemma 4.2to deduce that
xn1−x Tnxn−x ≤ T nxn−Tnx Tnx−x. 4.8
Note that
Tnx−x PC1−αnUx−PCUx
≤ 1−αnUx−Ux αnUx αnx.
4.9
Substituting4.9into4.8, we get
xn1−x ≤ 1−αnxn−x αnx
≤max{xn−x, x}. 4.10
By induction, we can easily show that, for alln≥0,
xn−x ≤ max{x0−x, x}. 4.11
In particular,xnis bounded.
We now claim that
nlim→ ∞xn1−xn0. 4.12
To see this, we compute
xn1−xnTnxn−Tn−1xn−1
≤ Tnxn−Tnxn−1Tnxn−1−Tn−1xn−1
≤1−αnxn−xn−1Tnxn−1−Tn−1xn−1.
4.13
LettingM >0 be a constant such thatM >Uxnfor alln≥0, we find
Tnxn−1−Tn−1xn−1PC1−αnUxn−1−PC1−αn−1Uxn−1
≤ 1−αnUxn−1−1−αn−1Uxn−1 αn−αn−1Uxn−1
≤M|αn−αn−1|.
4.14
Substituting4.14into4.13, we arrive at
xn1−xn ≤1−αnxn−xn−1M|αn−αn−1|. 4.15
By virtue of the assumptions a–c, we can apply Lemma 2.3 to 4.15 to obtain 4.12.
Consequently we also have
nlim→ ∞xn−Txn0. 4.16
This follows from the following computations:
xn−Txn ≤ xn−xn1Tnxn−Txn
≤ xn−xn11−αnUxn−Uxn
≤ xn−xn1Mαn−→0.
4.17
Therefore, the demiclosedness principleLemma 2.1ensures that each weak limit point of xnis a fixed point of the nonexpansive mappingT PCU, that is, a point of the solution set Fof SFP1.1.
One of the key ingredients of the proof is the following conclusion:
lim sup
n→ ∞ Uxn−x, −x ≤0, 4.18
wherexis the minimum-norm element ofFi.e., the projectionPF0. Since
Uxn−x, −x Uxn−xn,−x xn−x, −x, 4.19
to prove4.18, it suffices to prove that
nlim→ ∞Uxn−xn0, 4.20
lim sup
n→ ∞ xn−x, −x ≤ 0. 4.21
To prove4.20, we useLemma 4.2to getx∈FixUandUis averaged. WriteU 1−βIβV for someβ ∈0,1and nonexpansive mappingV. Then we derive, by taking a pointz∈ F, that
xn1−z2PC1−αnUxn−z2
≤ 1−αnUxn−z2
1−αnUxn−z αn−z2
≤1−αnUxn−z2αnz2
≤1−βxn−z βV xn−z2αnz2
1−β
xn−z2βV xn−z2
−β 1−β
xn−V xn2αnz2
≤ xn−z2−β 1−β
xn−V xn2αnz2 aszV z.
4.22
It turns out thatfor some constantM >xn−zfor alln β
1−β
xn−V xn2≤ xn−z2− xn1−z2αnz2
≤2M|xn−z − xn1−z|αnz2
≤2Mxn−xn1αnz2
−→0 by4.12.
4.23
Now sinceI−UβI−V,4.23implies4.20.
To prove4.21, we take a subsequencexnofxnso that lim sup
n→ ∞ xn−x, −x lim
n→ ∞ xn−x, −x. 4.24
Sincexnis bounded, we may further assume with no loss of generality thatxnconverges weakly to a pointx. Noticing that x ∈FixT Fand thatxis the projection of the origin ontoF, and applying2.5, we arrive at
lim sup
n→ ∞ xn−x, −x lim
n→ ∞ xn−x, −x −x, x−x ≤ 0. 4.25 This is4.21.
Finally we provexn → xin norm. To see this, we compute xn1−x 2PC1−αnUxn−PCUx 2
≤ 1−αnUxn−Ux 2
≤ 1−αnUxn−x 2 asxUx 1−αnUxn−x αn−x 2
1−αn2Uxn−x 2
2αn1−αn Uxn−x, −xα2nx 2
≤1−αnxn−x 2
2αn1−αn Uxn−x, −xα2nx 2
≤1−αnxn−x 2αnδn,
4.26
where
δn:21−αn Uxn−x, −x αnx 2 4.27
satisfies the propertydue to4.18
lim sup
n→ ∞ δn≤0. 4.28
We therefore can applyLemma 2.3to4.26to conclude thatxn−x 2 → 0. This completes the proof.
Acknowledgment
H. K. Xu was supported in part by NSC 97-2628-M-110-003-MY3, and by DGES MTM2006- 13997-C02-01.
References
1 Y. Censor and T. Elfving, “A multiprojection algorithm using Bregman projections in a product space,” Numerical Algorithms, vol. 8, no. 2–4, pp. 221–239, 1994.
2 C. Byrne, “Iterative oblique projection onto convex sets and the split feasibility problem,” Inverse Problems, vol. 18, no. 2, pp. 441–453, 2002.
3 C. Byrne, “A unified treatment of some iterative algorithms in signal processing and image reconstruction,” Inverse Problems, vol. 20, no. 1, pp. 103–120, 2004.
4 B. Qu and N. Xiu, “A note on the CQ algorithm for the split feasibility problem,” Inverse Problems, vol.
21, no. 5, pp. 1655–1665, 2005.
5 H.-K. Xu, “A variable Krasnosel’ski˘ı-Mann algorithm and the multiple-set split feasibility problem,”
Inverse Problems, vol. 22, no. 6, pp. 2021–2034, 2006.
6 Q. Yang, “The relaxed CQ algorithm solving the split feasibility problem,” Inverse Problems, vol. 20, no. 4, pp. 1261–1266, 2004.
7 Q. Yang and J. Zhao, “Generalized KM theorems and their applications,” Inverse Problems, vol. 22, no.
3, pp. 833–844, 2006.
8 W. R. Mann, “Mean value methods in iteration,” Proceedings of the American Mathematical Society, vol.
4, pp. 506–510, 1953.
9 A. Genel and J. Lindenstrauss, “An example concerning fixed points,” Israel Journal of Mathematics, vol. 22, no. 1, pp. 81–86, 1975.
10 O. G ¨uler, “On the convergence of the proximal point algorithm for convex minimization,” SIAM Journal on Control and Optimization, vol. 29, no. 2, pp. 403–419, 1991.
11 Y. Alber and I. Ryazantseva, Nonlinear Ill-Posed Problems of Monotone Type, Springer, Dordrecht, The Netherlands, 2006.
12 K. Goebel and W. A. Kirk, Topics in Metric Fixed Point Theory, vol. 28 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, Mass, USA, 1990.
13 J.-P. Aubin, Optima and Equilibria: An Introduction to Nonlinear Analysis, vol. 140 of Graduate Texts in Mathematics, Springer, Berlin, Germany, 1993.
14 H. W. Engl, M. Hanke, and A. Neubauer, Regularization of Inverse Problems, vol. 375 of Mathematics and Its Applications, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1996.
15 H.-K. Xu, “Iterative algorithms for nonlinear operators,” Journal of the London Mathematical Society.
Second Series, vol. 66, no. 1, pp. 240–256, 2002.
16 B. Eicke, “Iteration methods for convexly constrained ill-posed problems in Hilbert space,” Numerical Functional Analysis and Optimization, vol. 13, no. 5-6, pp. 413–429, 1992.
17 A. Neubauer, “Tikhonov-regularization of ill-posed linear operator equations on closed convex sets,”
Journal of Approximation Theory, vol. 53, no. 3, pp. 304–320, 1988.
