Line search algorithms with guaranteed sufficient decrease.
The development of software for minimization problems is often based on a line search method. We consider line search methods that satisfy sufficient decrease and curvature conditions, and formulate the problem of determining a point that satisfies these two conditions in terms of finding a point in a set T(&mgr;).  We describe a search algorithm for this problem that produces a sequence of iterates that converge to a point in T(&mgr;) and that, except for pathological cases, terminates in a finite number of steps. Numerical results for an implementation of the search algorithm on a set of test functions show that the algorithm terminates within a small number of iterations.
Introduction
Given a continuously differentiable function OE defined on [0; 1) with OE 0
and constants - and j in (0; 1), we are interested in finding an ff ? 0 such that
and
The development of a search procedure that satisfies these conditions is a crucial ingredient
in a line search method for minimization. The search algorithm described in this paper has
been used by several authors, for example, Liu and Nocedal [10], O'Leary [12], Schlick and
Fogelson [14, 15], and Gilbert and Nocedal [7]. This paper describes this search procedure
and the associated convergence theory.
In a line search method we are given a continuously differentiable function f :
and a descent direction p for f at a given point x 2 IR n . Thus, if
then (1.1) and (1.2) define an acceptable step. The motivation for requiring conditions (1.1)
and (1.2) in a line search method should be clear. If ff is not too small, condition (1.1) forces
a sufficient decrease in the function. However, this condition is not sufficient to guarantee
convergence, because it allows arbitrarily small choices of ff ? 0. Condition (1.2) rules out
arbitrarily small choices of ff and usually guarantees that ff is near a local minimizer of OE.
Condition (1.2) is a curvature condition because it implies that
and thus the average curvature of OE on (0; ff) is positive. The curvature condition (1.2)
is particularly important in a quasi-Newton method because it guarantees that a positive
definite quasi-Newton update is possible. See, for example, Dennis and Schnabel [4] and
Fletcher [6].
Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy
Research of the U.S. Department of Energy under Contract W-31-109-Eng-38.
Permanent address: Department of Mathematical Sciences, Indiana-Purdue University, Fort Wayne,
Indiana 46805.
As final motivation for the solution of (1.1) and (1.2), we mention that if a step satisfies
these conditions, then the line search method is convergent for reasonable choices of
direction. See, for example, Dennis and Schnabel [4] and Fletcher [6] for gradient-related
methods; Powell [13] and Byrd, Nocedal, and Yuan [3] for quasi-Newton methods; and Al-
Baali [1], Liu and Nocedal [10], and Gilbert and Nocedal [7] for conjugate gradient methods.
In most practical situations it is important to impose additional requirements on ff. In
particular, it is natural to require that ff satisfy the bounds
The main reason for requiring a lower bound ff min is to terminate the iteration, while the
upper bound ff max is needed when the search is used for linearly constrained optimization
problems or when the function OE is unbounded below. In linearly constrained optimization
problems the parameter ff max is a function of the distance to the nearest active constraint.
An unbounded problem can be approached by accepting any ff in [ff min ; ff max ] such that
is a lower bound specified by the user of the search. In
this case
is a reasonable setting because if ff max satisfies the sufficient decrease condition (1.1), then
. On the other hand, if ff max does not satisfy the sufficient decrease
condition, then we will show that it is possible to determine an acceptable ff.
The main problem that we consider in this paper is to find an acceptable ff in the sense
that ff belongs to the set
By phrasing our results in terms of T (-) we make it clear that the search algorithm is
independent of j; the parameter j is used only in the termination test of the algorithm.
Another advantage of phrasing the results in terms of T (-) is that T (-) is usually not
empty. For example, T (-) is not empty when OE is bounded below.
Several authors have done related work on the solution of (1.1) and (1.2). For example,
Gill and Murray [8] attacked (1.1) and (1.2) by using a univariate minimization algorithm
for OE to find a solution ff   to (1.2). If ff   did not satisfy (1.1), then ff   was repeatedly halved
in order to obtain a solution fi   to (1.1). Of course, fi   did not necessarily satisfy (1.2); but
if - was sufficiently small, then it was argued that this was an unlikely event. In a similar
vein, we mention that the search algorithm of Shanno and Phua [16, 17] is not guaranteed
to work in all cases. In particular, the sufficient decrease condition (1.1) can rule out many
of the points that satisfy (1.2), and then the algorithm is not guaranteed to converge.
Gill, Murray, Saunders, and Wright [9] proposed an interesting variation on (1.1) and
(1.2) when they argued that if there is no solution to (1.1) and (1.2), then it was necessary
to compute a point such that
If (1.6) has a solution, then their algorithm computes a sequence of nested intervals such
that each interval contains points that satisfy (1.1) and (1.2), or just (1.6). Their algorithm,
however, is not guaranteed to produce a point that satisfies (1.1) and (1.2).
Fletcher [5] suggested that it is possible to compute a sequence of nested intervals that
contain points that satisfy (1.1) and (1.2), but he did not prove any result along these lines.
This suggestion led to the algorithms developed by Al-Baali and Fletcher [2] and Mor'e and
Sorensen [11]. In this paper we provide a convergence analysis, implementation details, and
numerical results for the algorithm of Mor'e and Sorensen [11].
The search algorithm for T (-) is defined in Section 2. We show that the search algorithm
produces a sequence of iterates that converge to a point in T (-) and that, except for
pathological cases, the search algorithm produces a finite sequence ff of trial values
in [ff min ; ff or is one of the bounds. Termination at one of the bounds
can be avoided by a suitable choice of bounds. For example, if ff defined
by (1.5), then either ff m lies in T (-) or OE(ff m ) - OE min .
The results of Section 2 show that the search algorithm can be used to find an ff that
satisfies (1.1) and (1.2) when - j. A result for an arbitrary j 2 (0; -) requires additional
assumptions because there may not be an ff that satisfies (1.1) and (1.2) even if OE is bounded
below. In Section 3 we show that if the search algorithm generates an iterate ff k that satisfies
the sufficient decrease condition and OE 0 (ff k ) ? 0, then the search algorithm terminates at
an ff k that satisfies (1.1) and (1.2).
Given ff 0 in [ff min ; ff max ], the search algorithm generates a sequence of nested intervals
and a sequence of iterates ff k 2 I k "[ff min ; ff max ]. Section 4 describes the specific choices
for the trial values ff k that are used in our algorithm. Our numerical results indicate that
these choices lead to fast termination.
Section 5 describes a set of test problems and numerical results for the search procedure.
The first three functions in the test set have regions of concavity, while the last three
functions are convex. In all cases the functions have a unique minimizer. The emphasis
in the numerical results is to explain the qualitative behavior of the algorithm for a wide
range of values of - and j.
2 The Search Algorithm for T (-)
In this section we present the search algorithm for determining an ff in T (-). We assume
that OE is continuously differentiable on [0; ff Most work on line searches
assumes that - ! 1, because if OE is a quadratic with OE 0 then the
global minimizer ff   of OE satisfies
OE(ff
and thus ff   satisfies (1.1) only if - 1. The restriction - ! 1also allows to be
ultimately acceptable to Newton and quasi-Newton methods. In this section we need only
assume that - lies in (0; 1).
Given ff 0 in [ff min ; ff max ], the search algorithm generates a sequence of nested intervals
and a sequence of iterates ff k 2 I according to the following procedure.
Search Algorithm. Set I
For
Choose a safeguarded ff k 2 I
Test for convergence.
Update the interval I k .
In this description the term safeguarded ff k refers to the rules that force convergence of the
algorithm. For the moment we assume that a safeguarded choice is made, and discuss the
updating of I k .
The aim of the updating process for the intervals I k is to identify and generate an interval
I k such that T (-) " I k is not empty, and then refine the interval so that T (-) " I k remains
not empty. We now specify conditions on the endpoints of an interval I that guarantee that
I has a nonempty intersection with T (-). The conditions on the endpoints ff l and ff u are
specified in terms of the auxiliary function / defined by
We assume that ff l 6= ff u but do not assume that ff l and ff u are ordered.
Theorem 2.1 Let I be a closed interval with endpoints ff l and ff u . If the endpoints satisfy
then there is an ff   in I with /(ff   In particular, ff   2 (T (-) " I).
Proof. Assume that ff u ? ff l ; the proof in the other case is similar. Define
first claim that /(ff m ) - /(ff l ). The assumption
on ff u shows that this is certainly the case if ff This also holds if ff m ! ff u , because
in this case the definition of ff m implies that /(ff m
to be a global minimizer of / on [ff l ; ff m ]. We claim that ff   2 T (-). The
global minimum cannot be achieved at ff l because / 0 (ff l since we have established
that l ), the global minimum cannot be achieved at ff m . Hence, ff   is in the
interior of [ff l In particular, / 0 (ff
that ff   satisfies (1.1) because /(ff) - 0 for all ff in [ff l ; ff m ]. Hence, ff   2 T (-), as desired.
Theorem 2.1 provides the motivation for the search algorithm by showing that if the
endpoints of I satisfy (2.1), then / has a minimizer ff   in the interior of I and, moreover,
that ff   belongs to T (-). Thus the search algorithm can be viewed as a procedure for
locating a minimizer of /.
The assumptions that Theorem 2.1 imposes on the endpoints ff l and ff u cannot be
relaxed because if we fix ff l and ff u by the assumption /(ff l ) - /(ff u ), then the result fails
to hold if either of the other two assumptions are violated. The assumptions (2.1) can be
paraphrased by saying that ff l is the endpoint with lowest / value, that ff l satisfies the
sufficient decrease condition (1.1), and that ff u \Gamma ff l is a descent direction for / at ff l so
that /(ff) ! /(ff l ) for all ff in I sufficiently close to ff l . In particular, this last assumption
guarantees that / can be decreased by searching near ff l .
We now describe an algorithm for updating the interval I , and then show how to use
this algorithm to obtain an interval that satisfies the conditions of Theorem 2.1.
Updating Algorithm. Given a trial value ff t in I , the endpoints ff
l and ff
u of the
updated interval I + are determined as follows:
Case U1: If /(ff
Case U2: If /(ff t
Case U3: If /(ff t
It is straightforward to show that if the endpoints ff l and ff u satisfy (2.1), then the updated
l and ff
course, in
this case there is no need to update I because ff t belongs to T (-).
Al-Baali and Fletcher [2] present two updating schemes. The aim of scheme S1 is to
identify a point that satisfies (1.1) and OE 0 (ff) - jOE 0 (0), while scheme S2 seeks a point that
satisfies (1.1) and (1.2). In scheme S2 the endpoints ff
l and ff
are determined as follows:
else if OE 0 (ff t )(ff l \Gamma ff
else
The two updating algorithms produce the same iterates as long as
but differ in their treatment of the situation where
In this case, our updating algorithm chooses I
Our algorithm seems to be preferable in this situation because the interval I
contains an acceptable point, while the interval generated by scheme S2 is not guaranteed
to contain an acceptable point.
We now show how the updating algorithm can be used to determine an interval I in
with endpoints that satisfy (2.1). Initially ff 1. Consider any
trial value ff t in [ff min ; ff max ]. If cases U1 or U3 hold, then we have determined an interval
with endpoints ff l and ff u that satisfy the conditions of Theorem 2.1. Otherwise case U2
holds, and we can repeat the process for some ff
t in [ff t ; ff max ]. We continue generating
trial values in [ff l ; ff max ] as long as case U2 holds, but require that eventually ff max be used
as a trial value. This is done by choosing
for some factor In our implementation we use
and thus an induction argument shows that (2.2) holds with
initially and the sequence ff of trial values is increasing
with
as long as case U2 holds. The search algorithm terminates at ff max if /(ff
This is a reasonable termination criterion because Theorem 2.1 shows that
when these conditions do not hold there is an ff   2 T (-) with ff   - ff max . Thus, after a
finite number of trial values, either the search algorithm terminates at ff max , or the search
algorithm generates an interval with endpoints that satisfy conditions (2.1).
Given an interval that satisfies conditions (2.1), the search algorithm uses the updating
algorithm to refine I . We claim that if the search algorithm does not generate an interval
I in [ff min ; ff max ] that satisfies conditions (2.1), then the sequence fff k g of trial values is
decreasing with
This claim is established by considering all three cases of the updating algorithm. If we
use an ff t with /(ff t case U2 or U3 holds, then the updating
algorithm shows that the interval I + lies to the right of ff t . Since ff t - ff min , the interval
I contains [ff min ; ff max ]. If case U1 holds, then /(ff l thus ff l - ff min . Hence, the
updated interval contains [ff min ; ff max ].
We force the search algorithm to use ff min as a trial value when (2.4) holds and ff min ? 0.
This is done by choosing
for some factor ffi min ! 1. In our implementation (2.5) holds with 7. For more
details, see Section 4.
The search algorithm terminates at ff min if /(ff min This is a
reasonable termination criterion because Theorem 2.1 shows that there is an ff   2 T (-)
with ff   - ff min when these conditions hold. Thus, after a finite number of trial values,
either the search algorithm terminates at ff min , or the search algorithm generates an interval
I in [ff min ; ff max ] with endpoints that satisfy conditions (2.1).
The requirements (2.2) and (2.5) are two of the safeguarding rules. Note that (2.2) is
enforced only when (2.3) holds, while (2.5) is used when (2.4) holds. If the search algorithm
generates an interval I in [ff min ; ff max ], then we need a third rule to guarantee that the
choice of ff t forces the length of I to zero. In our implementation this is done by monitoring
the length of I ; if the length of I does not decrease by a factor of after two trials,
then a bisection step is used for the next trial ff t . In our implementation we use
Theorem 2.2 The search algorithm produces a sequence fff k g in [ff min ; ff max ] such that
after a finite number of trial values one of the following conditions hold.
The search terminates at ff max , the sequence of trial values is increasing, and (2.3) holds.
The search terminates at ff min , the sequence of trial values is decreasing, and (2.4) holds.
An interval I k ae [ff min ; ff max ] is generated.
Proof. In this proof we essentially summarize the arguments presented above. Let ff (k)
l and
u be the endpoints of I k , and define
The left endpoint fi (k)
l of I k is nondecreasing, while the right endpoint is nonincreasing.
We first show that fi (k)
hold for all k - 0. If fi (k)
case U2
of the updating algorithm holds because in the other two cases both endpoints are set to
finite values. Since only case U2 holds, it is clear that (2.3) holds, and thus the safeguarding
rule (2.2) shows that the bound ff max is eventually used as a trial value. If the search does
not terminate at ff max , then fi (k)
A similar argument shows that fi (k)
hold for all k - 0. If fi (k)
only case U1 or U3 of the updating algorithm holds because in case U2 both endpoints are
set to positive values. Moreover, in this case (2.4) holds. The safeguarding rule (2.5) shows
that (2.4) cannot hold for all k - 0 when ff and that if ff min ? 0, then ff min is
eventually used as a trial value. If the search does not terminate at ff min , then fi (k)
We have thus shown that after a finite number of trial values, either the search terminates
at one of the two bounds ff min or ff max , or fi (k)
l ? 0 and fi (k)
course, in this last
case I k is a subset of [ff min ; ff max ]. \Xi
The most interesting case of Theorem 2.2 occurs when an interval I k ae [ff min ; ff
is generated. In this case the safeguarding rules guarantee that the length of the intervals
converges to zero, and thus the sequence fff k g converges to some ff   in T (-).
We can rule out finite termination at one of the bounds by ruling out (2.3) and (2.4).
The simplest way to do this is to assume that ff min satisfies
and that ff max satisfies
Under these assumptions, Theorem 2.2 shows that an interval I k ae [ff min ; ff max ] is generated
after a finite number of trial values.
Conditions (2.6) and (2.7) can be easily satisfied. For example, if ff
holds. Condition (2.7) holds if ff max is defined by (1.5) and OE min is a strict lower bound for
OE. Condition (2.7) also holds if OE 0 (ff
Theorem 2.3 If the bounds ff min and ff max satisfy (2.6) and (2.7), then the search algorithm
terminates in a finite number of steps with an ff k 2 T (-), or the iterates fff k g
converge to some ff   2 T (-) with / 0 (ff   If the search algorithm does not terminate
in a finite number of steps, then there is an index k 0 such that the endpoints ff (k)
l , ff (k)
u of
the interval I k satisfy ff (k)
u . Moreover, if /(ff   changes sign on
changes sign on [ff (k)
for all k - k 0 .
Proof. Assume that ff
all the iterates generated by the search algorithm. Since
the intervals I k are uniformly bounded and their lengths tends to zero, any sequence f' k g
with must converge to a common limit ff   . Theorem 2.1 guarantees that there is a
This implies that ff   2 T (-) and that
In particular, / 0 (ff
We define k 0 by noting that the continuity of OE 0 shows that there is a k 0 ? 0 such that
l
must have
l )j ? -jOE 0 (0)j. We also know that OE 0 (ff (k)
l
l
Hence,
l Condition (2.1) on the endpoints implies that ff (k)
u , and in
particular, ff (k)
Now consider the case where /(ff
this implies that /(ff (k)
l we have shown that / 0 changes sign on [ff (k)
Finally, consider the case where /(ff   Assume that k 0 is such that /(ff (k)
for all k - k 0 . If / 0 (ff (k)
(0), and since OE 0 (ff (k)
contradiction shows that / 0 (ff (k)
We have already shown that
l changes sign on [ff (k)
This is clear because if / 0 (ff) - 0 on [ff (k)
If the search algorithm does not terminate in a finite number of steps, then Theorem 2.3
implies that / 0 changes sign an infinite number of times in the sense that there is a monotone
sequence that converges to ff   and such that / 0 (fi k )/ 0 (fi Theorem 2.3 thus
justifies our claim that, except for pathological cases, the search algorithm terminates in a
finite number of iterations. Closely related results have been established by Al-Baali and
Fletcher [2] and Mor'e and Sorensen [11]. In these results, however, the emphasis is on
showing that the search algorithm eventually generates an ff k that satisfies (1.1) and (1.2)
3 Search for a Local Minimizer
Theorem 2.3 guarantees finite termination at an ff k that satisfies (1.1) and (1.2) provided
-. In this section we modify the search algorithm and show that under reasonable
conditions we can guarantee that the modified search algorithm generates an ff k that satisfies
(1.1) and (1.2) for any j ? 0.
A difficulty with setting - is that, even if T (-) is not empty, there may not be an
that satisfies (1.1) and (1.2). We illustrate this point with a minor modification of
an example of Al-Baali and Fletcher [2]. Define
-. The solid plot in Figure 3.1 is the function OE with the dashed
plot is the function computation shows that OE is
-0.4
-0.3
-0.2

Figure

3.1: Solid plot is OE; dotted plot is
continuously differentiable and that
for all ff - 0. Moreover, if - ! 1, then
Thus T (-) is a nonempty interval with in the interior. In Figure 3.1 we have set
We now show that if during the search for T (-) we compute a trial value ff k such that
belongs to T (-) or we have identified an interval
that contains points that satisfy the sufficient decrease condition (1.1) and the curvature
condition (1.2).
Theorem 3.1 Assume that the bounds ff min and ff max satisfy (2.6) and (2.7). Let fff k g
be the sequence generated by the search algorithm, and let ff (k)
l and ff (k)
u be the endpoints of
the interval I k generated by the search algorithm. If ff k is the first iterate that satisfies
then ff (k)
then the interval
I   j
contains an ff   that satisfies (1.1) and OE 0 (ff
also satisfies (1.1).
Proof. We first claim that / 0 (ff (k)
l this is not the case, then / 0 (ff
l is a previous iterate. However, this contradicts the assumption
that ff k is the first iterate that satisfies (3.2). This proves that / 0 (ff (k)
l
l assumptions (2.1) imply that ff (k)
u . This implies, in particular,
that
l so I   is well defined.
If then it is clear that jOE 0 (ff k )j -jOE 0 (0)j. Since /(ff k ) - 0,
this implies that ff k 2 T (-).
Now assume that OE 0 (ff k ) ? 0, and let ff   be a global minimizer of OE on I   . Since OE 0 (ff
0 and ff   is a minimizer, ff   6= ff k . Similarly, since we proved above that / 0 (ff (k)
l
ff   is a minimizer, ff   6= ff (k)
l .
We have shown that ff   is in the interior of I   . Hence, OE 0 (ff   We
complete the proof by noting that if OE(ff) - OE(ff k ) for some ff 2 I   , then
The second inequality holds because ff k satisfies (1.1), while the third inequality holds
because ff - ff k . Hence, any ff 2 I   with OE(ff) - OE(ff k ) also satisfies (1.1). \Xi
There is no guarantee that the search algorithm will generate an iterate ff k such that
example, if OE is the function shown in Figure 3.1, then
if OE has a minimizer ff   that satisfies the sufficient decrease
condition, the search algorithm may be trapped in a region that contains points in T (-),
but where (1.1) and (1.2) are not satisfied.
Theorem 3.1 is one of the ingredients needed to develop a search algorithm for a minimizer
that satisfies the sufficient decrease condition (1.1) and the curvature condition (1.2).
We also need to show that the interval I   specified by Theorem 3.1 satisfies the assumptions
of the following result.
Theorem 3.2 Let I be a closed interval with endpoints ff l and ff u . If the endpoints satisfy
then there is an ff   in I with OE(ff
Proof. The proof of this result is almost immediate. If ff   is the global minimizer of OE on
I , then the assumptions on ff l and ff u guarantee that ff   is in the interior of I and thus
The interval I   specified by Theorem 3.1 satisfies the assumptions of Theorem 3.2 because
the derivative of OE has the proper sign at the endpoints. We assumed that OE 0 (ff
Moreover, in Theorem 3.1 we established that ff (k)
u , and thus assumptions (2.1) on
the endpoints of I k imply that / 0 (ff (k)
l
l These two results show
that I   has the desired properties.
We now need to modify the updating algorithm so that we can guarantee finite termination
at an iterate that satisfies the sufficient decrease condition (1.1) and the curvature
condition (1.2). The modification is simple; we just replace / by OE in the updating algorithm

Modified Updating Algorithm. Given a trial value ff t in I , the endpoints ff
l and ff
of the updated interval I + are determined as follows:
Case a: If OE(ff
Case b: If OE(ff t
Case c: If OE(ff t
We have shown that the interval I   specified by Theorem 3.1 satisfies the assumptions of
Theorem 3.2. Moreover, a short computation shows that if I is any interval that satisfies
the assumptions of Theorem 3.1, then the modified updating algorithm preserves these
assumptions.
Our implementation of the search algorithm of Section 2 uses the modified updating
algorithm in an obvious manner: If some iterate ff k satisfies /(ff k
then the modified updating algorithm is used on that iteration and all further iterations.
Theorem 3.3 Assume that the bounds ff min and ff max satisfy (2.6) and (2.7). If the modified
search algorithm generates an iterate such that /(ff k then the
modified search terminates at an ff k that satisfies (1.1) and (1.2).
Proof. If the search algorithm generates an ff k with /(ff k
Theorem 3.1 shows that ff k ? ff (k)
l , and thus the modified updating algorithm sets
I
because case U2 does not hold. Moreover, Theorem 3.1 guarantees that any ff 2 I k+1 with
This implies that for any iteration j ? k the endpoint ff (j)
l
satisfies (1.1). We also know that any sequence f' k g with ' k 2 I k must converge to a
common limit ff   . Since Theorem 3.2 shows that there is a ' k 2 I k such that OE 0 (' k
we obtain that OE 0 (ff
l satisfies (1.2) for all j ? k sufficiently large. This
proves that the modified search terminates at an iterate that satisfies (1.1) and (1.2). \Xi
4 Trial Value Selection
Given the endpoints ff l and ff u of the interval I , and a trial value ff t in I , the updating algorithm
described in the preceding section produces an interval I + that contains acceptable
points. We now specify the new trial value ff
t in I + .
We assume that in addition to the endpoints ff l and ff u , and the trial point ff t , we
have function values f l ; f derivatives . The function values f l ; f
derivatives t can be obtained from either the function OE or the auxiliary function /.
The function and derivative values are obtained from the auxiliary function / until some
iterate satisfies the test /(ff k Once this test is satisfied, OE is used.
We have divided the trial value selection in four cases. In the first two cases we choose
t by interpolating the function values at ff l and ff t so that the trial value ff
lies between
ff l and ff t . We define ff
t in terms of ff c (the minimizer of the cubic that interpolates f l , f t ,
l , and g t ), ff q (the minimizer of the quadratic that interpolates f l , f t , and g l ), and ff s (the
minimizer of the quadratic that interpolates g l and g t ).
Case 1: f t ? f l . In this case compute ff c , ff q , and set
Both ff c and ff q lie in I + so they are both candidates for ff
t . We desire a choice that is close
to ff l since this is the point with the lowest function value. Both ff q and ff c are relatively
close to ff l because
Thus, for the above choice of ff
A choice close to ff l is clearly desirable when f t is much larger than f l . In this case the
quadratic step is closer to ff l than ff c , but usually abnormally so. Indeed, if ff q (f t ) is the
value of ff q as a function of f t , then
lim
On the other hand, a computation shows that
lim
Thus, the midpoint of ff c and ff t is a reasonable compromise.
Case 2: f t - f l and g t g l ! 0. In this case compute ff c , ff s , and set
ff s otherwise.
Both ff c and ff s lie in I + so they are both candidates for ff
t . Since g t g l ! 0, a minimizer
lies between ff l and ff t . Choosing the step that is farthest from ff t tends to generate a step
that straddles a minimizer, and thus the next step is also likely to fall in this case.
In the next case we choose ff
t by extrapolating the function values at ff l and ff t , so
the trial value ff
lies outside of the interval with ff t and ff l as endpoints. We define ff
in terms of ff c (the minimizer of the cubic that interpolates f l , f t , g l , and g t ) and ff s (the
minimizer of the quadratic that interpolates g l and g t ).
Case 3: f t - f l , g t g l - 0, and jg t j - jg l j. In this case the cubic that interpolates the
function values f l and f t and the derivatives g l and g t may not have a minimizer. Moreover,
even if the minimizer ff c exists, it may be in the wrong direction. For example, we may
have . On the other hand, the secant step ff s always exists and is in
the right direction.
If the cubic tends to infinity in the direction of the step and the minimum of the cubic
is beyond ff t , set
ff s otherwise.
Otherwise, set ff
This choice is based on the observation that during extrapolation
it is sensible to be cautious and choose the step closest to ff t .
The trial value ff
defined above may be outside of the interval with ff t and ff u as
endpoints, or it may be in this interval but close to ff u . Either situation is undesirable, so
we redefine ff
t by setting
for some ffi ! 1. In our algorithm we use
In the last case the information available at ff l and ff t indicates that the function is
decreasing rapidly in the direction of the step, but there does not seem to be a good way
to choose ff
t from the available information.
Case 4: f t - f l , g t g l - 0, and jg t j ? jg l j. In this case we choose ff
t as the minimizer of the
cubic that interpolates f u , f t , g u , and g t ,
5 Numerical Results
The set of test problems that we use to illustrate the behavior of the search algorithm
includes convex and general functions. The first three functions have regions of concavity,
while the last three functions are convex. In all cases the functions have a unique minimizer.
Our numerical results were done in double precision on an IPX Sparcstation.
The region of concavity of the first function in the test set is to the right of the minimizer,
while the second function is concave to the left of the minimizer. The first function is defined
by
ff
with while the second function is defined by
with 0:004. Plots for these two functions appear in Figures 5.1 and 5.2.
The third function in the test set was suggested by Paul Plassmann. This function is
defined in terms of the parameters l and fi by
l-
sin( l-
where
The parameter fi controls the size of OE 0 This parameter also controls the size of
the interval where (1.2) holds because jOE 0 (ff)j - fi for jff \Gamma 1j - fi, and thus (1.2) can hold
only for fi. The parameter l controls the number of oscillations in the function for
because in that interval OE 00 (ff) is a multiple of sin( l-
ff). Note that if l is odd,
then OE 0
that OE is convex for
l-
We have chosen plot of this function with these parameter settings
appears in Figure 5.3.
The other three functions in the test set are from the paper of Yanai, Ozawa, and Kaneko
[18]. These functions are defined in terms of parameters fi 1 and fi 2 by
where
These functions are convex, but different choices of fi 1 and fi 2 lead to functions with quite
different characteristics. This can be seen clearly in Figures 5.4, 5.5, and 5.6.
In the tables below we present numerical results for different values of ff 0 . We have
used ff This illustrates the behavior of the algorithm from different
starting points. We are particularly interested in the behavior from the remote starting
points ff
Figure

5.1: Plot of function (5.1) with

Figure

5.2: Plot of function (5.2) with

Figure

5.3: Plot of function (5.3) with

Figure

5.4: Plot of function (5.4) with

Figure

5.5: Plot of function (5.4) with

Figure

5.6: Plot of function (5.4) with

Table

5.1: Results for the function in Figure 5.1 with
In our numerical results we have used different values of - and j in order to illustrate
different features of the problems and the search algorithm. In many problems we have
used 0:1 because this value is typical of those used in an optimization setting. We
comment on what happens for other values of - and j. The general trend is for the number
of function evaluations to decrease if - is decreased or if j is increased. The reason for this
trend is that as - is decreased or j is increased, the measure of the set of acceptable values
of ff increases.
An interesting feature of the numerical results for the function in Figure 5.1 is that
values of ff much larger than ff   - 1:4 can satisfy (1.1) and (1.2). This should be clear from

Figure

5.1 and from the results in Table 5.1. These results show that if we use
then the starting point ff and thus the search
algorithm exits with ff 0 . Similarly, the search algorithm exits with ff 4 - 37 when the
starting point is ff
We can avoid termination at points far away from the minimizer ff   by increasing - or
decreasing j. If we increase - and set then the algorithm terminates with
. There is no change in the
behavior of the algorithm from the other two starting points. If we decrease j by setting
leave - unchanged at then the final iterate ff m is near ff   for
all starting points. For 0:001 the search algorithm needs six function evaluations for
evaluations for ff . The number of function evaluations
for respectively, 8 and 4. This increase in the number of
function evaluations is to be expected because now the set of acceptable ff is smaller.
Another interesting feature of the results in Table 5.1 is that the six function evaluations
needed for ff could have been predicted from the nature of the extrapolation
process. This can be explained by noting that in a typical situation the extrapolation
process generates iterates by setting ff
4, and thus

Table

5.2: Results for the function in Figure 5.2 with
until the minimizer is bracketed, or until one of these iterates satisfies the termination
conditions. This implies, for example, that if the minimizer is ff
of the above iterates satisfies (1.1) and (1.2), or at least six functions are evaluations are
required before the search algorithm exits.
The number of function evaluations needed to find an acceptable ff is usually dependent
on the measure of the set of acceptable ff. From this point of view, the only difficult
test problems are those based on the functions in Figures 5.2 and 5.3, because for these
functions the set of acceptable ff is small. The choice of for the function in

Figure

5.2 guarantees that this function has a large region of concavity, but also forces OE 0 (0)
to be quite small (approximately \Gamma5 10 \Gamma7 ). As a consequence (1.2) is quite restrictive for
any j ! 1. Similar remarks apply to the numerical results for the function in Figure 5.3.
This is a difficult test problem because information based on derivatives is unreliable as a
result of the oscillations in the function. Moreover, as already noted, (1.2) can hold only
for
In

Table

5.2 we present the numerical results for the function in Figure 5.2. In this table
we have used these results remain unchanged if we set choose
any - ! j.
The number of function evaluations in Table 5.2 compares favorably with a search algorithm
based on bisection. Given the starting value ff search algorithm based
on bisection requires 48 function evaluations to determine an acceptable ff because in this
problem the set of acceptable ff is an interval of approximate length 2:5 10 \Gamma9 . The comparison
is even more favorable for the starting point ff because in this case a bisection
algorithm requires 107 function evaluations.
For the function in Figure 5.3 the set of acceptable ff is an interval of length 10 \Gamma3 , so a
bisection algorithm requires 10 function evaluations for the starting value ff
function evaluations for ff . If we now compare this information with the numerical
results in Table 5.3, we see that the search algorithm of this paper performs better than an
algorithm based on bisection. This is surprising because for this function the information

Table

5.4: Results for the function in Figure 5.4 with
provided by OE 0 is unreliable.
The numerical results for the problems based on function (5.4) appear in Tables 5.4,
5.5, and 5.6. In all these tables we have chosen Although these choices are
not typical of those found in an optimization environment, they lead to more interesting
results.
If we compare the results in these three tables, we notice that for a given starting
point, the number of function evaluations sometimes differs considerably. The results in

Tables

5.5 are typical of those that occur for In examining the results in

Table

5.5, allowances must be made for the fact that the starting points are not distributed
symmetrically around the minimizer ff   - 0:074. In particular, the small number of function
evaluations for ff mainly due to the fact that in this case ff 0 is close to ff   .
The number of function evaluations in Table 5.4 is lower because the set of acceptable ff
is unusually large. In particular, note that the value ff m returned by the search algorithm
is not close to the minimizer ff  1of the function in Figure 5.4.
The number of function evaluations in Table 5.6 is higher because in this problem it
is difficult to determine an iterate ff k such that OE 0 (ff satisfies the sufficient
decrease condition. Recall that once such an iterate is determined, we know that the
problem has a minimizer that satisfies the sufficient decrease condition.

Table

5.5: Results for the function in Figure 5.5 with

Table

5.6: Results for the function in Figure 5.6 with
In an optimization setting, we would not tend to use and then the number of
function evaluations needed to obtain an acceptable ff would decrease considerably. Con-
sider, for example, the results for the function in Figure 5.6 with 0:1. For
these settings, the number of function evaluations needed to obtain an acceptable ff from
the starting points ff would be, respectively, 2; 4. Similar
results would be obtained for the functions in Figures 5.4 and 5.5.

Acknowledgments

. This work benefited from discussions and suggestions from many
sources. We thank, in particular, Bill Davidon, Roger Fletcher, and Michael Powell. We
are also grateful to Jorge Nocedal for his encouragement during the final phases of this work,
to Paul Plassmann for providing the monster function of Section 5, and to Gail Pieper for
her careful reading of the manuscript.



--R

Descent property and global convergence of the Fletcher-Reeves method with inexact line searches
An efficient line search for nonlinear least squares
Global convergence of a class of quasi-Newton methods on convex problems
Numerical Methods for Unconstrained Optimization and Nonlinear Equations
Practical Methods of Optimization Volume

Global convergence properties of conjugate gradient methods for optimization
Safeguarded steplength algorithms for optimization using descent methods
Two steplength algorithms for numerical optimization
On the limited memory BFGS method for large scale optimization

Robust regression computation using iteratively reweighted least squares
Some global convergence properties of a variable metric method without line searches


Minimization of unconstrained multivariate func- tions

Interpolation methods in one dimensional optimization
--TR
An efficient line search for nonlinear least squares
Practical methods of optimization; (2nd ed.)
On the limited memory BFGS method for large scale optimization
Robust regression computation computation using iteratively reweighted least squares
TNPACKMYAMPERSANDmdash;A truncated Newton minimization package for large-scale problems
TNPACKMYAMPERSANDmdash;a truncated Newton minimization package for large-scale problems
Algorithm 500: Minimization of Unconstrained Multivariate Functions [E4]

--CTR
Yasushi Narushima , Hiroshi Yabe, Global Convergence of a Memory Gradient Method for Unconstrained Optimization, Computational Optimization and Applications, v.35 n.3, p.325-346, November  2006
A. Varga, A numerically reliable approach to robust pole assignment for descriptor systems, Future Generation Computer Systems, v.19 n.7, p.1221-1230, October
Ciyou Zhu , Richard H. Byrd , Peihuang Lu , Jorge Nocedal, Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization, ACM Transactions on Mathematical Software (TOMS), v.23 n.4, p.550-560, Dec. 1997
I. Yu. Gejadze , G. J. M. Copeland , I. M. Navon, Open Boundary Control Problem for Navier-Stokes Equations Including a Free Surface: Data Assimilation, Computers & Mathematics with Applications, v.52 n.8-9, p.1269-1288, October, 2006
W. Hager , Hongchao Zhang, Algorithm 851: CG_DESCENT, a conjugate gradient method with guaranteed descent, ACM Transactions on Mathematical Software (TOMS), v.32 n.1, p.113-137, March 2006
Mariano Rivera , Jose L. Marroquin, Adaptive rest condition potentials: first and second order edge-preserving regularization, Computer Vision and Image Understanding, v.88 n.2, p.76-93, November 2002
variable metric algorithms;line search algorithms;conjugate gradient algorithms;nonlinear optimization;truncated Newton algorithms