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

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

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, 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

) and compute the limit lim
k→∞
u
k
.
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
u
k
− u
k−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 u
0
∈ H and a sequence {ρ
k
} of positive real numbers satisfying
the condition ρ
k
≥ ρ > 0 for all k ∈ IN. If u
k−1
has been defined, one can
choose u
k
as any solution of the auxiliary problem VI(K, F

u
k
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 u
k
− u
k−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: u
0
∈ K and α ∈ (0, 1/L).
Step 0: Set k = 0.
Step 1: If u
k
= P
K

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 ⊂ IR
n
is a nonempty closed convex set, F : K → IR
n
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 IR

ric and nonsingular matrix, and q ∈ IR
n
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 = 0 and M
T
= −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 : IR
n
→ IR
n
is a map of the form
F (u) = g(u)(Mu + q),
where g : IR
n
→ IR is a positive and continuously differentiable function,
M ∈ IR
n×n
is a positive semidefinite nonsingular matrix, and q ∈ IR
n
. Then
there exists ¯ε > 0 such that the regularized problem VI(K, F
ε
) has a unique
solution for all ε ∈ (0, ¯ε).

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 IR
n
, n ≥ 2.
Theorem 2.6 Suppose that F (u) = Mu + q is an affine map, where
M = diag(λ
1
, λ
2
, . . . , λ
n
), q = (q
1
, q
2
, . . . , q
n
)
T
(2.1)
are respectively a diagonal matrix and a vector in IR
n
. Then F is pseu-
domonotone on IR
n
+
if and only if one of the following conditions holds:
(i) λ
i

n
)
T
being a vector in IR
n
. If F is merely
pseudomonotone on IR
n
+
(i.e., F is pseudomonotone but not monotone on
IR
n
+
), then there exists ¯ε > 0 such that F
ε
(u) = F (u) +εu is not pseudomono-
tone on IR
n
+
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 u
k
∈ IR
n
and ε > L the regularized operator
F
k,ε

then F
(k)
(.) is strongly monotone on K with the constant α
k
:= 1 − ρ
k
L.
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 ∈ IR
n×n
\{0} and q ∈ IR
n
then F
(k)
(.) is strongly monotone on K with the
constant α
k

} ⊂ (0, +∞).
Step 0: Set k = 0.
Step 1: If u
k
= P
K
(u
k
− λ
k
F (u
k
)) then stop.
Step 2: Compute u
k+1
= P
K
(u
k
− λ
k
F (u
k
)) and replace k by k + 1; go to
Step 1.
If the computation terminates at a step k, then we put u
k

= u
k


2
≤ u
k
− 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γ
L
2
∀k ∈ IN, (3.2)
where a, b are some positive constants. Let {u
k
} be the sequence generated by
Algorithm 3.1. If u
∗
is the unique solution of VI(K, F ) then the sequence {u
k
}

µ :=
1

1 + a(2γ − bL
2
)
∈ (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 = (u
1
, u
2
, . . . , u
i
, . . .) :
∞

i=1
|u
i
|
2
< +∞}.

, . . .) 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

2

is taken arbitrarily. From Theorem 3.1 it follows that the sequence {u
k
} 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),
u
k+1
− 0 ≤
µ
k+1
1 − µ
u
1
− u
0
 and u
k+1
− 0 ≤
µ
1 − µ
u
k+1
− u
k

, then the sequence {u
k
} converges in norm to u
∗
. Moreover, there
exists an index k
0
∈ IN such that, for each k ≥ k
0
, one has λ
k
(2γ −λ
k
L
2
) > 0
and
u
k+1
− u
∗
 ≤
1


k
i=k
0
[1 + λ
i

λ
k
< +∞,
both the conditions (3.2) and (3.6) are violated. The iterative sequence {u
k
}
produced by Algorithm 3.1 for u
0
= 1 is given by
u
k+1
= P
K
(u
k
− λ
k
F (u
k
)) = u
k
− λ
k
u
k
= (1 − λ
k
)u
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 lim
k→∞
u
k
=
1
2
. This means that {u
k
} does not
converge to the unique solution of VI(K, F ) under our consideration.

k
= (1 − λ
k
)u
k
.
Since lim
k→∞
λ
k
= 0 and u
k
= 0 for all k ∈ IN, we have
lim
k→∞
u
k+1
− 0
u
k
− 0
= lim
k→∞
|1 − λ
k
| = 1
Hence one cannot find any µ ∈ (0, 1) such that the inequality
u
k+1
− 0 ≤ µu

(u
k
− α
k
F (u
k
)) then stop.
Step 2: Set
¯u
k
= P
K
(u
k
− α
k
F (u
k
)),
u
k+1
= P
K
(u
k
− α
k
F (¯u
k
)),

} 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 {u
k
} is a
sequence generated by the Algorithm 4.1. If {u
k
} 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 u
0
= 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

k+1

i=1
(1 − 2
−i
+ 4
−i
) ∀k ∈ IN.
Then {u
k
} 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 {u
k
} is a sequence
generated by Algorithm 4.1. If Sol(K, F ) is nonempty, then there exists ˆu in
Sol(K, F ) such that {u
k
} converges weakly to ˆu.
4.3 Convergence Rate of the Iterative Sequences
Suppose that a sequence {u
k
} in H converges in norm to u
∗
∈ H. We say
that
17
(a) {u
k
} converges to u

k
} ⊂ IR be the sequence of real numbers defined by
setting u
k
= 2
−k
if k is even and u
k
= 3
−k
if k is odd. Since limsup
k→∞
u
k
−
0
1/k
=
1
2
, {u
k
} converges to 0 with R-linear convergence rate. However {u
k
}
does not converge to 0 with Q-linear convergence rate since
limsup
k→∞
u
k+1

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 − P
K
(u − F (u)) = u
2
.
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 u
0
= 1 ∈ K
and α
k
= 1/4 ∈ (0, 1/2) for all k ∈ IN. The sequence {u
k
} produced by (4.1)
is given by
u
k+1
= −(1/64)(u
k
)
4
+ (1/8)(u
k
)
3

∗
= 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 {u
k
} 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 u
0
∈ K and {α
k
}
∞
k=0
⊂ IR
+
be such that

k
− α
k
F (u
k
)),
u
k+1
= P
K
(u
k
− α
k
F (¯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 u
k

= u
k
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-

j
)u
k
0
− u
∗
, (5.3)
where γ > 0 is a strong pseudomonotonicity constant of F . In addition,
lim
k→∞




k

j=k
0
(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

+ α
2
j
) =
k

j=0

1 −
1
(j + 1)
2
+
1
(j + 1)
4

∀k ∈ IN.
Note that lim
k→∞
u
k
= u
∗
for some u
∗
≥
1
2
. So {u

}
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 = IR
2
and F (u) = (−u
2
, u
1
)
T
for all u = (u
1
, u
2
)
T
∈ K.
It is clear that F is Lipschitz continuous and monotone on K, and Sol(K, F )
= {(0, 0)
T
}. Let u
0

, u
0
2
)
T
and







u
k+1
1
=

1 −
1
(k + 1)
2

u
k
1
+
1
k + 1
u

k→∞




k

j=0

1 −
1
(j + 1)
2
+
1
(j + 1)
4

≥
√
2
2
. (5.6)
Hence {u
k
} does not converge to the unique solution of VI(K, F ). Interest-
ingly, the set of the cluster points of the sequence {u
k
} is the circle
S := {u ∈ IR