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

\min _{x}f(\mathbf {x} )

for some smooth $f:\mathbb {R} ^{n}\to \mathbb {R}$ . Each step often involves approximately solving the subproblem

\min _{\alpha }f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})

where $\mathbf {x} _{k}$ is the current best guess, $\mathbf {p} _{k}\in \mathbb {R} ^{n}$ is a search direction, and $\alpha \in \mathbb {R}$ is the step length.

The inexact line searches provide an efficient way of computing an acceptable step length $\alpha$ that reduces the objective function 'sufficiently', rather than minimizing the objective function over $\alpha \in \mathbb {R} ^{+}$ exactly. A line search algorithm can use Wolfe conditions as a requirement for any guessed $\alpha$ , before finding a new search direction $\mathbf {p} _{k}$ .

Armijo rule and curvature

A step length $\alpha _{k}$ is said to satisfy the Wolfe conditions, restricted to the direction $\mathbf {p} _{k}$ , if the following two inequalities hold:

{\begin{aligned}{\textbf {i)}}&\quad 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}),\\[6pt]{\textbf {ii)}}&\quad {-\mathbf {p} }_{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})\leq -c_{2}\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}),\end{aligned}}

with $0<c_{1}<c_{2}<1$ . (In examining condition (ii), recall that to ensure that $\mathbf {p} _{k}$ is a descent direction, we have $\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k})<0$ , as in the case of gradient descent, where $\mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k})$ , or Newton–Raphson, where $\mathbf {p} _{k}=-\mathbf {H} ^{-1}\nabla f(\mathbf {x} _{k})$ with $\mathbf {H}$ positive definite.)

$c_{1}$ is usually chosen to be quite small while $c_{2}$ is much larger; Nocedal and Wright give 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.[3] Inequality i) is known as the Armijo rule[4] and ii) as the curvature condition; i) ensures that the step length $\alpha _{k}$ decreases $f$ '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.

Strong Wolfe condition on curvature

Denote a univariate function $\varphi$ restricted to the direction $\mathbf {p} _{k}$ as $\varphi (\alpha )=f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})$ . The Wolfe conditions can result in a value for the step length that is not close to a minimizer of $\varphi$ . If we modify the curvature condition to the following,

{\textbf {iii)}}\quad {\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 |}

then i) and iii) together form the so-called strong Wolfe conditions, and force $\alpha _{k}$ to lie close to a critical point of $\varphi$ .

Rationale

The principal reason for imposing the Wolfe conditions in an optimization algorithm where $\mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha \mathbf {p} _{k}$ is to ensure convergence of the gradient to zero. In particular, if the cosine of the angle between $\mathbf {p} _{k}$ and the gradient,

\cos \theta _{k}={\frac {\nabla f(\mathbf {x} _{k})^{\mathrm {T} }\mathbf {p} _{k}}{\|\nabla f(\mathbf {x} _{k})\|\|\mathbf {p} _{k}\|}}

is bounded away from zero and the i) and ii) conditions hold, then $\nabla f(\mathbf {x} _{k})\rightarrow 0$ .

An additional motivation, in the case of a quasi-Newton method, is that if $\mathbf {p} _{k}=-B_{k}^{-1}\nabla f(\mathbf {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.

Comments

While Wolfe's conditions are more complicated than Armijo's condition, as of now the algorithm based on Armijo's condition (that is, Backtracking Gradient Descent) has better theoretical guarantee, see sections "Upper bound for learning rates" and "Theoretical guarantee" in Backtracking line search.

References

Wolfe, P. (1969). "Convergence Conditions for Ascent Methods". SIAM Review. 11 (2): 226–000. doi:10.1137/1011036. JSTOR 2028111.
Wolfe, P. (1971). "Convergence Conditions for Ascent Methods. II: Some Corrections". SIAM Review. 13 (2): 185–000. doi:10.1137/1013035.
Nocedal, Jorge; Wright, Stephen (1999). Numerical Optimization. p. 38.
Armijo, Larry (1966). "Minimization of functions having Lipschitz continuous first partial derivatives". Pacific J. Math. 16 (1): 1–3. doi:10.2140/pjm.1966.16.1.