Superlinearly Convergent Algorithms for Solving Singular Equations and Smooth Reformulations of Complementarity Problems.
We propose a new algorithm for solving smooth nonlinear equations in the case where their solutions can be singular. Compared to other techniques for computing singular solutions, a distinctive feature of our approach is that we do not employ second derivatives of the equation mapping in the algorithm and we do not assume their existence in the convergence analysis. Important examples of once but not twice differentiable equations whose solutions are inherently singular are smooth equation-based reformulations of the nonlinear complementarity problems. Reformulations of complementarity problems serve both as illustration of and motivation for our approach, and one of them we consider in detail. We show that the proposed method possesses local superlinear/quadratic convergence under reasonable assumptions. We further demonstrate that these assumptions are in general not weaker and not stronger than regularity conditions employed in the context of other superlinearly convergent Newton-type algorithms for solving complementarity problems, which are typically based on nonsmooth reformulations. Therefore our approach appears to be an interesting complement to the existing ones.
Introduction
. In this paper we are interested in solving nonlinear equations
in the case where their solutions can be singular, and smoothness requirements are
weaker than those usually assumed in this context. Our development is partially
motivated by the nonlinear complementarity problem, which we consider in detail,
and for which our method takes a particularly simple and readily implementable
form.
be a given mapping, where V is a neighborhood of a point
x in
x being a solution of the system of equations
In the sequel, F is assumed to be once (but not necessarily twice) dierentiable on
V . In this setting
x is referred to as singular solution if the linear operator F 0 (x) is
singular, i.e.,
or, equivalently,
In other cases  x is referred to as regular solution.
Computing Center of the Russian Academy of Sciences, Vavilova Str. 40, Moscow, GSP-1, Russia
(izmaf@ccas.ru). Research of this author is supported by the Russian Foundation for Basic Research
Grants 99-01-00472 and 01-01-00810. The rst author also thanks IMPA, where he was a visiting
professor during the completion of this work.
y Instituto de Matematica Pura e Aplicada, Estrada Dona Castorina 110, Jardim Bot^anico, Rio
de Janeiro, RJ 22460-320, Brazil (solodov@impa.br). Research of this author is supported in part
by CNPq Grant 300734/95-6, by PRONEX{Optimization, and by FAPERJ.
A. F. IZMAILOV AND M. V. SOLODOV
gives rise to numerous di-culties. It is well-known that for Newton-type
methods at best one can guarantee linear convergence rate to a singular solution
[6, 7, 9]. Moreover, it is not su-cient to choose a starting point only close enough
to a solution (usually the set of appropriate starting points does not contain a full
neighborhood of the solution, although this set is normally rather \dense" [18]). We
refer the reader to the survey [19] and references therein. Another di-culty typical
in this context is related to possible instability of a singular solution with respect
to perturbations of F [27]. Certain special approaches to overcome those di-culties
have been developed in the last two decades, but they employ second derivatives of
F . Concerning methods for computing singular solutions, we cite [8, 20, 19, 43, 14, 1],
and the more recent proposals in [26, 22, 21, 2, 27, 4] (of course, this list does not
mention all contributions in this eld).
One of the motivations for our new approach to solving singular equations lies in
applications to the classical nonlinear complementarity problem (NCP) [37, 12, 13],
which is to nd an x 2 R n such that
smooth. One of the most useful approaches to numerical and
theoretical treatment of the NCP consists in reformulating it as a system of smooth
or nonsmooth equations [35, 29, 46]. One possible choice of a smooth reformulation
is given by the following function (for other choices, see Section 5.1):
It is easy to check that for this mapping the solution set of the system of equations
coincides with the solution set of the NCP (1.2) [29, 47]. If
x is a solution of the
NCP, by direct computations (see Section 3), we obtain that
denotes the standard basis in R n , and the index sets I 0 , I 1 and I 2
are dened by
I 0 :=
I 1 :=
I 2 :=
It is immediately clear that F 0 (x) cannot be nonsingular, unless the index set I 0 is
empty. The latter strict complementarity assumption is regarded rather restrictive.
Therefore, smooth NCP reformulation provided by (1.3) gives rise to inherently singular
solutions of the corresponding system of equations. In fact, it is known that
any other smooth NCP reformulation has the same singularity properties [31] (see
also Section 5.1). Furthermore, it is clear that F is once dierentiable with Lipschitz-continuous
derivative (if g is twice continuously dierentiable), but F is not twice
dierentiable when I 0 6= ;. This is also a common property shared by all useful
smooth reformulations, e.g., see the collection [16]. Thus NCP reformulations provide
an interesting example of once dierentiable nonlinear equations whose solutions
are inherently singular. As discussed above, application of standard numerical techniques
(e.g., Newton methods) in this context is prone to di-culties (and even failure)
ALGORITHMS FOR SINGULAR EQUATIONS AND COMPLEMENTARITY 3
because of singularity. On the other hand, known special approaches to computing
singular solutions are inapplicable, since these require second derivatives of F . This is
the apparent reason why superlinearly convergent Newton-type algorithms for solving
the NCP are typically based on nonsmooth equation reformulations and nonsmooth
Newton methods (see [13] for a discussion and some references). In this paper we
show that it is, in fact, possible to devise superlinearly convergent algorithms based
on the smooth NCP reformulations. Specically, we propose an alternative approach
based on computing singular solutions of the smooth reformulation stated above, and
show that conditions needed for convergence of our method are principally dierent
from those required for convergence of known nonsmooth algorithms. Thus the two
can be considered as a complement to each other.
We complete this section with some notation, which is fairly standard. We denote
by L n the space of linear operators from R n to R n . For A 2 L n , let ker
stand for its kernel (null space), and im stand for
its image (range space). For a bilinear mapping and an element
the linear operator B[p] 2 L n by Recall that
symmetric bilinear mappings and linear operators of the form p
are in isometrically isomorphic correspondence to each other, i.e., the correspondence
is one-to-one, linear, and it preserves the norm. Therefore, in the sequel we shall not
be making a formal distinction between those objects. Given a set S in a vector space,
by conv S we denote its convex hull, and by span S its linear hull. Finally, by E we
denote the identity operator in R n .
2. A General Approach to Solving Singular Equations. We start with describing
an approach to computing singular solutions of twice dierentiable nonlinear
equations, which was developed in [26, 22, 27]. We then extend it to the setting of
once dierentiable mappings, and in the next section show how it applies to solving
complementarity problems.
A solution
x of (1.1) being regular is equivalent to saying that im F 0
while singularity means that im F 0 (x) 6= R n . In this situation, one possibility to
\regularize" a singular solution
x is to add to the left-hand side of (1.1) another term,
which vanishes at
x (so that
x remains a solution), and such that its Jacobian at  x
\compensates" for the singularity of F 0 (x) (so that to complement im F 0 (x) in R n ).
It is natural to base this extra term on the information about the rst derivative of
F .
To this end, dene the mappings
and consider the equation
Suppose that P () is dened in such a way that for
holds that
Then, by the structure of , solution
x of (1.1) is also a solution for (2.2). Furthermore,
if F is su-ciently smooth (at least twice dierentiable at
x), then under appropriate
assumptions on the rst two derivatives of F at
x, and on P () and h(), it is possible
to ensure that  is dierentiable at  x, and  x is a regular solution of (2.2). As these
assumptions will not be used in this paper, we omit the details, referring the reader
4 A. F. IZMAILOV AND M. V. SOLODOV
to [26, 27]. The regular solution  x of (2.2) can be computed by means of eective
special methods [26, 22, 27], or by conventional numerical techniques (the latter would
typically require stronger assumptions, in order to ensure dierentiability of  not
only at
x but also in its neighborhood). There exist certain general techniques to
dene P () and h() with necessary properties (see [26, 27]). However, when one has
additional information about the structure of singularity of F at
x (e.g., recall (1.4) for
the NCP reformulation), it can often be used to choose P () and h() in a particularly
simple and constructive way. One such application is precisely the NCP, where the
subspace im F 0 (x) can be identied (locally, but without knowing  x), and so the two
mappings can be chosen constant (see Section 3).
In this paper, we shall focus exclusively on the case where it is possible to choose
We emphasize that, of course,
P should be determined without knowing the exact solution  x. The simplest case
when this is possible is when we know that corank F 0
when we are interested in determining a solution specically with this particular type
of singularity. In that case, it is natural to take
In Section 3, we show
how appropriate
P for the NCP reformulation can be determined using information
available at any point close enough to a solution (but without knowing the solution
itself). In general, if P () is dened as a constant
satisfying (2.3), one also can
usually take h()  p, with p 2 R n n f0g being an arbitrary element. Indeed, with
those choices the function dened by (2.1) takes the form
and  x is still a solution of (2.2), due to (2.3). If F is twice dierentiable at
x, then it
is clear that  is dierentiable at this point, and
Therefore,
x is a regular solution of (2.2) if the linear operator in the right-hand side
of (2.5) is nonsingular. This is possible under appropriate assumptions. Since the
case of twice dierentiable F is not the subject of this paper, we shall not discuss here
technical details. We only note that nonsingularity of (2.5) subsumes the condition
Observe that the latter relation implies that (2.3) must hold as equality. Summarizing,
we obtain the following assumptions on the choice of
ker
These assumptions clearly hold if, for example,
P is the projector onto some complement
of im F 0 (x) in R n parallel to im F 0 (x). With this choice, nonsingularity of (2.5)
formally coincides with the notion of 2-regularity of  at
x with respect to p 2 R n ,
in the sense of [23, 3, 27]. We note, however, that this connection does not seem conceptually
important, and in fact, appears to be in some sense a coincidence. Indeed,
in the case of once dierentiable mappings considered below, nonsingularity condition
that would be required no longer has any direct relation to 2-regularity for mappings
with Lipschitzian derivatives, as dened in [24, 25].
As a nal note, we remark that it can be shown (by simple argument, see [26, 27])
that if there exists at least one element p 2 R n such that the operator (2.5) is
nonsingular, then it will be so for almost every p 2 R n .
ALGORITHMS FOR SINGULAR EQUATIONS AND COMPLEMENTARITY 5
We conclude the discussion of the twice dierentiable case by the following ex-
ample, which is very simple but serves to illustrate the basic idea.
Example 2.1. Let R be twice continuously dierentiable
on V , where V is a neighbourhood of
x 2 R which is a singular solution of (1.1).
The latter means here that F Taking
we obtain the following regularized equation: Obviously,
which is distinct from zero for any p 2 R n f0g,
This shows that in this example, if F 00 (x) 6= 0, singularity can
be easily dealt with by using the second-order information.
In the approach outlined above, F is assumed to be twice dierentiable. Suppose
now that F is once (but not twice) dierentiable, and its rst derivative is Lipschitz-continuous
on V . Then  dened by (2.4) is also Lipschitz-continuous on V , and it
is natural to try to apply to the corresponding equation (2.2) the generalized (non-
smooth) Newton method [32, 33, 41, 42, 40, 28]. We emphasize that we shall use
the nonsmooth Newton method to solve a (nonsmooth) regularization of a smooth
equation. In the context of NCP, this should be compared to the more traditional
approach of solving an inherently nonsmooth reformulation by the nonsmooth Newton
method. As we shall show in Section 4, the two dierent approaches lead to two
dierent regularity conditions, neither of which is weaker or stronger than the other.
Let @(x) denote the Clarke's generalized Jacobian [5] of  at x 2 V . That is
where @B (x) stands for the B-subdierential [45] of  at x, which is the set
with D  V being the set of points at which  is dierentiable. With this notation,
the nonsmooth Newton method is the following iterative procedure:
It is well-known [42, 40, 28] that if
(i)  is semismooth [36] at  x, and
(ii) all the linear operators comprising @(x) are nonsingular,
then the process (2.7) is locally well-dened and superlinearly convergent to  x. More-
over, if  is strongly semismooth [36] then the rate of convergence is quadratic.
The regularity condition (ii) can be relaxed if a more specic rule of determining
employed. For example, if one chooses
is enough to assume BD-regularity, i.e., that all elements in @B (x) are nonsingular
[41].
In applications,  usually has some special (tractable) structure, and at each
iterate x k we are interested in obtaining just one, preferably easily computable,
This would be precisely the case here. The choice of an element
in @(x) that we suggest to use in the nonsmooth Newton method for solving (2.2)
with  given by (2.4), is the following:
denotes the usual directional derivative of the mapping
at with respect to a direction p 2 R n . In Section 3, we show that this
6 A. F. IZMAILOV AND M. V. SOLODOV
H(x) is explicitly and easily computable for the NCP reformulations. The validity
of the choice suggested in (2.8) for an element of @(x) is actually not so obvious.
The possibility of choosing the directional derivative (
as an element in the
generalized Jacobian of
is based on the following fact. At a point x
its derivative is in fact the second derivative of
PF (). Due to
can be considered as a symmetric bilinear mapping. This symmetry
will be essential in the proof of Lemma 2.1 below. For a mapping x ! Q(x)p, where
is an arbitrary Lipschitzian mapping, the inclusion
can be in general invalid.
Lemma 2.1. Suppose that F : V ! R n has a Lipschitzian derivative on V , where
V is an open set in R n . Assume that for some
the mapping
is directionally dierentiable at a point x 2 V with respect to a direction p 2 R n .
are dened in (2.8) and (2.4), respectively.
Proof. Since
clearly Lipschitz-continuous, using further the assumption
that
PF 0 is directionally dierentiable at x with respect to p, it follows that there
exists a linear operator
The above conclusion can be deduced from [42, Lemma 2.2(ii)] after identifying the
space L n with the equivalent space R m , using the equivalence of the
norms in nite-dimensional spaces.
By the denition of the generalized Jacobian, B 2 @(
means that there
exist an integer m, sequences fx i;k g  V and numbers  i , with the
following properties:  i
is dierentiable at each x i;k , and
where the limits in the right-hand side of the second equality exist for each
Note that dierentiability of
at each x i;k means that the mapping
twice dierentiable at these points. Taking into account the symmetry of
the bilinear mapping representing the second derivative, we conclude that
Therefore,
where the second equality follows from (2.10), and the third from (2.9). Using the
denition of the generalized Jacobian, we conclude that H(x) 2 @(x).
Remark 2.1. There exists another way to construct the regularized equation
which can have advantages in certain situations over the one described
above. Specically, the mapping  dened by (2.4) can be modied as follows:
ALGORITHMS FOR SINGULAR EQUATIONS AND COMPLEMENTARITY 7
It is clear that with this denition,
x is still a solution of Modifying H
accordingly, we have
Furthermore, it is clear that Lemma 2.1 is still valid with  and H dened by (2.11)
and (2.12). Finally, it is easy to see that since
the possible limits of H(x)
as
x are the same, whether H is dened by (2.8) or (2.12). Hence, the regularity
condition at
x that would be needed for the superlinear convergence of our method
is again the same, whether the method is applied to one regularized equation or the
other.
The possible advantage of the modied equation is the following. If singularity
of F 0 (x) has a certain structure, then not all the components of F may need to be
computed in (2.11). Furthermore, (2.12) can also take a simpler form in that case.
For example, suppose that F 0 (x) is such that
satisfying (2.3) can be chosen as
the orthogonal projector onto the subspace span fe is the
standard basis in R n and I
P is the orthogonal projector
onto span fe ng n Ig. It is easy to see that in this case, (2.11) would not
require computing the function values F i I . Furthermore, the derivatives of
would not appear in (2.12), and so this part would also be simplied. This
feature would be further illustrated in the context of NCP in Section 3.
In the sequel, we shall also consider the following modication of the Newton
algorithm (2.7), which will be useful for solving the NCP reformulation in Section 3:
This modication is essentially motivated by the idea of \truncating" elements of the
(generalized) Jacobian by omitting the terms which vanish at the solution
x. These
terms typically involve some higher-order derivatives of the problem data (in the
context of NCP (1.2), the second derivatives of g), and so it can be advantageous not
to compute them, if possible.
Note that the regularity condition which is typically employed in nonsmooth
Newton methods consists of saying that every element in the generalized Jacobian
@(x) (or the B-subdierential @B (x)) is nonsingular (recall condition (ii) stated
above). This seems to be unnecessarily restrictive, because in most implementable
algorithms some specic rule to choose H(x k used. We shall therefore
replace the traditional condition by a weaker one. Specically, we shall assume that
all the possible limits of H(x k ) as x k !
x are nonsingular, where H(x k ) is precisely
the element given by (2.8) (or by (2.12)). To this end, we shall dene the set
Hg:
Our regularity assumption would be that elements in  p (x) are nonsingular. We
remind the reader that this set is the same for both choices of H , i.e., (2.8) and (2.12).
We point out that unlike in the twice dierentiable case, this regularity condition
cannot be related to the notion of 2-regularity [24, 25] of  at
x.
Lemma 2.1 in hand, convergence of algorithms (2.7) and (2.13), with the
data dened in (2.4) and (2.8) or (2.11) and (2.12), can be established similarly to
[41], but taking into account the modied nonsingularity assumption.
8 A. F. IZMAILOV AND M. V. SOLODOV
Theorem 2.2. Suppose has a Lipschitz-continuous derivative on
is a neighborhood of a solution  x of (1.1). Let
Assume further that the mapping
directionally dierentiable with
respect to a direction p 2 R n at any point in V , and the mapping
is semismooth at
x. Let  and H be dened by (2.4) and (2.8), or (2.11) and (2.12).
Assume further that all linear operators comprising  p (x) are nonsingular.
Then the iterates given by (2.7) or (2.13) are locally well-dened, and converge
to  x superlinearly. If, in addition, the mapping
strongly semismooth at  x
then the rate of convergence is quadratic.
Proof. It is easy to see that under our regularity assumption, (H()) 1 is locally
uniformly bounded. Indeed, assume the contrary, i.e., that there exists a sequence
x, and the sequence f(H(x k is unbounded
(this subsumes the possibility that some elements of the latter sequence are not even
well-dened). Recall that the generalized Jacobian is locally bounded [5]. Since,
by Lemma 2.1, H(x k ) 2 @(x k ) for every k, it follows that the sequence fH(x k )g is
bounded. Hence, we can assume that fH(x k )g converges to some
the inclusion is by the very denition of the set  p (x). But then
H is nonsingular,
which is in contradiction with the earlier assumption that f(H(x k is unbounded.
Consider rst algorithm (2.7), and suppose that the iterates are well-dened up
to some index k  0. We have that
where M > 0. Note that when
semismooth, so is (). It is
known [40, Proposition 1] that semismoothness of  at  x implies that
sup
(the latter property was introduced in the context of the nonsmooth Newton methods
in [33]). Using Lemma 2.1 and combining the last two relations, well-denedness of
the whole sequence fx k g and its superlinear convergence to  x follow by a standard
argument.
In the strongly semismooth case, one has that
sup
and so convergence is quadratic.
Consider now the iterates fx k g generated by (2.13). By our regularity assumption
and the classical results of linear analysis, the condition
implies that
Hence,
ALGORITHMS FOR SINGULAR EQUATIONS AND COMPLEMENTARITY 9
where the Lipschitz-continuity of  was also used. It follows that the dierence between
the original and modied steps is of the second order. By the obvious argument,
it can now be easily seen that the modied algorithm has the same convergence rate
as the original one.
Note that in principle, our regularity condition depends not only on the structure
of singularity of F at  x, but also on the choice of p. Implementation of this approach
presumes that there exists at least one p 2 R n for which this condition is satised.
Furthermore, a way to choose such p should be available. Fortunately, a typical
situation is the following. The existence of one suitable p can usually be established
under some reasonable regularity assumption. Then, given the existence of one such
it can further be proven that the set of appropriate elements is, in fact, open and dense
in the whole space. Hence, p can be chosen arbitrary, with the understanding that
almost any is suitable. We shall come back to this issue in Section 4, where regularity
conditions for NCP are discussed. In the computational experience of [22, 26], where
conceptually related methods for smooth operator equations are considered, a random
choice of p does the job. Even though this choice certainly aects the rate and range
of convergence, the dierences between dierent choices are usually not dramatic.
Finally, we remark that the development presented above can be extended to the
case when P () is not necessarily constant, but it is a Lipschitzian mapping satisfying
with
In that case, we would have to provide a technique to dene
such P () in the general setting. Such techniques are possible, but they go beyond the
scope of the present paper. Here we are mainly concerned with a specic application
of our approach to the nonlinear complementarity problem, which we consider next.
3. Algorithm for the Nonlinear Complementarity Problem. Consider
the nonlinear complementarity problem (1.2), and its reformulation as a system of
smooth equations (1.1), given by (1.3). For convenience, we re-state the associated
function F , which is
We choose a specic reformulation for the clarity of presentation. In Section 5.1, we
show that our analysis is intrinsic and extends to other smooth reformulations.
Let
x 2 R n be a solution of NCP. Suppose that g is twice continuously dier-
entiable in some neighborhood V of
x in R n . Then it is easy to see that F has a
Lipschitz-continuous derivative on V , which is given by
is the standard basis in R n . Recalling the three index sets
I 0 :=
I 1 :=
I 2 :=
from (3.1) we immediately obtain that
(3.
A. F. IZMAILOV AND M. V. SOLODOV
As already discussed in Section 1, the Jacobian F 0 (x) is necessarily singular whenever
I 0 6= ;, the latter being the usual situation for complementarity problems of interest.
Furthermore, F is not twice dierentiable. Hence, smooth NCP reformulations fall
precisely within the framework of Section 2. Such equations cannot be eectively
solved by previously available methods, and so our approach comes into play. We
next show that in the setting of NCP, the general algorithm introduced in Section 2
takes a simple implementable form.
Given the structure of F 0 (x), we have that
Then the natural choice of
condition (2.3)), is
the operator with the matrix representation consisting of rows
At the end of this section, we shall show how to dene
knowing the solu-
tion
x (clearly, this task reduces to identifying the index set I 0 ). This is possible by
means of error bound analysis. A su-cient condition for our error bound is weaker
than b-regularity [39], which is currently the weakest assumption under which Newton
methods for nonsmooth NCP reformulations are known to be (superlinearly) convergent
[30, 34].
Once
P is dened according to (3.3), we x p 2 R n n f0g arbitrarily. Then the
function  dened by (2.4) takes the form
According to Section 2,
x is a solution of which is our \regularized" equa-
tion. We proceed to derive explicit forms for iterations of algorithms (2.7) and (2.13),
and the regularity condition needed for their convergence.
First, by (2.8) and (3.3), the matrix representation of H(x), which is the element
of @(x) employed in algorithm (2.7), consists of rows
Furthermore, the directional derivatives employed in (3.5) exist, and can be obtained
explicitly from (3.1):
where
ALGORITHMS FOR SINGULAR EQUATIONS AND COMPLEMENTARITY 11
Note that according to (3.5), one has to compute
Another
useful observation which would suggest truncation of the Jacobian to be discussed
later, is that for i 2 I 0 all the terms in (3.6) involving the second derivatives of g
vanish at
x.
Furthermore, taking into account (3.5), (3.2), (3.6) and (3.7), we conclude that
the matrix representation of an arbitrary limit point
H of H(x) as x !  x consists of
rows
Hence, we can state the following su-cient condition for nonsingularity of every linear
operator in  p (x). Denote by J the collection of pairs of index sets (J
that Our regularity condition consists of saying that for
every pair of index sets (J holds that
are linearly independent in R
In Section 4, we shall discuss the relation between this condition and other regularity
conditions for the NCP, as well as compare convergence results of our algorithm with
convergence results of other locally superlinearly convergent equation-based methods
for solving NCP.
Under our assumptions, semismoothness of
readily from (3.1)
and standard calculus of semismooth mappings [36, Theorem 5]. Moreover, under
the additional assumption of Lipschitz-continuity of g 00 () on V ,
strongly
semismooth, which follows from results on the superposition of strongly semismooth
mappings [15, Theorem 19]. Hence, () is (strongly) semismooth.
Note that all the elements involved in the iteration scheme (2.7) are computed in
this section by explicit formulas. In principle, computing H via (3.5)-(3.7) involves
second derivatives of g. However, as already noted above, the terms containing second
derivatives of g tend to zero as x !  x. This suggests the idea to modify the process
by omitting these terms, which leads to the method represented by (2.13). We shall
also take into account the structure of
P , and make use of Remark 2.1.
Note that for
given by (3.3), we have that (E
P ) is the orthogonal projector
onto span fe g. According to (2.11), we can therefore re-dene
Taking into account (2.12) and omitting further the terms that vanish at
x, we can
take
~
Comparing expressions (3.9) and (3.10) with (3.4) and (3.5), one can easily observe
that the former are simpler and require less computations.
A. F. IZMAILOV AND M. V. SOLODOV
Furthermore, under our smoothness assumptions, it is easy to see that
and so the modied Newton method given by (2.13) is applicable.
We next give a formal statement of the convergence result for our methods applied
to NCP, which is a corollary of Theorem 2.2.
Theorem 3.1. Let be a twice continuously dierentiable mapping
on being a neighborhood of a solution
x of the NCP (1.2). Assume that for some
condition (3.8) is satised for every pair of index sets (J
Then the iterates given by (2.7) or (2.13) (with all the objects as dened in this
section) converge to
x locally superlinearly. If, in addition, the second derivative of g
is Lipschitz-continuous on V , then the rate of convergence is quadratic.
We next show how to construct
knowing the solution  x. Given the
structure of
P , see (3.3), it is clear that this task reduces to correct identication of
the degenerate set I 0 . This can be done with the help of error bounds, as described
next (our approach is in the spirit of the technique developed in [10] for identication
of active constraints in nonlinear programming). To our knowledge, the weakest
condition under which a local error bound for NCP is currently available is the 2-
regularity of F given by (1.3) at the NCP solution  x [25]. Specically, if F is 2-regular
at  x then there exist a neighborhood U of  x in R n and a constant M 1 > 0 such that
We shall not introduce the notion of 2-regularity formally here, as this would require
an extensive discussion. We only emphasize that the bound (3.11) may hold when the
so-called natural residual minfx; g(x)g does not provide an error bound, and always
holds when it does (see [25], and in particular [25, Example 1]). Hence, 2-regularity
of F is a weaker assumption than the R 0 type property or semistability, which in case
of NCP are both equivalent to an error bound in terms of the natural residual [38].
And it is further weaker than b-regularity, see [25].
We note that in Lemma 3.2 below we could also use other error bounds for
identifying I 0 . However, they would require either stronger local assumptions, or
global assumptions.
Lemma 3.2. Suppose that
x is a solution of NCP, g is Lipschitz-continuous on
is a neighborhood of  x. Suppose nally that the local error bound (3.11)
holds. Then for any  2 (0; 1) there exists a neighborhood U of
x such that
ng
Proof. It is easy to observe that there exist some M 2 > 0 and some neighborhood
U of
x such that
where the inequality follows from the Lipschitz-continuity of the functions involved.
Therefore, by (3.11) (possibly adjusting the neighborhood U ), for an arbitrary xed
we have that
ALGORITHMS FOR SINGULAR EQUATIONS AND COMPLEMENTARITY 13
In particular, the quantity in the left-hand side of the inequality above tends to zero
as x tends to
x. On the other hand, it is clear that there exists " > 0 such that
(U should be adjusted again, if necessary). Combining those facts, we obtain (3.12)
for U su-ciently small.
By Lemma 3.2, the index set I 0 , and hence the mapping
P , are correctly identied
by (3.12), provided one has a point close enough to the solution. We note that this
requirement of closedness to solution is completely consistent with the setting of the
paper, since the subject under consideration are superlinearly convergent Newton-like
methods, which are local by nature.
Finally, we mention other considerations that can also be useful for identifying
I 0 . Sometimes the cardinality r of I 0 may be known from a priori analysis of the
problem, or one can be interested in nding an NCP solution with a given cardinality
of I 0 . Then for any x 2 R n su-ciently close to
x, the set I 0 coincides with the set
of indices corresponding to the r smallest values of j maxfg i (x); x i gj. In this case, no
error bound is needed to identify I 0 . We note that in the present setting, cardinality
of I 0 is closely related to corank of singularity. In the literature on numerical methods
for solving singular equations, the assumption that corank of singularity is known is
absolutely standard [20, 19, 43, 14, 1, 2]. In the complementarity literature, on the
other hand, assumptions about cardinality of I 0 are not common, except possibly for
I
4. Regularity Conditions. The weakest condition under which there exists
a locally superlinearly convergent Newton-type algorithm for solving a (nonsmooth)
equation reformulation of the NCP, is the b-regularity assumption, which can be stated
as follows: for every pair of index sets (J holds that
are linearly independent in R
Under this assumption, the natural residual mapping x !
is BD-regular at
x. Furthermore, it is also (strongly) semismooth under standard
assumptions on g. Hence, the nonsmooth Newton method (2.7) based on it converges
locally superlinearly [30, 34]. Note that Newton methods applied to another
popular reformulation based on the Fischer-Burmeister function [17, 11], require for
convergence the stronger R-regularity [44] assumption, see [34].
In what follows, we compare our regularity condition (3.8) with b-regularity, and
show that they are essentially dierent. In general, neither is weaker or stronger than
the other. This implies that our approach based on the smooth NCP reformulation
is a complement to nonsmooth reformulations, and vice versa, as each approach can
be successful in situations when the other is not.
The next result is important to obtain an insight into the nature of our regularity
condition (3.8). We start with the following denition.
Definition 4.1. A solution  x of the NCP (1.2) is referred to as quasi-regular, if
for every pair of index sets (J there exists an element
such that (3.8) is satised.
Proposition 4.2. Suppose that the solution  x of the NCP (1.2) is quasi-regular.
Then there exists a universal p 2 R n which satises (3.8) for every pair (J
J . Moreover, the set of such p is open and dense in R n .
14 A. F. IZMAILOV AND M. V. SOLODOV
Proof. Fix a pair (J consider the determinant of the system
of vectors in (3.8) as a function of p. This function is a polynomial on R n , and this
polynomial is not everywhere zero, since it is not zero at
But then the set where the polynomial is not zero is obviously open and dense in R n .
Moreover, the intersection of such sets corresponding to pairs (J
open and dense, since it is a nite intersection of open and dense sets.
It follows that if  x is a quasi-regular solution of NCP in the sense of Denition
4.1, then even picking a random p 2 R n one is extremely unlikely to pick a \wrong"
(as the set of wrong elements is \thin"). Hence, under the assumption of quasi-
regularity, for the implementation of the algorithm described in Section 3 we can
choose arbitrarily, with the understanding that almost every p 2 R n is
appropriate. In particular, for all practical purposes, we can think of quasi-regularity
as the regularity condition needed for superlinear convergence of our algorithm. We
next investigate the relationship between quasi-regularity and b-regularity.
First, we show that if the cardinality of I 0 is equal to one, then quasi-regularity
is in fact weaker than b-regularity.
Proposition 4.3. Suppose that  x is a b-regular solution of the NCP, and the
cardinality of I 0 is equal to one. Then
x is quasi-regular.
Proof. Let I and denote
g. In this
setting, b-regularity clearly means that
corresponding to the two possible choices of (J It follows that
Assume for a contradiction that  x is not quasi-regular. Then by Denition 4.1, there
exists a pair (J such that for every p 2 R n condition (3.8) is violated. This
means that is either
or
Taking any q 2 L ? n f0g, we deduce that for every p 2 R n either
or
Setting we then obtain that either
or
ALGORITHMS FOR SINGULAR EQUATIONS AND COMPLEMENTARITY 15
which contradicts b-regularity, because of (4.1).
It is easy to see that in the setting of Proposition 4.3, the quasi-regularity condition
can be satised without b-regularity. For example, let g 0
Then b-regularity is violated. On the other hand, quasi-regularity here is equivalent
to saying that there exist elements (corresponding to the two possible
choices of (J
which is satised for almost any p 1 and p 2 , provided
It is also quite clear
that just choosing randomly should do the job.
In general, i.e., in the cases of higher cardinality of I 0 , b-regularity and quasi-regularity
become dierent, not directly related conditions. In particular, neither is
stronger or weaker than the other, as illustrated by the following examples.
Example 4.1. Let
Then b-regularity is obvious, but
This means that for J does not hold for any p, and so the
quasi-regularity condition is not satised.
Example 4.2. Let
Then b-regularity does not hold (the linear independence condition is violated for
but quasi-regularity is satised, which can be shown by straight-forward
computations. We omit the details, as they do not provide any further insight

We complete our discussion with a su-cient condition for quasi-regularity of  x,
which is meaningful when the cardinality of I 0 is not greater than n=2, half dimensionality
of the space. Specically, suppose that
are linearly independent in R n ;
and
are linearly independent in R
It is clear that (4.3) is subsumed by b-regularity (where it must hold for all partitions
of I 0 ). It is also not di-cult to see that (4.3) is necessary for quasi-regularity of  x.
Hence, this assumption does not introduce any additional restrictions with respect to
regularity conditions under consideration. Furthermore, for non-pathological problems
the cardinality of I 0 should not be too large compared to the dimensionality of
the space, and so condition (4.2) should not be di-cult to satisfy. Therefore, (4.2)
and (4.3) appear to be not restrictive.
Proposition 4.4. Suppose that (4.2) and (4.3) hold. Then  x is a quasi-regular
solution of NCP.
A. F. IZMAILOV AND M. V. SOLODOV
Proof. Take any pair of index sets (J consider the system of (twice
the cardinality of I 0 ) linear equations
in the variable p 2 R n . Under the assumption (4.2), this system has a solution
further that substituting this p into (3.8) reduces the system
of vectors appearing in (3.8) precisely to the system of vectors appearing in (4.3),
which is linearly independent by the hypothesis.
Again, it is easy to see that the latter su-cient condition for quasi-regularity of
x can hold without b-regularity. On the other hand, in general it is not implied by
b-regularity. In particular, b-regularity need not imply (4.2).
Summarizing the preceding discussion, we conclude that the regularity assumption
required for the algorithm proposed in Section 3 for solving the NCP is dier-
ent from b-regularity, which is the typical assumption in the context of nonsmooth
Newton-type methods for solving nonsmooth NCP reformulations. In fact, the two
assumptions are of a rather distinct nature. This is not surprising, considering that
they result from approaches which are also quite dierent.
5. Some Further Applications. The general approach presented in Section
2 can be also useful in other problems where complementarity is present. Below
we outline applications to another class of smooth reformulations of NCP (dierent
from (1.3)), and to the mixed complementarity problems. We limit this discussion to
exhibiting the structure of singularity associated with the smooth equation reformulations
of those problems. Deriving the resulting regularity conditions and comparing
them to known ones requires too much space. Without going into detail, we claim
that regularity assumptions needed for our approach would again be dierent from
assumptions of Newton methods for nonsmooth equations.
5.1. Other NCP Reformulations. The analysis presented in Sections 3 and
4 for NCP is intrinsic in the sense that it is also applicable to smooth reformulations
other than the one given by (1.3). Indeed, following [35], consider the family of
functions
strictly increasing function such that It can be
checked that the NCP solution set coincides with zeroes of F . As an aside, note that
reformulation (1.3) cannot be written in the form stated above, so the two are really
dierent.
Suppose further that  is dierentiable on R with  0
t > 0. For example, we could take
Let
x be some solution of NCP, and V be its neighborhood. If g is twice continuously
dierentiable on V and  0 is Lipschitz-continuous, then the derivative of F is Lipschitz-continuous
near
x, and it is given by
ALGORITHMS FOR SINGULAR EQUATIONS AND COMPLEMENTARITY 17
As is easy to see,
Since  0 (t) > 0 for any t > 0, we conclude that the structure of singularity here is
absolutely identical to that for F given by (1.3) (recall (1.4)). In particular,
and all the objects and the analysis in Sections 3 and 4 can be derived in a similar
fashion.
5.2. Mixed Complementarity Problems. The mixed complementarity problem
(MCP) is a variational inequality on a (generalized) box
ug, where l i 2 [1;+1) and u are such that l i < u
Specically, the problem is to nd
It can be seen that this is equivalent to x 2 R n satisfying the
following conditions: for every
if
if
if
NCP is a special case of MCP corresponding to l
We claim that solutions of MCP coincide with zeroes of the function F
whose components are given by
We omit the proof, which can be carried out by direct verication. Let  x be some
solution of MCP, and V be its neighborhood. If g is twice continuously dierentiable
on V then the derivative of F is Lipschitz-continuous near
x. Dening
I 0 :=
I 1 :=
I 2 :=
it can be veried that
A. F. IZMAILOV AND M. V. SOLODOV
where
In particular,  i . Observing the structure of F 0 (x),
further analysis can now follow the ideas of Sections 3 and 4.
6. Concluding Remarks. We have presented a new approach to solving smooth
singular equations. Unlike previously available algorithms, our method is applicable
when the equation mapping is not necessarily twice dierentiable. Important examples
of once dierentiable singular equations are reformulations of the nonlinear
complementarity problems, which we have studied in detail. In particular, we have
demonstrated that in the case of NCP our method takes a readily implementable
simple form. Furthermore, the structure of singularity can be completely identied
by means of local error bound analysis, without knowing the solution itself. It was
further shown that the regularity condition required for the superlinear convergence of
the presented algorithm is dierent from conditions needed for the nonsmooth Newton
methods applied to nonsmooth NCP reformulations. Thus the two approaches should
be regarded as complementing each other. Finally, it was demonstrated that the main
ideas of this paper should be also applicable to other problems where complementarity
structures are present.



--R



Optimality Conditions: Abnormal and Degenerate Problems.
An approach to
Optimization and Nonsmooth Analysis.
Newton's method at singular points.
Newton's method at singular points.
Convergence acceleration for Newton's method at singular points.
Convergence rates for Newton's method at singular points.
On the accurate identi
A new merit function for nonlinear complementarity problems and a related algorithm.
Pang (editors). Complementarity and variational problems: State of the Art.

A geometric framework for the numerical study of singular points.
Solution of monotone complementarity problems with locally Lipschitzian functions.

On the resolution of monotone complementarity problems.
Starlike domains of convergence for Newton's method at singularities.
On solving nonlinear equations with simple singularities or nearly singular solutions.
Characterization and computation of generalized turning points.
Augmented systems for computation of singular points in Banach space problems.
Stable methods for
On certain generalizations of Morse's lemma.
The theory of 2-regularity for mappings with Lipschitzian derivatives and its applications to optimality conditions
bounds for 2-regular mappings with Lipschitzian derivatives and their applications
Local regularization of certain classes of nonlinear operator equations.

Semismoothness and superlinear convergence in non-smooth optimization and nonsmooth equations
Some equation-based methods for the nonlinear complementarity problem
Solving box constrained variational inequality problems by using the natural residual with D-gap function globalization
A new class of semismooth Newton-type methods for nonlinear complementarity problems
Newton's method for nondi
Newton's method based on generalized derivatives for nonsmooth functions.
A theoretical and numerical comparison of some semismooth algorithms for complementarity problems.
Equivalence of the complementarity problem to a system of nonlinear equations.

Pang Complementarity problems.
Pang Private communication
NE/SQP: A robust algorithm for the nonlinear complementarity
Nonsmooth equations: Motivation and algorithms.
Convergence analysis of some algorithms for solving nonsmooth equations.
A nonsmooth version of Newton's method.
Characterization and computation of singular points with maximum rank de
Strongly regular generalized equations.
Local structure of feasible sets in nonlinear programming

Growth behavior of a class of merit functions for the nonlinear complementarity problem.
--TR
singularity;superlinear convergence;complementarity;reformulation;nonlinear equations;regularity