Best Approximation from the Kuhn

Best Approximation from the Kuhn-Tucker Set of
Composite Monotone Inclusions∗
arXiv:1401.8005v1 [math.OC] 30 Jan 2014
Abdullah Alotaibi,♮ Patrick L. Combettes,♭,♮ and Naseer Shahzad ♮
♮
King Abdulaziz University
Department of Mathematics, P. O. Box 80203
Jeddah 21859, Saudi Arabia
♭
Sorbonne Universit´
es – UPMC Univ. Paris 06
UMR 7598, Laboratoire Jacques-Louis Lions
F-75005, Paris, France
Abstract
Kuhn-Tucker points play a fundamental role in the analysis and the numerical solution of monotone inclusion problems, providing in particular both primal and dual solutions. We propose a
class of strongly convergent algorithms for constructing the best approximation to a reference
point from the set of Kuhn-Tucker points of a general Hilbertian composite monotone inclusion
problem. Our framework does not impose additional assumptions on the operators present in
the formulation.
Keywords best approximation, duality, Haugazeau, monotone operator, primal-dual algorithm,
splitting algorithm, strong convergence
Mathematics Subject Classifications (2010) Primary 47H05, 41A50; Secondary 65K05,
41A65, 90C25.
∗
Contact author: P. L. Combettes, [email protected], phone:
1
+33 1 4427 6319, fax:
+33 1 4427 7200.
1 Introduction
Let H and G be real Hilbert spaces, let L : H → G be a bounded linear operator, and let f : H →
]−∞, +∞] and g : G → ]−∞, +∞] be proper lower semicontinuous convex functions. Classical
Fenchel-Rockafellar duality [25] concerns the interplay between the optimization problem
minimize f (x) + g(Lx)
(1.1)
x∈H
and its dual
minimize
f ∗ (−L∗ v ∗ ) + g∗ (v ∗ ).
∗
(1.2)
v ∈G
An essential ingredient in the analysis of such dual problems is the associated Kuhn-Tucker set [26]
Z = (x, v ∗ ) ∈ H ⊕ G −L∗ v ∗ ∈ ∂f (x) and Lx ∈ ∂g∗ (v ∗ ) ,
(1.3)
which involves the maximally monotone subdifferential operators ∂f and ∂g∗ . A fruitful generalization of (1.1)–(1.2) is obtained by pairing the inclusion 0 ∈ Ax + L∗ BLx on H with the dual
inclusion 0 ∈ −LA−1 (−L∗ v ∗ ) + B −1 v ∗ on G, where A and B are maximally monotone operators
acting on H and G, respectively. Such operator duality has been studied in [16, 22, 23, 24] and
the first splitting algorithm for solving such composite inclusions was proposed in [9]. The strategy
adopted in that paperwas to use a standard
2-operator splitting method
to construct a point in the
Kuhn-Tucker set Z = (x, v ∗ ) ∈ H ⊕ G −L∗ v ∗ ∈ Ax and Lx ∈ B −1 v ∗ and hence obtain a primaldual solution (see also [7, 12, 14, 15, 28] for variants of this approach). In [1] we investigated a
different strategy based on an idea first proposed in [17] for solving the inclusion 0 ∈ Ax + Bx. In
this framework, at each iteration, one uses points in the graphs of A and B to construct a closed
affine half-space of H ⊕ G containing Z; the primal-dual update is then obtained as the projection
of the current iterate onto it. The resulting Fej´er-monotone algorithm provides only weak convergence to an unspecified Kuhn-Tucker point. In the present paper we propose a strongly convergent
modification of these methods for solving the following best approximation problem.
Problem 1.1 Let H and G be real Hilbert spaces, and set K = H ⊕ G. Let A : H → 2H and
B : G → 2G be maximally monotone operators, and let L : H → G be a bounded linear operator. Let
(x0 , v0∗ ) ∈ K, assume that the inclusion problem
find x ∈ H such that 0 ∈ Ax + L∗ BLx
(1.4)
has at least one solution, and consider the dual problem
find v ∗ ∈ G such that 0 ∈ −LA−1 (−L∗ v ∗ ) + B −1 v ∗ .
(1.5)
The problem is to find the best approximation (x, v ∗ ) to (x0 , v0∗ ) from the associated Kuhn-Tucker
set
Z = (x, v ∗ ) ∈ K −L∗ v ∗ ∈ Ax and Lx ∈ B −1 v ∗ .
(1.6)
The principle of our algorithm goes back to the work of Yves Haugazeau [19] for finding the
projection of a point onto the intersection of closed convex sets by means of projections onto the
2
individual sets. Haugazeau’s method was generalized in several directions and applied to a variety
of problems in nonlinear analysis and optimization in [11]. In [4], it was formulated as an abstract
convergence principle for turning a class of weakly convergent methods into strongly convergent
ones (see also [20] for recent related work). In the area of monotone inclusions,
Haugazeau-like
T
−1
methods were used in [27] for solving x ∈ A−1 0 and in [4] for solving x ∈ m
A
i=1 i 0. They were
also used in splitting method for solving 0 ∈ Ax + Bx as a modification of the forward-backward
splitting algorithm in [13] and [5, Corollary 29.5], and as a modification of the Douglas-Rachford
algorithm in [6] and [29].
The paper is organized as follows. Section 2 is devoted to a version of an abstract Haugazeau
principle. The algorithms for solving Problem 1.1 are presented in Section 3, where their strong
convergence is established. In Section 4, we present an extension to systems of coupled monotone
inclusions and consider applications to the relaxation of inconsistent common zero problems and
to structured multivariate convex minimization problems.
Notation. Our notation is standard and follows [5], where the necessary background on monotone
operators and convex analysis is available. The scalar product of a Hilbert space is denoted by
h· | ·i and the associated norm by k · k. We denote respectively by ⇀ and → weak and strong
convergence, and by Id the identity operator. Let H and G be real Hilbert space. The Hilbert direct
sum of H and G is denoted by H ⊕ G, and the power set of H by 2H . Now let A : H → 2H . Then
ran A is the range A, gra A the graph of A, A−1 the inverse of A, and JA = (Id +A)−1 the resolvent
of A. The projection operator onto a nonempty closed convex subset C of H is denoted by PC
and Γ0 (H) is the class of proper lower semicontinuous convex functions from H to ]−∞, +∞]. Let
f ∈ Γ0 (H). The conjugate of f is Γ0(H) ∋ f ∗ : u∗ 7→ supx∈H (hx | u∗ i − f (x))
and the subdifferential
of f is ∂f : H → 2H : x 7→ u∗ ∈ H (∀y ∈ H) hy − x | u∗ i + f (x) 6 f (y) .
2 An abstract Haugazeau algorithm
In [19, Th´eor`eme 3-2] Haugazeau proposed an ingenious method for projecting a point onto the
intersection of closed convex sets in a Hilbert space using the projections onto the individual sets.
Abstract versions of his method for projecting onto a closed convex set in a real Hilbert space were
devised in [11] and [4]. In this section, we present a formulation of this abstract principle which
is better suited for our purposes.
Let H be a real Hilbert space. Given an ordered triplet (x, y, z) ∈ H3 , we define
H(x, y) = h ∈ H hh − y | x − yi 6 0 .
(2.1)
Moreover, if R = H(x, y) ∩ H(y, z) 6= ∅, we denote by Q(x, y, z) the projection of x onto R. The
principle of the algorithm to project a point x0 ∈ H onto a nonempty closed convex set C ⊂ H
is to use at iteration n the current iterate xn to construct an outer approximation to C of the
form H(x0 , xn ) ∩ H(xn , xn+1/2 ); the update is then computed as the projection of x0 onto it, i.e.,
xn+1 = Q(x0 , xn , xn+1/2 ).
3
Proposition 2.1 Let C be a nonempty closed convex subset of H and let x0 ∈ H. Iterate
for
n = 0, 1, . . .
take xn+1/2 ∈ H such that
C ⊂ H(xn , xn+1/2 )
xn+1 = Q x0 , xn , xn+1/2 .
(2.2)
Then the sequence (xn )n∈N is well defined and the following hold:
(i) (∀n ∈ N) C ⊂ H(x0 , xn ) ∩ H(xn , xn+1/2 ).
P
2
(ii)
n∈N kxn+1 − xn k < +∞.
P
2
(iii)
n∈N kxn+1/2 − xn k < +∞.
(iv) Suppose that, for every x ∈ H and every strictly increasing sequence (kn )n∈N in N, xkn ⇀ x ⇒
x ∈ C. Then xn → PC x0 .
Proof. The proof is similar to those found in [4, Section 3] and [11, Section 3]. First, recall that the
projector onto a nonempty closed convex subset D of H is characterized by [5, Theorem 3.14]
(∀x ∈ H) PD x ∈ D
and D ⊂ H(x, PD x).
(2.3)
(i): Let n ∈ N be such that xn exists. Since by construction C ⊂ H(xn , xn+1/2 ), it is enough
to show that C ⊂ H(x0 , xn ). This inclusion is trivially true for n = 0 since H(x0 , x0 ) = H.
Furthermore, it follows from (2.3) and (2.2) that
C ⊂ H(x0 , xn ) ⇒ C ⊂ H(x0 , xn ) ∩ H(xn , xn+1/2 )
⇒ C ⊂ H x0 , Q(x0 , xn , xn+1/2 )
⇔ C ⊂ H(x0 , xn+1 ),
(2.4)
which establishes the assertion by induction. This also shows that H(x0 , xn ) ∩ H(xn , xn+1/2 ) is a
nonempty closed convex set and therefore that the projection xn+1 of x0 onto it is well defined.
(ii): Let n ∈ N. By construction, xn+1 = Q(x0 , xn , xn+1/2 ) ∈ H(x0 , xn ) ∩ H xn , xn+1/2 .
Consequently, since xn is the projection of x0 onto H(x0 , xn ) and xn+1 ∈ H(x0 , xn ), we have
kx0 − xn k 6 kx0 − xn+1 k. On the other hand, since PC x0 ∈ C ⊂ H(x0 , xn ), we have kx0 − xn k 6
kx0 − PC x0 k. It follows that (kx0 − xk k)k∈N converges and that
lim kx0 − xk k 6 kx0 − PC x0 k.
(2.5)
On the other hand, since xn+1 ∈ H(x0 , xn ), we have
kxn+1 − xn k2 6 kxn+1 − xn k2 + 2hxn+1 − xn | xn − x0 i = kx0 − xn+1 k2 − kx0 − xn k2 . (2.6)
P
P
Hence, nk=1 kxk+1 −xk k2 6 kx0 −xn+1 k2 6 kx0 −PC x0 k2 and, in turn, k∈N kxk+1 −xk k2 < +∞.
(iii): For every n ∈ N, we derive from the inclusion xn+1 ∈ H(xn , xn+1/2 ) that
kxn+1/2 − xn k2 6 kxn+1 − xn+1/2 k2 + kxn − xn+1/2 k2
6 kxn+1 − xn+1/2 k2 + 2hxn+1 − xn+1/2 | xn+1/2 − xn i + kxn − xn+1/2 k2
= kxn+1 − xn k2 .
(2.7)
4
Hence, it follows from (ii) that
P
n∈N kxn+1/2
− xn k2 < +∞.
(iv): Let us note that (2.5) implies that (xn )n∈N is bounded. Now, let x be a weak sequential
cluster point of (xn )n∈N , say xkn ⇀ x. Then, by weak lower semicontinuity of k·k [5, Lemma 2.35]
and (2.5) kx0 − xk 6 lim kx0 − xkn k 6 kx0 − PC x0 k = inf y∈C kx0 − yk. Hence, since x ∈ C,
x = PC x0 is the only weak sequential cluster point of the sequence (xn )n∈N and it follows from [5,
Lemma 2.38] that xn ⇀ PC x0 . In turn (2.5) yields kx0 −PC x0 k 6 lim kx0 −xn k = lim kx0 −xn k 6
kx0 − PC x0 k. Thus, x0 − xn ⇀ x0 − PC x0 and kx0 − xn k → kx0 − PC x0 k. We therefore derive
from [5, Lemma 2.41(i)] that x0 − xn → x0 − PC x0 , i.e., xn → PC x0 .
Remark 2.2 Suppose that, for some n ∈ N, xn ∈ C in (2.2). Then kx0 − PC x0 k 6 kx0 − xn k
and, since we always have kx0 − xn k 6 kx0 − PC x0 k, we conclude that xn = PC x0 and that the
iterations can be stopped.
Algorithm (2.2) can easily be implemented thanks to the following lemma.
Lemma 2.3 Let (x, y, z) ∈ H3 and set R = H(x, y) ∩ H(y, z). Moreover, set χ = hx − y | y − zi,
µ = kx − yk2 , ν = ky − zk2 , and ρ = µν − χ2 . Then exactly one of the following holds:
(i) ρ = 0 and χ < 0, in which case R = ∅.
(ii) [ ρ = 0 and χ > 0 ] or ρ > 0, in which case R 6= ∅ and


if ρ = 0 and χ > 0;
z,
Q(x, y, z) = x + (1 + χ/ν)(z − y),
if ρ > 0 and χν > ρ;


y + (ν/ρ) χ(x − y) + µ(z − y) , if ρ > 0 and χν < ρ.
(2.8)
Proof. See [19, Th´
eor`eme 3-1] for the original proof and [5, Corollary 28.21] for an alternate
derivation.
3 Main result
In this section, we devise a strongly convergent algorithm for solving Problem 1.1 by coupling
Proposition 2.1 with the construction of [1] to determine the half-spaces (H(xn , xn+1/2 ))n∈N . First,
we need a couple of facts.
Proposition 3.1 [9, Proposition 2.8] In the setting of Problem 1.1, Z is a nonempty closed convex
set and, if (x, v ∗ ) ∈ Z, then x solves (1.4) and v ∗ solves (1.5).
Proposition 3.2 [1, Proposition 2.5] In the setting of Problem 1.1, let (an , a∗n )n∈N be a sequence in
gra A, let (bn , b∗n )n∈N be a sequence in gra B, and let (x, v ∗ ) ∈ K. Suppose that an ⇀ x, b∗n ⇀ v ∗ ,
a∗n + L∗ b∗n → 0, and Lan − bn → 0. Then han | a∗n i + hbn | b∗n i → 0 and (x, v ∗ ) ∈ Z.
The next result features our general algorithm for solving Problem 1.1.
5
Theorem 3.3 Consider the setting of Problem 1.1. Let ε ∈ ]0, 1[, let α ∈ ]0, +∞[, and set, for every
(x, v ∗ ) ∈ K,
n
Gα (x, v ∗ ) = (a, b, a∗ , b∗ ) ∈ K × K (a, a∗ ) ∈ gra A, (b, b∗ ) ∈ gra B, and
hx − a | a∗ + L∗ v ∗ i + hLx − b | b∗ − v ∗ i > α ka∗ + L∗ b∗ k2 + kLa − bk2
Iterate
for
 n = 0, 1,∗. . .∗
 (an , bn , an , bn ) ∈ Gα (xn , vn∗ )
 ∗
 sn = a∗n + L∗ b∗n

 tn = bn − Lan

 τn = ks∗ k2 + ktn k2
n

 if τn = 0
  θ =0
n

 if τ > 0
n
  λ ∈ [ε, 1]

n

 θn = λn hxn | s∗n i + htn | vn∗ i − han | a∗n i − hbn | b∗n i /τn

 xn+1/2 = xn − θn s∗n
 ∗
 vn+1/2 = vn∗ − θn tn

 χn = hx0 − xn | xn − xn+1/2 i + hv0∗ − vn∗ | vn∗ − v ∗
n+1/2 i

 µ = kx − x k2 + kv ∗ − v ∗ k2
0
n
 n
n
0
 ν = kx − x
2
∗
∗
2
n
 n
n+1/2 k + kvn − vn+1/2 k

2
 ρn = µ n ν n − χ n

 if ρn = 0 and χn > 0
  xn+1 = xn+1/2

∗
∗
 vn+1
= vn+1/2

 if ρ > 0 and χ ν > ρ
n n
n
 n
 x
n+1 = x0 + (1 + χn /νn )(xn+1/2 − xn )

 v ∗ = v ∗ + (1 + χ /ν )(v ∗
∗

n n
0
n+1
n+1/2 − vn )

 if ρn > 0 and χn νn < ρn
  xn+1 = xn + (νn /ρn ) χn (x0 − xn ) + µn (xn+1/2 − xn )
∗
∗
− vn∗ ) .
= vn∗ + (νn /ρn ) χn (v0∗ − vn∗ ) + µn (vn+1/2
vn+1
o
. (3.1)
(3.2)
Then (3.2) generates infinite sequences (xn )n∈N and (vn∗ )n∈N , and the following hold:
P
∗
− vn∗ k2 < +∞.
− xn k2 < +∞ and n∈N kvn+1
P
P
∗ 2
2
(ii)
n∈N ksn k < +∞ and
n∈N ktn k < +∞.
(i)
P
n∈N kxn+1
(iii) Suppose that xn − an ⇀ 0 and vn∗ − b∗n ⇀ 0. Then xn → x and vn∗ → v ∗ .
Proof. We are going to show that the claims follow from Proposition 2.1 applied in K to the set Z
of (1.6), which is nonempty, closed, and convex by Proposition 3.1. First, let us set
∗
(∀n ∈ N) xn = (xn , vn∗ ) and xn+1/2 = (xn+1/2 , vn+1/2
).
6
(3.3)
We deduce from (3.2) that
(∀(x, v ∗ ) ∈ K)(∀n ∈ N) hx | s∗n i + htn | v ∗ i − han | a∗n i − hbn | b∗n i
= hx | a∗n + L∗ b∗n i + hbn − Lan | v ∗ i − han | a∗n i − hbn | b∗n i
= hx − an | a∗n + L∗ v ∗ i + hLx − bn | b∗n − v ∗ i.
(3.4)
Next, let us show that
(∀n ∈ N) Z ⊂ H xn , xn+1/2 .
(3.5)
To this end, let z = (x, v ∗ ) ∈ Z and let n ∈ N. We must show that hz − xn+1/2 | xn − xn+1/2 i 6 0.
If τn = 0, then xn+1/2 = xn and the inequality is trivially satisfied. Now suppose that τn > 0. Then
(3.4) and (3.1) yield
hxn | s∗n i + htn | vn∗ i − han | a∗n i − hbn | b∗n i
τn
∗
∗
∗
hxn − an | an + L vn i + hLxn − bn | b∗n − vn∗ i
= λn
τn
> εα
θ n = λn
> 0.
(3.6)
On the other hand, it follows from (3.2) and (1.6) that a∗n ∈ Aan and −L∗ v ∗ ∈ Ax. Hence, since A
is monotone, hx − an | a∗n + L∗ v ∗ i 6 0. Similarly, since v ∗ ∈ B(Lx) and b∗n ∈ Bbn , the monotonicity
of B implies that hLx − bn | b∗n − v ∗ i 6 0. Consequently, we derive from (3.2), (3.4), and (3.1) that
hz − xn+1/2 | xn − xn+1/2 i/θn
= hz | xn − xn+1/2 i/θn + hxn+1/2 | xn+1/2 − xn i/θn
∗
= hx | xn − xn+1/2 i/θn + hv ∗ | vn∗ − vn+1/2
i/θn
∗
∗
+ hxn+1/2 | xn+1/2 − xn i/θn + hvn+1/2
| vn+1/2
− vn∗ i/θn
= hx | s∗n i + htn | v ∗ i − hxn | s∗n i − htn | vn∗ i + θn ks∗n k2 + ktn k2
= hx | s∗n i + htn | v ∗ i − hxn | s∗n i − htn | vn∗ i + λn hxn | s∗n i + htn | vn∗ i − han | a∗n i − hbn | b∗n i
= hx | s∗n i + htn | v ∗ i − han | a∗n i − hbn | b∗n i
− (1 − λn ) hxn | s∗n i + htn | vn∗ i − han | a∗n i − hbn | b∗n i
= hx − an | a∗n + L∗ v ∗ i + hLx − bn | b∗n − v ∗ i
− (1 − λn ) hxn − an | a∗n + L∗ vn∗ i + hLxn − bn | b∗n − vn∗ i
6 hx − an | a∗n + L∗ v ∗ i + hLx − bn | b∗n − v ∗ i − α(1 − λn ) ka∗n + L∗ b∗n k2 + kLan − bn k2
6 hx − an | a∗n + L∗ v ∗ i + hLx − bn | b∗n − v ∗ i
6 0.
(3.7)
This verifies (3.5). It therefore follows from (2.8) that (3.2) is an instance of (2.2).
P
P
∗
−vn∗ k2 =
(3.3) and Proposition 2.1(ii) that n∈N kxn+1 −xn k2 + n∈N kvn+1
P (i): It follows from
2
n∈N kxn+1 − xn k < +∞.
(ii): Let n ∈ N. We consider two cases.
7
• τn = 0: Then (3.2) yields ks∗n k2 + ktn k2 = 0 = kxn+1/2 − xn k2 /(αε)2 .
• τn > 0: Then it follows from (3.1) and (3.2) that
ks∗n k2 + ktn k2 = τn
2
hxn − an | a∗n + L∗ vn∗ i + hLxn − bn | b∗n − vn∗ i
6
α2 τn
2
hxn | s∗n i + htn | vn∗ i − han | a∗n i − hbn | b∗n i
=
α2 τn
2
λ2n hxn | s∗n i + htn | vn∗ i − han | a∗n i − hbn | b∗n i
6
α2 ε2 τn
θ 2 τn
= n2 2
α ε
∗
kxn+1/2 − xn k2 + kvn+1/2
− vn∗ k2
=
α2 ε2
kxn+1/2 − xn k2
=
.
α2 ε2
Altogether, it follows from Proposition 2.1(iii) that
P
∗ 2
n∈N ksn k
+
P
2
n∈N ktn k
(3.8)
< +∞.
(iii): Take x ∈ H, v ∗ ∈ G, and a strictly increasing sequence (kn )n∈N in N, such that xkn ⇀ x
and vk∗n ⇀ v ∗ . We derive from (ii) and (3.2) that a∗n + L∗ b∗n → 0 and Lan − bn → 0. Hence, the
assumptions yield
akn ⇀ x,
b∗kn ⇀ v ∗ ,
a∗kn + L∗ b∗kn → 0,
and Lakn − bkn → 0.
(3.9)
On the other hand, (3.1) also asserts that (∀n ∈ N) (an , a∗n ) ∈ gra A and (bn , b∗n ) ∈ gra B. Altogether,
Proposition 3.2 implies that (x, v ∗ ) ∈ Z. In view of Proposition 2.1(iv), the proof is complete.
Remark 3.4 Here are a few observations pertaining to Theorem 3.3.
(i) These results appear to provide the first algorithmic framework for composite inclusions problems that does not require additional assumptions on the constituents of the problem to
achieve strong convergence.
∗
∗
= vn+1/2
, and if
(ii) If the second half of (3.2) is by-passed, i.e., if we set xn+1 = xn+1/2 and vn+1
the relaxation parameter λn is chosen in the range [ε, 2 − ε], one recovers the algorithm of [1,
Corollary 3.3]. However, this algorithm provides only weak convergence to an unspecified
Kuhn-Tucker point, whereas (3.2) guarantees strong convergence to the best Kuhn-Tucker
approximation to (x0 , v0∗ ). This can be viewed as another manifestation of the weak-to-strong
convergence principle investigated in [4] in a different setting (T -class operators).
The following proposition is an application of Theorem 3.3 which describes a concrete implementation of (3.2) with a specific rule for selecting (an , bn , a∗n , b∗n ) ∈ Gα (xn , vn∗ ).
8
Proposition 3.5 Consider the setting of Problem 1.1. Let ε ∈ ]0, 1[ and iterate
for n = 0, 1, . . .

 (γn , µn ) ∈ [ε, 1/ε]2

 an = Jγn A (xn − γn L∗ vn∗ )

 ln = Lxn

 bn = Jµn B (ln + µn vn∗ )

 s∗ = γ −1 (xn − an ) + µ−1 L∗ (ln − bn )
n
n
 n
 tn = bn − Lan

 τ = ks∗ k2 + kt k2
n
 n
n
 if τ = 0
 n
 θ =0

n
 if τ > 0
 n

 λn ∈ [ε, 1]

2
 θn = λn γn−1 kxn − an k2 + µ−1
n kln − bn k /τn

 xn+1/2 = xn − θn s∗n
 ∗
 vn+1/2 = vn∗ − θn tn

 χn = hx0 − xn | xn − xn+1/2 i + hv ∗ − v ∗ | v ∗ − v ∗
n
n
0

n+1/2 i
 µ = kx − x k2 + kv ∗ − v ∗ k2
 n
0
n
n
0

∗
k2
 νn = kxn − xn+1/2 k2 + kvn∗ − vn+1/2

2
 ρn = µ n ν n − χ n

 if ρn = 0 and χn > 0
  xn+1 = xn+1/2

 v∗ = v∗
n+1
n+1/2

 if ρ > 0 and χ ν > ρ
n n
n
 n
 x

n+1 = x0 + (1 + χn /νn )(xn+1/2 − xn )

∗
∗
− vn∗ )
= v0∗ + (1 + χn /νn )(vn+1/2
 vn+1

 if ρn > 0 and χn νn < ρn
  xn+1 = xn + (νn /ρn ) χn (x0 − xn ) + µn (xn+1/2 − xn )
∗
∗
− vn∗ ) .
= vn∗ + (νn /ρn ) χn (v0∗ − vn∗ ) + µn (vn+1/2
vn+1
(3.10)
Then (3.10) generates infinite sequences (xn )n∈N and (vn∗ )n∈N , and the following hold:
P
∗
− vn∗ k2 < +∞.
− xn k2 < +∞ and n∈N kvn+1
P
P
∗ 2
2
(ii)
n∈N ksn k < +∞ and
n∈N ktn k < +∞.
P
P
2
∗
∗ 2
(iii)
n∈N kxn − an k < +∞ and
n∈N kvn − bn k < +∞.
(i)
P
n∈N kxn+1
(iv) xn → x and vn∗ → v ∗ .
Proof. Let us define
α=
and
1+
kLk2
ε
+ 2(1 − ε2 )max 1, kLk2
(∀n ∈ N) a∗n = γn−1 (xn − an ) − L∗ vn∗
(3.11)
∗
and b∗n = µ−1
n (Lxn − bn ) + vn .
9
(3.12)
Then it is shown in [1, proof of Proposition 3.5] that
(∀n ∈ N) (an , bn , a∗n , b∗n ) ∈ Gα (xn , vn∗ )
(3.13)
(∀n ∈ N) kxn − an k2 6 2ε−2 ks∗n k2 + ε−2 kLk2 ktn k2 .
(3.14)
and
We deduce from (3.12) and (3.13) that (3.10) is a special case of (3.2). Consequently, assertions
(i) and (ii) follow from their counterparts in Theorem 3.3. To complete the proof, it remains to
show (iii), which will imply (iv) by virtue of Theorem 3.3(iii). We derive from (3.12) that
2
−2
(∀n ∈ N) kvn∗ − b∗n k2 = µ−2
kLk2 kxn − an k2 + ktn k2 . (3.15)
n kL(xn − an ) + Lan − bn k 6 2ε
Thus, in view of (3.14), (3.15), and (ii), the proof is complete.
Remark 3.6 In (3.10), the identity τn = 0 can be used as a stopping rule. Indeed, τn = 0 ⇔
(a∗n + L∗ b∗n , bn − Lan ) = (0, 0) ⇔ (−L∗ b∗n , Lan ) = (a∗n , bn ) ∈ Aan × B −1 b∗n ⇔ (an , b∗n ) ∈ Z. On
the other hand, it follows from (3.14) and (3.15) that τn = 0 ⇒ (xn , vn∗ ) = (an , b∗n ). Altogether,
Remark 2.2 yields (xn , vn∗ ) = PZ (x0 , v0∗ ) = (x, v ∗ ).
4 Extension to systems of monotone inclusions
As discussed in [1, 2, 3, 8, 10, 12, 18], various problems in applied mathematics can be modeled
by systems of coupled monotone inclusions. In this section, we consider the following setting.
Problem 4.1 Let m and K be strictly positive integers, let (Hi )16i6m and (Gk )16k6K be real Hilbert
spaces, and set K = H1 ⊕ · · · Hm ⊕ G1 ⊕ · · · ⊕ GK . For every i ∈ {1, . . . , m} and k ∈ {1, . . . , K},
let Ai : Hi → 2Hi and Bk : Gk → 2Gk be maximally monotone, let zi ∈ Hi , let rk ∈ Gk , and let
∗ , . . . , v ∗ ) ∈ K, assume
Lki : Hi → Gk be linear and bounded. Let (x0 , v ∗0 ) = (x1,0 , . . . , xm,0 , v1,0
K,0
that the coupled inclusions problem
find x1 ∈ H1 , . . . , xm ∈ Hm such that
(∀i ∈ {1, . . . , m})
zi ∈ Ai xi +
K
X
L∗ki
k=1
Bk
X
m
j=1
Lkj xj − rk
(4.1)
has at least one solution, and consider the dual problem
find v ∗1 ∈ G1 , . . . , v ∗K ∈ GK such that
(∀k ∈ {1, . . . , K})
− rk ∈ −
m
X
i=1
Lki
A−1
i
zi −
K
X
L∗li v ∗l
l=1
∗
∗
(x1 , . . . , xm , v 1 , . . . , v K ) to
+ Bk−1 v ∗k . (4.2)
The problem is to find the best approximation
(x0 , v ∗0 ) from the associated Kuhn-Tucker set
K
X
∗
∗
Z = (x1 , . . . , xm , v1 , . . . , vK ) ∈ K (∀i ∈ {1, . . . , m}) zi −
L∗ki vk∗ ∈ Ai xi and
k=1
(∀k ∈ {1, . . . , K})
10
m
X
i=1
Lki xi − rk ∈ Bk−1 vk∗ . (4.3)
The next result presents a strongly convergent method for solving Problem 4.1. Let us note
that existing methods require stringent additional conditions on the operators to achieve strong
convergence and, in addition, they produce only unspecified points in the Kuhn-Tucker set [2, 12].
Proposition 4.2 Consider the setting of Problem 4.1. Let ε ∈ ]0, 1[ and iterate
for
 n = 0, 1, . . .
 (γn , µn ) ∈ [ε, 1/ε]2

 for i = 1, . . . , m
 j
P

∗
 ai,n = Jγn Ai xi,n + γn zi − K
L∗ki vk,n
k=1

 for k = 1, . . . , K
 
  l = Pm L x
  k,n
i=1 ki i,n
  b =r +J
∗
µn Bk lk,n + µn vk,n − rk
k,n
k

P

tk,n = bk,n − m

i=1 Lki ai,n

i
=
1,
.
.
.
,
m
 for
 j
 s∗ = γ −1 (xi,n − ai,n ) + µ−1 PK L∗ (l − b )
k,n
n
n

i,n
k=1 ki k,n
Pm
PK

∗
2
2
 τn = i=1 ksi,n k + k=1 ktk,n k

 if τn = 0
  θn = 0

 if τn > 0
  λ ∈ [ε, 1]
n

 θ = λ γ −1 Pm kx − a k2 + µ−1 PK kl − b k2 /τ

n
n n
i,n
i,n
n
k,n
n
i=1
k=1 k,n

i
=
1,
.
.
.
,
m
 for
  xi,n+1/2 = xi,n − θn s∗i,n

 for
k = 1, . . . , K
 j
∗
 v∗

k,n+1/2 = vk,n − θn tk,n

PK
P
∗
∗
∗
∗
 χn = m
k=1 hvk,0 − vk,n | vk,n − vk,n+1/2 i
i=1 hxi,0 − xi,n | xi,n − xi,n+1/2 i +

P
P
 µ = m kx − x k2 + K kv ∗ − v ∗ k2
 n
i,0
i,n
k=1
P i=1
PK k,0 ∗ k,n ∗

2+
2
 νn = m
kx
−
x
k
i,n
i,n+1/2
i=1
k=1 kvk,n − vk,n+1/2 k

 ρn = µ n ν n − χ 2
n

 if ρn = 0 and χn > 0
 
  for i = 1, . . . , m
    x
i,n+1 = xi,n+1/2
 
  for k = 1, . . . , K
  j

∗
∗

vk,n+1
= vk,n+1/2


if ρn > 0 and χn νn > ρn
 
 
i = 1, . . . , m
  for
    xi,n+1 = xi,0 + (1 + χn /νn )(xi,n+1/2 − xi,n )
 
  for
j k = 1, . . . , K

∗
∗ + (1 + χ /ν )(v ∗
∗

= vk,0
vk,n+1
n n

k,n+1/2 − vk,n )

 if ρn > 0 and χn νn < ρn
 
  for i = 1, . . . , m
    xi,n+1 = xi,n + (νn /ρn ) χn (xi,0 − xi,n ) + µn (xi,n+1/2 − xi,n )
 
  for k = 1, . . . , K
  j
∗
∗
∗
∗
∗
∗
vk,n+1
= vk,n
+ (νn /ρn ) χn (vk,0
− vk,n
) + µn (vk,n+1/2
− vk,n
) .
11
(4.4)
∗
∗ )
Then (4.4) generates infinite sequences (x1,n )n∈N , . . . , (xm,n )n∈N , (v1,n
n∈N , . . . , (vK,n )n∈N , and the
following hold:
∗
2
n∈N ksi,n k < +∞,
(i) (∀i ∈ {1, . . . , m})
and xi,n → xi .
P
(ii) (∀k ∈ {1, . . . , K})
∗ → v∗ .
and vk,n
k
P
P
2
n∈N ktk,n k < +∞,
2
n∈N kxi,n − ai,n k < +∞,
2
n∈N kxi,n+1 − xi,n k < +∞,
P
∗
∗
2
n∈N kvk,n+1 −vk,n k < +∞,
P
P
∗
∗
2
n∈N kvk,n −bk,n k < +∞,
L
LK
Proof. Let us set H = m
i=1 Hi and G =
k=1 Gk , and let us introduce the operators

m
H

A : H → 2 : (xi )16i6m 7→ ×i=1 (−zi + Ai xi )
(4.5)
B : G → 2G : (yk )16k6K 7→ ×K
k=1 Bk (yk − rk )

Pm

L : H → G : (xi )16i6m 7→
i=1 Lki xi 16k6K .
P
∗
Then L∗ : G → H : (yk )16k6K 7→ ( K
k=1 Lki yk )16i6m and, in this setting, Problem 1.1 becomes Problem 4.1. Next, for every n ∈ N, let us introduce the variables an = (ai,n )16i6m , s∗n = (s∗i,n )16i6m ,
xn = (xi,n )16i6m , xn+1/2 = (xi,n+1/2 )16i6m , bn = (bk,n )16k6K , ln = (lk,n )16k6K , tn = (tk,n )16k6K ,
∗
∗
∗ )
vn∗ = (vk,n
16k6K , and vn+1/2 = (vk,n+1/2 )16k6K . Since [5, Propositions 23.15 and 23.16] assert
that
(∀n ∈ N)(∀(xi )16i6m ∈ H)(∀(yk )16k6K ∈ G) Jγn A (xi )16i6m = Jγn Ai (xi + γn zi ) 16i6m
and Jµn B (yk )16k6K = rk + Jµn Bk (yk − rk ) 16k6K , (4.6)
(3.10) reduces in the present scenario to (4.4). Thus, the results follow from Proposition 3.5.
Example 4.3 Let A, (Bk )16k6K , and (Sk )16k6K be maximally monotone operators acting on a real
Hilbert space H. We revisit a problem discussed in [12, Section 4], namely the relaxation of the
possibly inconsistent inclusion problem
find x ∈ H such that 0 ∈ Ax ∩
to
find x ∈ H such that 0 ∈ Ax +
K
\
Bk x
(4.7)
k=1
K
X
(Bk Sk )x,
k=1
where
Bk Sk = Bk−1 + Sk−1
−1
. (4.8)
We assume that (4.8) has at least one solution and that, for every k ∈ {1, . . . , K}, Sk−1 is at most
single-valued and strictly monotone, with Sk−1 0 = {0}. Hence, (4.8) is a relaxation of (4.7) in
the sense that if the latter happens to have solutions, they coincide with those of the former [12,
Proposition 4.2]. As shown in [12], this framework captures many relaxation schemes, and a point
x1 ∈ H solves (4.8) if and only if (x1 , x2 , . . . , xm ) solves (4.1), where m = K + 1, H1 = H, A1 = A,
z1 = 0, and, for every k ∈ {1, . . . , K},


Hk+1 = H







G
=
H
k
Lk1 = Id

(
(4.9)
and
− Id , if i = k + 1;
Ak+1 = Sk


(∀i ∈ {2, . . . , m}) Lki =


0,
otherwise.
zk+1 = 0




rk = 0
12
Thus (4.4) can be reduced to
for
 n = 0, 1, . . .
 (γn , µn ) ∈ [ε, 1/ε]2

PK ∗  a =J
 1,n
γn A x1,n − γn
k=1 vk,n

 for k = 1, . . . , K
 
∗
  ak+1,n = Jγn Sk xk+1,n + γn vk,n
 
  lk,n = x1,n − xk+1,n
 
∗
  bk,n = Jµn Bk lk,n + µn vk,n
 
  tk,n = bk,n + ak+1,n − a1,n


(b − lk,n )
s∗k+1,n = γn−1 (xk+1,n − ak+1,n ) + µ−1

PK n k,n
 ∗
−1
−1
 s1,n = γn (x1,n − a1,n ) + µn
k=1 (lk,n − bk,n )
PK
P

2
2
∗
 τn = K+1
k=1 ktk,n k
k=1 ksk,n k +

 if τn = 0
  θn = 0

 if τn > 0
 
λn ∈ [ε, 1]

P
PK

2
−1
2
θn = λn γn−1 K+1

k=1 kxk,n − ak,n k + µn
k=1 klk,n − bk,n k /τn

 x1,n+1/2 = x1,n − θn s∗1,n

k = 1, . . . , K
 for
 $

xk+1,n+1/2 = xk+1,n − θn s∗k+1,n

∗
∗ −θ t

vk,n+1/2
= vk,n
n k,n

P
PK

∗
∗
∗
∗
 χn = K+1
k=1 hxk,0 − xk,n | xk,n − xk,n+1/2 i +
k=1 hvk,0 − vk,n | vk,n − vk,n+1/2 i

P
P
 µ = K+1 kx − x k2 + K kv ∗ − v ∗ k2
k,0
k,n
 n P k=1
k=1
P k,0 ∗ k,n ∗

K+1
2
 νn = k=1 kxk,n − xk,n+1/2 k2 + K
k=1 kvk,n − vk,n+1/2 k

2
 ρn = µ n ν n − χ n

 if ρn = 0 and χn > 0
 
  x1,n+1 = x1,n+1/2
 
  for k = 1, . . . , K
   
xk+1,n+1 = xk+1,n+1/2


∗
∗
vk,n+1
= vk,n+1/2


 if ρn > 0 and χn νn > ρn
 
  x1,n+1 = x1,0 + (1 + χn /νn )(x1,n+1/2 − x1,n )
 
  for k = 1, . . . , K
   
xk+1,n+1 = xk+1,0 + (1 + χn /νn )(xk+1,n+1/2 − xk+1,n )

∗
∗ + (1 + χ /ν )(v ∗
∗

= vk,0
vk,n+1
n n
k,n+1/2 − vk,n )

 if ρ > 0 and χ ν < ρ
n n
n
  n
  x
  1,n+1 = x1,n + (νn /ρn ) χn (x1,0 − x1,n ) + µn (x1,n+1/2 − x1,n )
 
k = 1, . . . , K
  for
  xk+1,n+1 = xk+1,n + (νn /ρn ) χn (xk+1,0 − xk+1,n ) + µn (xk+1,n+1/2
− xk+1,n )

∗
∗ + (ν /ρ ) χ (v ∗ − v ∗ ) + µ (v ∗
∗
= vk,n
vk,n+1
n k,n+1/2 − vk,n ) ,
n n
n k,0
k,n
(4.10)
and it follows from Proposition 4.2 that (x1,n )n∈N converges strongly to a solution x1 to the relaxed problem (4.8). Let us note that the algorithm proposed in [12, Proposition 4.2] to solve
(4.8) requires that A be uniformly monotone at x1 to guarantee strong convergence, whereas this
assumption is not needed here. In addition, the scaling parameters used in the resolvents of the
13
monotone operators in [12, Proposition 4.2] must
√ be identical at each iteration and bounded by a
fixed constant: (∀n ∈ N) γn = µn ∈ [ε, (1 − ε)/ K + 1]. By contrast, the parameters µn and γn
in (4.10) may differ and they can be arbitrarily large since ε can be arbitrarily small, which could
have some beneficial impact in terms of speed of convergence.
As a second illustration of Proposition 4.2, we consider the following multivariate minimization
problem.
Problem 4.4 Let m and K be strictly positive integers, let (Hi )16i6m and (Gk )16k6K be real Hilbert
spaces, and set K = H1 ⊕ · · · Hm ⊕ G1 ⊕ · · · ⊕ GK . For every i ∈ {1, . . . , m} and k ∈ {1, . . . , K}, let
fi ∈ Γ0 (Hi ) and gk ∈ Γ0 (Gk ), let zi ∈ Hi , let rk ∈ Gk , and let Lki : Hi → Gk be linear and bounded.
∗ , . . . , v ∗ ) ∈ K, assume that the problem
Let (x0 , v ∗0 ) = (x1,0 , . . . , xm,0 , v1,0
K,0
minimize
x1 ∈H1 ,..., xm ∈Hm
m
X
i=1
fi (xi ) − hxi | zi i +
K
X
k=1
gk
X
m
i=1
Lki xi − rk
(4.11)
has at least one solution, and consider the dual problem
minimize
∗
∗
v1 ∈G1 ,..., vK ∈GK
m
X
i=1
fi∗
zi −
K
X
k=1
L∗ki vk∗
+
K
X
k=1
gk∗ (vk∗ ) + hvk∗ | rk i .
(4.12)
The problem is to find the best approximation (x1 , . . . , xm , v ∗1 , . . . , v ∗K ) to (x0 , v ∗0 ) from the associated Kuhn-Tucker set
K
X
∗
∗
Z = (x1 , . . . , xm , v1 , . . . , vK ) ∈ K (∀i ∈ {1, . . . , m}) zi −
L∗ki vk∗ ∈ ∂fi (xi ) and
(∀k ∈ {1, . . . , K})
k=1
m
X
i=1
Lki xi − rk ∈
∂gk∗ (vk∗ )
. (4.13)
The following corollary provides a strongly convergent method to solve Problem 4.4. Recall
that the Moreau proximity operator [21] of a function ϕ ∈ Γ0 (H) is proxϕ = J∂ϕ , i.e., the operator
which maps every point x ∈ H to the unique minimizer of the function y 7→ ϕ(y) + kx − yk2 /2.
Corollary 4.5 Consider the setting of Problem 4.4. Suppose that
(∀i ∈ {1, . . . , m})
X
m
K
X
Lkj · −rk
,
L∗ki ◦ ∂gk ◦
zi ∈ ran ∂fi +
(4.14)
j=1
k=1
let ε ∈ ]0, 1[, and execute (4.4), where Jγn Ai is replaced by proxγn fi and Jµn Bk is replaced by proxµn gk .
Then the conclusions of Proposition 4.2 hold true.
Proof. Let us define (∀i ∈ {1, . . . , m}) Ai = ∂fi and (∀k ∈ {1, . . . , K}) Bk = ∂gk . Then, as
shown in the proof of [12, Proposition 5.4], (4.14) implies that Problem 4.1 assumes the form of
Problem 4.4. Hence, applying Proposition 4.2 in this setting yields the claim.
Acknowledgement. This work was funded by the Deanship of Scientific Research (DSR), King
Abdulaziz University, under grant number 4-130/1433 HiCi.
14
References
[1] A. Alotaibi, P. L. Combettes, and N. Shahzad, Solving coupled composite monotone inclusions by successive Fej´er approximations of their Kuhn-Tucker set, submitted.
http://arxiv.org/abs/1312.6696
[2] H. Attouch, L. M. Brice˜
no-Arias, and P. L. Combettes, A parallel splitting method for coupled
monotone inclusions, SIAM J. Control Optim., vol. 48, pp. 3246–3270, 2010.
[3] H. Attouch, A. Cabot, P. Frankel, and J. Peypouquet, Alternating proximal algorithms for
linearly constrained variational inequalities: application to domain decomposition for PDE’s,
Nonlinear Anal., vol. 74, pp. 7455–7473, 2011.
[4] H. H. Bauschke and P. L. Combettes, A weak-to-strong convergence principle for Fej´ermonotone methods in Hilbert spaces, Math. Oper. Res., vol. 26, pp. 248–264, 2001.
[5] H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert
Spaces. Springer, New York, 2011.
[6] H. H. Bauschke, P. L. Combettes, and D. R. Luke, A strongly convergent reflection method for
finding the projection onto the intersection of two closed convex sets in a Hilbert space, J.
Approx. Theory, vol. 141, pp. 63–69, 2006.
[7] R. I. Bot¸, E. R. Csetnek, and A. Heinrich, A primal-dual splitting algorithm for finding zeros
of sums of maximal monotone operators, SIAM J. Optim., vol. 23, pp. 2011–2036, 2013.
[8] R. I. Bot¸, E. R. Csetnek, and E. Nagy, Solving systems of monotone inclusions via primal-dual
splitting techniques, Taiwanese J. Math., to appear.
[9] L. M. Brice˜
no-Arias and P. L. Combettes, A monotone+skew splitting model for composite
monotone inclusions in duality, SIAM J. Optim., vol. 21, pp. 1230–1250, 2011.
[10] L. M. Brice˜
no-Arias and P. L. Combettes, Monotone operator methods for Nash equilibria in non-potential games, in Computational and Analytical Mathematics, (D. Bailey, H. H.
Bauschke, P. Borwein, F. Garvan, M. Th´era, J. Vanderwerff, and H. Wolkowicz, eds.) pp.
143–159. Springer, New York, 2013.
[11] P. L. Combettes, Strong convergence of block-iterative outer approximation methods for convex optimization, SIAM J. Control Optim., vol. 38, pp. 538–565, 2000.
[12] P. L. Combettes, Systems of structured monotone inclusions: Duality, algorithms, and applications, SIAM J. Optim., vol. 23, pp. 2420–2447, 2013.
[13] P. L. Combettes and S. A. Hirstoaga, Equilibrium programming in Hilbert spaces, J. Nonlinear
Convex Anal., vol. 6, pp. 117–136, 2005.
[14] P. L. Combettes and J.-C. Pesquet, Primal-dual splitting algorithm for solving inclusions with
mixtures of composite, Lipschitzian, and parallel-sum type monotone operators, Set-Valued
Var. Anal., vol. 20, pp. 307–330, 2012.
[15] P. L. Combettes and B. C. V˜
u, Variable metric forward-backward splitting with applications to
monotone inclusions in duality, Optimization, published on line 2012-12-13.
http://www.tandfonline.com/doi/full/10.1080/02331934.2012.733883.
[16] J. Eckstein and M. C. Ferris, Smooth methods of multipliers for complementarity problems,
Math. Programming, vol. 86, pp. 65–90, 1999.
15
[17] J. Eckstein and B. F. Svaiter, A family of projective splitting methods for the sum of two
maximal monotone operators, Math. Programming, vol. 111, pp. 173–199, 2008.
[18] P. Frankel and J. Peypouquet, Lagrangian-penalization algorithm for constrained optimization
and variational inequalities, Set-Valued Var. Anal., vol. 20, pp. 169–185, 2012.
[19] Y. Haugazeau, Sur les In´equations Variationnelles et la Minimisation de Fonctionnelles Convexes.
Th`ese, Universit´
e de Paris, Paris, France, 1968.
[20] M. Marques Alves and J. G. Melo, Strong convergence in Hilbert spaces via Γ-duality, J. Optim.
Theory Appl., to appear, DOI 10.1007/s10957-012-0253-9.
[21] J.-J. Moreau, Fonctions convexes duales et points proximaux dans un espace hilbertien, C. R.
Acad. Sci. Paris S´er. A, vol. 255, pp. 2897–2899, 1962.
[22] T. Pennanen, Dualization of generalized equations of maximal monotone type, SIAM J. Optim., vol. 10, pp. 809–835, 2000.
[23] S. M. Robinson, Composition duality and maximal monotonicity, Math. Programming, vol. 85,
pp. 1–13, 1999.
[24] S. M. Robinson, Generalized duality in variational analysis, in: N. Hadjisavvas and P. M.
Pardalos (eds.), Advances in Convex Analysis and Global Optimization, pp. 205–219. Dordrecht, The Netherlands, Kluwer, 2001.
[25] R. T. Rockafellar, Duality and stability in extremum problems involving convex functions,
Pacific J. Math., vol. 21, pp. 167–187, 1967.
[26] R. T. Rockafellar, Conjugate Duality and Optimization. SIAM, Philadelphia, PA, 1974.
[27] M. V. Solodov and B. F. Svaiter, Forcing strong convergence of proximal point iterations in a
Hilbert space, Math. Programming vol. 87, pp. 189–202, 2000.
[28] B. C. V˜
u, A splitting algorithm for dual monotone inclusions involving cocoercive operators,
Adv. Comput. Math., vol. 38, pp. 667–681, 2013.
[29] H. Zhang and L. Cheng, Projective splitting methods for sums of maximal monotone operators
with applications, J. Math. Anal. Appl., vol. 406, pp. 323–334, 2013.
16

Download Report