# 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?

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.

• You mean $x=\epsilon \text{ sign}(w)$, right? Commented Aug 3, 2017 at 21:58
• Yes indeed. Good catch. Thanks. I've fixed it. Commented Aug 4, 2017 at 5:27

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?

• I know that $\left\lVert \boldsymbol{x} \right\rVert_{\infty} = \underset{i} \max |x_i|$. Moreover, all that you said is clear to me, that's why I am pretty sure that the solution is $\boldsymbol{x} = \epsilon \text{ sign}(\boldsymbol{w})$. Is it possible to prove it using KKT multipliers, anyway? Commented Aug 2, 2017 at 10:50
• Sure, thanks ;) Commented Aug 2, 2017 at 10:57