# Subderivative of $||Au||_{L^{\infty}}$ to compute proximal operator

I am looking for ways to compute the subderivative of $||Au||_{L^{\infty}}$, as I want to solve the minimization problem of
\min\limits_u \quad \lambda ||Au||_{L^{\infty}} + \frac{1}{2} || u – f ||^2_{L^{2}} \quad.

However I have no idea where to start. I tried looking at the Gateaux derivative to get an intuition on the subdifferential, but I am not even certain how the derivative interacts with the esssup of the norm.

After Boyd-Vanderbergh, there should exist a unique prox. operator for the min-problem. I am fammiliar with the procedure for subdiff/prox operator for $L^1$ and $L^2$, yet how do I deal with the $esssup$ ?

P.S: A similar question has already been asked here: proximal operator of infinity norm, but I am fairly certain that this is wrong as $L^1$ is not dual to $L^\infty$.

#### Solutions Collecting From Web of "Subderivative of $||Au||_{L^{\infty}}$ to compute proximal operator"

Yes, the problem has a unique solution (by strong convexity of the objective), but you can’t compute it closed-form…

Let’s concentrate on your “real” problem: computing the subdifferential of that composite term. To this end, define $g = \|.\|_\infty$ and $f := g \circ A$. By basic properties of subdifferentials, it’s clear that

\partial f(u) = A^T\partial g(Au) := \{A^Tv | v \in \partial \|Au\|_\infty\}.

So it suffices to compute the subdifferential of the $\infty$-norm.

Now, for any $z$, $g(z) = \|z\|_\infty = \underset{\|w\|_1 \le 1}{\sup}z^Tw$, and so by the Danskin-Bertsekas Theorem for subdifferentials (Proposition A.22 of the PhD thesis of Bertsekas), it holds that
\partial \|z\|_\infty = \mathrm{conv}\{w\text{ s.t } \|w\|_1 \le 1, z^Tw = \|z\|_\infty\} = \{w\text{ s.t } \|w\|_1 \le 1, z^Tw = \|z\|_\infty\}.

Putting things together, we have $\partial f(u) = \{A^Tw \text{ s.t } \|w\|_1 \le 1, w^TAu = \|Au\|_\infty\}$.