Past exam of the numerical linear algebra and continuous optimisation course of the University of Oxford / 2009 / B / 4 / c

Choose $x_0$, fixed $\bar{\alpha }>0$, $\sigma ,\beta \in (0,1)$, and repeat for every $n\ge 0$: compute $g_n=\nabla f(x_n)$, choose ${\alpha }_n$ by the backtracking line search in part (b) with $s_n=-g_n$, and set $x_{n+1}=x_n-{\alpha }_n{g}_n$. At a stationary point keep the sequence constant.

Assume $f\in C^1$ has a globally Lipschitz gradient and is bounded below on its initial sublevel set $\{x:f(x)\le f(x_0)\}$. Then the steepest descent method satisfies $\boxed{\nabla f(x_n)\to 0}$. Indeed, the Armijo condition and the uniform lower step bound giveThe objective values decrease and stay in the stated sublevel set. Summing the inequality and using its lower bound $f_{\inf }$ yieldswhich proves the limit. Every cluster point is a stationary point by continuity of the gradient. If the initial sublevel set is compact, cluster points exist. This global convergence result guarantees stationarity from arbitrary initial points under these assumptions; it does not, for a general nonconvex objective, guarantee convergence of the whole iterate sequence or a global minimum.