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

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.