# Strong Convergence of a Modified  Extragradient  Method to the Minimum-Norm Solution of Variational Inequalities

Authors: Yonghong Yao; Muhammad Aslam Noor; Yeong-Cheng Liou
Journal: Abstract and Applied Analysis
 (2012)

---

## Abstract

We suggest and analyze a modified extragradient method for solving variational inequalities, which is convergent strongly to the minimum-norm solution of some variational inequality in an infinite-dimensional Hilbert space.


---

## Body

## 1. Introduction

LetC be a closed convex subset of a real Hilbert space H. A mapping A:C→H is called α-inverse-strongly monotone if there exists a positive real number α such that (1.1)〈Au-Av,u-v〉≥α‖Au-Av‖2,∀u,v∈C.
The variational inequality problem is to find u∈C such that (1.2)〈Au,v-u〉≥0,∀v∈C.
The set of solutions of the variational inequality problem is denoted by VI(C,A). It is well known that variational inequality theory has emerged as an important tool in studying a wide class of obstacle, unilateral, and equilibrium problems, which arise in several branches of pure and applied sciences in a unified and general framework. Several numerical methods have been developed for solving variational inequalities and related optimization problems; see [1–36] and the references therein.It is well known that variational inequalities are equivalent to the fixed point problem. This alternative formulation has been used to study the existence of a solution of the variational inequality as well as to develop several numerical methods. Using this equivalence, one can suggest the following iterative method.Algorithm 1.1.
For a givenu0∈C, calculate the approximate solution un+1 by the iterative scheme
(1.3)un+1=PC[un-λAun],n=0,1,2,….
It is well known that the convergence of Algorithm 1.1 requires that the operator A must be both strongly monotone and Lipschitz continuous. These restrict conditions rules out its applications in several important problems. To overcome these drawbacks, Korpelevič suggested in [8] an algorithm of the form
(1.4)yn=PC[xn-λAxn],xn+1=PC[xn-λAyn],n≥0.
Noor [2] further suggested and analyzed the following new iterative methods for solving the variational inequality (1.2).Algorithm 1.2.
For a givenu0∈C, calculate the approximate solution un+1 by the iterative scheme
(1.5)un+1=PC[wn-λAwn],wn=PC[un-λAun],n=0,1,2,…,
which is known as the modified extragradient method. For the convergence analysis of Algorithm 1.2, see Noor [1, 2] and the references therein. We would like to point out that Algorithm 1.2 is quite different from the method of Korpelevič [8]. However, Algorithm 1.2 fails, in general, to converge strongly in the setting of infinite-dimensional Hilbert spaces.
In this paper, we suggest and consider a very simple modified extragradient method which is convergent strongly to the minimum-norm solution of variational inequality (1.2) in an infinite-dimensional Hilbert space. This new method includes the method of Noor [2] as a special case.


## 2. Preliminaries

LetH be a real Hilbert space with inner product 〈·,·〉 and norm ∥·∥, and let C be a closed convex subset of H. It is well known that, for any u∈H, there exists a unique u0∈C such that (2.1)‖u-u0‖=inf⁡{‖u-x‖:x∈C}.
We denote u0 by PCu, where PC is called the metric projection of H onto C. The metric projection PC of H onto C has the following basic properties:(i)
∥PCx-PCy∥≤∥x-y∥ for all x,y∈H;(ii)
〈x-y,PCx-PCy〉≥∥PCx-PCy∥2 for every x,y∈H;(iii)
〈x-PCx,y-PCx〉≤0 for all x∈H, y∈C.We need the following lemma for proving our main results.Lemma 2.1 (see [15]).
Assume that{an} is a sequence of nonnegative real numbers such that
(2.2)an+1≤(1-γn)an+δn,
where {γn} is a sequence in (0,1) and {δn} is a sequence such that(1)
∑n=1∞γn=∞;(2)
limsupn→∞δn/γn≤0 or ∑n=1∞|δn|<∞.Then limn→∞an=0.


## 3. Main Result

In this section we will state and prove our main result.Theorem 3.1.
LetC be a closed convex subset of a real Hilbert space  H. Let  A:C→H be an  α-inverse-strongly monotone mapping. Suppose that  VI(C,A)≠∅. For given  x0∈C arbitrarily, define a sequence  {xn} iteratively by
(3.1)yn=PC[(1-αn)(xn-λAxn)],xn+1=PC(yn-λAyn),n≥0,
where {αn} is a sequence in (0,1) and λ∈[a,b]⊂(0,2α) is a constant. Assume the following conditions are satisfied:(C1)
:limn→∞αn=0;(C2)
:∑n=1∞αn=∞;(C3)
:limn→∞(αn+1/αn)=1. Then the sequence {xn} generated by (3.1) converges strongly to PVI(C,A)(0) which is the minimum-norm element in VI(C,A).We will divide our detailed proofs into several conclusions.Proof.
Takex*∈VI(C,A). First we need to use the following facts: (1)
x*=PC(x*-λAx*)forallλ>0; in particular,(3.2)x*=PC[x*-λ(1-αn)Ax*]=PC[αnx*+(1-αn)(x*-λAx*)],∀n≥0;(2)
I-λA is nonexpansive and for all x,y∈C(3.3)‖(I-λA)x-(I-λA)y‖2≤‖x-y‖2+λ(λ-2α)‖Ax-Ay‖2.
From (3.1), we have
(3.4)‖yn-x*‖=‖PC[(1-αn)(xn-λAxn)]-PC[αnx*+(1-αn)(x*-λAx*)]‖≤‖αn(-x*)+(1-αn)[(xn-λAxn)-(x*-λAx*)]‖≤αn‖x*‖+(1-αn)‖(I-λA)xn-(I-λA)x*‖≤αn‖x*‖+(1-αn)‖xn-x*‖.
Thus,
(3.5)‖xn+1-x*‖=‖PC(yn-λAyn)-PC(x*-λAx*)‖≤‖(yn-λAyn)-(x*-λAx*)‖≤‖yn-x*‖≤αn‖x*‖+(1-αn)‖xn-x*‖≤max⁡{‖x*‖,‖x0-x*‖}.
Therefore, {xn} is bounded and so are {yn},{Axn}, and {Ayn}.
From (3.1), we have
(3.6)‖xn+1-xn‖=‖PC(yn-λAyn)-PC(yn-1-λAyn-1)‖≤‖(yn-λAyn)-(yn-1-λAyn-1)‖≤‖yn-yn-1‖=‖PC[(1-αn)(xn-λAxn)]-PC[(1-αn-1)(xn-1-λAxn-1)]‖≤‖(1-αn)[(I-λA)xn-(I-λA)xn-1]-(αn-αn-1)(I-λA)xn-1‖≤(1-αn)‖(I-λA)xn-(I-λA)xn-1‖+|αn-αn-1|‖(I-λA)xn-1‖≤(1-αn)‖xn-xn-1‖+|αn-αn-1|M,
where M>0 is a constant such that supn{∥(I-λA)xn∥,∥(I-λA)xn∥(∥(I-λA)xn∥+2∥xn-x*∥)}≤M. Hence, by Lemma 2.1, we obtain
(3.7)lim⁡n→∞⁡‖xn+1-xn‖=0.
From (3.4), (3.5) and the convexity of the norm, we deduce
(3.8)‖xn+1-x*‖2≤‖αn(-x*)+(1-αn)[(xn-λAxn)-(x*-λAx*)]‖2≤αn‖x*‖2+(1-αn)‖(I-λA)xn-(I-λA)x*‖2≤αn‖x*‖2+(1-αn)[‖xn-x*‖2+λ(λ-2α)‖Axn-Ax*‖2]≤αn‖x*‖2+‖xn-x*‖2+(1-αn)a(b-2α)‖Axn-Ax*‖2.
Therefore, we have
(3.9)(1-αn)a(2α-b)‖Axn-Ax*‖2≤αn∥x*∥2+∥xn-x*∥2-∥xn+1-x*∥2≤αn‖x*‖2+(‖xn-x*‖+‖xn+1-x*‖)×‖xn-xn+1‖.
Since αn→0 and ∥xn-xn+1∥→0 as n→∞, we obtain ∥Axn-Ax*∥→0 as n→∞.
By the property (ii) of the metric projectionPC, we have
(3.10)‖yn-x*‖2=‖PC[(1-α)(xn-λAxn)]-PC(x*-λAx*)‖2≤〈(1-αn)(xn-λAxn)-(x*-λAx*),yn-x*〉=12{‖(xn-λAxn)-(x*-λAx*)-αn(I-λA)xn‖2+‖yn-x*‖2-‖(xn-λAxn)-(x*-λAx*)-(yn-x*)-αn(I-λA)xn‖2}≤12{‖(xn-λAxn)-(x*-λAx*)‖2+αnM+‖yn-x*‖2-‖(xn-yn)-λ(Axn-Ax*)-αn(I-λA)xn‖2}≤12{‖xn-x*‖2+αnM+‖yn-x*‖2-‖xn-yn‖2+2λ〈xn-yn,Axn-Ax*〉+2αn〈(I-λA)xn,xn-yn〉-‖λ(Axn-Ax*)+αn(I-λA)xn‖2}≤12{‖xn-x*‖2+αnM+‖yn-x*‖2-‖xn-yn‖2+2λ‖xn-yn‖‖Axn-Ax*‖+2αn‖(I-λA)xn‖‖xn-yn‖‖xn-x*‖2}.
It follows that
(3.11)‖yn-x*‖2≤∥xn-x*∥2+αnM-∥xn-yn∥2+2λ‖xn-yn‖‖Axn-Ax*‖+2αn‖(I-λA)xn‖‖xn-yn‖,
and hence
(3.12)‖xn+1-x*‖2≤‖yn-x*‖2≤‖xn-x*‖2+αnM-‖xn-yn‖2+2λ‖xn-yn‖‖Axn-Ax*‖+2αn‖(I-λA)xn‖‖xn-yn‖
which implies that
(3.13)‖xn-yn‖2≤(‖xn-x*‖+‖xn+1-x*‖)‖xn+1-xn‖+αnM+2λ‖xn-yn‖‖Axn-Ax*‖+2αn‖(I-λA)xn‖‖xn-yn‖.
Since αn→0,∥xn-xn+1∥→0, and ∥Axn-Ax*∥→0, we derive ∥xn-yn∥→0.
Next we show that(3.14)limsup⁡n→∞⁡〈z0,z0-yn〉≤0,
where z0=PVI(C,A)(0). To show it, we choose a subsequence {yni} of {yn} such that
(3.15)limsup⁡n→∞〈z0,z0-yn〉=lim⁡i→∞〈z0,z0-yni〉.
As {yni} is bounded, we have that a subsequence {ynij} of {yni} converges weakly to z.
Next we show thatz∈VI(C,A). We define a mapping T by
(3.16)Tv={Av+NCv,v∈C,∅,v∉C.
Then T is maximal monotone (see [16]). Let (v,w)∈G(T). Since w-Av∈NCv and yn∈C, we have 〈v-yn,w-Av〉≥0. On the other hand, from yn=PC[(1-αn)(xn-λAxn)], we have
(3.17)〈v-yn,yn-(1-αn)(xn-λAxn)〉≥0,
that is,
(3.18)〈v-yn,yn-xnλ+Axn+αnλ(I-λA)xn〉≥0.
Therefore, we have
(3.19)〈v-yni,w〉≥〈v-yni,Av〉≥〈v-yni,Av〉-〈v-yni,yni-xniλ+Axni+αniλ(I-λA)xni〉=〈v-yni,Av-Axni-yni-xniλ-αniλ(I-λA)xni〉=〈v-yni,Av-Ayni〉+〈v-yni,Ayni-Axni〉-〈v-yni,yni-xniλ+αniλ(I-λA)xni〉≥〈v-yni,Ayni-Axni〉-〈v-yni,yni-xniλ+αniλ(I-λA)xni〉.
Noting that αni→0, ∥yni-xni∥→0, and A is Lipschitz continuous, we obtain 〈v-z,w〉≥0. Since T is maximal monotone, we have z∈T-1(0), and hence z∈VI(C,A). Therefore,
(3.20)limsup⁡n→∞〈z0,z0-yn〉=lim⁡i→∞〈z0,z0-yni〉=〈z0,z0-z〉≤0.
Finally, we prove xn→z0. By the property (ii) of metric projection PC, we have
(3.21)‖yn-z0‖2=‖PC[(1-αn)(xn-λAxn)]-PC[αnz0+(1-αn)(z0-λAz0)]‖2≤〈αn(-z0)+(1-αn)[(xn-λAxn)-(z0-λAz0)],yn-z0〉≤αn〈z0,z0-yn〉+(1-αn)‖(xn-λAxn)-(z0-λAz0)‖‖yn-z0‖≤αn〈z0,z0-yn〉+(1-αn)‖xn-z0‖‖yn-z0‖≤αn〈z0,z0-yn〉+1-αn2(‖xn-z0‖2+‖yn-z0‖2).
Hence,
(3.22)‖yn-z0‖2≤(1-αn)‖xn-z0‖2+2αn〈z0,z0-yn〉.
Therefore,
(3.23)‖xn+1-z0‖2≤‖yn-z0‖2≤(1-αn)‖xn-z0‖2+2αn〈z0,z0-yn〉.
We apply Lemma 2.1 to the last inequality to deduce that x0→z0. This completes the proof.Remark 3.2.
Our Algorithm (3.1) is similar to Noor’s modified extragradient method; see [2]. However, our algorithm has strong convergence in the setting of infinite-dimensional Hilbert spaces.



---

*Source: 817436-2011-12-15.xml*