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.
In these methods the idea is to find
for some smooth f : R n → R . Each step often involves approximately solving the subproblem
where x k is the current best guess, p k ∈ R n is a search direction, and α ∈ R is the step length.
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 α ∈ R + exactly. A line search algorithm can use Wolfe conditions as a requirement for any guessed α , before finding a new search direction p k .
Armijo rule and curvature
A step length α k is said to satisfy the Wolfe conditions, restricted to the direction p k , if the following two inequalities hold:
i)
f ( x k + α k p k ) ≤ f ( x k ) + c 1 α k p k T ∇ f ( x k ) ,ii)
p k T ∇ f ( x k + α k p k ) ≥ c 2 p k T ∇ f ( x k ) ,
with 0 < c 1 < c 2 < 1 . (In examining condition (ii), recall that to ensure that p k is a descent direction, we have p k T ∇ f ( x k ) < 0 .)
c 1 is usually chosen to be quite small while c 2 is much larger; Nocedal gives example values of c 1 = 10 − 4 and c 2 = 0.9 for Newton or quasi-Newton methods and c 2 = 0.1 for the nonlinear conjugate gradient method. Inequality i) is known as the Armijo rule and ii) as the curvature condition; i) ensures that the step length α k decreases f 'sufficiently', and ii) ensures that the slope has been reduced sufficiently.
Denote a univariate function ϕ restricted to the direction p k as ϕ ( α ) = f ( x k + α p k ) . 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,
iii)
| p k T ∇ f ( x k + α k p k ) | ≤ c 2 | p k T ∇ f ( x k ) | then i) and iii) together form the so-called strong Wolfe conditions, and force α k to lie close to a critical point of ϕ .
The principal reason for imposing the Wolfe conditions in an optimization algorithm where x k + 1 = x k + α p k is to ensure convergence of the gradient to zero. In particular, if the cosine of the angle between p k and the gradient,
is bounded away from zero and the i) and ii) conditions hold, then ∇ f ( x k ) → 0 .
An additional motivation, in the case of a quasi-Newton method, is that if p k = − B k − 1 ∇ f ( x k ) , where the matrix B k is updated by the BFGS or DFP formula, then if B k is positive definite ii) implies B k + 1 is also positive definite.
