Tóm tắt Luận án Solution methods for pseudomonotone variational inequalities

VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY INSTITUTE OF MATHEMATICS PHAM DUY KHANH SOLUTION METHODS FOR PSEUDOMONOTONE VARIATIONAL INEQUALITIES Speciality: Applied Mathematics Speciality code: 62 46 01 12 SUMMARY DOCTORAL DISSERTATION IN MATHEMATICS HANOI - 2015 The dissertation was written on the basis of the author’s research works carried at Institute of Mathematics, Vietnam Academy of Science and Technology. Supervisors: 1. Prof. Dr. Hab. Nguyen Dong Yen 2. Dr. Trinh Cong Dieu First referee: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Second referee: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Third referee: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . To be defended at the Jury of Institute of Mathematics, Vietnam Academy of Science and Technology: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . on . . . . . . . . . . . . . . . . . . . . . 2015, at . . . . . . . . . o’clock . . . . . . . . . . . . . . . . . . . . . . . . . . . The dissertation is publicly available at: • The National Library of Vietnam • The Library of Institute of Mathematics Introduction Monotone operators have been studied since the early 1960s. F. Browder systematically employed the monotonicity of operators to study various prob- lems related to nonlinear elliptic partial differential equations. Independently, P. Hartman and G. Stampacchia studied variational inequalities (VIs for brevity) with monotone operators. Until now, monotone VIs continue to be a subject of the concern of many researchers. Different solution methods have been proposed for monotone VIs: the projection method, the Tikhonov reg- ularization method, the proximal point method, the extragradient method, etc. The concept of pseudomonotone operator introduced by S. Karamardian (1976) is an important generalization of monotone operator. Inspired by this paper, S. Karamardian and S. Schaible (1990) introduced several general- ized monotonicity concepts such as strict pseudomonotonicity, strong pseu- domonotonicity, and quasimonotonicity. For each type of generalized mono- tonicity of operators, these authors established a relation to the corresponding type of generalized convexity of functions. It turns out that pseudomonotone operator is a special case of quasimonotone operator. In the last decade, solu- tion existence and solution methods for pseudomonotone and quasimonotone VIs have been studied in many books and papers. The two-volume book of F. Facchinei and J.S. Pang (2003) and the handbook edited by N. Hadjisav- vas, S. Komlo´si, and S. Schaible (2005) are among the most cited references in this field. Facchinei and Pang (2003) raised a question about the convergence of the Tikhonov regularization method (TRM) for pseudomonotone VIs. With the aid of a solution existence theorem based on the degree theory and some interesting arguments, N. Thanh Hao (2006) solved the question in the af- firmative. Namely, she proved that if the original problem has a solution, then the Tikhonov regularized problem has a compact nonempty solution set which diameter tends to zero, and any selection of the solution mapping 1 converges to the least-norm solution of the original problem. The results of Facchinei and Pang on solution existence of pseudomonotone VIs have been extended by B.T. Kien, J.-C. Yao, and N.D. Yen (2008) to VIs and set-valued VIs in reflexive Banach spaces. The results of Thanh Hao on the convergence of the TRM for pseudomonotone VIs have been developed to VIs in Hilbert spaces by N.N. Tam, J.-C. Yao, and N.D. Yen (2008). For monotone VIs, the convergence of the iterative sequence generated by the proximal point algorithm (PPA) and the applicability of the algorithm (in the exact form as proposed by B. Martinet (1970), or in the inexact form as proposed by R.T. Rockafellar (1976)) are a novel research theme in this direction. For pseudomonotone VIs in Hilbert spaces, N.N. Tam, J.-C. Yao, and N.D. Yen (2008) have obtained some new results on the convergence of the exact PPA and inexact PPA. The auxiliary problems of the TRM and of the PPA, applied to pseu- domonotone VIs, may not be pseudomonotone, or may remain without any solution (if one considers the infinite-dimensional Hilbert space setting). In addition, if the auxiliary problems have a solution then they may have mul- tiple solutions. These phenomena indicate that the auxiliary problems can be more difficult than the original one. A natural question arises: If there is any algorithm that can solve pseudomonotone VIs in an effective way? The extragradient method (EGM) proposed by G.M. Korpelevich (1976) is such an algorithm. The thesis has five chapters. Chapter 1 recalls some basic notions like variational inequality problem, complementarity problem, monotonicity, pseudomonotonicity, and metric pro- jection. Several fundamental solution methods for monotone VIs are also presented. Chapter 2 deals with some questions related to applying the TRM for pseu- domonotone VIs. Solution uniqueness for the regularized problems is studied in two cases: unconstrained VIs and linear complementarity problems. The pseudomonotonicity of the regularized mappings of an affine mapping defined on a polyhedral convex set is investigated. Chapter 3 presents a modified projection method for solving strongly pseu- domonotone VIs. Strong convergence and error estimates for the iterative sequences are investigated in two versions of the method: the stepsizes are chosen arbitrarily from a given fixed closed interval and the stepsizes form 2 a non-summable decreasing sequence of positive real numbers. In addition, an interesting class of strongly pseudomonotone infinite-dimensional VIs is considered. Chapter 4 is devoted to a modified EGM for solving pseudomonotone VIs in Hilbert spaces. The convergence and convergence rate of the iterative sequences generated by this method are studied. Chapter 5 proposes a new EGM for solving strongly pseudomonotone VIs in Hilbert spaces. A detailed analysis of the iterative sequences’ convergence and of the range of applicability of the method is provided. The results of the thesis were reported by the author at - Seminar of Department of Numerical Analysis and Scientific Computing of Institute of Mathematics, Vietnam Academy of Science and Technology, Hanoi; - Summer School “Variational Analysis and Applications”, Institute of Mathematics, Vietnam Academy of Science and Technology, Hanoi (June 20–25, 2011); - The 8th Vietnam-Korea Workshop “Mathematical Optimization Theory and Applications”, University of Dalat (December 8–10, 2011); -The VMS-SMF Joint Congress at University of Hue (August 20–24, 2012). 3 Chapter 1 Preliminaries The concepts of variational inequality, complementarity problem, metric pro- jection, together with three basic solution methods for variational inequalities (the Tikhonov regularization method, the proximal point algorithm, the ex- tragradient method) are described in this chapter. 1.1 Variational Inequalities and Complementarity Prob- lems Let K be a nonempty subset of a real Hilbert space (H, 〈., .〉) and let F : K → H be a single-valued mapping. The variational inequality defined by K and F which is denoted by VI(K,F ) is the problem of finding a vector u∗ ∈ K such that 〈F (u∗), u− u∗〉 ≥ 0, ∀u ∈ K. (1.1) The set of solutions to this problem is denoted by Sol(K,F ). The complementarity problem given by a convex cone K and a mapping F : K → H is the problem of finding a vector u∗ ∈ H with u∗ ∈ K, F (u∗) ∈ K∗, 〈F (u∗), u∗〉 = 0, (1.2) where K∗ := {d ∈ H : 〈d, u〉 ≥ 0 ∀u ∈ K} is the dual cone of K. Problem (1.2) is abbreviated to CP(K,F ). If u ∈ K and F (u) ∈ K∗ then u is called a feasible vector of CP(K,F ). If the problem CP(K,F ) has a feasible vector, it is said to be feasible. When H = IRn, F is an affine mapping, i.e., F (u) = Mu + q with M ∈ IRn×n, 4 q ∈ IRn, and K = IRn+ (in this case K∗ = IRn+), CP(K,F ) becomes the linear complementarity problem LCP(M, q): u∗ ≥ 0, Mu∗ + q ≥ 0, 〈Mu∗ + q, u∗〉 = 0. (1.3) Here the inequalities are taken componentwise. The solution set of this prob- lem is denoted by Sol(M, q). 1.2 Monotonicity and Generalized Monotonicity A mapping F : K ⊂ H → H is said to be (a) strongly monotone if there exists γ > 0 such that 〈F (u)− F (v), u− v〉 ≥ γ‖u− v‖2 ∀u, v ∈ K; (b) strongly pseudomonotone if there exists γ > 0 such that, for all u, v ∈ K, 〈F (u), v − u〉 ≥ 0 =⇒ 〈F (v), v − u〉 ≥ γ‖u− v‖2; (c) monotone if 〈F (u)− F (v), u− v〉 ≥ 0 for all u, v ∈ K; (d) pseudomonotone if, for all u, v ∈ K, 〈F (u), v − u〉 ≥ 0 =⇒ 〈F (v), v − u〉 ≥ 0; (e) quasimonotone if, for all u, v ∈ K, 〈F (u), v − u〉 > 0 =⇒ 〈F (v), v − u〉 ≥ 0. 1.3 Metric Projection Let K ⊂ H be a closed convex set. Then for each u ∈ H, there is a unique v ∈ K such that ‖u− v‖ = inf w∈K ‖u− w‖. (1.4) The unique vector v satisfying (1.4) is called the metric projection of u on K. It is denoted by PK(u). Several basic properties of the metric projection are recalled in the thesis. 5 1.4 The Tikhonov Regularization Method Consider the problem VI(K,F ) in a real Hilbert space H. Denote the identity mapping of H by I, and put Fε = F + εI for every ε > 0. To solve VI(K,F ), one solves the sequence of problems VI(K,Fεk) where {εk} is a sequence of positive real numbers converging to zero and Fεk = F + εkI. For each k ∈ IN , one selects a solution uk ∈ Sol(K,Fεk) and compute the limit lim k→∞ uk. When such limit exists, we may hope that the obtained vector is a solution of VI(K,F ). To terminate the computation process after a finite number of steps and to obtain an approximate solution of VI(K,F ), one has to introduce a stopping criterion. For example, we can terminate the computation when ‖uk − uk−1‖ ≤ θ where θ > 0 is a constant. Two basic convergence theorems for the Tikhonov regularization are re- called in the thesis. 1.5 The Proximal Point Algorithm Choose a point u0 ∈ H and a sequence {ρk} of positive real numbers satisfying the condition ρk ≥ ρ > 0 for all k ∈ IN . If uk−1 has been defined, one can choose uk as any solution of the auxiliary problem VI(K,F (k)) where F (k)(u) = ρkF (u) + u− uk−1, u ∈ K, (1.5) that is uk ∈ K and 〈ρkF (uk) + uk − uk−1, v − uk〉 ≥ 0, ∀v ∈ K. (Suppose that Sol(K,F (k)) is nonempty.) If the iterative scheme yields a sequence {uk}, then one computes the limit lim k→∞ uk in the norm topology or in the weak topology of H. When the limit exists, one may hope that the obtained element belongs to the solution set of VI(K,F ). To terminate the computation process after a finite number of steps and to obtain an approximate solution of VI(K,F ), one introduces a stopping criterion. For example, one can terminate the computation when ‖uk − uk−1‖ ≤ θ where θ > 0 is a constant. Basic convergence theorems for the proximal point algorithm are recalled in the thesis. 6 1.6 The Extragradient Method The extragradient method executes two projections per iteration. Suppose that F is Lipschitz continuous on K with the Lipschitz constant L > 0, that is ‖F (u)− F (v)‖ ≤ L‖u− v‖, ∀u, v ∈ K. (1.6) Algorithm 1.1 Data: u0 ∈ K and α ∈ (0, 1/L). Step 0: Set k = 0. Step 1: If uk = PK(u k − αF (uk)), stop. Step 2: Compute u¯k = PK(u k − αF (uk)), u¯k+1 = PK(u k − αF (u¯k)); set k ← k + 1 and go to Step 1. Two convergence theorems for the extragradient method are recalled in the thesis. 7 Chapter 2 On the Tikhonov Regularization Method and the Proximal Point Algorithm for Pseudomonotone Problems This chapter presents our partial solutions for the some open questions about the solution uniqueness of the regularized problem of a pseudomonotone VI and the preservation of the pseudomonotonicity under the regularization. 2.1 Open Questions on Pseudomonotone Variational Inequalities Open questions. If K ⊂ IRn is a nonempty closed convex set, F : K → IRn is a continuous pseudomonotone mapping, and the problem VI(K,F ) has a solution, then there exists ε1 > 0 such that the mapping Fε = F + εI is pseudomonotone for each ε ∈ (0, ε1)? Is there any ε2 > 0 such that the problem VI(K,Fε) has a unique solution for every ε ∈ (0, ε2)? 2.2 Solution Uniqueness of the Regularized Problems Let K be a subset of IRn. A mapping F : K → IRn is said to be pseudoaffine on K if F and −F are both pseudomonotone. 8 Theorem 2.1 A mapping F : IRn → IRn is pseudoaffine if and only if there exists a skew matrix M ∈ IRn×n, i.e., MT = −M , a vector q ∈ IRn, and a positive function g : IRn → IR such that F (u) = g(u)(Mu+ q), ∀u ∈ IRn. Theorem 2.2 Suppose that F (u) = g(u)(Mu+ q) with g : IRn → IR being a positive and continuously differentiable function, M ∈ IRn×n a skew symmet- ric and nonsingular matrix, and q ∈ IRn an arbitrarily given vector. Then there exists ε¯ > 0 such that the regularized problem VI(K,Fε) has a unique solution for all ε ∈ (0, ε¯). If detM 6= 0 and MT = −M , then n must be an even number. This shows that the assumptions of Theorem 2.2 are rather strict. It is natural to find some ways to enlarge the applicability of Theorem 2.2. Theorem 2.3 Suppose that F : IRn → IRn is a map of the form F (u) = g(u)(Mu+ q), where g : IRn → IR is a positive and continuously differentiable function, M ∈ IRn×n is a positive semidefinite nonsingular matrix, and q ∈ IRn. Then there exists ε¯ > 0 such that the regularized problem VI(K,Fε) has a unique solution for all ε ∈ (0, ε¯). Consider the linear complementarity problem of the form (1.3). Theorem 2.4 Suppose that (1.3) is feasible and the mapping F (u) = Mu+q is pseudomonotone on IRn+. Then the regularized problem LCP(Mε, q), where Mε = M + εI, has a unique solution for any ε ∈ (0,+∞). 2.3 Pseudomonotonicity of the Regularized Mappings Theorem 2.5 Let K ⊂ IR be a closed convex subset and F (u) = au + b be an affine map. Then F is pseudomonotone on K if and only if one of the following five cases occurs: (a) K has a unique element; (b) K = IR and a ≥ 0; (c) K = [α,+∞) for some α ∈ IR, and either a ≥ 0 or a < 0 and aα+b < 0; 9 (d) K = (−∞, β] for some β ∈ IR, and either a ≥ 0 or a 0; (e) K = [α, β], for some α, β ∈ IR with α < β, and either a ≥ 0 or a < 0 and aα + b 0. Corollary 2.1 Let K be a closed convex set in IR and F (u) = au + b be an affine map. If F is pseudomonotone on K then there exists ε¯ > 0 such that Fε(u) = (a+ ε)u+ b is pseudomonotone on K for all ε ∈ (0, ε¯). The pseudomonotonicity preservation of Fε for small enough ε > 0 (pro- vided that F is pseudomonotone), which was described in Corollary 2.1 for the case K ⊂ IR, is no longer valid if K is a nonempty closed convex subset of IRn, n ≥ 2. Theorem 2.6 Suppose that F (u) = Mu+ q is an affine map, where M = diag(λ1, λ2, . . . , λn), q = (q1, q2, . . . , qn) T (2.1) are respectively a diagonal matrix and a vector in IRn. Then F is pseu- domonotone on IRn+ if and only if one of the following conditions holds: (i) λi ≥ 0 for every i ∈ {1, 2, . . . , n}; (ii) There exists a unique i ∈ {1, 2, . . . , n} such that{ λi < 0, qi < 0, λj = 0, qj = 0 ∀j ∈ {1, 2, . . . , n} \ {i}. (2.2) There is a class of pseudomonotone affine mappings whose regularized op- erators Fε are not pseudomonotone for all sufficiently small ε > 0. Theorem 2.7 Let F (u) = Mu + q, with M = diag(λ1, λ2, . . . , λn) being a diagonal matrix and q = (q1, q2, . . . , qn) T being a vector in IRn. If F is merely pseudomonotone on IRn+ (i.e., F is pseudomonotone but not monotone on IRn+), then there exists ε¯ > 0 such that Fε(u) = F (u)+εu is not pseudomono- tone on IRn+ for all ε ∈ (0, ε¯). 2.4 Some Remarks on the Proximal Point Algorithm in the Affine Case Observe that if F is Lipschitz continuous on K with a Lipschitz constant L > 0, then for any uk ∈ IRn and ε > L the regularized operator Fk,ε(u) := F (u) + ε(u− uk) 10 is strongly monotone. For the PPA, we have F (k)(u) = ρkF (u) + u− uk−1 = ρkF (u) + ε(u− uk−1), (2.3) where ε = 1. Hence, if L is a Lipschitz constant of F on K then ρkL is a Lip- schitz constant of ρkF (.) on K, so the above fact on the strong monotonicity of the regularized operator tells us that if ε = 1 > ρkL (i.e., 0 < ρk < L −1), then F (k)(.) is strongly monotone on K with the constant αk := 1− ρkL. The following advantage of PPA in comparison with the TRM is clear: the auxiliary problem VI(K,F (k)), for every k ∈ IN , is strongly monotone if F is merely Lipschitzian (no monotonicity is required!), provided that the coefficient ρk is such that 0 < ρk < L −1. Since affine operators are obviously Lipschitzian, the PPA can be effective applied for pseudomonotone affine VIs. Namely, if F (u) = Mu + q with M ∈ IRn×n \{0} and q ∈ IRn then F (k)(.) is strongly monotone on K with the constant αk := 1 − ρk‖M‖ for any ρk satisfies 0 < ρk < ‖M‖−1. Therefore, the iterative sequence given by the PPA, where 0 < ρ ≤ ρk < ‖M‖−1 for all k, converges, provided that the original problem has a solution. In other words, the PPA can solve any pseudomonotone affine VI. 11 Chapter 3 A Modified Projection Method The projection method is a fundamental solution method for strongly mono- tone variational inequalities. We now consider a modified projection method for strongly pseudomonotone variational inequalities. 3.1 Algorithm Consider the problem VI(K,F ) under the assumption that K ⊂ H is a nonempty closed convex set. Algorithm 3.1 Data: u0 ∈ K and {λk} ⊂ (0,+∞). Step 0: Set k = 0. Step 1: If uk = PK(u k − λkF (uk)) then stop. Step 2: Compute uk+1 = PK(u k − λkF (uk)) and replace k by k + 1; go to Step 1. If the computation terminates at a step k, then we put uk ′ = uk for all k′ ≥ k + 1. Thus, for a given sequence of variable stepsizes {λk} ⊂ (0,+∞), Algorithm 3.1 produces for each initial point u0 ∈ K a unique iterative se- quence {uk}. Proposition 3.1 Suppose that F is strongly pseudomonotone on K with a constant γ and Lipschitz continuous on K with a constant L. Let {uk} be a sequence generated by Algorithm 3.1. If u∗ is a unique solution of VI(K,F ) then [1 + λk(2γ − λkL2)]‖uk+1 − u∗‖2 ≤ ‖uk − u∗‖2 ∀k ∈ IN. (3.1) 12 3.2 Modified Projection with A Priori Constants Iterative sequences generated by Algorithm 3.1 for strongly pseudomonotone VIs are linearly convergent, provided that the given problem has a solution. Theorem 3.1 Let F be strongly pseudomonotone on K with a constant γ and Lipschitz continuous on K with a constant L. Suppose that 0 < a ≤ λk ≤ b < 2γ L2 ∀k ∈ IN, (3.2) where a, b are some positive constants. Let {uk} be the sequence generated by Algorithm 3.1. If u∗ is the unique solution of VI(K,F ) then the sequence {uk} converges linearly to u∗. Moreover, the priori and posteriori error estimates ‖uk+1 − u∗‖ ≤ µ k+1 1− µ‖u 1 − u0‖ (3.3) and ‖uk+1 − u∗‖ ≤ µ 1− µ‖u k+1 − uk‖ (3.4) hold for all k ∈ IN . Here µ := 1√ 1 + a(2γ − bL2) ∈ (0, 1). (3.5) As an illustration, we now apply Theorem 3.1 to a class of strongly pseu- domonotone infinite-dimensional variational inequality problems. To the best of our knowledge, this is the first time a class of strongly pseudomonotone operators, not just a single problem, is given explicitly. Example 3.1 Let H = `2, the Hilbert space whose elements are the 2- summable sequences of real scalars, i.e., H = {u = (u1, u2, . . . , ui, . . .) : ∞∑ i=1 |ui|2 < +∞}. The inner product and the norm on H are given by setting 〈u, v〉 = ∞∑ i=1 uivi and ‖u‖ = ( ∞∑ i=1 ui )1/2 for any u = (u1, u2, . . . , ui, . . .) and v = (v1, v2, . . . , vi, . . .) in H. Let α, β ∈ IR be such that β > α > β 2 > 0 and define Kα = {u ∈ H : ‖u‖ ≤ α}, Fβ(u) = (β − ‖u‖)u. 13 Here α and β are parameters. We have Sol(Kα, Fβ) = {0}. The operator Fβ is Lipschitz continuous with the Lipschitz constant L := β+ 2α and strongly pseudomonotone with the modulus γ := β − α on Kα. Moreover, Fβ are neither strongly monotone nor monotone on Kα. To see this, it suffices to choose u = (β 2 , 0, . . . , 0, . . .), v = (α, 0, . . . , 0, . . .) ∈ Kα and note that 〈Fβ(u)− Fβ(v), u− v〉 = ( β 2 − α )3 < 0. Pick any u0 ∈ Kα and set λk = λ for all k ∈ IN , where λ ∈ (0, 2γ L2 ) = ( 0, 2(β − α) (β + 2α)2 ) is taken arbitrarily. From Theorem 3.1 it follows that the sequence {uk} gen- erated by Algorithm 3.1 converges linearly to 0, which is the unique solution of the problem VI(Kα, Fβ). Moreover, in view of (3.3) and (3.4), ‖uk+1 − 0‖ ≤ µ k+1 1− µ‖u 1 − u0‖ and ‖uk+1 − 0‖ ≤ µ 1− µ‖u k+1 − uk‖ for all k ∈ IN , where µ = 1√ 1 + λ[2(β − α)− λ(β + 2α)2] . 3.3 Modified Projection without A Priori Constants Theorem 3.2 Let F be strongly pseudomonotone on K with a constant γ and Lipschitz continuous on K with a constant L. Suppose that {λk} is a sequence of positive scalars with ∞∑ k=0 λk = +∞, lim k→∞ λk = 0. (3.6) Let {uk} be a sequence generated by Algorithm 3.1. If VI(K,F ) has a unique solution u∗, then the sequence {uk} converges in norm to u∗. Moreover, there exists an index k0 ∈ IN such that, for each k ≥ k0, one has λk(2γ−λkL2) > 0 and ‖uk+1 − u∗‖ ≤ 1√∏k i=k0 [1 + λi(2γ − λiL2)] ‖uk0 − u∗‖. (3.7) To analyze the conditions (3.2) and (3.6) given respectively in Theorem 3.1 and Theorem 3.2, we can consider two examples. 14 Example 3.2 Put K = IR and F (u) = u. It is clear that F is Lipschitz continuous, strongly monotone on K, and Sol(K,F )={0}. Choose u0 = 1 ∈ K and λk = (k + 2) −2 for all k ∈ IN . Since lim k→∞ λk = 0 and ∞∑ k=0 λk < +∞, both the conditions (3.2) and (3.6) are violated. The iterative sequence {uk} produced by Algorithm 3.1 for u0 = 1 is given by uk+1 = PK(u k − λkF (uk)) = uk − λkuk = (1− λk)uk. Hence, uk+1 = k∏ i=0 (1− λi) = k∏ i=0 ( 1− 1 (i+ 2)2 ) ∀k ∈ IN. This shows that the sequence {uk} is decreasing and bounded from below. So {uk} is convergent. Note that uk+1 = k∏ i=0 ( 1− 1 (i+ 2)2 ) = k∏ i=0 (i+ 1)(i+ 3) (i+ 2)2 = k + 3 2(k + 2) . Letting k → ∞, we obtain limk→∞ uk = 12 . This means that {uk} does not converge to the unique solution of VI(K,F ) under our consideration. We have seen that, in Theorem 3.1 and Theorem 3.2, the conditions (3.2) and (3.6) cannot be dropped. Finally, let us show that the sequence {uk} considered in Theorem 3.2 may not converge linearly to the unique solution of VI(K,F ). Example 3.3 Let K,F be the same as in Example 3.2 and u0 ∈ IR\{0}. Let {λk} ⊂ (0,+∞) be satisfying (3.6) and λk 6= 1 for all k ∈ IN . The iteration formula in Algorithm 3.1 now becomes uk+1 = PK(u k − λkF (uk)) = uk − λkuk = (1− λk)uk. Since lim k→∞ λk = 0 and u k 6= 0 for all k ∈ IN , we have lim k→∞ ‖uk+1 − 0‖ ‖uk − 0‖ = limk→∞ |1− λk| = 1 Hence one cannot find any µ ∈ (0, 1) such that the inequality ‖uk+1 − 0‖ ≤ µ‖uk − 0‖ holds for every k ∈ IN . This means that {uk} does not converge linearly to the unique solution of VI(K,F ). 15 Chapter 4 A Modified Extragradient Method 4.1 Algorithm Consider the problem VI(K,F ) where K is a nonempty convex subset of a real Hilbert space H and F is Lipschitz continuous for some constant L > 0. The modified EGM for solving VI(K,F ) can be described as follows. Algorithm 4.1 Data: u0 ∈ K and {αk}∞k=0 ⊂ [a, b], where 0 < a ≤ b < 1L . Step 0: Set k = 0. Step 1: If uk = PK(u k − αkF (uk)) then stop. Step 2: Set u¯k = PK(u k − αkF (uk)), uk+1 = PK(u k − αkF (u¯k)), (4.1) and replace k by k + 1; go to Step 1. 4.2 Convergence of the Iterative Sequences Theorem 4.1 Let F be a pseudomonotone mapping and let {uk} be a se- quence generated by the Algorithm 4.1. If Sol(K,F ) is nonempty, then {uk} is a bounded sequence and lim k→∞ ‖uk− u¯k‖ = 0. Moreover, if there exists a sub- sequence {uki} ⊂ {uk} converging strongly to some uˆ ∈ K, then uˆ ∈ Sol(K,F ) and the whole sequence {uk} converges strongly to uˆ. Theorem 4.2 Let F be a pseudomonotone mapping and let {uk} be a se- quence generated by Algorithm 4.1. If {uk} converges strongly to some u∗, 16 then u∗ is a solution of VI(K,F ). Theorem 4.3 Suppose that F is a pseudomonotone mapping and {uk} is a sequence generated by the Algorithm 4.1. If {uk} is bounded and it has a strongly convergent subsequence, then the whole sequence converges strongly to a solution of VI(K,F ). We are interested in finding a lower bound for the constant a and an upper bound for the constant b in Algorithm 4.1 and in Theorems 4.1-4.3. Example 4.1 Consider the problem VI(K,F ) with K = IR and F (u) = u. We can easily check that F is Lipschitz continuous with Lipschitz constant L = 1, monotone, and Sol(K,F ) = {0}. Let u0 = 1 ∈ K and let the real sequence {αk} ⊂ (0, 1) be defined by setting αk = 2−(k+1) for all k ∈ IN := {0, 1, 2, . . .}. The iterative sequence in (4.1) is given by uk+1 = k+1∏ i=1 (1− 2−i + 4−i) ∀k ∈ IN. Then {uk} converges to u¯ /∈ Sol(K,F ). Example 4.1 shows that the exact lower bound for a is 0. Example 4.2 Let K,F, u0 be the same as in Example 4.1 and let αk = 1 − 2−(k+1) for all k ∈ IN . Observe that αk → 1 = 1/L as k → ∞, where L = 1 is the Lipschitz constant of F . The iterative sequence in (4.1) is given by uk+1 = k+1∏ i=1 (1− 2−i + 4−i) ∀k ∈ IN. Then {uk} converges to u¯ /∈ Sol(K,F ). Example 4.2 shows that the exact upper bound for b is 1/L. Theorem 4.4 Suppose that F is a monotone mapping and {uk} is a sequence generated by Algorithm 4.1. If Sol(K,F ) is nonempty, then there exists uˆ in Sol(K,F ) such that {uk} converges weakly to uˆ. 4.3 Convergence Rate of the Iterative Sequences Suppose that a sequence {uk} in H converges in norm to u∗ ∈ H. We say that 17 (a) {uk} converges to u∗ with R-linear convergence rate if limsup k→∞ ‖uk − u∗‖1/k < 1, (b) {uk} converges to u∗ with Q-linear convergence rate if there exists a con- stant µ ∈ (0, 1) such that, for all sufficiently large k, ‖uk+1 − u∗‖ ≤ µ‖uk − u∗‖. Note that Q-linear convergence rate implies R-linear convergence rate. To see that R-linear convergence does not imply Q-linear convergence in general, one can considers the next simple example. Example 4.3 Let {uk} ⊂ IR be the sequence of real numbers defined by setting uk = 2−k if k is even and uk = 3−k if k is odd. Since limsup k→∞ ‖uk − 0‖1/k = 1 2 , {uk} converges to 0 with R-linear convergence rate. However {uk} does not converge to 0 with Q-linear convergence rate since limsup k→∞ ‖uk+1 − 0‖ ‖uk − 0‖ = +∞. The problem VI(K,F ) is said to satisfy Tseng’s regularity assumption if it has a solution and there exist real numbers δ, η > 0 such that d(u, Sol(K,F )) ≤ η‖u− PK(u− F (u))‖ (4.2) for all u ∈ K with the property ‖u− PK(u− F (u))‖ ≤ δ. (4.3) Theorem 4.5 Let F be a pseudomonotone mapping. Suppose that the prob- lem VI(K,F ) satisfies Tseng’s regularity condition and {uk} is an iterative sequence produced by Algorithm 4.1. Then, {uk} converges in norm to an element of Sol(K,F ) with R-linear convergence rate. If Tseng’s regularity assumption is violated, then the iterative sequence {uk} may not converge in norm to any solution of VI(K,F ) with R-linear convergence rate. The following example clarifies this remark. Example 4.4 Consider the problem VI(K,F ) with K = [0, 1] ⊂ IR and F (u) = u2 for every u ∈ IR. Then F is Lipschitz continuous on K with Lipschitz constant L = 2, monotone on K, and Sol(K,F ) = {0}. For every u ∈ K, note that d(u, Sol(K,F )) = u and ‖u− PK(u− F (u))‖ = u2. 18 Hence one cannot find any pair {η, δ} of positive real numbers such that (4.2) holds for every u ∈ K satisfying (4.3). This means that our problem VI(K,F ) does not satisfy Tseng’s regularity assumption. Choose u0 = 1 ∈ K and αk = 1/4 ∈ (0, 1/2) for all k ∈ IN . The sequence {uk} produced by (4.1) is given by uk+1 = −(1/64)(uk)4 + (1/8)(uk)3 − (1/4)(uk)2 + uk ∀k ∈ IN. Using induction, we can prove that uk ≥ 1 k+1 for all k ∈ IN . Hence limsup k→∞ ‖uk‖1/k ≥ limsup k→∞ ( 1 k + 1 )1/k = 1. Therefore, although {uk} converges to the unique solution u∗ = 0 of VI(K,F ), the convergence rate is not R-linear. Theorem 4.6 Suppose that F is a strongly pseudomonotone mapping and VI(K,F ) has a solution u∗. Then, the sequence {uk} generated by Algorithm 4.1 converges in norm to u∗ with Q-linear convergence rate. 19 Chapter 5 A New Extragradient Method The idea of using stepsizes which form a non-summable diminishing sequence of positive real numbers to deal with a strongly pseudomonotone problem VI(K,F ) came to us from the theory of solution methods for nonsmooth convex optimization problems. Algorithm 5.1 Data: Let u0 ∈ K and {αk}∞k=0 ⊂ IR+ be such that ∞∑ k=0 αk = +∞, lim k→∞ αk = 0. (5.1) Step 0: Set k = 0. Step 1: If uk = uk = PK(u k − αkF (uk)) then stop. Step 2: Compute u¯k = PK(u k − αkF (uk)), uk+1 = PK(u k − αkF (u¯k)), (5.2) and replace k by k + 1; go to Step 1. If the computation terminates at a step k, then one puts uk ′ = uk for all k′ ≥ k + 1. Thus, Algorithm 5.1 produces an infinite iterative sequence. 5.1 Convergence of the Iterative Sequences Theorem 5.1 If F : K → H is Lipschitz continuous and strongly pseu- domonotone on K, and if VI(K,F ) has a unique solution u∗, then the se- quence {uk} generated by Algorithm 5.1 converges in norm to u∗. Moreover, 20 there exists an index k0 ∈ IN such that γαk < 1 for all k ≥ k0 and ‖uk+1 − u∗‖ ≤ √√√√ k∏ j=k0 (1− γαj)‖uk0 − u∗‖, (5.3) where γ > 0 is a strong pseudomonotonicity constant of F . In addition, lim k→∞ √√√√ k∏ j=k0 (1− γαj) = 0. (5.4) 5.2 Further Analysis The strong pseudomonotonicity assumption on F and the two conditions in (5.1) are essential for the validity of the assertion of Theorem 5.1. To see this, let us start with analyzing the condition ∞∑ k=0 αk = +∞ described in (5.1). Example 5.1 Put K = IR and F (u) = u. It is clear that F is Lipschitz continuous, strongly monotone on K, and Sol(K,F )={0}. Choose u0 = 1 ∈ K and define the sequence {αk} by setting αk = (k + 1)−2 for all k ∈ IN . Since ∞∑ k=0 αk < +∞, the first condition in (5.1) is violated. The sequence {uk} produced by (5.2) is given by uk+1 = k∏ j=0 (1− αj + α2j) = k∏ j=0 ( 1− 1 (j + 1)2 + 1 (j + 1)4 ) ∀k ∈ IN. Note that lim k→∞ uk = u∗ for some u∗ ≥ 1 2 . So {uk} does not converge to the unique solution of the problem VI(K,F ) under our consideration. Thus we have seen that the assumption ∞∑ k=0 αk = +∞ cannot be dropped in the formulation of Theorem 5.1. The second condition in (5.1) is analyzed in the next example. Example 5.2 Let K,F, u0 be the same as in Example 5.1 and let αk = 1 for all k ∈ IN . Here ∞∑ k=0 αk = +∞, but {αk} does not converge to 0. By the calculations done in Example 5.1 we get uk = 1 for all k ∈ IN . So {uk} does not converge to the unique solution of VI(K,F ). We have seen that the condition lim k→∞ αk = 0 cannot be omitted in the formulation of Theorem 5.1. 21 Finally, let us show that the strong pseudomonotonicity assumption on F in Theorem 5.1 is essential. Example 5.3 Put K = IR2 and F (u) = (−u2, u1)T for all u = (u1, u2)T ∈ K. It is clear that F is Lipschitz continuous and monotone on K, and Sol(K,F ) = {(0, 0)T}. Let u0 = (u01, u02)T be any point in K \ {(0, 0)T} and let αk = 1 k + 1 ∀k ∈ IN. This sequence satisfies (5.1). To see that F is not strongly pseudomonotone on K with any constant γ > 0, it suffices to choose u = (1, 0)T , v = (2, 0)T and note that 〈F (u), v − u〉 = 0, but 〈F (v), v − u〉 = 0. The sequence {uk} in (5.2) is given by u0 = (u01, u 0 2) T and uk+11 = ( 1− 1 (k + 1)2 ) uk1 + 1 k + 1 uk2 uk+12 = ( 1− 1 (k + 1)2 ) uk2 − 1 k + 1 uk1 (5.5) for k = 0, 1, 2, . . .. Observe that lim k→∞ ‖uk‖ = µ‖u0‖, where µ = lim k→∞ √√√√ k∏ j=0 ( 1− 1 (j + 1)2 + 1 (j + 1)4 ) ≥ √ 2 2 . (5.6) Hence {uk} does not converge to the unique solution of VI(K,F ). Interest- ingly, the set of the cluster points of the sequence {uk} is the circle S := {u ∈ IR2 : ‖u‖ = µ‖u0‖}. Example 5.3 shows that Algorithm 5.1, which works well for strongly pseu- domonotone VIs, cannot serve as an adequate solution method for pseu- domonotone VIs. 22 General Conclusions The main results of this dissertation include: - Partial solutions for the open questions stated in a paper by N. Thanh Hao (2006) about the solution uniqueness of the Tikhonov regularized problem of a pseudomonotone variational inequality and the preservation of the pseu- domonotonicity under the regularization; - A modified extragradient method for solving infinite-dimensional varia- tional inequalities together with a convergence analysis; - A new extragradient method for strongly pseudomonotone variational inequalities, accompanied by a detailed analysis of the iterative sequences’ convergence and of the range of applicability of the method; - Two modified projection methods for strongly pseudomonotone varia- tional inequalities which have a strong convergence; - Several theorems on convergence rates of the iterative sequences. Further investigations on the following topics would be of interest: - Verification of the pseudomonotonicity of an affine operator on a given polyhedral convex set; - Effective solution methods for quasimonotone variational inequalities; - Extragradient methods for continuous pseudomonotone variational in- equalities. 23 List of Author’s Related Papers 1. P. D. Khanh, Partial solution for an open question on pseudomonotone variational inequalities. Appl. Anal. 91 (2012), 1691–1698. 2. P. D. Khanh, On the Tikhonov regularization of affine pseudomonotone mappings. Optim. Lett. 8 (2014), 1325–1336. 3. P. D. Khanh, A modified extragradient method for infinite-dimensional variational inequalities. (Accepted for publication in Acta Mathematica Vietnamica.) 4. P. D. Khanh, On the convergence rate of a modified extragradient method for pseudomonotone variational inequalities. (Submitted to Journal of Nonlinear and Convex Analysis on October 25, 2012.) 5. P. D. Khanh, A new extragradient method for strongly pseudomonotone variational inequalities. (Submitted to Numerical Functional Analysis and Optimization on January 29, 2013.) 6. P. D. Khanh and P. T. Vuong, Modified projection method for strongly pseudomonotone variational inequalities. J. Global Optim. 58 (2014), 341–350. 24