next up previous

2.2.2 Line Search and Trust Region Steps     continued...

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.

(See exercises 6 and 6.)