2.2.2 Line Search and Trust Region Steps

next up previous
Next: 2.2.3 Convergence Criteria Up: 2.2 Basic Structure Of Previous: 2.2.1 Descent Directions

2.2.2 Line Search and Trust Region Steps


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:







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




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

(See exercises 2 and 3.)

next up previous
Next: 2.2.3 Convergence Criteria Up: 2.2 Basic Structure Of Previous: 2.2.1 Descent Directions