I want to show that $u = \text{prox}_f(x) \iff x - u \in \partial f(u)$, where $f$ is a proper, convex and lower semicontinuous function where $\partial$ is the subdifferential and $$ \text{prox}_f(x) = \text{argmin}_{y \in \mathbb R^d} \left\{ f(y) + \frac{1}{2} \| y - x \|_2^2 \right\} $$
Here's my attempt.
If $u = \text{prox}_{f}(x)$, then $$ f(u) + \frac{1}{2} \| u - x \|_2^2 \le f(y) + \frac{1}{2} \| y - x \|_2^2 \qquad \forall y \in \mathbb R^d $$ and thus $$ \frac{1}{2} \left(\| u - x \|_2^2 - \| y - x \|_2^2\right) \le f(y) - f(u) \qquad \forall y \in \mathbb R^d $$ On the other hand, $$ \partial f(u) = \{ d \in \mathbb R^d : f(y) - f(u) \ge \langle d, y - u \rangle \ \forall y \in \mathbb R^d \} $$ so, $x - u \in \partial f(u)$ means that $$ f(y) - f(u) \ge \langle x - u, y - u \rangle $$ Unfortunately, $$ \langle x - u, y - u \rangle \ne \frac{1}{2} \left(\| u - x \|_2^2 - \| y - x \|_2^2\right) = \frac{\| u \|^2 - \| y \|^2}{2} + \langle x, y - u \rangle. $$ What have I done wrong?
Use Fermat's rule:
$$0\in \partial_u(f(u) + \frac{1}{2}\|u-x\|_2^2) = \partial f(u) + u-x\implies x-u\in\partial f(u)$$
The trick, then, is to justify the fact that we distributed the subdifferential operator through the sum. This is justified since the domain of $\frac{1}{2}\|\cdot\|_2^2$ is the whole space, assuming that $f\in\Gamma_0$.