Properties of a Multivalued Mapping Associated with Some Nonmonotone Complementarity Problems.
Using the homotopy invariance property of the  degree and a newly introduced concept of the interior-point-$\varepsilon$-exceptional family for continuous functions, we prove an alternative theorem concerning the existence of a certain interior-point of a continuous  complementarity problem. Based on this result, we develop several sufficient conditions to assure some desirable properties (nonemptyness, boundedness, and upper-semicontinuity) of a multivalued mapping associated with   continuous (nonmonotone) complementarity problems corresponding to  semimonotone, P$(\tau, \alpha, \beta)$-, quasi-P*-, and exceptionally regular maps. The results proved in this paper generalize well-known results on the existence of central paths in continuous P0 complementarity problems.
Introduction
. Consider the nonlinear complementarity problem (NCP)
where f is a continuous function from R n into itself. This problem has now gained
much importance because of its many applications in optimization, economics, engi-
neering, etc. (see [8, 12, 16, 18]).
There are several equivalent formulations of the NCP in the form of a nonlinear
equation F is a continuous function from R n into R n . Given such an
equation F the most used technique is to perturb F to a certain F # , where #
is a positive parameter, and then consider the equation F # has a
unique solution denoted by x(#) and x(#) is continuous in #, then the solutions {x(#)}
describe, depending on the nature of F # (x), a short path denoted by {x(# (0, -
or a long path {x(# (0, #)}. If a short path {x(# (0, - #]} is bounded,
then for any subsequence {# k } with # k # 0, the sequence {x(# k )} has at least one
accumulation point, and by the continuity each of the accumulation points is a solution
to the NCP. Thus, a path can be viewed as a certain continuous curve associated
with the solution set of the NCP. Based on the path, we may construct various
computational methods for solving the NCP, such as interior-point path-following
methods (see, e.g., [15, 25, 26, 27, 28, 32, 39]), regularization methods (see [8, 10, 11,
41]), and noninterior path-following methods (see [1, 2, 3, 5, 7, 17, 21]). The most
common interior-point path-following method is based on the central path. The curve
(0, #)} is said to be the central path if for each # > 0 the vector x(#) is
the unique solution to the system
(1)
# Received by the editors September 28, 1998; accepted for publication (in revised form) March 14,
2000; published electronically September 20, 2000.
http://www.siam.org/journals/sicon/39-2/34519.html
Institute of Computational Mathematics and Scientific/Engineering Computing, Chinese
Academy of Sciences, P.O. Box 2719, Beijing 100080, China (zyb@lsec.cc.ac.cn, ybzhao@se.cuhk.
edu.hk).
# Department of Mathematics and Computer Sciences, Royal Military College of Canada,
Kingston, Ontario, K7K 7B4, Canada (isac-g@rmc.ca).
572 YUN-BIN ZHAO AND GEORGE ISAC
is continuous on (0, #).
In the case when f is a monotone function and the NCP is strictly feasible (i.e.,
there is a vector u # R n such that u > 0 and f(u) > 0), the existence of the central
path is well known (see, for example, [14, 25, 30, 31]). This existence result has been
extended to some nonmonotone complementarity problems. Kojima, Mizuno, and
proved that the central path exists if f is a uniform-P function. If f is a
-function satisfying a properness condition and the NCP is strictly feasible, Kojima,
Megiddo, and Noma [25] showed that there exists a class of interior-point trajectories
which includes the central path as a special case. If f is a P 0 -function and NCP
has a nonempty and bounded solution set, Chen, Chen, and Kanzow [4] and Gowda
and Tawhid [13] proved that the NCP has a short central path {x(# (0, -
#)}.
Under a certain properness condition, Gowda and Tawhid [13] showed that the NCP
with a P 0 -function has a long central path [13, Theorem 9]. It should be pointed out
that noninterior-point trajectories have also been extensively studied in the recent
literature (see [1, 2, 3, 5, 10, 11, 13, 17, 35, 37]).
However, for a general complementarity problem, the system (1) may have multiple
solutions for a given # > 0, and even if the solution is unique, it is not necessarily
continuous in #. As a result, the existence of the central path is not always guaranteed.
We define the (multivalued) mapping U : (0, # S(R n
(2)
++ ) is the set of all subsets of R n
++ , the positive orthant
of R n . The main contribution of this paper is to describe several su#cient conditions
which ensure that the multivalued mapping U(#) has the following desirable
properties.
(a) U(# for each # (0, #).
(b) For any fixed - # > 0, the set #(0,-#] U(#) is bounded.
(c) If U(#, then U(#) is upper-semicontinuous at #. (That is, for any su#-
ciently small # > 0, we have that #= U(# U(#B for all # su#ciently close to
#, where 1} is the Euclidean unit ball.)
(d) If U(-) is single-valued, then U(#) is continuous at # provided that U(#.
If the mapping U(-) satisfies properties (a), (b), and (c), then the set
can be viewed as an "interior band" associated with the solution set of the NCP.
The "interior band" can be viewed as a generalization of the concept of the central
path. Indeed, if U(-) satisfies properties (a), (b), and (d), then the set #(0,#) U(#)
coincides with the central path of the NCP.
There exist several ways of generating the central path of the NCP, including
maximal monotone methods [14, 30], minimization methods [31], homeomorphism
techniques [6, 14, 15, 25, 33], the parameterized Sard theorem [42], and weakly univalent
properties of continuous functions [13, 35, 37]. In this paper, we develop a
di#erent method for the analysis of the existence of the central path. By means of
the homotopy invariance property of the degree and a newly introduced concept of
interior-point-exceptional family for continuous functions, we establish an alternative
theorem for the nonemptyness of the mapping U(#). For a given # > 0, the result
states that there exists either an interior-point-exceptional family for f or U(#.
Consequently, to show the nonemptyness of the mapping U(-), it is su#cient to verify
conditions under which the function f possesses no interior-point-exceptional family
for any # > 0. Along with this idea, we provide several su#cient conditions that
guarantee the aforementioned desirable properties of the multivalued mapping U(-).
PROPERTIES OF A MULTIVALUED MAPPING 573
These su#cient conditions are related to several classes of (nonmonotone) functions
such as semimonotone, quasi-P # -, P(#)-, and exceptionally regular maps. The
results proved in the paper include several known results on the central path as special
instances.
This paper is organized as follows. In section 2, we introduce some definitions
and some basic results that will be utilized in the paper. In section 3, we show
an essential alternative theorem that is useful in later derivations. In section 4, we
establish some su#cient conditions to guarantee the nonemptyness, boundedness, and
upper-semicontinuity of the map U(#), and the existence of the central path. Some
concluding remarks are given in section 5.
Notations: R n
(respectively, R n
denotes the space of n-dimensional real vectors
with nonnegative components (respectively, positive components), and R n-n stands
for the space of n - n matrices. For any x # R n , we denote by #x# the Euclidean
norm of x, by x i the ith component of x for the vector whose
ith component is max{0, x i }. When x # R n
(R n
++ ), we also write it as x # 0
for simplicity.
2. Preliminaries. We first introduce the concept of an E 0 -function, which is
a generalization of an E 0 -matrix, i.e., semimonotone matrix, (see [8]). Recall that
an is said to be an E 0 -matrix if for any 0 #= x # 0, there exists a
component x i > 0 such that (Mx) i # 0. M is a strictly semimonotone matrix if for
any 0 #= x # 0, there exists a component x i > 0 such that (Mx) i > 0.
Definition 2.1. A function f : R n
R n is said to be an E 0 -function (i.e.,
semimonotone function) if for any x #= y and x # y in R n , there exists some i such
that x i > y i and f i (x) # f i (y). f is a strictly semimonotone function if for any x #= y
and x # y in R n , there exists some i such that x i > y i and f i (x) > f i (y).
It is evident that is an E 0 -function
if and only if M is an E 0 -matrix. We recall that a function f is said to be a P 0 (P)-
function if for any x #= y in R n
Clearly, a P 0 -function is an E 0 -function. However, the converse is not true (see [8,
Example 3.9.2]). Thus the class of E 0 -functions is larger than that of P 0 -functions.
Definition 2.2. (D1) [23, 24]. A map f : R n
R n is said to be quasi monotone
if for x #= y in R n , f(y) T implies that f(x) T
R n is said to be a P # -map if there exists a scalar
# 0 such that for any x #= y in R n we have
where
I
I - (x,
[26]. M is said to be a P # -matrix if there exists a scalar # 0 such that
Clearly, for a linear map is a P # -map if and only if M is a
showed that the class of P # -matrices coincides with the class
of su#cient matrices [8, 9]. A new equivalent definition of the P # -matrix is given in
[46]. The next concept is a generalization of the quasi monotone function and the
Definition 2.3. [46] A function f : R n
R n is said to be a quasi-P # -map if
there exists a constant # 0 such that the following implication holds for all x #= y
in R n .
defined by (3).
From the above definition, it is evident that the class of quasi-P # -maps includes
quasi monotone functions and P # -maps. (see [46] for details). The following concept
of a P (#)-map is also a generalization of the P # -map. In [46], it is pointed out
that monotone functions and P # -maps are special cases of P(#)-maps.
Definition 2.4. [46] A mapping f : R n
R n is said to be a P(#)-map if
there exist constants # 0, # 0, and 0 # < 1 such that the following inequality
holds for all x #= y in R
1#i#n
1#i#n
The concept of exceptional regularity that we are going to define next has a close
relation to such concepts as copositive, R 0 -, P 0 -, and E 0 -functions. It is shown that
the exceptional regularity is a weak su#cient condition for the nonemptyness and the
boundedness of the mapping U(#) (see section 4.4 for details).
Definition 2.5. Let f be a function from R n into R n . f is said to be exceptionally
regular if, for each # 0, the following complementarity problem has no solution of
norm 1:
The following two results are employed to prove the main result of the next
section. Let S be an open bounded set of R n . We denote by S and #(S) the closure
and boundary of S, respectively. Let F be a continuous function from S into R n . For
any y # R n such that y # F (#(S)), the symbol deg(F, S, y) denotes the topological
degree associated with F, S, and y (see [34]).
Lemma 2.1. [34] Let S # R n be an open bounded set and F, G be two continuous
functions from S into R n .
(i) Let the homotopy H(x, t) be defined as
and let y be an arbitrary point in R n . If y /
then deg(G, S,
(ii) If deg(F, S, y) #= 0, then the equation F y has a solution in S.
The following upper-semicontinuity theorem of weakly univalent maps is due to
Ravindran and Gowda [35].
PROPERTIES OF A MULTIVALUED MAPPING 575
Lemma 2.2. [35] Let g : R n
R n be weakly univalent; that is, g is continuous
and there exist one-to-one continuous functions
uniformly on every bounded subset of R n . Suppose that q # R n such that g -1 (q # ) is
nonempty and compact. Then for any given scalar # > 0 there exists a scalar # > 0
such that for any weakly univalent function h : R n
R n and for any q # R n with
sup
-#
we have
where B denotes the open unit ball in R n
3. Interior-point-exceptional family and an alternative theorem. We
now introduce the concept of the interior-point-exceptional family for a continuous
function, which brings us to a new idea, to investigate the properties of the mapping
U(#) defined by (2), especially the existence of the central path for NCPs. This
concept can be viewed as a variant of the exceptional family of elements which was
originally introduced to study the solvability of complementarity problems and variational
inequalities [19, 20, 36, 43, 44, 45, 46].
Definition 3.1. Let f : R n
R n be a continuous function. Given a scalar
# > 0, we say that a sequence {x r
++ is an interior-point-exceptional
family for f if #x r
# as r # and for each x r there exists a positive number
x r
for all
Based on the above concept, we can prove the following result which plays a key
role in the analysis of the paper.
Theorem 3.1. Let f be a continuous function from R n into R n . Then for each
there exists either a point x(#) such that
or an interior-point-exceptional family for f .
Proof. Let F be the Fischer-Burmeister function of f
defined by
It is well known that x solves the NCP if and only if x solves the equation F
Given # > 0, we perturb F (x) to F # (x) given by
It is easy to see that x(#) solves the equation F # only if x(#) satisfies
the system (5). We now consider the convex homotopy between the mapping F # (x)
and the identity mapping, that is,
576 YUN-BIN ZHAO AND GEORGE ISAC
Let r > 0 be an arbitrary positive scalar. Consider the open bounded set S
r}. The boundary of S r is given by #S There are
only two cases.
Case 1. There exists a number r > 0 such that 0 /
[0, 1]}. In this case, by (i) of Lemma 2.1, we have that deg(I, S r ,
where I is the identity mapping. Since deg(I, S r , 1, from the above equation and
(ii) of Lemma 2.1, we deduce that the equation F # has a solution, denoted by
x(#), which satisfies the system (5).
Case 2. For each r > 0, there exists some point x r
#S r and t r # [0, 1] such that
then the above equation reduces to F #
implies that x(#) := x r satisfies the system (5).
We now verify that t r #= 1. In fact, if t 0, then from (7) we
have that x which is impossible since x r
#S r .
Therefore, it is su#cient to consider the case of 0 < t r < 1 for all r > 0. In
this case, it is easy to show that f actually has an interior-point-exceptional family.
Indeed, in this case, (7) can be written as
x r
Squaring both sides of the above and simplifying, we have
x r
1), the above equation implies that x r
We see from the above equation that
x r
We further show that x r
++ . In fact, it follows from (8) that
x r
On the other hand, by using (9) we obtain
x r
x r
Combining (10) and the above equation yields x r
++ . Since #x r
it is clear
that #x r
# as r #. Consequently, the sequence {x r
} is an interior-point-
exceptional family for f .
The above result shows that if f has no interior-point-exceptional family for
each # > 0, then property (a) of the mapping U(-) holds. From the result, it is
interesting to study various practical conditions under which a continuous function
does not possess an interior-point-exceptional family for every # (0, #). In the
next section, we provide several such conditions ensuring the aforementioned desirable
properties of the mapping U(-).
PROPERTIES OF A MULTIVALUED MAPPING 577
4. Su#cient conditions for properties of U(-).
4.1. -function. In this section, we prove that the multivalued mapping U(-)
has properties (a) and (b) if f is a continuous E 0 -function satisfying a certain properness
condition. Moreover, if F # (x) given by (6) is weakly univalent, then property (c)
also holds. Applied to P 0 complementarity problems, this existence result extends a
recent result due to Gowda and Tawhid [13]. The following lemma is quite useful.
Lemma 4.1. Let f : R n
R n be an E 0 -function. Then for any sequence
++ with #u k
#, there exist an index i and a subsequence of {u k
denoted by {u k j
}, such that u k j
Proof. This proof has appeared in several works, see [11, 13, 35, 38]. Let {u k
++ be a sequence satisfying #u k
#. Choosing a subsequence if necessary, we
may suppose that there exists an index set I # {1, . , n} such that u k
for each
i } is bounded for each i /
R n be a vector constructed as
follows:
Thus,
} is a bounded sequence. Clearly, u k
is an E 0 -function,
there exist an index i # I and a subsequence of {u k
}, denoted by {u k j
}, such that
Note that the right-hand side of the above inequality is bounded. The desired result
follows.
To show the main result of this subsection, we will make use of the following
assumption which is weaker than several previously known conditions.
Condition 4.1. For any sequence {x k
satisfying
# and [-f(x k
# 0, and
(ii) for each index i with x k
i #, the corresponding sequence {f i
above, and
(iii) there exists at least one index i 0 such that x k
it holds that
1#i#n
for some subsequence {x k l
As we see in the following result the above condition encompasses several particular
cases; we omit the details.
Proposition 4.1. Condition 4.1 is satisfied if one of the following conditions
holds.
(C1) For any positive sequence {x k
++ with #x k
# and [-f(x k
0, it holds that max 1#i#n x k l
subsequence {x k l
(C2) For any sequence {x k
++ with #x k
# and min 1#i#n f i
0, it holds that max 1#i#n x k l
subsequence {x k l
[22, 29] For any sequence {x k
} with #x k
#,
# 0, and
# 0, it holds that
lim inf
578 YUN-BIN ZHAO AND GEORGE ISAC
[13] For any sequence {x k
} with #x k
#,
lim inf
min 1#i#n x k
# 0, and lim inf
there exist an index j and a subsequence {x k l
} such that x k l
is a R 0 -function.
monotone and the NCP is strictly feasible.
is a uniform P-function.
Remark 4.1. The condition (C1) of the above proposition is weaker than each of
the conditions (C2) through (C7). (C2) is weaker than each of the conditions (C4)
through (C7). The concept of the R 0 -function, a generalization of the R 0 -matrix [8],
was introduced in [39] and later modified in [6].
In what follows, we show under a properness condition that the short "interior
band" #(0,-#] U(#) is bounded for each given -
# > 0. The boundedness is important
because it implies that the sequence {x(# k )}, where
is bounded and each accumulation point of the sequence is a solution to the NCP
provided that f is continuous. We impose the following condition on f .
Condition 4.2. For any positive sequence {x k
++ such that #x k
#,
and the sequence {f i is bounded for each index i with
#, it holds that
1#i#n
for some subsequence {x k l
Clearly, Condition 4.2 is weaker than Condition 4.1 and thereby weaker than all
conditions listed in Proposition 4.1. We now prove the boundedness of the short
"interior band" under the above condition.
Lemma 4.2. Suppose that Condition 4.2 is satisfied. If U(# for each # > 0,
then for any -
# > 0 the set
#(0,-#] U(#) is bounded, i.e., property (b) holds. Particu-
larly, U(#) is bounded for each # > 0.
Proof. Suppose that there exists some -
#(0,-#] U(#) is unbounded.
Then there exists a sequence {x(# k )}, where # k # (0, -
#], such that #x(# k )# as
and that
for all
Thus, for each i such that x i #, the sequence {f i (x(# k ))} is bounded. By
Condition 4.2, we deduce that there exists a subsequence {x(# k l )} such that
1#i#n
This is a contradiction since x i
# for all
The main result on E 0 -functions is given as follows. Even for P 0 -functions, this
result is new.
Theorem 4.1. Suppose that f is a continuous E 0 -function and Condition 4.1 is
satisfied. Then the properties (a) and (b) of the mapping U(#) hold. Moreover, if F # (x)
defined by (6) is weakly univalent in x, then the mapping U(-) is upper-semicontinuous,
i.e., property (c) also holds.
PROPERTIES OF A MULTIVALUED MAPPING 579
Proof. To prove property (a), by Theorem 3.1, it su#ces to show that there exists
no interior-point-exceptional family of f for any # > 0. Assume to the contrary that
for certain # > 0 the function f has an interior-point-exceptional family {x r
#x r
#, {x r
++ , and f is an E 0 -function, by Lemma 4.1 there exist some
index m and a subsequence {x r j
}, such that x r j
From (4), we have
bounded below, the right-hand side of the above
equation is bounded below. It follows that lim j# - r
On the other hand, we note that for any 0 < - < 1 the function
# --
-#
is monotonically decreasing with respect to the variable t # (0, #). Passing through a
subsequence, we may suppose that there exists an index set I # {1, . , n} such that
i } is bounded for each i /
# I.
# I, then there exists some scalar C > 0 such that x r j
#(t) is decreasing and - r j # 1, we have
Thus, for all su#ciently large j, we have
# I.
using (4) and the facts - r
#, we have
which implies that
Therefore, [-f(x r
it follows from (4) that
which implies that {f i (x r j )} is bounded above for all i # I. Since m # I and {f m
is bounded below, the sequence {f m (x r j )} is indeed bounded. From Condition 4.1,
there is a subsequence of {x r j
denoted also by {x r j
}, such that
1#i#n
However, from (4) we have
for all i # {1, . , n}. This is a contradiction. Property (a) of U(#) follows.
Since Condition 4.1 implies Condition 4.2, the boundedness of the set
follows immediately from Lemma 4.2. It is known that x(# U(#) if and only if x(#)
is a solution to the equation F #
# (0). Since U(#) is bounded,
the set F -1
# (0) is bounded (in fact, compact, since f is continuous). If F # (x) is weakly
univalent in x, by Lemma 2.2, for each scalar # > 0 there is a # > 0 such that for any
weakly univalent function h : R n
sup
x#
-#
we have
It is easy to see that for the given # > 0 there exists a scalar # > 0 such that
sup
x#
-#
Setting h(x) := F # (x) in (13) and (14), we obtain that #= F -1
for all |#, i.e., U(# U(#B for all # su#ciently close to #. Thus, U(#)
is upper-semicontinuous.
Ravindran and Gowda [35] showed that if f is a P 0 -function, then F # (x) given by
(6) is a P-function in x, and hence the equation F # has at most one solution
x(#). In this case, the upper-semicontinuity of U(-) reduces to the continuity of x(#).
By the fact that every P 0 -function is an E 0 -function and is weakly univalent, we have
the following result from Theorem 4.1.
Corollary 4.1. Suppose that f : R n
R n is a continuous P 0 -function and
Condition 4.1 is satisfied. Then the central path exists and any slice of it is bounded,
i.e., for each # > 0 there exists a unique x(#) satisfying the system (1), x(#) is continuous
on (0, #), and the set {x(# (0, -
#]} is bounded for each -
When f is a P 0 -function, Gowda and Tawhid [13, Theorem 9] showed that the
(long) central path exists if condition (C4) of Proposition 4.1 is satisfied. Corollary 4.1
can serve as a generalization of the Gowda and Tawhid result. It is worth noting that
the consequences of Corollary 4.1 remain valid if condition (C1) or (C2) of Proposition
4.1 holds.
4.2. Quasi-P # -maps. The concept of the quasi-P # -map that is a generalization
of the quasi monotone function and the P # -map was first introduced in [46] to study
the solvability of the NCP. Under the strictly feasible assumption as well as the
following condition, we can show the nonemptyness and the boundedness of U(-) if f
is a continuous quasi-P # -map .
Condition 4.3. For any sequence {x k
++ such that
#, lim
and {f(x k )} is bounded, it holds that
1#i#n
for some subsequence {x k l
PROPERTIES OF A MULTIVALUED MAPPING 581
Clearly, the above condition is weaker than Conditions 4.1 and 4.2. It is also
weaker than Condition 3.8 in [4] and Condition 1.5(iii) in [25]. The following is the
main result of this subsection.
Theorem 4.2. Let f be a continuous quasi-P # -map with the constant # 0 (see
Definition 2.3). Suppose that Condition 4.3 is satisfied. If the NCP is strictly feasible,
then property (a) of U(#) holds. Moreover, if Condition 4.2 is satisfied, then property
(b) holds, and if F # (x) is weakly univalent in x, then property (c) also holds.
While the nonemptyness of U(#) is ensured under Condition 4.3, it is not clear if
the boundedness of U(#) can follow from this condition. However, from the implications
Condition 4.1# Condition 4.2 # Condition 4.3, we have the next consequence.
Corollary 4.2. Suppose that f is a continuous quasi-P # -map and F # (x) is
weakly univalent in x. If the NCP is strictly feasible and Condition 4.1 or 4.2 is
satisfied, then the mapping U(-) has properties (a), (b), and (c).
The proof of Theorem 4.2 is postponed until we have proved two technical lemmas.
Lemma 4.3. Let f satisfy Condition 4.3. Assume that {x r
} r>0 is an interior-
point-exceptional family for f . If there exists a subsequence of {x r
}, denoted by
{x rk
}, such that for some 0 < # < 1,
lim
#x rk
then we have
lim
1#i#n
x rk
Proof. Suppose that {x rk
} is an arbitrary subsequence of {x r
} such that (15)
holds. Since #(t) defined by (11) is decreasing on (0, #), for each i # {1, . , n} we
have
1#i#n
x rk
min 1#i#n x rk
and
1#i#n
x rk
Suppose to the contrary that there exists a subsequence of {x rk
denoted also by
{x rk
}, such that min 1#i#n x rk
is a constant. We
derive a contradiction. Indeed, since - rk - 1
< 0, from (16) we have
min 1#i#n x rk
# for all
From (17) and the above relation, we obtain
1#i#n
x rk
Since #x rk
#, we deduce from (15) that
lim
1#i#n
x rk
Therefore, it follows from (18) that there exists a scalar c such that c # f i
for all Condition 4.3, there exists a
subsequence of {x rk
denoted still by {x rk
}, such that max 1#i#n x rk
However, from (12) we have that x rk
This is a
contradiction.
Lemma 4.4. Let f satisfy Condition 4.3. Assume that {x r
} is an interior-point-
#-exceptional family for f . Let u > 0 be an arbitrary vector in R n . Then for any
subsequence {x rk
(where r k # as k #) there exists a subsequence of {x rk
denoted still by {x rk
}, such that f(x rk
su#ciently large k.
Proof. Let {x rk
} be an arbitrary subsequence of {x r
(where r k # as k #).
By using (4) we have
#x rk
x rk
#x rk
x rk
# .
We suppose that f(x rk
su#ciently large k. We derive a contra-
diction. From (19), we have
#x rk
Since #x rk
#, for all su#ciently large k we have
#x rk
which implies that
lim
#x rk
#x rk
for any scalar 0 < # < 1. Thus, we see from Lemma 4.3 that
min
1#i#n
x rk
Notice
#x rk
for all su#ciently large k. From (19), (20), and the above inequality, we have
x rk
min 1#i#n x rk
PROPERTIES OF A MULTIVALUED MAPPING 583
for all su#ciently large k. This is a contradiction.
We are now ready to prove the results of Theorem 4.2.
Proof of Theorem 4.2. To show property (a) of the mapping U(#), by Theorem
3.1, it su#ces to show that f has no interior-point-exceptional family for any # > 0.
Assume to the contrary that there exists an interior-point-exceptional family for f ,
denoted by {x r
}. By the strict feasibility of the NCP, there is a vector u > 0 such
that f(u) > 0. Consider two possible cases.
Case (A). There exists a number r 0 > 0 such that
1#i#n
In this case, the index set I
#,
it is easy to see that
for all su#ciently large r. Since f is a quasi-P # -map and I is empty, the
above inequality implies that f(x r
su#ciently large r. How-
ever, by Lemma 4.4 there exists a subsequence of {x r
}, denoted by {x rk
}, such that
su#ciently large k. This is a contradiction.
Case (B). There exists a subsequence of {x r
} denoted by {x r j
as j #, such that
1#i#n
By using (4), for each i we have
# .
There exist a subsequence of {x r j
denoted also by {x r j
}, and a fixed index m such
that
1#i#n
For each i such that x r j
#, (21) implies that A (r j )
j, we deduce that {x r j
m} is bounded, i.e., there is a constant - # such that 0 < x r j
for all j.
um , setting in (21), we have
um # 1# 1
If um < x r j
#, setting in (21), we obtain
584 YUN-BIN ZHAO AND GEORGE ISAC
We consider two subcases, choosing a subsequence whenever it is necessary.
Subcase 1. - r j # 1. From (22) and (23), for all su#ciently large j we have
um
Thus, for all su#ciently large j, we obtain
1#i#n
um /2)}
The last inequality above follows from the fact that f(u) > 0, {x r j
++ , and
#. Since f is a quasi-P # -map, the above inequality implies that f(x r
su#ciently large j, which is impossible according to Lemma 4.4.
Subcase 2. There exists a subsequence of {- r j }, denoted also by {- r j }, such that
1. In this case, from (22) and (23), we have
# .
It follows from (4) that
1#i#n
.
We now show that T (r su#ciently large j.
noting that - r j # and #x r j
#, we obtain
), by the same argument as the above, we can
show that
for all su#ciently large j. Thus, by the quasi-P # -property of f , we deduce from
su#ciently large j. It is a contradiction
since {x r j
#, and f(u) > 0.
The above contradictions show that f has no interior-point-exceptional family
for each # > 0. By Theorem 3.1, the set U(# for any # > 0. The boundedness of
PROPERTIES OF A MULTIVALUED MAPPING 585
the short "interior band " follows from Lemma 4.2, and the upper-semicontinuity of
U(#) follows easily from Lemma 2.2.
The class of quasi-P # -maps includes the quasi monotone functions as particular
cases. The following result is an immediate consequence of Theorem 4.2.
Corollary 4.3. Suppose that f is a continuous quasi monotone (in particular,
pseudomonotone) function, and the NCP is strictly feasible.
(i) If Condition 4.3 is satisfied, then property (a) of U(#) holds.
(ii) If Condition 4.2 is satisfied, then properties (a) and (b) of U(#) hold.
In the case when F # (x) is univalent (continuous and one-to-one) in x, the equation
has at most one solution. Combining this fact and Theorem 4.2, we have
the following result concerning the existence of the central path of the NCP. To our
knowledge, this result can be viewed as the first existence result on the central path
for the NCP with a (generalized) quasi monotone function. Up to now, there is
no interior-point type algorithms designed for solving (generalized) quasi monotone
complementarity problems.
Corollary 4.4. Let f be a quasi-P # -map, and F # (x) is univalent in x. If the
NCP is strictly feasible and Condition 4.2 is satisfied, then the central path exists and
the set {x(# (0, -
#]} is bounded for any given - # > 0.
Particularly, if f is a P 0 -function, then F # (x) is univalent in x (see [35]). We have
the following result.
Corollary 4.5. Let f be a continuous P 0 and quasi-P # -map. If the NCP is
strictly feasible and Condition 4.2 is satisfied, then the conclusions of Corollary 4.4
are valid.
4.3. P (#)-maps. It is well known (see [14, 25, 30, 31]) that the monotonicity
combined with strict feasibility implies the existence of the central path. In this
section, we extend the result to a class of nonmonotone complementarity problems.
Our result states that if f is a P(#) and P 0 -map (see Definition 2.4), the central
path exists provided that the NCP is strictly feasible. This result gives an answer
to the question "What class of nonlinear functions beyond P # -maps can ensure the
existence of the central path if the NCP is strictly feasible?" We first show properties
of the mapping U(-) when f is a P (#)-map.
Theorem 4.3. Let f be a continuous P (#)-map. If the NCP is strictly fea-
sible, then properties (a) and (b) of U(#) hold. Moreover, if F # (x) is weakly univalent
in x, property (c) also holds.
Proof. Suppose that there exists a scalar # > 0 such that f has an interior-point-
#-exceptional family denoted by {x r
++ and #x r
# as r #,
there exist some p and a subsequence denoted by {x r j
such that #x r j
# and
1#i#n
Clearly, x r j
On the other hand, there exists a subsequence of {x r j
denoted also by {x r j
}, such that for some fixed index m and for all j we have
1#i#n
By the definition of the P(#)-map, we have
586 YUN-BIN ZHAO AND GEORGE ISAC
1#i#n
1#i#n
- u# .
From (4), we have that f p
p , and hence
It is easy to see that
Combining (25) and (26) leads to
From
min := min
1#i#n
we deduce that
min # as j #.
We now show that {x r j
m} is bounded. Assume that there exists a subsequence of {x r j
denoted still by {x r j
m}, such that x r j
#. Then, from (21), we have
and hence for all su#ciently large j we have
1#i#n
By (27) and the above relation, we obtain
min # as j #.
However, since f is a P(#)-map, we have
min #,
which contradicts (28). This contradiction shows that the sequence {x r j
m} is bounded.
By using (4) and (24), we have
- u# .
PROPERTIES OF A MULTIVALUED MAPPING 587
Multiplying both sides of the above inequality by 1/(x r j
rearranging terms,
and using (26), we have
For all su#ciently large j, the left-hand side of the above inequality is negative, but
the right-hand side tends to f p (u) > 0 as j #. This is a contradiction. The
contradiction shows that f has no interior-point-exceptional family for every # > 0.
By Theorem 3.1, property (a) of U(#) follows. The proof of the boundedness of the
set
#(0,-#] U(#) is not straightforward. It can be proved by the same argument as
the above. Indeed, we suppose that {x(# k )} 0<#k<-#(0,-#] U(#) is an unbounded
sequence. Replacing {x r j
} by {x(# k )}, using
instead of (4), and repeating the aforementioned proof, we can derive a contradic-
tion. The upper-semicontinuity of U(-) can be obtained by Lemma 2.2. The proof is
complete.
The class of P(#)-maps includes several particular cases such as P (#, 0)-,
P(#, 0, 0)-, and P(0, #)-maps. It is shown in [46] that the class of P(#, 0, 0)-maps
coincides with the class of P # -maps. Therefore, f is said to be a P # -map if and only
if there exists a nonnegative scalar # 0 such that
1#i#n
1#i#n
Particularly, a matrix M # R n-n is a P # -matrix if and only if there is a constant
# 0 such that
1#i#n
1#i#n
This is an equivalent definition of the concept of a P # -matrix (su#cient matrix) introduced
by Kojima et al. [26] and Cottle, Pang, and Venkateswaran [9]. The following
result follows immediately from Theorem 4.3.
Corollary 4.6. Let f be a continuous P 0 and P(#)-map. If the NCP is
strictly feasible, then the central path exists and any slice of it is bounded.
It is worth noting that each P # -map is a P 0 and a P(#)-function. The following
result is a straightforward consequence of the above corollary.
Corollary 4.7. Let f be a continuous P # -map. If the NCP is strictly feasible,
then the central path exists and any slice of it is bounded.
It should be pointed out that P # -maps are also special instances of quasi-P # -
maps. A result similar to Corollary 4.3 can be stated for P # -maps. However, as we
have shown in Corollary 4.7, the additional conditions such as Conditions 4.1, 4.2,
and 4.3 are not necessary for a P # -map to guarantee the existence of the central path.
While P # -maps and quasi monotone functions are contained in the class of quasi-P # -
maps, Zhao and Isac [46] gave examples to show that a P # -map, in general, is not a
quasi monotone function, and vice versa.
588 YUN-BIN ZHAO AND GEORGE ISAC
4.4. Exceptionally regular functions. In section 4.1, we study the properties
of the mapping U(#) for -functions satisfying a properness condition, i.e., Condition
4.1. In sections 4.2, we show properties of U(#) for quasi-P # -maps under the
strictly feasible condition as well as some properness conditions. In the above section,
properness assumptions are removed, and properties of U(#) for P (#)-maps are
proved under the strictly feasible condition only. In this section, removing both the
strictly feasible condition and properness conditions, we prove that properties of U(#)
hold if f is an exceptionally regular function. The exceptional regularity of a function
(see Definition 2.5) was originally introduced in [46] to investigate the existence of a
solution to the NCP.
Definition 4.1. [16] A map v : R n
R n is said to be positively homogeneous
of degree # > 0 if
the above concept reduces to the standard concept of positive
homogeneity. Under the assumption of positively homogeneous of degree # > 0, we
can show that properties (a) and (b) of U(#) hold if f is exceptionally regular. See
the following result.
Theorem 4.4. Let f be a continuous and exceptionally regular function from
R n into R n . If positively homogeneous of degree # > 0, then
properties (a) and (b) of U(#) hold. Moreover, if F # (x) is weakly univalent, property
(c) also holds.
Proof. Suppose that there is a scalar # > 0 such that f has an interior-point-
exceptional family {x r
We derive a contradiction. Indeed, since G(x) is positively
homogeneous of degree # > 0, we have
#) - f(0)).
Without loss of generality, assume that x r /#x r
x. From the above relation, we
have
lim
r#
From (4), we have2
x r
for all
# and x r
we deduce that x r
for each i # I (-x). We now show that
lim
#x r
for some -
It is su#cient to show the existence of the above limit. Indeed, for
each using (30) and (29) we have
lim
#x r
r#
#x r
x r
#x r
x r
Thus, (31) holds, with
PROPERTIES OF A MULTIVALUED MAPPING 589
Now, we consider the case of i /
(-x). In this case, -
using (4), (31), and
(29), we see from x r
# 0 that
r#
x r
r#
#x r
r#
#x r
#x r
i.e.,
Combining (32) and the above relation implies that f is not exceptionally regular.
This is a contradiction. The contradiction shows that f has no interior-point-
exceptional family for each # > 0, and hence property (a) of U(#) follows from Theorem
3.1. Property (b) of U(#) can be easily proved. Actually, suppose that there exists
a sequence {x(# k )} 0<#k<-# with #x(# k )#, where loss of
generality, let x(# k )/#x(# k )# -
1. As in the proof of (29) we have
Therefore,
which contradicts the exceptional regularity of f(x).
It is not di#cult to see that a strictly copositive map and a strictly semimonotone
function are special cases of exceptionally regular maps. Hence, we have the following
result.
Corollary 4.8. Suppose that positively homogeneous
of degree # > 0. Then conclusions of Theorem 4.4 are valid if one of the following
conditions holds.
(i) f is an E 0 -function, and for each 0 #= x # 0 there exists an index i such that
(ii) f is strictly copositive, that is, x
(iii) f is a strictly semimonotone function.
Proof. Since each of the above conditions implies that f(x) is exceptionally reg-
ular, the result follows immediately from Theorem 4.4.
Motivated by Definition 2.5, we introduce the following concept.
4.2. M # R n-n is said to be an exceptionally regular matrix if for
all #I is an R 0 -matrix.
It is evident that an exceptionally regular matrix is an R 0 -matrix, but the converse
is not true. The following result is an immediate consequence of Theorem 4.4 and its
corollary.
Corollary 4.9. Let is an arbitrary vector
in R n . If one of the following conditions is satisfied, then properties (a) and (b) of
the mapping U(#) hold:
590 YUN-BIN ZHAO AND GEORGE ISAC
(i) M # R n-n is an exceptionally regular matrix.
(ii) M is a strictly copositive matrix.
(iii) M is a strictly semimonotone matrix.
(iv) M is an E 0 -matrix, and for each 0 #= x # 0 there exists an index i such that
(possibly, (Mx) i < 0).
Furthermore, if M is also a P 0 -matrix, then the central path of a linear complementarity
problem exists and any slice of it is bounded.
The R 0 -property of f has played an important role in the complementarity theory.
We close this section by considering this situation. The concept of a nonlinear R 0 -
function was first introduced by Tseng [38] and later modified by Chen and Harker
[6]. We now give a definition of the R 0 -function that is di#erent from those in [38]
and [6].
R n is said to be an R 0 -function if is the unique
solution to the following complementarity problem:
This concept is a natural generalization of the R 0 -matrix [8]. In fact, for the linear
function it is easy to see that f is an R 0 -function if and only if M is
an R 0 -matrix. In the case when f is an E 0 -function, we have shown in Theorem 4.1
that there exists a subsequence {- rk } such that - rk # 1. Moreover, if G is positively
homogeneous, then from (31) we deduce that -
using these facts and the
above R 0 -property and repeating the proof of Theorem 4.4, we have the following
result.
Theorem 4.5. Suppose that for each scalar t # 0 and x # R n ,
and that f is an E 0 and R 0 -function. Then the conclusions of Theorem 4.4 remain
valid. Moreover, if f is a P 0 and R 0 -function, the central path exists and any slice
of it is bounded.
5. Conclusions. We introduced the concept of the interior-point-exceptional
family for continuous functions, which is important since it strongly pertains to the
existence of an interior-point x(# U(#) and the central path, even to the solvability
of NCPs. By means of this concept, we proved that for every continuous NCP the set
U(#) is nonempty for each scalar # > 0 if there exists no interior-point-exceptional
family for f . Based on the result, we established some su#cient conditions for the
assurance of some desirable properties of the multivalued mapping U(#) associated
with certain nonmonotone complementarity problems. Since properties (a) and (b)
of U(#) imply that the NCP has a solution, the argument of this paper based on
the interior-point-exceptional family can serve as a new analysis method for the
existence of a solution to the NCP.
It is worth noting that any point in U(#) is strictly feasible, i.e., x(#) > 0 and
Therefore, the analysis method in this paper can also be viewed as a
tool for investigating the strict feasibility of a complementarity problem. In fact, from
Theorems 3.1, 4.1, 4.4, and 4.5, we have the following result.
Theorem 5.1. Let f be a continuous function. Then the complementarity problem
is strictly feasible whenever one of the following conditions holds.
(i) There exists a scalar # > 0 such that f has no interior-point-exceptional
family.
(ii) f is an E 0 -function and Condition 4.1 is satisfied.
positively homogeneous of degree # > 0 and f is
exceptionally regular.
PROPERTIES OF A MULTIVALUED MAPPING 591
is an E 0 and R 0 -matrix.
It should be pointed out that the results and the argument of this paper can
be easily extended to other interior-point paths. For instance, we can consider the
existence of the path
(where b and a > 0 are fixed vectors in R n ) first studied by Kojima, Megiddo, and
the above path reduces to the central path). This
path can be studied by the concept of interior-point-#(a, b)-exceptional family. For a
continuous
we say that a sequence {x r
++ is an interior-
b)-exceptional family for f if #x r
# as r #, and for each x r there
exists a positive number - r # (0, 1) such that for each i
x r
Using
and arguing as in the same proof of Theorem 3.1, we can show that for any # > 0 there
exists either a point x(#) satisfying (33) or an interior-point-#(a, b)-exceptional family
for f . This result enables us to develop some su#cient conditions for the existence of
the path (33).

Acknowledgments

. The authors would like to thank the referees and Professor
Jim Burke for their helpful suggestions and comments on an earlier version of this
paper, which helped the authors to correct some mistakes and improve the presentation
of the manuscript. They also thank Dr. Mustapha Ait Rami for his valuable
comments.



--R

The global linear convergence of a non-interior-point path following algorithm for linear

A global and local superlinear continuation-smoothing method for P 0 and R 0 NCP or monotone NCP
A Penalized Fischer-Burmeister NCP-Function: Theoretical Investigation and Numerical Results

Smooth approximations to
A. class of smoothing functions for nonlinear and mixed
The Linear Complementarity Problem


Beyond monotonicity in regularization methods for
Engineering and economic applications of
Existence and limiting behavior of trajectories associated with


A survey of theory
Global convergence of a class of non-interior-point algorithms using Chen-Harker-Kanzow functions for
Lecture Notes in Math.

Functions without exceptional families of elements and
Some nonlinear continuation methods for linear
New NCP-functions and their properties
Complementarity problems over cones with monotone and pseudomonotone maps
Seven kinds of monotone maps
Homotopy continuation methods for
A. Unified Approach to Interior Point Algorithms for Linear
A. new continuation method for
A. polynomial-time algorithm for linear
A new class of merit functions for the nonlinear complementarity problem
The complementarity problem for maximal monotone multifunctions
Pathways to the optimal set in linear programming
Interior path following primal dual algorithms
Properties of an interior-point mapping for mixed
Iterative Solution of Nonlinear Equations in Several Variables
Regularization of P 0
A. solution condition for

Growth behavior of a class of merit functions for the
An infeasible path-following method for monotone

An algorithm for the linear complementarity problem with a P 0
On Constructing Interior-Point Path-Following Methods for Certain Semimonotone Linear
Existence of a solution to nonlinear variational inequality under generalized positive homogeneity
Exceptional family of elements for a variational inequality problem and its applications


--TR

--CTR
Y. B. Zhao , D. Li, A New Path-Following Algorithm for Nonlinear P*Complementarity Problems, Computational Optimization and Applications, v.34 n.2, p.183-214, June      2006
generalized monotonicity;weakly univalent maps;nonlinear complementarity problems;interior-point-va-exceptional family;central path