next up previous

2.2.2 Line Search and Trust Region Steps     continued...

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.