Wolfe conditions

In (unconstrained) optimization, the Wolfe conditions are a set of inequalities for performing inexact linesearches; that is, for efficiently selecting a step length in the linesearch algorithm.

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

i) <math>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)<math>,

ii) <math>\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)<math>,

with <math>0Armijo condition and ii) as the curvature condition. i) demands that <math>\alpha_k<math> gives 'sufficient' decrease in <math>f<math>, and ii) ensures that the slope of the function <math>\phi(\alpha)=f(\mathbf{x}_k+\alpha\mathbf{p}_k)<math> at <math>\alpha_k<math> is greater than <math>c_2<math> times that at <math>0<math>.

The Wolfe conditions provide a computationally more attractive way of computing a step length than minimizing exactly <math>\phi<math> over <math>\alpha\in\mathbb R<math>. However, the conditions can result in a value for the step length that is not close to a minimizer of <math>\phi<math>. If we modify the curvature condition to say

iia) <math>\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|<math>

then i) and iia) together are the so-called strong Wolfe conditions, and as such <math>\alpha_k<math> is forced to lie close to a critical point of <math>\phi<math>.

Reference

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