# Why is the epigraph of Moreau-Yosida Regularization a projection of a convex set?

The Moreau-Yosida Regularization is given by

$$\begin{equation} f_\mu(x) = \inf_y \left( f(y) + \frac{1}{2\mu} \| x - y \|^2 \right). \end{equation}$$

We know that $$L(x, y) = f(y) + \frac{1}{2\mu} \| x - x \|^2$$ is jointly convex in $$x$$ and $$y$$.

Why is the epigraph of $$f_\mu(x)$$ a projection of a convex set?

• Who claims it is a projection? I would rather call it the intersection of (infinitely many) convex sets. – LinAlg Feb 12 at 20:25
• The course note states that "$f_u(x)$'s epigraph is the projection of a convex set" on the first page. – MathematicaIsAwesome Feb 12 at 22:10
• I do not see how you get $\{(x,t) : \inf_y L(x,y) \leq t\}$ from a projection of $\{(x,y,t) : L(x,y) \leq t\}$. Ask the author. – LinAlg Feb 13 at 0:12

To the best of my knowledge, this is a common mistake. It might be, of course, a projection of some convex set onto the $$(x, t)$$ coordinates, but it is not "the" convex set you might first think of.
Like any other 'infimal convolution', the epigraph of the Moreau-Yosida regularization is a sum of epigraphs. To be precise, it is the Minkowski sum of the epigraph of $$f$$ and the epigraph of $$\frac{1}{2\mu}\|x\|_2^2$$: $$\operatorname{epi}(f_\mu) = \operatorname{epi}(f)+\operatorname{epi}(\tfrac{1}{2\mu}\|\cdot\|_2^2) \equiv \{ (x+y, t+s) : (x, t) \in \operatorname{epi}(f),~(y, s) \in \operatorname{epi}(\tfrac{1}{2\mu}\|\cdot\|_2^2) \}$$ See the excellent paper on Epigraphical Analysis by Attouch and Wets for more details. The sum of convex sets is convex, and that is one reason why $$f_\mu$$ is convex.