Maximization of dot product subject to infinity norm constraint I have read a paper where, at some point, the following optimization problem appears:
\begin{align}
&\underset{\boldsymbol{x}}\max \boldsymbol{w}^T \boldsymbol{x} \\
&\text{subject to } \left\lVert \boldsymbol{x} \right\rVert_{\infty} \leq \epsilon
\end{align}
where $\boldsymbol{x}$ and $\boldsymbol{w}$ are real vectors and $\epsilon$ is some given positive constant.
The authors claim that the solution for this problem is $\boldsymbol{x}=\text{sign}(\boldsymbol{w})$, which seems clearly wrong to me, since then we would have $\left\lVert \boldsymbol{x} \right\rVert_{\infty} = 1$.
I believe the correct answer is $\boldsymbol{x}=\epsilon \,\text{sign}(\boldsymbol{w})$. However, I am not being able to prove it. I have tried KKT multipliers, with no success. Any ideas?
 A: The $\ell_1$ and $\ell_\infty$ norms are duals of each order in the sense that $\|w\|_1 = \max_{\|x\|_\infty \le 1}w^Tx$. Thus for any $\epsilon > 0$, by an trivial change of variable, you have
$$ \max_{\|x\|_\infty \le \epsilon}w^Tx = \epsilon \|w\|_1.
$$
Taking $x = \epsilon\operatorname{sign}(w)$, clearly attains this maximum, since $\langle \epsilon\operatorname{sign}(w),w\rangle = \epsilon \sum_{i}|w_i| := \epsilon\|w\|_1$. Conclude.
A: Hints:


*

*What is the relation between infinity norm and the largest absolute value among the entries for a vector? From this, can you convince your self that $0\leq |x_i| \leq \epsilon$?

*Convince yourself about the sum \begin{align}w_1x_1 ~+~\dots~ + ~w_n x_n \\=\sum_{i,w_i\geq0}|w_i|x_i~-~\sum_{i,w_i<0}|w_i|x_i\end{align}

*Given above two, can you figure out the values for $x_i$ that will maximize your dot product?


Update: OP asked for using KKT multipliers
Convince yourself that each constraint $0\leq |x_i| \leq \epsilon$ is equivalent to the linear constraints $x_i\geq -\epsilon$ and $x_i\leq \epsilon$. Now your optimization problem is a linear program. Thus KKT conditions are necessary and sufficient. Can you prove the result you require now?
