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

A descent direction $s$ satisfies $g^{T}s<0$, where $g=\nabla f(x)$; the first-order Taylor expansion then gives $f(x+\alpha s)<f(x)$ for sufficiently small $\alpha >0$. To compare directions one must fix their scale. Among Euclidean unit vectors, the Cauchy-Schwarz inequality givesThis is the unit steepest descent direction. The conventional unnormalized direction used in the algorithm is the same ray, $\boxed{s=-g}$. Equivalently it is the unique minimizer of $g^{T}s+\frac{1}{2}\Vert s{\Vert }_2^2=\frac{1}{2}\Vert s+g{\Vert }_2^2-\frac{1}{2}\Vert g{\Vert }_2^2$. If $g=0$ there is no strict first-order descent direction, and the conventional update is zero.

A line search chooses a positive step size giving useful decrease along the chosen direction. Fix $\sigma ,\beta \in (0,1)$ and a trial step $\bar{\alpha }>0$. The Armijo condition isThe backtracking line search tests $\bar{\alpha },\beta \bar{\alpha },{\beta }^2\bar{\alpha },\dots$ and takes the first accepted value. A Lipschitz gradient has $\Vert \nabla f(y)-\nabla f(x){\Vert }_2\le L\Vert y-x{\Vert }_2$ with a constant $L$ independent of $x,y$.

Integrating the gradient along a segment gives the descent lemmaFor $s=-g$, every $0<\alpha \le \tau =2(1-\sigma )/L$ satisfies the Armijo condition. Thus backtracking terminates. If the trial step is accepted, $\alpha =\bar{\alpha }$; otherwise the immediately preceding step $\alpha /\beta$ failed, so it exceeded $\tau$. ConsequentlyThe same global Lipschitz constant and fixed search parameters make $c$ independent of $x$. If $g=0$, the zero direction passes the first test. If $L=0$, the gradient is constant and the first test passes, so take $c=\bar{\alpha }$.

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.

For any vectors $a,b$,Thus, among directions with $\Vert d{\Vert }_{\infty }\le 1$, $g^{T}d\ge -\Vert g{\Vert }_1$. Equality is achieved byFor $g\ne 0$ these minimizing directions have infinity norm one. The strongest decrease per unit infinity-norm step is $-\Vert g{\Vert }_1$, illustrating the dual norm pairing between the infinity norm and the one-norm.

To match the unnormalized convention in part (a), minimize $g^{T}s+\frac{1}{2}\Vert s{\Vert }_{\infty }^2$. At fixed $t=\Vert s{\Vert }_{\infty }$, its minimum is $-t\Vert g{\Vert }_1+\frac{1}{2}{t}^2$, attained at $t=\Vert g{\Vert }_1$. One conventional choice is therefore $\boxed{s=-\Vert g{\Vert }_1\mathrm{sgn}(g)}$, with zero entries where $g_j=0$. Its ray agrees with the unit direction just computed.