Calculation of minimum infinity norm subject to L1 norm

Question

Can somebody tell me how to evaluate the following in MATLAB or any other programming language?

\begin{equation} \min_{x \in \partial \|w\|_1} \| x+y\|_\infty \end{equation} $x,w,y \in R^n$. $w,y$ is known to us. My concern is that there are many subgradients of $\|w\|_1$. Which one to choose and how? I want the calculation in $O(n)$ flops.

Another way to put the question is: choose a subgradient from subdifferential set of L1 norm that mimimizes $\|\cdot\|_\infty$ norm. Correct me if I interpreted the question wrongly. Thanks.

Answer 1

Hint: to calculate the subgradienet for $f(w)=\|w\|_1=\sum_{k=1}^n|w_k|$, use three facts:

1. $f(w)=\sum_{k=1}^n f_k(w)$, $f_k$ convex $\Rightarrow$ $\partial f(w)=\sum_{k=1}^n\partial f_k(w)$.
2. $f(z)=\max_{1\le k\le n}f_k(z)$, $f_k$ convex and differentiable $\Rightarrow$ $$ \partial f(z)=\text{Convex hull}(\nabla f_k(z)\colon f_k(z)=f(z)). $$
3. $\|w\|_1=\sum_{k=1}^n|w_k|$ and $|w_k|=\max\{p\cdot w_k\colon p\in\{-1,1\}\}$.

Addendum: After one calculates the subgradient (see here, p. 5) $$ \partial \|w\|_1=\{x\colon \|x\|_\infty\le 1,\ w^Tx=\|w\|_1\} $$ the problem is LP $$ \min_{x,t}\, t\qquad\text{subject to}\ -t\le x_i+y_i\le t,\ -1\le x_i\le 1,\ w^Tx=\|w\|_1. $$

Answer 2

This is just the soft thresholding operation. The subgradient of $|w|$, where $w$ is a scalar, is $$\partial |w| \triangleq \begin{cases}\{1\} & w > 0 \\ [-1,1] & w = 0 \\ \{-1\} & w < 0 \end{cases}$$ Therefore, to minimize $|x+y|$, we need to choose the value of $x$ closest to $-y$, but not exceeding $1$: $$\begin{aligned}\min_{x\in\partial |w|} |x+y| &= \begin{cases} -y-1 & y < -1 \\ 0 & -1\leq y \leq 1 \\ y - 1 & y > 1 \end{cases} \\&= \max\{|y|-1,0\}\end{aligned}$$ For the vector case you simply apply this elementwise: $$\min_{x\in\partial\|w\|_1} \|x+y\|_\infty = \sum_i \max\{|y_i|-1,0\}$$ The minimizing $x$ and $x+y$ is $$x_i = -\mathop{\textrm{sgn}}(y_i) \min\{|y_i|,1\}, \quad i=1,2,\dots, n$$ $$x_i+y_i = \mathop{\textrm{sgn}}(y_i) \max\{|y_i|-1,0\}$$