# On an Iterative Method for Finding a Zero to the Sum of Two Maximal Monotone Operators

Authors: Hongwei Jiao; Fenghui Wang
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

In this paper we consider a problem that consists of finding a zero to the sum of two monotone operators. One method for solving such a problem is the forward-backward splitting method. We present some new conditions that guarantee the weak convergence of the forward-backward method. Applications of these results, including variational inequalities and gradient projection algorithms, are also considered.


---

## Body

## 1. Introduction

It is well known that monotone inclusions problems play an important role in the theory of nonlinear analysis. This problem consists of finding a zero of maximal monotone operators. However, in some examples such as convex programming and variational inequality problems, the operator is needed to be decomposed of the sum of two monotone operators (see, e.g., [1–6]). In this way, one needs to find x
∈
H so that
(1)
0
∈
A
x
+
B
x
,
where A and B are two monotone operators on a Hilbert space H. To solve such problem, the splitting method, such as Peaceman-Rachford algorithm [7] and Douglas-Rachford algorithm [8], is usually considered. We consider a special case whenever B
:
H
→
2
H is multivalued and A
:
H
→
H is single-valued. A classical way to solve problem (1) under our assumption is the forward-backward splitting (FBS) (see [2, 9]). Starting with an arbitrary initial x
0
∈
H, the FBS generates a sequence (
x
n
) satisfying
(2)
x
n
+
1
=
(
I
+
r
B
)
-
1
(
I
-
r
A
)
x
n
,
where r is some properly chosen real number. Then the FBS converges weakly to a solution of problem (1) whenever such point exists.On the other hand, we observe that problem (1) is equivalent to the fixed point equation:
(3)
(
I
+
r
B
)
-
1
(
I
-
r
A
)
x
=
x
,
for the single-valued operator (
I
+
r
B
)
-
1
(
I
-
r
A
). Moreover, if r is properly chosen, the operator (
I
+
r
B
)
-
1
(
I
-
r
A
) should be nonexpansive. Motivated by this assumption, by using the techniques of the fixed point theory for nonexpansive operators, we try to investigate and study various monotone inclusion problems.The rest of this paper is organized as follows. In Section2, some useful lemmas are introduced. In Section 3, we consider the modified forward-backward splitting method and prove its weak convergence under some new conditions. In Section 4, some applications of our results in finding a solution of the variational inequality problem are included.


## 2. Preliminary and Notation

Throughout the paper,I denotes the identity operator, Fix
⁡
(
S
) the set of the fixed points of an operator S, and ∇
f the gradient of the functional f
:
H
→
R. The notation “→” denotes strong convergence and “⇀” weak convergence. Denote by ω
w
(
x
n
) the set of the cluster points of (
x
n
) in the weak topology (i.e., the set {
x
:
∃
x
n
j
⇀
x
}, where (
x
n
j
) means a subsequence of (
x
n
)).LetC be a nonempty closed convex subset of H. Denote by P
C the projection from H onto C; namely, for x
∈
H, P
C
x is the unique point in C with the property
(4)
∥
x
-
P
C
x
∥
=
min
⁡
y
∈
C
∥
x
-
y
∥
.
It is well-known that P
C
x is characterized by the inequality
(5)
〈
x
-
P
C
x
,
z
-
P
C
x
〉
≤
0
,
z
∈
C
.
A single-valued operator S
:
H
→
H is called nonexpansive if
(6)
∥
S
x
-
S
y
∥
≤
∥
x
-
y
∥
(
∀
x
,
y
∈
H
)
;
firmly nonexpansive if
(7)
〈
S
x
-
S
y
,
x
-
y
〉
≥
∥
S
x
-
S
y
∥
2
(
∀
x
,
y
∈
H
)
;
and κ-averaged if there exists a constant κ
∈
(
0,1
) and a nonexpansive operator R such that S
=
(
1
-
κ
)
I
+
κ
R. Firmly nonexpansive operators are (
1
/
2
)-averaged.Lemma 1 (see [10]).
The following assertions hold.(i)
S is κ-averaged for κ
∈
(
0,1
) if and only if
(8)
∥
S
x
-
S
y
∥
2
≤
∥
x
-
y
∥
2
-
1
-
κ
κ
∥
(
I
-
S
)
x
-
(
I
-
S
)
y
∥
2
for allx
,
y
∈
dom
⁡
S.
(ii)
Assume thatS
i is κ
i-averaged for κ
i
∈
(
0,1
)
,
i
=
1,2. Then S
1
S
2 is κ-averaged with κ
=
κ
1
+
κ
2
-
κ
1
κ
2.The following lemma is known as the demiclosedness principle for nonexpansive mappings.Lemma 2.
LetC be a nonempty closed convex subset of H and S a nonexpansive operator with Fix
⁡
(
S
)
≠
∅. If (
x
n
) is a sequence in C such that x
n
⇀
x and (
I
-
S
)
x
n
→
y, then (
I
-
S
)
x
=
y. In particular, if y
=
0, then x
∈
Fix
⁡
(
S
).A multivalued operatorB
:
H
→
2
H is called monotone if
(9)
〈
u
-
v
,
x
-
y
〉
≥
0
,
(
∀
u
∈
B
x
,
v
∈
B
y
)
;
κ-inverse strongly monotone (κ-ism), if there exists a constant κ
>
0 so that
(10)
〈
u
-
v
,
x
-
y
〉
≥
κ
∥
u
-
v
∥
2
,
(
∀
u
∈
B
x
,
v
∈
B
y
)
;
and maximal monotone if it is monotone and its graph G
(
B
)
=
{
(
x
,
y
)
:
y
∈
B
x
} is not properly contained in the graph of any other monotone operator.In what follows, we shall assume that(i)
A
:
H
→
H is single-valued and κ-ism;
(ii)
B
:
H
→
2
H is multivalued and maximal monotone. Hereafter, if no confusion occurs, we denote by
(11)
J
r
:
=
(
I
+
r
B
)
-
1
the resolvent of B for any given r
>
0. It is known that J
r is single-valued and firmly nonexpansive; moreover dom
⁡
(
I
+
r
B
)
=
H (see [11]).Lemma 3 (see [12]).
Forr
>
0, let T
r
=
J
r
(
I
-
r
A
). Then(i)
Fix
⁡
(
T
r
)
=
(
A
+
B
)
-
1
(
0
);
(ii)
T
r is (
2
κ
+
r
)
/
4
κ-averaged;
(iii)
For0
<
r
≤
s
≤
2
κ
,
x
∈
H, it follows that
(12)
∥
x
-
T
r
x
∥
≤
2
∥
x
-
T
s
x
∥
,
∥
T
s
x
-
T
r
x
∥
≤
|
1
-
r
s
|
∥
x
-
T
s
x
∥
.Definition 4.
Assume that(
x
n
) is a sequence in H and that (
ϵ
n
) is a real sequence with ∑
n
‍
ϵ
n
<
∞. Then (
x
n
) is calledquasi Fejér monotone w.r.t. C, if
(13)
∥
x
n
+
1
-
z
∥
≤
∥
x
n
-
z
∥
+
ϵ
n
(
∀
z
∈
C
)
.Lemma 5 (see [13]).
LetC be a nonempty closed convex subset of H. If the sequence (
x
n
) is quasi-Fejér-monotone w.r.t. C, then the following hold:(i)
x
n
⇀
x
*
∈
C if and only if ω
w
(
x
n
)
⊆
C;
(ii)
the sequence(
P
C
x
n
) converges strongly;
(iii)
ifx
n
⇀
x
*
∈
C, then x
*
=
lim
⁡
n
→
∞
P
C
x
n.


## 3. Weak Convergence Theorem

In [10] Combettes considered a modified FBS: for any initial guess x
0
∈
H, set
(14)
x
n
+
1
=
(
1
-
α
n
)
x
n
+
α
n
J
r
n
(
x
n
-
r
n
A
x
n
)
+
e
n
,
where (
α
n
)
⊆
[
0,1
]
,
(
r
n
)
⊆
[
0,2
κ
] and (
e
n
)
⊆
H is computation error. He proved the weak convergence of algorithm (14) provided that (1)
lim
⁡
_
n
α
n
>
0,
(2)
0
<
lim
⁡
_
n
r
n
≤
lim
⁡
¯
n
r
n
<
2
κ,
(3)
∑
n
‍
∥
e
n
∥
<
∞.We observe that (14) is in fact a Mann-type iteration. In the following we shall prove the convergence of (14) under some sightly weak conditions.Theorem 6.
Suppose the following conditions are satisfied:(C1)
lim
⁡
¯
n
α
n
>
0;
(C2)
0
≤
r
n
≤
2
κ;
(C3)
0
≤
α
n
≤
4
κ
/
(
2
κ
+
r
n
);
(C4)
lim
⁡
¯
n
(
4
κ
/
(
2
κ
+
r
n
)
-
α
n
)
>
0;
(C5)
∑
n
‍
∥
e
n
∥
<
∞.If in addition Ω
:
=
(
A
+
B
)
-
1
(
0
)
≠
∅, then the sequence (
x
n
) generated by (14) converges weakly to x
*
:
=
P
Ω
x
n.Proof.
We first show that(
x
n
) is quasi-Fejér-monotone. Let T
n
=
J
r
n
(
I
-
r
n
A
). Then It follows from Lemma 3 that T
n is β
n-averaged with β
n
=
(
2
κ
+
r
n
)
/
4
κ and Ω
=
Fix
⁡
(
T
n
). Letting z
∈
Ω, we have that
(15)
∥
x
n
+
1
-
z
∥
=
∥
(
1
-
α
n
)
(
x
n
-
z
)
+
α
n
(
T
n
x
n
-
z
)
+
e
n
∥
≤
(
1
-
α
n
)
∥
x
n
-
z
∥
+
α
n
∥
x
n
-
z
∥
+
∥
e
n
∥
=
∥
x
n
-
z
∥
+
∥
e
n
∥
.
By condition (C5), we conclude that (
x
n
) is quasi-Fejér-monotone w.r.t Ω.
Next let us showω
w
(
x
n
)
⊆
Ω. To see this, choose M
>
0 so that
(16)
2
sup
⁡
n
≥
0
(
∥
x
n
-
z
∥
)
≤
M
.
Let R
n
=
(
1
-
α
n
)
I
+
α
n
T
n. Obviously R
n is α
n
β
n-averaged. According to Lemma 1, we deduce that
(17)
∥
x
n
+
1
-
z
∥
2
=
∥
(
(
1
-
α
n
)
I
+
α
n
T
n
)
x
n
-
z
+
e
n
∥
2
≤
∥
R
n
x
n
-
z
∥
2
+
2
〈
x
n
+
1
-
z
,
e
n
〉
≤
∥
R
n
x
n
-
z
∥
2
+
M
∥
e
n
∥
≤
∥
x
n
-
z
∥
2
-
1
-
α
n
β
n
α
n
β
n
∥
R
n
x
n
-
x
n
∥
2
+
M
∥
e
n
∥
≤
∥
x
n
-
z
∥
2
-
α
n
(
1
β
n
-
α
n
)
∥
T
n
x
n
-
x
n
∥
2
+
M
∥
e
n
∥
,
which in turn implies that
(18)
∑
i
=
0
n
‍
α
i
(
1
β
i
-
α
i
)
∥
T
i
x
i
-
x
i
∥
2
≤
∥
x
0
-
z
∥
2
+
M
∑
i
=
0
∞
‍
∥
e
i
∥
for all n
∈
N. Letting n
→
∞ yields
(19)
∑
n
=
0
∞
‍
α
n
(
1
β
n
-
α
n
)
∥
T
n
x
n
-
x
n
∥
2
<
∞
.
By conditions (C1) and (C4), we check that
(20)
liminf
⁡
n
→
∞
α
n
(
1
β
n
-
α
n
)
>
0
,
which yields that ∥
T
n
x
n
-
x
n
∥
→
0. By condition (C2), we find n
0
∈
N and r
∈
(
0,2
κ
] so that r
n
≥
r for all n
≥
n
0. Let T
r
=
J
r
(
I
-
r
B
). It then follows from Lemma 3 that
(21)
∥
T
r
x
n
-
x
n
∥
≤
2
∥
T
n
x
n
-
x
n
∥
for all n
≥
n
0. Letting n
→
∞, we have ∥
T
r
x
n
-
x
n
∥
→
0 as n
→
∞. Take x
′
∈
ω
w
(
x
n
) and a subsequence (
x
n
k
) of (
x
n
) such that x
n
k
⇀
x
′. Since T
r is nonexpansive, applying Lemmas 2 and 3 yields x
′
∈
Fix
⁡
(
T
r
)
=
Ω and thus ω
w
(
x
n
)
⊆
Ω. By Lemma 5 the proof is complete.We can also present another condition for the weak convergence of (14).Theorem 7.
Suppose that the following conditions are satisfied:(C1)
∑
n
‍
|
r
n
+
1
-
r
n
|
<
∞;
(C2)
0
<
lim
⁡
n
r
n
≤
2
κ;
(C3)
0
≤
α
n
≤
4
κ
/
(
2
κ
+
r
n
);
(C4)
∑
n
‍
α
n
(
4
κ
/
(
2
κ
+
r
n
)
-
α
n
)
=
∞;
(C5)
∑
n
‍
∥
e
n
∥
<
∞.If in addition Ω
:
=
(
A
+
B
)
-
1
(
0
)
≠
∅, then the sequence (
x
n
) generated by (14) converges weakly to x
*
:
=
P
Ω
x
n.Proof.
Compared with the proof of Theorem6, it suffices to show that ∥
T
n
x
n
-
x
n
∥
→
0 as n
→
∞. Observe that the estimate
(22)
∑
n
=
0
∞
‍
α
n
(
4
κ
2
κ
+
r
n
-
α
n
)
∥
T
n
x
n
-
x
n
∥
2
<
∞
still holds. Let a
n
:
=
∥
x
n
-
T
n
x
n
∥. Then by condition (C4) lim
⁡
_
n
a
n
=
0. According to Lemma 3, we have
(23)
a
n
+
1
=
∥
(
1
-
α
n
)
(
x
n
-
T
n
x
n
)
+
(
T
n
x
n
-
T
n
+
1
x
n
+
1
)
+
e
n
∥
≤
(
1
-
α
n
)
∥
x
n
-
T
n
x
n
∥
+
∥
T
n
x
n
-
T
n
+
1
x
n
+
1
∥
+
∥
e
n
∥
≤
(
1
-
α
n
)
∥
x
n
-
T
n
x
n
∥
+
∥
T
n
+
1
x
n
-
T
n
+
1
x
n
+
1
∥
+
∥
T
n
x
n
-
T
n
+
1
x
n
∥
+
∥
e
n
∥
≤
(
1
-
α
n
)
∥
x
n
-
T
n
x
n
∥
+
∥
x
n
-
x
n
+
1
∥
+
∥
T
n
x
n
-
T
n
+
1
x
n
∥
+
∥
e
n
∥
=
(
1
-
α
n
)
∥
x
n
-
T
n
x
n
∥
+
∥
α
n
(
x
n
-
T
n
x
n
)
-
e
n
∥
+
|
1
-
r
n
+
1
r
n
|
∥
x
n
-
T
n
x
n
∥
+
∥
e
n
∥
≤
(
1
-
α
n
)
∥
x
n
-
T
n
x
n
∥
+
α
n
∥
x
n
-
T
n
x
n
∥
+
|
1
-
r
n
+
1
r
n
|
∥
x
n
-
T
n
x
n
∥
+
2
∥
e
n
∥
≤
a
n
+
M
(
|
r
n
-
r
n
+
1
|
+
∥
e
n
∥
)
,
where M
>
0 is properly chosen real number. Then, for any given p
∈
N, we arrive at
(24)
a
n
+
p
≤
a
n
+
M
∑
i
=
n
∞
‍
(
|
r
i
-
r
i
+
1
|
+
∥
e
i
∥
)
.
Conditions (C1) and (C5) imply that lim
⁡
n
→
∞
a
n exists and therefore ∥
x
n
-
T
n
x
n
∥
→
0 as n
→
∞. Hence the proof is complete.Applying Theorem7, one can easily get the following.Corollary 8.
Suppose that the following conditions are satisfied:(1)
0
<
r
<
2
κ,
(2)
0
≤
α
n
≤
4
κ
/
(
2
κ
+
r
);
(3)
∑
n
‍
α
n
(
4
κ
/
(
2
κ
+
r
)
-
α
n
)
=
∞,
(4)
Ω
:
=
(
A
+
B
)
-
1
(
0
)
≠
∅. Then the sequence (
x
n
) generated by
(25)
x
n
+
1
=
(
1
-
α
n
)
x
n
+
α
n
J
r
(
x
n
-
r
A
x
n
)
converges weakly to some point in Ω.Remark 9.
Corollary8 implies that our condition is slightly weaker than that of Combettes’ whenever the sequence (
r
n
) approaches to some constant.


## 4. Application

LetC be a nonempty closed convex subset of H. A variational inequality problem (VIP) is formulated as a problem of finding a point x
*
∈
C with the property
(26)
〈
A
x
*
,
z
-
x
*
〉
≥
0
,
∀
z
∈
C
,
where A
:
H
→
H is a nonlinear operator. We shall denote by Ω the solution set of VIP (26). One method for solving VIP is the projection algorithm which generates, starting with an arbitrary initial x
0
∈
H, a sequence (
x
n
) satisfying
(27)
x
n
+
1
=
P
C
(
x
n
-
r
A
x
n
)
,
where r is properly chosen real number. If, in addition, A is κ-ism, then the iteration (27) with 0
<
r
<
2
κ converges weakly to a point in Ω, whenever such point exists.LetB be the normal cone for C, that is, B
:
=
{
w
∈
H
:
〈
x
-
z
,
w
〉
≥
0
,
∀
z
∈
C
}. By [14, Theorem 3], VIP (26) is equivalent to finding a zero of the maximal monotone operator A
+
B. Recalling P
C
=
J
r for any r
>
0, we thus can apply the previous results to get the following.Corollary 10.
Suppose the following conditions are satisfied:(C1)
lim
⁡
¯
n
α
n
>
0;
(C2)
0
≤
r
n
≤
2
κ;
(C3)
0
≤
α
n
≤
4
κ
/
(
2
κ
+
r
n
);
(C4)
lim
⁡
¯
n
(
4
κ
/
(
2
κ
+
r
n
)
-
α
n
)
>
0. Then the sequence (
x
n
) generated by
(28)
x
n
+
1
=
(
1
-
α
n
)
x
n
+
α
n
P
C
(
x
n
-
r
n
A
x
n
)
converges weakly to x
*
:
=
P
Ω
x
n, whenever such point exists.Corollary 11.
Suppose that the following conditions are satisfied:(C1)
∑
n
‍
|
r
n
+
1
-
r
n
|
<
∞;
(C2)
0
<
lim
⁡
n
r
n
≤
2
κ;
(C3)
0
≤
α
n
≤
4
κ
/
(
2
κ
+
r
n
);
(C4)
∑
n
‍
α
n
(
4
κ
/
(
2
κ
+
r
n
)
-
α
n
)
=
∞. Then the sequence (
x
n
) generated by
(29)
x
n
+
1
=
(
1
-
α
n
)
x
n
+
α
n
P
C
(
x
n
-
r
n
A
x
n
)
converges weakly to x
*
:
=
P
Ω
x
n, whenever such point exists.Consider the optimization problem of finding a pointx
* with the property
(30)
x
*
∈
arg
min
⁡
x
∈
C
f
(
x
)
,
where f
:
H
→
R is a convex and differentiable function. The gradient projection algorithm (GPA) generates a sequence (
x
n
) by the iterative procedure
(31)
x
n
+
1
=
P
C
(
x
n
-
r
∇
f
(
x
n
)
)
,
where x
0
∈
H and r is a positive parameter. If, in addition, ∇
f is (
1
/
κ
)-Lipschitz continuous, that is, for any x
,
y
∈
H,
(32)
∥
∇
f
(
x
)
-
∇
f
(
y
)
∥
≤
1
κ
∥
x
-
y
∥
,
then the GPA with 0
<
r
<
2
κ converges weakly to a minimizer of f onto C, if such minimizers exist (see, e.g., [15, Corollary 4.1]). Denote by Ω the solution set of the variational inequality
(33)
〈
∇
f
(
x
)
,
z
-
x
〉
≥
0
,
z
∈
C
.
According to [16, Lemma 5.13], we have Ω
=
arg
min
⁡
x
∈
C
f
(
x
). Further, if ∇
f is (
1
/
κ
)-Lipschitz continuous, then it is also κ-ism (see [17, Corollary 10]). Thus, we can apply the previous results by letting A
=
∇
f.Corollary 12.
Assume thatf
:
H
→
R is convex and differentiable with (
1
/
κ
)-Lipschitz-continuous gradient ∇
f and that (C1)
lim
⁡
¯
n
α
n
>
0;
(C2)
0
≤
r
n
≤
2
κ;
(C3)
0
≤
α
n
≤
4
κ
/
(
2
κ
+
r
n
);
(C4)
lim
⁡
¯
n
(
4
κ
/
(
2
κ
+
r
n
)
-
α
n
)
>
0. Then the sequence (
x
n
) generated by
(34)
x
n
+
1
=
(
1
-
α
n
)
x
n
+
α
n
P
C
(
x
n
-
r
n
∇
f
(
x
n
)
)
converges weakly to x
*
:
=
P
Ω
x
n, whenever such point exists.Corollary 13.
Assume thatf
:
H
→
R is convex and differentiable with (
1
/
κ
)-Lipschitz-continuous gradient ∇
f and that (C1)
∑
n
‍
|
r
n
+
1
-
r
n
|
<
∞;
(C2)
0
<
lim
⁡
n
r
n
≤
2
κ;
(C3)
0
≤
α
n
≤
4
κ
/
(
2
κ
+
r
n
);
(C4)
∑
n
‍
α
n
(
4
κ
/
(
2
κ
+
r
n
)
-
α
n
)
=
∞. Then the sequence (
x
n
) generated by
(35)
x
n
+
1
=
(
1
-
α
n
)
x
n
+
α
n
P
C
(
x
n
-
r
n
∇
f
(
x
n
)
)
converges weakly to x
*
:
=
P
Ω
x
n, whenever such point exists.



---

*Source: 414031-2014-08-21.xml*