# An Explicit Method for the Split Feasibility Problem with Self-Adaptive Step Sizes

Authors: Youli Yu
Journal: Abstract and Applied Analysis
 (2012)

---

## Abstract

An explicit iterative method with self-adaptive step-sizes for solving the split feasibility problem is presented. Strong convergence theorem is provided.


---

## Body

## 1. Introduction

Since its publication in 1994, the split feasibility problem has been studied by many authors. For some related works, please consult [1–18]. Among them, a more popular algorithm that solves the split feasibility problems is Byrne’s CQ method [2]:
(1.1)xn+1=PC(xn-τA*(I-PQ)Axn),
where C and Q are two closed convex subsets of two real Hilbert spaces H1 and H2, respectively, and A:H1→H2 is a bounded linear operator. The CQ algorithm only involves the computations of the projections PC and PQ onto the sets C and Q, respectively, and is therefore implementable in the case where PC and PQ have closed-form expressions.Note thatCQ algorithm can be obtained from optimization. If we set
(1.2)f(x):=12∥Ax-PQAx∥2,
then the convex objective f is differentiable and has a Lipschitz gradient given by
(1.3)∇f(x)=A*(I-PQ)A.
Thus, the CQ algorithm can be obtained by minimizing the following convex minimization problem
(1.4)minx∈Cf(x).
We can use a gradient projection algorithm below to solve the split feasibility problem:
(1.5)xn+1=PC(xn-τn∇f(xn)),
where τn, the step size at iteration n, is chosen in the interval (0,2/L), where L is the Lipschitz constant of ∇f.However, we observe that the determination of the step sizeτn depends on the operator (matrix) norm ∥A∥ (or the largest eigenvalue of A*A). This means that in order to implement the CQ algorithm, one has first to compute (or, at least, estimate) the matrix norm of A, which is in general not an easy work in practice. To overcome the above difficulty, the so-called self-adaptive method which permits step size τn being selected self-adaptively was developed. See, for example, [10, 14, 15, 19–23].Inspired by the above results and the self-adaptive method, in this paper, we present an explicit iterative method with self-adaptive step sizes for solving the split feasibility problem. Convergence analysis result is given.


## 2. Preliminaries

LetH1 and H2 be two real Hilbert spaces and C and Q two closed convex subsets of H1 and H2, respectively. Let A:H1→H2 be a bounded linear operator. The split feasibility problem is to find a point x* such that
(2.1)x*∈C,Ax*∈Q.
Next, we use Γ to denote the solution set of the split feasibility problem, that is, Γ={x∈C:Ax∈Q}.We know that a pointx*∈C is a stationary point of problem (1.4) if it satisfies
(2.2)〈∇f(x*),x-x*〉≥0,∀x∈C.
Given x*∈H1. x* solves the split feasibility problem if and only if x* solves the fixed point equation
(2.3)x*=PC(x*-γA*(I-PQ)Ax*).
Next we adopt the following notation:(i)
xn→x means that xn converges strongly to x;(ii)
xn⇀x means that xn converges weakly to x;(iii)
ωw(xn):={x:∃xnj⇀x} is the weak ω-limit set of the sequence {xn}.Recall that a functionf:H→ℝ is called convex if
(2.4)f(λx+(1-λ)y)≤λf(x)+(1-λ)f(y),
for all λ∈(0,1) and ∀x, y∈H. It is known that a differentiable function f is convex if and only if there holds the relation:
(2.5)f(z)≥f(x)+〈∇f(x),z-x〉,
for all z∈H. Recall that an element g∈H is said to be a subgradient of f:H→ℝ at x if
(2.6)f(z)≥f(x)+〈g,z-x〉,
for all z∈H. If the function f:H→ℝ has at least one subgradient at x is said to be sub-differentiable at x. The set of subgradients of f at the point x is called the subdifferential of f at x, and is denoted by ∂f(x). A function f is called sub-differentiable if it is subdifferentiable at all x∈H. If f is convex and differentiable, then its gradient and subgradient coincide. A function f:H→ℝ is said to be weakly lower semi continuous (w-lsc) at x if xn⇀x implies
(2.7)f(x)≤liminfn→∞f(xn).f is said to be w-lsc on H if it is w-lsc at every point x∈H.A mappingT:C→C is called nonexpansive if
(2.8)∥Tx-Ty∥≤∥x-y∥,
for all x,y∈C.Recall that the (nearest point or metric) projection fromH onto C, denoted PC, assigns, to each x∈H, the unique point PC(x)∈C with the property
(2.9)∥x-PC(x)∥=inf{∥x-y∥:y∈C}.
It is well known that the metric projection PC of H onto C has the following basic properties:(a)
∥PC(x)-PC(y)∥≤∥x-y∥ for all x,y∈H;(b)
〈x-y,PC(x)-PC(y)〉≥∥PC(x)-PC(y)∥2 for every x,y∈H;(c)
〈x-PC(x),y-PC(x)〉≤0 for all x∈H, y∈C.Lemma 2.1 (see [24]).
Assume that{an} is a sequence of nonnegative real numbers such that
(2.10)an+1≤(1-γn)an+δn,
where {γn} is a sequence in (0,1) and {δn} is a sequence such that(1)
∑n=1∞‍γn=∞;(2)
limsupn→∞(δn/γn)≤0 or ∑n=1∞‍|δn|<∞.
Thenlimn→∞an=0.Lemma 2.2 (see [25]).
Let(sn) be a sequence of real numbers that does not decrease at infinity, in the sense that there exists a subsequence (sni) of (sn) such that sni≤sni+1 for all i≥0. For every n≥n0, define an integer sequence (τ(n)) as
(2.11)τ(n)=max{k≤n:sni<sni+1}.
Then τ(n)→∞ as n→∞ and for all n≥n0(2.12)max{sτ(n),sn}≤sτ(n)+1.


## 3. Main Results

In this section, we will introduce our algorithm and prove our main results.LetC and Q be nonempty closed convex subsets of real Hilbert spaces H1 and H2, respectively. Let A:H1→H2 be a bounded linear operator. In the sequel, we assume that the split feasibility problem is consistent, that is Γ≠∅.Algorithm 3.1.
Foru∈C and given x0∈C, let the sequence {xn+1} defined by
(3.1)yn=αnu+(1-αn)xn,xn+1=PC(yn-τnf(yn)∇f(yn)∥∇f(yn)∥2),n≥0,
where {αn}⊂(0,1) and {τn}⊂(0,2).Remark 3.2.
In the sequel, we may assume that∇f(yn)≠0 for all n. Note that this fact can be guaranteed if the sequence {yn} is infinite; that is, Algorithm 3.1 does not terminate in a finite number of iterations.Theorem 3.3.
Assume that the following conditions are satisfied:(i)
limn→∞αn=0 and ∑n=1∞‍αn=∞;(ii)
infnτn(2-τn)>0.
Then{xn} defined by (3.1) converges strongly to PΓ(u).Proof.
Letν∈Γ. It follows that ∇f(ν)=0 for all ν∈Γ. From (2.5), we deduce that
(3.2)f(yn)=f(yn)-f(ν)≤〈∇f(yn),yn-ν〉.
Thus, by (3.1) and (3.2), we have
(3.3)∥xn+1-ν∥2=∥PC(yn-τnf(yn)∇f(yn)∥∇f(yn)∥2)-ν∥2≤∥yn-τnf(yn)∇f(yn)∥∇f(yn)∥2-ν∥2=∥yn-ν∥2-2τnf(yn)∥∇f(yn)∥2〈∇f(yn),yn-ν〉+τn2f2(yn)∥∇f(yn)∥2≤∥yn-ν∥2-2τnf2(yn)∥∇f(yn)∥2+τn2f2(yn)∥∇f(yn)∥2=∥yn-ν∥2-τn(2-τn)f2(yn)∥∇f(yn)∥2,∥yn-ν∥2=∥αn(u-ν)+(1-αn)(xn-ν)∥2≤αn∥u-ν∥2+(1-αn)∥xn-ν∥2.
It follows that
(3.4)∥xn+1-ν∥2≤αn∥u-ν∥2+(1-αn)∥xn-ν∥2-τn(2-τn)f2(yn)∥∇f(yn)∥2≤αn∥u-ν∥2+(1-αn)∥xn-ν∥2≤max{∥u-ν∥2,∥xn-ν∥2}.
By induction, we deduce
(3.5)∥xn+1-ν∥≤max{∥u-ν∥,∥x0-ν∥}.
Hence, {xn} is bounded.
At the same time, we note that(3.6)∥yn-ν∥2=∥αn(u-ν)+(1-αn)(xn-ν)∥2≤(1-αn)∥xn-ν∥2+2αn〈u-ν,yn-ν〉.
Therefore,
(3.7)∥xn+1-ν∥2≤(1-αn)∥xn-ν∥2+2αn〈u-ν,yn-ν〉-τn(2-τn)f2(yn)∥∇f(yn)∥2=(1-αn)∥xn-ν∥2+2αn〈u-ν,αn(u-ν)+(1-αn)(xn-ν)〉-τn(2-τn)f2(yn)∥∇f(yn)∥2=(1-αn)∥xn-ν∥2+2αn2∥u-ν∥2+2αn(1-αn)〈u-ν,xn-ν〉-τn(2-τn)f2(yn)∥∇f(yn)∥2.
It follows that
(3.8)∥xn+1-ν∥2-∥xn-ν∥2+αn(∥xn-ν∥2-2αn∥u-ν∥2+2αn〈u-ν,xn-ν〉)+τn(2-τn)f2(yn)∥∇f(yn)∥2≤2αn〈u-ν,xn-ν〉.
Next, we will prove that xn→ν. Set ωn=∥xn-ν∥2 for all n≥0. Since αn→0 and infnτn(2-τn)>0, we may assume without loss of generality that τn(2-τn)≥σ for some σ>0. Thus, we can rewrite (3.8) as
(3.9)ωn+1-ωn+αnUn+σf2(yn)∥∇f(yn)∥2≤2αn〈u-ν,xn-ν〉,
where Un=∥xn-ν∥2-2αn∥u-ν∥2+2αn〈u-ν,xn-ν〉.
Now, we consider two possible cases.
Case  1. Assume that {ωn} is eventually decreasing; that is, there exists N>0 such that {ωn} is decreasing for n≥N. In this case, {ωn} must be convergent and from (3.9) it follows that
(3.10)0≤σf2(yn)∥∇f(yn)∥2≤ωn-ωn+1-αnUn+2αn∥u-ν∥∥xn-ν∥≤ωn-ωn+1+Mαn,
where M>0 is a constant such that supn{2∥u-ν∥∥xn-ν∥+∥Un∥}≤M. Letting n→∞ in (3.10), we get
(3.11)limn→∞f(yn)=0.
Since {yn} is bounded, there exists a subsequence {ynk} of {yn} converging weakly to x~∈C. Since, xn-yn→0, we also have {xnk} of {xn} converging weakly to x~∈C. From the weak lower semicontinuity of f, we have
(3.12)0≤f(x~)≤liminfk→∞f(ynk)=limn→∞f(yn)=0.
Hence, f(x~)=0; that is, Ax~∈Q. This indicates that
(3.13)ωw(yn)=ωw(xn)⊂Γ.
Furthermore, by using the property of the projection (c), we deduce
(3.14)limsupn→∞〈u-ν,xn-ν〉=maxx~∈ωw(xn)〈u-PΓ(u),x~-PΓ(u)〉≤0.
From (3.8), we obtain
(3.15)ωn+1≤(1-αn)ωn+αn(2αn∥u-ν∥2+2(1-αn)〈u-ν,xn-ν〉).
This together with Lemma 2.1 imply that ωn→0.
Case  2. Assume that {ωn} is not eventually decreasing. That is, there exists an integer n0 such that ωn0≤ωn0+1. Thus, we can define an integer sequence {τn} for all n≥n0 as follows:
(3.16)τ(n)=max{k∈ℕ∣n0≤k≤n,ωk≤ωk+1}.
Clearly, τ(n) is a nondecreasing sequence such that τ(n)→+∞ as n→∞ and
(3.17)ωτ(n)≤ωτ(n)+1,
for all n≥n0. In this case, we derive from (3.10) that
(3.18)σf2(yτ(n))∥∇f(yτ(n))∥2≤Mατ(n)→0.
It follows that
(3.19)limn→∞f(yτ(n))=0.
This implies that every weak cluster point of {yτ(n)} is in the solution set Γ; that is, ωw(yτ(n))⊂Γ. So, ωw(xτ(n))⊂Γ. On the other hand, we note that
(3.20)∥yτ(n)-xτ(n)∥=ατ(n)∥u-xτ(n)∥→0,∥xτ(n)+1-yτ(n)∥≤ττ(n)f(yτ(n))∥∇f(yτ(n))∥→0.
From which we can deduce that
(3.21)limsupn→∞〈u-ν,xτ(n)-ν〉=maxx~∈ωw(xτ(n))〈u-PΓ(u),x~-PΓ(u)〉≤0.
Since ωτ(n)≤ωτ(n)+1, we have from (3.9) that
(3.22)ωτ(n)≤(1-2ατ(n))〈u-ν,xτ(n)-ν〉+2ατ(n)∥u-ν∥2.
Combining (3.21) and (3.22) yields
(3.23)limsupn→∞ωτ(n)≤0,
and hence
(3.24)limn→∞ωτ(n)=0.
From (3.15), we have
(3.25)limsupn→∞ωτ(n)+1≤limsupn→∞ωτ(n).
Thus,
(3.26)limn→∞ωτ(n)+1=0.
From Lemma 2.2, we have
(3.27)0≤ωn≤max{ωτ(n),ωτ(n)+1}.
Therefore, ωn→0. That is, xn→ν. This completes the proof.



---

*Source: 432501-2012-11-19.xml*