Compute the min of $a^Tx+||x||_{\infty}$

Question

Prove that for any $a\in\mathbb{R}^n$ the following holds
$$\min a^Tx+\|x\|_\infty=\left\{\begin{array}{rcl} 0&\|a\|_1\leq1\\-\infty&\text{else}\end{array}\right.$$

I've tried looking at $\|x\|\cdot\|a\| \cos(\theta)+\|x\|_\infty$ and bound it from below by looking at the norm of $a$ but it didn't get me anywhere. edit:
I've tried taking norm 1 on $a^Tx+\|x\|_\infty\geq-\|a\|_1 \|x\|_\infty + \|x\|_\infty$ from holder's inequality and from here i got $\|x\|_\infty(1-\|a\|_1) > -\infty\iff\|a\|_1\leq1$ but to get that the minimum is zero still stuck

any hint will be welcome :)

Answer 1

Denote $f(x) = a^Tx + \Vert x \Vert_\infty$.

Case $\Vert a \Vert_1 \gt 1$

Suppose that $\Vert a \Vert = \vert a_1 \vert + \dots + \vert a_n \vert \gt 1$ and denote for $\lambda \gt 0$ $x_\lambda = -\lambda(\text{sign}(a_1), \dots, \text{sign}(a_n))$ where $\text{sign}$ denotes the sign function.

You have $f(x_\lambda) = - \lambda \Vert a \Vert_1 + \lambda = \lambda (1 - \Vert a \Vert_1)$ and therefore $\lim\limits_{\lambda \to \infty} f(x_\lambda) = -\infty$.

Case $\Vert a \Vert_1 \le 1$

Then $$ 0 \le -\Vert a \Vert_1 \Vert x \Vert_\infty + \Vert x \Vert_\infty\le f(x)$$ and $f(0) = 0$. Therefore $\min\limits_x f(x) = 0$

Answer 2

For the case $\|a\|_1 \leq 1$ use the fact that $-a^{T}x \leq \sum |a_i||x_i| \leq \max_i |x_i| \sum |a_i| \leq \|x\|_{\infty}$. This proves that $a^T x + \|x\|_\infty \geq 0$ for all $x$ so $0$ is a lower bound. This bound is attained when $x=0$ so the minimum value is $0$. For the case $\|a\|_1 > 1$ take $x_i=-n \operatorname{sgn} (a_i)$.