Hindawi Publishing Corporation
Journal of Inequalities and Applications
Volume 2010, Article ID 657192, 20 pages
doi:10.1155/2010/657192
Research Article
A New Method for Solving Monotone Generalized
Variational Inequalities
Pham Ngoc Anh and Jong Kyu Kim
Department of Mathematics, Kyungnam University, Masan, Kyungnam 631-701, Republic of Korea
Correspondence should be addressed to Jong Kyu Kim, [email protected]
Received 11 May 2010; Revised 27 August 2010; Accepted 4 October 2010
Academic Editor: Siegfried Carl
Copyright q 2010 P. N. Anh and J. K. Kim. This is an open access article distributed under the
Creative Commons Attribution License, which permits unrestricted use, distribution, and
reproduction in any medium, provided the original work is properly cited.
We suggest new dual algorithms and iterative methods for solving monotone generalized
variational inequalities. Instead of working on the primal space, this method performs a dual
step on the dual space by using the dual gap function. Under the suitable conditions, we prove
the convergence of the proposed algorithms and estimate their complexity to reach an ε-solution.
Some preliminary computational results are reported.
1. Introduction
Let C be a convex subset of the real Euclidean space R
n
, F be a continuous mapping from C
into R
n
,andϕ be a lower semicontinuous convex function from C into R. We say that a point
x
∗
is a solution of the following generalized variational inequality if it satisfies
,x− y
∗
ϕ
x
− ϕ
y
∗
≥ 0, ∀x ∈ C. DGVI
In recent years, this generalized variational inequalities become an attractive field
for many researchers and have many important applications in electricity markets,
transportations, economics, and nonlinear analysis see 1–9.
2 Journal of Inequalities and Applications
It is well known that the interior quadratic and dual technique are powerfull tools for
analyzing and solving the optimization problems see 10–16. Recently these techniques
have been used to develop proximal iterative algorithm for variational inequalities see 17–
22.
In addition Nesterov 23 introduced a dual extrapolation method for solving
variational inequalities. Instead of working on the primal space, this method performs a dual
step on the dual space.
In this paper we extend results in 23 to the generalized variational inequality
problem GVI in the dual space. In the first approach, a gap function gx is constructed
such that gx ≥ 0, for all x
∗
∈ C and gx
∗
F
x
,x− y
≥ 0, ∀x, y ∈ C, 2.1
ii monotone on C if for each x, y ∈ C,
F
x
− F
y
,x− y
≥ 0, 2.2
iii strongly monotone on C with constant β>0 if for each x, y ∈ C,
F
x
− F
y
, ∀x, y ∈ C. 2.4
Note that when ϕ is differentiable on some open set containing C, then, since ϕ is lower
semicontinuous proper convex, the generalized variational inequality GVI is equivalent to
the following variational inequalities see 25, 26:
Journal of Inequalities and Applications 3
Find x
∗
∈ C such that
F
x
∗
∇ϕ
x
∗
,x− x
∗
≥0, ∀x ∈ C. 2.5
Throughout this paper, we assume that:
A
1
the interior set of C,intC is nonempty,
A
2
the set C is bounded,
A
3
y ∈ C :
y, z − x
≤ 0, ∀z ∈ C
, if x ∈ C,
∅, otherwise.
2.6
The dual gap function of problem GVI is defined as follows:
g
x
: sup
F
y
,x− y
ϕ
x
− ϕ
y
: max
F
y
,x− y
ϕ
x
− ϕ
y
| y ∈ C,
y −
x
≤ R
. 2.8
For the following consideration, we define B
R
x : {y ∈ R
n
0
∈ C such that g
R
x
0
0 and x
0
− x <R, and F is pseudomonotone,
then x
0
is a solution to DGVI (and also GVI).
Proof. i Note that Fy,x − y ϕx − ϕy is upper semicontinuous on C for x ∈ C
and B
R
x is bounded. Therefore, the supremum exists which means that g
R
is well-defined.
Moreover, since ϕ is convex on C and g is the supremum of a parametric family of convex
functions which depends on the parameter x, then g
R
is convex on C
ii By definition, it is easy to see that g
R
x ≥ 0 for all x ∈ C ∩ B
R
x.Letx
∗
be a
solution of DGVI and x
∗
− y
ϕ
y
− ϕ
x
∗
≤ 0 2.10
for all y ∈ C ∩ B
R
x.Thus
g
R
x
∗
sup
F
y
,x
∗
− y
0 means that x is a solution to DGVI
restricted to C ∩ int B
R
x. Since F is pseudomonotone, x
0
is also a solution to GVI restricted
to C ∩ B
R
x. Since x
0
∈ int B
R
x, for any y ∈ C, we can choose λ>0sufficiently small such
that
y
λ
: x
0
λ
y − x
0
∈ C ∩ B
R
x
, 2.12
0 ≤
λ
y − x
0
− x
0
ϕ
x
0
λ
y − x
0
− ϕ
x
0
≤ λ
F
x
0
,y− x
ϕ
y
− ϕ
x
0
,
2.13
where 2.13 follows from the convexity of ϕ·. Since λ>0, dividing this inequality b y λ,we
obtain that x
0
is a solution to GVI on C. Since F is pseudomonotone, x
0
is also a solution to
DGVI.
Journal of Inequalities and Applications 5
Let C ⊆ R
n
be a nonempty, closed convex set and x ∈ R
n
. Let us denote d
C
x the
Euclidean distance from x to C and Pr
C
x the point attained this distance, that is,
d
is a nonexpansive and co-coercive operator on C see 27, 28.
The following lemma gives a tool for the next discussion.
Lemma 2.4. For any x, y, z ∈ R
n
and for any β>0, the function d
C
and the mapping Pr
C
defined
by 2.14 satisfy
Pr
C
x
− x, y − Pr
C
x
≥ 0, ∀y ∈ C, 2.15
d
2
C
x y
≥ d
x − Pr
C
x
1
β
y
2
≤
1
β
2
y
2
− d
2
C
x
1
β
xy
2
2
v −
Pr
C
x
y
,Pr
C
x
− x
Pr
C
x − x
2
x − x
2
≥
v − Pr
C
xy
2
− 2
y, Pr
C
x
− x
Pr
C
x − x
2
.
2.18
C
x
− 2
y, Pr
C
x
− x
,
2.19
which proves 2.16.
6 Journal of Inequalities and Applications
From the definition of d
C
, we have
d
2
C
x
1
β
y
−
x
1
β
y − Pr
C
x
1
β
y
−
x − Pr
C
x
1
β
y
y
2
−
x − Pr
C
x
1
β
y
2
2
x
1
k0
⊂ C, a finite sequence of arbitrary points {w
k
}
m
k0
⊂ R
n
and a finite positive sequence
{λ
k
}
m
k0
⊆ 0, ∞.Letusdefine
w
m
m
k0
λ
k
w
k
, λ
m
m
x
k
− ∂ϕ
x
k
. 2.22
Then, for any β>0,
i max{w, y−
x|y ∈ C
R
}≤1/2βw
2
−β/2d
2
C
x1/βwβR
2
/2, for all x ∈ C,
w ∈ R
n
.
ii g
R
x
m
≤ 1/λ
m
maximizing problem max{w, y −
x|y ∈ C
R
}. Using duality theory in convex optimization,
then we have
max
w, y −
x
| y ∈ C
R
max
w, y −
x
| y ∈ C,
y −
x
2
≤ R
2
x
−
ρ
2
y −
x
2
ρ
2
R
2
min
ρ≥0
1
2ρ
max
y∈C
w
2
− β
2
min
y∈C
y −
x −
1
β
w
2
βR
2
2
1
2β
w
,x
k
− y
ϕ
x
k
− ϕ
y
≤−
m
k0
λ
k
F
x
k
,y− x
k
m
k0
λ
k
w
k
, x − x
k
w
m
,y− x
m
k0
λ
k
w
k
, x − x
k
.
max
F
y
,
1
λ
m
m
k0
λ
k
x
k
− y
ϕ
1
λ
m
m
k0
λ
k
x
k
− ϕ
y
| y ∈ C
R
1
λ
m
max
m
k0
λ
k
F
y
,x
k
w
m
,y− x
| y ∈ C
R
m
k0
λ
k
w
k
, x − x
k
≤
1
λ
m
1
2β
w
, x − x
k
.
2.26
3. Dual Algorithms
Now, we are going to build the dual interior proximal step for solving GVI. The main idea
is to construct a sequence {
x
k
} such that the sequence g
R
x
k
tends to 0 as k →∞.Byvirtue
of Lemma 2.5, w e can check whether
x
k
is an ε-solution to GVI or not.
The dual interior proximal step u
k
,x
k
, w
k
,w
k
at the iteration k ≥ 0 is generated by
using the following scheme:
u
k
βρ
k
2
y − u
k
2
| y ∈ C
,
w
k
: w
k−1
1
ρ
k
w
k
x
1
β
w
k
≥ d
2
C
x
1
β
w
k−1
x
k
− u
k
2
2
ρ
2
k
w
k
2
2
βρ
k
w
k
, x − x
k
1
β
w
k−1
,
3.2
1
β
w
k
− d
2
C
x
1
β
w
k−1
≥
2
βρ
k
w
k
, x − x
k
1
β
2
ξ
k
w
k
2
.
3.3
Journal of Inequalities and Applications 9
Proof. We replace x by x 1/βy and y by 1/βz into 2.16 to obtain
d
2
C
x
1
β
y z
≥ d
2
C
x
1
y
−
x
1
β
y
.
3.4
Using the inequality 3.4 with x
x, y w
k−1
, z 1/ρ
k
w
k
and noting that u
k
Pr
C
x
1/β
w
k−1
,weget
d
2
C
x
1
β
w
k−1
1
βρ
k
w
k
−
2
βρ
k
w
k
,Pr
C
x
1
β
w
k−1
−
2
C
u
k
1
βρ
k
w
k
−
2
βρ
k
w
k
,u
k
− x −
1
β
w
k−1
.
3.6
From the subdifferentiability of the convex function ϕ to scheme 3.1, using the first-order
u
k
−
1
βρ
k
ξ
k
,
3.8
where ξ
k
η
k
Fu
k
.
10 Journal of Inequalities and Applications
We apply inequality 3.4 with x u
k
, y −1/ρ
k
ξ
k
and z 1/ρ
k
ξ
k
d
2
C
x
k
1
βρ
k
ξ
k
w
k
−
2
βρ
k
ξ
k
w
k
,x
k
− u
k
ξ
k
2
d
2
C
x
k
1
βρ
k
ξ
k
w
k
−
2
βρ
k
ξ
2
d
2
C
x
k
1
βρ
k
ξ
k
w
k
2
βρ
k
ξ
k
w
k
ξ
k
2
2
βρ
k
ξ
k
,x
k
− u
k
d
2
C
x
k
1
βρ
Combine this inequality and 3.6,weget
d
2
C
x
1
β
w
k
≥ d
2
C
x
1
β
w
k−1
−
2
βρ
k
w
k
,u
k
2
2
βρ
k
ξ
k
,x
k
− u
k
d
2
C
x
k
1
βρ
k
ξ
k
w
x
k
1/βρ
k
ξ
k
w
k
, then it follows that
d
2
C
x
k
1
βρ
k
ξ
k
w
k
2
−
2
βρ
k
π
k
C
− x
k
,ξ
k
w
k
1
β
2
ρ
2
k
ξ
x
k
− u
k
2
π
k
C
− x
k
2
−
2
βρ
k
k
w
k
, x − x
k
1
β
w
k−1
,
3.12
which proves 3.2.
On the other hand, from 3.9 we have
d
2
C
u
k
1
βρ
k
w
k
≥
k
ξ
k
,x
k
− u
k
2
βρ
k
ξ
k
w
k
,u
k
−
1
βρ
k
ξ
k
− x
k
.
x
1
β
w
k−1
.
3.14
Step 2. Solve the strongly convex programming problem
min
F
u
k
,y− u
k
ϕ
y
β
2
. 3.16
Set
w
k
: w
k−1
w
k
.
Step 4. Compute
r
k
:
k
i0
w
i
,
x
− x
i
max
w
k
,y−
3
) are satisfied and F is L-Lipschitz continuous on
C. Then, one has
g
R
x
k
≤
βR
2
2
k 1
,
3.19
where
x
k
is the final output defined by the sequence u
k
,x
k
, w
k
,w
k
k
,π
k
C
− x
k
F
x
k
− F
u
k
,x
k
− π
k
C
≤
L
2
C
x
1
β
w
k
≥ d
2
C
x
1
β
w
k−1
1 −
L
βρ
k
x
k
w
k
2
2
βρ
k
w
k
, x − x
k
1
β
w
k−1
.
3.21
Using this inequality with ρ
i
1 for all i ≥ 0andβ ≥ L,weobtain
d
2
C
2
π
k
C
− x
k
2
1
β
2
w
k
2
w
k
2
2
β
w
k
, x − x
k
1
β
w
k−1
.
3.22
If we choose λ
i
1 for all i ≥ 0in2.21, then we have
w
k
k
i0
w
i
, x − x
i
1
2β
w
k
2
−
β
2
d
2
C
x
1
β
w
k
1
2β
w
k
2
−
β
2
d
2
C
x
1
β
w
k
βR
2
2
β
2
d
2
C
x
1
β
w
k
βR
2
2
≤
k−1
i0
w
i
, x − x
i
w
k
w
k−1
1
β
2
w
k
2
2
β
w
k
, x − x
k
1
β
w
k−1
1
β
w
k−1
βR
2
2
a
k−1
.
3.25
14 Journal of Inequalities and Applications
Note that a
−1
βR
2
/2. It follows from the inequalities 3.24 and 3.25 that
k 1
g
R
x
k
≤
βR
k
F
x
k
− F
u
k
sup
k
w
k
ξ
k
,
Step 2. Solve the strong convex programming problem
min
F
u
k
,y− u
k
ϕ
y
β
k
2
y − u
k
2
| y ∈ C
.
Journal of Inequalities and Applications 15
Step 4. Compute
r
k
:
k
i0
w
i
,
x
− x
i
max
w
k
,y−
x
|y ∈ C
R
.
3.31
If r
k
≤ k 1ε, where ε>0 is a given tolerance, then stop.
k
,w
k
be generated
by Algorithm 3.4. Suppose that the sequences Fx
k
and Fu
k
are uniformly bounded by 3.27.
Then, we have
g
R
x
k
≤
MR
√
k 1
.
3.33
As a c onsequence, the sequence {g
R
x
k
} converges to 0 and the number of iterations to reach an
ε-solution is k
ε
:M
g
R
x
k
≤
k
i0
w
i
, x − x
i
1
2β
k
w
k
2
−
i
, x − x
i
1/2β
k
w
k
2
− β
k
/2d
2
C
x 1/β
k
w
k
. Then, we have
b
k
− b
k−1
w
k
, x − x
k
2β
k−1
w
k−1
2
β
k−1
2
d
2
C
x
1
β
k−1
w
k−1
.
3.36
We consider, for all y ∈ R
n
y
2
−
β
2
min
v∈C
v − x −
1
β
w
2
.
3.37
Then derivative of q is given by
q
β
≤w
k
, x − x
k
1
2β
k
w
k
2
−
β
k
2
d
2
C
x
1
β
k
w
.
3.39
From Lemma 3.1, β β
k
and ρ
k
1, we have
d
2
C
x
1
β
k
w
k
− d
2
C
x
1
β
k
w
k−1
≥
k−1
2
−
1
β
2
k
ξ
k
w
k
2
.
3.40
Combining 3.39 and t his inequality, we have
b
k
− b
k−1
≤
By induction on k, it follows from 3.41 and β
0
:M
x
M
u
/R that
b
k
≤
MR
2
k
i0
1
√
i 1
≤
MR
2
k 1 ≡
β
k
R
2
2
.
3.42
{
x ∈ R
n
| Ax ≤ b
}
, 4.1
where A ∈ R
m×n
, b ∈ R
m
. The cost function F : C → R is defined by
F
x
D
x
− Mx q, 4.2
where D : C → R
n
, M ∈ R
n×n
is a symmetric positive semidefinite matrix and q ∈ R
n
.The
function ϕ is defined by
ϕ
Proof. Since D is τ-strongly monotone on C,thatis
D
x
− D
y
,x− y
≥ τ
x − y
2
, ∀x, y ∈ C,
M
x − y
,x− y
≤
M
,x− y−
M
x − y
,x− y
≥
τ −
M
x − y
2
, ∀x, y ∈ C.
4.5
Then i and ii easily follow.
Using the Lipschitz condition, it is not difficult to obtain iii.
To illustrate our algorithms, we consider the following data.
n 10,D
x
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
120000000 0
22.20000000 0
003100000 0
001400000 0
00004.52 0 0 0 0
000003000 0
0000201.50 0 0
000000011 0
000000012.50
0000000003.5
⎤
⎥
⎥
√
10,
4.6
with τ M 2.2071, L τ M 4.4142, β L/2 2.2071. From Lemma 4.1, we have F
is monotone on C. The subproblems in Algorithm 3.2 can be solved efficiently, for example,
by using MATLAB Optimization Toolbox R2008a. We obtain the approximate solution
x
10
0.0510, 0.6234, −0.2779, 1.0000, 0.0449, 1.0000, −1.0000, 1.0000, 0.7927, −1.0000
T
.
4.7
Now we use Algorithm 3.4 on the same variational inequalities except that
F
x
: τx D
x
− Mx q, 4.8
where the n components of the Dx are defined by: D
j
xd
j
arctanx
x
k
8
x
k
9
x
k
10
1 −0.278 0.001 −0.006 −0.377 0.272 −0.007 −0.462 −0.227 0.395 −0.364
2 −0.054 0.133 −0.245 −0.435 −0.348 0.080 0.493 −0.223 −0.146 0.307
3 −0.417 0.320 −0.027 −0.270 0.463 −0.375 −0.381 0.255 −0.087 −0.403
4 0.197 0.161 0.434 −0.090 0.505 −0.001 0.451 −0.358 −0.320 0.278
5 0.291 0.071
−0.383 −0.290 0.453 −0.035 −0.393 −0.536 0.238 0.166
6 −0.021 0.246 0.211 −0.036 0.044 −0.241 0.466 −0.186 0.486 −0.072
7 −0.429 0.220 0.134 0.321 −0.312 0.364 −0.278 0.551 0.421 −0.118
8 −0.349 −0.448 0.365 −0.467 −0.137 0.387 0.217 −0.049 −0.443 −0.453
9 −0.115 0.562 −0.371 −0.536 −
0.198 −0.248 −0.233 0.124 −0.149 0.319
10 0.071 0.134 −0.268 −0.340 0.307 0.010 0.052 −0.168 −0.206 −0.244
With x 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ∈ int C and the tolerance 10
−6
, we obtained the
computational results see, the Table 1.
Acknowledgments
The authors would like to thank the referees for their useful comments, remarks and
suggestions. This work was completed while the first author was staying at Kyungnam
University for the NRF Postdoctoral Fellowship for Foreign Researchers. And the second
author was supported by Kyungnam University Research Fund, 2010.
14 J. K. Kim and K. S. Kim, “New systems of generalized mixed variational inequalities with nonlinear
mappings in Hilbert spaces,” Journal of Computational Analysis and Applications, vol. 12, no. 3, pp. 601–
612, 2010.
15 J. K. Kim and K. S. Kim, “A new system of generalized nonlinear mixed quasivariational inequalities
and iterative algorithms in Hilbert spaces,” Journal of the Korean Mathematical Society,vol.44,no.4,pp.
823–834, 2007.
16 R. A. Waltz, J. L. Morales, J. Nocedal, and D. Orban, “An interior algorithm for nonlinear optimization
that combines line search and trust region steps,” Mathematical Programming, vol. 107, no. 3, pp. 391–
408, 2006.
17 P. N. Anh, “An interior proximal method for solving monotone generalized variational inequalities,”
East-West Journal of Mathematics, vol. 10, no. 1, pp. 81–100, 2008.
18 A. Auslender and M. Teboulle, “Interior projection-like methods for monotone variational inequali-
ties,” Mathematical Programming, vol. 104, no. 1, pp. 39–68, 2005.
19 A. Bnouhachem, “An LQP method for pseudomonotone variational inequalities,” Journal of Global
Optimization, vol. 36, no. 3, pp. 351–363, 2006.
20 A. N. Iusem and M. Nasri, “Augmented Lagrangian methods for variational inequality problems,”
RAIRO Operations Research, vol. 44, no. 1, pp. 5–25, 2010.
21 J. K. Kim, S. Y. Cho, and X. Qin, “Hybrid projection algorithms for generalized equilibrium problems
and strictly pseudocontractive mappings,” Journal of Inequalities and Applications, vol. 2010, Article ID
312062, 17 pages, 2010.
22 J. K. Kim and N. Buong, “Regularization inertial proximal point algorithm for monotone
hemicontinuous mapping and inverse strongly monotone mappings in Hilbert spaces,” Journal of
Inequalities and Applications, vol. 2010, Article ID 451916, 10 pages, 2010.
23 Y. Nesterov, “Dual extrapolation and its applications to solving variational inequalities and related
problems,” Mathematical Programming, vol. 109, no. 2-3, pp. 319–344, 2007.
24 J P. A ubin and I. Ekeland, Applied Nonlinear Analysis, Pure and Applied Mathematics, John Wiley &
Sons, New York, NY, USA, 1984.
25 P. N. Anh and L. D. Muu, “Coupling the Banach contraction mapping principle and the proximal
point algorithm for solving monotone variational inequalities,”
Acta Mathematica Vietnamica, vol. 29,
Copyright: Tài liệu đại học ©