On nite termination of an iterative method for linear

complementarity problems
Andreas Fischer
a
and Christian Kanzow
b
a
Institute for Numerical Mathematics, Technical University of Dresden,
D-01062 Dresden, Germany; e-mail: scher@[Link]
b
Institute of Applied Mathematics, University of Hamburg, Bundesstrasse 55,
D-20146 Hamburg, Germany; e-mail: kanzow@[Link]
Abstract
Based on a well-known reformulation of the linear complementarity problem
(LCP) as a nondierentiable system of nonlinear equations, a Newton-type method
will be described for the solution of LCPs. Under certain assumptions, it will be
shown that this method has a nite termination property, i.e., if an iterate is su-
ciently close to a solution of LCP, the method nds this solution in one step. This
result will be applied to a recently proposed algorithm by Harker and Pang in order
to prove that their algorithm also has the nite termination property.
Keywords: linear complementarity problems; nonsmooth equations; generalized
Jacobians; Newtons method; nite termination
1 Introduction
In this paper, we will consider the linear complementarity problem LCP(q, M)
of nding a vector pair (x, y) IR
2n
such that the conditions
x 0, y 0, x
T
y = 0, Mx + q = y
are satised, where the matrix M IR
nn
and the vector q IR
n
are given.
Several well-known methods for the solution of LCP(q, M) exist. Many of them
are described in the books by Murty [23], Cottle, Pang and Stone [3], Kojima
et al. [19] and Harker [11]. Here, we will focus on a Newton-type method being
applied to the nonlinear system of equations F(z) = 0, where F : IR
2n
IR
2n
Preprint submitted to Elsevier Science 8 March 2005
is dened by
F(z) := F(x, y) :=
_
_
_
Mx + q y
min{x, y}
_
_
_ (1)
with the min-operator taken componentwise. Obviously, a vector pair (x, y)
is a solution of LCP(q, M) if and only if (x, y) is a zero of F. A Newton-type
method applied to this characterization was proposed by Pang [24,25] in con-
nection with nonlinear complementarity and variational inequality problems.
This approach has been specialized by Harker and Pang [12] to the linear
complementarity problem. In order to overcome the nondierentiability of the
operator F, they made use of the so-called B-derivative of F. The numerical re-
sults reported by Harker and Pang [12] are quite promising. In particular, their
method outdoes Lemkes classical complementary pivot algorithm if measured
in CPU-times. An unsolved question raised by Harker and Pang is, however,
the nite termination of their method. It is the main contribution of this paper
to show that their method has indeed the nite termination property under
some standard assumptions.
We want to mention some relevant works. The characterization (1) of LCP(q, M)
as a system of nonlinear equations is not the only one. The rst such approach
can be found in Mangasarian [22], who presents a general class of characteriza-
tions. Theoretical and numerical results for particular members of Mangasar-
ians class can be found, e.g., in Watson [31], Subramanian [29] and Ferris
and Lucidi [6]. An even more general approach is given in Kanzow [15] and
Tseng [30]. Special characterizations not belonging to the Mangasarian-class
are considered in Fischer [79], Harker and Xiao [13] and Dirkse and Ferris
[4]. Chen and Harker [1] and Kanzow [17] use similar ideas in an interior-point
setting.
Most of the above-mentioned papers consider nondierentiable characteriza-
tions of the complementarity problem, although there are also some dieren-
tiable ones. Methods based on (appropriate) nondierentiable characteriza-
tions usually seem to be numerically more successful than their dierentiable
counterparts. There are at least two reasons for this. First, the dierentiable
characterizations involve more complicated functions, i.e., the characteriza-
tions themselves are more nonlinear, and second, the Jacobian matrices of dif-
ferentiable characterizations of LCP(q, M) are singular at degenerate solutions
of LCP(q, M), see Theorem 3.1 and Remark 3.2 in Kanzow and Kleinmichel
[18].
This paper is organized as follows. After reviewing some background material
in Section 2 we will describe our algorithm. In contrast to the approach by
Harker and Pang [12], this algorithm is based on Clarkes [2] generalized Jaco-
2
bian in order to overcome the diculty of nondierentiable points. In Section
3, we will prove a nite termination property of this algorithm under certain
assumptions. In Section 4 we will apply our results to a method of Harker
and Pang [12] and prove, in this way, that their algorithm also has the nite
termination property. Some nal remarks in Section 5 will conclude this paper.
In the following, z denotes the Euclidean norm of a vector z of appropriate
dimension. The letter k is always used as an iteration index, whereas a
subscript i usually denotes the ith component of a vector. Throughout this
paper, the index set {1, . . . , n} is abbreviated by I. For arbitrary p IR
n
and J I, the vector p
J
consists of the components p
i
, i J. Similarly, for
a given matrix M IR
nn
, M
JJ
denotes the submatrix (m
ij
)
i,jJ
. Moreover,
M
i
means the ith row vector of M. The n-vector of all ones is denoted by e.
2 Mathematical Background and Algorithm
In this section, we will restate some basic denitions which will be used in the
subsequent analysis.
Denition 1 Let M IR
nn
. Then M is said to be a
(a) nondegenerate matrix if det(M
JJ
) = 0 for all J I;
(b) P-matrix if det(M
JJ
) > 0 for all J I.
Obviously, any P-matrix is nondegenerate. Moreover, it is well-known that M
is a P-matrix if and only if, for all x IR
n
, x = 0, an index i I exists such
that x
i
= 0 and x
i
[Mx]
i
> 0, see [3].
Let z

:= (x

, y

) IR
2n
be a solution of LCP(q, M), and dene the following
index sets:
:= (z

) :={i I| x

i
> 0 = y

i
},
:= (z

) :={i I| x

i
= 0 = y

i
},
:= (z

) :={i I| x

i
= 0 < y

i
}.
Note that is the set of degenerate indices, and that the results of this paper
hold without the assumption that is an empty set.
Denition 2 A solution z

:= (x

, y

) IR
2n
of LCP(q, M) is called
(a) b-regular if the submatrices M

are nonsingular for all ;

(b) R-regular if the submatrix M

is nonsingular and the matrix

M

M
1

(2)
3
is a P-matrix.
We note that the matrix (2) is the Schur-complement of M

in
_
_
_
M

_
_
_.
Obviously, the b-regularity assumption is weaker than the R-regularity as-
sumption. The latter originates from Robinsons concept of a strongly regular
solution of a generalized equation [28]. Both assumptions are important for
stability results and to prove fast local convergence of certain Newton-type
methods, see, e.g., [3,5].
Now let F be the nonlinear operator dened in (1). Furthermore, let
D := {z = (x, y) IR
2n
| x
i
= y
i
for all i I}
denote the set of vectors z at which F is dierentiable. Obviously, F is a locally
Lipschitz-continuous operator. Hence, we can dene its B-subdierential (see
[26])

B
F(z) :=
_
G IR
nn
| {z
k
} D : lim
k
z
k
= z, G = lim
k
F(z
k
)
_
and its generalized Jacobian (see [2])
F(z) := conv {
B
F(z)} ,
where conv(A) is the convex hull of a set A, and F(z
k
) denotes the Jacobian
matrix of F at z
k
. If z D, then
B
F(z) = F(z) = {F(z)} is a singleton.
Otherwise F(z) can be shown to be a nonempty, convex and compact set,
see Clarke [2].
From the denitions of F,
B
F(z) and F(z), we obtain that any G F(z)
has the following structure:
G = G(a) :=
_
_
_
M I
D
a
I D
a
_
_
_, D
a
:= diag(a
1
, . . . , a
n
), (3)
where the vector a IR
n
with a
i
[0, 1] for i I depends on which G
F(z) is chosen. More precisely, we get the following representations of the
B-subdierential and of the generalized Jacobian:

B
F(z) = {G(a) | a
i
= 1 if x
i
< y
i
, a
i
= 0 if x
i
> y
i
, a
i
{0, 1} if x
i
= y
i
},(4)
F(z) = {G(a) | a
i
= 1 if x
i
< y
i
, a
i
= 0 if x
i
> y
i
, a
i
[0, 1] if x
i
= y
i
}.(5)
4
We will now give a formal description of an algorithm whose theoretical prop-
erties will be analyzed in the following section.
Algorithm 1 (Nonsmooth Newton method)
(S.0) Choose z
0
:= (x
0
, y
0
) IR
2n
, , (0, 1) and set k := 0.
(S.1) If F(z
k
) = 0, stop. (z
k
solves the LCP(q, M).)
(S.2) Choose a nonsingular matrix G
k
F(z
k
) and compute z
k
:= (x
k
, y
k
)
as the unique solution of the generalized Newton equation
G
k
z = F(z
k
). (6)
(S.3) Set t
k
:=
m
k
, where m
k
is the smallest nonnegative integer m satisfying
the Armijo condition
F(z
k
+
m
z
k
)
2
(1
m
)F(z
k
)
2
.
(S.4) Set z
k+1
:= z
k
+ t
k
z
k
, k := k + 1 and go to (S.1).
Generalized Newton methods of this kind were also considered by Kummer
[21], Qi and Sun [27] and Qi [26]. In order for Algorithm 1 to be well-dened,
we have to guarantee that there is always a nonsingular matrix G
k
F(z
k
)
(under appropriate assumptions on the matrix M involved in the LCP(q, M))
and that a steplength t
k
> 0 can always be found, i.e. that z
k
is a suit-
able descent direction for the merit function F
2
. An answer to the former
problem will be given in Section 3, whereas the latter problem will shortly be
discussed in Section 4. We stress, however, that Algorithm 1 is mainly used as
a theoretical tool in this paper in order to prove nite termination of Harker
and Pangs algorithm, see Section 4.
We note that in practical computations it seems preferable to use a nonmono-
tone line search instead of step (S.3). For instance, we have successfully used
one modelled on the strategy by Grippo, Lampariello and Lucidi [10].
3 Finite Termination
In this section, we will prove that Algorithm 1 terminates in one step for linear
complementarity problems provided that the current iterate z
k
:= (x
k
, y
k
)
is in a suciently small neighbourhood of a solution z

:= (x

, y

) of the
LCP(q, M). The following lemma is the key ingredient for this result.
Lemma 3 Let z

:= (x

, y

) IR
2n
denote a solution of the LCP(q, M). Then
there is a positive number (z

) such that
F(z) G(z z

) = 0 (7)
5
for all z B
(z

)
and all matrices G F(z), where B

:= {z IR
2n
| z z

< }.
Proof. For an arbitrary z = (x, y) IR
2n
, we obtain
Mx + q y (M(x x

) (y y

)) = Mx

+ q y

= 0,
i.e., the rst n equations of system (7) are satised. Now it will be shown that
the remaining equations
(x
i
, y
i
) := min{x
i
, y
i
} a
i
(x
i
x

i
) (1 a
i
)(y
i
y

i
) = 0 (i I),
where a
i
comes from the representation of the generalized Jacobian (cf. (3),
(5)), are fullled in a certain neighbourhood of the solution z

= (x

, y

). If
there is at least one index i I with x

i
+ y

i
> 0, then set
(z

) :=
1
3
min{x

i
+ y

i
| i I, x

i
+ y

i
> 0}.
Otherwise, let (z

) be any positive number. Now, let z B

(z

)
and G F(z)
be arbitrarily chosen. We distinguish the following cases:
(a) If x

i
= y

i
= 0 and x
i
= y
i
, we directly get (x
i
, y
i
) = 0.
(b) If x

i
= y

i
= 0 and x
i
< y
i
, it follows that a
i
= 1 and therefore (x
i
, y
i
) =
0.
(c) If x

i
= y

i
= 0 and x
i
> y
i
, the same is obvious with a
i
= 0.
(d) If x

i
= 0 < y

i
, we obtain y
i
y

i
(z

) 2(z

) > (z

) |x
i
x

i
| x
i
.
This yields a
i
= 1 and (x
i
, y
i
) = 0.
(e) If y

i
= 0 < x

i
, it follows analogously to case (d) that a
i
= 0 and
(x
i
, y
i
) = 0.
Consequently, we have (x
i
, y
i
) = 0 for all i I and all z B
(z

)
. 2
We note that Lemma 3 is true even for infeasible vectors z = (x, y) B
(z

)
,
i.e., y = Mx + q need not be satised.
Theorem 4 Let z

:= (x

, y

) IR
2n
denote a solution of the LCP(q, M). If
z
k
B

for some suciently small > 0 and if G

k
F(z
k
) is nonsingular,
then z
k+1
as generated by Algorithm 1 solves the LCP(q, M).
Proof. Let := (z

) be as in Lemma 3. Based on this lemma and the non-

singularity of G
k
, step (S.2) of Algorithm 1 yields
(z
k
+ z
k
) z

= z
k
G
1
k
F(z
k
) z

= G
1
k
(F(z
k
) G
k
(z
k
z

)) = 0.
6
Therefore, we have
F(z
k
+ z
k
)
2
= F(z

)
2
= 0 (1 )F(z
k
)
2
,
i.e., step (S.3) of Algorithm 1 computes t
k
= 1 and step (S.4) provides
z
k+1
= z
k
+ z
k
= z

. 2
The proof of this theorem is based on an idea of Kojima and Shindo [20]
in connection with Newtons method for piecewise continuously dierentiable
equations, see also Kummer [21] and Fischer [7] for related results.
Theorem 4 raises the following question - under what assumptions can we
nd a nonsingular matrix G
k
F(z
k
) ? The following results give sucient
conditions.
Theorem 5 Let M IR
nn
be a P-matrix and let z IR
2n
be an arbitrary
vector. Then every element G F(z) is nonsingular.
Proof. Let z IR
2n
and G F(z) be arbitrary. Then, we consider p =
(p
(1)
, p
(2)
) IR
2n
such that Gp = 0 is satised. With regard to (3) we have
Mp
(1)
p
(2)
=0, (8)
a
i
p
(1)
i
+ (1 a
i
)p
(2)
i
=0 (i I), (9)
where a
i
[0, 1]. From (8), we obtain p
(2)
= Mp
(1)
and therefore p
(2)
i
=
(Mp
(1)
)
i
= M
i
p
(1)
. Together with (9) it follows that
a
i
p
(1)
i
+ (1 a
i
)M
i
p
(1)
= 0 (i I). (10)
Multiplying the ith equation by p
(1)
i
and recalling that M is a P-matrix, we
immediately get p
(1)
= 0. This and (8) yields p
(2)
= 0. Consequently, the
matrix G is indeed nonsingular. 2
As a direct consequence of Theorems 4 and 5, we get the result that Algorithm
1 possesses the nite termination property for P-matrix linear complementar-
ity problems independent of the particular choice of the matrix G F(z).
The following theorem deals with the case where the matrix M is only assumed
to be nondegenerate and states a somewhat weaker assertion.
Theorem 6 Let M IR
nn
be a nondegenerate matrix and let z IR
2n
be an
arbitrarily chosen vector. Then all elements G
B
F(z) are nonsingular.
7
Proof. The proof is similar to the one given for Theorem 3.1 in [16]. Let
z IR
n
and G
B
F(z) be arbitrary. According to (3) and (4) there is a
vector a IR
n
with a
i
{0, 1} such that G = G(a). Dene the index sets
J := {i I|a
i
= 0} and

J := {i I|a
i
= 1}.
Since a
i
{0, 1}, we have

J = I \ J. Let p = (p
(1)
, p
(2)
) IR
2n
with Gp = 0,
i.e., let equations (8) and (9) hold. The latter and the denitions of J and

J
yield
p
(1)

J
= 0 and p
(2)
J
= 0. (11)
Using this, it follows from (8) that
M
JJ
p
(1)
J
= 0. (12)
Since M is nondegenerate, the submatrix M
JJ
is nonsingular. Therefore, equa-
tion (12) implies
p
(1)
J
= 0.
This together with the rst equation in (11) yields p
(1)
= 0 and we obtain
from (8) that p
(2)
= 0. Thus, p = 0. Therefore, all matrices G
B
F(z) are
nonsingular for any z IR
n
. 2
If z D, then
B
F(z) consists solely of the Jacobian matrix F(z), which
must then be nonsingular for nondegenerate matrices M because of Theorem
6. The following example, however, shows that if z = (x, y) is a vector not
belonging to D, then singular matrices G F(z) might exist.
Example 7 Let n = 1, M = (1) IR
11
, q IR
1
arbitrary and z = (x, y)
IR
2
such that x = y. Obviously, M is a nondegenerate matrix, but not a P-
matrix. From the representation of the generalized Jacobian F(z), it follows
directly that the singular matrix
G =
_
_
_
1 1
0.5 0.5
_
_
_
is an element of F(z) (just take a = 0.5).
Based on the following example, it is clear that it may happen that there is
no nonsingular element G F(z) if the underlying matrix M is degenerate
(i.e., not nondegenerate).
8
Example 8 Let n = 1, M = (0) IR
11
, q IR
1
arbitrary and z = (x, y)
IR
2
such that x > y. Then M is degenerate and F(z) solely contains the
singular matrix
G =
_
_
_
0 1
0 1
_
_
_.
Now let z

:= (x

, y

) IR
2n
be a solution of LCP(q, M), and let , and
denote the corresponding index sets as dened in Section 2. Without loss of
generality we can partition the matrix M as well as the diagonal matrix D
a
as follows:
M =
_
_
_
_
_
_
_
M

_
_
_
_
_
_
_
, D
a
=
_
_
_
_
_
_
_
D
a,
D
a,
D
a,
_
_
_
_
_
_
_
,
where D
a,
= (D
a
)

etc. Similarly, for an arbitrary vector q IR

n
, we use
the corresponding partitioning
q = (q

, q

, q

).
Based on this notation, we are able to formulate and prove our next results.
Theorem 9 Let z

:= (x

, y

) IR
2n
be an R-regular solution of LCP(q, M).
Then all elements G F(z

) are nonsingular.
Proof. Taking an arbitrary G F(z

), we consider p = (p
(1)
, p
(2)
) IR
2n
such that Gp = 0. With regard to (3) as well as to (8) and (9), we get
D
a
p
(1)
+ (I D
a
)Mp
(1)
= 0 (13)
and p
(2)
= Mp
(1)
. Therefore, we only have to show that p
(1)
= 0 follows from
(13). Using the denition of the index sets , , and formula (3) together
with the representation (5) of F(z), it follows in the above notation that
D
a,
= 0

and D
a,
= I

. Consequently, (13) can be rewritten as

M

p
(1)

+ M

p
(1)

+ M

p
(1)

=0

, (14)
D
a,
p
(1)

+ (I D
a,
)
_
M

p
(1)

+ M

p
(1)

+ M

p
(1)

_
=0

, (15)
p
(1)

=0

. (16)
9
According to (16) and the R-regularity of z

, we get
p
(1)

= M
1

p
(1)

(17)
from (14). Substituting this into (15) and rearranging terms yields
_
D
a,
+ (I D
a,
)
_
M

M
1

__
p
(1)

= 0

. (18)
Due to the R-regularity the bracketed term in (18) is a P-matrix. Hence, we
can argue as in the proof of Theorem 5 that p
(1)

= 0

. This implies p
(1)

= 0

(cf. (17)). Because of (16) the proof is complete. 2

Theorem 10 Let z

= (x

, y

) IR
2n
be a b-regular solution of LCP(q, M).
Then all elements G
B
F(z

) are nonsingular.
Proof. Let G
B
F(z

) be arbitrarily chosen. Keeping the representation

(4) of the B-subdierential
B
F(z) and formula (3) in mind, we see that an
index set exists with and
a

= 0

, a

= e

, (19)
where

= I \ . If we write
M =
_
_
_
M

_
_
_, D
a
=
_
_
_
D
a,
D
a,

_
_
_
and assume that Gp = 0 for some vector p = (p
(1)
, p
(2)
) IR
2n
, then (13) can
be rewritten as
D
a,
p
(1)

+ (I

D
a,
)
_
M

p
(1)

+ M

p
(1)

_
=0

, (20)
D
a,

p
(1)

+ (I

D
a,

)
_
M

p
(1)

+ M

p
(1)

_
=0

. (21)
With regard to (3) and (19), we have D
a,
= 0

and D
a,

= I

. Therefore,
(20) and (21) can be reduced to
p
(1)

= 0

, M

p
(1)

= 0

.
Owing to the b-regularity assumption, the submatrix M

is nonsingular and
we get
p
(1)

= 0

.
10
This shows that p
(1)
= 0. Finally, p
(2)
= Mp
(1)
= 0, according to (8), implies
p = 0. 2
From well-known properties of the B-subdierential and the generalized Jaco-
bian, see [26,2], it follows that the nonsingularity results given in Theorems 9
and 10 remain true in a certain small neighbourhood of the solution z

. Hence
we can also apply Theorem 4 under the R- and b-regularity assumptions. In
contrast to the case of a nondegenerate or P-matrix complementarity prob-
lem, however, the neighbourhood for the nite termination is possibly smaller
and not necessarily given by the constant (z

) dened in the proof of Lemma

3.
In order to illustrate the nite termination of Algorithm 1, we implemented
that algorithm in MATLAB (using a nonmonotone line search) and tested it
on the following problem found in Harker and Pang [12].
Example 11 Let
M := A
T
A + B + diag(c
i
).
The matrix A IR
nn
, the skew-symmetric matrix B IR
nn
and the vectors
c, q IR
n
are randomly generated with uniformly distributed entries
a
ij
, b
ij
(5, 5), c
i
(0, 0.3), q
i
(500, 0) (i, j I).
In our MATLAB-implementation we chose G
k
F(z
k
) such that a
i
= 1
if x
k
i
< y
k
i
and otherwise a
i
= 0. Figure 1 shows the convergence history of
Algorithm 1 for one typical instance of Example 11. This gure is interesting
since it clearly demonstrates both the nonmonotone line search and the nite
termination (note that the norm F(z
k
)/F(z
0
) for the sixth iterate k = 6
is relatively large, whereas F(z
7
)/F(z
0
) is almost around the machine
precision).
4 Application to Harker and Pangs Algorithm
We will rst give a review of Harker and Pangs algorithm [12], see also Pang
[24]. They have considered the characterization H(x) = 0 of the LCP(q, M)
11
with H : IR
n
IR
n
being dened by
H(x) = min{x, Mx + q}. (22)
Their algorithm is as follows:
Algorithm 2 (Harker-Pang method)
(S.0) Choose x
0
IR
n
, , (0, 1) and set k := 0.
(S.1) If H(x
k
) = 0, stop. (x
k
solves the LCP(q, M).)
(S.2) Compute x
k
as a solution of the generalized Newton equation
BH(x
k
; x) = H(x
k
). (23)
(S.3) Set t
k
:=
m
k
with m
k
being the smallest nonnegative integer m satisfy-
ing the Armijo condition
H(x
k
+
m
x
k
)
2
(1
m
)H(x
k
)
2
.
(S.4) Set x
k+1
:= x
k
+ t
k
x
k
, k := k + 1 and go to(S.1).
By BH(x; ) the B-derivative of H at x is denoted, see e.g. [13,24] for details.
In particular, BH(x; ) is a positive homogeneous but not necessarily linear
mapping. Therefore, in contrast to Algorithm 1, the Newton equation (23)
of Algorithm 2 is in general nonlinear. For the particular function H, the
B-derivative at x
k
is given by
(BH(x
k
; x))
i
=
_

_
M
i
x if i (x
k
) := {i I| (Mx
k
+ q)
i
< x
k
i
}
min{M
i
x, x
i
} if i (x
k
) := {i I| (Mx
k
+ q)
i
= x
k
i
}
x
i
if i (x
k
) := {i I| (Mx
k
+ q)
i
> x
k
i
}
.
The generalized Newton equation (23) (with x = x
k
) can therefore be
rewritten as follows:
M
i
x
k
=(Mx
k
+ q)
i
(i (x
k
)), (24)
min{M
i
x
k
, x
k
i
} =x
k
i
(i (x
k
)), (25)
x
k
i
=x
k
i
(i (x
k
)). (26)
In order to avoid nonlinear subproblems, Harker and Pang proposed a modi-
cation of step (S.3) of Algorithm 2, see also [3]. This modication, together
with a nondegenerate starting point x
0
, ensures that all iterates x
k
remain
nondegenerate, i.e., (x
k
) = for k = 0, 1, . . . Consequently, the subproblems
only consist of the linear equations (24) and (26).
12
A further modication of Algorithm 2 is obtained if the Newton-type algorithm
given in [25] is used for linear complementarity problems LCP(q, M). There,
roughly speaking, another index set denition possibly enlarges the dimension
of the linear complementarity part (25) in the subproblems. However, stronger
results on global and locally quadratic convergence can be proved.
It can easily be seen that the subsequent considerations, in particular Theo-
rems 12 and 13, also hold for these modied versions of Harker and Pangs
algorithm.
Throughout this section, we will follow Harker and Pang [12] and assume that
the system (24)(26) has a solution x
k
for all iteration steps k = 0, 1, . . . We
will now show that (under this assumption) both Algorithm 1 and Algorithm
2 generate the same sequence x
0
, x
1
, . . . if we take y
0
:= Mx
0
+q in Algorithm
1 and choose a particular matrix G
k
F(z
k
). From y
0
= Mx
0
+ q and a
simple induction argument, we rst get
y
k
= Mx
k
+ q (k = 0, 1, . . .). (27)
Let x
k
IR
n
denote a solution of (24)(26) and dene
a
i
:= a
k
i
:=
_

_
1 if x
k
i
M
i
x
k
0 if x
k
i
> M
i
x
k
(i (x
k
)). (28)
From this choice of a
i
it follows that the corresponding matrix G
k
is an element
of the B-subdierential
B
F(z
k
). Moreover, using (28) and (27), it can easily
be veried that the system G
k
z
k
= F(z
k
) leads to exactly the same system
as (24)(26), i.e., both algorithms are indeed identical. Since Algorithm 1 has
the nite termination property for nondegenerate matrices M with the choice
of a
i
given in (28), it follows directly from the results of Section 3 that the
same holds for Algorithm 2. We will summarize these considerations in the
following theorem, which answers the unsolved question raised by Harker and
Pang [12].
Theorem 12 Let M IR
nn
be a nondegenerate matrix, and let x

be a
solution of the LCP(q, M). If x
k
B

for some small enough > 0, and if

the generalized Newton-equation (23) has a solution x
k
, then the next iterate
x
k+1
generated by Algorithm 2 will coincide with x

.
As noted in [12], the system (23) is always solvable for P-matrix linear com-
plementarity problems. Therefore, if we assume M IR
nn
being a P-matrix,
the additional assumption that the system (23) is solvable can be omitted in
Theorem 12.
13
From Theorem 10, we further get the following result.
Theorem 13 Let x

be a b-regular solution of LCP(q, M). If x

k
B

for
some small enough > 0, and if the generalized Newton-equation (23) has a
solution x
k
, then the next iterate x
k+1
generated by Algorithm 2 will coincide
with x

.
Once again, we note that if the b-regularity assumption of Theorem 13 is
replaced by the stronger R-regularity, the additional assumption of the solv-
ability of the subproblems (23) becomes superuous.
We conclude this section by noting that Harker and Pang [12] were able to
prove that their search direction x
k
is a descent direction for H
2
. This in
turn implies that the search direction z
k
obtained in Algorithm 1 for the
choice of G
k
F(z
k
) based on (28), is also a descent direction for F
2
.
However, this particular choice of G
k
is unknown a priori.
5 Final Remarks
In this paper, we proved that a certain iterative method for the solution of
linear complementarity problems terminates after a nite number of steps
under suitable assumptions. In particular, this result can be applied to an
algorithm of Harker and Pang [12] and gives an armative answer to an
unsolved question raised by these authors.
In order to prove nite termination of Harker and Pangs method, we in-
troduced (as a theoretical tool) the generalized Newton method described in
Algorithm 1. Here we want to mention that there is a close relationship be-
tween Algorithm 1 and (block) principal pivoting methods (see, e.g., J udice
[14] for a recent survey). The central idea of pivoting methods is to maintain
the equations
y
k
= Mx
k
+ q, x
k
i
y
k
i
= 0 (i I) (29)
at all steps k = 0, 1, . . . and to reach the feasibility condition x
k
0, y
k
0
during the iteration. Now consider Algorithm 1 and assume that the matrix
G
k
is always taken from the B-subdierential
B
F(z
k
). Let z
0
= (x
0
, y
0
) be a
starting vector such that (29) is satised for k = 0 (e.g., take x
0
= 0, y
0
= q).
Then it is not dicult to see that (29) holds for all k = 0, 1, . . . as long as
the full stepsize t
k
= 1 is accepted by Algorithm 1. Although the line search
procedure in Step (S.3) distinguishes Algorithm 1 from pivoting methods this
procedure can be viewed as another kind of pivoting rule, see also [12,3].
14
Acknowledgement
We wish to thank the referees, the associate editor and Professor J. J. J udice
for their helpful comments.
References
[1] B. Chen and P. T. Harker, A non-interior-continuation method for linear
complementarity problems, SIAM Journal on Matrix Analysis and Applications
14 (1993) 11681190.
[2] F. H. Clarke, Optimization and Nonsmooth Analysis (John Wiley & Sons, New
York, 1983).
[3] R. W. Cottle, J.-S. Pang and R. E. Stone, The Linear Complementarity Problem
(Academic Press, New York, 1992).
[4] S. P. Dirkse and M. C. Ferris, The PATH solver: a nonmonotone stabilization
scheme for mixed complementarity problems, Optimization Methods and
Software 5 (1995) 123156
[5] F. Facchinei and J. Soares, A new merit function for nonlinear complementarity
problems and a related algorithm, Technical Report 15.94, Dipartimento di
Informatica e Sistemistica, Universita di Roma La Sapienza, Rome, Italy,
1994. To appear in SIAM Journal on Optimization.
[6] M. C. Ferris and S. Lucidi, Globally convergent methods for nonlinear equations,
Journal of Optimization Theory and Applications 81 (1994) 5371.
[7] A. Fischer, A special Newton-type optimization method, Optimization, 24
(1992) 269284.
[8] A. Fischer, A Newton-type method for positive semidenite linear
complementarity problems, Journal of Optimization Theory and Applications
86 (1995) 585608.
[9] A. Fischer, On the superlinear convergence of a Newton-type method for LCP
under weak conditions, Optimization Methods and Software 6 (1995) 83107.
[10] L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique
for Newtons method, SIAM Journal on Numerical Analysis, 23 (1986) 707
716.
[11] P. T. Harker, Lectures on Computation of Equilibria with EquationBased
Methods (CORE Lecture Series, CORE Foundation, Universite Catholique de
Louvain, Louvain-la-Neuve, Belgium, 1993).
15
[12] P. T. Harker and J.-S. Pang, A damped Newton method for the linear
complementarity problem, in: E. L. Allgower and K. Georg, eds., Computational
Solution of Nonlinear Systems of Equations (Lectures on Applied Mathematics
26, AMS, Providence, Rhode Island, 1990) 265284.
[13] P. T. Harker and B. Xiao, Newtons method for the nonlinear complementarity
problem: a Bdierentiable equation approach, Mathematical Programming 48
(1990) 339357.
[14] J. J. J udice, Algorithms for linear complementarity problems, in: E. Spedicato,
ed., Algorithms for Continuous Optimization. The State of the Art (Kluwer
Academic Publishers, Dordrecht, 1994) 435474.
[15] C. Kanzow, Some equation-based methods for the nonlinear complementarity
problem, Optimization Methods and Software 3 (1994) 327340.
[16] C. Kanzow, Global convergence properties of some iterative methods for linear
complementarity problems, Preprint 72, Institute of Applied Mathematics,
University of Hamburg, Hamburg, June 1994 (revised 1995). To appear in SIAM
Journal on Optimization.
[17] C. Kanzow, Some noninterior continuation methods for linear complementarity
problems, Preprint 79, Institute of Applied Mathematics, University of
Hamburg, Hamburg, Germany, February 1994 (revised 1995). To appear in
SIAM Journal on Matrix Analysis and Applications.
[18] C. Kanzow and H. Kleinmichel, A class of Newton-type methods for equality
and inequality constrained optimization, Optimization Methods and Software 5
(1995) 173198.
[19] M. Kojima, N. Meggido, T. Noma and A. Yoshise, A Unied Approach to
Interior Point Algorithms for Linear Complementarity Problems (Lecture Notes
in Computer Science 538, Springer-Verlag, Berlin, Germany, 1991).
[20] M. Kojima and S. Shindo, Extensions of Newton and quasi-Newton methods to
systems of PC
1
equations, Journal of the Operations Research Society of Japan
29 (1986) 352374.
[21] B. Kummer, Newtons method for non-dierentiable functions, in: J. Guddat
et al., eds., Mathematical Research, Advances in Mathematical Optimization
(Akademie-Verlag, Berlin, Germany, 1988) 114125.
[22] O. L. Mangasarian, Equivalence of the complementarity problem to a system of
nonlinear equations, SIAM Journal on Applied Mathematics 31 (1976) 8992.
[23] K. G. Murty, Linear Complementarity, Linear and Nonlinear Programming
(Sigma Series in Applied Mathematics 3, Heldermann Verlag, Berlin, Germany,
1988).
[24] J.-S. Pang, Newtons method for B-dierentiable equations, Mathematics of
Operations Research 15 (1990) 311341.
16
[25] J.-S. Pang, A B-dierentiable equation-based, globally and locally quadratically
convergent algorithm for nonlinear programs, complementarity and variational
inequality problems, Mathematical Programming 51 (1991) 101131.
[26] L. Qi, Convergence analysis of some algorithms for solving nonsmooth
equations, Mathematics of Operations Research 18 (1993) 227244.
[27] L. Qi and J. Sun, A nonsmooth version of Newtons method, Mathematical
Programming 58 (1993) 353367.
[28] S. M. Robinson, Strongly regular generalized equations, Mathematics of
Operations Research 5 (1980) 4362
[29] P. K. Subramanian, Gauss-Newton methods for the complementarity problem,
Journal of Optimization Theory and Applications 77 (1993) 467482.
[30] P. Tseng, Growth behaviour of a class of merit functions for the nonlinear
complementarity problem, Technical Report, Department of Mathematics,
University of Washington, Seattle, WA, May 1994. To appear in Journal of
Optimization Theory and Applications.
[31] L. T. Watson, Solving the nonlinear complementarity problem by a homotopy
method, SIAM Journal on Control and Optimization 17 (1979) 3646.
17