# Modified Projection Algorithms for Solving the Split Equality Problems

Authors: Qiao-Li Dong; Songnian He
Journal: The Scientific World Journal
 (2014)

---

## Abstract

The split equality problem (SEP) has extraordinary utility and broad applicability in many areas of applied mathematics. Recently, Byrne and Moudafi (2013)
proposed a CQ algorithm for solving it. In this paper, we propose a modification for the CQ algorithm, which computes the stepsize adaptively and performs an additional projection step onto two half-spaces in each iteration. We further propose a relaxation scheme for the self-adaptive projection algorithm by using projections onto half-spaces instead of those onto the original convex sets, which is much more practical. Weak convergence results for both algorithms are analyzed.


---

## Body

## 1. Introduction

The split equality problem (SEP) was introduced by Moudafi [1] and its interest covers many situations, for instance, in domain decomposition for PDE’s, game theory, and intensity-modulated radiation therapy (IMRT) (see [2–7] for more details). Let H
1, H
2, and H
3 be real Hilbert spaces; let C
⊂
H
1 and Q
⊂
H
2 be two nonempty closed convex sets; let A
:
H
1
→
H
3 and B
:
H
2
→
H
3 be two bounded linear operators. The SEP can mathematically be formulated as the problem of finding x and y with the property
(1)
x
∈
C
,
y
∈
Q
,
such
that
A
x
=
B
y
,
which allows asymmetric and partial relations between the variables x and y. If H
2
=
H
3 and B
=
I, then the split equality problem (1) reduces to the split feasibility problem (originally introduced in Censor and Elfving [8]) which is to find x
∈
C with A
x
∈
Q.For solving the SEP (1), Moudafi [1] introduced the following alternating C
Q algorithm:
(2)
x
k
+
1
=
P
C
(
x
k
-
γ
k
A
*
(
A
x
k
-
B
y
k
)
)
,
y
k
+
1
=
P
Q
(
y
k
+
γ
k
B
*
(
A
x
k
+
1
-
B
y
k
)
)
,
where γ
k
∈
(
ɛ
,
min
⁡
(
1
/
λ
A
,
1
/
λ
B
)
-
ɛ
) and λ
A and λ
B are the spectral radii of A
*
A and B
*
B, respectively. By studying the projected Landweber algorithm of the SEP (1) in a product space, Byrne and Moudafi [7] obtained the following C
Q algorithm:
(3)
x
k
+
1
=
P
C
(
x
k
-
γ
k
A
*
(
A
x
k
-
B
y
k
)
)
,
y
k
+
1
=
P
Q
(
y
k
+
γ
k
B
*
(
A
x
k
-
B
y
k
)
)
,
where γ
k, the stepsize at the iteration k, is chosen in the interval(
ɛ
,
(
2
/
(
λ
A
+
λ
B
)
)
-
ɛ
).  It is easy to see that the alternating C
Q algorithm (2) is sequential but the algorithm (3) is simultaneous.Observe that in the algorithms (2) and (3), the determination of the stepsize γ
n depends on the operator (matrix) norms ∥
A
∥ and ∥
B
∥ (or the largest eigenvalues of A
*
A and B
*
B). This means that, in order to implement the alternating C
Q algorithm (2), one has first to compute (or, at least, estimate) operator norms of A and B, which is in general not an easy work in practice. Considering this, Dong and He [9] proposed algorithms without prior knowledge of operator norms.In this paper, we first propose a modification forC
Q algorithm (3), inspired by Tseng [10] (also see [11]). Our modified projection method computes the stepsize adaptively and performs an additional projection step onto two half-spaces, X
k
⊂
H
1 and Y
k
⊂
H
2, in each iteration. Then we give a relaxation scheme for this modification by replacing the orthogonal projections onto the sets C and Q by projections onto the two half-spaces C
k and Q
k, respectively. Since projections onto half-spaces can be directly calculated, the relaxed scheme will be more practical and easily implemented.The rest of this paper is organized as follows. In the next section, some useful facts and tools are given. The weak theorem of the proposed self-adaptive projection algorithm is obtained in Section3. In Section 4, we consider a relaxed self-adaptive projection algorithm, where the sets C and Q are level sets of convex functions.


## 2. Preliminaries

In this section, we review some definitions and lemmas which will be used in this paper.LetH be a Hilbert space and let I be the identity operator on H. If f
:
H
→
ℝ is a differentiable functional, then denote by ∇
f the gradient of f. If f
:
H
→
ℝ is a subdifferentiable functional, then denote by ∂
f the subdifferential of f. Given a sequence (
x
k
,
y
k
) in H
1
×
H
2, ω
w
(
x
k
,
y
k
) stands for the set of cluster points in the weak topology. “x
k
→
x” (resp., “x
k
⇀
x”) means the strong (resp., weak) convergence of (
x
k
) to x.Definition 1.
A sequence(
x
k
) is said to be asymptotically regular if
(4)
lim
⁡
k
→
∞
∥
x
k
+
1
-
x
k
∥
=
0
.Definition 2.
The graph of an operator is called to be weakly-strongly closed ify
n
∈
T
(
x
n
) with y
n strongly converging to y and x
n weakly converging to x; then y
∈
T
(
x
).The next lemma is well known (see [10, 12]) and shows that the maximal monotone operators are weakly-strongly closed.Lemma 3.
LetH be a Hilbert space and let T
:
H
⇉
H be a maximal monotone mapping. If (
x
k
) is a sequence in H bounded in norm and converging weakly to some x and (
w
k
) is a sequence in H converging strongly to some w and w
k
∈
T
(
x
k
) for all k, then w
∈
T
(
x
).The projection is an important tool for our work in this paper. LetΩ be a closed convex subset of real Hilbert space H. Recall that the (nearest point or metric) projection from H onto Ω, denoted byP
Ω, is defined in such a way that, for each x
∈
H, P
Ω
x is the unique point in Ω such that
(5)
∥
x
-
P
Ω
x
∥
=
min
⁡
{
∥
x
-
z
∥
:
z
∈
Ω
}
.The following two lemmas are useful characterizations of projections.Lemma 4.
Givenx
∈
H and z
∈
Ω, then z
=
P
Ω
x if and only if
(6)
〈
x
-
z
,
y
-
z
〉
≤
0
,
∀
y
∈
Ω
.Lemma 5.
For anyx
,
y
∈
H and z
∈
Ω, it holds  (i)
∥
P
Ω
(
x
)
-
P
Ω
(
y
)
∥
2
≤
〈
P
Ω
(
x
)
-
P
Ω
(
y
)
,
x
-
y
〉;
(ii)
∥
P
Ω
(
x
)
-
z
∥
2
≤
∥
x
-
z
∥
2
-
∥
P
Ω
(
x
)
-
x
∥
2.Throughout this paper, assume that the split equality problem (1) is consistent and denote by Γ the solution of (1); that is,
(7)
Γ
=
{
x
∈
C
,
y
∈
Q
:
A
x
=
B
y
}
.
Then Γ is closed, convex, and nonempty. The split equality problem (1) can be written as the following minimization problem:
(8)
min
⁡
x
∈
H
1
,
y
∈
H
2
ι
C
(
x
)
+
ι
Q
(
y
)
+
1
2
∥
A
x
-
B
y
∥
2
,
where ι
C
(
x
) is an indicator function of the set C defined by
(9)
ι
C
(
x
)
=
{
0
,
x
∈
C
+
∞
,
otherwise
.
By writing down the optimality conditions, we obtain
(10)
0
∈
∇
x
{
1
2
∥
A
x
-
B
y
∥
2
}

+

∂
ι
C
(
x
)
=
A
*
(
A
x
-
B
y
)
+
N
C
(
x
)
,
0
∈
∇
y

{
1
2
∥
A
x
-
B
y
∥
2
}

+

∂
ι
Q
(
y
)
=
-
B
*
(
A
x
-
B
y
)
+
N
Q
(
y
)
,
which implies, for γ
>
0 and β
>
0,
(11)
x
-
γ
A
*
(
A
x
-
B
y
)
∈
x
+
γ
N
C
(
x
)
,
y
+
β
B
*
(
A
x
-
B
y
)
∈
y
+
β
N
Q
(
y
)
,
which in turn leads to the fixed point formulation
(12)
x
=
(
I
+
γ
N
C
)
-
1
(
x
-
γ
A
*
(
A
x
-
B
y
)
)
,
y
=
(
I
+
β
N
Q
)
-
1
(
y
+
β
B
*
(
A
x
-
B
y
)
)
.
Since (
I
+
γ
N
C
)
-
1
=
P
C and (
I
+
β
N
Q
)
-
1
=
P
Q, we have
(13)
x
=
P
C
(
x
-
γ
A
*
(
A
x
-
B
y
)
)
,
y
=
P
Q
(
y
+
β
B
*
(
A
x
-
B
y
)
)
.
The following proposition shows that solutions of the fixed point equations (17) are exactly the solutions of the SEP (1).Proposition 6 (see [9]).
Givenx
*
∈
H
1 and y
*
∈
H
2, then (
x
*
,
y
*
) solves the SEP (1) if and only if (
x
*
,
y
*
) solves the fixed point equations (13).


## 3. A Self-Adaptive Projection Algorithm

Based on Proposition6, we construct a self-adaptive projection algorithm for the fixed point equations (13) and prove the weak convergence of the proposed algorithm.Define the functionF
:
H
1
×
H
2
→
H
1 by
(14)
F
(
x
,
y
)
=
A
*
(
A
x
-
B
y
)
and the function G
:
H
1
×
H
2
→
H
2 by
(15)
G
(
x
,
y
)
=
B
*
(
B
y
-
A
x
)
.
The self-adaptive projection algorithm is defined as follows.Algorithm 7.
Given constantsσ
0
>
0,  β
∈
(
0,1
),  θ
∈
(
0,1
) and ρ
∈
(
0,1
), let x
0
∈
H
1 and y
0
∈
H
2 be arbitrary. For k
=
0,1
,
2
,
…, compute
(16)
u
k
=
P
C
(
x
k
-
τ
k
F
(
x
k
,
y
k
)
)
,
v
k
=
P
Q
(
y
k
-
τ
k
G
(
x
k
,
y
k
)
)
,
where γ
k is chosen to be the largest γ
∈
{
σ
k
,
σ
k
β
,
σ
k
β
2
,
…
} satisfying
(17)
∥
F
(
x
k
,
y
k
)
-
F
(
u
k
,
v
k
)
∥
2
+
∥
G
(
x
k
,
y
k
)
-
G
(
u
k
,
v
k
)
∥
2
≤
θ
2
∥
x
k
-
u
k
∥
2
+
∥
y
k
-
v
k
∥
2
γ
2
.
Construct the half-spaces X
k and Y
k, the bounding hyperplanes of which support C and Q at u
k and v
k, respectively,
(18)
X
k
∶
=
{
u
∈
H
1
∣
〈
x
k
-
τ
k
F
(
x
k
,
y
k
)
-
u
k
,
u
-
u
k
〉
≤
0
}
,
Y
k
∶
=
{
v
∈
H
2
∣
〈
y
k
-
τ
k
G
(
x
k
,
y
k
)
-
v
k
,
v
-
v
k
〉
≤
0
}
.
Set
(19)
x
k
+
1
=
P
X
k
(
u
k
-
γ
k
(
F
(
u
k
,
v
k
)
-
F
(
x
k
,
y
k
)
)
)
,
y
k
+
1
=
P
Y
k
(
v
k
-
γ
k
(
G
(
u
k
,
v
k
)
-
G
(
x
k
,
y
k
)
)
)
.
If
(20)
∥
F
(
x
k
+
1
,
y
k
+
1
)
-
F
(
x
k
,
y
k
)
∥
2
+
∥
G
(
x
k
+
1
,
y
k
+
1
)
-
G
(
x
k
,
y
k
)
∥
2
≤
ρ
2
∥
x
k
+
1
-
x
k
∥
2
+
∥
y
k
+
1
-
y
k
∥
2
γ
k
2
,
then set σ
k
=
σ
0; otherwise, set σ
k
=
γ
k.In this algorithm, (19) involves projection onto half-spaces X
k (resp., Y
k) rather than onto the set C (resp., Q) and it is obvious that projections on X (resp., Y) are very simple. It is easy to show C
⊂
X
k and Q
⊂
Y
k. The last step is used to reduce the inner iterations for searching the stepsize γ
k.Lemma 8.
The search rule (17) is well defined. Besides γ
_
≤
γ
k
≤
σ
0, where
(21)
γ
_
=
min
⁡
{
σ
0
,
β
θ
∥
A
∥
2
(
∥
A
∥
2
+
∥
B
∥
2
)
,
β
θ
∥
B
∥
2
(
∥
A
∥
2
+
∥
B
∥
2
)
}
.Proof.
Obviously,γ
k
≤
σ
0. If γ
k
=
σ
0, then this lemma is proved; otherwise, if γ
k
<
σ
0, by the search rule (17), we know that γ
k
/
β must violate inequality (17); that is,
(22)
∥
F
(
x
k
,
y
k
)
-
F
(
u
k
,
v
k
)
∥
2
+
∥
G
(
x
k
,
y
k
)
-
G
(
u
k
,
v
k
)
∥
2
≥
θ
2
∥
x
k
-
u
k
∥
2
+
∥
y
k
-
v
k
∥
2
γ
k
2
/
β
2
.
On the other hand, we have
(23)
∥
F
(
x
k
,
y
k
)
-
F
(
u
k
,
v
k
)
∥
2
+
∥
G
(
x
k
,
y
k
)
-
G
(
u
k
,
v
k
)
∥
2
=
∥
A
*
(
A
x
k
-
B
y
k
)
-
A
*
(
A
u
k
-
B
v
k
)
∥
2
+
∥
B
*
(
B
y
k
-
A
x
k
)
-
B
*
(
B
v
k
-
A
u
k
)
∥
2
≤
(
∥
A
∥
2
+
∥
B
∥
2
)
×
(
∥
A
∥
∥
x
k
-
u
k
∥
+
∥
B
∥
∥
y
k
-
v
k
∥
)
2
≤
2
(
∥
A
∥
2
+
∥
B
∥
2
)
×
(
∥
A
∥
2
∥
x
k
-
u
k
∥
2
+
∥
B
∥
2
∥
y
k
-
v
k
∥
2
)
≤
2
(
∥
A
∥
2
+
∥
B
∥
2
)
max
⁡
{
∥
A
∥
2
,
∥
B
∥
2
}
×
(
∥
x
k
-
u
k
∥
2
+
∥
y
k
-
v
k
∥
2
)
.
Consequently, we get
(24)
γ
k
≥
min
⁡
{
σ
0
,
β
θ
∥
A
∥
2
(
∥
A
∥
2
+
∥
B
∥
2
)
,
β
θ
∥
B
∥
2
(
∥
A
∥
2
+
∥
B
∥
2
)
}
,
which completes the proof.Theorem 9.
Let(
x
k
,
y
k
) be the sequence generated by Algorithm 7 and let X and Y be nonempty closed convex sets in H
1 and H
2 with simple structures, respectively. If (
X
×
Y
)
∩
Γ is nonempty, then (
x
k
,
y
k
) converges weakly to a solution of the SEP (1).Proof.
Let(
x
*
,
y
*
)
∈
Γ; that is, x
*
∈
C, y
*
∈
Q, and A
x
*
=
B
y
*. Define s
k
=
u
k
-
γ
k
(
F
(
u
k
,
v
k
)
-
F
(
x
k
,
y
k
)
); then we have
(25)
∥
x
k
+
1
-
x
*
∥
2
≤
∥
s
k
-
x
*
∥
2
=
∥
s
k
-
u
k
+
u
k
-
x
k
+
x
k
-
x
*
∥
2
=
∥
s
k
-
u
k
∥
2
+
∥
u
k
-
x
k
∥
2
+
∥
x
k
-
x
*
∥
2
+
2
〈
s
k
-
u
k
,
u
k
-
x
*
〉
+
2
〈
u
k
-
x
k
,
x
k
-
x
*
〉
=
∥
x
k
-
x
*
∥
2
+
∥
s
k
-
u
k
∥
2
-
∥
u
k
-
x
k
∥
2
+
2
〈
s
k
-
x
k
,
u
k
-
x
*
〉
=
∥
x
k
-
x
*
∥
2
+
γ
k
2
∥
F
(
u
k
,
v
k
)
-
F
(
x
k
,
y
k
)
∥
2
-
∥
u
k
-
x
k
∥
2
+
2
〈
s
k
-
x
k
,
u
k
-
x
*
〉
,
where the first inequality follows from nonexpansivity of the projection mapping P
X
k. Similarly, defining t
k
=
v
k
-
γ
k
(
G
(
u
k
,
v
k
)
-
G
(
x
k
,
y
k
)
), we get
(26)
∥
y
k
+
1
-
y
*
∥
2
≤
∥
y
k
-
y
*
∥
2
+
γ
k
2
∥
G
(
u
k
,
v
k
)
-
G
(
x
k
,
y
k
)
∥
2
-
∥
v
k
-
y
k
∥
2
+
2
〈
t
k
-
y
k
,
v
k
-
y
*
〉
.
Adding the above inequalities, we obtain
(27)
∥
x
k
+
1
-
x
*
∥
2
+
∥
y
k
+
1
-
y
*
∥
2
≤
∥
x
k
-
x
*
∥
2
+
∥
y
k
-
y
*
∥
2
+
γ
k
2
(
∥
F
(
u
k
,
v
k
)
-
F
(
x
k
,
y
k
)
∥
2
+
∥
G
(
u
k
,
v
k
)
-
G
(
x
k
,
y
k
)
∥
2
)
-
∥
u
k
-
x
k
∥
2
-
∥
v
k
-
y
k
∥
2
+
2
〈
s
k
-
x
k
,
u
k
-
x
*
〉
+
2
〈
t
k
-
y
k
,
v
k
-
y
*
〉
≤
∥
x
k
-
x
*
∥
2
+
∥
y
k
-
y
*
∥
2
-
(
1
-
θ
2
)
×
(
∥
u
k
-
x
k
∥
2
+
∥
v
k
-
y
k
∥
2
)
+
2
〈
s
k
-
x
k
,
u
k
-
x
*
〉
+
2
〈
t
k
-
y
k
,
v
k
-
y
*
〉
=
∥
x
k
-
x
*
∥
2
+
∥
y
k
-
y
*
∥
2
-
(
1
-
θ
2
)
×
(
∥
u
k
-
x
k
∥
2
+
∥
v
k
-
y
k
∥
2
)
+
2
〈
u
k
-
γ
k
F
(
u
k
,
v
k
)
+
γ
k
F
(
x
k
,
y
k
)
-
x
k
,
u
k
-
x
*
〉
+
2
〈
v
k
-
γ
k
G
(
u
k
,
v
k
)
+
γ
k
G
(
x
k
,
y
k
)
-
y
k
,
v
k
-
y
*
〉
≤
∥
x
k
-
x
*
∥
2
+
∥
y
k
-
y
*
∥
2
-
(
1
-
θ
2
)
(
∥
u
k
-
x
k
∥
2
+
∥
v
k
-
y
k
∥
2
)
-
2
γ
k
〈
F
(
u
k
,
v
k
)
,
u
k
-
x
*
〉
-
2
γ
k
〈
G
(
u
k
,
v
k
)
,
v
k
-
y
*
〉
,
where the equality follows from s
k
=
u
k
-
γ
k
(
F
(
u
k
,
v
k
)
-
F
(
x
k
,
y
k
)
) and t
k
=
v
k
-
γ
k
(
G
(
u
k
,
v
k
)
-
G
(
x
k
,
y
k
)
), the second inequality follows from (17), and the last follows from (16) and Lemma 3 and x
*
∈
C,y
*
∈
Q. Using the fact and A
x
*
=
B
y
*, we have
(28)
〈
F
(
u
k
,
v
k
)
,
u
k
-
x
*
〉
+
〈
G
(
u
k
,
v
k
)
,
v
k
-
y
*
〉
=
〈
A
*
(
A
u
k
-
B
v
k
)
,
u
k
-
x
*
〉
+
〈
B
*
(
B
v
k
-
A
u
k
)
,
v
k
-
y
*
〉
=
〈
A
u
k
-
B
v
k
,
A
u
k
-
A
x
*
〉
+
〈
B
v
k
-
A
u
k
,
B
v
k
-
B
y
*
〉
=
∥
A
u
k
-
B
v
k
∥
2
,
which with (27) implies that
(29)
∥
x
k
+
1
-
x
*
∥
2
+
∥
y
k
+
1
-
y
*
∥
2
≤
∥
x
k
-
x
*
∥
2
+
∥
y
k
-
y
*
∥
2
-
(
1
-
θ
2
)
×
(
∥
u
k
-
x
k
∥
2
+
∥
v
k
-
y
k
∥
2
)
-
2
γ
k
∥
A
u
k
-
B
v
k
∥
2
.
Consequently, the sequence Γ
k
(
x
*
,
y
*
)
∶
=
∥
x
k
-
x
*
∥
2
+
∥
y
k
-
y
*
∥
2 is decreasing and lower bounded by 0 and thus converges to some finite limit, say, l
(
x
*
,
y
*
). Moreover, (
x
k
) and (
y
k
) are bounded. This implies that
(30)
lim
⁡
k
→
∞
∥
u
k
-
x
k
∥
=
0
,
lim
⁡
k
→
∞
∥
v
k
-
y
k
∥
=
0
,
lim
⁡
k
→
∞
∥
A
u
k
-
B
v
k
∥
=
0
.
From (30), we get
(31)
lim
⁡
k
→
∞
∥
A
x
k
-
B
y
k
∥
=
0
.
Let(
x
^
,
y
^
)
∈
ω
w
(
x
k
,
y
k
); then there exist the two subsequences (
x
k
l
) and (
y
k
l
) of (
x
k
) and (
y
k
) which converge weakly to x
^ and y
^, respectively. We will show that (
x
^
,
y
^
) is a solution of the SEP (1). The weak convergence of (
A
x
k
l
-
B
y
k
l
) to A
x
^
-
B
y
^ and lower semicontinuity of the squared norm imply that
(32)
∥
A
x
^
-
B
y
^
∥
≤
liminf
⁡
l
→
∞
∥
A
x
k
l
-
B
y
k
l
∥
=
0
;
that is, A
x
^
=
B
y
^.
By noting that the two equalities in (16) can be rewritten as
(33)
x
k
l
-
u
k
l
γ
k
l
-
A
*
(
A
u
k
l
-
B
v
k
l
)
∈
N
C
(
u
k
l
)
,
y
k
l
-
v
k
l
γ
k
l
-
B
*
(
B
v
k
l
-
A
u
k
l
)
∈
N
Q
(
v
k
l
)
,
and that the graphs of the maximal monotone operators, N
C and N
Q, are weakly-strongly closed and by passing to the limit in the last inclusions, we obtain, from (30), that
(34)
x
^
∈
C
,
y
^
∈
Q
.
Hence (
x
^
,
y
^
)
∈
Γ.
To show the uniqueness of the weak cluster points, we will use the same strick as in the celebrated Opial Lemma. Indeed, let(
x
¯
,
y
¯
) be other weak cluster point of (
x
k
,
y
k
). By passing to the limit in the relation
(35)
Γ
k
(
x
^
,
y
^
)
=
Γ
k
(
x
¯
,
y
¯
)
+
∥
x
^
-
x
¯
∥
2
+
∥
y
^
-
y
¯
∥
2
+
2
〈
x
k
-
x
¯
,
x
¯
-
x
^
〉
+
2
〈
y
k
-
y
¯
,
y
¯
-
y
^
〉
,
we obtain
(36)
l
(
x
^
,
y
^
)
=
l
(
x
¯
,
y
¯
)
+
∥
x
^
-
x
¯
∥
2
+
∥
y
^
-
y
¯
∥
2
.
Reversing the role of (
x
^
,
y
^
) and (
x
¯
,
y
¯
), we also have
(37)
l
(
x
¯
,
y
¯
)
=
l
(
x
^
,
y
^
)
+
∥
x
^
-
x
¯
∥
2
+
∥
y
^
-
y
¯
∥
2
.
By adding the two last equalities, we obtain
(38)
∥
x
^
-
x
¯
∥
2
+
∥
y
^
-
y
¯
∥
2
=
0
.
Hence (
x
^
,
y
^
)
=
(
x
¯
,
y
¯
); this implies that the whole sequence (
x
k
,
y
k
) weakly converges to a solution of the SEP (1), which completes the proof.


## 4. A Relaxed Self-Adaptive Projection Algorithm

In Algorithm7, we must calculate the orthogonal projections, P
C and P
Q, many times even in one iteration step, so they should be assumed to be easily calculated; however, sometimes it is difficult or even impossible to compute them. In this case, we always turn to relaxed methods [13, 14], which were introduced by Fukushima [15] and are more easily implemented. For solving the SEP (1), Moudafi [16] followed the ideas of Fukushima [15] and introduced a relaxed alternating C
Q algorithm which depends on the norms ∥
A
∥ and ∥
B
∥. In this section, we propose a relaxed scheme for the self-adaptive Algorithm 7.Assume that the convex setsC and Q are given by
(39)
C
=
{
x
∈
H
1
:
c
(
x
)
≤
0
}
,
Q
=
{
y
∈
H
2
:
q
(
y
)
≤
0
}
,
where c
:
H
1
→
ℝ and q
:
H
2
→
ℝ are convex functions which are subdifferentiable on C and Q, respectively, and we assume that their subdifferentials are bounded on bounded sets.In thekth iteration, let (
C
k
) and (
Q
k
) be two sequences of closed convex sets defined by
(40)
C
k
=
{
x
∈
H
1
:
c
(
x
k
)
+
〈
ξ
k
,
x
-
x
k
〉
≤
0
}
,
where ξ
k
∈
∂
c
(
x
k
) and
(41)
Q
k
=
{
y
∈
H
2
:
q
(
y
k
)
+
〈
η
k
,
y
-
y
k
〉
≤
0
}
,
where η
k
∈
∂
q
(
y
k
).It is easy to see thatC
k
⊃
C and Q
k
⊃
Q for every k
≥
0.Algorithm 10.
Given constantsσ
0
>
0,  β
∈
(
0,1
),  θ
∈
(
0,1
),  and ρ
∈
(
0,1
), let x
0
∈
H
1 and y
0
∈
H
2 be arbitrary. For k
=
0,1
,
2
,
…, compute
(42)
u
k
=
P
C
k
(
x
k
-
τ
k
F
(
x
k
,
y
k
)
)
,
v
k
=
P
Q
k
(
y
k
-
τ
k
G
(
x
k
,
y
k
)
)
,
where γ
k is chosen to be the largest γ
∈
{
σ
k
,
σ
k
β
,
σ
k
β
2
,
…
} satisfying
(43)
∥
F
(
x
k
,
y
k
)
-
F
(
u
k
,
v
k
)
∥
2
+
∥
G
(
x
k
,
y
k
)
-
G
(
u
k
,
v
k
)
∥
2
≤
θ
2
∥
x
k
-
u
k
∥
2
+
∥
y
k
-
v
k
∥
2
γ
2
.
Construct the half-spaces X
k and Y
k the bounding hyperplanes of which support C
k and Q
k at u
k and v
k, respectively,
(44)
X
k
∶
=
{
u
∈
H
1
∣
〈
x
k
-
τ
k
F
(
x
k
,
y
k
)
-
u
k
,
u
-
u
k
〉
≤
0
}
,
Y
k
∶
=
{
v
∈
H
2
∣
〈
y
k
-
τ
k
G
(
x
k
,
y
k
)
-
v
k
,
v
-
v
k
〉
≤
0
}
.
Set
(45)
x
k
+
1
=
P
X
(
u
k
-
γ
k
(
F
(
u
k
,
v
k
)
-
F
(
x
k
,
y
k
)
)
)
,
y
k
+
1
=
P
Y
(
v
k
-
γ
k
(
G
(
u
k
,
v
k
)
-
G
(
x
k
,
y
k
)
)
)
.
If
(46)
∥
F
(
x
k
+
1
,
y
k
+
1
)
-
F
(
x
k
,
y
k
)
∥
2
+
∥
G
(
x
k
+
1
,
y
k
+
1
)
-
G
(
x
k
,
y
k
)
∥
2
≤
ρ
2
∥
x
k
+
1
-
x
k
∥
2
+
∥
y
k
+
1
-
y
k
∥
2
γ
k
2
,
then set σ
k
=
σ
0; otherwise, set σ
k
=
γ
k.Following the proof of Lemma8, we easily obtain the following.Lemma 11.
The search rule (43) is well defined. Besides γ
_
≤
γ
k
≤
σ
0, where
(47)
γ
_
=
min
⁡
{
σ
0
,
β
θ
∥
A
∥
2
(
∥
A
∥
2
+
∥
B
∥
2
)
,
β
θ
∥
B
∥
2
(
∥
A
∥
2
+
∥
B
∥
2
)
}
.Theorem 12.
Let(
x
k
,
y
k
) be the sequence generated by Algorithm 10 and let X and Y be nonempty closed convex sets in H
1 and H
2 with simple structures, respectively. If (
X
×
Y
)
∩
Γ is nonempty, then (
x
k
,
y
k
) converges weakly to a solution of the SEP (1).Proof.
Let(
x
*
,
y
*
)
∈
Γ; that is, x
*
∈
C, y
*
∈
Q, and A
x
*
=
B
y
*. Following the similar proof of Theorem 9, we obtain
(48)
∥
x
k
+
1
-
x
*
∥
2
+
∥
y
k
+
1
-
y
*
∥
2
≤
∥
x
k
-
x
*
∥
2
+
∥
y
k
-
y
*
∥
2
-
(
1
-
θ
2
)
(
∥
u
k
-
x
k
∥
2
+
∥
v
k
-
y
k
∥
2
)
-
2
γ
k
∥
A
u
k
-
B
v
k
∥
2
.
Let Γ
k
(
x
*
,
y
*
)
∶
=
∥
x
k
-
x
*
∥
2
+
∥
y
k
-
y
*
∥
2. Then the sequence Γ
k
(
x
*
,
y
*
) is decreasing and lower bounded by 0 for that μ
∈
(
0,1
) and thus converges to some finite limit, say, l
(
x
*
,
y
*
). Moreover, (
x
k
) and (
y
k
) are bounded. This implies that
(49)
lim
⁡
k
→
∞
∥
u
k
-
x
k
∥
=
0
,
lim
⁡
k
→
∞
∥
v
k
-
y
k
∥
=
0
,
(50)
lim
⁡
k
→
∞
∥
A
u
k
-
B
v
k
∥
=
0
.
Therefore, we have
(51)
lim
⁡
k
→
∞
∥
A
x
k
-
B
y
k
∥
=
0
.
Next we show that the sequence(
x
k
,
y
k
) generated by Algorithm 10 weakly converges to a solution of the SEP (1). Let (
x
^
,
y
^
)
∈
ω
w
(
x
k
,
y
k
); then there exist the two subsequences (
x
k
l
) and (
y
k
l
) of (
x
k
) and (
y
k
) which converge weakly to x
^ and y
^, respectively. The weak convergence of (
A
x
k
l
-
B
y
k
l
) to A
x
^
-
B
y
^ and the lower semicontinuity of the squared norm imply that
(52)
∥
A
x
^
-
B
y
^
∥
≤
liminf
⁡
l
→
∞
∥
A
x
k
l
-
B
y
k
l
∥
=
0
;
that is, A
x
^
=
B
y
^.
Sinceu
k
l
∈
C
k
l, we have
(53)
c
(
x
k
l
)
+
〈
ξ
k
,
u
k
l
-
x
k
l
〉
≤
0
.
Thus
(54)
c
(
x
k
l
)
≤
-
〈
ξ
k
l
,
u
k
l
-
x
k
l
〉
≤
ξ
∥
u
k
l
-
x
k
l
∥
,
where ξ satisfies ∥
ξ
k
∥
≤
ξ for all k
∈
ℕ. The lower semicontinuity of c and the first formula of (49) lead to
(55)
c
(
x
^
)
≤
liminf
⁡
l
→
∞
c
(
x
k
l
)
≤
0
,
and therefore x
^
∈
C.
Likewise, sincev
k
l
∈
Q
k
l, we have
(56)
q
(
y
k
l
)
+
〈
η
k
l
,
v
k
l
-
y
k
l
〉
≤
0
.
Thus
(57)
q
(
y
k
l
)
≤
-
〈
η
k
l
,
v
k
l
-
y
k
l
〉
≤
η
∥
v
k
l
-
y
k
l
∥
,
where η satisfies ∥
η
k
∥
≤
η for all k
∈
ℕ. Again, the lower semicontinuity of q and the second formula of (49) lead to
(58)
q
(
y
^
)
≤
liminf
⁡
l
→
∞
q
(
y
k
l
)
≤
0
,
and therefore y
^
∈
Q. Hence (
x
^
,
y
^
)
∈
Γ.
Following the same argument of Theorem9, we can show the uniqueness of the weak cluster points and hence the whole sequence (
x
k
,
y
k
) weakly converges to a solution of the SEP (1), which completes the proof.



---

*Source: 328787-2014-01-19.xml*