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$$

  • $\begingroup$ if $a=0$, then every point with $\| p \|_{\infty} \le 1$ is optimal. $\endgroup$ – Brian Borchers Aug 31 '18 at 15:31
  • $\begingroup$ What do you mean by $a=0$? It is a multi-dimensional vector $\endgroup$ – Mostafa Ayaz Aug 31 '18 at 15:34
  • $\begingroup$ I mean that all components of a are 0. $\endgroup$ – Brian Borchers Aug 31 '18 at 16:39
  • $\begingroup$ That's right.... $\endgroup$ – Mostafa Ayaz Aug 31 '18 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.