Convergence Properties of Minimization Algorithms for Convex Constraints Using a Structured Trust Region.
In this paper, we present a class of trust region algorithms for minimization problems within convex feasible regions in which the structure of the problem is explicitly used in the definition of the trust region.  This development is intended to  reflect the possibility that some parts of the problem may be more accurately modelled than others, a common occurrence in large-scale nonlinear applications. After describing the structured trust region mechanism, we prove global convergence for all algorithms in our class.
Introduction
Trust region algorithms have enjoyed a long and successful history as tools for the solution of non-
linear, nonconvex, optimization problems. They have been studied and applied to unconstrained
problems (see [7], [17], [25], [28], [29], [30], [31], [34], [35], [38]) and to problems involving various
classes of constraints, including simple bounds ([6], [10], [11], [27], [32]), convex constraints ([2],
[3], [14], [41]), and nonconvex ones ([5], [8], [16], [36], [44]). This long lasting interest is probably
justified by the attractive combination of a solid convergence theory, a noted algorithmic
robustness, the existence of numerically efficient implementations and an intuitively appealing
motivation. The main idea behind trust region algorithms is that, if a nonlinear function (ob-
jective and/or constraints) is expensive to compute or difficult to handle explicitly, it should be
replaced by a suitable model. This model is deemed to be trustworthy within a certain trust
region around the current point. The trust region is defined by its shape and its radius. The
minimization involving the difficult nonlinear function(s) is then replaced by a sequence of minimizations
of the simpler model(s) within appropriate trust regions. The trust region radii are
adjusted to reflect the agreement between the model and true functions as the process proceeds.
It is remarkable that, up to now, all algorithms that we are aware of use a single trust
region radius to measure the degree of trustworthiness of the models employed, even if several
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.
different functions are involved. This choice is somewhat surprising if one admits that some of
the modelled functions could be substantially "better behaved" than others in the same problem,
as this implies that the region in which their models can be trusted might also be substantially
larger. In this context, the unstructured trust region choice might be viewed as a conservative
strategy ensuring that all models may be trusted in what amounts to a "safe minimal" region.
While this strategy might be reasonable for small problems, where each involved function depends
on all the problem's variables, it is clearly questionable for large-scale applications, where each
of the problem's function typically depends only on a small number of variables. For instance,
one might consider the minimization of an unconstrained objective function consisting of the sum
of many quadratic and a few highly nonlinear terms, the latter involving a small subset of the
variables. If a classical unstructured trust region algorithm, with a quadratic model, is used, the
quadratic terms are perfectly modelled, but the steps that one can make at each iteration are
(unnecessarily) limited by the highly nonlinear behaviour of a small subset of the variables.
It is the purpose of this paper to present and analyze a class of algorithms that use the
problem's structure in the definition of the trust region, allowing large steps in directions in
which the model has proved to be adequate while restricting the movement in directions where the
model seems unreliable. To be more precise, we will consider the problem of minimizing a partially
separable objective function subject to convex constraints; we will then use the decomposition of
the objective function into element functions as the basis for our structured trust region definition.
The choice of the partially separable structure, a concept introduced in [21], is motivated by the
very general geometric nature of this structure and by the increasing recognition of its practical
use (see [4], [9], [12], [13], [18], [19], [20], [22], [26], [39], [42], [43], amongst others). More
significantly, partial separability provides a decomposition of the considered nonlinear function
into a linear combination of smaller element functions, each of which may then be modelled
separately (see [40]). It is then quite natural to assign one trust region radius per element
function and to decide on its increase or decrease separately. Because different element functions
typically involve different sets of variables, each element trust region only restricts the components
of the step corresponding to its elemental variables.
An obvious approach is to use the norm-scaling matrices allowed in the theory for unstructured
trust region methods ([10], for instance) to account for differences in model adequacy among
elements when constructing the trust region. This would be satisfactory if the existing theory did
not require that the scaling matrices be of uniformly bounded condition number. Unfortunately,
it is easy to conceive of instances where this is a severe handicap. For example, it would prevent
the trust region radius of a well-modelled (perhaps linear or quadratic) element from increasing to
infinity while at the same time ensuring that that of a badly behaved nonlinear element function
remains of modest size. Moreover, this strategy may well cause numerical difficulties when
attempting to solve the trust region problem. In fact, as we will shortly see, additional algorithmic
safeguards are important when simultaneously handling trust regions of vastly different sizes.
Thus, we do not consider such an approach further in this paper.
Section 2 of the paper presents the problem in more detail and the new class of algorithms
using the principle of structured trust regions. Global convergence for all algorithms in the class
is proved in Section 3. We briefly discuss the identification of active constraints in Section 4. We
examine in Section 5 some extensions of the results of the previous sections. We finally give some
comments and perspectives in Section 6.
Structured trust region for partially separable problems
2.1 A structured model of the objective and the corresponding structured
trust region
2.1.1 The problem
The problem we consider is that of minimizing a smooth objective function subject to convex
constraints. That is, we wish to solve the problem
minimize
where X is a closed convex subset of R n . We denote the Euclidean inner product on R n by h\Delta; \Deltai,
and the associated ' 2 -norm by k \Delta k. Given Y a closed convex subset of R n , we define the operator
Y (\Delta) to be the orthogonal projection onto Y . We now list our additional assumptions on (2.1).
AS.1 X has a non-empty interior.
AS.2 f is bounded below on X .
AS.3 f is partially separable, which means that
and that, for each i 2 there exists a subspace N i 6= f0g such that, for all w 2 N i
and all x 2 X ,
AS.4 For each continuously differentiable in an open set containing X and
its gradient is uniformly bounded on X .
Note that we admit the case where X is unbounded or even identical to R n itself, in which
case we obtain an unconstrained problem. In relation to the partial separability of the objective
function, we also consider the range subspace (see [23]) associated with each element function f i ,
which is defined as
We are mostly interested in the case where the dimension of each R i is small compared to n.
A commonly occurring case is when each element function f i only depends on a small subset
of the problem's variables: R i is then the subspace spanned by the vectors of the canonical
basis corresponding to the variables that occur in f i (the elemental variables). The range of the
projection operator PR i (\Delta) is therefore of low dimensionality. The reader is referred to [12] for a
more detailed introduction to partially separable functions.
We note that f is invariant for any translation in the subspace (
We may therefore
restrict our attention to the case where
without loss of generality.
2.1.2 The element models
The algorithm we have in mind is iterative and generates feasible iterates (in the sense that all
iterates belong to X). At iteration k, we will associate a model m i;k with each element function
f i . This model, defined on R i in a neighbourhood of the projection of the k-th iterate x k on this
subspace, is meant to approximate f i for all x in the element trust region
where is the i-th trust region radius at iteration k and the norm k \Delta k is chosen to be the
usual Euclidean norm in order to simplify the exposition. In what follows, we will slightly abuse
notation by writing m i;k (x) for an x 2 R n , instead of the more complete m i;k (PR i
(x)). We will
furthermore assume that each model m i;k (i differentiable and has
Lipschitz continuous first derivatives on an open set containing B i;k , and that
Moreover, we assume that g i;k
in the sense that,
for all
where e i;k
is a constant and where \Delta min;k is defined by
i2f1;:::;pg
Condition (2.8) is quite weak, as it merely requires that the first order information be reasonably
accurate whenever some trust region radius is small (i. e. the corresponding model fits
badly). Indeed, one expects the coherency of this first order behaviour to be of crucial importance
in such cases. Further arguments supporting a choice similar to (2.8) for problems with convex
constraints are presented in [14].
Amongst the most commonly used element models, linear or quadratic approximations are
pre-eminent. One can, for instance, consider the quadratic model given by the first three terms
of the element function Taylor series around the current iterate. Another popular choice is a
quadratic model where the second derivative matrix is recurred using quasi-Newton formulae.
2.1.3 The overall model and trust region
With all the element models at hand, we are now in position to define the overall model at
iteration k, denoted m k , whose purpose is to approximate the overall objective function f in a
neighbourhood of the current iterate x k . From (2.2), it is natural to use the overall model
for all x in the overall trust region defined by
i2f1;:::;pg
Indeed B k is the intersection of all element trust regions, that is the region in which all element
models may be trusted, irrespective of the additional limitation possibly imposed by the feasible
set X .
Of course, the actual shape of the trust region B k is determined by the choice of the Euclidean
norm: it corresponds to the intersection of cylinders whose axis are aligned with the subspaces N i
and whose radii reflect the quality of the element models: large in subspaces where the element
models predict the element function correctly and smaller in subspaces where the prediction is
poorer. In practice, one might wish to choose other norms, such as the ' 1 -norm. In this case,
and assuming that the subspaces R i are spanned by subsets of the canonical basis vectors, the
shape of the trust region is that of a box, the length of whose sides again reflects the quality of the
element models. The extension of the theory to more general norms is considered in Section 5.4.
2.1.4 Curvature
We now follow [14] and [41] and define the generalized Rayleigh quotient of f at x along s 6= 0 by
Obviously, this definition is valid only if s is such that x belongs to the domain of definition
of f . Note that, by convention,
If we assume that f is twice continuously differentiable, the mean-value theorem (see [24]) implies
that
Z 1Z 1t
dv dt: (2:14)
Furthermore, if f is quadratic, then one easily verifies that !(f; x; s) is independent of x and is
equal to the Rayleigh quotient of the matrix r 2 f in the direction s. We note that, because of
is bounded by some constant L i - 0 (see [24]). Hence we obtain that
i2f1;:::;pg
for all pg. The quantity that we need in our algorithm statement
and analysis is a monotonically increasing upper bound on the magnitude of the generalized
Rayleigh quotient !(m i;k defined by
q2f0;:::;kg
i2f1;:::;pg
where s i;k
the actual trial step computed by the algorithm, as defined below.
The quantity !(m i;k measures the curvature of the model m i;k in the direction of the trial
step s k . If quadratic models m i;k are considered, an upper bound on fi k is given by the largest
singular value of all Hessian matrices, plus one. We will assume that our choice of models is such
that this curvature does not increase too fast, which could lead to premature convergence of the
algorithm to a non-critical point (see [41]). More precisely, we make the following assumption,
as in [14], [10], [35] and [41].
This condition is weaker than the common assumption that the model's second derivative
matrices are uniformly bounded [32], which holds, for instance, for the classical Newton's method,
where quadratic models using analytical second derivatives are used on a compact domain. It is
also weaker than the condition
for some constant c 0 ? 0, which holds in the case where quadratic element models are used and
updated using either the BFGS or the safeguarded Symmetric Rank One quasi-Newton formulae.
2.1.5 Criticality
Before we can describe our algorithm in detail, we also need a criticality criterion for our problem.
A critical point of our problem is a feasible point x where the negative gradient of the objective
function \Gammarf (x) belongs to the normal cone of X at x 2 X , which is defined by
fy
The associated tangent cone of X at x 2 X is the polar of N (x), that is
Thus every measure of criticality has to depend on the (differentiable) objective f and on the
geometry of the feasible set at the current point. We will use the symbol ff(x; f; X) to denote
such a criticality measure.
AS.6 The criticality measure ff(x; h; X) is non-negative for all x 2 X and all functions h differentiable
in an open neighbourhood of x. Moreover ff(x; h; only if x is critical
for the problem
minimize x2X h(x): (2:21)
But, within the algorithm, only approximate gradient vectors might be available, namely the
vectors g k and g i;k , the gradients of the models. It is therefore natural to use
the criticality measure for the problem
as an "approximate" criticality measure for (2.1). Note that ff k ? 0 implies that g k 6= 0.
In unconstrained optimization, one typically chooses
the obvious criticality measure (see [31] or [34]). When bound constraints are present, the choice
is made in [10]. For the infinite dimensional case, the definition
is used in [41]. For the case where convex constraints are considered,
is chosen in [32], where t C
is the line coordinate of the so-called "generalized Cauchy point"
to be discussed below. In a similar context,
is used in [14].
2.2 Ensuring sufficient model decrease
2.2.1 An overview of the classical sufficient decrease condition
A key to trust region algorithms is to choose a step s k at iteration k that is guaranteed to provide
a sufficient decrease on the overall objective function model m k . In other words, a step such that
is sufficiently positive, given the value of a suitable criticality measure ff k satisfying AS.6. This
concept of "sufficient decrease" is usually made more formal by introducing the notion of the
(generalized) Cauchy point. This remarkable point, denoted x C
k , is typically computed by trust
region algorithms as a point on (or close to) the projected gradient path PX
that is also within the trust region and sufficiently reduces the overall model in the sense that
is a constant and ff k a criticality measure satisfying AS.6. However, such a point
may not exist when the trust region radius \Delta k is small compared with ff 2
. In this case, the
generalized Cauchy point is chosen as (or close to) the intersection of the projected gradient path
with the boundary of the trust region, yielding an inequality of the form
A point on the projected gradient path satisfying (2.30) may also fail to exist because the projected
gradient path itself ends on the boundary of X , well inside the trust region. In that case, this
end point (or another feasible point close to it) is typically chosen as generalized Cauchy point,
and it is then typically shown that
One then ensures the "sufficient decrease" by requiring that the chosen step s k produces at least
a fixed fraction of the overall model reduction achieved by the generalized Cauchy point, which
is to say that
ae ff k
oe
Many variants on the above scheme exist in the literature for the unstructured trust region
case. All of these variants ensure that a suitable step is found after a finite number of trials. The
best known is for unconstrained problems when the ' 2 -norm is used to define the trust region
shape. In that case, the projected gradient path is simply given by all negative multiples of
the gradient g k and the Cauchy point is simply the point that minimizes the model m k in the
intersection of the steepest descent direction and the trust region (see, for instance, [34] and [37]).
When other norms are used, for example the ' 1 -norm, one can then choose either to minimize
the model in the intersection of this steepest descent direction and the trust region, as before
(see [10]), or to "bend" the projected gradient path onto the boundary of the trust region and to
choose the generalized Cauchy point as a point which satisfies classical Goldstein-type linesearch
conditions along that path while staying within the trust region (see [33] and [41]). Both these
latter strategies are used in the LANCELOT software [13]. When additional convex constraints
are present, the projected gradient path is additionally "bent" to follow the boundary of the
feasible domain. Thus the philosophy is the same, in that (2.33) is guaranteed in the above cases.
Indeed satisfaction of this condition has been derived for each of the choices (2.24)-(2.28) for ff k
in the papers where they were respectively introduced.
2.2.2 Sufficient decrease for structured model and trust region
We will use a similar approach in our structured model and trust region framework to determine
what is a sufficient decrease of the overall model m k within the region B k , whose shape is chosen
to reflect the structure of the problem. Special care is needed because this region might be very
"asymmetric" in the sense that it may allow very large steps in some directions and only very
short ones in others. As a consequence, we have to adapt the notion of trust region "radius" to
our context and adequately reformulate condition (2.33).
From a practical point of view, one might use a two-stage approach. In this, one first aims
to find a step producing a sufficient model decrease in a smaller, but more symmetric, region.
Following this, one then allows the step to increase within the trust region while maintaining
control over the model decrease.
To be specific, let
be the trust region whose radius is determined by the possibly most nonlinear part of the model.
Applying the results discussed in the previous section after condition (2.33), one may deduce that
it is possible to find, in a finite number of trials, a step s min;k such that x k
and
ae ff k
oe
for some suitably chosen criticality measure ff k satisfying AS.6 and some constant -
However, the restriction that the length of s min;k is bounded by \Delta min;k makes the whole
exercise of shaping B k to reflect the problem's structure entirely irrelevant. One might therefore
be prepared to accept a larger step provided it remains feasible, within the trust region B k , and
produces a further significant model decrease. More specifically, we allow our algorithm to choose
any step s k such that x k which guarantees that
ae ff k
ks k k]; 1
oe
Note that, since (2.36) holds for s this condition can therefore be achieved in
practice after a finite number of trials. Observe also that (2.36) is fundamentally different from
an angle test of the form
as (2.36) does not prevent s k from being orthogonal to the steepest descent direction, so long
as a sufficient model reduction is obtained. This is useful because such a step may occur when
moving away from a saddle point of the objective function. Finally note that, as expected, (2.36)
reduces to (2.33) in the case where only one trust region is considered.
2.3 A class of structured trust region algorithms
We now describe the class of algorithms that we consider for solving (2.1). Besides - 1 used in
used in (2.36), it depends on the constants
and
In addition to the above conditions, we also require a compatibility condition between the j i 's
and the - i 's. Specifically, we request that
Typical values for these constants are -
Algorithm
step 0: initialization.
The starting point x together with the element function values ff i
and the initial trust region radii
step 1: model choice.
For choose the model m i;k of the element function f i in the trust region B i;k
centered at x k (as defined in (2.6)), satisfying (2.7) and (2.8).
step 2: determination of the step.
Choose a step s k such that the sufficient decrease condition (2.36) holds and
step 3: measure overall model fit.
If
then
else
step 4: update the element trust region radii.
Denote the achieved changes in the element functions and their models by
ffif i;k
and
respectively. Then define the set of negligible elements at iteration k as
and the set of meaningful elements as its complement, that is
Then, for each i 2 perform the following.
Case 1:
ffl If
and (2.43) both hold, then choose
ffl If (2.50) holds but (2.43) fails then choose
ffl If (2.50) fails, but
holds, then choose
ffl If (2.53) fails, then choose
Case 2:
ffl If
and (2.43) both hold, then choose
ffl If (2.56) holds but (2.43) fails, then choose
ffl If (2.56) fails, then choose
Increment k by one and return to step 1.
End of Algorithm
As is traditional in trust region algorithms, we will call an iteration successful if the test
(2.43) is satisfied, that is when the achieved objective reduction ffif k is large enough compared
to the reduction predicted by the overall model. If (2.43) fails, the iteration is said to be
unsuccessful. In what follows, we will denote by S the set of all successful iterations.
We now comment on various aspects of the algorithm.
1. The algorithm is constructed in such a way that a successful step is always possible, for
sufficiently small trust region radii, if the current iterate x k is not critical. This result is
formally proved in Corollary 8.
2. The choice of the element models m i;k is left rather open in the above description. It clearly
needs to be made precise for any practical implementation of the algorithm. One common
choice would be to set
where H i;k is a symmetric approximation to r 2 f i nullspace contains the subspace
In particular, Newton's method corresponds to the choice g
which is guaranteed to satisfy this latter condition. Another possible choice is
which may be attractive for the simpler element functions. In
this case, the model's fit to the true function is always good for the i-th element, and the
algorithm guarantees that the \Delta i;k form a non-decreasing sequence.
3. If the model change for an element is negligible, that is small compared to the overall
predicted change, we do not need to restrict its element trust region size unless the true
element change is relatively large compared with the same overall predicted change. We
can therefore afford to ignore negligible items until they stop being relatively negligible,
something which is inevitable when convergence occurs. Hence our distinction between
"negligible" elements (in N k ) and "meaningful" ones (in M k ).
Condition (2.41) can be viewed in this context as a guarantee that a new iterate will be
accepted in (2.43) whenever the model reduction obtained for all meaningful elements is
also acceptable (i.e. (2.53) holds for all irrespective of the contribution of the
negligible ones. This interpretation is clarified in Lemma 2.
4. The apparent intricacy of (2.50) and (2.53) is caused by two complications which arise in
the context of multiple elements. The first is that, although (2.36) ensures that
always positive, we may not assume in general that the same is true for ffim i;k . The second
is that possible cancellation between elements makes it necessary to consider the "accuracy
of model fit" for an element to be relative to the overall model fit. Indeed, requiring small
relative errors for models with very large values may result in large absolute errors. If
these large errors will then cause to be a poor prediction of ffif k and the
iteration might be unsuccessful. This explains why the perhaps more intuitive tests
cannot be used instead of (2.53) (j = 2) and (2.50) (j = 3).
Observe also that conditions (2.50) and (2.53) reduce to the familiar
when
5. Note again the consistency between the trust region radii updates in step 4 and the case
1. In this latter case, the set N k is always empty and (2.50) then implies (2.43),
because of (2.39). Equation (2.52) is thus never invoked.
stopping criterion has been explicitly included in our algorithm description. This is
adequate for the theoretical analysis that we consider in the present paper, where we are
interested in the asymptotic behaviour of the method, but it should be completed for any
practical use. The choice of a particular stopping criterion will depend on the type of
models being used.
7. The mechanism that we specified for updating the trust region radii does not exclude the
additional requirement that the radii be uniformly bounded, if that is judged suitable for
the type of models used. In practice, keeping the radii bounded is essential to prevent
numerical overflow.
8. One possible implementation of Step 2 first computes a feasible step s C
k that minimizes
trust region of radius \Delta min;k . Note that s C
satisfies (2.35) and
by construction. This step may then subsequently be increased by progressing further
along the arc PX long as the overall model m k continues to decrease and
holds. Additional decrease in m k may then be obtained (for instance by applying
conjugate-gradient steps) provided condition (2.36) is maintained.
Before starting our global convergence analysis, we first state, for future reference, some
properties that result from the mechanism of the algorithm.
Assume that AS.3 holds. At each iteration k of the algorithm,
1. M k contains at least one element. Furthermore
2.
for all pg.
Proof. The first result immediately follows from the definition of N k and the inequality
1. One then deduces that N k contains at most
from which the first part of (2.63) may be deduced. The second inequality in this result is
obtained from X
the relation (2.48) and jN k 1. The bound (2.64) results from (2.51), (2.54), (2.55), (2.57)
and (2.59). 2
We also investigate the coherency between the measure of fit for individual elements and that
for the overall model.
Assume AS.3 holds and that, at iteration k of the algorithm, (2.53) holds for all
and that (2.56) holds for all i 2 N k . Then iteration k is successful, i.e. k 2 S.
Proof. Because (2.53) holds for , one has that
for all such i, where we used the inequality jM k j - p and Lemma 1 to deduce the second inequality.
On the other hand, since (2.56) holds for i 2 N k , one obtains for these i that
where we used item 1 of Lemma 1 to bound jN k j. Now,
jffif i;k j: (2:69)
Combining this last inequality with (2.67) and (2.68) gives that
which then yields (2.43) because of (2.41). 2
We observe from this proof that the weaker condition
could be imposed instead of (2.41). However (2.71), and hence the setting of the algorithm's
constants, would then be problem dependent, which one might consider to be undesirable.
Of course, (2.53) holds whenever (2.50) holds because of (2.39). Lemma 2 therefore shows that
(2.43) is coherent with the measure of the fit between the element models and element functions.
3 Global convergence
We now study the convergence properties of the class of algorithms that we introduced in the
preceding section. Our analysis follows the pattern of similar proofs with an unstructured trust
region (see [14] or [41]). The central idea in the proof is that the algorithm will continue to make
progress as long as a critical point is not reached. We first start by bounding the error between
the true element functions and their models. We next derive a lower bound on the size of the
smallest trust region radius at a non-critical point. This lower bound ensures that the trust region
constraint will not prevent further progress towards a critical point. Only with this bound can
we then prove that limit points of the sequence of iterates produced by the algorithm are indeed
critical for the models used. We close the section by deriving some simple consequences of these
results on the criticality of the limit points for the true objective function.
We first start by bounding the error made between the model of any element function and
the element function itself at x k
Lemma 3 Assume that AS.4 holds and consider a sequence fx k g of iterates generated by the
algorithm. Then there exists a positive constant c 1 - 1 such that
for all
Proof. We first observe that, for each i 2 the definition (2.12),
(2.7) and the Cauchy-Schwarz inequality imply that
ks i;k k
But ks i;k k - \Delta i;k because of (2.6), and hence we obtain from (2.8), (2.15) and (2.16) that
Using (2.9), this then yields (3.1) with
where the last inequality results from (2.15). 2
We now derive an upper bound on the change predicted for an element at a non-critical point,
as a function of the size of the step in the corresponding range subspace.
Lemma 4 Assume that AS.1, AS.3 and AS.4 hold. Consider iteration k of the algorithm and
assume that, for some
Then one has that
ks i;k k (3:6)
for some constant c 2 ? 0 independent of i and k.
Proof. We first note that (2.9), (2.16) and (3.5) imply that
Using (2.12) and (2.16), we also obtain that
ks i;k ks i;k
Remembering now (2.8), (2.6), (3.5) and (3.7), we can deduce that
ks ks ks i;k k 2
ks i;k k:
Inequality (3.9) then gives (3.6) with
i2f1;:::;pg
next prove the important fact that, so long as a critical point has not been determined, the
trust region radii stay sufficiently bounded away from zero, therefore allowing further progress
to be made.
Lemma 5 Assume that AS.1-AS.4 hold. Consider a sequence fx k g of iterates generated by the
algorithm and assume that there exists a constant ffl ? 0 such that
for all k. Then there is a constant c 3 ? 0 such that
for all k.
Proof. Assume, without loss of generality, that
In order to derive a contradiction, assume that there exists a k such that
define r to be the smallest iteration number such that (3.14) holds.
(Note that r - 1 because of (3.13) and the inequality
The monotonic nature of the sequence ffi k g and the bound (2.64) then ensure that
where we used (3.14) and the inequality (3.13). We note that the definitions of i and r give that
which in turn implies that \Delta because of the monotonic nature of the sequence
g. Using this inequality with (2.36), (3.11), and (3.15), we obtain that
ae ffl
ks
oe
ae ffl
oe
which ensures, because of (2.64), that
But (3.15) guarantees that fi We may thus apply Lemma 4 and deduce that
ks
where we also used (2.6) and (3.18).
Assume first that i 2 M r\Gamma1 , which guarantees that using (2.48) and
(3.18),
Because of (2.7), (3.1) and (3.20), we therefore obtain that
ffif
But (3.14) and (3.15) together give that
which, with (3.21), implies that
ffif
Consider first the case where ffim may then apply (3.19) and deduce that
Using (3.23), we now deduce that
ffif
and therefore, because of (3.24), that
which implies that (2.50) holds for element i at iteration r \Gamma 1. Now turn to the case where
Because of (3.19), we deduce that
As above, we use (3.23) to obtain that
ffif
and therefore, because of (3.27), that
which again implies that (2.50) holds for element i at iteration r \Gamma 1.
Assume now that i 2 N r\Gamma1 . Then, because of (2.7), (2.48) and (3.1), we have that
multiplying (3.18) by \Delta i;r\Gamma1 , we obtain that
Combining (3.30) and (3.31), we deduce that
Observing now that (3.14) and (3.15) imply that
we obtain from (3.32) that
But this inequality implies that (2.56) holds for element i at iteration r \Gamma 1. Thus either (2.50)
or (2.56) holds for element i at iteration r \Gamma 1 and the mechanism of the algorithm then implies
that But we may deduce from this inequality that
which contradicts the assumption that r is the smallest iteration number such that (3.14) holds.
The inequality (3.14) therefore never holds and we obtain that (3.12) is satisfied for all k. 2
We now turn to one of the main results in this section, which proves a weak form of global
convergence. The technique is inspired by [35].
Theorem 6 Assume that AS.1-AS.6 hold. Consider a sequence fx k g of iterates generated by
the algorithm. Then
lim inf
Proof. Assume, for the purpose of obtaining a contradiction, that there exists an ffl 2 (0; 1)
such that (3.11) holds for all k - 0. Then
ks k k]; 1
where we used successively (2.43), (2.36), (3.11) and Lemma 5. We note that (3.37) and AS.2
then imply that X
Now let r be an integer such that
and define
the number of successful iterations up to iteration 1). Then define
We now wish to show that both sums
and
are finite. Consider the first. If it has only finitely many terms, its convergence is obvious.
Otherwise, we may assume that F 1 has an infinite number of elements, and we then construct
two subsequences. The first consists of the indices of F 1 in ascending order and the second, F 3
say, of the set of indices in S (in ascending order) with each index repeated r times. Hence the
j-th element of F 3 is no greater than the j-th element of F 1 . This gives that
because of the nondecreasing nature of the sequence ffi k g and (3.38). Now turn to the second
sum in (3.42). Lemma 2 and the mechanism of the algorithm imply that, at each unsuccessful
iteration, at least one element trust region radius satisfies (2.55) or (2.59) and none of them is
allowed to increase. Hence p
Y
Y
which immediately implies that
where
We deduce from this inequality that, for k 2 F 2 ,
where we have also used Lemma 5 and the definition of F 2 in (3.41). Using (3.39), this gives that
and the second sum is convergent. Therefore the sumX
is finite, which contradicts AS.5. Hence condition (3.11) is impossible and (3.36) follows. 2
Notice that the relation between ff k , the criticality measure for problem (2.23), and ff(x k ; f; X),
the criticality measure for problem (2.1), has been left rather unspecified up to this point. It
is indeed remarkable that we can prove Theorem 6 assuming so little on ff. In order to derive
convergence properties for the original problem from Theorem 6, we have to be slightly more
specific and request that, if both function and model have the same first order information, then
the criticality measures on the original problem and on the model problem agree.
AS.7 Let h 1 and h 2 be two continuously differentiable functions in the intersection of X with
a neighbourhood of the feasible point x, such that h 1 Then, the difference
tends to zero.
In other words, we require the criticality measure to be continuous (near zero) in the gradient
of its second argument. Again, this is true for the choices (2.24)-(2.25) and (2.28).
With this additional assumption, we are now ready to examine the criticality of the limit
points of the sequence of iterates generated by the algorithm for the original problem (2.1).
Corollary 7 Assume that AS.1-AS.7 hold. Consider a sequence fx k g of iterates generated by
the algorithm and assume that
lim
for all pg. Then this sequence has at least one critical limit point x   .
Proof. From AS.7 and (3.49), we obtain that
lim
which, with (3.36), guarantees
lim inf
The desired conclusion then follows by taking a subsequence of fx k g if necessary. 2
Condition (3.49) is important, otherwise the situation might arise that an iterate is critical for
the current overall model (because its gradient is inexact) while not being critical for the original
problem. There are various ways in which (3.49) can be achieved in a practical algorithm, the
simplest being to make the size of e i;k also depend on ff k itself, ensuring that the first goes to
zero if the latter does.
Corollary 8 Assume that AS.1-AS.7 hold. If S, the set of successful iterations generated by the
algorithm is finite, then all iterates x k are equal to some x   for k large enough, and x   is critical.
Proof. Assume indeed that S is finite. It is then clear from (2.45) that x k is unchanged for
large enough, and therefore that x  is the largest index in S. Note now that
Lemma 2 implies that, if k 62 S, then (2.53) or (2.56) must be violated for at least one element.
Hence we obtain that \Delta min;k converges to zero. But (2.8) then implies that e i;k also converges to
zero for all k converges to rf(x k ). Thus AS.7 and Corollary 7 then guarantee
the criticality of x   . 2
As in existing theories for the unstructured trust region case, it is possible to replace the limit
inferior in (3.36) by a true limit, therefore ensuring (if the gradients are asymptotically exact)
that all limit points are critical. As in these theories, a slight strengthening of our assumptions
is however necessary.
AS.8 We assume that
lim
This assumption is similar to that used in [14] and [41], where it is motivated in detail. We only
mention here that (3.52) holds for Newton's method on bounded domains, because fi k is bounded
above in that case.
With this additional assumption, we are now able to replace the limit inferior by a true limit.
Theorem 9 Assume that AS.1-AS.8 hold. Consider the sequence fx k g of iterates generated by
the algorithm and assume that there are infinitely many successful iterations. Then
lim
where S is, as above, the set of successful iterations.
Proof. We again proceed by contradiction. Assume therefore that there exists an ffl 1 2 (0; 1)
and a subsequence fq j g of successful iterates such that, for all q j in this subsequence
Theorem 6 guarantees the existence of another subsequence fl j g such that
where we have chosen ffl 2 2 (0; ffl 1 ). We may now restrict our attention to the subsequence of
successful iterations whose indices are in the set
where q j and l j belong, respectively, to the two subsequences defined above. Applying now (2.36)
we obtain from (2.43), (2.16) and ffl
ks k k]; 1
oe
ks k k]
oe
But AS.8, along with (3.57), imply that
lim
ks
and, because of (2.16), that
lim
ks
Therefore, we can deduce from (3.57) and (3.58), that, for j sufficiently large,
ks k k
where the sums with superscript (K) are restricted to the indices in K, and
But AS.2 and the decreasing nature of the sequence ff(x k )g imply that the last right-hand side
of (3.60) converges to zero as j tends to infinity. Hence the continuity of rf and AS.7 give that
sufficiently large. On the other hand, the second part of (3.59) and (2.8) imply that g q j
is
arbitrarily close to rf(x q j
large enough, and AS.7 hence guarantees that
sufficiently large. We note also that, because of (2.8),
But the mechanism of the algorithm guarantees that no \Delta i;k can increase between iterations
is the largest integer in K that is smaller than l j .
This yields that
We now deduce from the second part of (3.59) that the left-hand side of (3.65) tends to zero
when j tends to infinity, and therefore that, for j sufficiently large,
because of AS.7. Combining (3.62), (3.63) and (3.66), we obtain, using (3.55), that
which is impossible because of (3.54). Hence our initial assumption cannot hold and the theorem
is proved. 2
As above, we now consider the case where we impose that the element gradients are asymptotically
exact.
Assume that AS.1-AS.8 hold. Consider the sequence fx k g of iterates generated
by the algorithm and assume furthermore that (3.49) holds for all pg. Then all limit
points of this sequence are critical.
Proof. If the set S is finite, the conclusion immediately follows from Corollary 8. If, on
the other hand, S has an infinite number of elements, (3.49) implies that g k is arbitrarily close
to rf(x k ) and the combination of AS.7 and Theorem 9 ensures the criticality of any limit point
of the sequence of successful iterates. 2
Of course, (3.49) might be impossible to achieve in practice, and one might consider the case
where we can only assert that
lim sup
i2f1;:::;pg
for some small constant - 3 ? 0. This is the case, for instance, if gradients are approximated by
finite differences.
Corollary 11 Assume that AS.1-AS.6 and AS.8 hold. Consider the sequence fx k g of iterates
generated by the algorithm. Assume furthermore that (3.68) holds and that, for some constant
the criticality measure ff satisfies
for all x 2 X and all functions h 1 and h 2 continuously differentiable in a neighbourhood of x such
that h 1 for each limit point x   of the sequence,
Proof. As in Corollary 10, the desired conclusion immediately follows from Corollary 8 if
S is finite. Assume therefore that S has infinitely many elements. We then deduce that, for all
Taking the limit for k tending to infinity in S and using Theorem 9 and (3.68) then gives the
desired conclusion. 2
Finally observe that although (3.69) is stronger than AS.7, it is not a very strong condition.
For instance, it is satisfied with L for the choices (2.24), and also for (2.25) and (2.26)
because of the non-expansive character of the projection operator PX (see [41], for example).
The same property also holds for the choice (2.28), as discussed in [14].
Finite identification of the correct active set
When applied to constrained problems, trust region algorithms typically use the notion of projected
gradient or projected gradient path in order to identify a subset of inequality constraints
that are satisfied as equalities. Ultimately, the aim thereby is to identify the constraints satisfied
as equalities at the solution well before the solution is reached. The methods then reduce to an
unconstrained calculation in the manifold defined by the currently "active" constraints. As a
consequence, it is possible to guarantee fast asymptotic rates of convergence when using accurate
models, as is the case when analytical second order information of the objective and constraint
functions is available.
It is possible to show that structured trust regions do not upset the theory developed in the
unstructured case: it can indeed be shown that the constraints active at a particular limit point
of the sequence of iterates are identified after a finite number of iterations, provided the normals
of the active constraints are linearly independent and strict complementarity holds, and provided
the step s k+1 satisfies the inequality
ks ks k k (k) (4:1)
for each k 62 S and for some constant This latter condition is meant to avoid
a situation where the successful iterates converge to a critical point while a subsequence of
unsuccessful iterates converges to another point with a different active set. It does not constitute
a severe restriction in the step selection procedure and is automatically verified if s k is determined
by a succession of steps of increasing norm such that they remain feasible, within the trust region
ensure (2.36). This is the case, for instance, if truncated conjugate gradients are used
for computing the step in the solution of an unconstrained problem (see [37] or [38]).
The theory considers the active constraint identification problem from a quite general point
of view. The main observation is that a number of the existing theories for active constraint
identification are based on the definition of a special criticality measure that satisfies AS.6 while
not satisfying AS.7 (see [2] or [3], for instance). Let us denote this measure at iteration k by -
ff k .
The steps leading to constraint identification are then as follows.
1. The first step is to prove that a sufficient decrease condition of the type (2.33) also holds
with -
ff k instead of ff k .
2. One then proceeds to prove that
lim inf
much in the same way as for (3.36).
3. The measure -
ff k is also constructed to ensure that it is asymptotically bounded away from
zero for all points such that their active set is not identical to that of a (close) critical point.
(This, in particular, prevents AS.7 from holding.)
4. Some contradiction is then deduced from these last two properties.
However, since this development is rather technical and lengthy, we do not include it in the
present paper, but refer the interested reader to [15] for details of the results and additional
assumptions. This reference also contains the theory concerning the convergence of the iterates
to a single limit point, adapted from [14].
Our experience with the solution of practical problems however indicates that the identification
of active constraints is seldom observed in practice before the very last iterations of the
algorithm, which makes the results discussed in this section mainly of theoretical interest.
Extensions
We examine in this section some extensions and variants of the results presented above.
5.1 A hybrid technique
One of the possible drawbacks of the algorithm of Section 2.3 is that steps might be constrained to
be unnecessarily small in directions corresponding to highly nonlinear element functions. Indeed,
the negative effect of inaccurate models for these elements might be compensated by a successful
step in directions corresponding to less nonlinear elements. This compromise between the different
parts of the objective is, of course, inherent to the classical method using an unstructured trust
region.
We might try to obtain the best of both classical and structured approaches by using a hydrid
technique. In this technique, a global trust region radius \Delta k is recurred for the objective function
considered as a single element (using the algorithm analyzed above, which is then equivalent to
the classical one), along with the individual radii \Delta i;k . We then define the individual "hybrid"
radii by
for each i 2
i;k g: (5:2)
We can then apply our algorithm with these new quantities, to the effect that well-modelled
elements have their associated trust regions possibly extended without having to contract those
corresponding to badly-modelled ones, as long as the global agreement is satisfactory.
It is not difficult to verify that the theory presented above still holds for this hybrid mod-
ification. The key points are to observe that the revised definition of our trust region implies
that
ae ff k
oe
which is the classical sufficient decrease condition (2.33), that the inequalities (2.64) are still valid
with \Delta i;k replaced by \Delta h
i;k , and also that an analogous result to Lemma 5 also holds for the global
trust region radius, as is already well-known from the unstructured trust region case (see [14],
for instance).
5.2 An alternative definition of success
An immediate consequence of inequality (2.63) in Lemma 1 is that it would be possible to replace
the condition (2.43) for an iteration to be successful by
without altering the developments presented above. Indeed, (2.63) shows the equivalence between
(2.43) and (5.4). We have chosen to use seems natural to consider the
same collection of elements on both sides of the inequality.
5.3 Weaker sufficient decrease conditions
It is remarkable to note that Lemma 5 and Theorem 6 can be proved in a weaker context. Indeed,
we could require the weaker sufficient decrease condition
ae ff k
oe
instead of (2.36), and still prove Lemma 5 and Theorem 6. However, we have not been able to
prove Theorem 9, nor active constraint identification, with these assumptions, because (5.5) only
involves the length of the step in a possibly small subspace of R n .
5.4 Using uniformly equivalent norms
Another possible generalization of the theory developed above allows the use of different norms
for each element and for each iteration. Let us denote these norms by the . The
element trust region definition (2.6) then becomes
while the gradient approximation condition (2.8) may be written as
where the norm k \Delta k [i;k] is any norm that satisfies
for all x; y 2 R n . In particular, one can choose the dual norm of k \Delta k (i;k) defined by
With iteration k, we may also associate an overall norm k \Delta k (k) defined on the whole of R n , whose
purpose is to reflect the relative weighting of the different elemental norms k \Delta k (i;k) in a global
measure.
If we assume that all the considered norms are uniformly equivalent, that is if there exists a
constant oe - 1 such that, for all x,oe
is any pair of the above defined norms, then the theory developed in all
the preceding sections is still valid without any substantial modification. Again the details of
the proofs in this more general setting are provided in [15]. Note that this extension covers
the possible introduction of iteration dependent scaling in a practical implementation of our
algorithm, which can be highly desirable for some difficult problems.
6 Conclusions
We have shown in this paper that the trust region concept, one of the most powerful tools for
building efficient and robust algorithms for optimization, can be extended in a very natural way
to reflect the structure of the underlying problem. The algorithm proposed above is indeed a
direct generalization of the more usual case where only an unstructured uniform trust region is
considered. Similar global convergence properties can be proved for the new algorithm, including
the case where dynamic scaling is performed on the variables and the situation where the gradients
are only known approximately.
It remains to see if this modification of a trust region algorithm will prove efficient in practice
and justify the slight additional complexity of the method. Note that the results of preliminary
numerical experiments (based on a modification of LANCELOT using the implementation described
after the algorithm) have been encouraging. Tests on unconstrained problems from the
collection [1] have shown that the new method, although very comparable to LANCELOT
in many cases, sometimes produces substantial improvements. However, we anticipate the real
power of the concept to appear when minimizing augmented Lagrangians or other penalty-like
because scaling is much more critical there than in many of the classical unconstrained
test examples. The authors are planning to include the new technique described in this paper
within the next release of LANCELOT.
One of the nice features of the partially separable functions considered in the present theory
is that the objective is a linear combination of its elements. While group partially separability, as
used in [12] or [13], has computational advantages in terms of economy of derivative calculation,
this structure involves a nonlinear relationship between the elements and the overall function.
This seems to make exploiting the link between local and global models much harder. While
we would be interested in deriving structured trust region methods for group partially separable
functions, the methods would undoubtedly be more complicated and less amenable to analysis.
Thus, we are content, in the present paper, to consider the simpler, but nonetheless very general,
partially separable structure.
Finally, there might be other ways to introduce structure in trust region methods than considering
(group) partially separable objective functions. In particular, trust region methods for
nonlinearly constrained problems seems attractive candidates for an alternative approach that
would separate the trust region(s) on the objective from those on the constraints.

Acknowledgments

The authors are indebted to Johara Shahabuddin for twice pointing out an unsuitable definition
of the sufficient decrease condition (2.36) in Section 2.2.2.



--R

CUTE: Constrained and Unconstrained Testing Environment.
On the identification of active constraints.
Convergence properties of trust region methods for linear and convex constraints.
Parallel global optimization: numerical methods
A trust region algorithm for nonlinearly constrained optimization.
Projected gradient methods for linearly constrained problems.
On the global convergence of trust region methods using inexact gradient information.
A trust region strategy for nonlinear equality constrained optimization.
Performance of a multifrontal scheme for partially separable optimization.
Global convergence of a class of trust region algorithms for optimization with simple bounds.
Testing a class of methods for solving minimization problems with simple bounds on the variables.
An introduction to the structure of large scale nonlinear optimization problems and the lancelot project.
LANCELOT: a Fortran package for large-scale nonlinear optimization (Release
Global convergence of a class of trust region algorithms for optimization using inexact projections on convex constraints.
Convergence properties of minimization algorithm for convex constraints using a structured trust region (revised).
A global convergence theory for the Dennis-Celis-Tapia trust-region algorithm for constrained optimization
Practical Methods of Optimization: Unconstrained Optimization.
Is exploiting partial separability useful?

The global convergence of partitioned BFGS on problems with convex decompositions and Lipschitzian gradients.
On the unconstrained optimization of partially separable functions.
Numerical experiments with partially separable optimization problems.
On the existence of convex decomposition of partially separable functions.
Algorithmic Methods in Optimal Control.
An algorithm for minimization using exact second derivatives.
Partially separable optimization and parallel computing.
Convergence of trust region algorithms for optimization with bounds when strict complementarity does not hold.
A method for the solution of certain problems in least squares.
An algorithm for least-squares estimation of nonlinear parameters
The Levenberg-Marquardt algorithm: implementation and theory
Recent developments in algorithms and software for trust region methods.
Trust regions and projected gradients.
On the solution of large scale quadratic programming problems with bound constraints.
A new algorithm for unconstrained optimization.
On the global convergence of trust region algorithms for unconstrained optimization.
A trust region algorithm for equality constrained optimization.
The conjugate gradient method and trust regions in large scale optimization.
Towards an efficient sparsity exploiting Newton method for minimization.
Global convergence of the partitioned BFGS algorithm for convex partially separable optimization.
On large scale nonlinear least squares calculations.
Global convergence of a class of trust region methods for nonconvex minimization in Hilbert space.
On large scale nonlinear network optimization.
LSNNO: a Fortran subroutine for solving large scale nonlinear network optimization problems.
A trust region algorithm for equality constrained minimization: convergence properties and implementation.
--TR

--CTR
Nicholas I. M. Gould , Dominique Orban , Philippe L. Toint, GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization, ACM Transactions on Mathematical Software (TOMS), v.29 n.4, p.353-372, December
partial separability;trust region methods;large-scale optimization;convex constraints;structured problems