- 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 0
. Inequality i) is known as the 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) ig|mathbf{p}_k^{mathrm T} abla f(mathbf{x}_k+alpha_kmathbf{p}_k)ig|leq c_2ig|mathbf{p}_k^{mathrm T} abla f(mathbf{x}_k)ig|
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.
Wikimedia Foundation. 2010.