Monotonicity of Fixed Point and Normal Mappings Associated with Variational Inequality and Its Application.
We prove     sufficient   conditions for  the monotonicity and the strong monotonicity of    fixed point and normal maps associated with   variational inequality problems over a general closed convex set. Sufficient conditions for  the strong  monotonicity of their perturbed versions are also shown. These results include    some well known  in the literature as particular instances. Inspired by these results,   we propose   a modified Solodov and Svaiter iterative algorithm   for the  variational inequality problem whose   fixed point map  or normal map is monotone.
Introduction
. Given a continuous function f : R n ! R n and a closed convex
set K in R n ; the well-known finite-dimensional variational inequality, denoted by
f ), is to find an element x   2 K such that
It is well-known that the above problem can be reformulated as nonsmooth equations
such as the fixed point and normal equations (see e.g. [9, 18]). The fixed point
equation is defined by
and the normal equation is defined by
positive scalar, and \Pi K (\Delta) denotes the projection operator on the
convex set K; i.e.,
Throughout the paper, k \Delta k denotes the 2-norm (Euclidean norm) of the vector in R
It turns out that x   solves VI(K; f) if and only if - ff (x   and that if x   solves
ff f(x   ) is a solution to \Phi ff conversely, if \Phi ff (u
\Pi K (u   ) is a solution to VI(K; f):
Recently, several authors studied the P 0 property of fixed point and normal maps
when K is a rectangular box in R n , i.e., the Cartesian product of n one-dimensional
This work was partially supported by Research Grants Council of Hong Kong under grant
CUHK4392/99E.
y Department of Systems Engineering and Engineering Management, The Chinese University
of Hong Kong, Shatin, New Territory, Hong Kong, and Institute of Computational Mathematics
and Scientific/Engineering Computing, Chinese Academy of Sciences, Beijing, China (Email:
ybzhao@se.cuhk.edu.hk).
z Corresponding author. Department of Systems Engineering and Engineering Management, The
Chinese University of Hong Kong, Shatin, New Territory, Hong Kong (Fax: (852) 26035505; Tel:
Y. B. ZHAO AND D. LI
intervals. For such a K, Ravindran and Gowda [17] (respectively, Gowda and Tawhid
[8]) showed that - ff (x) (respectively, \Phi ff (x)) is a P 0 -function if f is. Notice that the
monotone maps are very important special cases of the class of P 0 -functions. It is
worth considering the problem:
(P) When are the mappings - ff (x) and \Phi ff (x) monotone if K is a general closed
convex set?
Intuitively, we may conjecture that the fixed point map and the normal map
are monotone if f is. However, this conjecture is not true. The following example
shows that for a given ff ? 0 the monotonicity of f , in general, does not imply the
monotonicity of the fixed point map - ff (x) and the normal map \Phi ff (x):
Example 1.1. Let K be a closed convex set given by
and
For any x; y we have that 0: Hence the function f is
monotone on R 2 . We now show that for an arbitrary scalar ff ? 0 the fixed point
mapping - ff not monotone in R 2 . Indeed, let
It is easy to verify that - ff
Thus, we have
which implies that - ff (\Delta) is not monotone on R
Example 1.2. Let K be a closed convex set given by
given as in Example 1.1. We now show that for an arbitrary
the normal mapping \Phi ff not monotone in
R 2 . Indeed, let We have that \Phi ff
Thus, we have
which implies that \Phi ff (\Delta) is not monotone on R
From the above examples, we conclude that certain condition stronger than the
monotonicity of f is required to guarantee the monotonicity of - ff (x) and \Phi ff (x). One
such condition is so-called co-coercivity condition. We recall that f is said to be co-
coercive with modulus fi ? 0 on a set S ae R n if there exists a constant fi ? 0 such
that
The co-coercivity condition was used in several works, such as Bruck [1], Gabay [7] (in
which this condition is used implicitly), Tseng [25], Marcotte and Wu [15], Magnanti
and Perakis [13, 14], and Zhu and Marcotte [29, 30]. It is also used to study the strict
feasibility of complementarity problems [27]. It is interesting to note that in an affine
MONOTONICITY OF FIXED POINT AND NORMAL MAPPINGS 3
case the co-coercivity has a close relation to the property of psd-plus matrices [12, 30].
A special case of the co-coercive map is the strongly monotone and Lipschitzian map.
We recall that a mapping f is said to be strongly monotone with modulus c ? 0 on
the set S if there is a scalar c ? 0 such that
It is evident that any co-coercive map on the set S must be monotone and Lipschitz
continuous (with constant not necessarily strongly monotone (for
instance, the constant mapping) on the same set.
In fact, the aforementioned problem (P) is not completely unknown. By using the
co-coercivity condition implicitly and using properties of nonexpansive maps, Gabay
actually showed (but did not explicitly state) that - ff (x) and \Phi 1=ff (x) are monotone
if the scalar ff is chosen such that the map I \Gamma fff is nonexpansive. Furthermore, for
strongly monotone and Lipschitzian map f , Gabay [7] and Sibony [20] actually showed
that - ff (x) and \Phi 1=ff (x) are strongly monotone if the scalar ff is chosen such that the
contractive. Throughout this paper, we use the standard concept
"nonexpansive" map and "contractive" map in the literature to mean a Lipschitzian
map with constant
However, it is easy to give an example to show that - ff (x) and \Phi ff (x) are still
monotone (strongly monotone) even when ff is chosen such that I \Gamma fff is not nonexpansive
(contractive). For instance, let
We see that the
function f is co-coercive with modulus fff is not nonexpansive for
remains monotone. As a result, the main purpose of this paper
is to expand the results of Sibony [20] and Gabay [7]. We show that if f is co-coercive
(strongly monotone and Lipschitz continuous, respectively), the monotonicity (strong
monotonicity, respectively) of the maps - ff (x) and \Phi ff (x) can be ensured when ff lies
in a larger interval in which the map I \Gamma fff may not be nonexpansive (contractive,
respectively). The results derived in this paper are not obtainable by the proof based
on the nonexpansiveness and contractiveness of maps.
The other purpose of the paper is to introduce an application of the monotonicity
of - ff (x) and \Phi ff (x): This application (see Section 3) is motivated by the globally
convergent inexact Newton method for the system of monotone equations proposed
by Solodov and Svaiter [21]. See also [22, 23, 24]). We propose a modified Solodov
and Svaiter method to solve the monotone equations - ff 0: This
modified algorithm requires no projection operations in the line-search step.
2. Monotonicity of - ff (x) and \Phi ff (x). It is known (see Sibony [20] and Gabay
[7]) that if f is strongly monotone with modulus c ? 0 and Lipschitz continuous
with constant L ? 0, then I \Gamma fff is contractive when
nonexpansive, this in turn implies that - ff (x) and \Phi 1=ff (x) are both strongly monotone
Similarly, it follows from Gabay [7] (see Theorem 6.1 therein) that
if f is co-coercive with modulus fi ? 0; then I \Gamma fff is nonexpansive for
and thus we can easily verify that - ff (x) and \Phi 1=ff (x) are monotone for
In this section, we prove an improved version of the above-mentioned results. We
prove that i) when ff lies outside of the interval (0; 2c=L 2 ), for instance, 2c=L 2 - ff -
are still strongly monotone although I \Gamma fff , in this case, is
not contractive, and ii) when ff lies outside of the interval (0; 2fi], for instance, 2fi !
remain monotone although I \Gamma fff is not nonexpansive.
This new result on monotonicity (strongly monotonicity) of - ff (x) and \Phi 1=ff (x) for ff ?
not obtainable by using the nonexpansive (contractive) property
4 Y. B. ZHAO AND D. LI
of I \Gamma fff: The reason goes as follows: Let f be co-coercive with modulus fi ? 0 on
the set S ' R n ; where
Clearly, such a scalar fi is unique and is not a constant
mapping. We now verify that I \Gamma fff is nonexpansive on S if and only if
It is sufficient to show that if ff ? 0 is chosen such that I \Gamma fff is nonexpansive on S,
then we must have ff - 2fi: In fact, if I \Gamma fff is nonexpansive, then for any x; y in S
we have
which implies that
By the definition of fi, we deduce that ff=2 - fi; the desired consequence. Similarly, let
f be strongly monotone with modulus c ? 0 and Lipschitz continuous with constant
on the set S, where
and
We can easily see that is not a single point set.
It is also easy to show that I \Gamma fff is contractive if and only if
Since the map I \Gammafff is not contractive (nonexpansive, respectively) for ff - 2c=L 2
our result established in this section cannot follow directly
from the proof of Sibony [20] and Gabay [7].
We also study the strong monotonicity of the perturbed fixed point and normal
maps defined by
and
respectively. This is motivated by the well-known Tikhonov regularization method for
complementarity problems and variational inequalities. See for example, Isac [10, 11],
Venkateswaran [26], Facchinei [3], Facchinei and Kanzow [4], Facchinei and Pang [5],
Gowda and Tawhid [8], Qi [16], Ravindran and Gowda [17], Zhao and Li [28], etc. It is
worth mentioning that Gowda and Tawhid [8] showed that when perturbed
mapping \Phi 1;" (x) is a P-function if f is a P 0 -function and K is a rectangular set. We
show in this paper a sufficient condition for the strong monotonicity of - ff;" (x) and
\Phi ff;" (x): The following lemma is helpful.
Lemma 2.1. (i) Denote
(2.
MONOTONICITY OF FIXED POINT AND NORMAL MAPPINGS 5
Then
(ii) For any ff ? 0 and vector b 2 R n ; the following inequality holds for all v 2 R n ;
Proof. By the property of projection operator, we have
Adding the above two inequalities leads to
i.e.,
This proves the result (i).
Given ff ? 0 and b 2 R n ; it is easy to check that the minimum value of ffkvk 2 +v T b
is \Gammakbk 2 =(4ff): This proves the result (ii).
We are ready to prove the main result in this section.
Theorem 2.1. Let K be an arbitrary closed convex set in R n and K ' S ' R
(i) If f is co-coercive with modulus fi ? 0 on the set S; then for any fixed scalar
the fixed point map - ff (x) defined by (1.1) is monotone on
the set S.
(ii) If f is strongly monotone with modulus c ? 0 on the set S; and f is Lipschitz
continuous with constant L ? 0 on S; then for any fixed scalar ff satisfying
the fixed point map - ff (x) is strongly monotone on the set S:
(iii) If f is co-coercive with modulus fi ? 0 on the set S; then for any 0 ! ff ! 4fi
the perturbed map - ff;" (x) is strongly monotone in x on the
set S.
Proof. Let ff ? 0 and 0 - 2=ff be two scalars. For any vector x; y in
By using the notation of (2.1) and Lemma 2.1, we have
6 Y. B. ZHAO AND D. LI
If f is co-coercive with modulus fi ? 0, using " - 2=ff we see from the above that
'ff
Setting in the above inequality, we see that for 0 ! ff - 4fi the right-hand side
is nonnegative, showing that - ff is monotone on the set S: This proves the result (i).
Also, if ff ! 4fi and
4fi ); the right-hand side of the above inequality is
greater than or equal to rkx \Gamma showing that - ff;" is
strongly monotone on the set S: The proof of the result (iii) is complete.
Assume that f is strongly monotone with modulus c ? 0 and Lipschitz continuous
with constant L ? 0: We now prove the result (ii). For this case, setting
(2.2), we have that
For it is evident that the scalar
4c
0:
Result (ii) is proved.
Similarly, we have the following result for \Phi ff (x):
Theorem 2.2. Let f be a function from R n into itself and K be a closed convex
set and K ' S ' R
(i) If f is co-coercive with modulus fi ? 0 on the set S; then for any constant ff
such that ff ? 1=(4fi); the normal map \Phi ff (x) given by (1.2) is monotone on the set
S.
(ii) If f is strongly monotone with modulus c ? 0 and Lipschitz continuous with
constant L ? 0 on the set S; then for any ff satisfying ff ? L 2 =(4c); the normal map
\Phi ff (x) given by (1.2) is strongly monotone on the set S.
(iii) If f is co-coercive with modulus fi ? 0 on the set S; then for any constant
ff ? 1=(4fi); the perturbed normal map \Phi ff;" (x), where strongly monotone
in x on the set S.
MONOTONICITY OF FIXED POINT AND NORMAL MAPPINGS 7
Proof. Let ff; "; r be given such that ff 0: For any vector x; y in
u x and u y be defined by (2.1) with
2.1 we have
kf (\Pi K
and
that further implies
By using the above three inequalities, we have
\Gammaf (\Pi K
\Gammaf (\Pi K
kf (\Pi K
Let f be co-coercive with modulus fi ? 0 on the set S. Setting in the above
inequality, and using the co-coercivity of f , we have
4ff kf (\Pi K
4ff
kf (\Pi K
For ff ? 1=(4fi); the right-hand side is nonnegative, and hence the map \Phi ff is monotone
on the set S: This proves the result (i).
By the co-coercivity
of f , the inequality (2.6) can be further written as
kf (\Pi K
8 Y. B. ZHAO AND D. LI
the right-hand side of the above is nonnegative, and thus
the map \Phi ff;" is strongly monotone on the set S: Result (iii) is proved.
Finally, we prove the result (ii). Assume that f is strongly monotone with modulus
continuous with constant L ? 0. For any vector x; y in
we note that the equation (2.5) holds for any ff ?
the equation (2.5) reduces to
Given ff ? L 2 =(4c): Let r be a scalar such that
Notice that
Substituting the above into (2.7) and using inequalities (2.3) and (2.4), we have
where the last inequality follows from the Lipschitz continuity and strong monotonicity
of f: The right-hand side of the above is nonnegative. Thus, the map \Phi ff is strongly
monotone on the set S: This proves the result (ii).
The following result is an immediate consequence of Theorems 2.1 and 2.2.
Corollary 2.1. Assume that f is monotone and Lipschitz continuous with
constant L ? 0 on a set S ' K:
; then the perturbed map - ff;" (x) is strongly
monotone in x on the set S.
then the perturbed normal map \Phi ff;" (x) is
strongly monotone in x on the set S.
Proof. Let " 2 (0; 1) be a fixed scalar. It is evident that under the condition
of the corollary, the function F strongly monotone with modulus
continuous with constant L+ ": Therefore, from Theorem 2.1(ii)
we deduce that if 0 the map - ff;" (x) is strongly monotone on S:
Similarly, the strong monotonicity of \Phi ff;" (x) follows from Theorem 2.2(ii).
The Item (iii) of both Theorem 2.1 and Theorem 2.2 shows that for any sufficiently
small parameter ", the perturbed fixed point and normal maps are strongly monotone.
This result is quite different from Corollary 2.1. When ff is a fixed constant, Corollary
MONOTONICITY OF FIXED POINT AND NORMAL MAPPINGS 9
2.1 does not cover the case where " can be sufficiently small. Indeed, for a fixed ff ? 0,
the inequalities
4" fail to hold when " ! 0:
Up to now, we have shown that the fixed point map - ff (x) (respectively, the
normal map \Phi ff (x)) is monotone if f is co-coercive with modulus fi ? 0 and ff 2 (0; 4fi]
(respectively, ff 2 (1=(4fi); 1)): This result includes the known ones from Sibony [20]
and Gabay [7] as special cases. Under the same assumption on f and ff; we deduce
from the Item (iii) of Theorems 2.1 and 2.2 that the perturbed forms - ff;" and \Phi ff;" are
strongly monotone provided that the scalar " is sufficiently small. In the succeeding
sections, we will introduce an application of the above results on globally convergent
iterative algorithms for VI(K; f) whose fixed point map or normal map is monotone.
3. Application: Iterative algorithm for VI(K; f) . Since - ff (x) and \Phi ff (x)
are monotone if the function f is co-coercive and ff lies in certain interval, we can
solve the co-coercive variational inequity problems via solving the system of monotone
equation - ff Recently, Solodov and Svaiter [21] (see also,
[22, 23, 24]) proposed a class of inexact Newton methods for monotone equations. Let
F(x) be a monotone mapping from R n into R n : The Solodov and Svaiter's algorithm
for the equation proceeds as follows:
Algorithm SS. [21] Choose any x 0
Inexact Newton step. Choose a positive semidefinite matrix G k . Choose
and
where
Line-search step. Find y being the
smallest nonnegative integer m such that
\GammaF
Projection step. Compute
repeat.
As pointed out in [21], the above inexact Newton step is motivated by the idea of
proximal point algorithm [2, 6, 19]. Algorithm SS has an advantage over other Newton
methods that the whole iteration sequence is globally convergent to a solution of the
system of equations, provided a solution exists, under no assumption on F other than
continuity and monotonicity. Setting or \Phi ff (x), from Theorems 2.1 and
2.2 in this paper and Theorem 2.1 of [21], we have the following result.
Theorem 3.1. Let f be a co-coercive map with constant fi ? 0: Substitute F(x)
in Algorithm SS by - ff (x) (respectively, \Phi ff (x)) where
ff ? 1=4fi). If - k is chosen such that C 2 - k - C 1 kF(x k )k, where C 1 and C 2
are two constants, then Algorithm SS converges to a solution of variational inequality
provided that a solution exists.
While Algorithm SS can be used to solve the monotone equations - ff
and \Phi ff each line-search step needs to compute the values of - ff
and \Phi ff that represents a major cost of the algorithm in calculating
projection operations. Hence, in general cases, Algorithm SS has high computational
Y. B. ZHAO AND D. LI
cost per iteration when applied to solve \Phi ff To reduce this major
computational burden, we propose the following algorithm which needs no projection
operations other than the evaluation of the function f in line-search steps.
Algorithm 3.1. Choose x 0
Inexact Newton Step: Choose a positive semidefinite matrix G k . Choose
Compute
where
Line-search step. Find y being the smallest
nonnegative integer m such that
Projection step. Compute
The above algorithm has the following property.
Lemma 3.1. Let - ff (x) be given as (1.1). At kth iteration, if m k is the smallest
nonnegative integer such that (3.2) holds, then y satisfies the following
estimation:
Proof. By the definition of - ff (x), the nonexpansiveness of projection operator
and (3.2), we have
\Gamma\Pi K
Also,
\Gamma- ff
MONOTONICITY OF FIXED POINT AND NORMAL MAPPINGS 11
By (3.1) and positive semi-definiteness of G k , we have
\Gamma- ff
Combining (3.3), (3.4) and (3.5) yields
\Gamma- ff
The proof is complete.
Using Lemma 3.1 and following the line of the proof of Theorem 2.1 in [21], it is
not difficult to prove the following convergence result.
Theorem 3.2. be a continuous function such that there exists
a constant ff ? 0 such that - ff (x) defined by (1.1) is monotone. Choose G k and - k
such that kG k k - C 0 and - are three fixed positive
numbers and p 2 (0; 1]: Then the sequence fx k g generated by Algorithm 3.1 converges
to a solution of the variational inequality provided that a solution exists.
Algorithm 3.1 can solve the variational inequality whose fixed point mapping
- ff (x) is monotone for some ff ? 0. Since the co-coercivity of f implies the monotonicity
of the functions - ff (x) and \Phi ff (x) for suitable choices of the value of ff; Algorithm
3.1 can locate a solution of any solvable co-coercive variational inequality problem.
This algorithm has an advantage over Algorithm SS in that it does not carry out
any projection operation in the line-search step, and hence the computational cost is
significantly reduced.
4. Conclusions . In this paper, we show some sufficient conditions for the monotonicity
(strong monotonicity) of the fixed point and normal maps associated with
the variational inequality problem. The results proved in the paper encompass some
known results as particular cases. Based on these results, an iterative algorithm for
a class of variational inequalities is proposed. This algorithm can be viewed as a
modified Solodov and Svaiter's method but has lower computational cost than the
latter.
Acknowlegements. The authors would like to thank two anonymous referees
for their incisive comments and helpful suggestions which help us to improve many
aspects of the paper. They also thank Professor O. L. Mangasarian for encouragement
and one referee for pointing out refs. [7, 20].



--R


On the Douglas-Rachford splitting method and the

Beyond monotonicity in regularization methods for
Total Stability of Variational Inequalities
Finite termination of the
Applications of the method of multipliers to variational inequalities
Existence and limiting behavior of trajectories associated with P0 equations
A survey of theory
Tikhonov's regularization and the complementarity problem in Hilbert spaces
A generalization of Karamardian's condition in complementarity theory
A decomposition property for a class of square matrices
A unifying geometric solution framework and complexity analysis for variational inequalities
The orthogonality theorem and the strong-f-monotonicity condition for variational inequality algorithms
On the convergence of projection methods: application to the decomposition of affine variational inequalities
regularization methods for variational inequality problems
Regularization of P 0
Normal maps induced by linear transformations
Control Optim.
M'ethods it'eratives pour les 'equations et in'equations aus d'eriv'ees partielles non- lin'earies de type monotone
A globally convergence inexact Newton method for systems of monotone equations
A truly globally convergent Newton-type method for the monotone nonlinear complementarity problem

A new projection method for variational inequality problems
Further applications of a matrix splitting algorithm to decomposition in variational inequalities and convex programming
An algorithm for the linear complementarity problem with a P 0
On condition for strictly feasible condition of
On a new homotopy continuation trajectory for
New classes of generalized monotonicity

--TR

--CTR
Zhang , Weijun Zhou, Spectral gradient projection method for solving nonlinear monotone equations, Journal of Computational and Applied Mathematics, v.196 n.2, p.478-484, 15 November 2006
iterative algorithm;fixed point and normal maps;strongly monotone maps;variational inequalities;cocoercive maps