On the Convergence Theory of Trust-Region-Based Algorithms for Equality-Constrained Optimization.
In a recent paper, Dennis, El-Alem, and Maciel proved global convergence to a stationary point for a general trust-region-based algorithm for equality-constrained optimization. This general algorithm is based on appropriate choices of trust-region subproblems and seems particularly suitable for large problems.This paper shows global convergence to a point satisfying the second-order necessary optimality conditions for the same general trust-region-based algorithm. The results given here can be seen as a generalization of the convergence results for trust-regions methods for unconstrained optimization obtained by Mor and Sorensen. The behavior of the trust radius and the local rate of convergence are analyzed. Some interesting facts concerning the trust-region subproblem for the linearized constraints, the quasi-normal component of the step, and the hard case are presented.It is shown how these results can be applied to a class of discretized optimal control problems.
Introduction
. Trust-region algorithms have been proved to be efficient and
robust techniques to solve unconstrained optimization problems. An excellent survey
in this area is Mor'e [22]. Other classical references for convergence results are Carter
[3], Mor'e and Sorensen [23], Powell [26], and Shultz, Schnabel, and Byrd [29]. The
standard techniques to handle the trust-region subproblems are the dogleg algorithm
(Powell [25]), conjugate gradients (Steihaug [32] and Toint [33]), and Newton-like
methods for the computation of locally constrained optimal steps (Gay [15], Mor'e
and Sorensen [23], and Sorensen [30]). See also the book of Dennis and Schnabel [9].
Recent new algorithms to compute a locally constrained optimal step (in other words a
step that satisfies a fraction of optimal decrease on the trust-region subproblem) that
are very promising for large problems have been proposed by Rendl and Wolkowicz
[28] and Sorensen [31].
Since the mid eighties a significant effort has been made to address the equality-
constrained optimization problem. References are Celis, Dennis, and Tapia [4], Vardi
[34] (see also El-Hallabi [14]), Byrd, Schnabel, and Shultz [2], Powell and Yuan [27],
and El-Alem [13]. The fundamental questions associated with the application of trust-region
algorithms to equality-constrained optimization are the decomposition of the
step, the choice of the trust-region subproblems, and the choice of the merit function.
During the first stages of the research conducted in this area it was not clear how to
answer these questions properly. However, if we examine carefully the most recent
Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005-
USA. E-Mail: dennis@rice.edu. Support of this author has been provided by DOE contract
DOE-FG03-93ER25178, NSF cooperative agreement CCR-9120008, and AFOSR contract F49620-
9310212.
y Departamento de Matem'atica, Universidade de Coimbra, 3000 Coimbra, Portugal. This work
was developed while the author was a graduate student at the Department of Computational and
Applied Mathematics of Rice University. E-Mail: lvicente@mat.uc.pt. Support of this author has
been provided by INVOTAN (NATO scholarship), CCLA (Fulbright scholarship), FLAD, and NSF
cooperative agreement CCR-9120008.
references (Byrd and Omojokon [24], Dennis, El-Alem, and Maciel [7], El-Alem [12],
[13], and Lalee, Nocedal, and Plantenga [21]) we can observe the same decomposition
of the step (in its normal, or quasi-normal, and tangential components) and the same
trust-region subproblems (the trust-region subproblem for the linearized constraints
and the trust-region subproblem for the Lagrangian reduced to the tangent subspace).
This is explained in great detail in Section 2 of this paper. As in the unconstrained
case, the conditions that each component has to satisfy and the way they are computed
might of course differ from algorithm to algorithm. We can see also in these most
recent references that the merit function used is either the ' 2 penalty function without
constraint term squared (cases of [21], [24]) or the augmented Lagrangian function (in
Consider now the equality-constrained optimization (ECO) problem
minimize f(x)
subject to
n. The functions f and c i , are assumed to be at least twice
continuously differentiable in the domain of interest.
In [7], Dennis, El-Alem, and Maciel have considered a general trust-region-based
algorithm for the solution of the ECO problem (1.1). This general algorithm is very
much like the algorithm proposed by Byrd and Omojokon [24] 1 . As mentioned before,
each step s is decomposed as s n is the quasi-normal component of
the step, associated with trust-region subproblem for the linearized constraints and
s t is the tangential component, associated with the trust-region subproblem for the
Lagrangian reduced to the tangent subspace. Each component of the step is only
required to satisfy a fraction of Cauchy decrease on the corresponding trust-region
subproblem. Another key feature of this general algorithm is the choice of the augmented
Lagrangian as a merit function and the use of the El-Alem's scheme [11] to
update the penalty parameter. Under appropriate assumptions, it can be shown that
there exists a subsequence of iterates driving to zero the norm of the residual of the
constraints and the norm of the gradient of the Lagrangian reduced to the tangent sub-space
(see [7][Section 8]). It is important to remark that this global convergence result
is obtained under very mild conditions on the components of the step, on the multipliers
estimates, and on the Hessian approximations. Thus, the Dennis, El-Alem, and
Maciel [7] result is similar to the global result given by Powell [26] for unconstrained
optimization.
One of the purposes of this paper is to show global convergence to a point satisfying
the second-order necessary optimality conditions for this class of algorithms.
Our result is similar to the results established by Mor'e and Sorensen [23], [30] for
trust-region algorithms for unconstrained optimization. We accomplish this here by
imposing a fraction of optimal decrease on the tangential component s t of the step,
by using exact second-order information, and by imposing conditions on the quasi-
normal component s n and on the Lagrange multipliers.
1 The Thesis [24] was directed by Professor R. H. Byrd. The trust-region algorithm proposed here
is usually referred as the Byrd and Omojokon algorithm.
In [2], Byrd, Schnabel, and Shultz have proposed a trust-region algorithm for
equality-constrained optimization and established global convergence to a point satisfying
the second-order necessary optimality conditions. However this algorithm does
not belong to the class of trust-region algorithms considered here and their result is
obtained with the use of the (exact) normal component and the least-squares multipliers
update which we do not require in this paper. Other differences are that they use
the ' 1 penalty function as the merit function and the analysis is carried out by using
an orthogonal null-space basis. In recent papers, Coleman and Yuan [6] and El-Alem
[12] have proposed trust-region algorithms for which they prove global convergence to
points satisfying first-order and second-order necessary optimality conditions. Their
algorithms use the (exact) normal component, an orthogonal null-space basis, and the
least-squares multipliers update.
The conditions we need to impose to assure that a limit point of the sequence of
iterates satisfies the second-order necessary optimality conditions are
k is the quasi-normal component of the step s k , and
k is the trust-region radius. In the case where kC(x k )k is small compared with
the first condition implies that any increase of the quadratic model of the Lagrangian
from x k to x k +s n
k is O(ffi 2
To see why this is relevant recall that a fraction of optimal
decrease is being imposed on the tangential component s t
k yielding a decrease of O(ffi 2
on the quadratic model. The second condition is needed for the same reasons because
appears in the definition of predicted decrease. We show that both conditions
are satisfied when either (i) the (exact) normal component and the least-squares
multipliers are used; or (ii) the most reasonable choices of quasi-normal component
and multipliers are made for a class of discretized optimal control problems. The
former result is in agreement with the result obtained by El-Alem [12].
Gill, Murray, and Wright [17] and El-Alem [10] considered in their analyses that
k). In the latter work this assumption is used to prove local convergence
results, and in the former to establish properties of an augmented Lagrangian
merit function. We point out that this assumption implies that r x '(x
k is
since s k is O(ffi k ) and we assume that s n
k is O(kC(x k )k).
We also prove that if the algorithm converges to a point where the reduced Hessian
is positive definite, then the penalty parameter ae k is uniformly bounded and the
trust-region radius ffi k is uniformly bounded away from zero, a desired property of a
trust-region algorithm. In this case, particular choices of the multipliers and of the
components s n and s t lead us to a q-quadratic rate of convergence in x.
A detailed treatment of the global convergence theory is given in Vicente [35].
The structure of the trust-region subproblem for the linearized constraints can be
exploited to obtain some interesting results. We introduce a quasi-normal component
that satisfies a fraction of optimal decrease on the trust-region subproblem for the linearized
constraints. We show that the (exact) normal component shares this property.
We also prove that if the algorithm is well behaved (for instance if the trust radius is
uniformly bounded away from zero), then this subproblem has a natural tendency to
fall into the so-called hard case.
We review the notation used in this paper. The Lagrangian function associated
with the ECO problem (1.1) is defined by '(x;
is the Lagrange multiplier vector. The matrix rC(x) is given by
, where rc i (x) represents the gradient of the function c i (x). Let
be the Hessian matrices of f(x) and c i (x) respectively. We use
subscripted indices to represent the evaluation of a function at a particular point of
the sequences fx k g and f k g. For instance, f k represents f(x k ) and ' k is the same
as The vector and matrix norms used are the ' 2 norms, and I l represents
the identity matrix of order l. Finally,  1 (A) denotes the smallest eigenvalue of the
symmetric matrix A.
The structure of this paper is as follows. In Section 2, we introduce the trust-region
subproblems and outline the general trust-region algorithm and the general
assumptions. In Section 3, we present the global convergence theory. A class of
discretized optimal control problems is introduced in Section 4 as a justification for
the general form of our algorithms and theory. In Sections 5 and 6, we analyze
respectively the behavior of the trust radius and the local rates of convergence. The
trust-region subproblem for the linearized constraints is studied in Section 7. We end
this paper with some summary conclusions.
2. Algorithm and general assumptions. The trust-region algorithm analyzed
by Dennis, El-Alem, and Maciel [7] for the solution of the ECO problem (1.1),
consists of computing, at each iteration k, a step s k decomposed as s
the components s n
k and s t
are required to satisfy given conditions. If the step s k is
accepted, the algorithm continues by setting x k+1 to x . If the step is rejected
then x
2.1. Decomposition of the step. Suppose that kC k k 6= 0. The component
k is called the quasi-normal (or quasi-vertical) component of s k and is required to
satisfy a fraction of Cauchy decrease on the trust-region subproblem for the linearized
constraints defined by
subject to ks n k
where r 2 (0; 1) and ffi k is the trust radius. In other words, s n
k has to satisfy
k is the so-called Cauchy point for this trust-region subproblem,
i.e. c n
k is the optimal solution of
subject to c n 2 spanf\GammarC k C k
and therefore
The component s n
k also is required to satisfy the condition
ks n
where  1 is a positive constant independent of the iterate k of the algorithm. This
condition is saying that close to feasibility the quasi-normal component has to be
small.
In this paper, we require the quasi-normal component s n
k also to satisfy
where  2 is a positive constant independent of the iterates. The important consequence
of this condition is that if kC k k is small compared with ffi k , then any increase of the
quadratic model of the Lagrangian along the quasi-normal component s n
k is of O(ffi 2
The two choices of s n
k given in Sections 4.1 and 4.2 satisfy conditions (2.1), (2.2),
and (2.3). Other choices have been suggested in [7], [20].
The component s t
k is the tangential (or horizontal) component, and it must satisfy
i.e. it must lie in the null space N (rC T
k ) of rC T
k . Let W k be an n \Theta (n \Gamma m) matrix
whose columns form a basis for N (rC T
be a quadratic model of ' at is an approximation to r 2
Since for any s t 2 N (rC T
k ), there exists a  s t 2 IR n\Gammam such that s
consider also
which is given by
with
If kg k k 6= 0,  s t
k is required to satisfy a fraction of Cauchy decrease for the trust-region
subproblem
minimize
subject to ks n
Note that this is not a standard trust-region subproblem because s n
k might not be
orthogonal to N (rC T
might not be the center of the trust region.
The steepest-descent direction at
associated with
in the ' 2 norm is \Gamma  g k .
If we take into account the scaling matrix W k , then the steepest-descent direction
in the kW k \Delta k norm is given by \Gamma(W T
k . We consider the steepest-descent
direction \Gamma  g k for
ks n
and require
k to satisfy
where  oe t ? 0, and
k is the Cauchy point for the ' 2 norm given by
with
ks n
This is equivalent to saying that  max is the maximum step length along s n
allowed inside the trust region defined by ffi k . It is easy to verify that
The results given in this paper hold also if c t
k is defined along \Gamma(W T
provided the sequence fk(W T
are valid also if the coupled
trust-region constraint ks n
is decoupled as ks t k  ffi k . In this latter case
the parameter r defining the quasi-normal component s n
k can have any positive value.
A step
k that satisfies this requirement can be computed by using Powell's dogleg
algorithm [25] or by the conjugate-gradient algorithm adapted for trust regions by
Steihaug [32] and Toint [33] (see also [7], [8], [21]).
In order to establish global convergence to a point satisfying the second-order
necessary optimality conditions, we need
k to satisfy a fraction of optimal decrease
on the following trust-region subproblem
minimize
subject to kW k
where
In other words, we require
k to satisfy the following conditions:
s
k is the optimal solution of the trust-region subproblem (2.5).
This can be accomplished by applying the GQTPAR routine of Mor'e and Sorensen
[23] or by using the algorithms recently proposed by Rendl and Wolkowicz [28] and
Sorensen [31].
If  s t
k satisfies a fraction of optimal decrease on the trust-region subproblem (2.5),
then
ks k k  ks n
If
k is only required to satisfy a fraction of Cauchy decrease, then ks k ks n
. We can combine both cases and write
ks ks n
It is also important to note that the definition of ~
assures that the fraction of
optimal decrease (2.6) implies the fraction of Cauchy decrease (2.4) provided
2.2. General trust-region algorithm. We introduce now the merit function
and the corresponding actual and predicted decreases. The merit function used is the
augmented Lagrangian
where ae is the penalty parameter. The actual decrease ared(s k ; ae k ) at the iteration k
is given by
The predicted decrease (see [7]) is the following:
pred(s
To update the penalty parameter ae k we use the scheme proposed by El-Alem [11].
The Lagrange multipliers  k are required to satisfy
where  3 is a positive constant independent of k. This condition is not necessary for
global convergence to a stationary point.
The general trust-region algorithm is given below.
Algorithm 2.1 (General trust-region algorithm).
and r such that
ae ? 0, and r 2 (0; 1).
do
2.1 If kC
is given in (2.10), stop the
algorithm and use x k as a solution for the ECO problem (1.1).
2.2 Set s n
satisfying (2.1), (2.2), (2.3), and ks n
If kW T
satisfying (2.6).
k .
2.3 Compute  k+1 satisfying (2.8).
2.4 Compute pred(s
If pred(s
then set ae
Otherwise set
ae:
2.5 If ared(s k ;ae k )
pred(s k ;ae k )
ks k k and reject s k .
Otherwise accept s k and choose ffi k+1 such that
2.6 If s k was rejected set x . Otherwise set x
It is important to understand that the role of ffi min is just to reset ffi k after a step
s k has been accepted. During the course of finding such a step the trust radius can be
decreased below ffi min . To our knowledge Zhang, Kim, and Lasdon [37] were the first
to suggest this modification. We remark that the rules to update the trust radius in
the previous algorithm can be much more complicated but those given suffice to prove
convergence results and to understand the trust-region mechanism.
As a direct consequence of the way the penalty parameter is updated, we have
the following result.
Lemma 2.1. The sequence fae k g satisfies
ae k  ae
pred(s
In order to establish global convergence results, we use the general assumptions
given in [7]. These are Assumptions A.1-A.4. However for global convergence to a
point that satisfies the second-order necessary optimality conditions, we also need
Assumption A.5. We assume that for all iterations k, x k and x are in \Omega\Gamma where
\Omega is an open subset of IR n .
General assumptions
A.1 The functions f , c i , are twice continuously differentiable in \Omega\Gamma
A.2 The gradient matrix rC(x) has full column rank for all x 2 \Omega\Gamma
A.3 The functions f , rf , r are bounded in \Omega\Gamma
The matrix (rC(x) T rC(x)) \Gamma1 is uniformly bounded in \Omega\Gamma
A.4 The sequences fW k g, fH k g, and f k g are bounded.
A.5 The Hessian approximation H k is exact, i.e. H
are Lipschitz continuous in \Omega\Gamma
Assumptions A.3 and A.4 are equivalent to the existence of positive constants
9 such that jf(x)j   0 , krf(x)k   1 , kr 2 f(x)k   2 , kC(x)k   3 ,
2.3. Predicted decrease along the tangential component. Consider again
the trust-region subproblem (2.5). We can use the general assumptions and the
structure of this subproblem to obtain a lower bound on the predicted decrease
along the tangential component of the step.
It follows from the Karush-Kuhn-Tucker conditions that there exists a fl k  0
such that
positive semi-definite,
s
~
s
0:
(It turns out that these conditions are also sufficient for
s
k to solve the trust-region
subproblem (2.5), see Gay [15] and Sorensen [30].) As a consequence of this we can
s
where
Hence we have
3. Global convergence. Dennis, El-Alem, and Maciel [7] have proved under
Assumptions A.1-A.4 and conditions (2.1), (2.2), and (2.4) that
lim inf
0:
In this section we assume that  s t
k satisfies the fraction of optimal decrease (2.6)
on the trust-region subproblem (2.5), as well as conditions (2.3), (2.8), and A.5 on
respectively, and show that (3.1) can be extended to
0:
The proof of (3.2) although simpler has the same structure as the proof given in [7].
We prove the result by contradiction, under the supposition that
for all k. We start by analyzing the fraction of Cauchy and optimal decrease conditions.
Lemma 3.1. Let the general assumptions hold. Then
and
and, moreover, since  s t
k satisfies a fraction of optimal decrease for the trust-region
subproblem (2.5),
are positive constants independent of the iterate k.
Proof. The conditions (3.4) and (3.5) are an application of Powell's result (see
[26, Theorem 4], [22, Lemma 4.8]) followed by the general assumptions. The condition
(3.6) is a restatement of (2.11) with
The following inequality is needed in the forthcoming lemmas.
Lemma 3.2. If the general assumptions hold, then
positive constant independent of k.
Proof. The term q k
k ) can be bounded using (2.2), (2.3), and Assumption
A.4, in the following way:
ks n
On the other hand, it follows from (2.8) and krC T
that
If we combine these two bounds we get (3.7) with
The following technical lemma gives us upper bounds on the difference between
the actual decrease and the predicted decrease. The proof follows similar arguments
as the proof of Lemma 6.3 in [11].
Lemma 3.3. Let the general assumptions hold. There exist positive constants
independent of k, such that
ks k k 3
ks k
ae k
3 ks k k 3 ks k k 2
and
ks k
ae k
6 ks k k 3 ks k k 2
Proof. If we add and subtract '(x
for some  1
1). Again using the Taylor expansion we can write
1). Now we expand c i
This and the
general assumptions give us the estimate (3.8) for some positive constants
The inequality (3.9) follows from (3.8) and ae k  1.
The following three lemmas bound the predicted decrease. They correspond respectively
to Lemmas 7.6, 7.7, and 7.8 given in [7].
Lemma 3.4. Let the general assumptions hold. Then the predicted decrease in the
merit function satisfies
pred(s
(3.
and also
pred(s
for any ae ? 0.
Proof. The two conditions (3.10) and (3.11) follow from a direct application of
(3.7) and from the two different lower bounds (3.5) and (3.6) on q k (s n
Lemma 3.5. Let the general assumptions hold, and assume that kW T
ff  min
ae ffl tol
min
ae  7 ffl tol
oe
9 ffl tol
oe
then the predicted decrease in the merit function satisfies either
pred(s
or
pred(s
for any ae ? 0.
Proof. From kW T
and the first bound on ff given by
(3.12), we get
Thus either kW T
us first assume that kW T
ffl tol . Then it follows from the second bound on ff given by (3.12) that
Using this, (3.10), and the third bound on ff given by (3.12), we obtain
pred(s
Now suppose that To establish (3.14), we combine (3.11) and the last
bound on ff given by (3.12) and get
pred(s
We can set ae to ae k\Gamma1 in Lemma 3.5 and conclude that, if kW T
ffl tol and kC k k  ffffi k , then the penalty parameter at the current iterate does not need
to be increased. See Step 2.4 of Algorithm 2.1.
The proof of the next lemma follows the argument given in the proof of Lemma
3.5 to show that either kg k k ? 1ffl tol or fl k ? 1ffl tol holds.
Lemma 3.6. Let the general assumptions hold, and assume that kW T
(3.12), then there exists a constant
pred(s
Proof. By Lemma 3.5 we know that either (3.13) or (3.14) holds. Now we set
. In the first case we use kg
pred(s
In the second case we use
pred(s
Hence (3.15) holds with
ae  6 ffl tol
min
ae  7 ffl tol
oe
9 ffl toloe
Next we prove under the supposition (3.3), that the penalty parameter ae k is
bounded.
Lemma 3.7. Let the general assumptions hold. If kW T
for all k, then
ae k  ae   ;
where ae   does not depend on k, and thus fae k g and fL k g are bounded sequences.
Proof. If ae k is increased at iteration k, then it is updated according to the rule
ae:
We can write
ae ki
By applying (3.4) to the left hand side and (3.5) and (3.7) to the right hand side, we
obtain
aei
If ae k is increased at iteration k, then from Lemma 3.5 we certainly know that kC k k ?
Now we use this fact to establish that
We have proved that fae k g is bounded. From this and the general assumptions we
conclude that fL k g is also bounded.
We can prove also under the supposition (3.3), that the trust radius is bounded
away from zero.
Lemma 3.8. Let the general assumptions hold. If kW T
for all k, then
where does not depend on k.
Proof. If s k\Gamma1 was an acceptable step, then ffi k  ffi min . If not then ks
and we consider the cases kC
(3.12). In both cases we use the fact
ared(s
pred(s
Case I. kC From Lemma 3.6, inequality (3.15) holds for
Thus we can use ks
ared(s
pred(s
)ks
Thus ks
Case II. kC . In this case from (2.9) and (3.4) with
pred(s
where rg. Again we use ae
and this time the last two lower bounds on pred(s
pred(s
ks
ae
ks
ae
ks
Hence ks
The result follows by setting ffi  g.
The next result is needed also for the forthcoming Theorem 3.1.
Lemma 3.9. Let the general assumptions hold. If kW T
for all k, then an acceptable step is always found in finitely many trial steps.
Proof. Let us prove the assertion by contradiction. Assume that for a given  k,
k. This means that lim k!+1 all steps are rejected
after iteration  k. See Steps 2.5 and 2.6 of Algorithm 2.1. We can consider the cases
and appeal to arguments similar
to those used in Lemma 3.8 to conclude that in any case
pred(s
where  15 is a positive constant independent of the iterates. Since we are assuming
that lim k!+1
ared(s k ;ae k )
pred(s k ;ae k )
1 and this contradicts the rules
that update the trust radius. See Step 2.5 of Algorithm 2.1.
Now we finally can state our first asymptotic result.
Theorem 3.1. Under the general assumptions, the sequence of iterates fx k g
generated by the Algorithm 2.1 satisfies
lim inf
0:
Proof. Suppose that there exists an ffl tol ? 0 such that kW T
for all k.
At each iteration k either kC k k  ffffi k or kC k k ? ffffi k , where ff satisfies (3.12). In
the first case we appeal to Lemmas 3.6 and 3.8 and obtain
pred(s
we have from ae k  1, (2.9), (3.4), and Lemma 3.8, that
pred(s
Hence there exists a positive constant  16 not depending on k such that pred(s k
From Lemma 3.9, we can ignore the rejected steps and work only with successful
iterates. So, without loss of generality, we have
Now, if we let k go to infinity, this contradicts the boundedness of fL k g.
From this result we can state our global convergence result: existence of a limit
point of the sequence of iterates generated by the algorithm satisfying the second-order
necessary optimality conditions. This result generalizes those obtained for unconstrained
optimization by Sorensen [30] and Mor'e and Sorensen [23].
Theorem 3.2. Let the general assumptions hold. Assume that W (x) and (x)
are continuous functions and
If fx k g is a bounded sequence generated by Algorithm 2.1, then there exists a limit
point x   such that
positive semi-definite on N (rC(x   ) T ).
Moreover, if (x   ) is such that r x '(x   ; (x   satisfies the second-order
necessary optimality conditions.
Proof. Let fk i g be the index subsequence considered in (3.16). Since fx k i g is
bounded, it has a subsequence fx k j g that converges to a point x   and for which
lim
0:
Now from this and the continuity of C(x), we get C(x   we use the
continuity of W (x) and rf(x) to obtain
Since  1 (\Delta) is a continuous function, we can use (2.10), lim j!+1 the
continuity of W (x), (x), and of the second derivatives of f(x) and c i (x),
to obtain
0:
This shows that r 2
positive semi-definite on N (rC(x   ) T ).
The continuity of an orthogonal null space basis has been discussed in [1], [5], [16].
A class of nonorthogonal null space basis is described in Section 4.1.
The equation r x '(x   ; (x   consistent updates of the Lagrange
multipliers like the least-squares update (4.7) or the adjoint update (4.3).
4. Examples.
4.1. A class of discretized optimal control problems. We now introduce an
important class of ECO problems where we can find convenient matrices W k , quasi-
normal components s n
k , and multipliers  k satisfying all the requirements needed for
our analysis. The numerical solution of many discretized optimal control problems
involves solving the ECO problem
subject to C(y;
y
(see [8], [19], [20]). The variables in y are
the state variables and the variables in u are the control variables. Other applications
include parameter identification, inverse, and flow problems and design optimization.
In many situations there are bounds on the control variables, but this is not considered
here. Another interesting aspect of these problems is that rC(x) T can be partitioned
as
where C y (x) is a square matrix of order m.
In this class of problems the following assumption traditionally is made:
The partial Jacobian C y (x) is nonsingular and its inverse is uniformly
bounded in \Omega\Gamma
As a consequence of this, the columns of
\GammaC
I n\Gammam
form a basis for the null space of rC(x) T .
The usual choice for  k in these problems is the so-called adjoint multipliers
It follows directly from the continuity of rC(x) and the uniformly boundedness of
continuously with x. Furthermore
is a continuous function of x with bounded derivatives.
Using the structure of the problem we can define the quasi-normal component s n
(see references [8], [19], [20]) as
where
kCy
As we will see in Section 7, the quasi-normal component (4.4) satisfies a fraction of optimal
decrease and hence a fraction of Cauchy decrease on the trust-region subproblem
for the linearized constraints.
Other choices for quasi-normal components are given in [20]. All these quasi-
normal components are of the form
Lemma 4.1. If s n
verifies (4.5) and  k is given by (4.3), then conditions (2.3)
and (2.8) are satisfied.
Proof. From (4.3) and (4.5) we can see that
/r
and condition (2.3) is trivially satisfied. Condition (2.8) follows from the existence of
bounded derivatives for
4.2. The normal component and the least-squares multipliers. Consider
again the general ECO problem (1.1). If the component s n
k of the step s k is orthogonal
to the null space of rC T
k , then it is a multiple of rC k (rC T
. If we also
require that s n
lies inside the trust region of radius rffi k , then it is given by
. If the quasi-normal component s n
k of the step is
given by (4.6), then it is called normal. As we will see in the Section 7, the normal
component (4.6) satisfies a fraction of optimal decrease and hence a fraction of Cauchy
decrease on the trust-region subproblem for the linearized constraints.
Lemma 4.2. The quasi-normal component (4.6) and the least-squares update
satisfy conditions (2.3) and (2.8).
Proof. It can be easily confirmed that r x ' T
The condition (2.8) holds
since bounded derivatives in \Omega\Gamma
5. The behavior of the trust radius. In Sections 5 and 6 we no longer need
to consider that the tangential component  s t
k satisfies a fraction of optimal decrease
on the trust-region subproblem (2.5). It suffices to assume the fraction of Cauchy
decrease condition (2.4). We assume that the component s n
k satisfies conditions (2.1)
and (2.2).
We need to strengthen conditions (2.3) and (2.8) in the following way:
ks k k;
ks k k;
ks n
ks k k;
3 , and  0
4 are positive constants independent of the iterates. The choices
of s n
k and  k suggested in Section 4 satisfy these requirements as well. See Lemmas
4.1 and 4.2 for the first two conditions. It is obvious that the normal component (4.6)
satisfy (5.3). The quasi-normal component (4.4) also satisfies (5.3) (see [35][Lemma
5.6.1]).
The next theorems show that if lim k!+1 x
positive
definite on N (rC(x   ) T ), then the penalty parameter ae k is uniformly bounded and
the trust radius ffi k is uniformly bounded away from zero.
Theorem 5.1. Let the general assumptions hold and W (x) and (x) be continu-
ous. If fx k g converges to x   and r 2
positive definite on N (rC(x
then fae k g is a bounded sequence.
Proof. First since r 2
positive definite on N (rC(x
are continuous functions of x, there exists a
neighborhood N (x   ) of x   and a  fl ? 0 such that for any x in N (x   ),
xx '(x; (x))W (x)
fl:
Since
ks t
Thus for all k such that x k 2 N (x   ) we
flks t
ks t
and this implies
ks t
Now by using (3.5) and (5.4), we have for all k such that x k 2 N (x   ), that
17 ks t
where
1+r
g.
Now let kC k k  ff 0 ks k k where the positive constant ff 0 is defined later. Using
similar arguments as in Lemma 3.2, it follows from (2.2), (5.1), (5.2), kC k k  ff 0 ks k k,
and Assumption A.4 that
ks k k;
3 .
From (2.2) and kC k k  ff 0 ks k k we also get
ks
ks n
ks t
2ks n
ks
which together with (5.5) and (5.6) implies
pred(s ks
ks
ks k k
for all ae ? 0. We now need to impose the following condition on ff
Now we set ae = ae k\Gamma1 in (5.7) and conclude that the penalty parameter does not
need to be increased if kC k k  ff 0 ks k k (see Step 2.4 of Algorithm 2.1). Hence, if ae k is
increased then kC ks k k holds, and by using (5.1)-(5.3) we obtain:
ks k k;
with  00
3 . Recall from the proof of Lemma 3.7 that if ae k is
increased then
ae
r
ks k k
oe
ae 4 )ks k k kC k k;
which in turn implies
ae
r
ae k   00
ae 4
This completes the proof of the Theorem.
Theorem 5.2. Let the general assumptions hold and W (x) and (x) be continu-
ous. If fx k g converges to x   and r 2
positive definite on N (rC(x
then ffi k is uniformly bounded away from zero and eventually all iterations are successful

Proof. The proof of the theorem is based on the boundedness of fae k g. We consider
the cases kC ks k k and kC k k  ff 0 ks k k, where ff 0 satisfies (5.8).
ks k k, then from (2.7), (2.9), and (3.4), we find that
pred(s
ks
where
g. In this case it follows from (3.9), (5.10), and ae k  1
that
pred(s
ks
Now, suppose that kC k k  ff 0 ks k k. From (5.7) with
pred(s
ks k
Now we use (3.9) and ae k  ae   to get
pred(s
ks
It follows from Theorem 8.4 in [7] that
lim inf
0:
From this result, the continuity of C(x), and the convergence of fx k g we obtain
Finally from (5.11), (5.12), and the limits lim k!+1 x
finally get
lim
pred(s
which by the rules for updating the trust radius in Step 2.5 of Algorithm 2.1 shows
that ffi k is uniformly bounded away from zero.
6. Local rate of convergence. In order to obtain q-quadratic local rates of
convergence, we require the reduced tangential component  s t
k to satisfy (2.4) and the
following
if
H k is positive definite and k
6.1. Discretized optimal control formulation. Consider again problem (4.1)
and assume that this problem has the structure described in Section 4.1. We can now
use Theorem 5.2 to obtain a local rate of convergence.
Theorem 6.1. Suppose that the ECO problem is of the form (4.1). Let the
general assumptions and assumption (4.2) hold and assume that fx k g converges to x   .
In addition to this, let  s t
k , and  k be given by (6.1), (4.4) and (4.3).
If r 2
xx '(x   ;    ) is positive definite on N (rC(x
then x k converges q-quadratically to x   .
Proof. It can be shown by appealing to Theorem 8.4 in [7] that r x '(x   ;
It follows from Theorem 5.2 that ffi k is uniformly bounded away from zero. Thus
there exists a positive integer  k such that for all k   k,
\GammaC y
. Now the rate of convergence follows from [19].
6.2. Normal component and least-squares multipliers. Consider the general
ECO problem (1.1) again and suppose that the quasi-normal component is the
normal component (4.6) and  k is given by (4.7).
We can now use Theorem 5.2 to obtain the desired local rate of convergence. It
is assumed that the orthogonal null-space basis is a continuous function of x.
Theorem 6.2. Let the general assumptions hold and assume that fx k g converges
to x   . In addition to this, let
k , and  k be given by (6.1), (4.6), and (4.7).
If r 2
xx '(x   ;    ) is positive definite on N (rC(x
then x k converges q-quadratically to x   .
Proof. It can be shown by appealing to Theorem 8.4 in [7] that r x '(x   ;
It follows from Theorem 5.2 that ffi k is uniformly bounded away from zero. Thus
there exists a positive integer  k such that for all k   k,
. The q-quadratic rate of convergence follows from [18], [36].
7. The trust-region subproblem for the linearized constraints. In this
section we investigate a few aspects of the trust-region subproblem for the linearized
constraints
subject to ks n k
First we prove that the normal component (4.6) and the quasi-normal component
always give a fraction of optimal decrease on this trust-region subproblem.
Theorem 7.1. Let the general assumptions hold. Then:
(i) The normal component (4.6) satisfies a fraction of optimal decrease on the
trust-region subproblem for the linearized constraints, i.e. there exists a positive
constant fi n
1 such that
where s
k is the optimal solution of (7.1).
(ii) In addition, assume assumption (4.2). The quasi-normal component (4.4)
satisfies the fraction of optimal decrease (7.2).
Proof. (i) If krC k (rC T
solves (7.1), and the result
holds for any positive value of fi n
1 in (0; 1]. If this is not the case, then
since krC k (rC T
We also have
ks
ks
ks
since krC k (rC T
ks
k. Combining this last inequality with
(7.3) we get
and this completes the proof of (i).
(ii) If kC y
solves (7.1), and (7.2) holds for any positive
value of fi n
1 . If this is not the case, we have
is the uniform bound on kC y Now the rest of the proof follows as
in (i).
As a consequence of this theorem, we have immediately that the normal component
(4.6) and the quasi-normal component (4.4) give a fraction of Cauchy decrease
on the trust-region subproblem for the linearized constraints.
To compute a step s n
k that gives a fraction of optimal decrease on the trust-region
subproblem for the linearized constraints we can also use the techniques proposed in
[23], [28], [31].
In the next theorem we show that the trust-region subproblem (7.1), due to its
particular structure, tends to fall in the hard case in the latest stages of the algorithm.
This result is relevant in our opinion since the algorithms proposed in [23], [28], [31]
deal with the hard case.
The trust-region subproblem (7.1) can be rewritten as
subject to ks n k
The matrix rC k rC T
k is always positive semi-definite and, under the general assump-
tions, has rank m. Let E k (0) denote the eigenspace associated with the eigenvalue
0g. The hard case is defined by the two
following conditions:
(a) (v k
(b) k(rC k rC T
Theorem 7.2. Under the general assumptions, if lim k!+1
exists a k h such that, for all k  k h , the trust-region subproblem (7.5) falls in the hard
case as defined above by (a) and (b).
Proof. First we show that (a) holds at every iteration of the algorithm. If v k 2
Multiplying both sides by (rC T
k gives us
Thus (v k
Now we prove that there exists a k h such that (b) holds for every k  k h . Since
is a monotone strictly decreasing function of
lim
is equivalent to g k () ! rffi k , for all  ? 0. Also, from the singular value decomposition
of rC k , we obtain
lim
Hence holds for all  ? 0 if and only if krC k (rC T
Now since lim k!+1
there exists a k h such that kC k
, and this
completes the proof of the theorem.
We complete this section with the following corollary.
Corollary 7.1. Under the general assumptions, if lim k!+1 kC k and the
trust radius is uniformly bounded away from zero, then there exists a k h such that, for
all k  k h , the trust-region subproblem (7.5) falls in the hard case as defined above by
(a) and (b).
Proof. If lim k!+1 kC k and the trust radius is uniformly bounded away from
zero then lim k!+1
Theorem 7.2 can be applied.
8. Concluding remarks. In Theorems 3.1 and 3.2 we have established global
convergence to a point satisfying the second-order necessary optimality conditions
for the general trust-region-based algorithm considered in this paper. In Theorem
5.2 we have proved that the trust radius is, under sufficient second-order optimality
conditions, bounded away from zero. With the help of this result we analyzed local
rates of convergence for different choices of steps and multipliers. We believe that
these results complement the theory developed by Dennis, El-Alem, and Maciel in [7]
that proves global convergence to a stationary point. We have also given a detailed
analysis of the trust-region subproblem for the linearized constraints.

Acknowledgments

. We thank Mahmoud El-Alem with whom we had many
discussions about the contents of this paper. We are also grateful to our referees for
their careful and insightful reading of this paper.


--R

Continuity of the null space basis and constrained optimiza- tion
A trust region algorithm for nonlinearly constrained optimization
On the global convergence of trust region algorithms using inexact gradient information
A trust region strategy for nonlinear equality constrained optimization
A note on the computation of an orthonormal basis for the null space of a matrix
A new trust region algorithm for equality constrained optimiza- tion
A global convergence theory for general trust-region-based algorithms for equality constrained optimization

Numerical Methods for Unconstrained Optimization and Nonlinear Equations
A Global Gonvergence Theory for a Class of Trust Region Algorithms for Constrained Optimization



A global convergence theory for arbitrary norm trust-region algorithms for equality constrained optimization
Computing optimal locally constrained steps
Properties of a representation of a basis for the null space
Some theoretical properties of an augmented Lagrangian merit function
Newton's method for constrained optimization
Projected sequential quadratic programming methods
Analysis of inexact trust-region interior-point SQP algorithms
On the implementation of an algorithm for large-scale equality constrained optimization


Trust Region Algorithms for Optimization with Nonlinear Equality and Inequality Constraints
A new algorithm for unconstrained optimization

A trust region algorithm for equality constrained optimization
A semidefinite framework for trust region subproblems with applications to large scale minimization
A family of trust-region-based algorithms for unconstrained minimization with strong global convergence properties
Newton's method with a model trust region modification

The conjugate gradient method and trust regions in large scale optimization
Towards an efficient sparsity exploiting Newton method for minimization
A trust region algorithm for equality constrained minimization: convergence properties and implementation

Numerical Methods for Nonlinearly Constrained Optimization
An improved successive linear programming algorithm
--TR

--CTR
Zhensheng Yu , Changyu Wang , Jiguo Yu, Combining trust region and linesearch algorithm for equality constrained optimization, Journal of Computational and Applied Mathematics, v.14 n.1-2, p.123-136, 1 January 1986
Detong Zhu, Nonmonotonic back-tracking trust region interior point algorithm for linear constrained optimization, Journal of Computational and Applied Mathematics, v.155 n.2, p.285-305, 15 June
equality-constrained optimization;second-order necessary optimality conditions;trust regions;local rate of convergence;hard case;SQP methods