Automatic Determination of an Initial Trust Region in Nonlinear Programming.
This paper presents a simple but efficient way to  find a good initial trust   region  radius (ITRR)  in    trust region  methods    for  nonlinear optimization.  The method consists of monitoring the agreement between the  model  and  the objective  function  along   the steepest descent direction, computed at  the starting point.   Further improvements for the starting    point are also derived  from   the information gleaned during the  initializing phase.  Numerical results  on  a large set of problems  show the impact the initial  trust region radius may have on trust   region methods behavior and   the  usefulness of the proposed strategy.
Introduction
. Trust region methods for unconstrained optimization were
first introduced by Powell in [14]. Since then, these methods have enjoyed a good
reputation on the basis of their remarkable numerical reliability in conjunction with
a sound and complete convergence theory. They have been intensively studied and
applied to unconstrained problems (see for instance [11], [14], and [15]), and also to
problems including bound constraints (see [4], [7], [12]), convex constraints (see [2],
[6], [18]), and non-convex ones (see [3], [5], and [19], for instance).
At each iteration of a trust region method, the nonlinear objective function is
replaced by a simple model centered on the current iterate. This model is built using
first and possibly second order information available at this iterate and is therefore
usually suitable only in a certain limited region surrounding this point. A trust region
is thus defined where the model is supposed to agree adequately with the true objective
function. Trust region approaches then consist of solving a sequence of subproblems
in which the model is approximately minimized within the trust region, yielding a
candidate for the next iterate. When a candidate is determined that guarantees
a sufficient decrease on the model inside the trust region, the objective function is
then evaluated at this candidate. If the objective value has decreased sufficiently,
the candidate is accepted as next iterate and the trust region is possibly enlarged.
Otherwise, the new point is rejected and the trust region is reduced. The updating
of the trust region is directly dependant on a certain measure of agreement between
the model and the objective function.
A good choice for the trust region radius as the algorithm proceeds is crucial.
Indeed, if the trust region is too large compared with the agreement between the
model and the objective function, the approximate minimizer of the model is likely
to be a poor indicator of an improved iterate for the true objective function. On
the other hand, too small a trust region may lead to very slow improvement in the
estimate of the solution.
When implementing a trust region method, the question then arises of an appropriate
choice for the initial trust region radius (ITRR). This should clearly reflect
the region around the starting point, in which the model and objective function approximately
agree. However, all the algorithms the author is aware of use a rather
ad hoc value for this ITRR. In many algorithms, users are expected to provide their
Department of Mathematics, Facult'es Universitaires N. D. de la Paix, 61 rue de Bruxelles, B-
5000, Namur, Belgium (as@math.fundp.ac.be). This work was supported by the Belgian National
Fund for Scientific Research.
own choice based on their knowledge of the problem (see [8], and [9]). In other cases,
the algorithm initializes the trust region radius to the distance to the Cauchy point
(see [13]), or to a multiple or a fraction of the gradient norm at the starting point
(see [8], and [9]). In each of these cases, the ITRR may not be adequate, and, even
if the updating strategies used thereafter generally allow to recover in practice from
a bad initial choice, there is usually some undesired additional cost in the number of
iterations performed. Therefore, the ITRR selection may be considered as important,
especially when the linear-algebra required per iteration is costly.
In this paper, we propose a simple but efficient way of determining the ITRR,
which consists of monitoring the agreement between the model and the objective
function along the steepest descent direction computed at the starting point. Further
improvements for the starting point will also be derived from the information gleaned
during this initializing phase. Numerical experiments, using a modified version of the
nonlinear optimization package LANCELOT (see [8]), on a set of relatively large test
examples from the CUTE test suite (see [1]), show the merits of the proposed strategy.
Section 2 of the paper develops the proposed automatic determination of a suitable
ITRR. The detailed algorithm is described in x3. Computational results are presented
and discussed in x4. We finally conclude in x5.
2. Automatic determination of an initial trust region.
2.1. Classical trust region update. We consider the solution of the unconstrained
minimization problem
The function f is assumed to be twice-continuously differentiable and a trust region
method is used, whose iterations are indexed by k, to solve this problem.
At iteration k, the quadratic model of f(x) around the current iterate x (k) is
denoted by
is a symmetric approximation of the Hessian
(Subsequently, we will use the notation f (k) and g (k) for f(x (k) )
and g(x (k) ), respectively.) The trust region is defined as the region where
Here \Delta (k) denotes the trust region radius and k \Delta k is a given norm.
When a candidate for the next iterate, x say, is computed that approximately
minimizes (2.2) subject to the constraint (2.3), a classical framework for the
trust region radius update is to set
for some selected fi (k) satisfying
In (2.5), the
quantity
represents the ratio of the achieved to the predicted reduction of the objective function.
The reader is referred to [8], [9], and [10] for instances of trust region updates using
(2.4)-(2.5).
2.2. Initial trust region determination. The problem in determining an ITRR
\Delta (0) is to find a cheap way to test agreement between the model (2.2) and the objective
function at the starting point, x (0) . The method presented here is based on the
use of information generally available at this point, namely the function value and
the gradient. With the extra cost of some function evaluations, a reliable ITRR will
be determined, whose use will hopefully reduce the number of iterations required to
find the solution. As shown in x4, the possible saving produced in most cases largely
warrants the extra cost needed to improve the ITRR.
The basic idea is to determine a maximal radius that guarantees a sufficient
agreement between the model and the objective function in the direction \Gammag (0) , using
an iterative search along this direction. At each iteration i of the search, given a
radius estimate \Delta (0)
i , the model and the objective function values are computed at
the point x
Writing
the ratio
ae (0)
is also calculated, and the algorithm then stores the maximal value among the estimates
whose associated ae (0)
' is "close enough to one" (following
some given criterion). It finally updates the current estimate \Delta (0)
The updating phase for \Delta (0)
i follows the framework presented in (2.4)-(2.5), but
includes a more general test on ae (0)
i because the predicted change in (2.8) (unlike that
in (2.6)) is not guaranteed to be positive. That is, we set \Delta (0)
for some Note that update (2.9) only takes the adequacy between
the objective function and its model into consideration, without taking care of the
minimization of the objective function f . That is, it may happen that the radius
estimate is decreased (fi (0)
i is not close enough to one (jae (0)
even though a big reduction is made in the objective function (if f
On the other hand, the radius estimate could
be augmented (fi (0)
i is close enough to one (jae (0)
when actually the objective function has increased (if f
for instance). This is not contradictory, as far as we forget temporarily about the
minimization of f and concentrate exclusively on the adequacy between the objective
function and its model to find a good ITRR. In the next section, we shall consider an
extra feature that will take account of a possible decrease in f during the process.
In order to select a suitable value for fi (0)
satisfying (2.9), a careful strategy
detailed below is applied, which takes advantage of the current available information.
This strategy uses quadratic interpolation (as already done in some existing framework
for trust region updates, see [9]), and has been inspired by the trust region updating
rules developed in [8].
The univariate function f(x
first modeled by the quadratic
i (fi) that fits f (0) , f (0)
, and the directional derivative \Gamma\Delta (0)
where d (0)
. Assuming that this quadratic does not coincide with the
univariate quadratic m (0)
used to provide candidates for fi (0)
which the ratio ae (0)
i would be close to one (slightly smaller and slightly larger than
one, respectively) if f were the quadratic q (0)
(fi). That is, equations
are solved (where ' ? 0 is a small positive constant), yielding candidates
and
respectively. These two candidates will be considered as possible choices for a suitable
satisfying (2.9), provided a careful analysis based on two principles is first
performed.
The first principle is to select and exploit, as much as possible, the relevant
information that may be drawn from fi (0)
i;1 and/or fi (0)
i;2 . For instance, if fi (0)
i;1 is greater
than one and the radius estimate must be decreased (because jae (0)
it should be ignored. The second principle consists in favouring the maximal value
for fi (0)
among the relevant ones. Based on the observation that the linear-algebraic
costs during a trust region iteration are generally less when the trust region has been
contracted (because part of the computation may be reused after a contraction but
not after an expansion), this corresponds to favour an ITRR choice on the large rather
than small side.
As in (2.9), we distinguish three mutually exclusive cases. The first case, for
which fi (0)
occurs when jae (0)
possibilities are
considered in this first case, that produce choice (2.14).
ffl Both fi (0)
i;1 and fi (0)
are irrelevant, that is, they recommend an increase of the
radius estimate while in this case, in reality it should be decreased. These
values are then ignored, and fi (0)
i is set to a fixed constant
ffl All the available relevant information provides a smaller value than the lower
bound fl 1 . Set fi (0)
ffl Either fi (0)
i;1 (or fi (0)
belongs to the appropriate interval, while fi (0)
i;2 (or fi (0)
respectively) is irrelevant or too small. The relevant one is selected.
ffl Both fi (0)
i;1 and fi (0)
i;2 are within the acceptable bounds. The maximum is then
chosen.
These possibilities yield:
if min(fi (0)
In the second case (i.e. when jae (0)
choice (2.15) is performed to
select a suitable fi (0)
based on the following reasoning.
ffl Both fi (0)
i;1 and fi (0)
are irrelevant because they recommend a decrease of the
radius estimate. fi (0)
i is set to a fixed constant
ffl At least one available piece of relevant information provides a larger value than
the upper bound fl 2 . Since any maximal pertinent information is favoured,
i is set to this bound.
ffl Either fi (0)
i;1 or fi (0)
i;2 belongs to the appropriate interval, while the other is
irrelevant. fi (0)
i is set to the relevant one.
ffl Both fi (0)
i;1 and fi (0)
i;2 are within the acceptable bounds. The maximum is then
selected.
This gives the following:
Finally, three situations are considered in the third case for selecting fi (0)
. Note that, since it is not clear from the value
of ae (0)
i that the radius estimate should be decreased or increased, fi (0)
i;1 and fi (0)
are
trusted and indicate if a decrease or an increase is to be performed.
ffl Both fi (0)
i;1 and fi (0)
i;2 advise a decrease of the radius estimate, but smaller than
the lower bound allowed. This lower bound, fl 3 , is then adopted.
ffl At least one among fi (0)
i;1 and fi (0)
i;2 recommends an increase of the radius es-
timate, but larger than the upper bound allowed, fl 4 . This upper bound is
used.
ffl The maximal value, max(fi (0)
belongs to the appropriate interval and
defines fi (0)
. The radius estimate is thus either increased or decreased, depending
on this value.
That is:
3. The algorithm. We are now in position to define our algorithm in full detail.
as used in (2.5), (2.9), (2.12) and (2.13), the ITRR
Algorithm depends on the constant - 0 ? 0. This one determines the lowest acceptable
level of agreement between the model and the objective function that must be reached
at a radius estimate to become a candidate for the ITRR.
The iterations of Algorithm ITRR will be denoted by the index i. While the
algorithm proceeds, \Delta max will record the current maximal radius estimate which
guarantees a sufficient agreement between the model and the objective function. Fi-
nally, the imposed limit on the number of iterations will be denoted by imax and
fixes the degree of refinement used to determine the ITRR.
ITRR Algorithm.
Step 0. Initialization. Let the starting point x (0) be given. Compute
and B (0) . Choose or compute an ITRR estimate \Delta (0)
0 and set
Step 1. Maximal radius estimate update. Compute
i as defined
in (2.7) and (2.8). If
set
Step 2. Radius estimate update. If i - imax, go to Step 3. Otherwise, compute
i;1 and fi (0)
using (2.12) and (2.13), respectively, compute
using
using
using (2.16) otherwise,
and set
Increment i by one and go to Step 1.
Step 3. Final radius update. If
Otherwise, set
Stop ITRR Algorithm.
The trust region algorithm may then begin, with \Delta (0) as ITRR.
We end this section by introducing an extra feature in the above scheme, which
takes advantage of the computations of f (0)
i , the function values at the trial points
(0) (see Step 1). That is, during the search of an improved radius estimate,
we simply monitor a possible decrease in the objective function at each trial point.
Doing so, at the end of Algorithm ITRR, rather than updating the final radius, we
move to the trial point that produced the best decrease in the objective function (if at
least one decrease has been observed). This point then becomes a new starting point,
at which Algorithm ITRR is repeated to compute a good ITRR. Of course, a limit is
needed on the number of times the starting point is allowed to change. Denoting by
this limit and by j the corresponding counter (initialized to one in Step 0), this
extra feature may be incorporated in Algorithm ITRR using two further instructions.
The first one, added at the end of Step 1, is
Here ffi denotes the current best decrease observed in the objective function and oe
stores the associated radius. (These two quantities should be initialized to zero in
Step 0). The second instruction, which comes at the beginning of Step 3, is
increment j by one and go to Step 0.
When starting a trust region algorithm with a rather crude approximation of the
solution, this kind of improvement, which exploits the steepest descent direction, may
be very useful. It is particularly beneficial when the cost of evaluating the function
is reasonable. A similar concept is used in truncated Newton methods (see [16], and
[17]).
Note that a change in the starting point requires the computation of a new gradient
and a new model, while the cost for determining the ITRR is estimated in
terms of function evaluations. Suitable choices for the limits imax and jmax and for
the constants used in Algorithm ITRR may depend on the problem type and will be
discussed in x4.
4. Numerical results. For a good understanding of the results, it is necessary
to give a rapid overview of the framework in which Algorithm ITRR has been embed-
ded, namely the large-scale nonlinear optimization package LANCELOT/SBMIN (see
[8]), designed for solving the bound-constrained minimization problem,
minimize x2R n f(x)
subject to the simple bound constraint
l - x - u;
where any of the bounds in (4.2) may be infinite.
SBMIN is an iterative trust region method whose version used for our testing has
the following characteristics:
ffl Exact first and second derivatives are used.
ffl The trust region is defined using the infinity norm in (2.3) for each k.
ffl The trust region update strategy follows the framework (2.4)-(2.5), and implements
a mechanism for contracting the trust region which is more sophisticated
than that for expanding it (see [8], p. 116).
ffl The solution of the trust region subproblem at each iteration is accomplished
in two stages. In the first, the exact Cauchy point is obtained to ensure a
sufficient decrease in the quadratic model. This point is defined as the first
local minimizer of m (k) (x (k) +d (k) (t)), the quadratic model along the Cauchy
arc d (k) (t) defined as
d
where l (k) , u (k) and the projection operator P (x; l are defined component-wise
by l (k)
l (k)
The Cauchy arc (4.3) is continuous and piecewise linear, and the exact Cauchy
point is found by investigating the model behaviour between successive pairs
of breakpoints (points at which a trust region bound or a true bound is
encountered along the Cauchy arc), until the model starts to increase. The
variables which lie on their bounds at the Cauchy point (either a trust region
bound or a true bound) are then fixed.
ffl The second stage applies a truncated conjugate gradient method (in which an
11-band preconditioner is used), to further reduce the quadratic model by
changing the values of the remaining free variables.
The reader is referred to [8], Chapter 3, for a complete description of SBMIN.
We selected our 77 test examples as the majority of large and/or difficult nonlinear
unconstrained or bound-constrained test examples in the CUTE (see [1]) collection.
Only problems which took excessive cpu time (more than 5 hours), or excessive number
of iterations (more than 1500), were excluded, since it was not clear that they
would have added much to the results. All experiments were made in double pre-
cision, on a DEC 5000/200 workstation, using optimized (-O) Fortran 77 code and
DEC-supplied BLAS.
The values for the constants of Algorithm ITRR used in our tests are
0:25. The values for
have been inspired from the trust region update strategy used in [8].
Suitable values for the other constants have been determined after extensive testing.
(Note that, fortunately, slight variations for these constants have no significant impact
on the behaviour of Algorithm ITRR). We set meaning that at most one
move is allowed in the starting point, and 4, such that 5 radius estimates
(including the first one) are examined per starting point. These values result from a
compromise between the minimum number of radius estimates that should be sampled
to produce a reasonable ITRR, and the maximum number of extra function evaluations
which may amount to (imax
4.1. The quadratic case. Before introducing our results for the general non-linear
case, a preliminary study of LANCELOT's behaviour on quadratic problems is
presented in this section, that is intended to enlighten some of the characteristics of
the specific trust region method implemented there. This should be helpful to set up
a more adequate framework, in which a reliable interpretation of our testing for the
general nonlinear case will become possible.
When the objective function f in problem (4.1)-(4.2) is a quadratic function,
model (2.2) is identical to f (since exact second derivatives are used in (2.2)). The
region where this model should be trusted is therefore infinite at any stage of a trust
region algorithm. Hence, a logical choice for the ITRR in that case is \Delta
ever, when no particular choice is specified by the user for the ITRR, LANCELOT does
not make any distinction when solving a quadratic problem and sets \Delta
On the other hand, equations in (2.11) have no solution for
(which is the case if f is a quadratic). There-
fore, in order to circumvent this possibility, the next instruction has been added in
Algorithm ITRR (before (3.1) in Step 1):
If ae (0)
and go to Step 3.
Note that this test does not ensure that f is a quadratic. If needed, a careful strategy
should rather be developed to properly detect this special situation.
In order to compare both issues, we have tested quadratic problems from the
collection, using LANCELOT with \Delta and with Algorithm ITRR
in which (4.4) has been added (see LAN and ITRR, respectively, in the tables below).
Results are presented in Tables 1 and 2 for a representative sample of quadratic problems
(6 unconstrained and 6 bound-constrained). In these tables and the following
ones, n denotes the number of variables in the problem, "#its" is the number of major
iterations needed to solve the problem, "#cg" reports the number of conjugate
gradient iterations performed beyond the Cauchy point, and the last column gives the
cpu times in seconds. Note that, for all the tests reported in this section, only one
additional function evaluation has been needed by Algorithm ITRR to set \Delta

Table
A comparison for the unconstrained quadratic problems.
LAN ITRR LAN ITRR LAN ITRR LAN ITRR
TESTQUAD 1000

Table

1 shows that, as expected, an infinite choice is the best when f is a quadratic
function, and the problem is unconstrained. On the other hand, a substantial increase
in the number of conjugate gradient iterations is observed in Table 2 (except for
problem TORSIONF) when bound constraints are imposed, while the number of
major iterations decreases. At first glance, these results may be quite surprising, but
they closely depend on the LANCELOT package itself. This package includes a branch,
after the conjugate gradient procedure, that allows re-entry of this conjugate gradient
procedure when the convergence criterion (based on the relative residual) has been
satisfied, but the step computed is small relative to the trust region radius and the
model's gradient norm. This is intended to save major iterations, when possible. In

Table
A comparison for the bound-constrained quadratic problems.
LAN ITRR LAN ITRR LAN ITRR LAN ITRR
the absence of bound constraints, this avoids an early termination of the conjugate
gradient process, allowing attainment of the solution in a single major iteration (see

Table

1). In the presence of bounds however, these (possibly numerous) re-entries
may not be justified as long as the correct set of active bounds has not yet been
identified. This behaviour is detailed in Table 3 for a sequence of increasing initial
radii, and exhibits, in particular, a high sensitivity to a variation of the ITRR, which
is a rather undesirable feature.

Table
A comparison for a sequence of increasing initial trust region radii with LANCELOT.
Problemn Initial radius \Delta (0)
#its
time
#its
OBSTCLAL 1024 #cg 48 55 70 76 93 117
time 14.64 15.73 18.52 18.28 20.97 24.75
#its 4 3 3 3 3 3
time 100.63 5.12 5.27 5.39 5.37 5.51
For comparison purposes, Tables 4 and 5 present the results when removing the
aforementioned branch in LANCELOT. This time, an infinitely large value for the
ITRR is justified. The conjugate gradient and timing results for Algorithm ITRR are
much closer to those of LANCELOT in Table 4 than in Table 2, with a slightly better
performance for problem OBSTCLAE and a slightly worse performance for problem
JNLBRNG1 (even though a clear improvement occurred due to the branch removal).
For problem JNLBRNG1 (as for others in our test set), a limited trust region acts as
an extra safeguard to stop the conjugate gradient when the correct active set is not
yet detected. This effect of the trust region may be considered as an advantage of
trust region methods.
In order to complete the above analysis, we now consider problem TORSIONF
in

Table

2. This problem is characterized by a very large number of active bounds
at the optimal solution, while most of the variables are free at the starting point.
Because of the very small ITRR, the identification process of the correct active set
during the Cauchy point determination is hindered. That is, during the early major
iterations, the trust region bounds are all activated at the Cauchy point, without
any freedom left for the conjugate gradient procedure. When the trust region has
been slightly enlarged, besides trust region bounds, some of the true bounds are also
identified by the Cauchy point, but much fewer than the number that would be the
case if the trust region was large enough. That is, the conjugate gradient procedure
in LANCELOT is restarted each time a true bound is encountered (which occurs at
almost every conjugate gradient iteration), in order to maintain the conjugacy between
the directions, and the iteration is stopped only when a trust region bound is
reached. All this produces extra linear-algebraic costs that greatly deteriorates the
algorithm's performance. On the other hand, when starting with a large ITRR, a
good approximation of the correct active set is immediately detected by the Cauchy
point, and very little work has to be performed during the conjugate gradient process.
This observation strengthens the priority given to a large choice for the ITRR, when
possible.

Table
A comparison for the bound-constrained quadratic problems (modified version).
Problemn #its #cg time
LAN ITRR LAN ITRR LAN ITRR

Table
A comparison for a sequence of increasing initial trust region radii with LANCELOT (modified ver-
sion).
Problemn Initial radius \Delta (0)
#its 9 6 6 6
time 33.43 30.38 30.57 30.33
#its 8 8 8 8
time 14.21 14.24 14.28 14.19
#its 5 4 4 4
time 102.02 5.66 5.61 5.55
In the light of the above analysis, we tested the 77 nonlinear problems with the
original version of LANCELOT versus a modified version, where the extra feature to
improve a too small step on output of the conjugate gradient process has been ignored.
Slight differences in the results have generally been observed, that were more often
in favour of the modified version. For this reason and in order to avoid an excessive
sensitivity of the method to the trust region size as well as preventing a large choice
for the ITRR (especially when this choice reflects a real adequacy between f and its
model), we decided to use the modified version for the testing of the nonlinear case
presented in the next section.
4.2. The general case. In order to test Algorithm ITRR, we ran LANCELOT
successively
ffl Algorithm ITRR, starting with \Delta (0)
computed by LANCELOT when no other choice
is made by the user);
(the distance to the unconstrained
Cauchy point, as suggested by Powell in [13]), except when the
quadratic model is indefinite, in wich case we omitted the test.
The detailed results are summarized in Tables 6 and 7 for the 64 unconstrained
problems (possibly including some fixed variables), and in Table 8 for the 13 bound-
constrained problems (see ITRR, LAN and CAU, respectively). For each case, the
number of major iterations ("#its") and the cpu times in seconds ("time") are re-
ported. Note that the number of function evaluations may then be easily deduced :
for LANCELOT without Algorithm ITRR, it is the number of major iterations plus 1,
while for LANCELOT with Algorithm ITRR, it is the number of major iterations plus
12 if the starting point is refined once (what is pointed out by an asterisk in the first
column), and plus 6 otherwise. The tables also present the relative performances for
the number of function evaluations, the number of major iterations and the cpu times
(see "%f", "%its", and "%time", respectively), computed as
\Theta 100 and
\Theta 100;
where "?" is, in turn, the number of function evaluations, "#its", and "time". In
these tables, a "+" indicates when the performance is in favour of Algorithm ITRR
and a "\Gamma" when not. Note that a difference of less than five percent in the cpu times
is regarded as insignificant.
The results first show that, all in all, Algorithm ITRR improves the overall cpu
time performance of LANCELOT for a large number of problems:
improvements against 13 deteriorations and ties when comparing with
improvements against 19 deteriorations and 12 ties when comparing with
CAU.
More importantly, when they exist, these improvements may be quite significant (19
of them are greater than 30% when comparing with LAN, while 21 of them are greater
than 30% when comparing with CAU), and confirm the impact the ITRR choice may
have on the method behaviour. On the other hand, the damage is rather limited
when it occurs (except for a few cases). Note that the larger number of improvements
observed when comparing with LAN does not mean that the ITRR computed by
LANCELOT is worse than the distance to the unconstrained Cauchy point. Actually,
the improvements when comparing Algorithm ITRR with CAU are generally more
significant, and the results show that, on average, LAN and CAU may be considered
as equivalent (when compared together).
As pointed out by the number of asterisks in the first column of Tables 6 to 8,
a change in the starting point occurs very often and makes a significant contribution
to the good performance observed. Columns 4 and 7 detail the relative extra cost in
terms of function evaluations produced by Algorithm ITRR. Note that, in the current
case where the starting point is refined once, the (fixed) extra cost incurs up to 11
extra function evaluations, which is quite high on average, compared with the total
number of function evaluations. However, considering the relative performance in the
cpu times, the extra cost is generally covered, sometimes handsomely, by the saving
produced in the number of major iterations (that is, when %its is positive, %time is
generally positive too). Only few cases produce a saving that just balances the extra
A comparison for the unconstrained problems.
Problemn ITRR LAN CAU ITRR LAN CAU
#its #its %f %its #its %f %its time time %time time %time
BROYDN7D  92 74 \Gamma39 \Gamma24 73 \Gamma41 \Gamma26 87.8 72.5 \Gamma21 71.1 \Gamma23
BRYBND  14
DQRTIC 1000 28 28 \Gamma17 0 28 \Gamma17 0 18.3 18.2 1 18.2 1
ERRINROS  59 67 \Gamma4 +12 68 \Gamma3 +13 2.9 3.2 +9 3.1 +6
GENROSE  1194 1290 +7 +7 1100 \Gamma10 \Gamma9 1023.8 1115.6 +8 920.3 \Gamma11
LIARWHD  14
LMINSURF  306 272 \Gamma16 \Gamma12 157 \Gamma101 \Gamma95 412.4 380.8 \Gamma8 279.7 \Gamma47
MSQRTALS
MSQRTBLS  31 34 \Gamma23 +9 6573.9 6925.5 +5
A comparison for the unconstrained problems (end).
Problemn ITRR LAN CAU ITRR LAN CAU
#its #its %f %its #its %f %its time time %time time %time
NONDIA 1000
POWER 1000
28 28 \Gamma17 0 28 \Gamma17 0 18.3 18.2 1
RAYBENDS  70 52 \Gamma55 \Gamma35

Table
A comparison for the bound\Gammaconstrained problems.
Problemn ITRR LAN CAU ITRR LAN CAU
#its #its %f %its #its %f %its time time %time time %time
4.3 5.6 +23 9.0 +52
QRTQUAD  118 173 +25 +32 315 +59 +63 11.9 16.2 +27 28.4 +58
function evaluations (see the problems for which %its ? 0 and 0 - %time ! 5), while
never a saving occurs which does not counterbalance the additional work. On the other
hand, when a deterioration occurs in the cpu times (%time ! 0), it is rarely due to
the extra cost of Algorithm ITRR exclusively (%its = 0). As a consequence, excepting
when functions are very expensive, the use of Algorithm ITRR may be considered
efficient and relatively cheap compared with the overall cost of the problem solution.
We have observed that only 4 problem tests terminated Algorithm ITRR using
update (3.3), while a successful maximal radius satisfying condition (3.1) was selected
in the 73 other cases. We also experimented with a simpler choice for fi (0)
when ae (0)
i is close enough to one and fi (0)
that resulted in a markedly
performance compared with that of Algorithm ITRR. This proves the necessity
of a sophisticated selection procedure for fi (0)
i , that allows a swift recovery from a bad
initial value for the ratio ae (0)
We conclude this analysis by commenting on the negative results of Algorithm
ITRR on problem TQUARTIC (see Table 7), when comparing with CAU, and on
problem LINVERSE (see Table 8), especially when comparing with LAN. For problem
TQUARTIC (a quartic), the ITRR computed by both LANCELOT and Algorithm
ITRR is quite small and prevents from doing rapid progress to the solution.
The trust region hence needs to be enlarged several times during the minimization
algorithm. On the other hand, the distance to the Cauchy point is sufficiently large
to allow solving the problem in one major iteration. For problem LINVERSE, the
ITRR selected by Algorithm ITRR corresponds to an excellent agreement between the
function and the model in the steepest descent direction. However, the starting point
produced by Algorithm ITRR, although reducing significantly the objective function
value, requires more work from the trust region method to find the solution. This is
due to a higher nonlinearity of the objective function in the region where this new
point is located and is, in a sense, just bad luck! When testing Algorithm ITRR
with this problem, the same ITRR as LANCELOT had been selected,
hence producing the same performance. On the other hand, we also tested a series
of slightly perturbed initial trust region radii, and observed a rapid deterioration of
the performance of the method. Problem LINVERSE is thus very sensitive to the
ITRR choice. Note that this sensitivity has been observed on other problems during
our testing, and leads to the conclusion that a good ITRR sometimes may not be a
sufficient condition to guarantee an improvement of the method.
We finally would like to note that no modification has been made in Algorithm
ITRR (nor a constrained Cauchy point for CAU has been considered), when solving the
bound-constrained problems reported in the paper. The purpose here was simply to
illustrate the proposed method on a larger sample than only unconstrained problems.
Of course, the author is aware that in the presence of bound constraints, a more
reliable version of Algorithm ITRR should include a projection of each trial point onto
the bound constraints.
We end this section by briefly commenting on the choice of the constants and
upper bounds on the iteration counters of Algorithm ITRR. Although a reasonable
choice has been used for the testing presented in this paper, a specific one could be
adapted depending on the a priori knowledge of a given problem. If, for instance,
function evaluations are costly, a lower value for the bounds imax and jmax could
be selected. Note however that imax should not be chosen excessively small, in order
to be fairly sure that condition (3.1) will be satisfied (unless this condition is suitably
relaxed by choosing the value of - 0 ). On the other hand, if the starting point is
known to be far away from the solution, it may be worthwhile to increase the value of
jmax, provided the function is cheap to evaluate. Improved values for the remaining
constants closely depend on a knowledge of the level of
nonlinearity of the problem.
5. Conclusions and perspectives. In this paper, we propose an automatic
strategy to determine a reliable ITRR for trust region type methods. This strategy
mainly investigates the adequacy between the objective function and its model in the
steepest descent direction available at the starting point. It further includes a specific
method for refining the starting point by exploiting the extra function evaluations
performed during the ITRR search.
Numerical tests are reported and discussed, showing the efficiency of the proposed
approach and giving additional insights to trust region methods for unconstrained and
bound-constrained optimization. The encouraging results suggest some direction for
future research, such as the use of a truncated Newton direction computed at the
starting point rather than the steepest descent direction for the search of an ITRR.
An adaptation of the algorithm for methods designed to solve general constrained
problems is presently being studied.

Acknowledgement

. The author wishes to thank an anonymous referee for suggesting
a comparison of Algorithm ITRR with the choice of setting the ITRR to the
distance to the Cauchy point (as in [13]). Thanks are also due to Andy Conn, Nick
Gould, Philippe Toint and Michel Bierlaire who contributed to improve the present
manuscript.



--R

CUTE: Constrained and Unconstrained Testing Environment

A trust region algorithm for nonlinearly constrained optimization

A trust region strategy for nonlinear equality constrained optimization
Global convergence of a class of trust region algorithms for optimization using inexact projections on convex constraints
Global convergence of a class of trust region algorithms for optimization with simple bounds

Numerical methods for unconstrained optimization and nonlinear equations
Practical Methods of Optimization: Unconstrained Optimization


A Fortran subroutine for solving systems of nonlinear algebraic equations


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
--TR

--CTR
Wenling Zhao , Changyu Wang, Value functions and error bounds of trust region methods, Journal of Applied Mathematics and Computing, v.24 n.1, p.245-259, May 2007
Stefania Bellavia , Maria Macconi , Benedetta Morini, An affine scaling trust-region approach to bound-constrained nonlinear systems, Applied Numerical Mathematics, v.44 n.3, p.257-280, February
Nicholas I. M. Gould , Dominique Orban , Philippe L. Toint, CUTEr and SifDec: A constrained and unconstrained testing environment, revisited, ACM Transactions on Mathematical Software (TOMS), v.29 n.4, p.373-394, December
initial trust region;trust region methods;numerical results;nonlinear optimization