Maximization of dot product subject to infinity norm constraint

Question

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?

Answer 1

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.

Answer 2

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?