# New Double Projection Algorithm for Solving Variational Inequalities

Authors: Lian Zheng
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

We propose a class of new double projection algorithms for solving variational inequality problem, which can be viewed as a framework of the method of Solodov and Svaiter by adopting a class of new hyperplanes. By the separation property of hyperplane, our method is proved to be globally convergent under very mild assumptions. In addition, we propose a modified version of our algorithm that finds a solution of variational inequality which is also a fixed point of a given nonexpansive mapping. If, in addition, a certain local error bound holds, we analyze the convergence rate of the iterative sequence. Numerical experiments prove that our algorithms are efficient.


---

## Body

## 1. Introduction

We consider the following variational inequality problem, denoted by VI(C,f), to find a vector x*∈C such that
(1)〈f(x*),y-x*〉≥0,∀y∈C,
where C is a nonempty closed convex set in ℝn, f is a continuous mapping from ℝn into itself, and 〈·,·〉 denotes the usual inner product in ℝn. Let SOL(C,f) denote the solution set of VI(C,f), and let ΠC denote the projection onto C. Throughout this paper, we assume that SOL(C,f) is nonempty and f has the property that
(2)〈f(y),y-x*〉≥0,∀y∈Candallx*∈SOL(C,f).
The property (2) holds if f is monotone or more generally pseudomonotone on C in the sense of Karamardian [1].The variational inequality problems have wide applications in reality. In recent years, many numerical algorithms for VI(C,f) have been proposed. These methods include Newton method, proximal algorithm, projection algorithm, and their variants; see [2, 3]. Among these methods, projection-type method is a simple and an efficient one; the oldest algorithm of this class is the extragradient projection method introduced in [4] and later refined and extended in [5–7].In 1999, Solodov and Svaiter [8] proposed a hyperplane projection algorithm for solving the VI(C,f) in Euclidean space, known also as the double projection algorithm due to the fact that one needs to implement double projections in each iteration. One is onto the feasible set C, and the other is onto the intersection of the feasible set C and the half-space. More precisely, they presented the following algorithm.Algorithm 1.
Choose an intial pointx0, parameters μ>0, σ,γ∈(0,1) and set k=0.
Step  1. Having xk, compute
(3)zk=ΠC[xk-μf(xk)].
Stop ifxk=zk; otherwise, go to Step 2.
Step  2. Compute yk=xk-ηk(xk-zk), where ηk=γmk with mk being the smallest nonnegative integer m such that
(4)〈f(xk-γm(xk-zk)),xk-zk〉≥σ∥xk-zk∥2.
Step  3. Compute
(5)xk+1=ΠC∩Hk(xk),
where
(6)Hk={x∈ℝn∣〈f(yk),x-yk〉≤0}.Letk∶=k+1, and return to Step 1.Wang et al. [9] shows that Algorithm 1 can get a longer step size, and hence it is a better algorithm than the extragradient method proposed by Korpelevich [7] in theory. The convergence rate of the iterative sequence generated by the hyperplane projection method depends mainly on the choice of hyperplane and projection way. We note that the hyperplane of Algorithm 1 is constructed by f(yk). In 2006, He [10] constructed a new hyperplane by a linear combination of f(yk) and xk-zk and hence modified the Algorithm 1.Inspired by the above, in this paper, we construct a class of new hyperplanes by a linear combination off(yk), xk-zk and f(xk) and hence present a class of new double projection algorithms. Using the proof method proposed by He in [10], our algorithms are proved to be globally convergent under continuous and pseudomonotone. Numerical experiments show that constructing hyperplane by f(xk) has a certain significance to change the convergence rate of the iterative sequence. In addition, we propose a modified version of our algorithm that find a solution of variational inequality which is also a fixed point of a given nonexpansive mapping.The organization of this paper is as follows. In the next section, we give some preliminaries. The details of the double projection algorithm are presented, and its global convergence analysis is proved in Section3. The modified double projection algorithm and its convergence analysis are in Section 4. Numerical results are reported in Section 5. Finally, conclusions together with some further studies are summarized in the last section.


## 2. Preliminaries

Letμ>0 be a parameter. The natural residual function rμ(·) is defined by
(7)rμ(x)∶=x-ΠC(x-μf(x)).A well-known fact is thatx* is a solution of VI(C,f) if and only if x* is a root of rμ(·).Lemma 2.
LetC⊂ℝn be a closed convex set. Then, it holds that(1)
〈y-ΠC(y),x-ΠC(y)〉≤0,∀x∈C,y∈ℝn,(2)
∥x-ΠC(y)∥2≤∥x-y∥2-∥y-ΠC(y)∥2,∀x∈C,y∈ℝn.By Lemma 2  (1), it is easy to prove that
(8)〈f(x),rμ(x)〉≥μ-1∥rμ(x)∥2.Lemma 3.
For everyx∈C, x*∈SOL(C,f), and η∈[0,1], one has
(9)〈x-x*,f(x-ηrμ(x))〉≥η〈rμ(x),f(x-ηrμ(x))〉.Proof.
Sincex*∈SOL(C,f), by property (2),
(10)〈f(y),y-x*〉≥0,∀y∈C.
In inequality (10), substitute y with x-ηrμ(x), and we obtain the desired result.Lemma 4.
LetC be a closed convex set in ℝn, h be a real-valued function on ℝn, and K be the set {x∈C:h(x)≤0}. If K is nonempty and h is Lipschitz continuous on C with modulus θ>0, then
(11)dist(x,K)≥θ-1max{h(x),0},∀x∈C,
where dist(x,K) denotes the distance from x to K.Proof.
See [10, Lemma 2.3].Lemma 5.
Let{αk} be a real sequence satisfying 0<a≤αk≤b<1 for all k, and let {νk} and {ωk} be two sequences in Rn such that for some θ≥0,
(12)limsupk→∞∥νk∥≤θ,limsupk→∞∥ωk∥≤θ,limk→∞∥αkνk+(1-αk)ωk∥=θ.
Then,
(13)limk→∞∥νk-ωk∥=0.Proof.
See [11, Lemma 3.1].


## 3. The Double Projection Algorithm and Convergence Analysis

Algorithm 6.
Selectx0∈C, α,β≥0, σ>0, μ∈(0,σ-1), γ∈(0,1), ω≥α. Set k=0.Step  1. For xk∈C, define
(14)zk=ΠC(xk-μf(xk)).Computerμ(xk). If rμ(xk)=0, stop; else go to Step 2.Step  2. Compute yk=xk-ηkrμ(xk), where ηk=γmk with mk being the smallest nonnegative integer m satisfying
(15)〈f(xk)-f(xk-γmrμ(xk)),rμ(xk)〉≤σ∥rμ(xk)∥2.Step  3. Compute xk+1=ΠCk(xk), where Ck=C∩Hk with Hk={v∈ℝn:hk(v)≤0} being a halfspace defined by the function
(16)hk(v)=〈dk,v-xk〉+ωηk(1-μσ)∥rμ(xk)∥2,
where normal vector dk=αηkrμ(xk)+βf(xk)+ωμf(yk).Letk=k+1, and return to Step 1.Remark 7.
In Algorithm6, the searching direction is taken as
(17)-dk=-(αηkrμ(xk)+βf(xk)+ωμf(yk)),
which is a linear combination set of rμ(xk), f(xk) with f(yk). When taking α=1, β=0, ω=μ-1, -dk degrade into the direction introduced by He [10]; when taking α=β=1, ω=μ-1, -dk degrade into the direction introduced by Noor et al. [12]; when taking α=1/ηk, β=0, ω=1/μηk, -dk degrade into the direction introduced by Wang et al. [13]; when taking α=β=0, ω=μ-1, -dk degrade into the direction introduced by Iusem and Svaiter [7], Solodov and Svaiter [8], and wang et al. [9], which shows that our direction is a framework of the ones of the above projection methods.Lemma 8.
Letx*∈SOL(C,f), and let the function hk be defined by (16). Then,
(18)hk(xk)≥ωηk(1-μσ)∥rμ(xk)∥2,hk(x*)≤0.
In particular, if rμ(xk)≠0, then hk(xk)>0.Proof.
Consider that(19)hk(xk)=〈dk,xk-xk〉+ωηk(1-μσ)∥rμ(xk)∥2=ωηk(1-μσ)∥rμ(xk)∥2.
If rμ(xk)≠0, then hk(xk)>0 because μσ<1. Next, we prove that hk(x*)≤0. Since
(20)zk=ΠC(xk-μf(xk)),
by (1) of Lemma 2, we have
(21)〈xk-zk-μf(xk),zk-x*〉≥0.
By property (2),
(22)〈μf(xk),xk-x*〉≥0.
Adding inequalities (21) and (22), we obtain
(23)〈xk-zk-μf(xk),zk-xk〉+〈xk-zk,xk-x*〉≥0.
We have
(24)〈xk-x*,dk〉=〈xk-x*,αηkrμ(xk)+βf(xk)+ωμf(yk)〉=αηk〈xk-x*,xk-zk〉+β〈f(xk),xk-x*〉=+ωμ〈f(yk),xk-x*〉≥αηk〈rμ(xk)-μf(xk),rμ(xk)〉=+ωμηk〈f(yk),rμ(xk)〉=αηk∥rμ(xk)∥2-αμηk〈f(xk)-f(yk),rμ(xk)〉=+(ω-α)μηk〈f(yk),rμ(xk)〉≥αηk∥rμ(xk)∥2-αμσηk∥rμ(xk)∥2=+(ω-α)μηk(μ-1-σ)∥rμ(xk)∥2=ηkω(1-μσ)∥rμ(xk)∥2,
where the first inequality follows from (2), (9), and (23) and the last one follows (8) and (15).
It follows that(25)hk(x*)=〈dk,x*-xk〉+ηkω(1-μσ)∥rμ(xk)∥2=-〈dk,xk-x*〉+ηkω(1-μσ)∥rμ(xk)∥2≤-ηkω(1-μσ)∥rμ(xk)∥2+ηkω(1-μσ)∥rμ(xk)∥2=0.
The proof is completed.Now, we turn to consider the convergence of Algorithm6. Certainly, if Algorithm 6 terminates at Step  k, then xk is a solution of VI(C,f). Therefore, in the following analysis, we assume that Algorithm 6 always generates an infinite sequence.Theorem 9.
IfC is a nonempty closed and convex set in ℝn and the property (2) holds, then the sequence {xk}⊂ℝn generated by Algorithm 6 is bounded and limk→∞dist(xk,Ck)=0.Proof.
Letx*∈SOL(C,f). Since
(26)xk+1=ΠCk(xk),
it follows from Lemma 2(2) that
(27)∥xk+1-x*∥2≤∥xk-x*∥2-∥xk+1-xk∥2=∥xk-x*∥2-dist2(xk,Ck).
It follows that the sequence {∥xk+1-x*∥2} is nonincreasing, and hence it is a convergent sequence. Therefore, {xk} is bounded and limk→∞dist(xk,Ck)=0. The proof is completed.Theorem 10.
IfC is a nonempty closed and convex set in ℝn, f is a continuous mapping from ℝn into itself, and the property (2) holds, then Algorithm 6 generates an infinite sequence {xk} converging to a solution of  VI(C,f).Proof.
By Theorem9, the sequence {xk} is bounded. Since f and projection operator are continuous, we have the sequence {zk}, and hence the sequence {yk} is bounded. Thus, {f(xk)}, {f(zk)}, and {rμ(xk)} are bounded sequences; that is, there exists some M>0, such that
(28)∥dk∥=∥αηkrμ(xk)+βf(xk)+ωμf(yk)∥≤M,∀k.
Clearly each function hk is Lipschitz continuous on C with modulus M. By Lemmas 8 and 4, we obtain that
(29)dist(xk,Ck)≥M-1hk(xk)≥M-1ωηk(1-μσ)∥rμ(xk)∥2.
Thus, by Theorem 9, we have
(30)limk→∞ηk∥rμ(xk)∥2=0,
which implies that there exist subsequences {xki} and {xkj} of {xk}, respectively, such that
(31)limi→∞∥rμ(xki)∥=0,orlimj→∞ηkj=0.
Suppose thatlimi→∞∥rμ(xki)∥ = 0. Since rμ(·) is continuous and {xki} is a bounded sequence, there exists an accumulation point x- of {xki} such that rμ(x-)=0, which implies that x- solves the VI(C,f). Replacing x* by x- in (27), we obtain that the sequence {∥xk-x-∥} is also nonincreasing and hence converges. Since x- is an accumulation point of {xki}, some subsequence of {∥xki-x-∥} converges to zero. This shows that the whole sequence {∥xk-x-∥} converges to zero, and hence limk→∞xk=x-.
Iflimj→∞ηkj=0, by the search procedure (15), we have
(32)〈f(xkj)-f(xkj-ηkjγ-1rμ(xkj)),rμ(xkj)〉>σ∥rμ(xkj)∥2.
Since f and 〈·,·〉 are continuous, we obtain by letting j→∞ that limj→∞∥rμ(xkj)∥=0. Similar discussion obtains the desired result.


## 4. The Modified Double Projection Algorithm and Convergence Analysis

In this section, we present the modified double projection algorithm which finds a solution of the VI(C,f) which is also a fixed point of a given nonexpansive mapping. Let S:Rn→Rn be a nonexpansive mapping, and denote by Fix(S) its fixed point set; that is,
(33)Fix(S)={x∈Rn∣S(x)=x}.
Let {αk}k=0∞⊂[c,d] for some c,d∈(0,1).Algorithm 11.
Selectx0∈C, α,β≥0, σ>0, μ∈(0,σ-1), γ∈(0,1), ω≥α. Set k=0.Step  1. Compute rμ(xk) and yk=xk-ηkrμ(xk), where ηk=γmk with mk being the smallest nonnegative integer m satisfying the line search (15).Step  2. Compute
(34)xk+1=αkxk+(1-αk)SΠCk(xk),
where Ck=C∩Hk with Hk={v∈ℝn:hk(v)≤0} being a halfspace defined by the function  (16).Letk∶=k+1, and return to Step 1.We, next, establish a convergence theorem for Algorithm11. We assume that the following condition holds. 						(35)Fix(S)∩SOL(C,f)≠∅.We also recall that inRn,
(36)∥λx+(1-λ)y∥2=λ∥x∥2+(1-λ)∥y∥2-λ(1-λ)∥x-y∥2,
for all x,y∈Rn and λ∈[0,1].Theorem 12.
Suppose that the assumptions of Theorem10 hold, then any sequence {xk} generalized by Algorithm 11 converges to some point of Fix(S)∩SOL(C,f).Proof.
Denotetk=ΠCk(xk) for all k≥0. Let u∈Fix(S)∩SOL(C,f). By the definition of xk+1, we obtain
(37)∥xk+1-u∥2=∥αkxk+(1-αk)S(tk)-u∥2=∥αk(xk-u)+(1-αk)(S(tk)-u)∥2(38)=αk∥xk-u∥2+(1-αk)∥S(tk)-u∥2z-αk(1-αk)∥xk-S(tk)∥2≤αk∥xk-u∥2+(1-αk)∥S(tk)-S(u)∥2≤αk∥xk-u∥2+(1-αk)∥tk-u∥2≤αk∥xk-u∥2+(1-αk)z×(∥xk-u∥2-∥tk-xk∥2)=∥xk-u∥2-(1-αk)∥tk-xk∥2(39)=∥xk-u∥2-(1-αk)dist2(xk,Ck),
where the third equality follows from (36), the second inequality follows from the nonexpansion of S, and the third inequality follows from Lemma 2(2). In (39), using the proof similar to those of Theorem 10, we obtain that {xk} converges to some solution x- of VI(C,f). It is now left to show that x-∈Fix(S). By (38), we obtain that {∥xk-u∥} is a convergent sequence; that is, there exists some θ>0, such that
(40)limk→∞∥xk-u∥=θ,(41)limk→∞∥xk-tk∥=0.
Since S is nonexpansive, we obtain
(42)∥S(tk)-u∥=∥S(tk)-S(u)∥≤∥tk-u∥≤∥xk-u∥,
which, together with (40), means that
(43)limsupk→∞∥S(tk)-u∥≤θ.
Furthermore,
(44)limk→∞∥αk(xk-u)+(1-αk)(S(tk)-u)∥=limk→∞∥αkxk+(1-αk)S(tk)-u∥=limk→∞∥xk+1-u∥=θ.
So applying Lemma 5, we obtain
(45)limk→∞∥S(tk)-xk∥=0.
Since
(46)∥S(xk)-xk∥=∥S(xk)-S(tk)+S(tk)-xk∥≤∥S(xk)-S(tk)∥+∥S(tk)-xk∥≤∥xk-tk∥+∥S(tk)-xk∥,
it follows from (41) and (45) that
(47)limk→∞∥S(xk)-xk∥=0.
Since S is nonexpansive on ℝn and xk converges to x-, we obtain that x--S(x-)=0, which means that x-∈Fix(S). Therefore, the sequence {xk} converges to x-∈Fix(S)∩SOL(C,f).Next, we provide a result on the convergence rate of the iterative sequence generated by Algorithm11. To establish this result, we need the following local error bound condition to hold.There exist two positive constantsc and δ such that
(48)dist(x,Fix(S)∩SOL(C,f))≤c∥rμ(xk)∥,∀xsatisfying∥rμ(x)∥≤δ.Theorem 13.
In addition to the assumptions of Theorem10, if f is Lipschitz continuous with modulus L>0 and the local error bound condition (48) holds, then there is a constant τ>0 such that for sufficiently large k,
(49)dist(xk,Fix(S)∩SOL(C,f))≤1τk+dist-2(x0,Fix(S)∩SOL(C,f)).Proof.
Setη:=min{1/3,L-1γσ}. We first prove that ηk>η for all k. By the definition of ηk, we obtain ηk∈(0,1]. If ηk=1, then ηk>η holds. Now, we assume that ηk<1. It follows from ηk=γmk that mk≥1. By the construction of ηk, we have
(50)〈f(xk)-f(xk-ηkγ-1rμ(xk)),rμ(xk)〉>σ∥rμ(xk)∥2.
From the Lipschitz continuity of f, we have
(51)σ∥rμ(xk)∥2<〈f(xk)-f(xk-ηkγ-1rμ(xk)),rμ(xk)〉≤Lγ-1ηk∥rμ(xk)∥2.
Thus, ηk>L-1γσ≥η.
Letu*∈ΠFix(S)∩SOL(C,f)(xk). By (29), (39), and (48), we obtain that for sufficiently large k,
(52)dist2(xk+1,Fix(S)∩SOL(C,f))≤∥xk+1-u*∥2≤∥xk-u*∥2-(1-αk)dist2(xk,Ck)≤∥xk-u*∥2-M-2ω2ηk2(1-μσ)2∥rμ(xk)∥4≤dist2(xk,Fix(S)∩SOL(C,f))-M-2ω2η2=.×(1-μσ)2c-4dist4(xk,Fix(S)∩SOL(C,f)).
Denote τ=M-2ω2η2(1-μσ)2c-4. Applying Lemma  6 in [14, Chapter 2], we have
(53)dist(xk,Fix(S)∩SOL(C,f))≤1τk+dist-2(x0,Fix(S)∩SOL(C,f)).


## 5. Numerical Experiments

In this section, we present some numerical experiments’ results to show the effectiveness of the proposed algorithm. The MATLAB codes are run on a notebook computer with Intel Core 2 CPU 2.10 GHZ and RAM 2.00 GM under MATLAB Version 7.0. We compare the performance of our Algorithm6, [10, Algorithm 2.1] and [8, Algorithm 2.2]. In all tables, we use Dim to mean the dimension of the problem, CPU to represent the CPU total runtime of the computer in seconds, and iter to mean the total iterative number of times. The tolerance ε means when ∥rμ(xk)∥≤ε, the procedure stops. We choose σ = 2.4, γ = 0.9, μ = 0.26, α = 0.04, β = 0.01, and ω = 5 for our Algorithm 6 in Tables 1 and 2, σ=2.4, γ=0.9, μ=0.32, α=0.04, β=0.001, and ω=5.3 as Algorithm 6 in Table 3; γ=0.5, σ=4, and μ=0.2 for Algorithm  2.1 in [10]; σ=0.3, θ=4, and γ=0.5 for Algorithm  2.2 in [8]. The choices of the parameters for the latter two algorithms are what the corresponding references proposed.Table 1
Example14: Numerical results for initial point x0=(1,1,…,1)T and ε=10-4.
Dim (n)
Algorithm6
[10, Algorithm 2.1]
[8, Algorithm 2.2]
iter
CPU
iter
CPU
iter
CPU
1
00
10
0.530
11
0.577
15
0.624
200
10
1.279
12
1.529
15
1.778
500
11
10.905
13
11.497
15
13.99
1000
12
66.63
13
75.04
17
104.08
2000
12
340.9
14
441.05
17
610.3Table 2
Example14: Numerical results for initial point x0=(0,0,…,0)T and ε=10-4.
Dim (n)
Algorithm6
[10, Algorithm 2.1]
[8, Algorithm 2.2]
iter
CPU
iter
CPU
iter
CPU
1
00
10
0.530
11
0.577
15
0.593
200
10
1.185
12
1.451
15
1.809
500
11
10.78
13
11.06
15
13.41
1000
12
65.69
13
74.16
17
101.4
2000
12
341.6
14
431.4
17
593.1Table 3
Examples15 and 16.
ε
Algorithm6
[10, Algorithm 2.1]
[8, Algorithm 2.2]
iter
CPU
iter
CPU
iter
CPU
Mathiesen
1
0
-
4
22
0.281
37
0.327
28
0.359
Harnash5
1
0
-
10
11
0.312
12
0.203
22
0.312
Harnash10
1
0
-
10
35
0.528
41
0.312
51
0.468Example 14.
Consider the affine variational inequality withC=[0,1]n and f(x)=Mx+d, where
(54)M=(4-20···0014-2···00014···00⋮000···4-2000···14),d=(-1-1⋮-1).
This problem was first tested in [15].From Tables1 and 2, we can see that our Algorithm 6 is more efficient than Algorithm  2.2 in [8] and Algorithm  2.1 in [10]. It can be observed that the number of iterations of our algorithm is much less than those of [8, 10], and the CPU time in our method is shorter than those of [8, 10]. In addition, for a set of similar problems, it seems that the number of iterations and the CPU time of the above three methods are not very sensitive to starting point. In fact, the initial points of the methods can be chosen randomly.Example 15.
The Kojima-Shindo nonlinear complementarity problem (NCP) (withn=4) was considered first in [16], where the function F(x) is defined by
(55)f(x1,x2,x3,x4)=(3x12+2x1x2+2x22+x3+3x4-62x12+x1+x22+10x3+2x4-23x12+x1x2+2x22+2x3+9x4-9x12+3x22+2x3+3x4-3).
Let the feasible set be the simplex C={x∈ℝ+n∣x1+x2+x3+x4=4}.Example 16.
The example comes from the problem of computing the Cournot-Nash equilibria ofN-firm noncooperative games. The defining mapping F:ℝn→ℝn is of the form
(56)fi(q)=ci(qi)-p(∑j=1nqj)-qip(∑j=1nqj),i=1,2,…,n,
where
(57)ci(qi)=αiqi+[βi1+βi]Li-1/βiqi1+1/βi,p(Q)=50001/γQ-1/γ,
with
(58)Q=∑j=1nqj.
The constants αi, Li, βi, and γ are positive scalars whose data are taken from [17] with n=5 and n=10.
In Table3, Mathiesen’s test problem is Example 15. We use x0=(1,1,1,1)T as the initial point. The test problem of Harnash5 and Harnash10 is Example 16 with n=5 and n=10, respectively.From Table3, we can see that the number of iterations of our algorithm is less than the ones of the methods in [8, 10]. In Mathiesen’s test problem, Table 3 shows that the CPU time in our algorithm is also shorter than those in [8, 10].Tables1, 2, and 3 show that constructing hyperplane by f(xk), has a certain significance to change the convergence rate of the iterative sequence.


## 6. Conclusion

In this paper, a class of double projection algorithms for solving pseudomonotone variational inequalities are proposed on the basis of the algorithms in [8, 10]. The global convergence of the proposed algorithms is proved under the condition that f is continuous and pseudomonotone. The numerical experiments’ results show that our algorithms are more efficient if the direction is chosen properly. How to choose a suitable direction for the different kind of variational inequalities problems would be an interesting topic in further research.In addition, in Algorithm6, the searching direction is taken as αηkrμ(xk)+βf(xk)+ωμf(yk), which is a linear combination of rμ(xk), f(xk) with f(yk). I wonder whether there exists an other combination for searching direction of projection method. This is also a topic for further research.



---

*Source: 714397-2013-06-09.xml*