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
© Copyright 2024 ExpyDoc