# An Improved Two-Step Method for Generalized Variational Inequalities

Authors: Haibin Chen
Journal: ISRN Mathematical Analysis
 (2013)

---

## Abstract

We propose an improved two-step extragradient algorithm for pseudomonotone
generalized variational inequalities. It requires two projections at each iteration and
allows one to take different stepsize rules. Moreover, from a geometric point of view, it is
shown that the new method has a long stepsize, and it guarantees that the distance from the
next iterative point to the solution set has a large decrease. Under mild conditions, we show
that the method is globally convergent, and then theR-linearly convergent property of the
method is proven if a projection-type error bound holds locally.


---

## Body

## 1. Introduction

LetF be a multivalued mapping from Rn into 2Rn with nonempty values, where Rn is a Euclidean space. Let X be a nonempty, closed, and convex subset of the Euclidean space Rn. The generalized variational inequality, abbreviated as GVI, is to find a vector x*∈X such that there exists ω*∈F(x*) satisfying
(1)〈ω*,x-x*〉≥0,∀x∈X,
where 〈·,·〉 stands for the inner product of vectors in Rn. The solution set of problem (1) is denoted by X*. If the multivalued mapping F is a single-valued mapping from Rn to Rn, then the GVI collapses to the classical variational inequality problem [1–4].For the problem GVI, we all know that it plays a significant role in economics and transportation equilibrium, engineering sciences, and so forth, and it has received considerable attention in the past decades [1, 2, 5–11]. Solution methods for GVI have been studied extensively. They can be roughly categorized into two popular approaches to attack the solution existence problem of the GVI. The first is analytic approaches. Instead of solving problem directly, the analytic approach reformulates the GVI as a well-studied mathematical problem first and then invokes an existence theorem for the latter problem [12]. The second is a constructive approach in which the existence can be verified by the behavior of the proposed method which will be considered in this paper.To the best of our knowledge, the extragradient method [2, 13] is a popular constructive approach which was proposed by Korpelevich [13]. It has been proved that the method has a contract property; that is, the generated sequence {xk} by the method satisfies that
(2)∥xk+1-x*∥≤∥xk-x*∥,∀k≥0,
for any solution x* of the GVI. It should be noted that the proximal point algorithm also possesses this property [14].In [15], the authors proposed a new type extragradient projection method for variational inequalities (VI). The method proposed in [15] required only two projections at each iteration and allowed one to take different stepsize rules. Moreover, it was shown that this method had a long stepsize, and it guaranteed that the distance from the next iterative point to the solution set had a large decrease. Some elementary numerical experiments showed its efficiency. Now a question is posed naturally: as the problem GVI is an extension of the problem VI, can this theory be extended to the GVI? This constitutes the main motivation of the paper.In this paper, inspired by [15], we presented an improved extragradient method to the GVI problem. Under mild conditions, we first show that the generated sequence of the proposed method globally converges to the solution of the problem, and then we show that the method is R-linearly convergent if in addition a projection-type error bound holds locally. The rest of this paper is organized as follows. In Section 2, we give some related concepts and conclusions needed in the subsequent analysis. In Section 3, we present our designed algorithm and establish the convergence and convergent rate of the algorithm.


## 2. Preliminaries

In this section, we first give some related concepts and conclusions which are useful in the subsequent analysis. Letx∈Rn and let K be a nonempty closed convex set in Rn. A point y0∈K is said to be the orthogonal projection of x onto K if it is the closest point to x in K; that is,
(3)y0=argmin{∥y-x∥∣y∈K},
and denote y0 by PK(x). The well-known properties of the projection operator are as follows.Lemma 1 (see [16]).
LetK be a nonempty, closed, and convex subset in Rn. Then, for any x,y∈Rn and z∈K, the following statements hold:(i)
〈PK(x)-x,z-PK(x)〉≥0,(ii)
∥PK(x)-PK(y)∥2≤∥x-y∥2-∥PK(x)-x+y-PK(y)∥2,(iii)
∥PK(x)-z∥2≤∥x-z∥2-∥PK(x)-x∥2,(iv)
〈z-x,z-PK(x)〉≥∥z-PK(x)∥2.Remark 2.
In fact, (i) in Lemma1 also provides a sufficient condition for a vector u to be the projection of the vector x;  that is,  u=PK(x) if and only if
(4)〈u-x,z-u〉≥0,∀z∈K.Lemma 3.
LetK be a nonempty, closed, and convex subset in Rn. For any x,d∈Rn and α≥0, define
(5)x(α)=PK(x-αd).
Then, 〈d,x-x(α)〉 is nondecreasing for α>0.Lemma 4.
LetK be a nonempty closed and convex subset in Rn. For any x,d∈Rn and α≥0, define
(6)φ(α)=min{∥y-x+αd∥2∣y∈K}.
Then,
(7)φ′(α)=2〈d,x(α)-x+αd〉.Definition 5.
LetK be a nonempty subset of Rn. The multivalued mapping F:K→2Rn is said to be(i)
monotone if and only if(8)〈u-v,x-y〉≥0,∀x,y∈K,u∈F(x),v∈F(y),(ii)
pseudomonotone if and only if, for anyx,y∈K,u∈F(x),v∈F(y),
(9)〈u,y-x〉≥0⟹〈v,y-x〉≥0.
To proceed, we need the following definition for a multivalued mappingF.Definition 6.
LetK be a nonempty, closed, and convex subset of Rn. A multivalued mapping F:K→2Rn is said to be(i)
upper semicontinuous atx∈K if, for every open set V containing F(x), there is an open set U containing x such that F(y)⊂V for all y∈K∩U;(ii)
lower semicontinuous atx∈K if, given any sequence xk converging to x and any y∈F(x), there exists a sequence yk∈F(xk) that converges to y;(iii)
continuous atx∈K if it is both upper semicontinuous and lower semicontinuous at x.To end this section, we state the assumptions needed in the subsequent analysis.Assumption 7.
LetX be a nonempty, closed, and convex subset of Rn. And we assume(i)
X* is nonempty;(ii)
the multivalued mappingF:X→2Rn is pseudomonotone and continuous on X with compact convex values.


## 3. Main Results

For anyx∈Rn and ξ∈F(x), set
(10)r(x,ξ)=x-PX(x-ξ).
Then the projection residue r(x,ξ) can verify the solution set of the GVI [17].Proposition 8.
Letx∈X and ξ∈F(x). Then (x,ξ) solves the problem (1) if and only if
(11)x=PX(x-ξ).The basic idea of the designed algorithm is as follows. At each step of the algorithm, compute the projection residuer(xk,ξk) at iterate xk. If r(xk,ξk)=0, then stop with xk being a solution of the GVI; otherwise, find a trial point yk by a back-tracking search at xk along the residue r(xk,ξk), and the new iterate is obtained by using a projection. Repeat this process until the projection residue is a zero vector.Now, we describe carefully our algorithmic framework for solving GVI.Algorithm 9.
Chooseσ,γ∈(0,1),  x0∈X,  k=0.Step 1.
Given the current iteratexk, if ∥r(xk,ξk)∥=0 for some ξk∈F(xk), stop; else take any ξk∈F(xk) and compute
(12)zk=PX(xk-ξk).
Let
(13)yk=(1-ηk)xk+ηkzk,
where ηk=γmk, with mk being the smallest nonnegative integer m satisfying: ∃ζk∈F(xk-γmr(xk,ξk)) such that
(14)〈ζk,r(xk,ξk)〉≥σ∥r(xk,ξk)∥2.Step 2.
Letxk+1=PX(xk-αkζk), where ζk is chosen as in (14) and αk is chosen such that
(15)αk≥〈ζk,xk-yk〉∥ζk∥2,(16)〈ζk,PX(xk-αkζk)-yk〉≥0.Step 3.
Setk=k+1 and go to Step 1.First, we give a conclusion which addresses the feasibility of the stepsize rule (14), that is, the existence of point ζk.Lemma 10.
Ifxk is not a solution of the problem (1), then there exists the smallest nonnegative integer m satisfying (14) under Assumption 7.Proof.
By the definition ofr(xk,ξk) and Lemma 1, it follows that
(17)〈PX(xk-ξk)-(xk-ξk),xk-PX(xk-ξk)〉≥0,
which implies
(18)〈ξk,r(xk,ξk)〉≥∥r(xk,ξk)∥2>0.
Since γ∈(0,1), we get
(19)limm→∞(xk-γmr(xk,ξk))=xk.
Combining this with the fact that F is lower semicontinuous, we know that there exists ζm∈F(xk-γmr(xk,ξk)) such that
(20)limm→∞ζm=ξk.
Hence, by (18), one has
(21)(22)limm→∞〈ζm,r(xk,ξk)〉=〈ξk,r(xk,ξk)〉≥∥r(xk,ξk)∥2>0.
This completes the proof.Now, for the sake of convenience, we define(23)xk(α)=PX(xk-αζk),φk(α)=2α〈ζk,xk-yk〉+∥xk-αζk-xk(α)∥2-α2∥ζk∥2
for α≥0. Then, we have the following result.Lemma 11.
For the generated sequence{xk} in Algorithm 9, it holds that
(24)∥xk+1-x*∥2≤∥xk-x*∥2-φk(αk)
under Assumption 7, where x* is a point in X*.Proof.
By Lemma1 (iii) and the iterative process of Algorithm 9, we have
(25)∥xk+1-x*∥2≤∥xk-x*-αkζk∥2-∥xk-αkζk-xk+1∥2∥xk+1-hx*∥2≤∥xk-x*∥2+αk2∥ζk∥2-2αk〈ζk,xk-x*〉∥xk+1-hx*∥2-∥xk-αkζk-xk+1∥2.
Since x*∈X*, it follows that there exists ω*∈F(x*) such that
(26)〈ω*,yk-x*〉≥0.
Combining this and the fact that F is pseudomonotone, one has
(27)〈ζk,yk-x*〉≥0.
On the other hand,
(28)〈ζk,xk-x*〉=〈ζk,xk-yk〉+〈ζk,yk-x*〉.
By (27), we have
(29)-2αk〈ζk,xk-x*〉≤-2αk〈ζk,xk-yk〉.
It is obvious that
(30)∥xk+1-x*∥2≤∥xk-x*-αkζk∥2-∥xk-αkζk-xk+1∥2≤∥xk-x*∥2+αk2∥ζk∥2-2αk〈ζk,xk-x*〉-∥xk-αkζk-xk+1∥2≤∥xk-x*∥2+αk2∥ζk∥2-2αk〈ζk,xk-yk〉-∥xk-αkζk-xk+1∥2.
So, by the definition of φk, we obtain
(31)∥xk+1-x*∥2≤∥xk-x*∥2-φk(αk),
and the proof is completed.To prove the existence ofαk in Step 2 of Algorithm 9, we first consider the following optimization problem:
(32)max{φk(α)∣α≥0},
which is very necessary for the feasibility proof of αk. By Lemma 4 and the definition of φk(α), it follows that
(33)φk′(α)=2〈ζk,xk-yk〉+2〈ζk,xk(α)-xk+αζk〉-2α∥ζk∥2=2〈ζk,xk-yk〉+2〈ζk,xk(α)-xk〉=2〈ζk,PX(xk-αζk)-yk〉.
Note that φk(0)=0 and
(34)φk′(0)=2〈ζk,xk-yk〉=2ηk〈ζk,r(xk,ξk)〉≥2σηk∥r(xk,ξk)∥2>0,
where the first inequality follows from (14). Then
(35)max{φk(α)∣α≥0}>0
if the maximal value exists. By Lemma 3, we know that φk′(α) is nonincreasing and continuous for α≥0. So if φk′(α)=0 is solvable on (0,+∞), then its solution coincides with the solution to the optimization problem
(36)max{φk(α)∣α≥0}.
Next, from a geometric point of view, we will show that the equation φk′(α)=0 is solvable on (0,+∞).Lemma 12.
Ifxk is not a solution of the problem (1), then equation φk′(α)=0 is solvable for α≥0 under the Assumption 7.Proof.
For the sake of simplicity, we first define halfspaces as follows:(37)Hk1={x∈Rn∣〈ζk,x-yk〉<0},Hk2={x∈Rn∣〈ζk,x-yk〉>0},Hk3={x∈Rn∣〈ζk,x-yk〉=0},
where ζk is the same as in (14).
Sincexk∉X*, by the iterative process of Algorithm 9, one has
(38)〈ζk,zk-yk〉=(1-ηk)〈ζk,zk-xk〉≤-(1-ηk)σ∥r(xk,ξk)∥2<0,
and since
(39)〈ζk,xk-yk〉=ηk〈ζk,r(xk,ξk)〉≥ηkσ∥r(xk,ξk)∥2>0,
we know that Hk1∩X,  Hk2∩X, and  Hk3∩X are all nonempty convex sets, respectively. Let
(40)αk1=〈ζk,xk-yk〉∥ζk∥2.
It is obvious that
(41)〈ζk,xk-αk1ζk-yk〉=0.
By the fact that 〈ζk,xk-αζk-yk〉 is nonincreasing for α>0, we have
(42)〈ζk,xk-αζk-yk〉<0,
for α>αk1.
Now, letQ be any point in Hk1∩X and let P be any point in Hk2∩X. In the triangle composed by the points Q,P, and O(α)=xk-αζk, we denote the inner corners at points Q and P by βQ and βP, respectively. By geometric consideration, if α>αk1 is sufficiently large, we obtain
(43)βP<βQ,∥O(α)Q∥<∥O(α)P∥.
By the arbitrariness of P∈Hk2∩X and the definition of projection, there exists αk′>αk1 satisfying
(44)PX(xk-αk′ζk)∈Hk1.
On the other hand, by (39), it follows that
(45)〈ζk,PX(xk-0ζk)-yk〉=〈ζk,xk-yk〉>0,
which implies that PX(xk-0ζk)∈Hk2. Then, by the continuity of the projection operator, there exists αk2∈(0,αk′) such that
(46)xk(αk2)=PX(xk-αk2ζk)∈Hk3∩X,
which means that
(47)〈ζk,PX(xk-αk2ζk)-yk〉=0.
So φk′(αk2)=0, and the desired result follows.In order to maintain consistency in the sequel, we denote the smallest positive solution to the equationφk′(α)=0 by αk2. Then, αk2 is the smallest positive solution to
(48)max{φk(α)∣α≥0}.Lemma 13.
Takeαk=αk2 in Algorithm 9; then αk satisfies (15) and (16) under Assumption 7.Proof.
By the proof of Lemma12, it is obvious that (16) holds. On the other hand, since φk′(αk2)=0 and
(49)φk′(α)=2〈ζk,xk-yk〉+2〈ζk,xk(α)-xk〉,
one has
(50)〈ζk,xk-yk〉=〈ζk,xk-xk(αk2)〉>0,
where the last inequality follows from (39). By the fact that the projection operator is nonexpansive, we have
(51)〈ζk,xk-yk〉=〈ζk,xk-xk(αk2)〉=〈ζk,xk-PX(xk-αk2ζk)〉≤∥ζk∥∥xk-PX(xk-αk2ζk)∥≤αk2∥ζk∥2,
which implies
(52)αk2≥〈ζk,xk-yk〉∥ζk∥2=αk1,
and (15) holds. The desired result follows.Sinceφk′(α)>0 for all α∈[0,αk2), we know that (15) and (16) hold for any αk∈[αk1,αk2]. That is to say, we can take αk∈[αk1,αk2] in Algorithm 9, which shows the feasibility and flexibility of the method. Of course, by Lemma 11, we know that αk=αk2 in Algorithm 9 is a better stepsize in the sense that the distance between the next iterate point and X* has a large decrease at each iteration, which shows theoretically the superiority of the method.Theorem 14.
Suppose Assumption7 holds. If Algorithm 9 generates an infinite sequence {xk}, then it converges to a solution of GVI and
(53)limk→∞∥r(xk,ξk)∥=0.Proof.
For each iterative process, by the stepsize rule, we have(54)φk(αk)≥φk(αk1).
Combining this and Lemma 11 one has
(55)∥xk+1-x*∥2≤∥xk-x*∥2-φk(αk)≤∥xk-x*∥2-φk(αk1)=∥xk-x*∥2+(αk1)2∥ζk∥2-2αk1〈ζk,xk-yk〉-∥xk-xk(αk1)-αk1ζk∥2=∥xk-x*∥2+〈ζk,xk-yk〉2∥ζk∥2-2〈ζk,xk-yk〉2∥ζk∥2-∥xk-xk(αk1)-αk1ζk∥2=∥xk-x*∥2-(αk1)2∥ζk∥2-∥xk-xk(αk1)-αk1ζk∥2≤∥xk-x*∥2-(αk1)2∥ζk∥2,
where x* is chosen from X*. Hence, the sequence {∥xk-x*∥} is nonincreasing and {∥xk-x*∥} is bounded. Then, it follows that
(56)limk→∞(αk1∥ζk∥)=0,
from which we obtain
(57)limk→∞〈ζk,xk-yk〉∥ζk∥=0.
Since F is continuous with compact values, Proposition  3.11 in [18] implies that {F(yk):k∈N} is a bounded set, and so the sequence {ζk:ζk∈F(yk)} is bounded. Hence
(58)limk→∞〈ζk,xk-yk〉=0.
By the iterative process of Algorithm 9 and since
(59)〈ζk,xk-yk〉≥ηkσ∥r(xk,ξk)∥2,
we have
(60)limk→∞(ηkσ∥r(xk,ξk)∥2)=0.
Without loss of generality, if limk→∞ηk≠0, by (60), one has
(61)limk→∞r(xk,ξk)=0,
and the desired result can be obtained.
On the other hand, supposelimk→∞ηk=0. By the fact that {∥xk∥} is bounded, so it has a convergent subsequence xkj, and the limit is denoted by x-; that is,
(62)limj→∞xkj=x-.
Therefore,
(63)ykj=(1-ηkj)xkj+ηkjzkj=xkj-ηkjr(xkj,ξkj)⟶x-,asj⟶∞.
Since F is continuous on X, so for all ξ∈F(x-) we know that there exist ξkj∈F(xkj) such that
(64)limj→∞ξkj=ξ,
and there exist ζkj∈F(xkj-(ηkj/γ)r(xkj,ξkj)) such that
(65)limj→∞ζkj=ξ.
Observing the definition of ηkj and ζkj∈F(xkj-(ηkj/γ)r(xkj,ξkj)), it implies that
(66)〈ζkj,r(xkj,ξkj)〉<σ∥r(xkj,ξkj)∥2.
Let j→∞ in (66), and we obtain
(67)〈ξ,r(x-,ξ)〉<σ∥r(x-,ξ)∥2.
By Lemma 1 (iv), it follows that
(68)〈ξ,r(x-,ξ)〉=〈x--(x--ξ),x--PX(x--ξ)〉≥∥x--PX(x--ξ)∥2=∥r(x-,ξ)∥2.
Combining this with (67) we have
(69)r(x-,ξ)=0,
which implies that x-∈X*. By the fact that {∥xkj-x-∥} converges to zero and the whole sequence {∥xk-x-∥} is nonincreasing, we obtain that limk→∞∥xk-x-∥=0; that is, limk→∞xk=x-. And the desired result holds.The study of the following results is in the spirit of convergence rate results in [19, 20] in Rn, which are based on error bounds. The research on error bounds is a large topic in mathematical programming. One can refer to the surveys [21] for some sufficient conditions ensuring the existence of error bounds and for the roles played by error bounds in the convergence analysis of iterative algorithms.Now, we first give the definition of Lipschitz continuous for a multivalued mapping.Definition 15.
A multivalued mappingF:X→2Rn is said to be Lipschitz continuous if there exists a constant L>0 such that
(70)H(F(x),F(y))≤L∥x-y∥,∀x,y∈Rn,
where H(·,·) is the Hausdorff metric on closed bounded subsets of Rn defined by
(71)H(A,B)=max{supu∈Adist(u,B),supv∈Bdist(v,A)}.
The convergence rate of projection methods for GVI has been considered by many researchers [20, 22], and the following assumption is needed.Assumption 16.
Assume there are two positive constantsμ and δ satisfying
(72)d(x,X*)≤μ∥r(x,ξ)∥,∀xwith∥r(x,ξ)∥≤δ,
where ξ∈F(x) and d(x,X*) denotes l2-norm distance from x to X*.Theorem 17.
Let Assumptions7 and 16 hold, and suppose the multivalued mapping F is Lipschitz continuous with constant L. For the generated sequence {xk}, the following statements hold:(i)
there is a constantτ>0 such that, for all sufficiently large k,
(73)d(x,X*)≤τk+1;(ii)
asX=Rn, then
(74)∥xk+1-x*∥2≤[1-σ2L2μ2(1+μ)2]∥xk-x*∥2,which means the sequence {xk} converges R-linearly to a solution of GVI.Proof.
(i) By the proof of Theorem14, we know that there exists a positive constant M such that
(75)∥ζk∥2≤M,∀k.
From the fact that ηk≤1 for all k and the proof of Theorem 14, we have
(76)∥xk+1-x*∥2≤∥xk-x*∥2-(αk1)2∥ζk∥2=∥xk-x*∥2-〈ζk,xk-yk〉2∥ζk∥2≤∥xk-x*∥2-σ2M∥r(xk,ξk)∥4.
Since
(77)∥r(xk,ξk)∥⟶0,ask⟶∞,
one has
(78)∥r(xk,ξk)∥≤δ,∀ksufficientlylarge.
Choosing x*∈X* such that
(79)d(xk,X*)=∥xk-x*∥,
we obtain
(80)d(xk+1,X*)≤∥xk+1-x*∥2≤∥xk-x*∥2-σ2M∥r(xk,ξk)∥4≤∥xk-x*∥2-σ2μ4M∥xk-x*∥4=d(xk,X*)2-σ2μ4Md(xk,X*)4,
where the third inequality follows from Assumption 16. By Lemma 6 in Chapter 2 of [16], there exists a positive constant τ such that
(81)d(x,X*)≤τk+1,
for all k sufficiently large.
(ii) IfX=Rn, then the problem GVI reduces to the situation such that
(82)∃x∈Rn,0∈F(x).
Choosing x*∈X* such that
(83)d(xk,X*)=∥xk-x*∥
and by the fact that F is Lipschitz continuous, we know that
(84)∥ζk∥=∥ζk-0∥≤L∥yk-x*∥=L∥(1-ηk)xk+ηkzk-x*∥=L∥(xk-x*)-ηkr(xk,ξk)∥≤L(1+μ)∥r(xk,ξk)∥.
Hence,
(85)∥xk+1-x*∥2≤∥xk-x*∥2-(αk1)2∥ζk∥2=∥xk-x*∥2-〈ζk,xk-yk〉2∥ζk∥2≤∥xk-x*∥2-σ2L2(1+μ)2∥r(xk,ξk)∥2≤∥xk-x*∥2-σ2L2μ2(1+μ)2∥xk-x*∥2=[1-σ2L2μ2(1+μ)2]∥xk-x*∥2,
and it is obvious that {xk} converges R-linearly to x*.


## 4. Discussion

Certainly, the proposed extragradient method for GVI in this paper has a good theoretical property in theory, as the generated sequence not only requires two projections at each iteration but also take different stepsize rules. Moreover, from a geometric point of view, it is shown that the new method has a long stepsize, and it guarantees that the distance from the next iterative point to the solution set has a large decrease. However, the proposed algorithm is not easy to be realized in practice as the residue and the trial point are not easy to execute. This is an interesting topic for further research.



---

*Source: 727892-2013-09-30.xml*