Wolfe conditions

From Wikipedia, the free encyclopedia

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 $f:\mathbb R^n\to\mathbb R$ be a smooth objective function, and let $\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 < c 1 < c 2 < 1$ . Inequality i) is known as the Armijo condition and ii) as the curvature condition. i) demands that $α k$ gives 'sufficient' decrease in $f$ , and ii) ensures that the slope of the function $\phi(\alpha)=f(\mathbf{x}_k+\alpha\mathbf{p}_k)$ at $α k$ is greater than $c 2$ times that at $0$ .

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