= Solution
For any vectors $a,b$,
$$
|a^Tb|\leq\sum_j|a_j||b_j|\leq\|a\|_\infty\sum_j|b_j|=\boxed{\|a\|_\infty\|b\|_1}.
$$
Thus, among directions with $\|d\|_\infty\leq1$, $g^Td\geq-\|g\|_1$. Equality is achieved by
$$
\boxed{d_j=-\operatorname{sgn}(g_j)\quad(g_j\ne0),\qquad d_j\in[-1,1]\quad(g_j=0).}
$$
For $g\ne0$ these minimizing directions have infinity norm one. The strongest decrease per unit infinity-norm step is $-\|g\|_1$, illustrating the <dual norm> pairing between the infinity norm and the one-norm.
To match the unnormalized convention in part (a), minimize $g^Ts+\tfrac12\|s\|_\infty^2$. At fixed $t=\|s\|_\infty$, its minimum is $-t\|g\|_1+\tfrac12t^2$, attained at $t=\|g\|_1$. One conventional choice is therefore $\boxed{s=-\|g\|_1\operatorname{sgn}(g)}$, with zero entries where $g_j=0$. Its ray agrees with the unit direction just computed.
Back to article page
