Subderivative of $ ||Au||_{L^{\infty}} $ to Compute Proximal Operator / Prox Operator

Question

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

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$.

Answer 1

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 \begin{equation} \partial f(u) = A^T\partial g(Au) := \{A^Tv | v \in \partial \|Au\|_\infty\}. \end{equation} 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 \begin{equation}\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\}. \end{equation} Putting things together, we have $\partial f(u) = \{A^Tw \text{ s.t } \|w\|_1 \le 1, w^TAu = \|Au\|_\infty\}$.