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.



L-infinity-norm regularized proximity problem
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](http://www.gipsa-lab.grenoble-inp.fr/~laurent.condat/publis/Condat_simplexproj.pdf), 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](http://www.gipsa-lab.grenoble-inp.fr/~laurent.condat/download/condat_l1ballproj.c)).


