Wolfe conditions

In (unconstrained) optimization, the Wolfe conditions are a set of inequalities for performing inexact linesearch, especially in quasi-Newton methods. Inexact line searches provide an efficient way of computing an acceptable step length $alpha$ that reduces the cost 'sufficiently', rather than minimizing the cost over $alphainmathbb\; R$ exactly.

Let $f:mathbb\; R^n\; omathbb\; R$ be a smooth objective function, and $mathbf\{p\}\_k$ be a given search direction. A step length $alpha\_k$ is said to satisfy the "Wolfe conditions" if the following two inequalities hold.

:i) $f(mathbf\{x\}\_k+alpha\_kmathbf\{p\}\_k)leq\; f(mathbf\{x\}\_k)+c\_1alpha\_kmathbf\{p\}\_k^\{mathrm\; T\}\; abla\; f(mathbf\{x\}\_k)$,:ii) $mathbf\{p\}\_k^\{mathrm\; T\}\; abla\; f(mathbf\{x\}\_k+alpha\_kmathbf\{p\}\_k)geq\; c\_2mathbf\{p\}\_k^\{mathrm\; T\}\; abla\; f(mathbf\{x\}\_k)$,

with Armijo rule and ii) as the curvature condition; i) ensures that $alpha\_k$ decreases $f$ 'sufficiently', and ii) ensures that the slope of the function $phi(alpha)=f(mathbf\{x\}\_k+alphamathbf\{p\}\_k)$ at $alpha\_k$ is greater than $c\_2$ times that at $alpha\; =\; 0$.

The Wolfe conditions, however, can result in a value for the step length that is not close to a minimizer of $phi$. If we modify the curvature condition to the following,

:iia)

then i) and iia) together form the so-called strong Wolfe conditions, and force $alpha\_k$ to lie close to a critical point of $phi$.

The Goldstein conditions are similar but more commonly used with Newton methods (as opposed to quasi-Newton methods).

References

* J. Nocedal and S. J. Wright, Numerical optimization. Springer Verlag, New York, NY, 1999.