Convergence Properties of an Augmented Lagrangian Algorithm for Optimization with a Combination of General Equality and Linear Constraints.
We consider the global and local convergence properties of a class of augmented Lagrangian methods for solving nonlinear programming problems.  In these methods, linear and more general constraints are handled in different ways.  The general constraints are combined with the objective function in an augmented Lagrangian. The iteration consists of solving a sequence of subproblems; in each subproblem the augmented Lagrangian is approximately minimized in the region defined by the linear constraints.  A subproblem is terminated as soon as a stopping condition is satisfied.  The stopping rules that we consider here encompass practical tests used in several existing packages for linearly constrained optimization.  Our algorithm also allows different penalty parameters to be associated with disjoint subsets of the general constraints.  In this paper, we analyze the convergence of the sequence of iterates generated by such an algorithm and prove global and fast linear convergence as well as show that potentially troublesome penalty parameters remain bounded away from zero.
Introduction
. Introduction
In this paper, we consider the problem of calculating a local minimizer of the
smooth function
where x is required to satisfy the general equality constraints
and the linear inequality constraints
Here f and c i map ! n into !, A is a p-by-n matrix and b 2 ! p .
A classical technique for solving problem (1.1)-(1.3) is to minimize a suitable
sequence of augmented Lagrangian functions. If we only consider the problem (1.1)-
(1.2), these functions are defined by
where the components - i of the vector - are known as Lagrange multiplier estimates
and - is known as the penalty parameter (see, for instance, Hestenes [18], Powell [23]
and Bertsekas [3]). The question then arises how to deal with the additional linear
inequality constraints (1.3). The case where A is the identity matrix (that is when
specifies bounds on the variables) has been considered by Conn et al. in [5]
This research was supported in part by the Advanced Research Projects Agency of the Department
of Defense and was monitored by the Air Force Office of Scientific Research under Contract No
F49620-91-C-0079. The United States Government is authorized to reproduce and distribute reprints
for governmental purposes notwithstanding any copyright notation hereon.
This work was also supported by the Belgian national Fund for Scientific Research.
and [7]. They propose keeping these constraints explicitly outside the augmented Lagrangian
formulation, handling them directly at the level of the augmented Lagrangian
minimization. That is, a sequence of optimization problems, in which (1.4) is approximately
minimized within the region defined by the simple bounds, is attempted. In this
approach all linear inequalities other than bound constraints are converted to equations
by introducing slack variables and incorporated in the augmented Lagrangian
function. This strategy has been implemented and successfully applied within the
LANCELOT package for large-scale nonlinear optimization (see Conn et al. [6]). How-
ever, such a method may be inefficient when linear constraints are present as there
are a number of effective techniques specifically designed to handle such constraints
directly (see Arioli et al. [1], Forsgren and Murray [14], Toint and Tuyttens [24], or
and Carpenter [25], for instance). This is especially important for large-scale
problems. The purpose of the present paper is therefore to define and analyze
an algorithm where the constraints (1.3) are kept outside the augmented Lagrangian
and handled at the level of the subproblem minimization, thus allowing the use of
specialized packages to solve the subproblem.
Our proposal extends the method of Conn et al. [5] in that not only bounds but
general linear inequalities are treated separately. Fletcher [13, page 295] remarks on
the potential advantages of this strategy.
Furthermore, it is often worthwhile from the practical point of view to associate
different penalty parameters to subsets of the general constraints (1.2) to reflect different
degrees of nonlinearity. This possibility has been considered by many authors,
including Fletcher [13, page 292], Powell [23] and Bertsekas [3, page 124]. In this case,
the formulation of the augmented Lagrangian (1.4) can be refined: we partition the
set of constraints (1.2) into q disjoint subsets fQ j g q
redefine the augmented
Lagrangian as
where - is now a q-dimensional vector, whose j-th component is - j ? 0, the penalty
parameter associated with subset Q j . Because of its potential usefulness, and because
its analysis is difficult to directly infer from the single penalty parameter case, this
refined formulation will be adopted in the present paper.
The theory presented below handles the linear inequality constraints in a purely
geometric way. Hence the same theory applies without modifications if linear equality
constraints are also imposed and all the iterates are assumed to stay feasible with
respect to these new constraints. It is indeed enough to apply the theory in the affine
subspace corresponding to this feasible set. As a consequence, linear constraints need
not be included in the augmented Lagrangian and thus have the desirable property
that they have no impact on the structure of its Hessian matrix.
The paper is organized as follows. In Section 2, we introduce our basic assumptions
on the problem and the necessary terminology. Section 3 presents the proposed
algorithm and the definition of a suitable stopping criterion for the subproblem. The
global convergence analysis is developed in Section 4 while the rate of convergence
is analyzed in Section 5. Second order conditions are investigated in Section 6. Section
7 considers some possible extensions of the theory. Finally, some conclusions and
perspectives are outlined in Section 8.
2. The problem and related terminology. We consider the problem stated
in (1.1)-(1.3) and make the following assumptions.
AS1: The region nonempty.
AS2: The functions f(x) and c i (x), are twice continuously differentiable
for all x 2 B.
Assumption AS1 is clearly necessary for the problem to make sense. We note that
it does not prevent B from being unbounded.
We now introduce the notation that will be used throughout the paper.
Let g(x) denote the gradient r x f(x) of f(x) and H(x) denote its Hessian matrix
r xx f(x). We also define J(x) to be the m-by-n Jacobian of c(x), where
Hence
denote the Hessian matrix r xx c i (x) of c i (x). Finally, let g ' (x; -) and
denote the gradient, r x '(x; -), and the Hessian matrix, r xx '(x; -), of the
Lagrangian function
We note that '(x; -) is the Lagrangian solely with respect to the c i constraints. If we
define first-order Lagrange multiplier estimates componentwise as
where w [S] denotes the jSj-dimensional subvector of w whose entries are indexed by
the set S, we shall use the identity
r x \Phi(x;
Now suppose that fx k 2 Bg, f- k g and f- k g are infinite sequences of n-vectors,
m-vectors and positive q-vectors, respectively. For any function F , we shall use the
notation that F k denotes F evaluated with arguments x
So, for instance, using the identity (2.2), we have that
where we have written (2.1) in the compact form
We denote the vector w at iteration k by w k and its i-th component by w k;i . We also
use w k;[S] to denote the jSj-dimensional subvector of w k whose entries are indexed by
S.
Now let fx k subset K of the natural numbers N, be a convergent
subsequence with limit point x   . Then we denote the matrix whose rows are those
of A corresponding to active constraints at x   - that is the constraints which are
satisfied as equalities at x   - by A   . Furthermore, we choose Z   to be a matrix
whose columns form an orthonormal basis of the null space of A   , that is
A   Z
We define the least-squares Lagrange multiplier estimates (corresponding to A   )
at all points where the right generalized inverse
of J(x)Z   is well defined. We note that, whenever J(x)Z   has full rank, -(x) is
differentiable and its derivative is given in the following lemma
Lemma 2.1. Suppose that AS2 holds. If J(x)Z   Z T
J(x) T is nonsingular, -(x) is
differentiable and its derivative is given by
where the i-th row of R(x) is (Z T
Proof. The result follows by observing that (2.5) may be rewritten as
g(x) and J(x)Z
for some vector r(x). Differentiating (2.7) and eliminating the derivative of r(x) from
the resulting equations gives the required result. 2
We stress that, as stated, the Lagrange multiplier estimate (2.5) is not directly calculable
as it requires a priori knowledge of x   . It is merely introduced as an analytical
device.
Finally, the symbol k \Delta k will denote the ' 2 -norm or the induced matrix norm. We
are now in position to describe more precisely the algorithm that we propose to use.
3. Statement of the algorithm. We consider the algorithmic model we wish
to use in order to solve the problem (1.1)-(1.3). This model proceeds at iteration k by
computing an iterate x k which satisfies (1.3) and approximately solves the subproblem
min x2B
where the values of the Lagrange multipliers - k and penalty parameters - k are fixed
for the subproblem. Subsequently we update the Lagrange multipliers and/or decrease
the penalty parameters, depending on how much the constraint violation for (1.2) has
been reduced within each subset of the constraints. The motivation is simply to ensure
global convergence by driving, in the worst case, the penalty parameters to zero, in
which case the algorithms essentially reduce to the quadratic penalty function method
(see, for example, Gould [15]). The tests on the size of the general constraint violation
are designed to allow the multiplier updates to take over in the neighbourhood of a
stationary point.
The approximate minimization for problem (3.1) is performed in an inner iteration
which is stopped as soon as its current iterate is "sufficiently critical". We propose to
base this decision on the identification of the linear constraints that are "dominant" at
x (even though they might not be active) and on a measure of criticality for the part of
the problem where those constraints are irrelevant. Given ! - 0, a criticality tolerance
for the subproblem, we define, for a vector x 2 B, the set of dominant constraints at
x as the constraints whose indices are in the set
for some - 0 ? 0. Here a T
is the i-th row of the matrix A and b i is the
corresponding component of the right-hand side vector b. Denoting by A D(x;!) the
submatrix of A consisting of the row(s) whose index is in D(x; !), we also define
the cone spanned by the outward normals of the dominant constraints. The associated
polar cone is then
where cl(V ) denotes the closure of the set V . The cone T (x; !) is the tangent cone
with respect to the dominant constraints at x for the tolerance !. Note that D(x; !)
might be empty, in which case A D(x;!) is assumed to be zero, N(x; !) reduces to the
origin and T (x; !) is the full space.
We then formulate our "sufficient criticality" criterion for the subproblem as fol-
lows: we require that
is the projection onto the convex set V and ! k is a suitable tolerance at
iteration k. Once x k satisfying (3.3) has been determined by the inner iteration, we
denote
For future reference, we define Z k to be a matrix whose columns form an orthonormal
basis of V k , the null space of AD k
, and Y k to be a matrix whose columns form an
orthonormal basis of W
k . As above, we have that T k is the full space and N k
reduces to the origin when D k is empty. We note that, in this case, Z
I ,
the identity operator, and Y
We also note that V k ' T k , and hence that
since Z k Z T
k is the orthogonal projection onto V k .
It is important to note that the stopping rule (3.3) covers a number of more specific
choices, including the rule used in much existing software for linearly constrained
optimization (such as MINOS [21], LSNNO [24], or VE14 and VE19 from the Harwell
Subroutine Library [17]). The reader is referred to Section 7.2 for further details.
We are now in position to describe our algorithmic model more precisely. In this
model, we define ff k to be the maximum penalty parameter at iteration k (see (3.10)).
At this iteration, the parameters ! k and j k represent criticality and feasibility levels,
respectively.
partition of the set disjoint subsets
is given, as well as initial vectors of Lagrange multiplier estimates - 0
and positive penalty parameters - 0 such that
The strictly positive constants -
are specified. Set ff
approximately solves (3.1), i.e. such
that (3.3) holds.
[Test for convergence]. If kP T k
Step 3 [Disaggregated updates]. For
or Step 3b otherwise.
Step 3a [Update Lagrange multiplier estimates]. Set
Step 3b [Reduce the penalty parameter]. Set
where
Step 4 [Aggregated updates]. Define
If
then set
otherwise set
Increment k by one and go to Step 1.
Algorithm 3.1 is specifically designed for the first-order estimate (2.1), a formula
with potential advantages for large-scale computations. We refer the reader to Section
7.1 for a further discussion of a more flexible choice of the multipliers, covering,
among others, the choice of the least-squares estimates -(x) as defined in (2.5).
We immediately verify that our algorithm is coherent, in that
lim
Indeed, we obtain from (3.6) that ff k ! 1 for all k, and (3.14) then follows from (3.12)
and (3.13) if ff k tends to zero, or from (3.13) alone if ff k is bounded away from zero.
The restriction (3.6) is imposed in order to simplify the exposition. In a more
practical setting, it may be ignored provided the definition of ff 0 and (3.10) are replaced
by
and ff
respectively, for some constant fl s 2 (0; 1), and that (3.11) is replaced by
Algorithm 3.1 may be extended in other ways. For instance, one may replace the
definition of ! 0 , the first equation in (3.12) and the first equation of (3.13) by
. The definition of j 0 and the second equation
in (3.12) may then be replaced by
for some j s ? 0. None of these extensions alter the results of the convergence theory
developed below. The values used in the LANCELOT package in a similar context are
(relation (3.15) is also used with
ensuring that 0:01). The values
also seem suitable. The parameters !   and j   specify the final accuracy requested by
the user.
Finally, the purpose of the update (3.9) is to put more emphasis on the feasibility of
the constraints whose violation is proportionally higher, in order to achieve a "balance"
amongst all constraint violations. This balance then allows the true asymptotic regime
of the algorithm to be reached. The advantage of (3.9) is that this balancing effect
is obtained gradually, and not enforced at every major iteration, as is the case in
Powell [23]. Furthermore Powell's approach increases the penalties corresponding to
the constraints that are becoming too slowly feasible, based on the ' 1 -norm. Thus it
is only when they have changed sufficiently so that they are all within the constraint
violation tolerance that the Lagrange multiplier update is performed. By contrast, we
update the multipliers of the well-behaved constraints (assuming they correspond to a
particular partition - which is likely since that is, partly at least, why the partitions
exist) independently of more badly behaved ones. In addition, by virtue of using the
-norm, we do not give quite the same emphasis to the most violated constraint.
4. Global convergence analysis. We now proceed to show that Algorithm 3.1
is globally convergent under the following assumptions.
AS3: The iterates fx k g considered lie within a closed, bounded
domain\Omega\Gamma
AS4: The matrix J(x   )Z   has column rank no smaller than m at any limit point,
x   , of the sequence fx k g considered in this paper.
We notice that AS3 implies that there exists at least a convergent subsequence
of iterates, but does not, of course, guarantee that this subsequence converges to a
stationary point, i.e. that "the algorithm works". We also note that it is always
satisfied in practice because the linear constraints (1.3) includes lower and upper
bounds on the variables, either actual or implied by the finite precision of computer
arithmetic.
Assumption AS4 guarantees that the dimension of the null space of A   is large
enough to provide the number of degrees of freedom that are necessary to satisfy the
nonlinear constraints and we require that the gradients of these constraints (projected
onto this null space) are linearly independent at every limit point of the sequence of
iterates. This assumption is the direct generalization of AS3 used by Conn et al. [5].
We shall analyse the convergence of our algorithm in the case where the convergence
tolerances !   and j   are both zero. We first need the following lemma, proving
that (3.3) prevents both the reduced gradient of the augmented Lagrangian and its
orthogonal complement from being arbitrarily large when ! k is small.
Lemma 4.1. Let fx k g ae B; k 2 K, be a sequence which converges to the point x
and suppose that
where the ! k are positive scalar parameters which converge to zero as k 2 K increases.
Then
for some - 1 ? 0 and for all k 2 K sufficiently large.
Proof. Observe that, for k 2 K sufficiently large, ! k is sufficiently small and
sufficiently close to x   to ensure that all the constraints in D k are active at x   .
This implies that the subspace orthogonal to the normals of the dominant constraints
at x k , V k , contains the subspace orthogonal to the normals of the constraints active
at x   . Hence, we deduce that
where we have used (3.5) to obtain the second inequality and (3.3) to deduce the third.
This proves the first part of (4.1).
We now turn to the second. If D k is empty, then Y k is the zero matrix and the
second part of (4.1) immediately follows. Assume therefore that D k 6= ;. We first
select a submatrix -
of AD k
that is of maximal full row-rank and note that the
orthogonal projection onto the subspace spanned by the fa i g i2D k
is nothing but
A T
A T
Hence we obtain from the orthogonality of Y k , the bound jD k j - p, (3.2) and (3.4)
and the fact that all constraints in D k are active at x   for k sufficiently large, that
A T
A T
A T
A T
But there are only a finite number of nonempty sets D k for all possible choices of x k
and we may thus deduce the second part of (4.1) from (4.2) by defining
A T
A T
where the minimum is taken on all possible choices of D k and -
. 2
We now examine the behaviour of the sequence fr x \Phi k g. We first recall a result
extracted from the classical perturbation theory of convex optimization problems.
This result is well known and can be found, for instance, in [12, pp. 14-17].
Lemma 4.2. Assume that U is a continuous point-to-set mapping from S ' ! '
into the power set of ! n such that the set U(') is convex and non-empty for each
S. Assume that the real-valued function F (y; ') is defined and continuous on the
space and convex in y for each fixed '. Then, the real-valued function F
defined by
is continuous on S.
We now show that, if it converges, the sequence fr x \Phi k g tends to a vector which
is a linear combination of the rows of A   with non-negative coefficients.
Lemma 4.3. Let fx k g ae B,k 2 K, be a sequence which converges to the point x
and suppose that the gradients r x \Phi k , k 2 K, converge to some limit r x \Phi   . Assume
furthermore that (3.3) holds for k 2 K and that ! k tends to zero as k 2 K increases.
Then,
r x \Phi
for some vector -   - 0, where A   is the matrix whose rows are those of A corresponding
to active constraints at x   .
Proof. We first define
with the aim to show that this quantity tends to zero when k 2 K increases. We
obtain from (4.3), the Moreau decomposition [20] of r x \Phi k and the Cauchy-Schwarz
inequality, that
1g. As, for
sufficiently close to x   and ! k sufficiently small, all the constraints in D k must be
active at x   , we have that N k is included in the normal cone N(x   ; 0) and therefore the
vector PN k
belongs to this normal cone. Moreover, since the maximization
problem of the last right-hand side of (4.4) is a concave program, since x   is feasible for
(1.3), and since kx  large enough, we thus deduce that
is a global solution of this problem. Observing that
we obtain that
where we used the Cauchy-Schwarz inequality to deduce the last inequality. We may
now apply Lemma 4.1 and deduce from the second part of (4.1), (4.5) and the contractive
character of the projection onto a convex set containing the origin that
and thus, from (4.4) and our assumptions, that
Our assumption on the ! k sequence then implies that oe k converges to zero as k increases
in K.
Consider now the minimization problem
d;
subject to A(x
Since the sequences fr x \Phi k g and fx k g converge to r x \Phi   and x   respectively, we
deduce from Lemma 4.2 applied to the optimization problem (4.3) (with the choices
and the convergence of the sequence oe k to zero that the optimal value for problem
(4.6) is zero. The vector thus a solution for problem (4.6) and satisfies
r x \Phi
for some vector -   - 0, which ends the proof. 2
The important part of our convergence analysis is the next lemma.
Lemma 4.4. Suppose that AS1 and AS2 hold. Let fx k g ae B; k 2 K, be a sequence
satisfying AS3 which converges to the point x   for which AS4 holds and let -
where - satisfies (2.5). Assume that f- k g, k 2 K, is any sequence of vectors and that
nonincreasing sequence of q-dimensional vectors. Suppose further
that (3.3) holds where the ! k are positive scalar parameters which converge to zero as
increases. Then
(i) There are positive constants - 2 and - 3 such that
and
for all sufficiently large.
Suppose, in addition, that c(x
(ii) x   is a Kuhn-Tucker point (first-order stationary point) for the problem (1.1)-
is the corresponding vector of Lagrange multipliers, and the sequences
converge to -   for k 2 K;
(iii) The gradients r x \Phi k converge to g '
Proof. As a consequence of AS2-AS4, we have that for k 2 K sufficiently large,
exists, is bounded and converges to (J(x   )Z   . Thus, we may write
for some constant - 2 ? 0. Equations (2.3) and (2.4), the inner iteration termination
criterion (3.3) and Lemma 4.1 give that
for all k 2 K large enough. By assumptions AS2, AS3, AS4 and (2.5), -(x) is bounded
for all x in a neighbourhood of x   . Thus we may deduce from (2.5), (4.10) and (4.11)
that
Moreover, from the integral mean value theorem and Lemma 2.1 we have that
Z 1r x -(x(s))ds \Delta
where r x -(x) is given by equation (2.6), and where Now the
terms within the integral sign are bounded for all x sufficiently close to x   and hence
for all k 2 K sufficiently large and for some constant - 3 ? 0, which implies the
inequality (4.8). We then have that -(x k ) converges to -   . Combining (4.12) and
(4.14) we obtain
which gives the required inequality (4.7). Then, since by assumption ! k tends to zero
as k increases, (4.15) implies that - k converges to -   and therefore, from the identity
(2.3), r x \Phi k converges to g ' (x   ; -   ). Furthermore, multiplying (2.1) by - k;j , we obtain
Taking norms of (4.16) and using (4.15), we derive (4.9).
Now suppose that
c(x
Lemma 4.3 and the convergence of r x \Phi k to g ' (x   ; -   ) give that
for some vector -   - 0. This last equation and (4.17) show that x   is a Kuhn-Tucker
point and -   is the corresponding set of Lagrange multipliers. Moreover (4.7) and
(4.8) ensure the convergence of the sequences f -(x
K. Hence the lemma is proved. 2
We finally require the following lemma in the proof of global convergence, which
shows that the Lagrange multiplier estimates cannot behave too badly.
Lemma 4.5. Suppose that, for some j (1 - j - q), - k;j converges to zero as k
increases when Algorithm 3.1 is executed. Then the product - k;j k- converges to
zero.
Proof. As - k;j converges to zero, Step 3b must be executed infinitely often
for the j-th subset. Let K be the set of indices of the iterations in
which Step 3b is executed.
We consider how the j-th subset of Lagrange multiplier estimates changes between
two successive iterations indexed in the set K j . Firstly note that - kv+1;[Q j
At iteration
where the summation is null if
Substituting (4.19) into (4.18), multiplying both sides by - kv+t;j , taking norms and
using (3.9), yields
and hence
Using the fact that (3.7) holds for we deduce that
Now defining
we obtain that
for all t such that k
Thus, from (4.22) and the inequality - ! 1, if ae v converges to zero, then ffi v and
hence, from (4.21), - kv+t;j k- both converge to zero. To complete the proof
it therefore suffices to show that ae v converges to zero as v tends to infinity.
Suppose first that ff k is bounded away from zero. Then we must have that (3.13)
is used for all k sufficiently large, with ff 1). This and
the definition of ae v in (4.20) imply that
min
for sufficiently large v. As (3.13) also guarantees that j k tends to zero, we deduce that
ae v converges to zero. This completes the proof for the first case.
Suppose now that ff k converges to zero. This implies that each of the q independent
penalty parameters is reduced an infinite number of times. Consider the progress
of ff k over the course of q successive decreases (3.11). As (3.11) only happens when
the currently largest penalty parameter, - k;j say, is reduced, as (3.9) requires that this
penalty parameter is reduced by - , and because there can only possibly be at most
parameters in the interval (- k;j ; - k;j ], it follows that ff k must be
reduced by at least - over q successive decreases (3.11). Thus, considering the possible
outcomes (3.12) and (3.13), each j kv+l must be bounded by a quantity of the form
t. Furthermore, at most q such terms can involve
any particular i and t. Therefore, since - ff kv ! 1, we obtain that
Thus we see that, as ff kv converges to zero, so does ae v , completing the proof for the
second case. 2
We can now derive the desired global convergence property of Algorithm 3.1,
which is analogous to Theorem 4.4 in Conn et al. [5].
Theorem 4.6. Assume that AS1 and AS2 hold. Let x   be any limit point of the
sequence fx k g generated by Algorithm 3.1 of Section 3 for which AS3 and AS4 hold
and let K be the set of indices of an infinite subsequence of the x k whose limit is x   .
Finally, let -  conclusions (i), (ii) and (iii) of Lemma 4.4 hold.
Proof. Our assumptions are sufficient to reach the conclusions of part (i) of
Lemma 4.4. We now show that c(x   and therefore that
c(x   To see this, we consider a analyze two separate cases.
The first case is when - k;j is bounded away from zero. Hence Step 3a must be
executed every iteration for k sufficiently large, implying that (3.7) is always satisfied
for k large enough. We then deduce from (3.14) that c(x k ) converge to zero.
The second case is when - k;j converges to zero. Then Lemma 4.5 shows that
tends to zero. Using this limit and (3.14) in (4.9), we obtain that
tends to zero, as desired.
As a consequence, conclusions (ii) and (iii) of Lemma 4.4 hold. 2
We finally note that global convergence of Algorithm 3.1 can be proved under
much weaker assumptions on - k;j and ! k . The reader is again referred to Conn et al.
[9] for further details.
5. Asymptotic convergence analysis. The distinction between dominant and
non-dominant (floating) linear inequality constraints has some implications in terms of
the identification of those constraints that are active at a limit point of the sequence of
iterates generated by the algorithm. Given such a point x   we know from Theorem 4.6
that it is critical, i.e. that \Gammag ' for the corresponding Lagrange
multipliers -   . If we now consider a linear constraint with index
is active at x   , we may define the normal cone N [i]
to be the cone spanned by the
outwards normals to all linear inequality constraints active at x   , except the i-th
one. We then say that the i-th linear inequality constraint is strongly active at x   if
\Gammag '
. In other words, the i-th constraint is strongly active at a critical
point if this point ceases to be critical when this constraint is ignored. Let us denote by
S(x   ) the set of strongly active constraints at x   . All non-strongly active constraints
at x   are called weakly active at x   . We now prove the reasonable result that all
strongly active constraints at a limit point x   are dominant for k large enough.
Theorem 5.1. Assume that AS1-AS3 hold. Let fx k g, k 2 K, be a convergent
subsequence of iterates produced by Algorithm 3.1, whose limit point is x   with corresponding
Lagrange multipliers -   . Assume furthermore that AS4 holds at x   . Then
for all k sufficiently large.
Proof. Consider a linear inequality constraint i 2 S(x   ). Then, by definition
of this latter set, we have that \Gammag '
. Since Theorem 4.6 guarantees that
r x \Phi k converges to g ' (x   ; -   ) and as N [i]
is closed, we have that \Gammar x \Phi k 62 N [i]
for
large enough. Therefore, one obtains from the Moreau decomposition [20] of
\Gammar x \Phi k that

for some ffl ? 0 and for all sufficiently large k 2 K, where T [i]

. We have
also from (3.3) that kP T k
(\Gammar x \Phi k )k is arbitrarily small, because ! k tends to zero (see
(3.14)). Assume now that, for some arbitrarily large k 2 K, we have that i 62 D k . This
implies that T [i]
hence that (5.1) is impossible. We therefore deduce that i
must belong to D k , which proves the theorem. 2
This result is important and is the generalization of Theorem 5.4 by Conn et al.
[5]. It can also be interpreted as a means of active constraint identification, as is clear
from the following easy corollary.
Corollary 5.2. Suppose that the conditions of Theorem 5.1 hold. Assume
furthermore that all linear inequality constraints active at x   have linearly independent
normals and are non-degenerate, in the sense that
where ri[V ] denotes the relative interior of a convex set V . Then D k is identical to
the set of active linear inequality constraints at x   for all k 2 K sufficiently large.
Proof. The non-degeneracy assumption and the linear independence of the
active constraints normals imply that -   is unique and only has strictly negative
components. Therefore each of the active linear inequality constraints at x   is strongly
active at x   , and the desired conclusion follows from Theorem 5.1. 2
We note here that the non-degeneracy assumption corresponds to strict complementarity
slackness in our context (see, for instance, Dunn [11], or Burke et al. [4]).
We now make some additional assumptions before pursuing our local convergence
analysis. We intend to show that all penalty parameters are bounded away from zero.
AS5: The second derivatives of the functions f(x) and c i (x) (1 - i - m) are Lipschitz
continuous at any limit point x   of the sequence of iterates fx k g.
Suppose that (x   ; -   ) is a Kuhn-Tucker point for problem (1.1)-(1.3) and let
I be any subset of the linear inequality constraints which are active at x
that contains all strongly active constraints (S(x   plus an arbitrary
subset of weakly active constraints at x   . Then, if the columns of the matrix
Z form an orthonormal basis of the subspace orthogonal to the normals of
the constraints in I, we assume that the matrix
is nonsingular for all possible choices of the weakly active constraints in the
set I.
We note that AS6 implies AS4 and seems reasonable in that the definition of
strongly and weakly active constraints may vary with small perturbations in the prob-
lem, for instance when lies in one of the extreme faces of the cone N   .
Our assumption might be seen as a safeguard against the possible effect of all such
perturbations.
We now make the distinction between the subsets for which the penalty parameter
converges to zero and those for which it stays bounded away from zero. We define
We also denote
and
ae k
We now prove an analog to Lemma 5.1 by Conn et al. [5] which is suitable for our
more general framework.
Lemma 5.3. Assume that AS1-AS3 hold. Let fx k g, k 2 K, be a convergent
subsequence of iterates produced by Algorithm 3.1, whose limit point is x   with corresponding
Lagrange multipliers -   . Assume that AS5 and AS6 hold at x   . Assume
furthermore that Z 6= ;.
there are positive constants -
and an integer k 1
such that, if ff k 1 -
ff, then
and
(ii) If, on the other hand, P 6= ;, there are positive constants -
and an integer k 1 such that, if - k 1 ;Z -
ff, then
and
Proof. We will denote the gradient and Hessian of the Lagrangian function,
taken with respect to x, at the limit point
and H '
, respectively. Similarly,
J   will denote J(x   ). We also define We observe that the assumptions
of the lemma guarantee that Theorem 4.6 can be used.
We first note that there is only a finite number of possible D k , and we may thus
consider subsequences of K such that D k is constant in each subsequence. We also
note that each k 2 K belongs to a unique such subsequence. In order to prove our
result, it is thus sufficient to consider an arbitrary infinite subsequence -
K such that,
is independent of k. This "constant" index set will be denoted by D.
As a consequence, the cones N k and T k , the subspaces V k and W k and the orthogonal
matrices Z k and Y k are also independent of k; they are denoted by N , T , V , W , Z
and Y , respectively.
Using (2.3) and Taylor's expansion around x   , we obtain that

where
ds
and
The boundedness and Lipschitz continuity of the Hessian matrices of f and c i in a
neighbourhood of x   , together with the convergence of -
- k to -   then imply that
and
for some positive constants - 8 and - 9 . Moreover, using Taylor's expansion again,
along with the fact that Theorem 4.6 ensures the equality c(x   we obtain that
where
Z 1s
ds
(see Gruver and Sachs [16, page 11]). The boundedness of the Hessian matrices of the
c i in a neighbourhood of x   then gives that
for some positive constant - 10 . Combining (5.9) and (5.12), we obtain

!/

where we have suppressed the arguments of the residuals r 1 , r 2 and r 3 for brevity.
Using the orthogonal decomposition of ! n into V \Phi W and defining
we may rewrite (5.14) as


r 4
where r 4
. Expanding this last equation gives thatB @


(5.15)B @
r
We now observe that (3.3), the inclusion V ' T and the fact that ! k tends to zero
imply that
0:
Substituting (5.16) in (5.15), removing the middle horizontal block and rearranging
the terms of this latter equation then yields that

!/
Roughly speaking, we now proceed by showing that the right-hand side of this relation
is of the order of ' k
We will then ensure that the vector on the left-hand side is of the same size, which is
essentially the result we aim to prove. We first observe that
from (4.1). We then obtain from (4.7) and (5.19) that
. Furthermore, from (5.10), (5.11), (5.13), (5.19) and (5.20),
. We now bound c(x k ) by distinguishing components from
Z and P . We first note that, since the penalty parameters for each subset in P are
bounded away from zero, the test (3.7) is satisfied for all k sufficiently large. Moreover,
the remaining components of c(x k ) satisfy the bound
for all j 2 Z and all k sufficiently large, using (4.9). Hence, using (5.3), (3.7) and
(5.22), we deduce that
Note that the first term of the last right-hand side only appears if P is not empty.
Since the algorithm ensures that
because may obtain from (4.1), (5.23) and (5.19) that
assumption AS6, the coefficient
matrix on the left-hand side of (5.17) is nonsingular. Let M be the norm of its
Multiplying both sides of the equation by this inverse and taking norms, we
obtain from (5.18), (5.21), (5.24) and (5.25) that
Suppose now that k is sufficiently large to ensure that
and let
Recall that ff 0 and hence -
ff, the relations (5.26)-(5.28) give
As converge to zero, we have that
for k large enough. Hence inequalities (5.29) and (5.30) yield that
If P is empty, we use (5.19), (5.31) and (5.18), the fact that - and the
inequality
to deduce (5.4), where - 4
deduce (5.5) from (4.7) and (5.4). Now, using (2.1),
and (5.6) then follows from (5.32) and (5.5).
If, on the other hand, P is not empty, (5.7) results from (4.7), (5.19), (5.31) with
Finally, (5.8)
results from (2.1) and (5.7). 2
For the remaining of this section, we will restrict our attention to the case where
the sequence of iterates converges to a single limit point. Obviously, this makes AS3
unnecessary. We briefly comment at the end of the section on why this additional
assumption cannot be relaxed.
We now show that, if the maximum penalty parameter ff k converges to zero, then
the Lagrange multiplier estimates - k converge to their true values -   .
Lemma 5.4. Assume AS1 and AS2 hold. Assume that fx k g, the sequence of
iterates generated by Algorithm 3.1, converges to the single limit point x   at which
AS6 holds, and with corresponding Lagrange multipliers -   . Then, if ff k tends to zero,
the sequence - k converges to -   .
Proof. Recall that AS6 implies AS4 and therefore that our assumptions are
sufficient to apply Theorem 4.6.
We observe that the desired convergence holds if - k;[Q j ] converges to -
It is thus sufficient to show this latter result for an arbitrary j between 1
and q. The result is obvious if Step 3a is executed infinitely often for the j-th subset.
Indeed, each time this step is executed, -
and the inequality (4.7)
guarantees that -
converges to -  ;[Q j ] . Suppose therefore that Step 3a is not
executed infinitely often for this subset. Then k(- remain fixed for all
executed for each remaining iteration. But
then implies that kc(x k )
As ff k tends to zero and ff
k sufficiently large for which ff k strictly decreases. But then inequality (3.7) must be
satisfied for some k - k 3 , which is impossible, as this would imply that Step 3a is
again executed for the j-th subset. Hence Step 3a must be executed infinitely often.We now consider the behaviour of the maximum penalty parameter ff k and show
the important result that, under stated assumptions, it is bounded away from zero.
The proof of this result is inspired by the technique developed by Conn et al. [5]. When
the single penalty parameter definition of the augmented Lagrangian (1.4) is used (or,
equivalently, when one then avoids a steadily increasing ill-conditioning of the
Hessian of the augmented Lagrangian. Note that this ill-conditioning is also avoided
when q ? 1, as we show below in Theorem 5.6.
Theorem 5.5. Assume AS1 and AS2 hold and suppose that the sequence of
iterates fx k g of Algorithm 3.1 converges to a single limit point x   with corresponding
Lagrange multipliers -   , at which AS5 and AS6 hold. Then there is a constant ff min 2
(0; 1) such that ff
Proof. Suppose otherwise that ff k tends to zero (that is
that - k;j tends to zero for each j between 1 and q. Then Step 3b must be executed
infinitely often for each subset. We aim to obtain a contradiction to this statement by
showing that Step 3a is always executed for each subset for sufficiently large k. We
note that our assumptions are sufficient to apply Theorem 4.6. Furthermore, we may
apply Lemma 5.3 to the complete sequence of iterates.
First observe that
for all k - k 1 , where -
ff and k 1 are those of Lemma 5.3. Note that
for all k - k 1 . This follows by definition if (3.12) is executed. Otherwise it is a
consequence of the fact that ff k is unchanged while ! k is reduced, when (3.13) occurs.
Let k 4 be the smallest integer k such that
and
that (5.33) and (5.35) imply that
5 be such that
for all k - k 5 , which is possible because of Lemma 5.4. Now define k
let \Gamma be the set fk j (3.12) is executed at iteration k \Gamma 1 and k - k 6 g and let k 0 be the
smallest element of \Gamma. By the assumption that ff k tends to zero, \Gamma has an infinite number
of elements.
By definition of \Gamma, for iteration k 0 ,
. Then inequality
(5.6) gives that, for each j,
(from (5.36))
(from (5.33))
(from (5.34)).
As a consequence of this inequality, Step 3a will be executed for each j with - k 0
Inequality (5.5) together with (5.37) guarantee that
We shall now make use of an inductive proof. Assume that, for each j, Step 3a is
executed for iterations and that
Inequalities (5.38) and (5.39) show that this is true for We aim to show that
the same is true for Our assumption that Step 3a is executed gives that, for
iteration
. Then,
inequality (5.6) yields that, for each j,
(from (5.40))
(from (5.36))
Hence Step 3a will again be executed for each j with
Inequality (5.5) then implies that
(from (5.40))
(from (5.35))
which establishes (5.40) for executed for each
all iterations k - k 0 . But this implies that \Gamma is finite, which contradicts the assumption
that Step 3b is executed infinitely often for each subset. Hence the theorem is proved.This theorem was all that was needed in Conn et al. [5]. However, the situation
is more complex here because q may be larger than one. If the ill-conditioning of
the Hessian is to be avoided, we must now prove the stronger result that all penalty
parameters stay bounded away from zero.
Theorem 5.6. Assume AS1 and AS2 hold and suppose that the sequence of
iterates fx k g of Algorithm 3.1 converges to a single limit point x   with corresponding
Lagrange multipliers -   , at which AS5 and AS6 hold. Then there is a constant - ? 0
such that - k;j - for all k and all
Proof. Assume otherwise that Z is not empty, and hence that - k;Z converges
to zero. Then Step 3b must be executed infinitely often for j 2 Z . We aim to obtain
a contradiction to this statement by showing that, for any j 2 Z , Step 3a is always
executed for sufficiently large k. We may deduce from Theorem 5.5 that ff k attains
its minimum value ff min 2 (0; 1) at iteration k max , say. Hence, P 6= ;. Furthermore,
we may apply Lemma 5.3 to the complete sequence of iterates. Let k 7 - k max be the
smallest integer for which
ff and k 1 are those of Lemma 5.3, and where
Note that ff fi j +ffl
Consider the j-th subset, for some j 2 Z . At iteration k - k 7 , the algorithm
ensures that
if Step 3b is executed for the j-th subset, while (5.7) ensures that
if Step 3a is executed for the same subset. Summing on all j 2 Z , and defining
executed for the j-th subset at iteration kg
executed for the j-th subset at iteration kg;
we obtain that
ae
For the purpose of obtaining a contradiction, assume now that
ae k -2
for all k - k 7 . Then (5.42) gives that, for all k - k 7 ,
ae k+1
ae k
because of (5.41). Hence we obtain from (5.44) that
ae
Therefore, since ae k 7 ff (k\Gammak 7 +1)ffl
min tends to zero, we obtain that
ae k+1 !2 ff ff j+(k 7 \Gammak
min ff (k\Gammak 7 +1)fij
for all sufficiently large k, where the last equality results from the definition of k max
and (3.13). But this contradicts (5.43), which implies that (5.43) does not hold for all
sufficiently large. As a consequence, there exists a subsequence K such that
ae k !2
for all k 2 K. Consider such a k. Then, using (5.42) and (5.45), we deduce that
ae
where we have used (5.41) to obtain the second inequality. As a consequence, k+1 2 K
and (5.45) holds for all k sufficiently large. Returning to subset j 2 Z , we now obtain
from (5.8) and (5.45) that
for all k sufficiently large, because of (5.41). Hence Step 3a is executed for the subset
j and for all sufficiently large k, which implies that j does not belong to Z . Therefore
Z is empty and the proof of the theorem is completed. 2
As in Conn et al. [5], we examine the rate of convergence of our algorithms.
Theorem 5.7. Under the assumptions of Theorem 5.6, the iterates x k and the Lagrange
multipliers -
- k of Algorithm 3.1 are at least R-linearly convergent with R-factor
at most ff fi j
min , where ff min is the smallest value of the maximum penalty parameter
generated by the algorithm.
Proof. The proof parallels that of Lemma 5.3. First, Theorem 5.5 shows that
the maximum penalty parameter ff k stays bounded away from zero, and thus remains
fixed at some value ff min ? 0, for k - k max . For all subsequent iterations,
(5.
hold. Moreover, Theorem 5.6 implies that, for all hold for all
sufficiently large. Hence and because of (4.1), the bound on the right-hand
side of (5.25) may be replaced by -
Therefore, if k is sufficiently large that
and
inequalities (5.47)-(5.49) can be rearranged to yield
But then (5.19) gives that
(5.50) show that x k converges to x   at least R-linearly, with R-factor ff fi j
min
. Inequalities
(4.7) and (5.50) then guarantee the same property for -
To conclude this section, we note that the conclusions of Theorems 5.5, 5.6 and 5.7
require that the complete sequence of iterates converges to a unique limit point. As
indicated above, this assumption cannot be relaxed. The counterexample presented
by Conn et al. [5] (where the linear inequality constraints are simple bound constraints
on the problem's variables) shows that the sequence of penalty parameters may indeed
converge to zero, if there is more than a single limit point.
6. Second order conditions. If we further strengthen the stopping test for the
inner iteration beyond (3.3) to include second-order conditions, we can then guarantee
that our algorithms converge to an isolated local solution. More specifically, we require
the following additional assumption.
AS7: Suppose that x k satisfies (3.3), converges to x   for k 2 K, such that Z   has
a rank strictly greater than m. Then, if Z is defined as in AS6, we assume
that Z T r xx \Phi k Z is uniformly positive definite (that is, its smallest eigenvalue
is uniformly bounded away from zero) for all k 2 K sufficiently large.
We can then prove the following result.
Theorem 6.1. Under assumptions AS1-AS3, AS5-AS7, the iterates x k , k 2 K,
generated by Algorithm 3.1 converge to an isolated local solution of (1.1)-(1.3).
Proof. By definition of \Phi,
r xx \Phi
(x) is the Jacobian of c(x) [Q j ] . Note that the rank of Z is at least that of
Z   . AS7 then implies that there exists a nonzero vector s such that
and hence
for each j. For any such vector, AS7 further implies that
for some - 21 ? 0, which in turn gives that
because of (6.1) and (6.2). By continuity of H ' as x k and -
approach their limits,
this ensures that
for all nonzero s satisfying
which implies that x   is an isolated local solution of (1.1)-(1.3) (see, for instance,
Avriel [2, Thm. 3.11]). 2
If we assume that the inner iteration stopping test is tightened so that r xx \Phi k is
required to be uniformly positive definite in the null space of the dominant constraints,
and if we assume that the non-degeneracy condition (5.2) holds, then Corollary 5.2
ensures that Z sufficiently large k and Theorem 6.1 holds. A weaker
version of this result also holds, where only positive semi-definiteness of the augmented
Lagrangian's Hessian is required, yielding then that x   is a (possibly not isolated)
minimizer of the problem.
7. Extensions.
7.1. Flexible Lagrange multiplier updates. The formula (2.1) has definite
advantages for large-scale computations, but may otherwise appear unduly restrictive.
The purpose of the first extension we consider is to introduce more freedom in our
algorithmic framework, by replacing this formula by a more general condition, allowing
a much larger class of Lagrange multiplier updates to be used. More specifically, we
consider modifying Algorithm 3.1 as follows.
Algorithm 7.1
This algorithm is identical to Algorithm 3.1, except that Step 3 is replaced
by the following, where fl is a constant in (0; 1).
Step 3 [Disaggregated updates]. Compute a new vector of Lagrange multiplier
estimates - k+1 . For
or Step 3b otherwise.
Step 3a [Update Lagrange multiplier estimates]. Set
Step 3b [Reduce the penalty parameter]. Set
where - k;j is defined by (3.9) in Algorithm 3.1.
Algorithm 7.1 allows a more flexible choice of the multipliers than Algorithm 3.1,
but requires that some control is enforced to prevent their growth at an unacceptably
fast rate. It covers, among others, the choice of the least-squares estimates -(x) as
defined in (2.5).
The global convergence theory presented in Section 4 for Algorithm 3.1 can be
extended to cover Algorithm 7.1. This extension is detailed in Conn et al. [9]. Conn
et al. [10] extend the local convergence analysis of Section 5 to Algorithm 7.1, under
the additional condition that
holds for some positive constants - 22 and - 23 and all k 2 K sufficiently large, where K
is the index set of a subsequence of iterates (generated by Algorithm 7.1) converging
to the critical point x   with corresponding Lagrange multipliers -   . Both (2.1) and
(2.5) satisfy this condition because of Theorem 4.6.
We also note that Corollary 5.2 ensures that the least-squares multiplier estimates
are implementable when the non-degeneracy condition (5.2) holds. By this we
mean that the estimates
are identical to those defined in (2.5) for all k sufficiently large, and, unlike (2.5), are
well defined when x   is unknown.
7.2. Alternative criticality measures. In Algorithms 3.1 and 7.1 we used the
criticality measure kP T k
in order to define the stopping criterion of the inner
iteration (see (3.3)), because it is general. However, this quantity might not be easily
computed in the course of the numerical method used to calculate x k , especially when
the dimension of the problem is high. It is therefore of interest to examine other
criticality measures that might be easier to calculate. It is the purpose of this section
to analyze such alternative proposals.
Given D k , N k , and AD k
as above, we first claim that (3.3) can be replaced by the
requirement that there exists a set of non-positive "dominant multipliers" f- ik g i2M k
is the jD k j-dimensional vector whose i-th component is - ik if or zero
otherwise. We prove this claim.
Lemma 7.1. Assume that there exists a non-positive - k such that (7.1) holds at
x k . Then (3.3) also holds at x k .
Proof. Since the vector A T
belongs, by construction, to the cone N k defined
in (3.4), we can immediately deduce from the definition of the othogonal projection
and (7.1) that
which is the desired inequality. 2
Condition (7.1) is appealing for two reasons. Firstly, a set of (possibly approx-
imate) multipliers is available in many numerical procedures that might be used to
perform the inner iteration and to compute a suitable x k ; one can then select those
multipliers which correspond to the dominant constraints, further restrict this choice
to the non-positive ones and finally check (7.1). Such a scheme is implicitly used by
both the Harwell [17] barrier-function quadratic programming codes VE14 and VE19
and the IMSL [19] general linearly constrained minimization package LCONG.
Alternatively, suitable multipliers can be computed, for instance by (approxi-
mately) solving the least-squares problem
min
-k
and selecting the non-positive components of the resulting vector -, or by (approxi-
mately) solving the constrained least-squares problem
min
-k:
Condition (7.1) is also appealing as it provides, in a single condition, both a stopping
condition on the inner iteration and a measure of the tolerated "inexactness" in solving
the associated least-squares problem, if this is the procedure chosen to obtain the
dominant multipliers.
We may therefore deduce from Lemma 7.1 that the convergence theory holds for
Algorithms 3.1 and 7.1 whenever (7.1) is used instead of (3.3).
Condition (7.1) can be further specialized. For instance, one might choose to
impose the familiar "reduced gradient" criterion
is an orthogonal matrix whose columns span the null space of the constraints
active at x k , provided that the multipliers associated with these linear constraints
are all non-positive. In this case, we have that
because T the tangent cone to the set determined by the linear inequality
constraints active at x k , contains T k . As a consequence, the convergence theory still
holds when this criterion, which has been implemented by several subroutines for
minimizing a general objective function subject to linear constraints (for example,
the NAG [22], quadratic programming code E04NFF and the more general package
E04UCF), is used as an inner-iteration stopping rule within Algorithms 3.1 and 7.1.
This is also true for reduced gradient methods (e.g. MINOS [21], or LSNNO [24])
which compute a full column rank matrix -
whose columns are generally non-
orthonormal but depend upon a subset of the (finite number) of coefficients for the
linear constraints. Indeed, the norm of -
bounded above and away from
zero, and a relationship that is a weighted form of (7.3) thus also holds in these cases.
In order to preserve coherence with the framework presented in Conn et al. [8],
we finally note that oe k as defined in (4.3) may also be viewed as a criticality measure.
Hence we might decide to stop the inner iteration when
The reader is referred to Conn et al. [9] for a proof that global convergence is still obtained
for this modification of Algorithms 3.1 and 7.1. However, the authors have not
been able to prove the desired local convergence properties with only (7.4). Instead,
the local convergence theory is covered for Algorithms 3.1 and 7.1 for the stronger
condition
(see Conn et al. [10] for details). This condition is theoretically interesting, but might
be practically too strong. Note, as we now show, that it implies a variant of (3.3).
Theorem 7.2. Assume that fx k g, k 2 K, is a convergent subsequence of vectors
of B such that (7.5) holds for each k 2 K, where the ! k converge to zero as k increases
in K. Then the inequality
also holds for each k 2 K sufficiently large and for some - 24 - 1.
Proof. We first consider the simple case where that is when no linear
inequality is present. In this case, it is easy to check from (4.3) that oe
But we must have that D
(\Gammar x \Phi k )k. We therefore obtain that
holds with - large enough to ensure that ! k - 1.
Assume now that p ? 0. The Moreau decomposition of \Gammar x \Phi k [20] is given by
obviously holds for any choice of - 24 . Assume
therefore that P T k
nonzero. We now show that x k B, where we
define
kAk1
Assume first that i 2 D k . Then \Gammaa i 2 N k and a T
because of the polarity of N k
and T k . Since x k 2 B, we obtain that
a T
On the other hand, if i 62 D k , we have that a T
(a T
Gathering (7.8) and (7.9), we obtain that x k B, as desired. Furthermore,
since kd k k - 1 by definition, we have verified that d k is feasible for the minimization
problem (4.3) associated with the definition of oe k . Hence,
where we have used successively the Moreau decomposition of \Gammar x \Phi k , the definition
of d k and the orthogonality of the terms in the Moreau decomposition. If ffl
(7.5) and (7.10) imply that
sufficiently large. Otherwise, we deduce from (7.10), (7.5) and (7.7) that
As a consequence of (7.11) and (7.12), we therefore obtain that (7.6) holds with
Combining all cases, we conclude that (7.6) holds with this last value of - 24 . 2
We finally note that Lemma 7.1 and Theorem 7.2 do not depend on the actual
form of the augmented Lagrangian (1.5), but are valid independently of the function
minimized in the inner iteration. This observation could be useful if alternative
techniques for augmenting the Lagrangian are considered for a merit function.
8. Conclusion. We have considered a class of augmented Lagrangian algorithms
for constrained nonlinear optimization, where the linear constraints present in the
problem are handled directly and where multiple penalty parameters are allowed.
The algorithms in this class have the advantage that efficient techniques for handling
linear constraints may be used at the inner iteration level, and also that the sparsity
pattern of the Hessian of the augmented Lagrangian is independent of that of the
linear constraints. The global and local convergence results available for the specific
case where linear constraints reduce to simple bounds have been extended to the more
general and useful context where any form of linear constraint is permitted.
We finally note that the theory presented is directly relevant to practical compu-
tation, as the inner iteration stopping rule (3.3) covers the type of optimality tests
used in available packages for linearly constrained problems. This means that these
packages can be applied to obtain an (approximate) solution of the subproblem, and
constitutes a realistic and attractive algorithmic development.
It is now the authors' intention to perform extensive numerical experiments on
large-scale problems. This development requires considerable care and sophistication
if an efficient solver for the subproblem is to be integrated with the class of algorithms
described here.

Acknowledgements

. The authors wish to acknowledge funding provided by a
NATO travel grant. They are also grateful to J. Nocedal and the anonymous referees
for their constructive comments.



--R

Computing a search direction for large-scale linearly constrained nonlinear optimization calculations
Nonlinear Programming: Analysis and Methods.
Constrained Optimization and Lagrange Multiplier Methods.
Convergence properties of trust region methods for linear and convex constraints.
A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds.
LANCELOT: a Fortran package for large-scale nonlinear optimization (Release
On the number of inner iterations per outer iteration of a globally convergent algorithm for optimization with general nonlinear equality constraints and simple bounds.
Global convergence of a class of trust region algorithms for optimization using inexact projections on convex constraints.
Global convergence of two augmented Lagrangian algorithms for optimization with a combination of general equality and linear constraints.
Local convergence properties of two augmented Lagrangian algorithms for optimization with a combination of general equality and linear constraints.
On the convergence of projected gradient processes to singular critical points.
Introduction to sensitivity and stability analysis in nonlinear programming.
Practical Methods of Optimization.
Newton methods for large-scale linear equality-constrained minimization
On the convergence of a sequential penalty function method for constrained minimization.
Algorithmic Methods in Optimal Control.
A catalogue of subroutines (release 11).
Multiplier and gradient methods.

D'ecomposition orthogonale d'un espace hilbertien selon deux c-ones mutuellement polaires

Mark 16.
A method for nonlinear constraints in minimization problems.
LSNNO: a Fortran subroutine for solving large scale nonlinear network optimization problems.
Indefinite systems for interior point methods.
--TR
constrained optimization;augmented Lagrangian methods;convergence theory;linear constraints