Wolfe conditions

From Wikipedia, the free encyclopedia

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 α that reduces the cost 'sufficiently', rather than minimizing the cost over \alpha\in\mathbb R exactly.

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

i) f(\mathbf{x}_k+\alpha_k\mathbf{p}_k)\leq f(\mathbf{x}_k)+c_1\alpha_k\mathbf{p}_k^{\mathrm T}\nabla f(\mathbf{x}_k),
ii) \mathbf{p}_k^{\mathrm T}\nabla f(\mathbf{x}_k+\alpha_k\mathbf{p}_k)\geq c_2\mathbf{p}_k^{\mathrm T}\nabla f(\mathbf{x}_k),

with 0 < c1 < c2 < 1. Inequality i) is known as the Armijo rule and ii) as the curvature condition; i) ensures that αk decreases f 'sufficiently', and ii) ensures that the slope of the function \phi(\alpha)=f(\mathbf{x}_k+\alpha\mathbf{p}_k) at αk is greater than c2 times that at α = 0.

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

iia) \big|\mathbf{p}_k^{\mathrm T}\nabla f(\mathbf{x}_k+\alpha_k\mathbf{p}_k)\big|\leq c_2\big|\mathbf{p}_k^{\mathrm T}\nabla f(\mathbf{x}_k)\big|

then i) and iia) together form the so-called strong Wolfe conditions, and force αk to lie close to a critical point of φ.

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

[edit] References

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