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 **f** 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.