Both line search and trust region methods are essential components of basic
descent schemes for guaranteeing *global* convergence
[45][16].
Of course, only one of the two methods is needed for a given
minimization algorithm.
To date, there has been no clear evidence for superiority of one class
over another. Thus we sketch below the line search procedure, more
intuitive and simpler to program.

Figure 6 A Line Search Step. View Figure

The line search is essentially an approximate *one-dimensional minimization
problem.* It is usually performed by safeguarded polynomial
interpolation. That is, in a typical
line step iteration, cubic interpolation is performed in a region of
that ensures that the minimum
of along has been *bracketed*.
Typically, if the search directions are properly scaled, the initial trial point
produces a first reasonable trial move from
(see Figure 6).
The minimum is bracketed by examining the new function value
and slope and decreasing or increasing the interval as needed
(see Figure 7).
The minimum of that polynomial interpolant
in the bracketed interval
then provides a new candidate for .
The minimized one-dimensional function at the current point is
defined by ,
and
the vectors corresponding to different values of are set
by .

Figure 7 Possible Situations in Line Search Algorithms, with respect to the Current and Trial Points: (a) The new slope is positive; (b) The new slope is negative but function value is greater; (c) The new slope is negative and function value is lower. View Figure

For example, at the first step, a cubic polynomial can be constructed from the two function values , and the two slopes , . The slopes are the directional derivatives defined as: . Note in Fig. 6 a negative slope at since is a descent direction. More generally, for the bracketed interval , and corresponding function and slopes , the cubic polynomial passing through and and having the specified slopes is given by:

where

A minimum of can be obtained by setting

as long as and . Otherwise, a quadratic interpolant fitted to , and can be constructed with the same coefficients:

and minimized to produce

The degenerate case of corresponds to a linear function rather than a quadratic and redundancy among the three values ; it is excluded by construction.

Once a new and corresponding trial point have been determined in a line search iteration, conditions of sufficient progress with respect to the objective function are tested. The conditions often used in optimization algorithms are derived from the Armijo and Goldstein criteria [16]. They require that

and

hold for two constants , where . Essentially, the first condition prescribes an upper limit on acceptable new function values, and the second condition imposes a lower bound on (see Figure 8). Typical values of and in line search algorithms are and . Larger values of make the first test more severe, and smaller make the second more severe. The work in the line search (number of polynomial interpolations) should be balanced with the overall progress in the minimization.

Figure 8 Line Search Conditions. View Figure