Wolfe conditions

In the unconstrained minimization problem, the Wolfe conditions are a set of inequalities for performing inexact line search, especially in quasi-Newton methods, first published by Philip Wolfe in 1969.

[1][2] In these methods the idea is to find

Each step often involves approximately solving the subproblem

The inexact line searches provide an efficient way of computing an acceptable step length

that reduces the objective function 'sufficiently', rather than minimizing the objective function over

A line search algorithm can use Wolfe conditions as a requirement for any guessed

, before finding a new search direction

is said to satisfy the Wolfe conditions, restricted to the direction

(In examining condition (ii), recall that to ensure that

is a descent direction, we have

, as in the case of gradient descent, where

is usually chosen to be quite small while

is much larger; Nocedal and Wright give example values of

for Newton or quasi-Newton methods and

for the nonlinear conjugate gradient method.

[3] Inequality i) is known as the Armijo rule[4] and ii) as the curvature condition; i) ensures that the step length

'sufficiently', and ii) ensures that the slope has been reduced sufficiently.

Conditions i) and ii) can be interpreted as respectively providing an upper and lower bound on the admissible step length values.

Denote a univariate function

φ ( α ) = f (

The Wolfe 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 the following, then i) and iii) together form the so-called strong Wolfe conditions, and force

to lie close to a critical point of

The principal reason for imposing the Wolfe conditions in an optimization algorithm where

is to ensure convergence of the gradient to zero.

is bounded away from zero and the i) and ii) conditions hold, then

An additional motivation, in the case of a quasi-Newton method, is that if

is updated by the BFGS or DFP formula, then if

is positive definite ii) implies

Wolfe's conditions are more complicated than Armijo's condition, and a gradient descent algorithm based on Armijo's condition has a better theoretical guarantee than one based on Wolfe conditions (see the sections on "Upper bound for learning rates" and "Theoretical guarantee" in the Backtracking line search article).