Nonexpansive mappings and monotone vector fields in Hadamard manifolds

Communications in Applied Analysis 13 (2009), no. 4, 633–646 NONEXPANSIVE MAPPINGS AND MONOTONE VECTOR FIELDS IN HADAMARD MANIFOLDS VICTORIA MART´ IN-M´ ARQUEZ Departamento de An´alisis Matem´atico, Universidad de Sevilla Sevilla, Apdo. 1160, 41080, Spain E-mail: [email protected] ABSTRACT. This paper briefly surveys some recent advances in the investigation of nonexpansive mappings and monotone vector fields, focusing in the extension of basic results of the classical nonlinear functional analysis from Banach spaces to the class of nonpositive sectional curvature Riemannian manifolds called Hadamard manifolds. Within this setting, we first analyze the problem of finding fixed points of nonexpansive mappings. Later on, different classes of monotonicity for set-valued vector fields and the relationship between some of them will be presented, followed by the study of the existence and approximation of singularities for such vector fields. We will discuss about variational inequality and minimization problems in Hadamard manifolds, stressing the fact that these problems can be solved by means of the iterative approaches for monotone vector fields. AMS (MOS) Subject Classification. 49M30, 90C26. 1. INTRODUCTION AND MOTIVATION Riemannian manifolds constitute a broad and fruitful framework for the development of different fields in mathematic, such as convexity, dynamical systems, optimization or mathematical programming, and other scientific areas, where some of its approaches and methods have successfully been extended from Euclidean spaces. The nonpositive sectional curvature is an important property which is enjoyed by a large class of Riemannian manifolds and it is strong enough to imply tight topological restrictions and rigidity phenomena. Hence Riemannian manifolds with this property have awakened the interest of many researches. Specially, Hadamard manifolds, which are complete simply connected and finite dimensional Riemannian manifolds of nonpositive sectional curvature, have worked out a suitable setting for diverse disciplines, being an example of hyperbolic spaces and geodesic spaces such as Busemann nonpositive curvature (NPC) spaces and CAT(0) spaces, see [24, 20, 53]. Received June 1, 2009 1083-2564 $15.00 c Dynamic Publishers, Inc. 634 V. MARTIN-MARQUEZ Within the setting of Riemannian manifolds we are particularly concerned about two problems: the approach of fixed points of nonexpansive mappings and the existence and approximation of singularities of monotone vector fields. In a metric space X, a mapping T:X→Xis nonexpansive if for any two points x, y ∈Xthe following inequality holds: d(T(x), T(y)) ≤d(x, y). The study of the asymptotic behavior of such mappings and its relevant role in the fixed point theory have seen a significant increase in interest on the part of scientists from nonlinear analysis and many other disciplines where it finds application. Two types of algorithms for approximating fixed points of nonexpansive mappings have been successfully considered in the normed linear framework: Halpern’s iteration, given by the formula xn+1 =αnu+ (1 −αn)Txn, n ≥0,(1.1) where u∈Xis an arbitrary point; and Mann’s iteration, whose iterative scheme is xn+1 =αnxn+ (1 −αn)Txn, n ≥0.(1.2) A large number of works about the convergence and some modifications of these two methods can be found (see [44, 55, 28] and reference therein), but just few results have been obtained out of the framework of linear spaces. With preciseness, some progresses have been made in the setting of geodesic spaces, hyperbolic metric spaces and in the special case of Hadamard manifolds. See [16, 17, 45, 23, 24, 27]. If we denote by X∗the dual space of the Banach space X, recall that a (setvalued) operator A:X→2X∗is said to be monotone provided that (x∗−y∗, x −y)≥0,∀x, y ∈ D(A) and x∗∈A(x), y∗∈A(y), where D(A) denotes the domain of Adefined by D(A) := {x∈X:A(x)6=∅}. The concept of a monotone operator has turned out to be very powerful in various areas of mathematics such as operator theory, numerical analysis, differentiability of convex functions and partial differential equations, because it is broad enough to cover both linear positive semi-definite operators and subdifferentials of convex functions (see [42, 31, 32]). It is the latter one which has received most of the recent attention in diverse frameworks, due to its increasing importance in optimization theory. On the other hand, extensions of concepts and techniques for optimization in Rn to Riemannian manifolds are natural, and this has been done frequently in order to develop theoretical results and get efficient algorithms, see [50, 53, 20]. The study of this optimization methods’ extension to solve minimization problems on Riemannian manifolds has been the subject of many works, solving non-convex constrained minimization problems in Euclidean spaces by means of convex problems on Riemannian NONEXPANSIVE MAPPINGS AND MONOTONE VECTOR FIELDS 635 manifolds, see [7, 8, 13, 15, 14, 39, 40]. A generalization of the convex minimization problem is the variational inequality problem. In the study of this problem in the framework of Riemannian manifolds several classes of monotone vector fields have been introduced (see [34, 35, 10] for single-valued vector field and [9] for point-to-set vector fields) and convergence properties of iterative methods to solve them have been presented (see for instance [11, 13]). A more general problem is the search of zeros of monotone operators, i.e. solutions of the inclusion 0 ∈A(x). In this direction, the concept of maximal monotone operators and its relationship with the notion of upper semicontinuity have been very useful, see [41, 2]. In [26] both definitions for set-valued vector fields were extended to Hadamard manifolds and proved to be equivalent. Many diverse approaches for approximating zeros in the setting of Banach spaces have been investigated by many authors (see [5, 6, 21, 29, 47]). It is worth mentioning the widely studied proximal point algorithm, inspired by Moreau and Martinet [29, 30, 33] and defined by Rockafellar [47] by means of the following iterative scheme 0∈A(xn+1) + λn(xn+1 −xn), where {λn}is a sequence of real positive numbers and x0is an initial point. Another successful iterative method is the extragradient algorithm proposed first by Korpelevich [25] and studied by many authors (see, for instance, [18, 51]). As regards the counterpart of these methods in Hadamard manifolds, convergence of the proximal point algorithm was proved for subdifferential of convex functions in minimization problems (see [15]) and for maximal monotone vector fields in general (see [26]). An extragradient-type method for continuous monotone vector fields was developed by Ferreira et al [13]. Most of this extended methods requires the Riemannian manifold to have nonpositive sectional curvature, specially, to be a Hadamard manifold. This is due to the fact that, in general, the exponential map cannot be defined in the whole tangent bundle and it is not invertible (see reference in section 2 for details). Then we will focus in the case of Hadamard manifolds, remarking the statements which remain true in Riemannian manifolds in general. The purpose of this paper is to describe the role of nonexpansive mappings and monotone vector fields in Hadamard manifolds, as well as the problems mentioned above which involve such operators and make its closeness quite clear. In section 2 we introduce some notations and we provide references about basic concepts on Riemannian manifolds. The fixed point problem for nonexpansive mappings will be discussed in section 3. Section 4 is devoted to introduce different classes of monotonicity, establishing some relationship between them, and analyze the existence and approximation of singularities of monotone vector fields. We deal with variational 636 V. MARTIN-MARQUEZ inequality and minimization problems in Hadamard manifolds in sections 5, stressing the fact that these problems can be solved by means of the iterative approaches for monotone vector fields. 2. NOTATION In this section we fix the notations used throughout this paper. We assume that the reader is familiar with the basic concepts and properties on Riemannian manifold. As general references in Riemannian geometry, we recommend [12, 43, 48, 53, 54]. Moreover, basic knowledge of fixed point theory [24], monotone operators [41, 56], variational inequalities [22] and optimization theory [1, 49] could ease the reading of these notes. Let Mbe a Hadamard manifold, that is a complete simply connected m-dimensional Riemannian manifold of nonpositive sectional curvature. Given p∈Mwe denote the tangent space of Mat pby TpMand the tangent bundle of Mby TM =Sp∈MTpM. Let X(M) denote the set of all set-valued vector fields A:M→2T M such that A(x)⊆TxMfor each x∈M. We assume that D(A) = {x∈M:A(x)6=∅},the domain of A, is closed and convex. Recall that a subset K⊆Mis convex if for any two points pand qin K, the geodesic joining pto qis contained in K. For any x∈Mand K⊂Mclosed convex set, there exists a unique x∗∈Ksuch that d(x, x∗)≤d(x, y) for all y∈K. That unique point is called the projection of x onto the convex set Kand is denoted by PK(x). We use Px,y to denote the parallel transport on the tangent bundle TM along the geodesic γstarting at xand ending at y. This is an isometry from TxMto TyM. Recall that the exponential map at p∈M, expp:TpM→M, is defined by exppv=γv(1, x), where γv(., p) is the geodesic starting at pwith velocity v. Then, for any value of t, expptv =γv(t, p). Since Mis Hadamard, exppis a diffeomorphism from Mto Rm. Then, Mhas the same topology and differential structure as Rm. Let f:M→(−∞,+∞] be a proper extended real-valued function with domain D(f) := {x∈M:f(x)6= +∞}. The function fis said to be convex if for any geodesic γin M, the composition function f◦γ:R→(−∞,+∞] is convex. 3. FIXED POINTS OF NONEXPANSIVE MAPPINGS Let F:= Fix(T) denote the set of all fixed points of a nonexpansive mapping T:K→K, where Kis a closed convex subset of M, and assume that F6=∅. We recall that from Brouwer’s theorem the existence of fixed points is ensured provided that Kis bounded. In order to solve the problem of approximating a fixed point of T, Kirk provided in [24] an implicit algorithm in general metric spaces called geodesic spaces which contains the class of Hadamard manifolds. Applying the general NONEXPANSIVE MAPPINGS AND MONOTONE VECTOR FIELDS 637 result due to Kirk to Hadamard manifolds, and writing the algorithm in terms of the exponential map, one obtain the following theorem. Theorem 3.1. [24] Let u∈K, and for each t∈[0,1) let xtbe the unique point such that xt= exputexp−1 uT(xt). Then limt→1−xt=x, the unique nearest point to xin F. In an Euclidean space Rn, this iterative scheme turns into xt= (1 −t)x+tT(xt), which coincides with the implicit Halpern-type algorithm called Browder’s iteration, see [4]. An analogue of Halpern’s algorithm (1.1) was developed for nonexpansive mappings on Hadamard manifolds, whose iterative scheme is xn+1 = expu(1 −αn) exp−1 uT(xn),∀n≥0,(3.1) where x0, u ∈Mand {αn} ⊂ (0,1) and which coincides with the Halpern’s one in the particular case of an Euclidean space. Theorem 3.2. [27] Let u, x0∈M. Suppose that {αn} ∈ (0,1) satisfies (H1) limn→∞ αn= 0; (H2) Pn≥0αn=∞; (H3) either Pn≥0|αn+1 −αn|<∞or limn→∞(αn−αn−1)/αn= 0. Then the sequence {xn}generated by the algorithm (3.1) converges to PF(u). As regards Mann’s iteration (1.2), an extension of this algorithm and its convergence results to the framework of metric spaces is due to Goebel-Kirk [23, 16] and Reich-Shafrir [45]. In spaces of hyperbolic type, which includes Hadamard manifolds, they provided an iterative scheme in terms of geodesic segments, coinciding with Mann’s algorithm in Euclidean spaces. In particular, under the assumption that {αn}is bounded away from 0 and 1, Reich and Shafrir proved the convergence of such iteration to a fixed point of Tdefined in the Hilbert ball. Goebel and Reich [17] studied the behavior of the sequence of the iterates xn+1 =T(xn) in hyperbolic metric spaces for a class of nonexpansive mappings. Recently, the authors of [27] proved the convergence of the algorithm xn+1 = expxn(1 −αn) exp−1 xnT(xn),∀n≥0,(3.2) in the setting of Hadamard manifolds. Theorem 3.3. [27] Suppose that {αn} ⊂ (0,1) satisfy the condition ∞ X n=0 αn(1 −αn) = ∞. Let x0∈Mand let {xn}be the sequence generated by the algorithm (3.2). Then {xn} converges to a fixed point of T. 638 V. MARTIN-MARQUEZ Note that the theorem above generalized the convergence result of the Mann’s algorithm in the case of an Euclidean space. In order to illustrate the behavior of both Halpern’s and Mann’s iteration in Hadamard manifolds, a numerical example in a finite-dimensional hyperbolic space is presented in [27]. 4. SINGULARITIES OF MONOTONE VECTOR FIELDS The concepts of monotonicity and strict monotonicity of vector fields defined on a Riemannian manifold were introduced by N´emeth in [35]. In [10] the strong monotonicity was defined, and they established the relationship between different classes of vector fields’ monotonicity and their differential operators’ definiteness. The authors of [13] provided a class of monotone vector fields, those which are gradients of convex functions, and the complementary vector field of a nonexpansive mappings is proved to be monotone in [34]. For more examples and relations between different kinds of generalized monotone vector fields in Riemannian manifolds see [35, 36, 37]. The first appearance of the concept of monotone set-valued vector field is found in [9] where it is shown that the subdifferential operator of a Riemannian convex function is a monotone set-valued vector field. The notion of maximal monotonicity for set-valued vector fields was given in [26] for Hadamard manifolds. The definitions below can be rewritten in general Riemannian manifold in term of geodesics. Definition 4.1. Let A∈ X (M).Ais called (a) monotone if for any x, y ∈ D(A)the following condition holds: hu, exp−1 xyi ≤ hv, −exp−1 yxi,∀u∈A(x)and ∀v∈A(y); (4.1) (b) strictly monotone if (4.1) is satisfied with strict inequality for any x, y ∈ D(A); (c) strongly monotone if there exists ρ > 0such that, for any x, y ∈ D(A), hu, exp−1 xyi − hv, −exp−1 yxi ≤ −ρd2(x, y),∀u∈A(x)and ∀v∈A(y); (4.2) (d) maximal monotone if it is monotone and, for any x∈ D(A)and u∈TxM, the condition that hu, exp−1 xyi ≤ hv, −exp−1 yxi,∀y∈ D(A)and v∈A(y) (4.3) implies that u∈A(x). With the aim of characterize the maximal monotone vector fields, the notions of upper semicontinuity and upper Kuratowski semicontinuity (cf. [49, p. 55]) as well as the local boundedness for operators in Banach spaces were extended to the setting of Hadamard manifolds in the following definition (see [26]). Definition 4.2. Let A∈ X (M)and x0∈ D(A).Ais called NONEXPANSIVE MAPPINGS AND MONOTONE VECTOR FIELDS 639 (a) upper semicontinuous at x0if for any open set Vsatisfying A(x0)⊆V⊆Tx0M, there exists an open neighborhood U(x0)of x0such that Px,x0A(x)⊆Vfor any x∈U(x0); (b) upper Kuratowski semicontinuous at x0if for any sequences {xk} ⊆ D(A) and {uk} ⊂ TM with each uk∈A(xk), the relations limk→∞ xk=x0and limk→∞ uk=u0imply u0∈A(x0); (c) locally bounded at x0if there exists an open neighborhood U(x0)of x0such that the set Sx∈U(x0)A(x)is bounded. (d) upper semicontinuous (resp. upper Kuratowski semicontinuous, locally bounded) on Mif it is upper semicontinuous (resp. upper Kuratowski semicontinuous, locally bounded) at each x0∈ D(A). Clearly, the upper semicontinuity implies the upper Kuratowski semicontinuity, and we can deduce that the converse is also true provided that Ais locally bounded. The authors of [26] proved that the maximality implies the upper Kuratowski semicontinuity, and if the domain of the vector field is all the manifold then we get the extension of the well-known equivalence between the maximal monotonicity and the upper semicontinuity for a set-valued operator with closed and convex values in a Hilbert space (cf. [41]). Theorem 4.3. [26] Suppose that A∈ X(M)is monotone and that D(A) = M. Then the following statements are equivalent: (i) Ais maximal monotone. (ii) Ais upper semicontinuous on Mand A(x)is closed and convex for each x∈M. Recall that x∈ D(A) is a singularity of Aif 0 ∈A(x). We denote the set of all singularities of Aby A−1(0) := {x∈ D(A) : 0 ∈A(x)}. Regarding the existence of singularities, it is a direct consequence of the definition that a strictly monotone vector field has at most one singularity. In [10, 13] it was proved that strongly monotone single-valued vector fields on Hadamard manifolds with D(A) = Mhave at least one singularity, that is, since the strong monotonicity implies the strictly monotonicity, existence and uniqueness are ensured. This result was extended to the set-valued case for maximal strong monotonicity, using the equivalence established in Theorem 4.3 and the coercivity condition of finite-dimensional Banach spaces. When the domain of a monotone vector field Ais open and convex, it is known that in Riemannian manifolds the set of singularities is convex, see [13]. Some topological and metric consequences of the existence of strictly monotone vector fields have been studied in both single-valued and set-valued case, involving the sectional curvature, dimension or volume of the Riemannian manifold, see [9, 10]. 640 V. MARTIN-MARQUEZ The study of approximating zeros of monotone operators within the framework of a Banach space has awakened the interest of many researchers. Motivated by the proximal point algorithm on Rmintroduced and studied by Moreau [33], Martinet [29] and Rockafellar [47], and with the aim of generalize the iterative method given in [15] for approximating solutions of convex minimization problems, the following proximal point algorithm for set-valued vector fields on Hadamard manifolds was presented. Let x0∈ D(A) and {λn} ⊂ (0,1). Having xn, define xn+1 such that 0∈A(xn+1)−λnexp−1 xn+1 xn.(4.4) Note that this algorithm is implicit. But defining the vector field Bn(x) := A(x)−λnexp−1 xxnfor each x∈ D(A) and n≥0, if D(A) = Mand Ais maximal monotone, Bnis maximal strongly monotone and then the algorithm (4.4) is welldefined. The convergence of the method was established in the following theorem. Theorem 4.4. [26] Let A∈ X (M)be such that A−1(0) 6=∅. Suppose that Ais upper Kuratowski semicontinuous and monotone. Let {λn} ⊂ (0,1) satisfy sup{λn:n≥0}<∞.(4.5) Let x0∈ D(A)and suppose that the sequence {xn}generated by the algorithm (4.4) is well-defined. Then {xn}converges to a singularity of A. In the assumptions of the previous theorem, if we assume that D(A) = Mand A is maximal monotone, we obtain as consequence that xngenerated by (4.4) is welldefined and converges to a singularity of A, which is the equivalence result for the proximal point algorithm in a Hilbert space (see [47]). Another approach for finding zeros of monotone operators is the well-known extragradient algorithm proposed first by Korpelevich [25] and studied by many authors specially for solving variational inequalities (see, for instance, [18, 51]). An extragradient-type method for approximating singularities of continuous monotone vector fields defined on a constant curvature Hadamard manifold was presented and proved to converge by Ferreira et al [13]. They also provided an example of computation of such algorithm in a finite-dimensional hyperbolic space, We remark that in the definition and convergence of both previous algorithms we need to impose restrictions on the manifold, namely nonpositive sectional curvature. It would be desirable to extend these methods to an arbitrary Riemannian manifold, but for the moment, we are unable to solve this problem because, in general, the exponential map cannot be defined in the whole tangent bundle and it is not invertible. It is worth mentioning that the concept of monotonicity has been introduced in the setting of infinite-dimensional manifolds, together with other notions such NONEXPANSIVE MAPPINGS AND MONOTONE VECTOR FIELDS 641 as resolvent, Yosida approximation and accretive operators, and some convergence results for approximating the solutions of the equation 0∈d dtu(t) + Au(t), t > 0, in this context, have been proved (see [19] and references therein). 5. VARIATIONAL INEQUALITY AND MINIMIZATION PROBLEMS In this section we consider a convex subset Kof Mand V:K→TM a singlevalued vector field, that is, V(x)∈TxMfor each x∈K. The problem of finding x∈Ksuch that hV(x),exp−1 xyi ≥ 0,∀y∈K, (5.1) is called a variational inequality on K. The first step in analyzing this problem on Hadamard manifolds was taken by N´emeth [38, 13], establishing some existence and uniqueness theorems and studying the properties of the solution set of a variational inequality. He proved the existence of solutions of the variational inequality (5.1) for continuous vector fields defined on a compact convex subset of M, by using an extension of the well-known Brouwer fixed point Theorem to Hadamard manifolds (see [38]), whose unclear proof was completed in [26]. This fact could be deduced from more general results involving some abstract concepts as the Lefschetz number on acyclic spaces (see [3]), and the NPC spaces (see [52]). Lemma 5.1. [38] Let Kbe a compact convex subset of M. Let F:K→Kbe a continuous map. Then Fhas a fixed point in K. The following iterative approach to solve variational inequalities, deduced from the proximal point algorithm (4.4), was developed in [26]. Clearly, a point x∈Kis a solution of the variational inequality (5.1) if and only if xsatisfies that 0∈V(x) + NK(x), that is, xis a singularity of the set-valued vector field A:= V+NK, where NK(x) denote the normal cone of the set Kat x∈K: NK(x) := {u∈TxM:hu, exp−1 xyi ≤ 0,∀y∈K}. Applying the algorithm (4.4) to A, we get the following proximal point algorithm with initial point x0for finding solutions of the variational inequality (5.1): 0∈V(xn+1) + NK(xn+1)−λnexp−1 xn+1 xn,∀n≥0.(5.2) By the characterization of maximal monotone vector fields (Theorem 4.3), the convergence of the proximal point algorithm (Theorem 4.4) and Lemma 5.1 we obtain the well behavior of the algorithm (5.2).