Wolfe conditions

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Wolfe conditions are two rules used when choosing how far to move along a search direction in unconstrained optimization, especially in methods like quasi-Newton. The idea is to pick a step length that makes enough progress without overstepping.

Key idea
- In each iteration, you have a current point x_k and a search direction p_k. You test steps of the form x_k + alpha p_k and want a good alpha without fully minimizing along that line.
- Let phi(alpha) = f(x_k + alpha p_k). The Wolfe conditions require two inequalities for alpha, with 0 < c1 < c2 < 1:

1) Armijo (sufficient decrease): phi(alpha) <= phi(0) + c1 alpha phi'(0). This ensures the objective f decreases enough.

2) Curvature condition: phi'(alpha) >= c2 phi'(0). Since phi'(0) = ∇f(x_k) · p_k is negative for a descent direction, this ensures the slope along the direction isn’t too small in magnitude.

Typical values
- c1 is small, e.g., around 1e-4.
- c2 is larger, often around 0.9 for Newton or quasi-Newton methods; around 0.1 for nonlinear conjugate gradient methods.

What it means in practice
- The Wolfe conditions keep the step length alpha neither too large nor too small, providing a balance between making progress and staying stable.
- They help ensure that the gradient goes to zero as iterations proceed, and, in quasi-Newton methods, help preserve a positive definite update matrix for reliable descent directions.

Strong Wolfe conditions
- A variant called the strong Wolfe conditions tightens the curvature part to force the step length to be closer to a critical point of the one-dimensional function phi(alpha). This can improve robustness in some cases.

Comparison to Armijo alone
- Armijo’s condition alone guarantees some decrease, but Wolfe conditions add a curvature check. This often gives stronger convergence guarantees, though they can be pricier to satisfy in practice.