Degenerate Nonlinear Programming with a Quadratic Growth Condition.
We show that the quadratic growth condition and the Mangasarian--Fromovitz constraint qualification (MFCQ) imply that local minima of nonlinear programs are isolated stationary points. As a result, when started sufficiently close to such points, an $L_\infty$ exact penalty sequential quadratic programming algorithm will induce at least R-linear convergence of the iterates to such a local minimum. We construct an example of a degenerate nonlinear program with a unique local minimum satisfying the quadratic growth and the MFCQ but for which no positive semidefinite augmented Lagrangian exists. We present numerical results obtained using several nonlinear programming packages on this example and discuss its implications for some algorithms.
Introduction
Recently, there has been renewed interest in analyzing and modifying sequential
quadratic programming (SQP) algorithms for constrained nonlinear optimization
for cases where the traditional regularity conditions do not hold [14,13,
20,25]. This research has been motivated by the fact that large-scale nonlinear
programming problems tend to be almost degenerate (have large condition
numbers for the Jacobian of the active constraints). It is therefore important
to establish to what extent the convergence properties of the SQP methods are
dependent on the ill-conditioning of the constraints. In this work, we term as
degenerate those nonlinear programs (NLPs) for which the gradients of the active
constraints are linearly dependent. In this case there may be several feasible
Lagrange multipliers.
Many of the previous analysis and rate of convergence results for degenerate
NLP are based on the validity of second-order conditions. These are essentially
equivalent to the condition in unconstrained optimization that, for a critical
point of a function f(x) to be a local minimum, f xx  0 is a necessary condition
and f xx  0 is a sufficient condition. Here  is the positive semidefinite ordering.
The place of f xx in constrained optimization is taken for these conditions by L xx ,
the Hessian of the Lagrangian, which is now required to be positive definite on
the critical cone for one or all of the Lagrange multipliers [6,21].
Department of Mathematics, University of Pittsburgh
This work was completed while the author was the Wilkinson Fellow at the Mathematics
and Computer Science Division, Argonne National Laboratory, 9700 South Cass Avenue,
Argonne, IL 60439. This work was supported by the Mathematical, Information, and Computational
Sciences Division subprogram of the Office of Advanced Scientific Computing, U.S.
Department of Energy, under Contract W-31-109-Eng-38.
This work differs from previous approaches in that we assume only that
1. At a local solution x   of the constrained nonlinear program, the first-order
Mangasarian-Fromowitz constraint qualification holds.
2. The quadratic growth condition (QG) [4,16] is satisfied:
for some oe ? 0 and all x feasible in a neighborhood of x   .
3. The data of the problem are twice continuously differentiable.
These assumptions are equivalent to a weaker form of the second-order sufficient
conditions [15,4] which do not require the positive semidefinitenes of the Hessian
of the Lagrangian on the entire critical cone.
We prove that these conditions guarantee that x   is the only local stationary
point (3) of the nonlinear program. This is an important issue because it guarantees
that descent-like algorithms will not stop arbitrarily close to x   , except
at x   . This extends a result from [21] that required some second-order sufficient
conditions to be satisfied for all multipliers. In particular, our work implies that
if MFCQ holds and the second-order sufficient conditions hold for one multiplier,
then x   is a strict local minimum and an isolated stationary point.
We also show that, under the same assumptions, the L1 exact penalty sequential
quadratic program (SQP) induces at least Q linear convergence [19] of
the penalized objective to f(x   ) and R-linear convergence of the iterates. Finally,
we provide an example of a nonlinear program that satisfies our assumptions for
which it is not possible to construct an augmented Lagrangian such that x   will
be an unconstrained local minimum. This may present an adverse case to algorithms
based on this assumption, such as Lagrange multiplier methods. However,
we show that it is possible to construct a nondifferentiable function that has x
as its minimum, namely the L1 penalty function (which can also be inferred
from the results in [4]). We describe our computational experience with several
nonlinear programming packages applied to this example and discuss the
expected and observed behavior of Lagrangian multiplier methods.
Our convergence analysis for the L1 exact penalty function suggests that it is
possible to construct a convergence theory with much more general second-order
conditions. This may result in algorithms with superior robustness, because their
properties depend on significantly fewer assumptions.
1.1. Previous Work, Framework, and Notations
We deal with the NLP problem
f(x) subject to g(x)  0; (2)
are twice continuously differentiable.
We call x a stationary point if the following conditions hold for some  2 IR
Degenerate Nonlinear Programming with a Quadratic Growth Condition 3
Here L is the Lagrangian function
If certain regularity conditions hold (discussed below), then a local solution
x   of (2) is a stationary point. In that case (3) are referred to as the KKT
(Karush-Kuhn-Tucker) conditions.
Since our analysis will be limited to a neighborhood of a point x   that is a
strict minimum, we will assume that all constraints are active at x   , or g(x
Such a situation can be obtained by simply dropping the constraints i for
which 0, since this relationship holds in an entire neighborhood of x   .
This does not reduce the generality of our results, but it simplifies the notation
because now we do not have to refer separately to the active set.
The regularity condition, or constraint qualification, ensures that a linear approximation
of the feasible set in the neighborhood of x   captures the geometry
of the feasible set. Often in local convergence analysis of constrained optimization
algorithms, it is assumed that the constraint gradients rg i
are linearly independent, so that the Lagrange multiplier in (3) is unique. We
assume instead the Mangasarian-Fromowitz constraint qualification (MFCQ):
n . (5)
It is well known [9] that MFCQ is equivalent to boundedness of the set M(x   )
of Lagrange multipliers that satisfy (3), that is,
Note that M(x   ) is certainly polyhedral in any case.
The critical cone at x   is [6,22]
We briefly review the some of the second-order conditions in the literature,
although they are not an assumption for our analysis but only a basis for com-
parison. In the framework of [6], the second-order sufficient conditions for x   to
be an isolated local solution of (2) are:
9   2 M(x
If these conditions hold at x   for some    , then the quadratic growth condition
is satisfied, irrespective of the validity of the first-order constraint qualification
[6,7]. However, this does not imply that x   is an isolated stationary point, as
shown by a simple example [21], which may prevent an optimization algorithm
that uses only first derivative information from reaching x   even when started
arbitrarily close to x   .
In [21] it is shown that if MFCQ holds, and the relation (8) is satisfied for
all    2 M(x   ) then x   is an isolated stationary point and a minimum of (2).
Also, with these conditions, the exact solution is Lipschitz stable with respect
to perturbations. By compactness of M(x   ), we can choose oe independently of
in this case. In [1] it is proven that, under these assumptions, the L1 exact
penalty SQP will converge Q-linearly to f(x   ), when the descent direction is
computed by a QP using only first-order information.
A refinement of the second-order conditions was introduced in [15]. In the
presence of MFCQ, those conditions require that
Further analysis shows that, in presence of MFCQ, these conditions are necessary
and sufficient for the quadratic growth condition to hold [4,15,16,22]. Also, the
exact solution is Lipschitz stable with respect to certain classes of perturbations
[22], though not to any perturbation (see an example in [10, p.308]). In this
paper we assume only the quadratic growth condition and MFCQ, and thus we
do not use the perturbation results.
If the condition (9) holds, but (8) does not, then there is no positive semidefinite
augmented Lagrangian, as we will show with an example. This is an interesting
aspect since it invalidates the usual working assumption of Lagrange
multiplier methods [3].
Finally, we review some of the facts concerning the L1 nondifferentiable
exact penalty function:
We are looking for an unconstrained minimum of the function
where c OE is a sufficiently large constant. Descent directions d of OE(x) at the point
x can be obtained by solving the following quadratic program (QP) [3]:
subject to g j (x)
where H is some positive definite matrix and g 0 In this paper the analysis
will be restricted to the case although the same results apply for any
other positive definite matrix.
At the current point x k of an iterative procedure that attempts to determine
x   , the QP (11) generates the descent direction d k . The next iterate is x
obtained by a line search procedure. Usual stepsize rules
are the minimization rule, the limited minimization rule, and the Armijo rule
[3]. For these rules, any limit point of fx k g is a stationary point of OE(x), and the
descent procedure is therefore globally convergent in this sense [3].
If, in addition,
Degenerate Nonlinear Programming with a Quadratic Growth Condition 5
for some    2 M(x   ), then x   is a stationary point of OE(x) [2]. A suitable value
for c OE is not available in the early stages of the algorithm, but a good estimate
can be found via an update scheme [2]. Here we assume that c is constant and
for all    2 M(x   ), where fl is some prescribed safety factor.
Consider the quadratic program
subject to g j (x)
We denote the unique solution of this program by d(x) and the set of its multipliers
by M(x). At x   (14) has the same multiplier set as (2), which are both
denoted by M(x   ). Since MFCQ is satisfied at x   , this QP is feasible in a neighborhood
of x   . The KKT conditions for this QP require
With these notations, d(x   If the QP (14) were unconstrained, then its
solution would be We name a descent-like algorithm a sequential
quadratic program that solves instances of the above QP.
At x   , the QP (14) satisfies MFCQ and some second-order sufficient con-
ditions. From [21] there exists c d such that, in a neighborhood of x   we have
there exists    2 M(x   ) such that
Therefore, from the definition of c OE , there exists a neighborhood of x   such that
for all multipliers  2 M(x). For such x, it can be verified by inspection that
is a solution of (11) [2, p. 195]. We therefore concentrate on the
QP (14), because, if c OE is large enough and we are sufficiently close to x   , it
generates the same descent direction as (11), thus sharing its global convergence
property.
For some function h : IR
k we denote by c 1h , c 2h bounds depending
on the first and second derivatives of h. The positive and negative parts of h(x)
are h
componentwise. With this notation
6 Mihai Anitescu
2. Stationary Points of NLPs Satisfying MFCQ
In this section, we assume that x is in a sufficiently small neighborhood of x   ,
whose size or properties are specified in each of the following results. In particular
the standing assumptions hold on all neighborhoods considered here and
Here p with one of the vectors satisfying (5),
suitable neighborhood of x   .
Lemma 1. There exist
a neighborhood W (x   ) such that
Here P (x) is the usual L1 penalty function (10).
Proof. We have by Taylor's theorem
We choose
For 0  ff  ff P we have
The claim follows after choosing c proof of the following lemma can be inferred from [4]. We include it here
for completeness.
Lemma 2. There exists a c OE such that
for all x in a neighborhood of x   .
Proof. Let r ? 0 be such that B(x   ; r) ae W (x   ). We choose r
2 such that
This is always possible because
We then have that, for any x 2 B(x
and thus x r). By the intermediate value theorem, we have that
implying in turn that rg i
Degenerate Nonlinear Programming with a Quadratic Growth Condition 7
Take now
If x is infeasible, then ff 1 ? 0 and there exists i such that g i
applies to give
If x is feasible, then ff and the previous bound still applies.
From the quadratic growth assumption (1) and the feasibility of x+ ff 1 p, we
must have that
or
By (23) and Taylor's theorem we have
c P
Choose
c P
c P
Then by (23)
c P
c P
c P
c P
Using (25), (24) and (26) we get
The conclusion follows, because
from the Cauchy-Schwartz inequality.
We can assume that c OE from the previous lemma satisfies (17), or otherwise
we replace it with the right-hand side of (17) and the conclusion of the lemma
still holds for the new c OE .
To prove the following results, we will use the results from [12] concerning
sets defined by linear inequalities:
For such a set, denote by d(x; P) the distance from a point x 2 IR
n to the set P.
Also, denote by dP (x) the maximum value of the infeasibility:
Then there exists a number    (P) ? 0 such that
If we have equality constraints, we recast them as two inequality constraints.
The following lemma uses the fact that M(x   ) is polyhedral and can thus be
expressed in the form (27).
Lemma 3. Let I be an index set such that there exists a multiplier
with
lambda there exists a constant c I such that 8 2 M(x   ) there
exists a    2 M(x   ) with
and such that jj \Gamma    jj  c I jj I jj 1 .
For a vector  we have denoted by  I the restriction of the vector to the index
set I.
Proof. Let M I (x   ) be the set of all    2 M(x   ) such that    I = 0. Then
0: (32)
From our assumptions, M I (x   ) is not empty. By eventually rescaling the x space,
we can assume, without loss of generality, that the vectors defining the equality
constraints in (30) are of norm 1; otherwise, if all entries are 0, we remove that
row, and the feasible  set remains unchanged. M I can be described in the
alternative, way:
I  0; (35)
I  0; (36)
0; (37)
where each row is described by a unit vector, which puts the set in the form
(27). Thus from [12] there exists a    (M I ) ? 0 such that
(M I )d(; M I )  dMI (): (38)
However, since  2 M(x   ) is a valid multiplier set, we have that only the constraints
I  0, (35), are violated. Thus . The conclusion follows
from (38) by taking c I
. The proof is complete.
We define
Iaef1;::;mg
c I ; for feasible M I (x
Lemma 4. There exists a neighborhood W of x   such that, 8x 2 W; 2 M(x),
implies that there exists a    2 M(x   ) with    I = 0.
Degenerate Nonlinear Programming with a Quadratic Growth Condition 9
Proof. Assume the contrary. Then there exists a sequence x k ! x   such that
there exists  k 2 M(x) and an index set I for which  I = 0, but    I 6= 0,
there is only a finite set of index sets, we can extract an
infinite subsequence for which the above happens for a fixed set I. By extracting
another subsequence, we can assume that  k is convergent, from (16) and the
fact that M(x   ) is compact.
But then  k !    2 M(x   ) and    I = 0, a contradiction.
From here on we will use extensively that, for h twice continuously differen-
tiable, we have
is a continuous function with / 3h Indeed by
Taylor's theorem we have that there exist continuous functions / 1
3h
and
3h
3h
3h
and
The relation (40) now follows by comparing the last two equations.
Theorem 1. There exists a constant c oe ? 0 such that in a neighborhood of x
we have that
where (d; ) is the solution of the QP (14).
Proof. From (16), there exists a    2 M(x   ) such that jj \Gamma    jj  c d jjx \Gamma x   jj.
Let I be the set of indices i for which  We have jj   I jj
c d jjx \Gamma x   jj. From (39) and Lemmas 3 and 4 there exists a ~  2 M(x   ) with
~
As a result
and  The important consequence of this fact, using the complementarity
relations from (15), is that
\Gamma( ~
Indeed,
all the above equalities are 0.
From Lemma 2 we have that
Here (d; ) is a solution of (15), and ~
We also used
(40). We now employ the identity ab
(42), and Taylor's theorem for rg(x) to get, by continuing from the previous
equation,
We denote
From
sufficiently close to x   . By using 1 , (40),
(43) and (42), we get
(x). Using the above bound in (52), together
with \Gammad T
Degenerate Nonlinear Programming with a Quadratic Growth Condition 11
We can now choose a sufficiently small neighborhood of x   such that /(jjx \Gamma
x   jj)  oeand subtract the last term of the last relation from the lower bound
We take and with this new notation, we
get that
We treat jjx \Gamma x   jj as a variable and, by using the formulas for the quadratic
equation, we get that
oe
By using the arithmetic-quadratic mean inequality, we get that
Choosing
oe c OE g (67)
we prove the claim.
Corollary 1. x   is an isolated stationary point.
Proof. Let x be another stationary point of the NLP in the neighborhood of x
where the above theorem holds. Therefore there exists a  2 M(x) satisfying
(3). Hence solution of (15) and is the unique solution of the
strictly convex QP (14). Since is feasible from (14) and P
(x). Now from the complementarity conditions in (15) we get  T
From the previous theorem we get which proves the claim.
Corollary 2. If the second-order sufficient condition (8) is satisfied for one
multiplier, and if MFCQ holds at x   , then x   is an isolated stationary point.
Proof. Since x   is satisfies the quadratic growth condition (1) under these assumptions
[6,7] and MFCQ holds, Corollary 1 applies.
3. An Example Without a Locally Convex Augmented Lagrangian
Consider the matrix
Take
We then have that u T 1. Since the vector
corresponds to the positive eigenvalue, we have that for any u at an
angle of at most
6 from u 0 , u T Qu  1jjujj 2 . Consider now the rotation matrix
since Q 0 and Q 2 have the same axes of symmetry, but with the eigenvalues
switched. Also, for any u 2 IR 2 , there exists a k such that u T Q k u  1jjujj 2 , since
the wide cones centered at the axis of the positive eigenvalues of Q k now sweep
the entire IR 2 .
Consider now the optimization problem
minz subject to z
By the previous observation, we have that z  1(x 2 +y 2 ) on the feasible set;
thus z  0. Clearly, the only solution of the problem is (0; 0; 0). Since z  z 2, if
4, we have that z  1(x 2 +y 2 +z 2 ), for all x;
Therefore at x  the quadratic growth condition is satisfied for the
above NLP, with constant 1. Obviously, MFCQ holds at (0; 0; 0), and a simple
calculation shows that
a multiplier of (70). In particular,
at least one multiplier has to be positive. Also, at (0; 0; 0), all constraints are
active and their gradients are (0; 0; \Gamma1) for any of them. As a result, the linear
constraints in (8) now become either z  0 or z = 0, with at least one being
Therefore the critical cone at x   is 0g. Also, from
(3), if  2 M(x   ), then
Assume that there is a choice  2 M(x   ) such that L xx , the Hessian of the
Lagrangian, is positive semidefinite on the critical cone:
y
zA  0; 8(x; y; z); such that z = 0: (71)
This is equivalent to X
Since our construction is invariant to rotations with (U T
that the positive semi-definiteness holds for any circular permutation oe of this
multiplier set: X
We denote by A c (4) the set of circular permutations of four elements. Since the
set of positive definite matrices is a convex cone, and
we must have
which is impossible. Therefore L xx cannot be positive semidefinite on the critical
cone for any choice  2 M(x   ). Hence the second-order conditions from [6,21]
will not hold for any choice of the multipliers.
Degenerate Nonlinear Programming with a Quadratic Growth Condition 13
3.1. Augmented Lagrangian Approaches
Here we discuss the expected behavior of augmented Lagrangian techniques when
applied to this example. For these methods, the inequalities of the NLP (2) are
converted into equalities [3,5]. The feasible set can be represented as [5]
The NLP is replaced by a bound-constrained optimization problem. The equality
constraints are incorporated in the objective function based on an estimate  of
the multipliers and a penalty term,
subject to t i  0;
Here  is the barrier parameter. The objective function in (76) is the augmented
Lagrangian. The problem is subjected to an additional trust-region constraint
[5] to enforce global convergence.
The desired outcome is to have  bounded away from zero and the trust-region
inactive as  approaches M(x   ) and the solution of the above problem
approaches x   .
If that happens for our example, then, by a continuity argument following
the lower boundedness of , should be a solution of (76) for an
appropriate choice of ; . Since (76) has linearly independent gradients of the
constraints, both the first and second order necessary conditions must hold [7].
The first order necessary condition results in
where , with components  i  0, are the multipliers associated with the variables
As a result  2 M(x   ). The second order necessary conditions require
that
I 4
be positive semidefinite, at least on the subspace of (ffix; ffi t) with
results in
or
We proved that the last matrix cannot be positive semidefinite for our example
and we thus get a contradiction. This shows that, either the trust region
will be active arbitrarily close to x   , or  ! 0.
14 Mihai Anitescu
This also shows that the Hessian of the augmented Lagrangian of the equality
constrained problem
F xx +X
is not positive semidefinite and thus the augmented Lagrangian of the equality
constrained problem cannot be locally convex.
4. Linear Convergence of the SQP with Nondifferentiable Exact
Penalty P (x)
The points x considered in thus subsection are assumed to be sufficiently close
to x   . The notation d and  2 M(x) will refer to the solutions of (14) and (15).
Also, P (x) is the L1 penalty function (10) and
4.1. Proof of the Technical Results
Lemma 5.
Proof. Since d is a feasible point of (14), we have that rg i (x) T d  \Gammag i (x); 8i 2
mg. By Taylor's remainder theorem
Hence
This completes the proof.
Lemma 6. There exist
ff]:
Proof. Writing the KKT conditions for (14), we obtain
and, hence,
(d) T d +rf(x) T d
(d)
Degenerate Nonlinear Programming with a Quadratic Growth Condition 15
since, by the complementarity conditions satisfied by the solution of (14),  T rg(x) T
m. Therefore, since g i
\Gamma(d)
\Gamma(d)
by (10), (17). By Taylor's remainder theorem,
Hence, for ff 2 [0; 1],
ff(\Gamma(d)
from (79) and Lemma 5. Therefore, for ff 2 [0; 1],
The result of the statement follows by choosing
and
Lemma 7. There exists a constant c 5 such that, 8() 2 M(x),
Proof. From (15) and the definition of the Lagrangian (4) it follows, using Tay-
lor's theorem, that, for a sufficiently small neighborhood of x,
g. Also, by (16), we can choose    2 M(x   ) such that
we have that
and, thus
Therefore
The conclusion of the lemma follows by choosing c 1g.
4.2. Nondifferentiable Exact Penalty Algorithms and the Linear Convergence
Theorem
The linearization algorithm [3, p.372] has the following form:
1.
2. Compute d k from (11).
3. Choose ff k from a line search procedure, and set x
4. return to Step 2.
The stepsize ff k is chosen by one of the following procedures [3, p.372].
(a) Minimization rule Here ff k is chosen such that
(b) Limited minimization rule Here a fixed scalar s ? 0 is selected, and ff k is
chosen such that
(c) Armijo rule Here fixed scalars s,  , and oe with s ? 0,  2 (0; 1), and oe 2 (0; 1)
are chosen and we set ff is the first nonnegative integer
m for which
It can be shown that the Armijo rule yields a stepsize after a finite number of
iterations.
The following theorem establishes the convergence properties of the linearization
algorithm. The global convergence properties, established in [2, Prop. 4.3.3],
are also stated here for completeness.
Theorem 2. Let x k be a sequence generated by the linearization algorithm,
where the stepsize ff k is chosen by the minimization rule, limited minimization
rule or the Armijo rule. Then any accumulation point of the sequence x k
is a stationary point of is a strict
local minimum of the problem (2) satisfying the local quadratic growth (1) and
the Mangasarian-Fromowitz constraint qualification (5), then OE(x k
Q-linearly and x k ! x   R-linearly.
Proof. The first part is an immediate consequence of [2, Prop. 4.3.3]. We prove
the linear convergence statement only for the Armijo rule, the proof being similar
for the other stepsize selection mechanisms. By Lemma 6
for all ff 2 [0;  ff]. Since m k is the smallest integer m for which
Degenerate Nonlinear Programming with a Quadratic Growth Condition 17
it follows that  m s
ff. This therefore ensures that the stepsize is at least
ff
for k sufficiently large. As a result of Lemma 6, we have that
On the other hand, by Lemma 7 we have that
By Theorem (1) and the previous relation it follows that there exists c
c6
by using Lemma 6 and where
. After some obvious manipulation, it
follows that
which proves the Q-linear convergence [19] of the sequence OE(x k ) to OE(x   ) with
a linear rate of at most ffi\Gamma1
. Therefore
lim sup
From Lemma 2
Therefore
lim sup
which proves the R-linear convergence [19] to 0 of the sequence x . The
proof is complete.
Following the techniques from [1], we can extend the result for the case where
the matrix H of the QP is not I but changes from iteration to iteration. The
only condition is that the sequence of strictly convex H k be uniformly upper
and lower bounded.
Iteration OE(x k )\GammaOE(x   )
9 4.00

Table

1. Rates of convergence for the L1 penalty algorithm
Iteration (New) Penalty Parameter Trust Region Radius jjjj 1
43 1e-4 1.1 e-02
268 1e-14 1.93
283 1e-16 4.41 e02
336 STOP

Table

2. Reduction of the penalty parameter  for LANCELOT
5. Numerical Experiments with Degenerate NLP
We experimented with several nonlinear programming packages on the example
from Section 3. Certainly, comparing the behavior of NLP algorithms on a
unique degenerate example cannot result in a complete characterization. Nev-
ertheless, it may be of interest to determine whether methods using augmented
Lagrangians will really encounter problems when solving an example without
a positive semidefinite augmented Lagrangian. We also desire to validate the
theoretical conclusions of the preceding sections.
We have shifted the origin for our example, to avoid one step convergence of
algorithms that start at 0; 0; 0 by default. The algebraic form of the example is
minz
From our analysis, we have that w  is a minimum satisfying the
quadratic growth condition (1) with z \Gamma 0
feasible (x; . The feasible set is described in Figure 5. In the lateral
view, the quadratic growth at (1; 1; 0) is fairly obvious from the curvature of the
ridges that appear at the intersection of two constraints. From the shape of the
feasible set it is also clear that (1; 1; 0) is the unique stationary point of the NLP.
Among the solvers we used, MINOS [17] and SNOPT [11] use quasi-Newton
methods that do not require second-order derivatives of the constraints. They
Degenerate Nonlinear Programming with a Quadratic Growth Condition 19
Feasible set: view from above. Center: (1,1,0)
lateral view.
Fig. 1. Feasible set of the nonlinear program (89) (1,1,0) is the local minimum satisfying the
quadratic growth condition (1). The jagged edges in the lateral view are a meshing effect.
also use an augmented Lagrangian as a merit function. DONLP2 [23] solves a
linear system instead of a Quadratic Program at each iteration and uses an L 1
penalty function. LANCELOT [5] uses an augmented Lagrangian technique in
conjunction with a trust-region. FilterSQP [8] also uses a trust region approach
but with a special classification of the relative merits of the iterates instead of
Nonlinear solver jjx final \Gamma x   jj 2
Iterations Message at termination
FilterSQP 5.26e-09 28 Convergence
LANCELOT 8.65e-07 336 Step size too small
LINF 1.05e-08 28 Step size too small
LOQO 1.60e-07 200 Iteration limit
LOQO 5.50e-07 1000 Iteration limit
MINOS 4.76e-06 27 Current point cannot be improved
SNOPT 3.37e-07 3 Optimal Solution Found

Table

3. Runs with various nonlinear solvers on the problem (89)
a penalty or merit function. LOQO [24] is an interior-point approach. Finally,
LINF is an ad hoc Matlab implementation of the L1 exact penalty function
described in the preceding section, with an Armijo rule. The latter algorithm is
started at (0; 0; 0). All runs, except for the L1 penalty and FilterSQP algorithms,
were done on the NEOS server [18], where additional documentation can be
found for all of the above solvers.
For such a small example the time of execution is not relevant in comparing
the behavior of the solvers. Since the solution of the problem is known, we chose
as a criteria for comparison the best achievable solution. We set all relevant
tolerances to 1e \Gamma 16, via the AMPL interface of NEOS. Smaller tolerances may
interfere with the machine precision, though most of the solvers gave comparable
answers even when the tolerances are set to 1e \Gamma 20. Larger tolerances (1e \Gamma 12-
resulted in very similar results. Whenever allowed, we also changed
other limiting parameters until an intrinsic stopping decision was issued. The
only exception was DONLP2 which converged to all digits in the mantissa with
the default settings.

Table

1 shows the ratios OE(x k )\GammaOE(x   )
at various iterations for our implementation
LINF. All are close to 4:00, which is consistent with the Q-linear
convergence claim for OE(x).

Table

2 shows that LANCELOT decreases succesively the value of the penalty
parameter (by 16 orders of magnitude), until it stops with the message 'Step size
too small'. This was indeed one of the alternatives allowed by our analysis in
Subsection 3.1 0). This is an undesirable outcome since the subproblems
may become harder to solve.
The results for all runs are illustrated in Table 3. It can be seen that the
solvers that use augmented Lagrangians MINOS, SNOPT, LANCELOT exhibit
an error of at least one order of magnitude larger compared to all other algo-
rithms. However, one would expect that SNOPT and MINOS would have had
at least as good a behavior as LINF if they would use a different merit function,
since the nature of the QP solved is very similar to (14). Increasing the iteration
limit in LOQO did not result in a better outcome. It is interesting to note that
the outcome in FilterSQP and LINF differ by only a factor of 2 in the same
number of iterations, though FilterSQP uses second-order information whereas
LINF does not. Both LINF and FilterSQP solve quadratic programs at each
Degenerate Nonlinear Programming with a Quadratic Growth Condition 21
iteration. DONLP2 has a remarkable behavior, though further investigation is
necessary to determine whether this has some general implications.
It is impossible to draw a general conclusion from one example. However,
there seems to be an adverse bias for methods using augmented Lagrangians on
degenerate NLPs as the one above. We are not advocating the use of LINF on
general NLP, since its similarity to steepest descent makes it very sensitive to
ill-conditioning. But the fact that it gives an outcome comparable to the one of
solvers using second-order information shows that, for better results, a different
way of incorporating second-order derivatives may be necessary.
6. Conclusions
In this work we analyze the behavior of nonlinear programs in presence of constraint
degeneracy: linear dependence of the gradients of the active constrains.
The problems of interest exhibit minima with a quadratic growth property that
satisfy the Mangasarian-Fromowitz constraint qualification. The novelty of our
approach is that, while studying the SQP convergence properties, we do not
assume the positive semidefiniteness of the Hessian of the Lagrangian on the
critical cone for any of the feasible Lagrange multipliers. Our conditions are
equivalent to a weak second-order sufficient condition [15,22].
We prove that, under these assumptions, if the data of the problem are twice
continuously differentiable, the target minimum will be an isolated stationary
point of the NLP. We also show that, when started sufficiently close to the
minimum, the L1 exact penalty SQPs induce Q-linear convergence of the values
of the penalized objective R-linear convergence of the
iterates. This shows that such methods are robust with respect to constraint
degeneracy.
We give an example of a nonlinear program with a unique minimum that
satisfies our conditions for which the Hessian of the Lagrangian is not positive
semidefinite on the critical cone for any feasible choice of the multipliers. The
direct consequence of this fact is that there is no augmented Lagrangian that
will be positive semidefinite at the solution. Therefore, Lagrange multipliers
algorithms will have to drive the penalty parameter to zero for such examples
unless the trust region is active even at convergence.
We provide our computational experience with this small nonlinear program.
As a criteria for comparison we used the best achievable solution, which was obtained
after tuning the parameters of the algorithms. We observed that, for
this example, algorithms that use augmented Lagrangians resulted in errors of
one order of magnitude or larger when compared to the other approaches. The
Lagrange multiplier package that we used (LANCELOT [5]), was confined to decrease
substantially the value of the penalty parameter (16 orders of magnitude),
which is one of the outcomes allowed by our analysis. The linear convergence
results concerning the L1 penalty function were also validated by our experiments

22 Mihai Anitescu
Undoubtedly, such a small experiment is insufficient to draw any conclusions,
especially about the approaches for which we have no theory under these assump-
tions, such as interior-point algorithms. However, both from our theory and our
experiments, it does appear that methods that use augmented Lagrangians are
less robust with respect to constraint degeneracy when compared to SQP.
We believe that attempting to develop a convergence theory in absence of the
usual second-order conditions is interesting because it may result in algorithms
that are more robust by virtue of the fact that their properties depend on fewer
assumptions. However, how to improve on the current results, and especially
how to define reliable variants of the Newton method (if possible) for this case,
is a subject of future research.

Acknowledgments

Thanks to Stephen Wright, Jorge Mor'e and Danny Ralph for the many discussions
on the subject. David Gay, Sven Leyffer and Chi-Jen Lin have kindly
provided me information and support for the numerical examples.



--R

"On the rate of convergence of sequential quadratic programming with non-differentiable exact penalty function in the presence of constraint degeneracy"
New York

"Second-order sufficiency and quadratic growth for nonisolated minima"
LANCELOT: A Fortran Package for Large-Scale Nonlinear Optimization
Introduction to Sensitivity and Stability Analysis in
Practical Methods of Optimization
"Nonlinear programming without a penalty function"
"A necessary and sufficient regularity condition to have bounded multipliers in nonconvex programming"
"Differential stability in nonlinear programming"
"User's guide for SNOPT 5.3: A Fortran package for large-scale nonlinear programming"
"The relaxation method for solving systems of linear inequalities"
"Stabilized sequential quadratic programming"
"Stability in the presence of degeneracy and error estima- tion"
"Necessary and sufficient conditions for a local minimum.3: Second order conditions and augmented duality"
"On Sensitivity analysis of nonlinear programs in Banach spaces: the approach via composite unconstrained optimization"

The NEOS Guide.
Iterative Solutions of Nonlinear Equations in Several Vari- ables
"Superlinear convergence of an interior-point method despite dependent constraints"
"Generalized equations and their solutions, Part II: Applications to non-linear programming"
"Sensitivity analysis of nonlinear programs and differentiability properties of metric projections"
"An SQP method for general nonlinear programs using only equality constrained subproblems"
"An interior-point code for quadratic programming"
"Superlinear convergence of a stabilized SQP method to a degenerate so- lution"
--TR

--CTR
Jin-Bao Jian, A Superlinearly Convergent Implicit Smooth SQP Algorithm for Mathematical Programs with Nonlinear Complementarity Constraints, Computational Optimization and Applications, v.31 n.3, p.335-361, July      2005
degeneracy;sequential quadratic programming;nonlinear programming;quadratic growth