Past exam of the numerical linear algebra and continuous optimisation course of the University of Oxford / 2007 / B / 7

For $g=\nabla f(x)\ne 0$, the unit steepest descent direction is $-g/\Vert g{\Vert }_2$ by the Cauchy-Schwarz inequality. The usual unnormalized direction is $\boxed{p=-g}$; choosing its scale separately as a line-search step gives the same ray. It satisfies $\boxed{g^{T}p=-\Vert g{\Vert }_2^2<0}$, so it is a descent direction. The first-order Taylor expansion then guarantees decrease for sufficiently small positive steps. The subsequent bounds use this unnormalized negative-gradient convention.

A Lipschitz gradient with constant $\gamma >0$ gives the descent lemmaFor $\alpha >0$, this upper bound is at most $f(x)+\alpha \beta g^{T}p$ whenever $\frac{\gamma }{2}\alpha \Vert p{\Vert }_2^2\le (\beta -1)g^{T}p$. Since $p$ is a descent direction, the right side is positive. Thus the Armijo condition holds throughoutAt $\alpha =0$ it holds by equality. If the gradient Lipschitz constant can be taken as zero, the objective is affine and every positive step along a descent direction passes this sufficient-decrease test.

The backtracking line search starts with ${\alpha }_{\mathrm{init}}>0$, tests the Armijo condition, and repeatedly replaces a failed step by $\tau \alpha$, with fixed $\tau \in (0,1)$. It accepts the first step that passes. Backtracking makes an overambitious trial step small enough for a local linear model to predict the change reliably; part (ii) ensures finite termination. The Armijo condition guarantees a decrease of at least $-\alpha \beta g^{T}p>0$ along a nonzero descent direction. Merely obtaining some decrease without this quantitative lower bound would not provide the convergence estimate in the following parts.

For $p=-g\ne 0$, part (ii) simplifies to ${\alpha }_{\max }=2(1-\beta )/\gamma$. If the initial step is accepted, ${\alpha }_k={\alpha }_{\mathrm{init}}$. Otherwise the immediately preceding trial ${\alpha }_k/\tau$ failed and hence exceeded ${\alpha }_{\max }$. ThereforeThe fixed global Lipschitz constant and search parameters make this lower bound uniform across iterations. At $g=0$, the zero update passes the first trial and the sequence can be kept stationary.

The Armijo condition with $p_k=-g(x_k)$ gives $f(x_k)-f(x_{k+1})\ge \beta {\alpha }_k\Vert g(x_k){\Vert }_2^2$. Summing these inequalities telescopes toIf $f\ge f_{\inf }$, these partial sums of nonnegative terms are bounded above by $(f(x_0)-f_{\inf })/\beta$. The resulting series converges, so its terms tend to zero: $\boxed{{\alpha }_k\Vert g(x_k){\Vert }_2^2\to 0}$.

Use the uniform lower step bound from part (iv):Thus $\boxed{g(x_k)\to 0}$. This is convergence to stationarity in the usual global convergence theorem for the steepest descent method. It does not itself prove that the iterates converge, or that any stationary limit is a global minimizer of a nonconvex objective.

Two reasons to prefer more advanced methods for smooth, high-accuracy optimization are:

The question's blanket wording is too strong: the steepest descent method and related gradient algorithms are used in practice, especially when problem size, cheap gradients or simplicity make curvature-based alternatives costly. The objections describe limitations, not universal nonuse.