Let $f$ be a proper, lower semicontinuous function, then the Moreau envelope is given by:
$e_\lambda g(x) := \inf_y \{g(y) + \dfrac{1}{2\lambda}\|x-y\|^2\}$
Recall that the Fenchel conjugate is:
Given $f: \mathbb{R}^n \to \mathbb{R}$
$f^*(x) := \sup_y \{x^Ty - f(y)\}$
Are these two definitions connected somehow?
It seems that if $g(y) = -x^Ty$, and $f(y) = \dfrac{1}{2\lambda}\|x-y\|^2$, the two definitions will coincide.
So can we say that the Moreau envelope of $g(y) = -x^Ty$ is the Fenchel conjugate of $f(y) = \dfrac{1}{2\lambda}\|x-y\|^2$?
Yes, they're related! Indeed, it's not too hard to show that $$ e_1(g)^* = g^* + \left(\frac{1}{2}\|.\|_2^2\right)^* = g^* + \frac{1}{2}\|.\|_2^2. $$
More generally, it holds that
$$ (g \Box f)^* = g^* + f^*,\; \forall f, g \in \Gamma_0(\mathcal H). $$ where $(g\Box f)(x) := \inf_{y \in \mathcal H}g(y) + f(x-y)$ defines the infimal-convolution of $f$ and $g$.
Bonus: $e_\lambda(g)$ is smooth with derivative given by $$\nabla e_\lambda g(x) = \text{prox}_\lambda g(x) := \text{argmin}_{y \in \mathcal H}g(y) + \frac{1}{2\lambda}\|x-y\|_2^2, $$ the proximal operator of $g$.
You can learn more on these things from this one-page manuscript from Bauschke.
N.B.: $\Gamma_0(\mathcal H) := $ the cone of proper convex lower-semicontinous functions on a hilbert space $\mathcal H$.