Next: Conjugate Direction Methods Up: Lecture 8 Previous: Quadratic Fit

Inexact Line Search

Since the line search is just one part of the optimization algorithm, it is enough to find an approximate minimizer, $\alpha_k$ , to the problem

$\begin{displaymath} \min_\alpha f(x_k + \alpha d_k) = \min_\alpha \varphi(\alpha). \end{displaymath}$

We then need criteras for when to stop the line search. We do not want $\alpha$ to small or large, and we want f to be reduced. Some examples of stopping criteria follows.

Arminjo's regel

Consider the line $\varphi(0) + \epsilon \varphi'(0)\alpha$ for a fix $\epsilon \in (0,1)$
This line is above $\varphi(\alpha)$
The current $\alpha$ is accepted if
$\begin{displaymath} \varphi(\alpha) \leq \varphi(0) + \epsilon \varphi'(0)\alpha \end{displaymath}$
Choose $\eta \gt 1$ , then $\alpha$ is large enough if
$\begin{displaymath} \varphi(\eta\alpha) \gt \varphi(0) + \epsilon \varphi'(0)\eta\alpha \end{displaymath}$

Goldstein Test

First criteria as above
$\alpha$ is large enough if
$\begin{displaymath} \varphi(\alpha) \gt \varphi(0) + (1-\epsilon) \varphi'(0) \alpha \end{displaymath}$

Wolfe Test

Variation of Goldstein
$\alpha$ is large enough if
$\begin{displaymath} \varphi'(\alpha) \geq (1-\epsilon) \varphi'(0) \end{displaymath}$

See Fig. 7.8 in Luenberger.

Mats Holmstr|m
10/31/1997