L-infinity-norm regularized proximity problem

Question

I have a question: $$\min_x {1\over 2} \|x-t\|^2 + \lambda \|x\|_\infty$$ where $t, \lambda$ are given constant. I think this may be a classic problem? However, I didn't find closed form of its solution. What I tried is as follows.

I tried transforming it into a constrainted version: $$\min_{x,s} {1\over 2} \|x-t\|^2 + \lambda s\\ s.t.\ x_i\leq s,\ x_i\geq -s,\ \forall i=1,2,...,p $$ where $p$ is the dimensionality of $x$. Then get the Lagrangian: $$L(x,s,a,b)={1\over 2} \|x-t\|^2 + \lambda s+\sum_{i=1}^pa_i(x_i-s)+\sum_{i=1}^pb_i(-x_i-s).$$ I tried to derive something from the KKT conditions, but that seems to be a total mess, making me doubt this way.

Answer 1

This is indeed a classic problem. Recall the more general problem of computing the prox operator of an lsc convex function $f$, i.e., \begin{equation*} \text{prox}_f(y) := \operatorname{argmin}\quad \tfrac12\|x-y\|^2 + f(x). \end{equation*} For this prox operator, we have the well-known Moreau decomposition \begin{equation*} \text{Id} = \text{prox}_f + \text{prox}_{f^*}, \end{equation*} where $f^*$ denotes the Fenchel conjugate of $f$. In your case, $f(x)=\lambda \|x\|_{\infty}$, whose conjugate is the indicator function for the constraint $\|x\|_1 \le \lambda$. Thus, you can alternatively solve the optimization problem \begin{equation*} \min\quad \tfrac12\|x-y\|^2\quad\text{s.t.}~~\|x\|_1 \le \lambda. \end{equation*} This is the projection onto the $\ell_1$-ball, which is an extensively well-studied problem. I would recommend this paper by L. Condat, which gives a more recent summary of this classic problem (dates to the 1950s), and to a few existing methods while providing some additional context (also, you can find C code at this link from L. Condat's webpage).