Consider the following minimization problem:
\begin{equation*} \begin{aligned} & \underset{}{\text{minimize}} & & \nabla f(\hat{x})^Tp \\ & \text{subject to} & & ||p||_\infty=1 \end{aligned} \end{equation*}
I need to prove that the solutions to this problem are all vectors $p^*$ such that $||p^*||_\infty=1$ and $\nabla f(\hat{x})^Tp^*=-||\nabla f(\hat{x})||_1$.
Now, when the problem involves norm 2 I can consider the angle $\theta$ between $\nabla f(\hat{x})$ and $p$
\begin{equation*} \nabla f(\hat{x})^Tp=cos(\theta)||\nabla f(\hat{x})||_2||p||_2=cos(\theta)||\nabla f(\hat{x})||_2 \end{equation*}
The second inequality is due to the fact that we assume $||p||_2=1$.
Clearly the minimizer is attained when $cos(\theta)=-1$ and $p=-\frac{\nabla f(\hat{x})}{||\nabla f(\hat{x})||}$.
How can I prove the original statement, involving $||p||_\infty$ and $||\nabla f(\hat{x})||_1$? I know there is some relationship between norms (mainly, that $||x||_\infty\leq ||x||_2 \leq ||x||_1$) but I'm not sure what to do next.
Let $$\nabla f(\hat x)=(a_1,a_2,\cdots ,a_n)$$then we need to minimize $$a_1p_1+\cdots +a_np_n$$subject to $$\max_n |p_n|=1$$this means that $$|p_k|\le 1\qquad,\qquad \forall k$$also $$-||\nabla f(\hat x)||_1=-|a_1|-\cdots-|a_n|\le a_1p_1+\cdots +a_np_n\le |a_1|+\cdots+|a_n|=||\nabla f(\hat x)||_1$$therefore the minimum is $-||\nabla f(\hat x)||_1$ and is attained when $$|p_k|=1\qquad,\qquad\forall k\\p_ka_k<0$$