Numerical Optimization

a descent direction

Standing on a hillside in fog, you want to get lower. You cannot see the whole valley, but you can feel which way the ground tilts under each foot. Any direction in which the very first step takes you downward — even slightly — is a direction worth walking. A descent direction is precisely that: a heading along which the function starts to decrease, so taking a small step that way is guaranteed to lower the value.

Mathematically, at a point x_k a direction p (a vector) is a descent direction for f if the slope of f along p is negative: grad f(x_k)^T p < 0. That dot product is the directional derivative — the instantaneous rate of change of f as you move along p — and a negative value means f goes down at first. Geometrically, p must point into the half-space that makes an angle of more than 90 degrees with the gradient (which points uphill); any such p qualifies. Descent methods build their iteration as x_{k+1} = x_k + alpha_k p_k, where p_k is a descent direction and alpha_k > 0 is a step length chosen by a line search. The whole zoo of algorithms differs mainly in HOW they pick p_k: steepest descent uses p = -grad f (straight downhill), Newton uses p = -H^{-1} grad f (rescaled by curvature), quasi-Newton approximates that.

Why insist on a descent direction? Because it guarantees progress: if grad f(x_k)^T p < 0, then for a small enough step f(x_k + alpha p) < f(x_k), so the method cannot accidentally climb. The honest subtlety is the words 'small enough' and 'at first'. A descent direction only promises decrease for a sufficiently short step; walk too far and you may overshoot the valley and climb the far wall. That is exactly the job of the line search and the Wolfe conditions — to find a step length that actually delivers the promised decrease, not just an infinitesimal one.

At x = (1, 0) for f(x, y) = x^2 + y^2, the gradient is (2, 0), pointing uphill (toward larger x). The direction p = (-1, 0) gives grad f^T p = -2 < 0, a descent direction. So is p = (-1, 1): grad f^T p = -2 < 0. But p = (0, 1) gives 0 (flat, not descent), and p = (1, 0) gives +2 (uphill).

Any direction at an obtuse angle to the gradient heads downhill.

A direction being 'downhill' only guarantees decrease for a sufficiently short step, not any step. Choosing the direction is half the algorithm; choosing how far to go along it (the step length) is the other half, and a poorly chosen length can wipe out a perfectly good direction.

Also called
downhill directionsearch direction下坡方向搜尋方向