Iterative methods for approximating fixed points of Bregman nonexpansive operators

Iterative Methods for Approximating Fixed Points of Bregman Nonexpansive Operators Victoria Mart´ın-M´arquez∗ , Simeon Reich†and Shoham Sabach‡ July 24, 2011 Abstract Diverse notions of nonexpansive type operators have been extended to the more general framework of Bregman distances in reflexive Banach spaces. We study these classes of operators, mainly with respect to the existence and approximation of their (asymptotic) fixed points. In particular, the asymptotic behavior of Picard and Mann type iterations is discussed for quasi-Bregman nonexpansive operators. We also present parallel algorithms for approximating common fixed points of a finite family of Bregman strongly nonexpansive operators by means of a block operator which preserves the Bregman strong nonexpansivity. All the results hold, in particular, for the smaller class of Bregman firmly nonexpansive operators, a class which contains the generalized resolvents of monotone mappings with respect to the Bregman distance. AMS 2010 Subject Classification: 37L65, 47H09, 47J25, 90C25. Key words and phrases. Banach space, Bregman distance, Bregman firmly nonexpansive operator, Bregman strongly nonexpansive operator, Bregman projection, fixed point, iterative algorithm, Legendre function, totally convex function. ∗Departamento de An´alisis Matem´atico, Universidad de Sevilla, Apdo. 1160, 41080 Sevilla, Spain. Email: [email protected]. †Department of Mathematics, The Technion – Israel Institute of Technology, 32000 Haifa, Israel. Email: [email protected]. ‡Department of Mathematics, The Technion – Israel Institute of Technology, 32000 Haifa, Israel. Email: [email protected]. 1 1 Introduction It is well known that many nonlinear problems can be reduced to the search for fixed points of nonlinear operators. See, for example, [19,25,31] and the references therein. Iterative methods are often used for finding and approximating such fixed points (see [5,17] and their references). Let Kbe a nonempty, closed and convex subset of a Banach space Xand let T:K→Kbe an operator. The most well-known method for solving the fixed point equation Tx =xis perhaps the Picard successive iterations method when Tis a strict contraction, that is, kTx −Tyk ≤ ckx−yk for some 0 ≤c < 1 and all x, y ∈K. Picard’s method generates a sequence {xn}n∈Nsuccessively by xn+1 =Txn(1) for each n≥0, with x0chosen arbitrarily in K. This sequence then converges in norm to the unique fixed point of T. However, if Tis not a strict contraction (for instance, even if Tis nonexpansive with a unique fixed point), then Picard’s successive iterations method fails, in general, to converge. To see this, it suffices, for example, to take for Ta rotation of the unit disc in the plane about the origin of coordinates. Krasnosel’ski [24], however, has shown that in this example, one can obtain a convergent sequence of successive approximations if instead of Tone takes the auxiliary nonexpansive operator (1/2) (I+T), where Idenotes the identity operator of X, that is, if the sequence of successive approximations is defined, for arbitrary x0∈K, by xn+1 =1 2(I+T)xn(2) for each n≥0. It is easy to check that the operators Tand (1/2) (I+T) have the same fixed point sets, so that the limit of a convergent sequence defined by (2) is necessarily a fixed point of T. A more general iterative scheme is the following one: xn+1 =αnxn+ (1 −αn)Txn(3) where {αn}n∈N⊂(0,1) is a sequence satisfying appropriate conditions. The sequence {xn}n∈N, generated by (3), is referred to as the Mann sequence in light of [26]. In 2 an infinite-dimensional Hilbert space, the Mann iterative scheme only yields weak convergence in general (see [4,20]). Our first purpose in this paper is to study (modifications of) these two methods in reflexive Banach spaces. We are also interested in finding variants of these methods for approximating common fixed points of finitely many operators. A commonly used approach to tackling this problem arose in the following way. The problem of finding a point in the intersection of a finite number of closed and convex subsets {Ki}N i=1 of a Banach space is a frequently appearing problem in diverse areas of mathematical and physical sciences. This problem is commonly referred to as the convex feasibility problem (CFP). A classical method for solving this problem is the cyclic projection one. In 1965 Bregman [7, Theorem 1] showed that in a Hilbert space H, for every initial point x0∈H, the sequence {xn}n∈N, generated by the cyclic projection algorithm xn+1 =Pn(mod N)+1xn,(4) where Pidenotes the metric projection onto Kiand the mod Nfunction takes values in {0, . . . , N −1}, converges weakly to a point in K:= TN i=1 Ki6=∅. In order to obtain a similar result in a general Banach space X, Bregman [8] introduced a distance-like function which later was given the name Bregman distance (see (9)) by Censor and Lent [15]. Bregman proved that if in (4) the metric projection is replaced with the Bregman projection (where the norm is replaced with the Bregman distance) then the cluster points of {xn}n∈Nare in K(see [8, Equation (1.2) and Theorem 1]). When a parallel computer is available, it may be more convenient to use another method, called the parallel scheme, for constructing an approximating sequence {xn}n∈N. To this end, at the n-th iteration a set of Npositive real numbers {wi n}N i=1 (the weights) with PN i=1 wi n= 1 is chosen, and, analogously to the sequential scheme, the new point xn+1 is created by computing a convex combination of all the projections, namely, xn+1 = N X i=1 wi nPixn.(5) Over the years, the sequential and parallel algorithmic schemes have been extended to more flexible block-iterative methods in which only a block {Ki}i∈Jof the sets is activated at the n-th iteration, where Jis a subset of {1, . . . , N}. The block-iterative methods evolved further to include the so-called relaxation methods for solving the convex feasibility problem, which go back to Kaczmarz [22] and Cimmino [18]. These methods are of special interest because of their relatively easy implementation and 3 computational efficiency in solving extremely large and sparse problems. Contributions to the study of relaxation methods are surveyed in [14]. Aharoni and Censor [1] discuss a block iterative projection method which incorporates as special cases many of the earlier relaxation techniques. Butnariu and Censor [10] studied the following iterative procedure in a Hilbert space H: xn+1 = N X i=1 wi n(αixn+ (1 −αi)Pixn),(6) where x0∈H,{wi n}N i=1 ⊂[0,1] (n∈N) such that PN i=1 wi n= 1 (n∈N) and {αi}N i=1 ⊂(−1,1). They proved that {xn}n∈Nconverged strongly to an element of K. Let Kbe a nonempty, closed and convex subset of a Hilbert space H. An operator T:K→Kis called nonexpansive (or 1-Lipschitz) if kTx −Tyk≤kx−yk for all x, y ∈K. It turns out that nonexpansive fixed point theory can be applied to the solution of a variety of problems such as finding zeroes of monotone operators and solutions to certain evolution equations, and to solving convex feasibility (CFP), variational inequality (VIP) and equilibrium problems (EP). Kikkawa and Takahashi [23] have recently applied method (6) to the problem of finding common fixed points of a finite family of nonexpansive mappings in Banach spaces. More precisely, they studied the algorithm xn+1 = N X i=1 wi nαi nxn+1−αi nTixn,(7) where x0∈X,{αi n}N i=1 and {wi n}N i=1 are sequences in [0,1] (n∈N) such that PN i=1 wi n= 1, (n∈N) and {Ti}N i=1 is a finite family of nonexpansive operators from Kinto itself. They prove that under certain conditions on the Banach space Xand the sequences {αi n}N i=1 and {wi n}N i=1, the sequence {xn}n∈Nconverges weakly to an element of F:= TN i=1 Fix (Ti), where Fix (T) stands for the fixed point set of the operator T. In the present paper we study a generalization of Algorithm (7) in the more general framework of Bregman distances. In this connection we introduce the block operator corresponding to a finite family of Bregman operators of nonexpansive type and prove several results concerning the relations between the common fixed points 4 of the family and the block operator. In order to approximate fixed points of such operators, we use two well-known iterative methods, namely, the Picard and Mann iterations. For both methods we prove diverse results in several scenarios. Our paper is organized in the following way. We start (see Section 2) with basic definitions, results and remarks concerning our main objects of studying, for example, Bregman distances, totally convex functions and Bregman nonexpansive type operators. In the following part (see Section 3) we prove several auxiliary results which are essential in our later analysis. We show, in particular, that any Bregman strongly nonexpansive operator is asymptotically regular (see Proposition 11). The third and the fourth sections are devoted to the analysis of Picard and Mann iterations, respectively. In these two sections we prove convergence results for Bregman nonexpansive operators. In the last, but not least, section (Section 6) we introduce the block operator and prove several results concerning approximating fixed points of such operators. 2 Preliminaries Let Xdenote a real reflexive Banach space with norm k·k and let X∗stand for the (topological) dual of Xequipped with the induced norm k·k∗. We denote the value of the functional ξ∈X∗at x∈Xby hξ, xi. Given {xn}n∈Nand x∈X, the strong convergence (weak convergence) of the sequence {xn}n∈Nto xis denoted by xn→x (xn* x). Let f:X→(−∞,+∞] be a function. The domain of fis defined to be dom f:= {x∈X:f(x)<+∞} . When dom f6=∅we say that fis proper. We denote by int dom fthe interior of the domain of f. The Fenchel conjugate of fis the function f∗:X∗→(−∞,+∞] defined by f∗(ξ) = sup {hξ, xi − f(x) : x∈X}. Let x∈int dom f. For any y∈X, we define the right-hand derivative of fat x by f◦(x, y) := lim t→0+ f(x+ty)−f(x) t.(8) If the limit as t→0 in (8) exists for any y, then the function fis said to be Gˆateaux differentiable at x. In this case, the gradient of fat xis the function ∇f(x) : X→(−∞,+∞] defined by h∇f(x), yi=f◦(x, y) for any y∈X. The function f 5 is called Gˆateaux differentiable if it is Gˆateaux differentiable at any x∈int dom f. Throughout this paper, the function f:X→(−∞,+∞] is a proper, convex and lower semicontinuous function which is also Gˆateaux differentiable on int dom f. Definition 1 (Legendre function).The function fis called Legendre if it satisfies the following two conditions: (L1) the interior of the domain of f, int dom f, is nonempty, fis Gˆateaux differentiable and dom ∇f= int dom f; (L2) the interior of the domain of f∗, int dom f∗, is nonempty, f∗is Gˆateaux differentiable and dom ∇f∗= int dom f∗. Since Xis reflexive, we always have ∇f= (∇f∗)−1(see [6, p. 83]). This fact, when combined with conditions (L1) and (L2), implies the following equalities: ran ∇f= dom ∇f∗= int dom f∗ and ran ∇f∗= dom ∇f= int dom f. Conditions (L1) and (L2), in conjunction with [3, Theorem 5.4, p. 634], imply that the functions fand f∗are strictly convex on the interior of their respective domains. Definition 2 (Bregman distance).The bifunction Df: dom f×int dom f→[0,+∞) given by Df(y, x) := f(y)−f(x)− h∇f(x), y −xi(9) is called the Bregman distance with respect to f(cf. [15]). With the function fwe associate the bifunction Wf: dom f∗×dom f→[0,+∞) defined by Wf(ξ, x) := f(x)− hξ, xi+f∗(ξ).(10) Proposition 1 (Properties of Wf).Let fbe a Legendre function. Then the following statements hold: (i) The function Wf(·, x)is convex for any x∈dom f. (ii) Wf(∇f(x), y) = Df(y, x)for any x∈int dom fand y∈dom f. 6 (iii) For any ξ, η ∈dom f∗and x∈dom f, we have Wf(ξ, x) + hη, (∇f∗) (ξ)−xi ≤ Wf(ξ+η, x). Proof. (i) This is clear since f∗is convex. (ii) Let x∈int dom fand let y∈dom f. It is known that f(x) + f∗(∇f(x)) = h∇f(x), xi. Therefore Wf(∇f(x), y) = f(y)− h∇f(x), yi+f∗(∇f(x)) =f(y)− h∇f(x), yi+ [h∇f(x), xi − f(x)] =f(y)−f(x)− h∇f(x), y −xi =Df(y, x). (iii) Let x∈dom fbe given. Define the function g:X∗→(−∞,+∞] by g(ξ) = Wf(ξ, x). Then ∇g(ξ) = ∇(f∗− h·, xi) (ξ) = (∇f∗) (ξ)−x. Hence g(ξ+η)−g(ξ)≥ hη, (∇f∗) (ξ)−xi, that is, Wf(ξ, x) + hη, (∇f∗) (ξ)−xi ≤ Wf(ξ+η, x) for all ξ, η ∈dom f∗. We now recall the definition of a totally convex function which was introduced in [11,12]. Definition 3 (Total convexity).The function fis called totally convex at a point x∈int dom fif its modulus of total convexity at x,υf(x, ·) : [0,+∞)→[0,+∞], defined by υf(x, t) := inf {Df(y, x) : y∈dom f, ky−xk=t}, is positive whenever t > 0. The function fis called totally convex when it is totally convex at every point of int dom f. 7 Definition 4 (Total convexity on bounded subsets).The function fis called totally convex on bounded sets if, for any nonempty bounded set E⊂X, the modulus of total convexity of fon E,υf(E, t), is positive for any t > 0, where υf(E, ·) : [0,+∞)→ [0,+∞] is defined by υf(E, t) := inf {υf(x, t) : x∈E∩int dom f}. Recall that, according to Censor and Lent [15], the Bregman projection with respect to fof a point x∈Xonto the closed convex set Kis the (necessarily unique) minimizer over Kof the functional Df(·, x) : X→[0,+∞]; i.e., projf K(x) := arg min {Df(y, x) : y∈K}. The following characterization was proved in [13, Corollary 4.4, p. 23]. Proposition 2 (Characterization of the Bregman projection).Let f:X→(−∞,+∞] be a Gˆateaux differentiable and totally convex function. Let x∈int dom fand let K⊂int dom fbe a nonempty, closed and convex set. If ˆx∈K, then the following statements are equivalent: (i) the vector ˆxis the Bregman projection of xonto K,projf K(x); (ii) the vector ˆxis the unique solution of the variational inequality h∇f(x)− ∇f(z), z −yi ≥ 0,∀y∈K; (11) (iii) the vector ˆxis the unique solution of the inequality Df(y, z) + Df(z, x)≤Df(y, x),∀y∈K. (12) Let K⊂int dom fbe a nonempty set. The fixed point set of an operator T: K→int dom fis the set {x∈K:Tx =x}and is denoted by Fix (T). A point pin the closure of Kis said to be an asymptotic fixed point of T(cf. [16,28]) if Kcontains a sequence {xn}n∈Nwhich converges weakly to psuch that the strong limn→∞ (xn−Txn) = 0. The set of asymptotic fixed points of Twill be denoted by c Fix (T). We next list significant types of nonexpansivity with respect to the Bregman distance. Definition 5 (Bregman nonexpansivity).Let S⊂dom fbe a nonempty subset. The operator T:K→int dom fis said to be: 8 (i) Bregman nonexpansive (BNE) if Df(Tx, Ty)≤Df(x, y),∀x, y ∈K; (13) (ii) quasi-Bregman nonexpansive (QBNE) with respect to Sif Df(p, Tx)≤Df(p, x),∀x∈K, p ∈S; (14) (iii) Bregman firmly nonexpansive (BFNE) if h∇f(Tx)− ∇f(Ty), Tx −Tyi ≤ h∇f(x)− ∇f(y), Tx −Tyi(15) for any x, y ∈K, or equivalently, Df(Tx, Ty) + Df(Ty, Tx) + Df(Tx, x) + Df(Ty, y) ≤Df(Tx, y) + Df(Ty, x) ; (16) (iv) quasi-Bregman firmly nonexpansive (QBFNE) with respect to Sif 0≤ h∇f(x)− ∇f(Tx), Tx −pi ∀ x∈K, p ∈S, (17) or equivalently, Df(p, Tx) + Df(Tx, x)≤Df(p, x) ; (18) (v) Bregman strongly nonexpansive (BSNE) with respect to Sif Df(p, Tx)≤Df(p, x)∀x∈K, p ∈S, (19) and if whenever {xn}n∈N⊂Kis bounded, p∈S, and lim n→+∞(Df(p, xn)−Df(p, Txn)) = 0,(20) it follows that lim n→+∞Df(Txn, xn) = 0.(21) Remark 1 (Types of quasi-Bregman nonexpansivity). (i) An operator which satisfies (14) (or (18)) with respect to S:= Fix (T) is called weakly QBNE (or weakly QBFNE). 9 Since {Tnx}n∈Nis bounded, we now obtain from Proposition 7that lim n→∞ Tn+1x−Tnx= 0. In other words, Tis asymptotically regular. The proof when Tis weakly BSNE is identical when we take u∈Fix (T). Remark 6. From the proof of Proposition 11 we see that Proposition 6can be improved for strongly BSNE operators since the result remains true if the assumption Fix (T)6=∅is replaced by the assumption c Fix (T)6=∅.♦ 4 Picard Iterations for Bregman Nonexpansive Operators The main result in this section is the following one. Theorem 1 (Picard Iteration).Let f:X→(−∞,+∞]be a Legendre function such that ∇f∗is bounded on bounded subsets of int dom f∗. Let Kbe a nonempty, closed and convex subset of int dom fand let T:K→Kbe a strongly QBNE operator. Then the following assertions hold: (i) if c Fix (T)is nonempty, then {Tnx}n∈Nis bounded for each x∈K; (ii) if, furthermore, Tis asymptotically regular, then, for each x∈K, any weak subsequential limit of {Tnx}n∈Nbelongs to c Fix (T); (iii) if, furthermore, ∇fis weakly sequentially continuous, then {Tnx}n∈Nconverges weakly to an element in c Fix (T)for each x∈K. Proof. (i) See Proposition 6and Remark 6. (ii) Since {Tnx}n∈Nis bounded (by point (i)), there is a subsequence {Tnkx}k∈N which converges weakly to some u. Define xn=Tnxfor any n∈N. Since Tis asymptotically regular, it follows from (33) that xn−Txn→0. Therefore we have xnk* u and xnk−Txnk→0, which means that u∈c Fix (T). (iii) From point (ii) and since Tis strongly QBNE, we already know that the limit limn→∞ Df(u, Tnx) exists for any weak limit uof the sequence {Tnx}n∈N. The result now follows immediately from Proposition 9. 16 Corollary 1. Let f:X→(−∞,+∞]be a Legendre function which is totally convex on bounded subsets of X. Suppose that ∇fis weakly sequentially continuous and ∇f∗is bounded on bounded subsets of int dom f∗. Let Kbe a nonempty, closed and convex subset of int dom f. Let T:K→Kbe a BSNE operator with respect to Fix (T) = c Fix (T)6=∅. Then {Tnx}n∈Nconverges weakly to an element in Fix (T) for each x∈K. Proof. The result follows immediately from Theorem 1and Proposition 11. Remark 7. If Fix (T)6=c Fix (T), but c Fix (T)6=∅, then we only know that, for a strongly BSNE operator T,{Tnx}n∈Nconverges weakly to an element in c Fix (T) for each x∈K. This result was previously proved in [28, Lemma 4, p. 315] under somewhat different assumptions. ♦ Remark 8. Let f:X→Rbe a uniformly Fr´echet differentiable function which is bounded on bounded subsets of X. From Proposition 5and Corollary 1we get that Theorem 1holds for BFNE operators. It is well known that in Hilbert spaces, Picard iterations of firmly nonexpansive operators converge weakly to a fixed point of the operator (see, for instance, [21]). ♦ Remark 9 (Common fixed point - Composition case).Let f:X→(−∞,+∞] be a Legendre function which is bounded, uniformly Fr´echet differentiable, and totally convex on bounded subsets of X. Suppose that ∇fis weakly sequentially continuous and ∇f∗is bounded on bounded subsets of int dom f∗. Let Kbe a nonempty, closed and convex subset of int dom f. Let {Ti: 1 ≤i≤N}be NBSNE operators with respect to c Fix (Ti) = Fix (Ti)6=∅ for each 1 ≤i≤Nand let T=TNTN−1· · · T1. From Proposition 4and Remark 4 we obtain that if T{Fix (Ti):1≤i≤N} 6=∅, then Tis also strongly BSNE with respect to c Fix (T) = Fix (T) = T{Fix (Ti) : 1 ≤i≤N}. From Theorem 1we now get that {Tnx}n∈Nconverges weakly to a common fixed point of the family of strongly BSNE operators. Similarly, if we just assume that each Tiis strongly BSNE, 1 ≤i≤N, with c Fix (Ti)6=∅, then we get weak convergence of the sequence {Tnx}n∈Nto a common asymptotic fixed point. ♦ 5 Mann Iterations for Bregman Nonexpansive Operators In the following theorem we study a different iterative method, which is defined by using convex combinations with respect to the convex function f, a concept which 17 was first introduced in [16]. Theorem 2 (Mann Iteration).Let T:X→Xbe a strongly BSNE operator with c Fix (T)6=∅. Let f:X→Rbe a Legendre function which is totally convex on bounded subsets of X. Suppose that ∇fis weakly sequentially continuous and ∇f∗ is bounded on bounded subsets of int dom f∗. Let {xn}n∈Nbe the sequence generated by the iterative scheme xn+1 =∇f∗(αn∇f(xn) + (1 −αn)∇f(Txn)) ,(34) where {αn}n∈N⊂[0,1] satisfies lim supn→∞ αn<1. Then, for each x0∈X, the sequence {xn}n∈Nconverges weakly to a point in c Fix (T). Proof. We divide the proof into 3 steps. Step 1. The sequence {xn}n∈Nis bounded. Let p∈c Fix (T). From Proposition 1(i), (ii) and (19) we have for all n∈N, Df(p, xn+1) = Df(p, ∇f∗(αn∇f(xn) + (1 −αn)∇f(Txn))) =Wf(αn∇f(xn) + (1 −αn)∇f(Txn), p) ≤αnWf(∇f(xn), p) + (1 −αn)Wf(∇f(Txn), p) =αnDf(p, xn) + (1 −αn)Df(p, Txn) ≤αnDf(p, xn) + (1 −αn)Df(p, xn) =Df(p, xn).(35) This shows that the nonnegative sequence {Df(p, xn)}n∈Nis decreasing, thus bounded, and limn→∞ Df(p, xn) exists. From Proposition 10 we obtain that {xn}n∈Nis bounded, as claimed. Step 2. Every weak subsequential limit of {xn}n∈Nbelongs to c Fix (T). For any p∈c Fix (T) we have by the first inequality of (35), Df(p, xn+1)≤Df(p, xn) + (1 −αn) (Df(p, Txn)−Df(p, xn)) . Hence (1 −αn) (Df(p, xn)−Df(p, Txn)) ≤Df(p, xn)−Df(p, xn+1) (36) for all n∈N. We already know that limn→∞ Df(p, xn) exists. Since lim supn→∞ αn< 1, it follows that lim n→∞ (Df(p, xn)−Df(p, Txn)) = 0. 18 Now, since Tis strongly BSNE and p∈c Fix (T), we obtain lim n→∞ Df(Txn, xn) = 0. Since {xn}n∈Nis bounded, Proposition 7implies that lim n→∞ kTxn−xnk= 0. Therefore, if there is a subsequence {xnk}k∈Nof {xn}n∈Nwhich converges weakly to some v∈Xas k→+∞, then v∈c Fix (T). Step 3. The sequence {xn}n∈Nconverges weakly to a point in c Fix (T). Since ∇fis weakly sequentially continuous, the result follows immediately from Proposition 9since limn→∞ Df(u, xn) exists for any weak subsequential limit uof the sequence {xn}n∈Nby Step 2. Corollary 2. Let T:X→Xbe a BSNE operator with respect to Fix (T) = c Fix (T)6=∅. Let f:X→Rbe a Legendre function which is totally convex on bounded subsets of X. Suppose that ∇fis weakly sequentially continuous and ∇f∗ is bounded on bounded subsets of int dom f∗. Let {xn}n∈Nbe the sequence generated by (34), where {αn}n∈N⊂[0,1] satisfies lim supn→∞ αn<1. Then, for each x0∈X, the sequence {xn}n∈Nconverges weakly to a point in Fix (T). Remark 10. When f= (1/2) k·k2and Xis a Hilbert space, since both ∇fand ∇f∗ are the identity operator, the iterative scheme (34) coincides with the Mann iteration the weak convergence of which for nonexpansive mappings is well known, even in more general Banach spaces, under the assumption that Pn∈Nαn(1 −αn) = ∞(see [27]). Remark 11 (Common fixed point - Composition case).Let f:X→Rbe a Legendre function which is bounded, uniformly Fr´echet differentiable, and totally convex on bounded subsets of X. Suppose that ∇fis weakly sequentially continuous and ∇f∗is bounded on bounded subsets of int dom f∗. Let {Ti: 1 ≤i≤N}be NBSNE operators with respect to c Fix (Ti) = Fix (Ti)6=∅ for each 1 ≤i≤Nand let T=TNTN−1· · · T1. Then from Proposition 4and Remark 4we obtain that, if T{Fix (Ti) : 1 ≤i≤N} 6=∅,Tis also BSNE with respect to c Fix (T) = Fix (T) = T{Fix (Ti):1≤i≤N}. Now combining Theorem 2, Proposition 3and (31), we get that the sequence {xn}n∈Ngenerated by (34) converges weakly to an element in T{Fix (Ti):1≤i≤N} for each x∈X. 19 In the case where each Tiis strongly BSNE with c Fix (Ti)6=∅, the sequence {xn}n∈Nweakly converges to a common asymptotic fixed point of the family {Ti: 1 ≤i≤N}whenever such a point exists. ♦ 6 Block Iterative Algorithms We begin this section with three simple observations which are essential for our later study of the block operator. Lemma 1. Let f:X→(−∞,+∞]be a Legendre function and let {ti}N i=1 ⊂(0,1) satisfy PN i=1 ti= 1. Let {xi}N i=1 be a subset of Xand assume that f N X i=1 tixi!= N X i=1 tif(xi).(37) Then x1=x2=. . . =xN. Proof. If xk6=xlfor some k, l ∈ {1,2, . . . , N}, then from the strict convexity of f we get ftk tk+tl xk+tl tk+tl xl<tk tk+tl f(xk) + tl tk+tl f(xl). Using this inequality, we obtain f N X i=1 tixi!=f (tk+tl)tk tk+tl xk+tl tk+tl xl+X i6=k,l tixi! ≤(tk+tl)ftk tk+tl xk+tl tk+tl xl+X i6=k,l tif(xi) <(tk+tl)tk tk+tl f(xk) + tl tk+tl f(xl)+X i6=k,l tif(xi) = N X i=1 tif(xi). This contradicts assumption (37). As a direct consequence of Lemma 1we have the following result. 20 Corollary 3. Let f:X→(−∞,+∞]be a Legendre function and let {ti}N i=1 ⊂(0,1) satisfy PN i=1 ti= 1. Let {ξi}N i=1 be a finite subset of X∗and assume that f∗ N X i=1 tiξi!= N X i=1 tif∗(ξi). Then ξ1=ξ2=. . . =ξN. Proof. Since the function fis Legendre, its conjugate f∗is also Legendre. Thus the result follows immediately from Lemma 1. The following lemma concerns the Bregman distance. Lemma 2. Let f:X→(−∞,+∞]be a Legendre function and let {ti}N i=1 ⊂(0,1) satisfy PN i=1 ti= 1. Let z∈X. Let {xi}N i=1 be a finite subset of Xand assume that Df z, ∇f∗ N X i=1 ti∇f(xi)!!= N X i=1 tiDf(z, xi).(38) Then x1=x2=. . . =xN. Proof. Equality (38) can be reformulated as follows: Df z, ∇f∗ N X i=1 ti∇f(xi)!!=Wf N X i=1 ti∇f(xi), z!= N X i=1 tiDf(z, xi). Now from the definition of Wf(see (10)) and the definition of the Bregman distance (see (9)) we get N X i=1 ti(f(z)−f(xi)− h∇f(xi), z −xii) = f(z) + f∗ N X i=1 ti∇f(xi)! −*N X i=1 ti∇f(xi), z+. Thus f∗ N X i=1 ti∇f(xi)!= N X i=1 ti(h∇f(xi), xii − f(xi)) . 21 Since f(xi) + f∗(∇f(xi)) = h∇f(xi), xiifor any 1 ≤i≤N, we obtain f∗ N X i=1 ti∇f(xi)!= N X i=1 tif∗(∇f(xi)) . Corollary 3now implies that x1=x2=. . . =xN, as claimed. Definition 10 (Block operator).Let {Ti: 1 ≤i≤N}be Noperators from Xto X and let {wi}N i=1 ⊂(0,1) satisfy PN i=1 wi= 1. Then the block operator corresponding to {Ti: 1 ≤i≤N}and {wi: 1 ≤i≤N}is defined by TB:= ∇f∗ N X i=1 wi∇f(Ti)!.(39) Remark 12. The following inequality will be essential in our next result: Df(p, TBx) = Df p, ∇f∗ N X i=1 wi∇f(Tix)!!=Wf N X i=1 wi∇f(Tix), p! ≤ N X i=1 wiWf(∇f(Tix), p) = N X i=1 wiDf(p, Tix).(40) It follows from Proposition 1(i),(ii). ♦ In our next result we prove that the block operator defined by (39) is weakly QBNE when each Ti, 1 ≤i≤N, is weakly QBNE. Proposition 12 (Block operator of weakly QBNE operators).Assume that f: X→(−∞,+∞]is a Legendre function and let {Ti: 1 ≤i≤N}be Nweakly QBNE operators from Xinto Xsuch that F=T{Fix (Ti):1≤i≤N} 6=∅. Let {wi}N i=1 ⊂ (0,1) satisfy PN i=1 wi= 1. Then TBis weakly QBNE with respect to F= Fix (TB). Proof. Let p∈F. Since each Ti,i= 1, . . . , N, is QBNE, we obtain from (40) that Df(p, TBx)≤ N X i=1 wiDf(p, Tix)≤ N X i=1 wiDf(p, x) = Df(p, x) (41) for all x∈X. Thus TBis a QBNE operator with respect to F. Next we will show that Fix (TB) = F. 22 The inclusion F⊂Fix (TB) is obvious, so it is enough to show that Fix (TB)⊂F. To this end, let u∈Fix (TB) and k∈ {1,2, . . . , N}. For p∈F, such that p6=u, we obtain from (40) that Df(p, u) = Df(p, TBu)≤ N X i=1 wiDf(p, Tiu)≤X i6=k wiDf(p, u) + wkDf(p, Tku). Therefore wkDf(p, u) = 1−X i6=k wi!Df(p, u)≤wkDf(p, Tku), that is, wkDf(p, u)≤wkDf(p, Tku). Since wk>0, it follows that Df(p, u)≤Df(p, Tku). On the other hand, since Tk is weakly QBNE and p∈F⊂Fix (Tk), we have Df(p, Tku)≤Df(p, u). Thus Df(p, u) = Df(p, Tku) for all k∈ {1,2, . . . , N}. Hence Df p, ∇f∗ N X i=1 wi∇f(Tiu)!!=Df(p, TBu) = Df(p, u) = N X i=1 wiDf(p, Tiu). (42) Now Lemma 2implies that T1u=T2u=. . . =Tnu. Therefore u∈F. Proposition 13 (Asymptotic fixed points of block operators).Let f:X→Rbe a Legendre function which is bounded, uniformly Fr´echet differentiable and totally convex on bounded subsets of X. If each Ti,i= 1, . . . , N, is a strongly BSNE operator from Xinto itself, and the set b F:= \nc Fix (Ti):1≤i≤No is not empty, then c Fix (TB)⊂b F. Proof. Let u∈b Fand let x∈c Fix (TB). Then there exists a sequence {xn}n∈Nwhich converges weakly to xsuch that limn→∞ (xn−TBxn) = 0. Since the function fis bounded on bounded subsets of X,∇fis also bounded on bounded subsets of X(see [12, Proposition 1.1.11, p. 17]). So the sequences {xn}n∈Nand {∇f(TBxn)}n∈Nare bounded. Since fis also uniformly Fr´echet differentiable, it is uniformly continuous on bounded subsets of Xand therefore lim n→∞ (f(TBxn)−f(xn)) = 0.(43) 23 In addition, by Proposition 8we obtain that ∇fis also uniformly continuous on bounded subsets of Xand thus lim n→∞ (∇f(TBxn)− ∇f(xn)) = 0.(44) From the definition of the Bregman distance (see (9)) we obtain that Df(u, xn)−Df(u, TBxn) = [f(u)−f(xn)− h∇f(xn), u −xni] −[f(u)−f(TBxn)− h∇f(TBxn), u −TBxni] =f(TBxn)−f(xn)− h∇f(xn), u −xni +h∇f(TBxn), u −TBxni =f(TBxn)−f(xn)− h∇f(xn)− ∇f(TBxn), u −xni +h∇f(TBxn), xn−TBxni. Combining the facts that {xn}n∈Nand {∇f(TB(xn))}n∈Nare bounded, (43) and (44), we obtain that lim n→∞ (Df(u, xn)−Df(u, TBxn)) = 0.(45) Since each operator Ti,i= 1, . . . , N, is strongly BSNE, we deduce from (19) and (40) that for any k= 1, . . . , N, Df(u, TBxn)≤ N X i=1 wiDf(u, Tixn) = wkDf(u, Tkxn) + X i6=k wiDf(u, Tixn) ≤wkDf(u, Tkxn) + X i6=k wiDf(u, xn) =wkDf(u, Tkxn) + (1 −wk)Df(u, xn) =wk(Df(u, Tkxn)−Df(u, xn)) + Df(u, xn).(46) Hence for any k∈ {1, . . . , N}, we have lim n→∞ wk(Df(u, xn)−Df(u, Tkxn)) ≤lim n→∞ (Df(u, xn)−Df(u, TBxn)) = 0. Thence lim n→∞ (Df(u, xn)−Df(u, Tkxn)) = 0 for any k∈ {1, . . . , N}. Since each operator Ti,i= 1, . . . , N, is strongly BSNE, we get from (20) and (21) that lim n→∞ Df(Tixn, xn) = 0. 24 Since fis totally convex and {xn}n∈Nis bounded, it follows from Proposition 7that lim n→∞ (Tixn−xn) = 0. This means that xbelongs to c Fix (Ti) because we also know that xn* x. Therefore x∈b F, which proves that c Fix (TB)⊂b F, as claimed. Proposition 14 (Block operator of strongly BSNE operators).Let f:X→Rbe a Legendre function which is bounded, uniformly Fr´echet differentiable and totally convex on bounded subsets of X. Assume that ∇f∗is bounded on bounded subsets of int dom f∗. If each Ti,i= 1, . . . , N, is a strongly BSNE operator from Xinto itself, and the sets b F:= \nc Fix (Ti):1≤i≤No and c Fix (TB)are not empty, then TBis also strongly BSNE. Proof. If u∈c Fix (TB), then u∈b Fby Proposition 13. Therefore the fact that each Ti,i= 1, . . . , N, is strongly BSNE, with respect to c Fix (Ti), implies that (19) holds for TBand any x∈X. Now we assume that there exists a bounded sequence {xn}n∈Nin Xsuch that lim n→∞ (Df(u, xn)−Df(u, TBxn)) = 0 and therefore, as we proved in Proposition 13, we get lim n→∞ (Df(u, xn)−Df(u, Tixn)) = 0 for any i∈ {1, . . . , N}. Since each Ti,i= 1, . . . , N, is strongly BSNE and u∈ c Fix (TB)⊂c Fix (Ti), it follows from (20) and (21) that lim n→∞ Df(Tixn, xn)=0. Since fis totally convex and {xn}n∈Nis bounded, it follows from Proposition 7that lim n→∞ (Tixn−xn) = 0. Since fis uniformly Fr´echet differentiable, it follows from Proposition 8that ∇fis uniformly continuous on bounded subsets of Xand thus lim n→∞ (∇f(Tixn)− ∇f(xn)) = 0. 25