On a New Homotopy Continuation Trajectory for Nonlinear Complementarity Problems.
Most known continuation methods for P 0 complementarity problems require some restrictive assumptions, such as the strictly feasible condition and the properness condition, to guarantee the existence and the boundedness of certain homotopy continuation trajectory. To relax such restrictions, we propose a new homotopy formulation for the complementarity problem based on which a new homotopy continuation trajectory is generated. For P 0 complementarity problems, the most promising feature of this trajectory is the assurance of the existence and the boundedness of the trajectory under a condition that is strictly weaker than the standard ones used widely in the literature of continuation methods. Particularly, the often-assumed strictly feasible condition is not required here. When applied to P * complementarity problems, the boundedness of the proposed trajectory turns out to be equivalent to the solvability of the problem, and the entire trajectory converges to the (unique) least element solution provided that it exists. Moreover, for monotone complementarity problems, the whole trajectory always converges to a least 2-norm solution provided that the solution set of the problem is nonempty. The results presented in this paper can serve as a theoretical basis for constructing a new path-following algorithm for solving complementarity problems, even for the situations where the solution set is unbounded.
Introduction
. We denote by R n the n-dimensional Euclidean space, R n
the nonnegative
orthant, and R n
++ the positive orthant. For simplicity, we also denote x 2 R n
(R n
by x - In this paper, all vectors are column vectors, and superscript T denotes
the transpose. e is the vector of all ones in R n : For any x 2 R n , kxk denotes the 2-norm
denotes the vector whose ith component is maxf0; x i g (respec-
tively, minf0; x i g): For any mapping g : R n ! R n and any subset D of R n , g \Gamma1 (D), unless
otherwise stated, denotes the set fx 2 R
Given a continuous mapping f the well-known complementarity problem
(abbreviated, CP(f)) is to determine a vector x satisfying
Let SOL cp (f) denote the solution set of the above problem. Define
We refer to S++ (f) as the set of strictly feasible points. There are several equivalent
equation-based reformulations of CP(f) reported in the literature. One of the well-known
forms is based on the following mapping:
Xy
It is easy to see that x   2 SOL cp (f) if and only if (x   ; y   ), where
is a solution of the system
This system provides us with a general theoretical framework for various efficient homotopy
continuation methods, including the interior-point methods. See, for example, Lemke
(1965), Lemke and Howson (1980), Kojima, Mizuno and Noma (1989, 1990), Kojima,
Megiddo and Noma (1991), Kojima, Megiddo, Noma and Yoshise (1991), Ye (1997), and
Wright (1997). Mor'e (1996) also used F(x; y) to study the trust-region algorithm for CP(f ).
The fundamental idea of a homotopy continuation method is to solve the problem by tracing
a certain continuous trajectory leading to a solution of the problem. The existence and the
boundedness of a continuation trajectory play an essential role in constructing the homotopy
continuation algorithms for the problem. The following two conditions are standard ones
widely used in the literature to ensure the existence and the boundedness of a continuation
trajectory. See, e.g. McLinden (1980), Megiddo (1989), Kojima, Mizuno and Noma (1989,
1990), Kojima, Megiddo and Noma (1991), Kojima, Megiddo and Mizuno (1993), Kanzow
(1996), Hotta and Yoshise (1999), Burke and Xu (2000), Qi and Sun (2000), and Hotta et
al. (1998).
Condition 1.1. (a) f is monotone on R n , i.e.,
(b) There is a strictly feasible point, i.e., S++ (f) 6= ;:
Condition 1.2. (a) f is a P 0 -function, that is,
(b) S++ (f) 6= ;:
(c) The set
is bounded for every compact subset D of R n
\Theta B++ (f); where
It is easy to see that Condition 1.1 implies Condition 1.2 (see, Kojima, Megiddo and Noma
(1991). Let (a; b) 2 R n
0: Kojima, Mizuno and Noma (1989, 1990) and
Kojima, Megiddo and Noma (1991) considered a family of the system of equations with a
a
0: (2)
Let (x(t); y(t)) denote a solution to the above system. If (x(t); y(t)) is unique for each t ? 0
and continuous in the parameter t, then the set
a
forms a continuous curve in R 2n
which is called the trajectory of solutions of the system
(2). As t ! 0, any accumulation point (-x; - y) of the trajectory, if exists, must be a solution
to CP(f ). Thus by tracing such a trajectory as t ! 0; we can obtain a solution of the
problem. In this paper, we say that a trajectory is bounded if any slice (subtrajectory) of
the trajectory, i.e., positive number, is bounded.
It should be noted that (3) includes several important particular situations. For example,
when the trajectory reduces to the one induced by the well-known Lemke's
method for linear complementarity problems (Lemke 1965, Lemke and Howson 1980). When
the trajectory (3) reduces to the central path based on which many interior-point
and non-interior-point algorithms are constructed. See, for example, Kojima, Mizuno
and Yoshise (1989), Kojima, Megiddo, Noma and Yoshise (1991), Ye (1997), Wright (1997),
Burke and Xu (1998, 1999, 2000).
For monotone maps and P 0 -functions, Kojima et al. (1990) and Kojima, Megiddo
and Noma (1991) proved the existence and the boundedness of the trajectory (3) under the
aforementioned Condition 1.1 and Condition 1.2, respectively. The strictly feasible condition
is indispensable to the existence and the boundedness of their continuation trajectories. In
fact, we give examples (see Section 6) to show that the trajectory (3) may not exist if
the strictly feasible condition fails to hold. It is well-known that Condition 1.1 implies
the existence and the boundedness of the central path (McLinden 1980, Megiddo 1989,
G-uler 1993). On the other hand, since each point on the central path is strictly feasible,
we deduce that for a monotone CP(f) the central path exists if and only if there exists
a strictly feasible point. This property actually holds for P   complementarity problems
(Kojima, Megiddo and Yoshise (1991), Zhao and Isac 2000b). Therefore, it is not possible
to remove the strictly feasible condition for those central path-based continuation methods
without destroying their convergence.
Recently, some non-interior point continuation methods have been intensively investigated
for solving CP(f) (Chen and Harker 1993, Kanzow 1996, Hotta and Yoshise 1999,
Burke and Xu 1998, 1999, 2000, Qi and Sun 2000, and Hotta et al. 1998). While these
algorithms start from a non-interior point, the strictly feasible condition is still assumed for
such a class of methods to ensure the existence of non-interior-point trajectories and the
convergence of algorithms. Specifically, Hotta and Yoshise (1999) considered the following
homotopy trajectory:
++ \Theta R 2n
++ \Theta R 2n is a given vector, and
where all algebraic operations are performed componentwise. Their analysis for the existence
and the boundedness of such a continuation trajectory also requires Condition 1.1 or
the one analogous to Condition 1.2 in which (c) of Condition 1.2 is replaced by
is bounded for every compact
subset D of range U(R n
++ \Theta R 2n
Hotta and Yoshise (1999) pointed out that their condition is not weaker than Condition
1.2.
Thus, most of the continuation methods in the literature, including both the interior-point
algorithms and the non-interior-point algorithms, are limited to solving the class of
complementarity problems satisfying Condition 1.2 or its similar versions. Since Condition
1.2 implies that the solution set of CP(f) is nonempty and bounded (see Section 4 for
details), it seems to be restrictive. Some continuation methods use other assumptions such
as the P 0 and R 0 (see, Burke and Xu 1998, Chen and Chen 1999, Zhao and Li 1998) which,
however, still imply the nonemptyness and boundedness of the solution set. It is worth
mentioning that Monteiro and Pang (1996) established several results on the existence of
certain interior-point paths for mixed complementarity problems. Restricted to CP(f ),
their results generalize and, to some extent, unify those already obtained for CP(f ). It is
easy to see, however, that the conditions used by Monteiro and Pang (1996) also imply the
boundedness of the solution set of the problems. In fact, the properness assumptions used
in Monteiro and Pang (1996), such as "uniformly norm coercive", imply that the solution
set of the problem is bounded.
Since the nonemptyness and boundedness of the solution set imply that the P 0 complementarity
problem must be strictly feasible (Corollary 5 in Ravindran and Gowda 1997 and
Corollary 3.14 in Chen et al. 1997), we conclude that most existing continuation methods
actually confine themselves to solve only the class of P 0 complementarity problems with
bounded solution sets, which are strictly feasible problems.
It is known that for monotone CP(f ), the strictly feasible condition is equivalent to the
nonemptyness and boundedness of the solution set of CP(f) (McLinden 1990, Chen et al.
1997, Ravindran and Gowda 1997). This result has been extended to P   complementarity
problems by Zhao and Li (2000) who showed that if f is a P   -function (see Definition 2.1
in the next section) the solution set of CP(f) is nonempty and bounded if and only if there
exists a strictly feasible point. In summary, we conclude that the following three conditions
are equivalent for P   complementarity problems.
ffl There exists a strictly feasible point, i.e., S++ (f) 6= ;:
ffl Solution set of CP(f) is nonempty and bounded.
ffl The central path exists and any slice of it is bounded.
Because of the dependence on the strictly feasible condition, most existing continuation
methods, when applied to a P 0 complementarity problem (in particular, a P   problem and
a monotone problem), fail to solve it if it is not strictly feasible (in this case, the solution
set of CP(f) is unbounded).
From the above discussion, a natural question arises: How to construct a homotopy
continuation trajectory such that its existence and boundedness do not require the strictly
feasible condition in the setting of P 0 -complementarity problems? At a cost of losing the
generality of the vector c 2 R n
in (2), a continuation trajectory, which does not need
the strictly feasible condition, does exist. In fact, Kojima et al. (1993) established a result
(Theorem 3.1 therein) which states that if a 2 R n
is fixed then for almost all b 2 R n
, the
trajectory (3) exists. However, their result cannot exclude a zero measure set on which a
trajectory fails to exist. A similar result is also obtained by Zhang and Zhang (1997).
In this paper, we propose a new homotopy formulation for the complementarity prob-
lem. Utilizing this formulation, we study the existence, boundedness and limiting behavior
of a new continuation trajectory which can serve as a theoretical basis for designing a new
path-following algorithm for CP(f) even when its solution set is unbounded. Our continuation
trajectory possesses several prominent features: (f 1 ) The Tihonov regularization
technique is used in the formulation of the homotopy mapping; (f 2 ) In the P 0 situation, the
proposed trajectory (a unique and continuous curve) always exists from arbitrary starting
point
assumption other than the continuity of the mapping f ,
and the boundedness of this trajectory only requires a condition that is strictly weaker than
(b) and (c) of Condition 1.2. Particularly, the strictly feasible condition is not assumed in
our derivation; (f 3 ) In the setting of P   complementarity problems, the boundedness of the
trajectory is equivalent to the solvability of the problem, i.e., the trajectory is bounded if
and only if the problem has a solution. Moreover, for monotone complementarity problems,
the whole trajectory converges to a least 2-norm solution provided that the solution set of
CP(f) is nonempty. This is a very desirable property of the homotopy continuation trajectory
with which we may design a continuation method (path-following method) to solve a
even when the solution set is not bounded. For semimonotone functions (in particular,
each accumulation point of the proposed trajectory turns out to be a weak
Pareto minimal solution (see Theorem 5.2). The above-mentioned properties essentially
distinguish the proposed continuation trajectory from the previous ones in the literature.
Since Tihonov regularization trajectory (see, Isac 1991, Venkateswaran 1993, Facchinei
1998, Facchinei and Kanzow 1999, Ravindran and Gowda 1997, Gowda and Tawhid 1999,
Sznajder and Gowda 1998, Tseng 1998, and Facchinei and Pang 1998) can be viewed as
an extreme variant of the proposed trajectory, some new properties of the regularization
trajectory (see Theorem 5.4) are also revealed as by-products from the discussion of this
paper.
The paper is organized as follows: In Section 2, we list some definitions and basic results
that will be utilized later. In Section 3, we give a new homotopy formulation for CP(f)
and prove a useful equivalent version of it. A useful alternative theorem is also shown. In
Section 4, we study the existence and the boundedness of a new continuation trajectory.
The limiting behavior of the trajectory is studied in Section 5. Two examples are given
in Section 6 to show that the central path and other interior-point trajectories studied by
Kojima et al. fail to exist if the strictly feasible condition is not satisfied. Based on the
proposed trajectory, a framework of a new path-following algorithm for CP(f) is also given
in Section 6. Conclusions are given in the last section.
2. Preliminaries. For reference purposes, we introduce some basic results and
definitions.
Let\Omega be a bounded open set in R n . The symbols
-\Omega and
@\Omega denote the closure
and boundary
respectively. Let v be a continuous function from
-\Omega into R n . For any
vector y 2 R n such that
the degree of v at y with respect
to\Omega is denoted by
The following result can be found in Lloyd (1978).
Lemma 2.1. (Lloyd 1978) (a) If v is injective on R n , then for any y
(b) If
then the equation y has a solution
(c) Let g be a continuous function from
The next result is an upper-semicontinuity theorem concerning weakly univalent maps
established recently by Ravindran and Gowda (1997). Since each P 0 -function must be
weakly univalent (Ravindran and Gowda 1997, Gowda and Sznajder 1999), the following
result is very helpful for the analysis in this paper.
Lemma 2.2. (Ravindran and Gowda 1997) 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   2 R n such that g \Gamma1 (q   )
is nonempty and compact. Then for any given " ? 0; there exists a scalar ffi ? 0 such that
for any weakly univalent function h and for any q with
sup
-\Omega
we have
where B denotes the open unit ball in R n
In particular, h \Gamma1 (q) and
are nonempty and uniformly bounded for q in a neighborhood of q   :
We now introduce two classes of functions.
Definition 2.1. (a): A function f is said to be a semimonotone function if for any
x 6= y in R n such that x \Gamma y - 0, there exists some i such that
(b): (Kojima, Megiddo, Noma and Yoshise (1991), Zhao and Isac 2000a) A function
is said to be a P   -function if there exists a constant - 0 such that
where
I ng
We note the following easily verifiable relations:
Monotone functions ' P   -functions ' P 0 -functions ' Semimonotone functions.
For a linear matrix and q 2 R n , it is evident that f
is a semimonotone function if and only if M is a semimonotone matrix Cottle et al. (1992),
and f is a P   -function if and only if M is a P   -matrix defined in Kojima, Megiddo, Noma
and Yoshise (1991). V-aliaho (1996) showed that the class of P   -matrices coincides with
that of sufficient matrices introduced in Cotlle et al. (1989). A new equivalent definition
for P   -function is given in Zhao and Isac (2000a).
3. A new homotopy formulation and an alternative theorem. Given a scalar
Xy
This map can be viewed as a perturbed version of F(x; y) defined by
(1) with the parameter - ? 0. Clearly, (x; y) 2 R 2n
such that F - (x; only if
Under suitable conditions, the solutions of the above system approach to a solution of
CP(f) as - ! 0: This is the basic idea of the well-known Tihonov regularization methods
for CP(f ). See, for example, Isac (1991), Venkateswaran (1993), Facchinei (1998), Facchinei
and Kanzow (1999), Ravindran and Gowda (1997), Gowda and Tawhid (1999), Sznajder
and Gowda (1998), Qi (2000), Tseng (1998), and Facchinei and Pang (1998).
R 2n be given by
Define the convex homotopy H : R n \Theta R n \Theta [0; 1] \Theta [0; 1) ! R 2n as follows:
We note that the above homotopy formulation has two important extreme cases. If
then the map (5) reduces to F - (x; y) which is used in Tihonov regularization
methods. If reduces to
which is investigated by Kojima et al. (1993) who proved that the above map is equivalent
to (2) under a suitable one-to-one transformation such as However, the version
of (6) is mathematically easier to be handled than (2). Let
and is easy to verify that (6) coincides with the homotopy formulation studied
by Zhang and Zhang (1997). Therefore, Zhang and Zhang's homotopy function is actually
a special case of that of Kojima et al. (1993).
the homotopy (5) is essentially different from previous ones in
the literature. We may treat the two parameters - and ' independently in general cases.
But for simplicity and convenience for designing algorithms, we use only one parameter by
setting satisfies the following properties:
is a continuous and strictly increasing function satisfying
An example of OE satisfying the above properties is is a fixed
positive number. Then (5) can be written as
Basing on the above homotopy, we consider the following system:
where the parameter ' 2 (0; 1): For given ' 2 (0; 1), we denote (x('); y(')) by a solution of
the above system, and consider the following set
If (x('); y(')) is unique for each ' 2 (0; 1) and continuous in '; the above set is called the
homotopy continuation trajectory generated by the system (8). We say that the trajectory
is bounded if for any scalar ffi 2 (0; 1); the set
is bounded. For any subsequence denoted by f(x(' k ); y(' k ))g ' T such that (x(' k ); y(' k
0; the cluster point must be a solution to CP(f)
(since f is continuous). Thus by tracing such a trajectory, if it exists, we may find a solution
to the problem.
In this paper, we study the existence, boundedness and limiting behavior of the above
trajectory. The following result, which gives an equivalent description of the system (8), is
useful in the analysis throughout the remainder of the paper.
Lemma 3.1. Given a pair (a; b) 2 R n
++ \Theta R n : For each ' ? 0; the vector (x; y); where
'b; is a solution to the system (8) if and only if x is a solution
to the following equation
where E(x; for each
Proof. Since a 2 R n
++ and ' ? 0; it is easy to verify that x is a solution to
only if it satisfies the following system:
it is easy to see that (x; y)
is a solution to the system (8) if and only if x is a solution to the system (11)-(13). (This
fact will be used again in later sections). 2
In what follows, we establish a basic result used to show the existence of the proposed
continuation trajectory. The following concept is useful.
Definition 3.1. Given (a; b) 2 R n
++ \Theta R n : Let ' 2 (0; 1) be a given scalar. A sequence
++ with kx k k !1 is said to be a ('; OE; -
H)-exceptional sequence for f if for each
x k there exists a scalar fi k 2 (0; 1) such that
for all
The above concept tailored to our needs here can be viewed as a modified form of those
introduced to investigate the solvability of complementarity problems (Isac et al. 1997,
Zhao and Isac 2000a) and variational inequalities (Zhao 1999, Zhao, Han and Qi 1999). For
given ', the concept of ('; OE; -
H)-exceptional sequence is closely related to the existence of a
solution of the system (8) as the following result shows.
Theorem 3.1. Let (a; b) 2 R n
++ \Theta R n and f continuous function. Then
for each ' 2 (0; 1); there exists either a solution to the system (8) or a ('; OE; -
H)-exceptional
sequence for f .
Proof. Let ' be an arbitrary number in (0; 1): Assume that there exists no solution
to the system (8). We now show that there exists a ('; OE; -
H)-exceptional sequence for f .
Consider the homotopy between the identity mapping and E(x; ') defined by (10), i.e.,
operations are performed componentwise. Define the set
We now show that the set is unbounded. Assume the contrary, that is, the set is bounded.
In this case, there is a bounded open
set\Omega ae R n such that f0g [S '
By the definition of S ' ; for any -
@\Omega ; we have H(-x; l) 6= 0 for any l 2 [0; 1]:
By (c) of Lemma 2.1, we deduce that
I denotes the identity
mapping which is one-to-one in R n : Thus by (a) and (b) of Lemma 2.1, we deduce that
has at least a solution, and hence by Lemma 3.1 the system (8) has a solution.
This contradicts the assumption at the beginning of the proof. Thus, the set S ' is indeed
unbounded, and thus there exists a sequence fx k g ' S ' with loss
of generality, we may assume k. We now show that fx k g is a ('; OE; -
exceptional sequence for f: For each x k , it follows from x k 2 S ' that there exists a number
Clearly, l k 6= 1 since kx k k ? 0: On the other hand, if l it follows from (15) that x k
is a solution to the equation E(x; 0: By Lemma 3.1, the pair
a solution to the system (8). This contradicts again the
assumption at the beginning of the proof. Thus, in the rest of the proof, we only need to
consider the situation of l k 2 (0; 1): We show that fx k g is a ('; OE; -
H)-exceptional sequence
for f . We first show that fx k g ae R n
noting that
and 2'a 2 R n
we have from (15) that
0:
Thus fx k g ae R n
It is sufficient to verify (14). Squaring both sides of (15), we have
Multiplying both sides of the above by
The above equation can be written as
'b
By definition, fx k g is a ('; OE; -
H)-exceptional sequence for f . 2.
4. Existence and boundedness of the trajectory. In this section, we show the
existence and the boundedness of the new trajectory under a very weak condition. The
strictly feasible condition is not required in our results. For any vectors v; v 0 2 R n with
we denote by [v the rectangular set [v 0
The following is our
assumption.
Condition 4.1. For any (a; b) 2 R n
++ \Theta R n ; there exists a scalar
the set [
is bounded, where F \Gamma1
and
ae
-oe
Clearly, D - is a rectangular set in R n
now show a general result.
Theorem 4.1. Let (a; b) be an arbitrary point in R n
++ \Theta R n and f
continuous semimonotone function. Then for each ' 2 (0; 1); the system (8) has a solution.
Denote the solution set by
Moreover, if Condition 4.1 holds, then for any ffi 2 (0; 1), the set
is bounded, where C ' is given by (16).
To prove the above result, we utilize the following lemma. Its proof, similar to the one
of Lemma 1 in Gowda and Tawhid (1999), is very easy and omitted here.
Lemma 4.1. Let f be a continuous semimonotone function. Then for any
sequence fu k g ae R n
exists some i 0 and a subsequence fu k j g
such that u k j
is bounded from below.
Proof of Theorem 4.1. To show the former part of the result, by Theorem 3.1,
it is sufficient to show that the function f has no ('; OE; -
H)-exceptional sequence for each
Assume the contrary, that is, there exists a scalar ' 2 (0; 1) such that fx k g is
a ('; OE; -
H)-exceptional sequence for f . By definition, kx
++ and (14) is
satisfied. Since f is semimonotone, by Lemma 4.1, there exist some subsequence fx k j g and
index m such that x k j
is bounded from below. However, by (14) we
have
a i
This is a contradiction since the left-hand side of the above is bounded from below. Thus f
has no ('; OE; -
H)-exceptional sequence for any ' 2 (0; 1), and hence it follows from Theorem
3.1 that the system (8) has a solution for each ' 2 (0; 1):
We now show the boundedness of the set (17). Let ffi 2 (0; 1) be a fixed scalar. Assume
that there exists a sequence f' k g ' (0; ffi] such that f(x(' k ); y(' k ))g is an unbounded sequence
contained in the set (17). We derive a contradiction. Indeed, in this case, fx(' k )g
must be unbounded. By Lemma 4.1, there exist an index p and a subsequence, denoted
also by fx(' k )g; such that x p (' k is bounded from below. Since
, we see from the proof of Lemma 3.1 that x(' k ) must satisfy (11)-
(13). By (13), we have
and the left hand-side of the above is bounded from below, we deduce
from the above that OE(' k
we have
By using (13) again, we have
for all
From the above two relations, we have
a
given as in Condition 4.1.
there exists a k 0 such that ' k ! fl for all k - k 0 and
a
where
ae
a
-oe
Therefore,
(D - k
which is bounded according to Condition 4.1. This contradicts the unboundedness of
)g. The proof is complete. 2
The following condition is slightly stronger than Condition 4.1.
Condition 4.2. There exists a constant fl ? 0 such that the following set
(D
is bounded, where D fl := [0; fle] \Theta [\Gammafl e; fle] and
(D
Corollary 4.1. Let (a; b) be an arbitrary point in R n
++ \Theta R n and f be a continuous
semimonotone function from R n into itself. If Condition 4.2 is satisfied, then for any
constant the set
is bounded, where C ' is given by (16).
Conditions 4.1 and 4.2 are motivated by the following observation.
Proposition 4.1. Let f be a continuous semimonotone function from R n into itself.
Then for each fixed scalar - ? 0, the set F \Gamma1
for any compact set D in R n
Proof. Let - ? 0 be a fixed number. We show this result by contradiction. Assume
that there exists a compact set D in R n
n such that F \Gamma1
- (D) is unbounded. Then there
is a sequence f(x k ; y k )g contained in F \Gamma1
- (D) such that k(x k ; y k )k !1: Notice that
Since D is compact set in R n
there is a bounded sequences f(d k ; w k )g ' D such that
If x k is bounded, then from the above, so is y k . Thus, by our assumption, fx k g must be
unbounded. We may assume that kx k Passing through a subsequence, we may
assume that there exists an index set I such that x k
I and fx k
i g is bounded
I: From the first relation of (19), we deduce that y k
I since
i is bounded. Thus, from the second expression of (19), we deduce that
This contradicts Lemma 4.1, which asserts that
there is an index p 2 I such that x k
is bounded from below. 2
Condition 4.1 actually states that the union of all the bounded sets F \Gamma1
(D - ) is also
bounded. It is equivalent to saying that F \Gamma1
(D - ) is uniformly bounded when the positive
parameter - is sufficiently small. Later, we will prove that for P 0 complementarity problems
Condition 4.1 is strictly weaker than Condition 1.2. In fact, Condition 4.1 may hold even
if the problem has no strictly feasible point (in this case, the solution set of CP(f) is
unbounded).
While the above results show that for any given (a; b) 2 R n
++ \Theta R n a solution (x(');
to the system (8) exists for each ' 2 (0; 1); it is not clear how to achieve the uniqueness and
the continuity of (x('); y(')) for semimonotone complementarity problems . Nevertheless,
at a risk of losing the arbitrariness of the starting point (a; b) in R n
++ \Theta R n ; it is possible
to obtain the uniqueness and the continuity by using the parameterized Sard Theorem,
see, e.g. Allgower and Georg (1990), Kojima et al. (1993), and Zhang and Zhang (1997).
But such a result cannot exclude a zero measure set (in Lebesgue sense) from which the
proposed trajectory fails to exist. For P 0 -functions, however, it is not difficult to achieve
the uniqueness and the continuity of the proposed trajectory as the next result shows.
Theorem 4.2. Let f be a continuous P 0 -function from R n into itself.
(a) For each ' 2 (0; 1); the system (8) has a unique solution denoted by (x('); y(')):
(b) (x('); y(')) is continuous in ' on (0; 1):
(c) If Condition 4.1 (in particular, Condition 4.2) is satisfied, the set f(x(');
(0; ffi]g is bounded for any ffi 2 (0; 1).
(d) If f is continuously differentiable, then (x('); y(')) is also continuously differentiable
in ':
Proof. Since f is a P 0 -function, the Tihonov regularization function, i.e., f(x)+ OE(')x;
is a P-function in x: Therefore, g(x) :=
a P-function in x; where ' 2 (0; 1): By the same proof of Ravindran and Gowda (1997), we
can show that
is a P-function in x for any given c 2 R n
P-function is injective, the equation
has at most one solution for each fixed ' 2 (0; 1); and hence by Lemma 3.1,
the system (8) has at most one solution. Using this fact and noting that each P-function
is semimonotone, we deduce from (a) of Theorem 4.1 that the system (8) has a unique
solution. Part (a) follows. By using this fact and noting that each P 0 -function (in particular,
P-function) is a weakly univalent function (Gowda and Tawhid 1999, Gowda and Sznajder
1999, Ravindran and Gowda 1997), from Lemma 2.2, we conclude that the solution of (8) is
continuous in ' on (0,1). This proves Part (b). Part (c) immediately follows from Theorem
4.1.
We now prove Part (d). Since f(x) is a P 0 -function, the Jacobian matrix f 0 (x) is a
matrix (Mor'e and Rheinholdt 1973). Hence, the matrix (1 \Gamma ')(f 0 (x)+ OE(')I) is a P-matrix
for each fixed number ' 2 (0; 1): Therefore, the matrix
is a nonsingular matrix (Kojima, Megiddo and Noma 1991, Kojima, Megiddo, Noma and
Yoshise 1991) for any (x; y) ? 0: Noting that the above matrix coincides with the Jacobian
matrix of the map -
with respect to (x; y). Thus, by the implicit function theo-
rem, there exists a ffi-neighborhood of ' such that there exists a unique and continuously
differentiable curve (x(t); y(t)) satisfying
In particular, (x('); y(')) is continuously differentiable at '. The proof is complete. 2
It is known that the structure property of the solution set of CP(f) has a close relationship
to the existence of some interior-point trajectories. For instance, Chen et al. (1997)
and Gowda and Tawhid (1999) have proved the existence of a short central path when the
solution set of a P 0 complementarity problem is nonempty and bounded. In fact, a long
central path may not exist in this case. Chen and Ye (1998) gave an example of a 2\Theta 2 P 0
linear complementarity problem with a bounded solution set to show that there is no long
central path. In contrast, the homotopy continuation trajectory proposed in this paper is
always a long trajectory provided that f is a continuous P 0 -function as shown in Theorem
4.1. The next result shows that any slice of the trajectory (subtrajectory) is always bounded
when SOL cp (f) is nonempty and bounded. The following lemma is employed to prove the
result.
Lemma 4.2 Suppose that S is an arbitrary compact set in R n . Let E(x; ') be given by
(10).
(a) Given (a; b) 2 R n
++ \Theta R n : For any ffi ? 0; there must exist a scalar
that
sup
(b) Let h   : R n \Theta R 1
++ \Theta R n
defined by
For any ffi ? 0; there exists a scalar fl 2 (0; 1) such that
sup
for all - 2 (0; fl] and (w; v) 2 [0; fle] \Theta [\Gammafl e; fle]:
Proof. Denote by
and
Notice that the inequality
holds for any
scalar
0: We have
Since S is a compact set in R n and OE(') ! 0 as ' ! 0, there exist two positive constants
such that for any sufficiently small ' the following holds:
Thus, for any sufficiently samll ', we have for each i that
By the compactness of S, the result (a) holds. Result (b) can be proved in a similar way. 2
Theorem 4.3. Let f be a continuous P 0 -function from R n into itself. Denote by
the trajectory generated by the (unique) solution of the system
(8) as ' varies. If the CP(f) has a nonempty and bounded solution set, then for any scalar
Proof. The existence of the (unique) trajectory follows from (a) and (b) of Theorem
4.2. It suffices to prove that any short part of the trajectory is bounded under the
assumption of the theorem. Assume that SOL cp (f) is nonempty and bounded. Notice that
E(x) := E(x;
is the well-known Fischer-Burmeister function. Thus
i.e., SOL cp nonempty and bounded by assumption. Since f
is a P 0 -function, E(x) is also a P 0 -function (see Ravindran and Gowda 1997, Gowda and
Tawhid 1999), and thus is weakly univalent (Gowda and Tawhid 1999, Gowda and Sznajder
1999, Ravindran and Gowda 1997). It follows from Lemma 2.2 that for any fixed " ? 0
there exists a ffi ? 0 such that for any weakly univalent function h
sup
-\Omega
we have
"B) is a compact set. By (a) of Lemma 4.2, there exists a number
1 such that for any ' 2 (0;
the map h(x) := E(x; '); a P 0 -function in x; satisfies
the relation (20). Thus, it follows from (21) that the set
is contained in the bounded set E 3.1, the subtrajectory, i.e.,
is bounded.
Let ffi be an arbitrary scalar with loss of generality, we assume ffi 0
Our goal is to show the boundedness of the subtrajectory
Notice that
It suffices to show the boundedness of the set T 2 . We show this by contradiction. Assume
that T 2 is unbounded, i.e., there exists a subsequence f(x(' k ); y(' k ))g ' T 2 such that
which implies that kx(' k )k !1: Thus, by Lemma 4.1, there exists a
subsequence, denoted also by fx(' k )g, such that there is an index p such that x p
and f p (' k ) is bounded from below. Since ' k 2 [ffi 0 ; ffi] for all k, by property of OE('); there
must exist a scalar ff ? 0 such that OE(' k ) - ff for all k: It follows from (13) that
which is a contradiction since the left-hand side is bounded from below. 2
The existence and the boundedness of most interior-point paths were established under
Condition 1.2 or some similar versions. See, e.g. Kojima, Megiddo and Noma (1991),
Kojima, Mizuno and Noma (1989), Kojima, Megiddo, Noma and Yoshise (1991), Hotta and
Yoshise (1999), Hotta et al. (1998), Qi and Sun (2000). In what follows, we show that
Condition 1.2 also implies the existence and the boundedness of our trajectory. In fact, we
can verify that Condition 1.2 implies the nonemptyness and boundedness of the solution
set of CP(f ).
Theorem 4.4. Let f be a continuous function. If Condition 1.2 is satisfied, then the
solution set of the problem CP(f) is nonempty and bounded, and hence the result of Theorem
4.3 remains valid.
Proof. By Theorem 4.3, it is sufficient to show that Condition 1.2 implies the nonemp-
tyness and boundedness of the solution set of CP(f ). Since Kojima, Megiddo and Noma
(1991) showed that Condition 1.2 implies the boundedness of their interior-point trajectory;
by continuity, any accumulation point of their trajectory, as the parameter approaches to
zero, is a solution to CP(f ). Thus the solution set is nonempty. We now show its bounded-
ness. By (b) of Condition 1.2, there is a point x Choose a scalar
r such that then by the definition of B++ (f); we have
\Theta B++ (f):
Since D is a compact set, thus by (c) of Condition 1.2, the following set
is bounded. Since 0 2 D; it follows that
which is contained in F \Gamma1 (D); is also bounded. Since F \Gamma1 (0) coincides with the solution
set of CP(f ), we have the desired result. 2
We have shown that for any P 0 complementarity problem the continuation trajectory
proposed in the paper always exists provided f being continuous (see Theorem 4.2), and
that the trajectory is bounded under any one of the following conditions.
ffl Condition 4.1.
ffl Condition 4.2.
ffl The solution set SOL cp (f) is nonempty and bounded.
ffl Condition 1.2 (in particular, Condition 1.1).
It is interesting to compare the above-mentioned conditions. We summarize the result as
follows:
Proposition 4.2. -function and let (a; b) 2 R n
++ \Theta R n be
a fixed vector. Then Condition 1.1 ) Condition 1.2 ) nonemptyness and boundedness
of the solution set of CP(f) ) Condition 4.2 ) Condition 4.1. However, Condition 4.1
may not imply the boundedness of solution set, and existence of a strictly feasible point.
Hence, Condition 4.1 is strictly weaker than Condition 1.2, and than the nonemptyness and
boundedness assumption of the solution set.
Proof. The first implication is well-known (Kojima, Megiddo and Noma 1991). The
second implication follows from Theorem 4.4, and the last implication is obvious. We
now prove the third implication. Assume that the solution set of CP(f) is nonempty and
bounded. We now show that Condition 4.2 is satisfied. Let E(x) be defined as in the proof
of Theorem 4.4, i.e., which is a P 0 -function. Notice that E \Gamma1 (0) is just the
solution set which is nonempty and bounded. Let " ? 0 be a fixed scalar. By Lemma 2.2,
there exists a ffi ? 0 such that for any weakly univalent function h
sup
-\Omega
it holds that
Consider the function h   : R n \Theta R 1
++ \Theta R n
For such fixed -; w and v; the function f(x)
is a P-function (in x) since f is a P 0 -function. Therefore, the function h   (x; -; w; v) must
be a P-function in x (Ravindran and Gowda 1997), and thus be weakly univalent in x. For
the above given ffi; by (b) of Lemma 4.2, there exists a number fl ? 0 such that
sup
-\Omega
for all - 2 (0; fl] and (w; v) 2 D fl := [0; fle] \Theta [\Gammafl e; fle]: Therefore, replacing h by h   in (22)
and (23), we have
where
Therefore, [
It is not difficult to verify that
(D
(D
It follows from the above two relations
that the set 8 !
(D
is bounded. By the definition of F - (x; y) and continuity of f , we deduce that
(D
is bounded. Thus Condition 4.2 holds.
We now give an example to show that Condition 4.1 holds even when a strictly feasible
point fails to exist. Consider the following example.
!/
This function is monotone. For this example, Condition 1.1 and Condition 1.2 do not hold
since f has no strictly feasible point. The solution set of the CP(f) is
which is unbounded. However, this example satisfies Condition 4.1. Indeed, for
any given (a; b) where a
verify that the
set [
(D - ) are given as in
Condition 4.1. Let (x; y) - 0 and
Xy
Then we have
a 2 ];
Thus,
That is,
which imply that must be uniformly bounded for all - 2 (0; fl] where fl is a fixed
scalar in (0,1). Thus, the set [
(D - ) is bounded, and thus Condition 4.1 is satisfied.While the above example has no strictly feasible point, it satisfies Condition 4.1. Hence,
it follows from Theorem 4.2 that from each point (a; b) 2 R n
++ \Theta R n the proposed continuation
trajectory always exists and any subtrajectory is bounded. It is worth noting that
for this example there exists no central path (Example 6.1).
When restricted to P   complementarity problems, it turns out that Condition 4.1 can
be further relaxed. In fact, for this case, we can achieve a necessary and sufficient condition
for the existence and boundedness of the trajectory (see the next section for details). This
prominent feature distinguishes the proposed trajectory from the central path and those
continuation trajectories studied by Kojima, Megiddo and Noma (1991), Kojima et al.
(1990), and Kojima et al. (1993).
5. Limiting behavior of the trajectory. The results proved in Section 4 reveal
that under certain mild conditions the continuation trajectory generated by (8) has at
least a convergence subsequence f(x(' k ); y(' k ))g whose limit point
solution to CP(f ). In this section, we consider the following questions: (a) When does the
entire trajectory converge? (b) In the setting of semimonotone functions, if a subsequence
what can be said about x   ?
In this section, we show that if '=OE(') ! 0 as ' ! 0; some much stronger convergence
properties of the proposed trajectory can be obtained. The case of '=OE(') ! 0 as
easy to be satisfied. An example of such a OE is
We first show that for P   complementarity problems this trajectory is always bounded
provided that the solution set is nonempty (not necessarily bounded). Hence, for a P
complementarity problem, this trajectory is bounded if and only if the CP(f) has a solution.
This result further improves the result of Theorem 4.2. Moreover, if the problem has a least
element solution x   ; i.e., x   - u   for all u   2 SOL cp (f); we prove that the entire trajectory
is convergent for P   complementarity problems.
Theorem 5.1. Let f be a continuous P   -function from R n into itself. Suppose that the
solution set of CP(f) is nonempty.
(a) The system (8) has a unique solution (x('); y(')) for each ' 2 (0; 1), and the solution
is continuous on (0,1). Therefore, the homotopy continuation trajectory
(0; 1)g generated by (8) always exists.
(b) If '=OE(') is bounded for ' 2 (0; 1], then any short part of the trajectory (subtrajectory)
is bounded, that is, for any ffi 2 (0; 1), the set f(x(');
(c) If OE is chosen such that '=OE(') ! 0 as ' ! 0 and SOL cp (f) has a least element,
then the entire trajectory must converge to (x   ; y   ) where x   is the (unique) least element
solution.
Proof. Since each P   -function is a P 0 -function, Part (a) follows immediately from
Theorem 4.2. We now prove (b) and (c). Since the system (8) is equivalent to (11) - (13),
we have
be an arbitrary solution to the CP(f ). For each i
we have
Thus,
On the other hand, by (24) and (25), we have
where
1-i-n
Since f is a P   -function, by using (26) and (27), we have
'e T a -
1-i-n
'(e T a
ne T a
Rearranging terms and dividing both sides by OE('), we have
1-i-n
be an arbitrary scalar. Since '=OE(') is bounded, it follows from the above
inequality that the set fx(') : ' 2 (0; ffi]g is bounded, and by (24), so is
Part (b) follows.
We now consider the case 0: By the boundedness of the trajectory,
there exists a convergence subsequence f(x(' k
which is a solution to CP(f ). Taking the limit, it follows from (28) that there exists an
index i 0 such that
If CP(f) has a least element solution -
substituting u   by -
x   in the above we deduce that
x   is unique, the entire trajectory must converge to this least element of the
solution set. Thus we have Part (c). 2
For the monotone cases, we have the following consequence of Theorem 5.1.
Theorem 5.2. Let f be a continuous monotone map from R n into R n : Suppose that the
solution set of CP(f) is nonempty. Let OE be given such that 0: Then the
trajectory generated by the system (8) converges, as ' ! 0;
to is a least 2-norm solution, i.e., kx   k - ku   k for all u   2 SOL cp (f):
Proof. Since each monotone map is a P   -map with the constant 0, from Theorem
5.1, the trajectory in question always exists and is bounded. In this case, the inequality
(28) reduces to
'(e T a)
Suppose that fx(' k )g; where ' k ! 0; is an arbitrary convergent subsequence with the
limiting point x   , i.e., x(' k we have from (29) that
Since u   is an arbitrary element in SOL cp (f ), the above inequality implies that x   is unique,
and thus the entire trajectory must converge to this solution. It follows from the above
inequality that
that is,
which implies that x   is a least 2-norm solution. 2
It is worth to stress the prominent features of the above results. First, it does not require
the strict feasible condition. Second, it does not need any properness conditions such as
Condition 4.1, Part (c) of Condition 1.2 and those used in Monteiro and Pang (1996). For
a P   complementarity problem the existence and boundedness of the proposed trajectory
is equivalent to the nonemptyness of the solution set. For a monotone problem, the entire
trajectory converges to a least 2-norm solution if and only if the solution set is nonempty.
Kojima, Megiddo and Noma (1991) showed that if Condition 1.2 holds and f is an affine
is an n \Theta n P 0 -matrix, then the whole interior-point
trajectory studied by them is convergent. Moreover, for positive semidefinite matrix M , if
the strictly feasible condition holds, Kojima et al. (1990) showed that the entire interior-point
trajectory studied by them converges to a solution of CP(f) which is a maximum
complementary solution. The trajectory studied in this paper is convergent even when f is
a nonlinear monotone map and the strictly feasible condition fails to hold.
Theorems 5.1 and 5.2 answer the first question presented at the beginning of this section.
They also partially answer the second question. For P   -functions, we have proved that the
limiting point x   of the trajectory generated by (8) is the least element of the solution
set provided such an element exists. For monotone problems, Theorem 5.2 states that the
limiting point x   is a least 2-norm solution. We now study the property of the limiting point
x   of the trajectory in more general cases. Our result reveals that x   is at least a weak
Pareto minimal solution if f is a semimonotone map. The following is the definition of weak
Pareto minimal solution (see, e.g. Definition 2 in Sznajder and Gowda 1998, Definition 2.1
and an equivalent description of the concept in Luc 1989).
Definition 5.1. (Sznajder and Gowda 1998, Luc 1989) Let x   be an element of a
nonempty set S. We say that x   is a weak Pareto minimal element if
In other words, x   is weakly Pareto minimal element of S if there is no element s of S
satisfying the inequality s
We have the following result.
Theorem 5.3. Let f be a continuous semimonotone function from R n into itself, and
let (x('); y(')) be a solution to the system (8) for each ' 2 (0; 1). If the subsequence
is a weak Pareto minimal element of
the solution set of CP(f ).
Proof. We assume that x   is not a weak Pareto minimum. Then by the definition,
there exists a solution u   such that u   ! x   . Since x(' k must have that x(' k ) ? u
for all sufficiently large k: Since f is a semimonotone function, there exist an index p and
a subsequence of fx(' k )g; denoted also by fx(' k )g; such that x p
sufficiently large k: Thus
for all sufficiently large k. Since x is a solution to CP(f ),
by the same proof of (25), we have
(y
On the other hand, we have
(y
Combining the above two inequalities yields
Taking the limit, by using the fact
x
which contradicts the relation
As we have mentioned in Section 3, the Tihonov regularization trajectory can be viewed
as an extreme variant of the trajectory generated by homotopy (5). We close this section
by considering this extreme variant. It is known that for P 0 -function, the system (4) has
a unique solution x(-) which is continuous in - 2 (0; 1): See Facchinei (1998), Facchinei
and Kanzow (1999), Ravindran and Gowda (1997), Sznajder and Gowda (1998), Gowda
and Tawhid (1999), and Facchinei and Pang (1998). The set fx(- 2 (0; 1)g forms
the Tihonov regularization trajectory. Motivated by the proof of Theorems 5.2 and 5.3, we
prove the following result which generalizes and improves several known results concerning
the Tihonov regularization methods for CP(f ).
Theorem 5.4. (a) Let f be a continuous P   -function from R n into R n : If SOL cp (f) 6= ;;
then the entire Tihonov regularization trajectory, i.e., fx(- 2 (0; 1)g; is bounded. If
CP(f) has a least element solution x   , i.e., x   - u   for all u   2 SOL cp (f ), then the entire
trajectory converges to this solution as
(b) continuous monotone function and SOL cp (f) 6= ;; then the
regularization trajectory, i.e., fx(- 2 (0; 1)g; is bounded and converges
to a least 2-norm solution as
(c) is a continuous semimonotone function, then for any sequence
a solution to the system (4) for each - k ; x   is a
Pareto minimal solution of CP(f ).
Proof. The ideas of the proof of Parts (a)-(c) are analogous to that of Theorems 5.1,
5.2 and 5.3, respectively. Here, we only prove the Part (a). Parts (b) and (c) can be easily
proved. Let u   be an arbitrary solution of CP(f ). Since
we have that
Thus
It follows from (30) that
for all using (31) and (32) and noting that f is a P   -function, we obtain
1-i-n
1-i-n
1-i-n
Thus,
1-i-n
which implies that the set fx(- 2 (0; 1)g is bounded. We assume that fx(- k )g is a
subsequence and x(- k 0: From (33), we deduce that
1-i-n
x
If u   is a least element solution in the sense that u   - v   for all v   2 SOL cp (f); it follows
from the above inequality that x  the least element solution is unique, the entire
trajectory fx(- 2 (0; 1)g must converge to this solution as
For a differentiable P 0 -function f , Facchinei (1998) showed that if SOL cp (f) is nonempty
and bounded the Tihonov regularization trajectory fx(- 2 (0; -
-]g is bounded for any
fixed -, and he gave an example to show that it is not possible to remove the boundedness
assumption of the solution set in his result without destroying the boundedness of the regularization
subtrajectory. Here, we significantly improved Facchinei's result in the setting of
showed that the boundedness assumption of the solution
set can be removed, and the entire Tihonov regularization trajectory fx(- 2 (0; 1)g;
rather than just a subtrajectory, is bounded. Since P   problems include the monotone ones
as special cases, the above (a) and (b) of Theorem 5.4 can be viewed as a generalization of
the results of Subramanian (1988) and Sznajder and Gowda (1998) for the monotone linear
complementarity problems. Part (c) of Theorem 5.4 extends the result of Theorem 3 in
Sznajder and Gowda (1998) concerning P 0 -functions to general semimonotone functions.
6. Examples and a framework of path-following method. We have shown that
for problems it only needs a mild condition to ensure the existence
and boundedness of the proposed homotopy continuation trajectory. This feature of the
homotopy continuation trajectory enable us to design a path-following method (continuation
method) to solve a very general class of complementarity problems even when a strictly
feasible point fails to exist (in this case, if it is solvable, the P 0 complementarity problem
has an unbounded solution set). We first give two examples to show that the proposed
trajectory does exist and is bounded in general situations.
Example 6.1: Consider the monotone LCP(M; q), where
The solution set SOL cp unbounded. Clearly, this problem
has no strictly feasible point. Thus, this problem has no central path, i.e., the following
system
has no solution for each - ? 0: However, from any (a; b) 2 R 2
++ \Theta R 2 , we can verify that the
proposed continuation trajectory exists and converges to the least 2-norm solution. Indeed,
let
The system (7) can be written as
i.e.,
This system has a unique solution x('); i.e.,
continuous trajectory. Let ' ! 0 and '=OE(') ! 0: Then it
is easy to see that which is the least 2-norm solution of the CP.
It is worth noting that for our trajectory the vector b can be chosen as an arbitrary
point in R 2 : However, we can easily check that the trajectory of Kojima, Megiddo and
Noma (1991) does not exist if there exists a component b i - 0:
Example 6.2. Let
This matrix is a P 0 -matrix, but not a P   -matrix. The solution set SOL cp
is an unbounded set. Clearly, this problem has no strictly feasible point.
We show that the trajectory studied by Kojima, Megiddo and Noma (1991) does not exist.
++ \Theta R 2 where a Consider the system
where H is given by (6). For this example, the above system can be written as
There are three possible cases:
Case 1: b 2 - 0: The above system has no solution.
Case 2: 0: The above system also has no solution.
Case 3:
a ? 0; and hence
for all sufficiently small ' ? 0: Thus the above system has no solution for all sufficiently
small ': In summary, from any starting point (a; b) 2 R 2
++ \Theta R 2 ; the trajectory of Kojima,
Megiddo and Noma (1991) does not exist. However, since f is a P 0 -function, by Theorem
4.2, the continuous trajectory generated by system (8) always exists for each given point
++ \Theta R 2 : We now verify this fact. Choose OE(') such that '=OE(') ! 0 as ' ! 0:
The system (8) can be written as
i.e.,
The system (34), (37) and (38) has a unique solution, i.e.,
Clearly, by (39) and
(40) is the unique solution to the system (34)-(38). Therefore,
continuous trajectory. Since '=OE(') ! 0; we deduce that x 2
which is the least 2-norm solution.
If '=OE 3 (') - c; where c is a positive constant, then x 2 (')=OE(') is bounded. Therefore, it is
easy to see that the set f(x 1 is bounded for any fixed ffi 2 (0; 1); and
any accumulation point of the set is a weakly Pareto minimal solution. If '=OE 3
then which can also be viewed as a weakly Pareto minimal solution.
Based on the results established in the paper, we may develop a continuation method
for CP(f) by tracing the proposed trajectory. Such a method is expected to solve a broad
class of complementarity problems without the requirement of the strictly feasible condition
or boundedness assumption of the solution set. Here we provide only a framework of the
algorithm without convergence analysis. Let a be an arbitrary point in R n
Thus the starting point can be
chosen as is the current point. We
attempt to obtain the next iterate by solving approximately the following system
scalar. The Newton direction (\Delta'; \Deltax; \Deltay) 2 R 1+2n to the above
system should satisfy the following equationB @
z
\Delta'
\Deltax
\DeltayC
where
Notice that We can specify a framework of the algorithm as follows.
Algorithm: (a): Select a starting point
(b): At the current iterate, solve the following system
!/
\Deltax
\Deltay
Choose suitable step parameters ff k and fi k such that
\Deltay
and
Update fl k and go back to (b).
The main feature of the above algorithm is that the newton direction (\Deltax; \Deltay) is determined
by a system which is quite different from the previous ones in the literature. Some
interesting topics are the global and local convergence and polynomial iteration complexity
of the above algorithm.
7. Conclusions. For most interior-point and non-interior-point continuation meth-
ods, either the existence or the boundedness of the trajectory in question requires some
relatively restrictive assumptions such as Condition 1.1 or Condition 1.2. Because these
methods strongly depend on the existence of a strictly feasible point that is equivalent to
the nonemptyness and boundedness of the solution set in the case of P   complementarity
problems Zhao and Li (2000), they possibly fail to solve the problems with an unbounded
solution set even for the monotone cases. However, the continuation trajectory proposed
in this paper always exists for P 0 problems without any additional assumption, and the
boundedness of it needs no strictly feasible condition as shown by Theorems 4.2, 5.1 and
5.2. Particularly, for P   problems we prove that the existence and the boundedness of the
proposed trajectory is equivalent to the solvability of CP(f ). Moreover, if f is monotone, the
entire trajectory converges to a least 2-norm solution whenever the solution set is nonempty.
As a by-product, a new property (Theorem 5.4) is elicited for Tihonov regularization tra-
jectory. The results presented in this paper have provided us with a theoretical basis for
constructing a new path-following method to solve a CP(f ). This method is expected to
solve a general class of complementarity problems which is broader than those to which
most existing path-following methods can be applied.

Acknowledgements

. The research presented in this paper was partially supported
by research Grants Council of Hong Kong grant CUHK358/96P. We would like to thank
two anonymous referees, Associate Editor and Area Editor Professor J. S. Pang for their
helpful comments and suggestions that lead to the improvement of the paper.



--R

Numerical Continuation Methods
The global linear convergence of a non-interior path-following algorithm for linear complementarity problems
A polynomial time interior-point path-following algorithm for LCP based on Chen-Harker-Kanzow smoothing techniques

A global and local superlinear continuation-smoothing method for P 0 and R 0 and monotone NCP
A penalized Fischer-Burmeister NCP-function: theoretical investigation and numerical results

On smoothing methods for the P 0
The Linear Complementarity Problem
Sufficient matrices and the linear complementarity problem.
Structural and stability properties of P 0 nonlinear complementarity prob- lems
Beyond monotonicity in regularization methods for nonlinear complementarity problems.
"La Sapienza"
Weak univalence and connected of inverse images of continuous functions.
Existence and limiting behavior of trajectories associated with
Existence of interior points and interior-point paths in nonlinear monotone complementarity problems
Global convergence of a class of non-interior-point algorithms using Chen-Harker-Kanzow-Functions for nonlinear complementarity problems
A complexity analysis of a smoothing method using CHKS-Function for monotone linear complementarity problems
Tikhonov's regularization and the complementarity problem in Hilbert space.
Exceptional families
Some nonlinear continuation methods for linear complementarity prob- lems
A general framework of continuation methods for complementarity problems.
Homotopy continuation methods for nonlinear complementarity problems.
A unified approach to interior point algorithms for linear complementarity problems
A new continuation method for complementarity problems with uniform P-functions
Limiting behavior of trajectories generated by a continuation method for monotone complementarity problems.
A polynomial-time algorithm for linear complementarity problems
Bimatrix equilibrium points and mathematical programming.

Degree Theory
Theory of Vector Optimization
The complementarity problem for maximal monotone multifunction
Stable monotone variational inequalities
Pathways to the optimal set in linear programming
Properties of an interior-point mapping for mixed complementarity problems

Global methods for nonlinear complementarity problems.
A regularization smoothing Newton method for box constrained variational inequality problems with P 0
Improving the convergence of non-interior point algorithm for nonlinear complementarity problems
Regularization of P 0
A note on least two norm solution of monotone complementarity problems.
On the limiting behavior of the trajectory of regularized solutions of P 0 complementarity problems
bounds for regularized complementarity problems
P matrices are just sufficient
An algorithm for the linear complementarity problem with a P 0 - matrix
Interior Point Algorithms Theory and Analysis

On constructing interior-point path-following methods for certain semimonotone linear complementarity problems
Existence of a solution to nonlinear variational inequality under generalized positive homogeneity.
Exceptional families and existence theorems for variational inequalities.


On the strict feasibility condition of complementarity problems
Characterization of a homotopy solution mapping for nonlinear complementarity problems
--TR

--CTR
Guanglu Zhou , Kim-Chuan Toh , Gongyun Zhao, Convergence Analysis of an Infeasible Interior Point Algorithm Based on a Regularized Central Path for Linear Complementarity Problems, Computational Optimization and Applications, v.27 n.3, p.269-283, March 2004
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
homotopy continuation trajectories;p-functions;strictly feasible condition;continuation methods;complementarity problems;P0-functions