A Superlinearly Convergent Sequential Quadratically Constrained Quadratic Programming Algorithm for Degenerate Nonlinear Programming.
We present an algorithm that achieves superlinear convergence for nonlinear programs satisfying the Mangasarian--Fromovitz constraint qualification and the quadratic growth condition. This convergence result is obtained despite the potential lack of a locally convex augmented Lagrangian. The algorithm solves a succession of subproblems that have quadratic objectives and quadratic constraints, both possibly nonconvex. By the use of a trust-region constraint we guarantee that any stationary point of the subproblem induces superlinear convergence, which avoids the problem of computing a global minimum. We compare this algorithm with sequential quadratic programming algorithms on several degenerate nonlinear programs.
Introduction
. Recently, there has been renewed interest in analyzing and
modifying the algorithms for constrained nonlinear optimization for cases where the
traditional regularity conditions do not hold [5, 12, 11, 20, 24, 23]. 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 define algorithms that are as little
dependent as possible of 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
[5, 12, 11, 20, 24, 23] are based on the validity of some 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 [7, 21].
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-Fromovitz [18, 17] constraint qualification holds.
2. The quadratic growth condition (QG) [6, 15] 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 [14, 6] which does not require the positive semidefiniteness of the Hessian
of the Lagrangian on the entire critical cone. In a recent a paper [2] it has been shown
Thackeray 301, Department of Mathematics, University of Pittsburgh, Pittsburgh, PA 15213
(anitescu@math.pitt.edu). Part of this work was completed while the author was the Wilkinson
Fellow at the Mathematics and Computer Science Division, Argonne National Laboratory. This
work was supported by the Mathematical, Information, and Computational Sciences Division sub-program
of the Office of Advanced Scientific Computing, U.S. Department of Energy, under Contract
W-31-109-Eng-38. This work was also supported by award DMS-9973071 of the National Science
Foundation.
that these conditions guarantee that x   is an isolated stationary point and that a
steepest-descent like algorithm induces linear convergence to x   . The framework used
here accommodates even problems for which no locally convex augmented Lagrangian
exists [2], which do not satisfy the assumptions of most other convergence results
[5, 12, 11, 20, 24].
In this paper we define an algorithm that is superlinearly convergent even in the
very general conditions outlined above. The trade-off is that the subproblems to be
solved are more complex than a quadratic program. The algorithm can be justified
by a particular perspective on Newton's method for unconstrained optimization. If
f(x) is the function to be minimized without constraints then sufficiently close to a
solution x   Newton's direction, d, is a solution of the quadratic minimization problem.
min
xx f(x)d:
The term f(x) is constant for this minimization problem, but we include it to emphasize
that we can regard d as a solution of the second-order approximation to the
problem. If we have an inequality constrained nonlinear program,
subject to g i
its second-order approximation at x is the following problem
min
xx f(x)d
subject to g(x) +r x
We call such a problem a quadratically constrained quadratic problem (QCQP). To
ensure that the problem is bounded even for x far from the solution x   , we add to
the problem a trust-region constraint, which is also quadratic:
The problem is generally not convex and thus finding the global optimum may be a
difficult problem. Also, the trust-region constraint may interfere with the order of
convergence. However, we show that for x close to x   and for sufficiently small but
fixed:
1. The trust region constraint is inactive at any stationary point of the QCQP.
2. Any stationary point d of the QCQP used as a progress direction induces
superlinear convergence.
Therefore, finding a local solution to the QCQP is sufficient to induce superlinear
convergence of the iterates, which considerably reduces the conceptual complexity of
a sequential QCQP (SQCQP) algorithm. Note that the QCQP subproblem is identical
to the one used in [16], although the analysis conditions in this work are more general.
The paper is structured as follows. In Subsection 1.1 we discuss the different conditions
defining a stationary point of a nonlinear program and the quadratic growth
condition. Section 2 characterizes stationary points of the second-order approximation
(QCQP) of the nonlinear program at x   . We show that, if the trust-region constraint
defines a sufficiently small region then the Mangasarian-Fromovitz constraint qualification
is satisfied at any feasible point and is the unique stationary point of
the QCQP. As a result, in Section 3 we prove that, for x sufficiently close to x   , the
trust-region constraint is inactive at any stationary point of QCQP and we prove the
superlinear convergence of the SQCQP algorithm. We conclude with Section 4, where
we briefly discuss possible approaches to solving the QCQP subproblem.
1.1. Previous Work, Framework, and Notations. We deal with the NLP
problem
f(x) subject to g(x) - 0;
are twice continuously differentiable.
We call x a stationary point if the Fritz John conditions conditions hold: There
exist
Here L is the Lagrangian function
A local solution x   of (1.2) is a stationary point [19]. If certain regularity conditions
hold at x   (discussed below), then there exists - 0 such that x   with -
In that case (1.3) are referred to as the KKT (Karush-
Kuhn-Tucker) conditions [3, 4, 8] and - are referred to as the Lagrange multipliers.
For that case, which is the one that most oftenly appears in this work, we define the
Lagrangian as
and the Karush-Kuhn-Tucker conditions become
r x L(x;
Since our analysis is limited to a neighborhood of a point x   that is a strict local
minimum, we assume that all constraints are active at x   , or g(x   Such a
situation can be obtained by choosing a sufficiently small trust-region and simply
dropping the constraints i for which g i (x   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 algo-
rithms, it is assumed that the constraint gradients r x are linearly
independent, so that the Lagrange multiplier in (1.6) is unique. We assume instead
the Mangasarian-Fromovitz constraint qualification (MFCQ) [18, 17]:
It is well known [9] that MFCQ is equivalent to boundedness of the set M(x   ) of
Lagrange multipliers that satisfy (1.6), that is,
Note that M(x   ) is certainly polyhedral in any case. Another condition equivalent
to MFCQ (1.7) is [10]
such that
The critical cone at x   is [7, 22]
\Phi
We briefly review some of the second-order conditions in the literature. In the
framework of [7], the second-order sufficient conditions for x   to be an isolated local
solution of (1.2) are [7, 8]:
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 [7, 8].
An important consequence of the condition (1.11) is that x   is a local minimum of
the augmented Lagrangian
for a sufficiently large constant c.
A refinement of the second-order conditions was introduced in [14]. 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 [6, 14, 15, 22].
If the condition (1.12) holds, but (1.11) does not, then there may be no augmented
Lagrangian with a positive semidefinite Hessian, as it is shown with an example in
[2]. This is an interesting aspect since it invalidates the usual working assumption
of Lagrange multiplier methods [4]. It also shows that the analysis in this paper is
done without assuming the existence of an augmented Lagrangian that has x   as an
unconstrained minimum.
In our analysis we use the L1 nondifferentiable exact penalty function:
If the MFCQ (1.7) conditions hold at x   , then the quadratic growth condition
(1.1) and the second order conditions (1.12) are each equivalent to the following
condition [6]
for some oe ? 0 and all x in a neighborhood of x   .
For some function h : 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
With this notation Also, in our notation, r x g i (x), - and
r x g(x)- are column vectors.
In this work we need to estimate distances to sets described by linear constraints:
where M eq and M in are n eq \Theta n and, respectively, n in \Theta n matrices and q eq and q in are
respectively, n in dimensional vectors. By Hoffman's Lemma [13], if P 6= ;,
there exists c P ? 0 such that
where by D( ~
d; P) we denoted the distance from ~
d to the set P. This result allows us
to relate the distance from a point ~
d to a polyhedral set in terms of the infeasibility
of ~
d in the representation (1.15).
2. Stationary Points of Quadratically Constrained Quadratic Pro-
grams. In this section we investigate the stationary points of the quadratically constrained
quadratic program
min d2IR n a T d
subject to b T
are n \Theta n
symmetric matrices and a 2 m. We denote this program by
TRQCQP(fl). Our assumptions concerning (2.1) are:
1. At
2. The quadratic growth condition is satisfied near 0: There exists fl 0
and oe 1 ? 0 such that
a
A local solution of (2.1) is clearly
The aim of this section is to show that under assumptions (2.3) and (2.2), there
exists is the only stationary point of TRQCQP(fl) (2.1), for
any 0 - As a consequence any algorithm that reaches a stationary point of
finds its global optimum. The results from [2] ensure that
an isolated stationary point of TRQCQP(fl) (2.1). However, the developments of this
section are necessary to ensure that additional stationary points are not introduced
by the trust region constraint.
The proof has the following steps, each stated for sufficiently small fl.
Lemma 2.4 proves that MFCQ (1.7) is satisfied for all stationary points ~
d
of (2.1). Therefore, at any stationary point there exist Lagrange multipliers
that satisfy (1.6);
ultimately implies that for any Lagrange multiplier - at a stationary
point ~
d of (2.1) there exists a sufficiently close Lagrange multiplier
at active subset is included in the active subset of -. This
leads to the identity (-
~
~
which helps bound above
the variations in the objective function of (2.1) in the proof of Theorem 2.7.
proves that the multiplier of the trust-region constraint is bounded
above. This in turn implies Lemma 2.6: the Lagrange multipliers of all
potential stationary points are uniformly bounded.
ffl Theorem 2.7, the main result of this section, proves that ~
is the unique
stationary point of (2.1).
Subsection 2.1 contains additional results implied by Hoffman's Lemma (1.16),
which are used in Section 3.
2.1. Sensitivity results for Lagrange Multipliers. An immediate consequence
of MFCQ (2.2) is that the set of Lagrange Multipliers of TRQCQP(fl) (2.1) at
is nonempty and bounded.
Lemma 2.1. There exists c M   ? 0 such that, for any w 2 IR
n , and for any - 2 IR
satisfying
a
there exists a -   2 M   such that
Proof Follows by direct application of Hoffman's Lemma (1.16), after using
that jjwjj 1 - jjwjj. \Pi
Lemma 2.2. There exists j ? 0 such that for all w 2 IR n with jjwjj - j and any
satisfying
a
there exists -   2 M   such that -
Proof Assume the contrary: For any k 2 IN , there exists w k 2 IR
n , such that
k and there exists - k satisfying
a
and an index set I k ae f1; mg, such that - k
I
From Lemma 2.1, D(-
is a
compact set, and the set of subsets of f1; is finite, there exists a subsequence
such that I
From our assumptions -   I 6= 0, 8-   2 M   . On the other hand, since - kq
I
I
and - kq ! -   we must have -
I  which is a contradiction. The proof is complete.
Lemma 2.3. There exists c M ? 0 and j ? 0 such that for any w 2 IR
n with
any - satisfying
a
there exists -   2 M   with and such that -
Proof Let j be the quantity defined by Lemma 2.2. Let I ae f1;
that there exists a - satisfying (2.5) and - I = 0. Lemma 2.2 implies that there exists
such that -   I = 0. Let M   I be the set of - 2 IR
m such that
From Lemma 2.2, M   I is not empty. From Hoffman's Lemma (1.16), there exists
c M   I ? 0 such that, for all - 2 IR
m , we have
From Lemma 2.1 choose -   2 M   such that
From the definition of M   (2.4) we have that
Thus, from (2.7) we must have
I
I
We also have from our choice of -   (2.8) that
we thus have
conjunction with the
preceding inequality and (2.9) implies that
Hence from (2.8) and the preceding inequality we have that
The conclusion now follows after taking
I
2.2. Stationary Points of Quadratically Constrained Quadratic Pro-
grams. In this section we analyze the stationary points of TRQCQP(fl) (2.1) for
sufficiently small values of the parameter fl. We choose fl 00
1 such that
are the quantities appearing in MFCQ (2.2) with choose
which guarantees that whenever jjdjj - fl 1 , both (2.10) and the quadratic growth
condition
Lemma 2.4. There exists
(1.7) at all its stationary points d with fl such that
The important consequence of this lemma is that Lagrange multipliers exist at
any stationary point of TRQCQP(fl) (2.1).
Proof Take the quadratically constrained quadratic program
min d2IR n d T d
subject to b T
with global solution as well as the
quadratic growth condition (1.1). From [2], is an isolated stationary point of
(2.12). Therefore there exists a fl 0
such that the only stationary point d of (2.12)
that satisfies d T d - (fl 0
Take now
g. Assume that there exists fl,
MFCQ (1.7) is not satisfied at some stationary point -
d of TRQCQP(fl) (2.1). From
and (1.3) it follows that there exists -
not both equal to 0, such
that
If -
would imply
or, after multiplying with p from (2.10) we get
d)
which implies -
contradiction with the assumption that not both - 0 and -
are
and from (2.13) we get -
dividing with -
(b
(b T
But this means that -
d 6= 0 is a stationary point of (2.12) with a Lagrange multiplier
, which contradicts the properties of our choice of fl 2 . The proof is complete. \Pi
Lemma 2.5. Consider the following quadratically constrained quadratic program
subject to \Gamma i
Then there exists the only stationary
point of (2.15) that satisfies jjdjj - fl 3 is
Proof Choose fl 0
g. From (2.11) this implies that for all d with
3 the quadratic growth condition (2.3) and (2.10) holds. Also, from Lemma
2.4, MFCQ (1.7) holds at any stationary point of (2.15).
Take ~
d 6= 0 a feasible point of (2.15). We now estimate the variation of the
constraints and objective function in a specific direction from ~
d, in order to decide
under what conditions ~
can be a stationary point of (2.15). Let the active set
at ~
d be
We estimate the first-order behavior of \Gamma i (d) in the direction \Gamma ~
is the
vector from (2.10) and fi - 0. For
d we get
~
d) T (\Gamma ~
\Gammab T
~
~
~
d)
\Gammab T
~
d)
d
where we used (2.10) and that, from (2.16), if
d then \Gammab T
~
~
For the objective function we have that
(r d \Psi( ~
~
d) T (\Gamma ~
\Gammaa T ~
d T A ~
~
d T ~
~
~
d T ~
~
d T ~
d T A ~
~
where we used the quadratic growth condition (2.3). Choose now
d
2:
Assume that ~
d 6= 0,
d
. Using that
d T A ~
~
d
d
d
d
d
d
d
d
d
where we used that from our choice of fl 00
3 (2.21) and since
d
3 we have c fi
d
and c fi
d
We also used the definition of c ffi (2.22) and that c 1 - c ffi .
Using (2.23) in (2.18) we get
r d \Psi( ~
d) T (\Gamma ~
d
d
d
Using (2.19) and (2.20) in (2.17) we get for all
d
d) T (\Gamma ~
d
d
d
d
0:
From (2.25) and (2.24) we get that if ~
and ~
3 (2.21) then there exists a direction
~
that produces strict decreases in the objective function and the active constraints.
Therefore ~
d cannot be a stationary point of (2.15). Otherwise (1.3) implies that there
exist the multipliers -
m , not all of them of 0 such that
d)
d
From (2.25) and (2.24) we get, after multiplying with ~
that
d) T ~
d
d) T ~
which is a contradiction that proves the lemma with c ffi defined in (2.22) and
Lemma 2.6. There exists
d with
d
stationary point of TRQCQP(fl) (2.1) with Lagrange multipliers - 2 IR
Proof We take
defined in (2.11), fl 2 is the quantity from Lemma 2.4 and fl 3 is the quantity
from Lemma 2.5. Lemma 2.4 ensures that the Lagrange multipliers exist at any
stationary point of TRQCQP(fl) (2.1).
Assume the contrary of the conclusion of the Lemma: For any k 2 IN , there exists
~
d k a stationary point of TRQCQP(fl) (2.1) with
multipliers
and (1.6). In particular,
a +A ~
~
By Lemma 2.5 since
must have c k
can choose -   such that for a subsequence k q , q !1, we have lim q!1
with jj-   jj
d   , where
d
We can now divide through (2.27) with
take the limit as
and
d
~
multiply with p and use (2.10) and the fact that jj-   jj
to get
~
d
which is a contradiction. This proves the lemma. \Pi
Theorem 2.7. There exists fl 5 ? 0, such that, for any fl such that
TRQCQP(fl) (2.1) has the unique stationary point
Proof Choose
ae
oe
where j is the quantity from Lemma 2.3, c ffi is the quantity from Lemma 2.5, -1
is the quantity from Lemma 2.6 and 4, are the bounds on the trust
regions that ensure that all preceding results hold.
Let ~
d 6= 0 be a stationary point of TRQCQP(fl) (2.1) with
Lemma 2.4 TRQCQP(fl) (2.1) satisfies MFCQ (1.7) at ~
d. Therefore there exist the
Lagrange multipliers - 0, c 1 - 0 which, together with ~
d satisfy (1.6), or
a
d)
~
d)
~
d T ~
~
~
d T ~
Since
d
applies to give that c 1 - c ffi . Since
d
4 we have that jj-jj 1 -1 from Lemma 2.6. We define
~
~
d:
After applying the triangle inequality and using (2.28) we have that
d
~
d
~
d
d
d
For the last inequality,
c- and
d
results in jjwjj - j. From (2.30)
and (2.31) we have that
a
This implies, from Lemma 2.3, that there exists -   2 M   ( a Lagrange multiplier for
TRQCQP(fl) (2.1) at
(2.
a
Adding the last equality to the first equation in (2.30), dividing by 2 and multiplying
with ~
d T we obtain
a T ~
dA ~
~
~
d)
d
0:
We now use the identity u
well as the fact that (-
~
~
from (2.33) and (2.30) to obtain
d +2
~
dA ~
d +2
~
~
~
d)
d
a T ~
dA ~
(-
~
d)
d
which results in
a T ~
dA ~
d
(-
~
Since ~
d is feasible for TRQCQP(fl) (2.1) and since
d
the quadratic
growth condition (2.3) holds to give that a T ~
dA ~
d
. Define
From (2.33), (2.31) and (2.32) we have jj-
d
Using all these bounds
in (2.34), together with the arithmetic-quadratic mean inequality we get
d
- a T ~
dA ~
d
(-
d) -4
d
d
d
Since
d
our assumption, we obtain, after dividing through the previous
inequality with
d
that
d
Choose now
ae
oe
From (2.35) it follows that the unique stationary point of TRQCQP(fl) (2.1) with
The proof is complete. \Pi
3. Sequential Quadratically Constrained Quadratic Programming. In
this section, we introduce the sequential quadratically constrained quadratic programming
algorithm. We prove that under the conditions set forth in the introduction,
the algorithm induces superlinear convergence. Since our main interest is the rate of
convergence of the algorithm, we do not address global convergence issues.
We consider the following form of the algorithm:
1. Choose a starting point x k ,
2. Let stationary point of
xx f(x)d
subject to g i (x) +r x
3. Take x restart.
At every step, the algorithm solves a problem with quadratic constraints and a
quadratic objective, none of which are assumed to be convex. We name the above
algorithm sequential quadratically constrained quadratic programming or SQCQP.
As outlined in Subsection 1.1, we assume without loss of generality that g i (x
eventually considering a sufficiently small trust-region, and
that the quadratic growth condition (1.1) and MFCQ (1.7) hold at a local solution
x   of the nonlinear program (1.2). From [14, 6] these conditions are equivalent to
MFCQ (1.7) and (1.12), which are expressed only in terms of the derivatives of the
data up to the second order. We show that (3.1) is feasible for fl fixed and x in some
neighborhood of x   . Since it is also bounded, a stationary point must exist.
Due to the fact that it captures the entire information up to second order for
(1.2) at x   , the quadratically constrained quadratic program
xx f(x   )d
subject to r x g(x   )
satisfies MFCQ (1.7) and (1.12) at As a result of [14, 6] it follows that (3.2)
satisfies MFCQ (2.2) and the quadratic growth condition (2.3). Therefore, all the
results from Section 2 apply for (3.2). We follow a line of proof similar to the one in
Section 2.
ffl Theorem 3.1 proves that MFCQ (1.7) is satisfied by (3.1) in a neighborhood
of x   and that the trust-region constraint is inactive at any stationary point
d of (3.1). Corollary 3.2 further insures that in a neighborhood of x   , the
Lagrange multipliers of (3.1) are uniformly bounded.
ultimately implies that for any Lagrange multiplier - at a stationary
point d of (3.1) at there exists a sufficiently close Lagrange
multiplier -   at whose active subset is included in the active subset of
-. This in turn leads to the conclusions of Lemma 3.4 that (- i +-
is a stationary point of (3.1).
This helps bound above the variations in the objective function of (3.1) in
the proof of Theorem 3.5.
Theorems 3.5 and 3.6 prove the superlinear convergence of a sequence x
initiated sufficiently close to x   , where d k is any stationary point of
(3.
Theorem 3.1. There exists fl 6 ? 0 and a neighborhood N fl 6
any fl with there exists a neighborhood N fl (x   ) of x   such that
(i) The QCQP (3.1) is feasible for any x 2 N fl (x   ).
(ii) For any x 2 N fl 6
any d with jjdjj - fl 6 we have
are the quantities entering the definition of MFCQ (1.7).
(iii) For any sequence x k 2 N fl (x
and with ~
d k a stationary point of (3.1) at must have ~
(iv) The constraint d T d - fl 2 is inactive for any x 2 N fl (x   ) and d stationary
point of (3.1).
Proof Since (3.2) satisfies MFCQ (2.2) and the quadratic growth condition
(2.3) at 0, from Theorem 2.7 there exists
6 , such that, for any 0 !
6 , ~
is the only stationary point of (3.2). Choose now fl such that
6 . Since (3.2)
satisfies MFCQ (2.2), then, from [21], for any sufficiently small perturbation of (3.2)
we still obtain a feasible nonlinear program. We regard (3.1) as a perturbation of (3.2)
and we therefore have, from the fact that f; g are twice continuously differentiable, that
there exist a neighborhood N 2
such that (3.1) is feasible for any x 2 N 2
which proves part (i) as long as N fl
which will be established later.
We also have that, for all
since from MFCQ (1.7) is a bound on the second derivatives
of m. If we chose fl 00
4c2g
, d with jjdjj - fl 00
6 and N fl 6
4c2g
we get from the previous bound that, since now c 2g jjx \Gamma x   jj - i0,
c 2g jjdjj - i0,
0which shows part (ii), after defining
00g. We now choose N 3
both the conclusions of (i) and (ii) hold. In
particular, for any fl 2 (0; fl 6
must have a stationary point since it
is feasible and bounded.
Assume now that the conclusion (iii) does not hold: There exists fl ? 0, with
and a sequence x k ! x   , x k 2 N 3
and the corresponding
stationary points d k of (3.1) are bounded bellow
sufficiently
large. Since d k is a stationary point of (3.1) at must satisfy the first-order
necessary conditions (1.3) for some multipliers - k
Since the multipliers -
1, and the direction
we can extract a subsequence k q such that x kq ! x   ,
1. Taking the limit as q ! 1 in (3.3) we obtain
from the continuity of all data involved in terms of (x; d), that d   is a stationary point
of (3.2). Since d   6= 0 this contradicts the outcome of Theorem 2.7 that is valid due
to our choice of fl 6 . This proves (iii).
Assume now that (iv) does not hold. It then follows that there exists a sequence
stationary point and such that
fl. But this contradicts
the conclusion of (iii) and thus there exists a neighborhood N fl
that for x 2 N fl (x   ) any stationary point of (3.1) satisfies d T d ! fl 2 and for which the
conclusions of parts (i),(ii) and (iii) hold. The proof is complete. \Pi
Corollary 3.2. Any stationary point of (3.1) satisfies the Kuhn-Tucker conditions
1.6, for any 0 - There exists
-1 such that, for any x 2 N fl (x   ), any stationary point d of (3.1) and any Lagrange
multipliers - satisfying the Kuhn-Tucker conditions we have jj-jj 1 -1 .
Proof Theorem 3.1(iv), we have that for any
stationary point d, we must have jjdjj ! fl. Therefore only the
can be active at a stationary point d. Then by
Theorem 3.1(ii), MFCQ (1.7) is satisfied at d and thus there exist multipliers - 0
satisfying the Kuhn-Tucker conditions and in particular:
Multiplying through with p we get
after using the usual norm inequalities we get
Since on N fl (x   ) the expression from the right hand side is bounded above, there
exists -1 for which the conclusion of this corollary holds. \Pi
Lemma 3.3. There exists fl 7 ? 0 and a constant c   ? 0 such that for any fl with
there exists a neighborhood N 1
for any d a stationary point of (3.1) with the Lagrange multipliers - there exist the
Lagrange multipliers at
and
Proof Take fl such that d be a stationary
point of (3.1) with the Lagrange multipliers - 0 (which exist from Corollary (3.2)).
From the Kuhn-Tucker conditions we obtain
and thus
Using that jjr x and that jjr x g i
c 2g jjx \Gamma x   jj, where c 2f and c 2g are bounds on the second derivatives of f and g, we
get from (3.5) and Corollary 3.2 that
We choose
, where j is the quantity from Lemma 2.2. From (3.6)
it follows that, for any fl -
that, since jjdjj -
We can therefore apply Lemma 2.2 and (3.6) to get that there exists -   2 M(x   )
with the properties required, after taking
is the constant from Lemma 2.3. \Pi
Lemma 3.4. Let x 2 N 1
is the neighborhood
obtained in Lemma 3.3. Let - be a Lagrange multiplier associated with a stationary
point d at x of (3.1). Let -   2 M(x   ) such that -
and such that
where \Theta P (d) is a continuous function that satisfies \Theta P
Proof Using the first-order Taylor remainder formula [1] for g i (y) around
for the fact that g i (x) is twice continuously differentiable for
we obtain that
is a continuous function, it follows that
is a continuous function on jjwjj - fl 7 with the property that \Theta i We have
that d is a stationary point of (3.1) and as a result satisfies g i
Replacing w with d in (3.7) we obtain
now
\Theta P
\Theta i (d):
From the definition of \Theta i (d) we have that \Theta P is continuous and that \Theta P
From the definition of P (x) (1.13), we get that,
This proves point (i). Since -   is such that - our hypothesis, and
since d is a stationary point of (3.1) and thus satisfies the complementarity condition
xx g(x)d
this implies that, for
xx g(x)d
or, by using (3.7),
and thus
which completes the proof of (ii) and of the Lemma. \Pi
From here on we use extensively that, for h twice continuously differentiable, we
have
is a continuous function with / 3h Indeed by
Taylor's theorem we have that there exist continuous functions / 1
3h
3h
3h
which satisfy / 1
3h
3h
3h
and
which in turn implies, after choosing / 2
3h
3h
and using the Cauchy-Schwarz
inequality, that
The relation (3.9) now follows by comparing (3.9), (3.10) and (3.12) and taking
3h (z). If h were three times continuously differentiable, then
would be related to the third derivative of h, from the error formula of trapezoidal
integration [1], which is the origin of our subscript notation.
Theorem 3.5. Let be a sequence such that x k ! x   , x k 6= x   . Let d k
be a stationary point of (3.1) for is the quantity
from Lemma 3.3. Then
lim
Proof Since x k ! x   , the sequence x k eventually reaches N 1
means that Lemmas 3.4 and 3.3, as well as all preceding results apply for
sufficiently large k. Using (3.9) we get that
is a bound obtained by using (3.11) for f(x) between x k
and x k . / 0
3f is a continuous function satisfying / 0
From Corollary 3.2, there exist the Lagrange multiplier - k , which, together with
d k satisfies the Kuhn-Tucker conditions (1.6) for (3.1) at
there exists a - \Lambdak 2 M(x   ) such that
Using the Kuhn-Tucker conditions (1.6) to replace r x
r x f(x   ) in terms of g and the Lagrange multipliers, and using the bounds
that follow from Corollary 3.2, we get from (3.13)
3g
is a bound obtained from applying (3.11) to g i (x),
between the points x k taking the maximum among
the resulting bounds. / 0
3g a continuous function satisfying / 0
We now
make use of the identity ab for the terms
Continuing the bounding in (3.15) we get
3f
(3.
We now bound all terms involving - and -   . Using that
and that g is twice continuously differentiable and thus
we get
mc   c 2g (
Using that jj-jj 1 -1 from Corollary 3.2, (3.9) for g i (x) and that g i (x
as well as Lemma 3.4 (ii) we obtain that
Putting together the bounds from (3.16), (3.17) and (3.18) we obtain
Since the bound on the right hand side is nonnegative, we can use Lemma 3.4 (i)
and the quadratic growth condition (1.14) to get that
oe
where
are continuous functions of their arguments that satisfy \Phi 1 (0;
We now use that ab - to get from (3.20) that
oe
0, from Theorem 3.1, there exists K 1 such that 8k - K 1
we have
Taking the corresponding term to the right-hand side, we get that, 8k - K 1 ,
Now using the continuity of \Phi 2 and \Theta P , and that, from Theorem 3.1 (iii), d k ! 0,
we get that
lim
oe
lim
0:
or that
lim
Using now the consequence of the triangle inequality
and dividing the relation with
and taking the limit, this implies that
lim
and thus
lim
Dividing (3.22) by the last limit we get that
lim
which proves the claim of the Theorem. \Pi
Theorem 3.6. Let fl be such that is the quantity from
Lemma 3.3. There exists a radius r   such that for any x 2 B(x
a stationary point of (3.1), then
Whenever started inside B(x   ; r   ), the SQCQP algorithm produces a sequence x k !
x   that is superlinearly convergent,
lim
Proof Assume the contrary: For any q 2 IN , there exists x q 6= x   such that
q and d q a stationary point of (3.1) such that
Therefore x q ! x   , and by Theorem 3.5
lim
which contradicts (3.23). As a result there exists r   with the properties required by
the Theorem. When started with x 0 2 B(x   ; r   ), the SQCQP algorithm produces a
sequence x , such that
We can now use Theorem 3.5 to claim that
lim
which proves the superlinear convergence of x k to x   . The proof is complete. \Pi
Note If the data of the problems are three times continuously differentiable,
then the functions /
are Lipschitzian in their respective arguments, which
considerably simplifies the notation for the proof of Theorem 3.5. For instance,
case. Using essentially the same proof, the conclusion
can then be strengthened to show that the order of convergence is at least 34. Conclusions. We present an algorithm that achieves superlinear convergence
of the iterates to a local minimum of the nonlinear program (1.2) at which MFCQ
(1.7) and the quadratic growth condition (1.1) are satisfied. The conditions we
impose allow even situations for which no locally convex augmented Lagrangian exists,
a case not accommodated by most previous results in the literature.
At each step we solve a subproblem generated by approximating the function and
the constraints by the second-order Taylor series at the current iterate. We also add
a trust-region constraint, which insures that the problem is bounded. The algorithm
therefore solves at each step a quadratically constrained quadratic program (QCQP)
and we thus call it sequential quadratically constrained quadratic program (SQCQP).
The subproblem to be solved is not necessarily convex. However we prove that
for a suitable, fixed size of the trust region, the associated constraint is inactive at
any stationary point of QCQP. As a result, any stationary point of the QCQP induces
superlinear convergence of the iterates, which obviates the need for finding the global
optimum of the subproblem.
A subproblem that has quadratic constraints is more difficult to solve than a
subproblem with linear constraints, the latter being the case of Sequential Quadratic
Programming algorithms [19]. One could of course solve the QCQP with a nonlinear
programming technique. The algorithm in [2] achieves at least linear convergence
on the subproblem under the conditions considered here. Since in this work a more
accurate model of the constraints is considered, compared to SQP, it would be expected
that a smaller number of exterior iterations and thus of function evaluations is
needed before completion. However, given the complexity of the subproblem, this will
not necessarily results in superior runtime. Nevertheless, algorithms can be derived
to deal directly with quadratically constrained problem via semidefinite relaxation
[16]. Devising methods that specifically accommodate quadratic constraints will be
the subject of future research.



--R

An Introduction to Numerical Analysis
Degenerate
New York

Local Analysis of Newton-Type Methods for Variational Inequalities and Non-linear Programming

Introduction to Sensitivity and Stability Analysis in
Practical Methods of Optimization
A necessary and sufficient regularity condition to have bounded multipliers in nonconvex programming
Differential stability in nonlinear programming
Stabilized sequential quadratic programming
Stability in the presence of degeneracy and error estimation
On approximate solutions of systems of linear inequalities
Necessary and sufficient conditions for a local minimum.
On Sensitivity analysis of nonlinear programs in Banach spaces: the approach via composite unconstrained optimization


The Fritz John necessary optimality conditions in the presence of equality constraints

Superlinear convergence of an interior-point method despite dependent constraints
Applications to nonlinear programming Mathematical Programming Study 19
Sensitivity analysis of nonlinear programs and differentiability properties of metric projections
Superlinear convergence of a stabilized SQP method to a degenerate solution
Modifying SQP for degenerate problems
--TR
quadratic constraints;sequential quadratic programming;degenerate constraints;superlinear convergence