On the Accurate Identification of Active Constraints.
We consider nonlinear programs with inequality constraints, and we focus on the problem of identifying those constraints which will be active at an isolated local solution. The correct identification of active constraints is important from both  a theoretical and a practical point of view. Such an identification removes the combinatorial aspect of the problem and locally reduces the inequality constrained minimization problem to an equality constrained problem which can be more easily dealt with. We present a new technique which identifies active constraints in a neighborhood of a solution and which requires neither complementary slackness nor uniqueness of the multipliers. We also present extensions  to variational inequalities and  numerical examples illustrating the identification technique.
Introduction
In this paper we consider the problem of identifying the constraints which are active
at an isolated stationary point -
x of the nonlinear program
where it is assumed that the functions f are at least
continuously differentiable. More specifically, we are interested in the following
question: Given an (x; -) 2 IR n+m belonging to a sufficiently small neighborhood
of a Karush-Kuhn-Tucker (KKT) point of Problem (P), is it possible to correctly
estimate, on the basis of the problem data in x, the set of indices
I 0 := fij g i
of the active constraints? The correct identification of active constraints is important
from both a theoretical and a practical point of view. Such an identification,
by removing the difficult combinatorial aspect of the problem, locally reduces the
inequality constrained minimization problem to an equality constrained one which
is much easier to deal with. In particular, the study of the local convergence rate
of most algorithms for Problem (P) implicitly or explicitly depends on the fact that
I 0 is eventually identified.
The identification of the active constraints is not difficult if strict complementarity
holds at the solution, see the discussion in the next section. However, as far
as we are aware of, to date no technique can successfully deal with the case in which
the complementary slackness assumption is violated, except in the case of linear
programs, see [10]. In this paper we present a new technique which, under mild as-
sumptions, correctly identifies active constraints in a neighborhood of a KKT point.
This technique appears to improve on existing techniques. In particular, it enjoys
the following properties:
(i) It is simple and independent of the algorithm used to generate the point (x; -).
(ii) It does not require complementary slackness.
(iii) It does not require uniqueness of the multipliers.
(iv) It does not rely on any convexity assumption.
(v) In the case of unique multipliers it also permits the correct identification of
strongly active constraints.
(vi) The identification technique can be applied also to the Karush-Kuhn-Tucker
system arising from variational inequalities.
IDENTIFICATION OF ACTIVE CONSTRAINTS 3
Strategies for identifying active constraints are part of the optimization folklore
[2, 13, 15], however, they almost invariably lack many of the good characteristics
listed above. In the last ten years a special attention has been devoted to this
problem in the field of interior point methods for linear programs; we refer the reader
to the survey paper [10]. Recent works on the nonlinear case include [9, 11, 23], where
the case of box constraints is considered, and [12, 36], where the general nonlinear
case is studied. Related material can also be found in [4, 5, 6], where the problem
of establishing whether or not a sequence fx k g, converging to a solution -
x, in some
way identifies the set I 0 is dealt with. Note, however, that in these latter papers
no explicit rule is given in order to identify the active constraints from a close, but
arbitrary point.
We remark that, in order to identify the active set, we suppose we are given a
pair (x; -) of primal and dual variables. If we think of algorithmic applications of
the results in this paper, we stress that most algorithms will produce a sequence
of primal and dual variables. Even in the rare cases in which this does not occur,
it is usually possible, under reasonable assumptions, to generate a continuous dual
estimate by using a multiplier function, see, e.g., [12] and references therein, as well
as Section 4.
This paper is organized as follows. In the next section we introduce the identification
technique and prove its main properties. The identification technique critically
depends on the definition of what we call identification function. Therefore, the
more technical Section 3 is devoted to the definition of identification functions under
different sets of assumptions. In Section 4 we use the results of the previous
sections in order to define a local active set Newton-type algorithm for the solution of
inequality constrained optimization problems for which a Q-quadratic convergence
rate of the primal variables can be proved under very weak conditions. In Section 5
we give some final comments.
We conclude this section by providing a list of the notation employed. Through-out
the paper, k \Delta k indicates the Euclidean vector norm. The symbol B ffl denotes
the open Euclidean ball with radius ffl ? 0 and center at the origin; the dimension of
the space will be clear from the context. The Euclidean distance of a point y from a
nonempty set S is abbreviated by dist[y; S]. We write x+ for the vector maxf0; xg;
where the maximum is taken componentwise. We set I := use
of the notation x J for J ' I in order to represent the jJ j-dimensional vector with
components Finally, the transposed Jacobian of the vector-valued mapping
g at a point x will be denoted by rg(x); i.e., the ith column of this matrix is the
gradient rg i (x):
Active Constraints
Following the usual terminology in constrained optimization, we call a vector -
a stationary point of (P) if there exists a vector - 2 IR m such that (-x; -
-) solves the
4 F. FACCHINEI, A. FISCHER AND C. KANZOW
Karush-Kuhn-Tucker system
(1)
The pair (-x; -) is called a KKT point of Problem (P). In the sequel -
x will always
denote a fixed, isolated stationary point, so that there is a neighborhood of -
x which
does not contain any further stationary point of (P). Moreover, we shall indicate
by   the set of all Lagrange multipliers -
- associated with - x and by K the set of all
KKT points associated with -
x, that is,
-) solves (1)g; K := f(-x; -
The set   is closed and convex and therefore, so is the set K. Gauvin [14] showed
that   is bounded (and hence compact) if and only if the Mangasarian-Fromovitz
constraint qualification (MFCQ) is satisfied, i.e., if and only if
On the other hand, Kyparisis [22] showed that   reduces to a singleton if and only
if the strict Mangasarian-Fromovitz constraint qualification (SMFCQ) holds, i.e., if
and only if
denotes the index set
I
In particular, the linear independence constraint qualification (LICQ), i.e., the linear
independence of the gradients of the active constraints, implies that   is a singleton.
Our basic aim is to construct a rule which is able to assign to every point (x; -)
an estimate A(x; -) ' I so that A(x; lies in a suitably small
neighborhood of a point (-x; -) 2 K.
Usually estimates of this kind are obtained by comparing the value of g i (x) to
the value of - i . For example, it can easily be shown that the set
I \Phi (x; -) :=
coincides with the set I 0 for all (x; -) in a sufficiently small neighborhood of a KKT
point (-x; -) which satisfies the strict complementarity condition. If this condition is
violated, then only the inclusion
I \Phi (x; -) ' I 0 (2)
IDENTIFICATION OF ACTIVE CONSTRAINTS 5
holds. Furthermore, if   is a singleton, then we also have, in a sufficiently small
neighborhood of (-x; -
-),
I
This relation was exploited to construct locally superlinearly convergent QP-free
optimization algorithms when the unique multiplier - does not satisfy the strict
complementarity condition, see, e.g., [12, 20, 35].
We refer the reader to [2, 12] and references therein for a more complete discussion
of these kind of results. An analysis of results established in the literature
shows that this conclusion holds in general: if strict complementarity is satisfied, it
is usually possible to correctly identify the active constraint set, otherwise a relation
like (3) is the best result that has been established in the general nonlinear case.
To overcome this situation we propose to compare g i (x) to a quantity which goes
to 0 at a known rate if (x; -) converges to a point in the KKT set K. To this end,
we introduce the notion of identification function.
called identification function for
(a) ae is continuous on K,
(b) (-x; -) 2 K implies ae(-x; -
(c) if (-x; -
-) belongs to K, then
lim
ae(x; -)
dist [(x; -); K]
In the next section we shall give examples of how to build, under appropriate as-
sumptions, identification functions. Basically, Definition 2.1 says that a function is
an identification function if it goes to 0 when approaching the set K at a "slower"
rate than the distance from the set K. We note that dist [(x; -); K] ? 0 whenever
since K is a closed set; hence the denominator in (4) is always nonzero.
Using Definition 2.1 it is easy to prove that the index set
correctly identifies all active constraints if (x; -) is sufficiently close to the KKT set
K.
Theorem 2.2 Let ae be an identification function for K. Then, for any - 2  , an
exists such that
6 F. FACCHINEI, A. FISCHER AND C. KANZOW
Proof. Since g is continuously differentiable, g is locally Lipschitz-continuous.
Hence there exists a constant c ? 0 such that, for all x sufficiently close to -
Suppose now that g i using (4) and (7), we obviously have, for
in a sufficiently small neighborhood of (-x; -),
dist [(x; -); K] - ae(x; -);
so that, by (5), i 2 A(x; -).
If, instead, (x; -) 2 K, then we have
x by the local uniqueness of -
x. From
the definition of an identification function, we also have ae(x; so that
and also in this case i 2 A(x; -).
On the other hand, if by continuity, that i 62 A(x; -) if (x; -)
is sufficiently close to (-x; -
-). Therefore, for any - 2  , we can find
such that (6) is satisfied. 2
From the previous theorem it is obvious that there exists an open set containing
K where the identification of the active constraints is correct. Using the MFCQ
condition we can obtain a somewhat stronger result.
Theorem 2.3 Let ae be an identification function for K. If the MFCQ condition
holds, then there is an ffl ? 0 such that
Proof. By the previous Theorem, for every (-x; -) 2 K, there exists a neighborhood
-) such that A(x; -)). The
collection of open
obviously forms an open cover of K. Since the
set K is compact in view of the MFCQ condition, we can extract from the infinite
cover
- such that (-x; -) 2 K a finite subcover \Omega\Gamma ffl( -
s: Then it is easy to see that the Theorem holds with ffl := min j=1;:::;s fffl( -
the SMFCQ holds, it is even possible to identify the set of strongly active constraints
at -
x, i.e., the set of constraints whose multipliers are positive. To this end,
let be defined by
The following theorem holds.
IDENTIFICATION OF ACTIVE CONSTRAINTS 7
Theorem 2.4 Let ae be an identification function for K. If the SMFCQ holds at - x,
then there is an ffl ? 0 such that
Proof. We first recall that the SMFCQ implies that   reduces to a singleton,
i.e.,  -g. Theorem 2.2 shows that A+ (x; -) ' I 0 for all (x; -) in a certain
neighborhood of (-x; -). Now, consider an index . By continuity, this implies
in a sufficiently small neighborhood of (-x; -). On the other hand, let
in a sufficiently small neighborhood of
-), we have
dist [(x; -); K] - ae(x; -)=2 ! ae(x; -):
This means i 62 sufficiently close to
Until now we made reference to the Karush-Kuhn-Tucker system (1) which expresses
first order necessary optimality conditions for the minimization Problem (P). We
showed how the active constraints associated to an isolated stationary point -
x can be
identified. However, the fact that the Karush-Kuhn-Tucker system (1) derives from
an optimization problem plays no role in the theory developed. What we actually
proved is the following: Given a solution (-x; -
-) of a system with the structure of
system (1) and with an isolated x-part, we can identify, in a suitable neighborhood
of this solution, those inequalities which hold as equalities at the solution (-x; -).
Therefore, if we consider the KKT system
continuous function, the theory of this section goes
through without any change. This is an important observation, since it allows us to
extend the theory developed so far to the identification of active constraints for the
variational inequality problem:
Find - x 2 X such that F (-x) T
is continuous and
is continuously differentiable. It is well known that, under a standard regularity
assumption [17], a necessary condition for -
to be a solution of the variational
inequality problem is that - 2 IR m exists such that (-x; -) solves system (8). There-
fore, if we have a sequence f(x converging to a solution of system (8) which
has an isolated primal part, we can apply the techniques described in this section
in order to identify which of the constraints g i (x) - 0 will be active at -
8 F. FACCHINEI, A. FISCHER AND C. KANZOW
3 Defining Identification Functions
From what exposed in the previous section we see that the crucial point in the
identification of active constraints is the definition of an identification function. In
this section we show how it is possible to define such a function for Problem (P):
We consider three cases. In the first one we assume that the functions f and g
are analytic, in the second case we require them to be LC 1 , but then we also need
that the MFCQ condition and a second order sufficient condition for optimality are
satisfied. Finally, in the third case, the functions are required to be C 2 and the
KKT point is assumed to satisfy a regularity condition related to (but weaker than)
Robinson's strong regularity [33] and which we call quasi-regularity. Extensions of
these results to the KKT system (8) are possible. We shall point out the relevant
changes in corresponding remarks.
The cases considered here do not cover all the situations in which an identification
function can be defined and computed, but they certainly show that the definition
and computation of an identification function is possible in most of the cases of
interest.
3.1 The Analytic Case
Let f and each g i (i 2 I) be analytic around a point x. We recall that this means
that f and each g i (i 2 I) possess derivatives of all orders and that they agree with
their Taylor expansions around x. We say that f and each g i (i 2 I) are analytic
on an open set X ' IR n if they are analytic around each x 2 X: We shall make use
of the following result due to Lojasiewicz, Luo and Pang [25, 27].
Theorem 3.1 Let S denote the set of points in IR r satisfying
are analytic functions defined on an open set
Suppose that S 6= ;. Then, for each compact
ae X, there exist
Using this result, it is possible to define an identification function for Problem (P):
Theorem 3.2 Suppose that f and g are analytic in a neighborhood of a stationary
point - x. Then, the function ae defined by
log(r(x;-))
if r(x; -) 2 (0; 0:9);
IDENTIFICATION OF ACTIVE CONSTRAINTS 9
where
is an identification function for K.
Proof. It is obvious, by definition, that ae 1 is a nonnegative function such that
lim
so that ae 1 is also continuous on K. Hence we only have to check the limit
lim
dist [(x; -); K]
To this end we recall that, for arbitrary - ? 0 and fl ? 0, the limit
lim
holds, see, e.g., [28, p. 328]. We can now apply Theorem 3.1 by considering the
system (1) which defines KKT points. It is then easy to see that (9) yields, for
every given compact
containing (-x; -) in its interior,
where - and fl are fixed positive constants. Therefore we can write
lim
dist [(x; -); K]
from which (11) follows taking into account (12), recalling the definition of ae 1 and
noting that r(x; -) is a continuous function that goes to 0 from the right as (x; -)
tends to (-x; -). 2
We stress that Theorem 3.2 holds under the mere assumption that f and g are
analytic.
Remark 3.3 If we want to define an identification function for the solutions of the
KKT system (8), we only have to substitute the definition of the residual (10) by
the following one:
Obviously, also in this case, we have to assume that F and each g i (i 2 I) are
analytic in a neighborhood of the KKT point under consideration.
F. FACCHINEI, A. FISCHER AND C. KANZOW
3.2 The Second Order Condition Case
In this subsection we assume that f and g are LC 1 , i.e., that they are differentiable
with Lipschitz-continuous derivatives. We denote the Lagrangian of problem (P) by
and write r x L(x; -) for the gradient of L with respect to the x-variables. We
further assume that the MFCQ holds along with the following second order sufficient
condition for optimality:
Assumption 3.4 There is
Here, W ( -) denotes the cone
and @ x r x L(-x; -
-) denotes Clarke's [8] generalized Jacobian with respect to x of the
gradient r x L, calculated at (-x; -
-).
We remark that, if the functions f and g are twice continuously differentiable and
only one multiplier exists, then the previous definition reduces to the classical KKT
second-order sufficient condition for optimality.
We shall show that these two conditions allow us to define an identification
function for K which, because the MFCQ holds, is a compact set. To this end
consider the perturbed nonlinear program
denotes the perturbation parameter. In what follows
we will assign to any vector (y; -) 2 IR n \Theta IR m a particular perturbation vector
For this purpose we first define the function
componentwise by
where, we recall, I \Phi (y; g. We can now introduce the function
\Gammag i (y) if i 2 I \Phi (y; -);
Although, in general, the functions - \Phi and - are not everywhere continuous, the
following properties can be proved.
IDENTIFICATION OF ACTIVE CONSTRAINTS 11
Lemma 3.5 (a) If - 2  , then - \Phi (-x; -.
(b) The function - \Phi is continuous on K.
(c) If - 2  , then -x;
(d) The function - is continuous on K.
Proof. (a) Since (-x; -) is a KKT point, it readily follows that I \Phi (-x;
the definition of the function - \Phi yields - \Phi (-x; - for all - 2  .
(b) Let (-x; -
-) belong to K. According to assertion (a), in order to show continuity
of - \Phi in (-x; -
-), we have to show that, for every i 2 I,
lim
If -
easily follows from the definition of - \Phi
sufficiently large, continuity. Using the
definition of - \Phi
again, we have - \Phi
i for all k large enough. Thus, (14)
follows also in this case.
(c) Taking into account assertion (a), the KKT conditions (1) for problem (P)
yield
On the other hand, analogously to point (a), we have I \Phi (-x;
readily follows from the definition of - g .
(d) The continuity of the function - f on K follows by its definition and assertion
(b). In order to prove the continuity of - g on K; let (-x; -
be given and let
be any sequence converging to (-x; -
-). In view of part (c), we have to show
that
lim
To this end, first consider an index i 2 I Hence
(15) follows from the definition of - On the other hand, if
sufficiently large. Hence - g (y k
all these indices, i.e., (15) holds also for i 62 I
Using the particular perturbation vector -), we can prove the following
result.
Lemma 3.6 Let (y; -) 2 IR n \Theta IR m be arbitrarily chosen. Then, (y; - \Phi (y; -)) is a
KKT point for problem (P(t)); where
Proof. The KKT system for the perturbed program (P(t)) reads as follows:
12 F. FACCHINEI, A. FISCHER AND C. KANZOW
Let (y; -) be arbitrary but fixed. Obviously, since we find that (x; -) :=
solves (16) and (17). Now, we will show that (y; - \Phi (y; -)) also satisfies
(18) and (19). For i 2 I \Phi (y; -) the definition of - g (y; -) yields (g(y)
that both (18) and (19) are fulfilled. If, instead, i 2 I n I \Phi (y; -), it follows from
the definition of - \Phi (y; -) that - \Phi
and (19) is satisfied. Moreover, the
definition of - g (y; -) implies
Thus, (18) is also valid for i 2 I n I \Phi (y; -). We therefore conclude that (y; - \Phi (y; -))
is a KKT point of (P(t)) when
The next result can easily be derived from Theorem 4.5 b) and formula (3.2 f) in
Klatte [18]. If the functions f and g of the program (P) are twice continuously
differentiable it can also be obtained from a corresponding result in Robinson [34,
Corollary 4.3]. We further note that Assumption 3:4 can be weakened by using
generalized directional derivatives, see [18] for more details and references.
Theorem 3.7 Let the MFCQ and Assumption 3.4 be satisfied. Then, there are
for every t 2 B ffi and for every KKT point (-x(t); -
-(t)) of problem (P(t)) for which
Putting together the last two results, we can easily prove the following theorem.
Theorem 3.8 Let the MFCQ and Assumption 3.4 be satisfied. Then, there are
Proof. By Lemma 3.5 (c), we have -x;
Lemma 3.5 (d) and by the compactness of K, we have that, for ffi from Theorem 3.7,
we can find an " ? 0 such that, if Therefore,
since ffl - j (with j from Theorem 3.7) can be assumed without loss of generality,
Theorem 3.7 together with Lemma 3.6 yields the desired result. 2
We are now in the position to show that the function ae defined
by
can be used as an identification function.
Theorem 3.9 Let the MFCQ and Assumption 3.4 be satisfied. Then ae 2 is an identification
function for K.
IDENTIFICATION OF ACTIVE CONSTRAINTS 13
Proof. By Lemma 3.5 we easily obtain that ae 2 is continuous on K and that
any sequence with
lim
Using Theorem 3.8 we get, for k sufficiently large,
Let z 1 2 K and z 2 2 K be the projections of
tively, on the closed convex set K. Then, using the triangle inequality, we get
Combining relations (21) and (22), we obtain, for k sufficiently large,
ae 2 is continuous on the compact set K and since its value is 0 on K it follows
from (20), (21) and Lemma 3.5 (b) that the quantity dist[(x
goes to 0 for k ! 1. But then the right hand side of (23), and thus
also the left hand side, tends to infinity. Therefore, we have shown that ae 2 possesses
all properties of an identification function. 2
If, instead of the upper Lipschitz-continuity as stated in Theorem 3.7, the multi-function
t 7! K(t) is upper H-older-continuous at with a known rate - 2 (0; 1],
that is, if, for some
dist [(-x(t); -(t)); K] - cktk -
for every t 2 B ffi and for every KKT point (-x(t); -
-(t)) of Problem (P(t)) for which
then the technique presented in this subsection can easily be
extended if we define ae
In particular, Theorems 3.8 and 3.9 remain valid for this ae 2 if Assumption 3.4 is
replaced by the upper H-older-continuity.
An interesting case in which it is possible to prove, under an assumption weaker
than Assumption 3.4, the upper H-older-continuity at of the multifunction
14 F. FACCHINEI, A. FISCHER AND C. KANZOW
t 7! K(t) is the case of convex problems. Assume that f is convex and each g i (i 2 I)
is concave, that the MFCQ holds and that the following growth condition holds (in
place of Assumption 3.4): positive -
exist such that
Under these assumptions and using the results in [19], it is possible to show (we
omit the details) that ffi ? exist such that
dist [(-x(t); -(t)); K] - c
ktk
for every t 2 B ffi and for every KKT point (-x(t); -(t)) of Problem (P(t)) for which
It may be interesting to note that the growth condition holds, in
particular, if Assumption 3.4 is fulfilled.
Remark 3.10 The extension of the results of this section to general KKT systems
is not straightforward, since the sensitivity analysis of perturbed KKT systems re-
quires, to date, stronger assumptions. The key point is to establish a result analogous
to Theorem 3.7. Once this has been done, we can easily prove theorems analogous
to Theorem 3.9 by substituting F to rf in every relevant formula. As an example
of the kind of the results that can be obtained we cite the following one. Suppose
that F is C 1 and g is C 2 . Assume also that the SMFCQ holds at -
x along with
Assumption 3.4. Then, according to [16, Corollary 8 (c)], Theorem 3.7 holds and
therefore ae 2 is a regular identification function for the KKT system (8).
3.3 The Quasi-Regular Case
In this subsection we assume that the functions f and g are C 2 . We shall introduce a
condition which we call quasi-regularity. As will be clear later, this quasi-regularity
is related to , but weaker than Robinson's strong regularity [33]. In order to motivate
the definition of a quasi-regular KKT point we will first recall a condition which is
equivalent to the notion of a strongly regular KKT point. To this end we shall use
the index set I 00 := I 0 n I + of all those indices for which the strict complementarity
condition does not hold at the KKT point (-x; -). For any J ' I 00 (empty set
included) introduce the matrix
xx L rg+ rg J
\Gammarg T
\Gammarg T
xx L, rg+ and rg J are abbreviations for the matrices r 2
-), rg I+ (-x)
and rg J (-x), respectively. The following result is due to Kojima et al. [21].
Theorem 3.11 The following statements are equivalent:
IDENTIFICATION OF ACTIVE CONSTRAINTS 15
(a) (-x; -) is a strongly regular KKT point.
(b) For any J ' I 00 (empty set included), the determinants of the matrices M(J)
all have the same nonzero sign.
Motivated by point (b) in Theorem 3.11, we introduce the following definition.
Definition 3.12 The KKT point (-x; -
-) is a quasi-regular point if the matrices M(J)
are nonsingular for every J ' I 00 (empty set included).
Note that, in view of Theorem 3.11, quasi-regularity is implied by Robinson's strong
regularity condition, but the converse is not true. In fact, consider the following
example:
It is easy to check that -
is a global minimizer and that the Lagrange
multipliers of the two constraints are both zero, so that I
Therefore (-x; 0; 0) is a quasi-regular KKT point, but not a strongly regular one. Note
that in this example the KKT point is an isolated KKT point. This is not a chance.
In fact we shall show in this section that quasi-regularity of a KKT point implies
its local uniqueness. It is also worth pointing out that quasi-regularity implies the
linear independence of the active constraints. This easily follows from the fact that
Now let us introduce the operator
r x L(x; -)
Note that the KKT conditions are equivalent to the nonlinear system of equations
By the differentiability assumption we have that \Phi is locally Lipschitzian. Hence,
by Rademacher's Theorem, \Phi is differentiable almost everywhere. Denote by D \Phi
the set of points where \Phi is differentiable. Then we can define the B-subdifferential
(see, e.g., [31]) of \Phi at (x; -) as
F. FACCHINEI, A. FISCHER AND C. KANZOW
Note that the B-subdifferential is a subset of Clarke's generalized Jacobian [8, 31].
The next lemma illustrates the structure of the B-subdifferential of \Phi: Before stating
this lemma, however, we introduce three index sets:
Lemma 3.13 Let (x; -) 2 IR n+m be arbitrary. Then
xx L(x; -) rg(x)D a (x; -)
where
D a (x; -) := diag (a 1
are diagonal matrices with
a
and D b (x;
Proof. This follows immediately from the definition of the operator \Phi: 2
We are now in the position to prove the following result.
Lemma 3.14 Let (-x; -
n+m be a quasi-regular KKT point. Then all matrices
are nonsingular.
Proof. Let In view of Lemma 3.13, there exists an index set
-) such that
\Gammarg T
\Gammarg T
\Gammarg T
\Gammarg T
denotes the complement of J in the set fi(-x; -): Obviously,
this matrix is nonsingular if and only if the matrixB @
xx L rg ff rg J
\Gammarg T
\Gammarg T
IDENTIFICATION OF ACTIVE CONSTRAINTS 17
is nonsingular. In turn, this matrix is nonsingular if and only if the matrix M(J) is
nonsingular. Hence the thesis follows immediately from Definition 3.12. 2
We are now able to prove the main result of this subsection.
Theorem 3.15 Let (-x; -
n+m be a quasi-regular KKT point of problem (P).
Then,
(a) (-x; -) is an isolated KKT point,
(b) the function ae 3 : defined by
ae 3 (x; -) :=
is an identification function for
-)g:
Proof. Obviously, ae 3 is a continuous and nonnegative function with ae 3 (-x; -
Furthermore, since f and g have locally Lipschitzian gradients and the min operator
is semismooth (see [29, 32] for the definition of semismoothness and [29] for the proof
that the min operator is semismooth) it follows that also \Phi, which is the composite
of semismooth functions, is semismooth [29, 32]. Hence it follows from Lemma 3.14
and [30, Proposition 3] that there exists a constant c ? 0 such that
for all (x; -) in a neighborhood of (-x; -
only if (x; -) is a
KKT point, part (a) follows immediately.
From (24) we also get
ae 3 (x; -)
c
and therefore
lim
ae 3 (x; -)
i.e., ae 3 is an identification function. 2
Remark 3.16 In the case of the KKT system (8) everything goes through. It is
sufficient to assume that F is continuously differentiable and to substitute everywhere
the gradient r x L(x; -) by the function F Also in this case
the definition of quasi-regularity is related to and weaker than that of a strongly
regular KKT point since Theorem 3.11 carries over to the KKT system (8), see
Actually, the case of KKT systems of variational inequalities
is probably the main case in which quasi-regularity can be applied. In fact, it is
F. FACCHINEI, A. FISCHER AND C. KANZOW
not difficult to see that, if strict complementarity holds and -
x is a local minimum
point of Problem (P), quasi-regularity implies the conditions of the previous sub-
section. However, these conditions and quasi-regularity are fairly distinct if one
considers variational inequalities. For example, it can easily be checked that, given
the variational inequality defined by the function F
and the
set 0g, the point (0; is a quasi-regular solution but does not
satisfy the conditions stated in Remark 3.10 of the previous subsection.
4 An Application
In this section we apply the results obtained in the previous sections to a local
active-set Newton algorithm for the solution of Problem (P). The algorithm to be
introduced here is a simple variation of the one presented in [12]. However, using the
new results obtained in this work, we are able to relax the assumptions used in [12].
The result is an algorithm which, by solving only linear systems at each iteration,
guarantees Q-quadratic convergence of the sequence fx k g to the solution under very
mild assumptions and without requiring strict complementarity. We remark that,
as far as we are aware of, there exist only two other algorithms which ensure Q-
quadratic convergence of the primal variables. The first one is due to Bonnans [3]
and requires, at each iteration, the solution of a quadratic and possibly nonconvex
subproblem. Furthermore the algorithm of Bonnans also requires the selection of a
suitable solution of the quadratic subproblem, which appears to be a difficult task in
practice. The other algorithm that guarantees Q-quadratic convergence is the one
discussed in [12] which, as already said, requires stronger assumptions. We refer the
interested reader to [12] for a more detailed discussion of these issues.
Consider problem (P) and assume that f and g are twice continuously differen-
tiable. The algorithm we consider generates a sequence fx k g as
with d k being obtained by solving the linear system
z k
In the previous system,
where N(x) is the m \Theta m matrix defined by:
diag
i2I
while
IDENTIFICATION OF ACTIVE CONSTRAINTS 19
We shall assume that the LICQ holds at - x, along with the following weak second
order assumption.
Assumption 4.1 It holds that
We note that Assumption 4.1 is extremely weak if compared to second order assumptions
usually used in the local analysis of algorithms for the solution of inequality
constrained optimization problems. In particular, even if coupled with the linear
independence assumption, it does not even imply that - x is an isolated local solution
of problem (P). This can be checked on the following example, where a is a
nonnegative constant:
t. x 2 - 0:
It is easy to see that -
is a stationary point satisfying both the LICQ
assumption and Assumption 4.1. However, if a ? 0, -
x is not a local solution, while,
if we have that -
x is indeed a local solution but not isolated.
We recall a result which illustrates the properties of the multiplier function defined
by (27).
Theorem 4.2 (see [26]) Let -
x be a KKT point where the linear independence of the
active constraints holds. Then,
- and there exists ffl 1 ? 0 such that, for all
(a) -(x) is well defined;
(b) -(x) is continuously differentiable.
We now pass to the proof that the algorithm (25)-(26) is Q-quadratically convergent
in the primal variables. To this end we first need a simple Lemma.
Lemma 4.3 Let (-x; -
-) be a KKT pair for Problem (P) which satisfies the LICQ and
Assumption 4.1. Then there exist
the matrix
xx L(x; -(x)) \Gammarg I 0
rg I 0
is nonsingular and kM(x)
Proof. Assumption 4.1 and well known properties of quadratic forms (see, e.g., [1,
p. 78]) imply that there exists a constant oe ? 0 such that the matrix
(-x)rg I 0
F. FACCHINEI, A. FISCHER AND C. KANZOW
is positive definite. Then, by continuity, the matrix
is positive definite for all x 2 f-xg +B ffl 2
sufficiently small. This implies
(see, e.g., [1, p. 78]) that, for all x 2 f-xg +B ffl 2
Therefore (29) and the linear independence assumption imply that ffl 2 ? 0 can be
chosen as small as necessary so that, for all x 2 f-xg +B ffl 2
and
rg I 0
using (30) and (31), it is easy to show that the matrix M(x) is nonsingular for
. Hence, the remaining result follows by the continuity of M(x). 2
Theorem 4.4 Let f and g i (i 2 I) be twice continuously differentiable with locally
Lipschitz-continuous Hessian matrices r 2 f and r 2 g i (i 2 I). Let (-x; -
-) be an
isolated KKT pair for Problem (P) which satisfies the LICQ and Assumption 4.1,
and suppose that an identification function ae for known. Then there
exists
the system (26) is nonsingular and the
sequence fx k g produced by (25) satisfies converges to - x, and
the rate of convergence is Q-quadratic.
Proof. For us consider the linear system
with
I 0
is arbitrary but fixed. Recalling that r x L(-x;
I 0
0: (33)
Taking into account (33) and the differentiability assumptions on f and each g i
(i 2 I), it is possible to show (see [12] for the details), by repeated use of Taylor's
formula, that positive numbers ffl 3 , C 1 , and C 2 exist such that, for all x 2 f-xg +B ffl 3
IDENTIFICATION OF ACTIVE CONSTRAINTS 21
By Lemma 4.3, (32) and (33), we have, for all x 2 f-xg +B ffl 3
Moreover, if ffl 3 ? 0 is small enough, it follows from Theorem 4.2 that C 3 ? 0 exists
such that, for all x 2 f-xg +B ffl 3
Assume now that
and suppose that ffl 3 2 (0; 1) is chosen small enough so that, according to Theorem
2.2,
Therefore, setting
the linear systems (26) and (32) are equivalent as long as x k
. By
(34)-(36), we also have, if x k 2 f-xg +B ffl 3
xk:
From these relations, all the assertions of the theorem easily follow by induction. 2
We stress that the example in Section 3.3 satisfies the assumptions of the previous
theorem, but not those of the corresponding Theorem 4.1 in [12].
Final Remarks
In this paper we introduced a technique to accurately identify active constraints in
inequality constrained optimization and variational inequality problems. The most
remarkable feature of the new identification technique is that it identifies all active
constraints even if strict complementarity does not hold. Furthermore, as discussed
in the introduction, it also enjoys several other favorable characteristics. In particu-
lar, the identification technique can be used in combination with any algorithm for
the solution of inequality constrained optimization or variational inequality prob-
lems. In Section 4 we gave an example of an application of the results of this paper
to an active set Newton-type method; however, we believe that the techniques introduced
in this paper can be useful in many other cases, especially in the theoretical
analysis and in the design of optimization methods.
From a practical point of view, the following questions may also be of interest:
22 F. FACCHINEI, A. FISCHER AND C. KANZOW
(a) How large is the region where exact identification occurs?
(b) Can we build identification functions which are scale invariant?
(c) Can we relax the assumption that -
x is an isolated stationary point and still
obtain useful results?
It is difficult to answer to these questions at the level of generality adopted in this
paper. We think that an answer can come from practical experiments and from an
analysis of structured classes of problems, e.g., linear or quadratic problems, box or
linearly constrained problems etc.

Acknowledgment

. We would like to thank Professor D. Klatte for helpful discussions
on the stability of KKT-systems.



--R

Introduction to Matrix Analysis.
Constrained Optimization and Lagrange Multiplier Meth- ods
Rates of convergence of Newton type methods for variational inequalities and nonlinear programming.
On the identification of active constraints II: The nonconvex case.



Optimization and Nonsmooth Analysis.
Global convergence for a class of trust region algorithms for optimization problems with simple bounds.
A study of indicators for identifying zero variables in interior-point methods
"La Sapienza"
Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems.
Practical Methods of Optimization.
A necessary and sufficient regularity condition to have bounded multipliers in nonconvex programming.
Practical Optimization.
Stability analysis of variational inequalities and nonlinear complementarity problems

Nonlinear optimization problems under data perturbations.
On quantitative stability for C 1

Strongly stable stationary solutions in nonlinear programs.
On uniqueness of Kuhn Tucker multipliers in nonlinear pro- gramming
Convergence of trust region algorithms for optimization with bounds when strict complementarity does not hold.
Strong stability in variational inequalities.
Sur la probl'em de la division.
New results on a continuously differentiable exact penalty function.
bounds for analytic systems and their applications.
Calculus I.
Semismooth and semiconvex functions in constrained optimiza- tion
Nonsmooth equations: motivation and algorithms.
Convergence analysis of some algorithms for solving nonsmooth equa- tions
A nonsmooth version of Newton's method.
Strongly regular generalized equations.
Generalized equations and their solution

surfaces in constrained optimization.
--TR

--CTR
Wang , Lifeng Chen , Guoping He, Sequential systems of linear equations method for general constrained optimization without strict complementarity, Journal of Computational and Applied Mathematics, v.182 n.2, p.447-471, 15 October 2005
Lus N. Vicente , Stephen J. Wright, Local Convergence of a Primal-Dual Method for Degenerate Nonlinear Programming, Computational Optimization and Applications, v.22 n.3, p.311-328, September 2002
Huang , Defeng Sun , Gongyun Zhao, A Smoothing Newton-Type Algorithm of Stronger Convergence for the Quadratically Constrained Convex Quadratic Programming, Computational Optimization and Applications, v.35 n.2, p.199-237, October   2006
A. N. Daryina , A. F. Izmailov, On the Newton-type method with admissible trajectories for mixed complementatiry problems, Automation and Remote Control, v.68 n.2, p.351-360, February  2007
Christian Kanzow , Andreas Klug, On Affine-Scaling Interior-Point Newton Methods for Nonlinear Minimization with Bound Constraints, Computational Optimization and Applications, v.35 n.2, p.177-197, October   2006
N. H. Xiu , J. Z. Zhang, Local convergence analysis of projection-type algorithms: unified approach, Journal of Optimization Theory and Applications, v.115 n.1, p.211-230, October 2002
Andreas Fischer , Houyuan Jiang, Merit Functions for Complementarity and Related Problems: A Survey, Computational Optimization and Applications, v.17 n.2-3, p.159-182, December 2000
Naihua Xiu , Jianzhong Zhang, Some recent advances in projection-type methods for variational inequalities, Journal of Computational and Applied Mathematics, v.152 n.1-2, p.559-585, 1 March
active constraints;constrained optimization;degeneracy;variational inequalities;identification of active constraints