How to prove that the proximal function $$ \Phi (y) \equiv \min_x \left(f(x)+\frac{1}{2} ||x-y||_2^2\right) $$ is a convex function of $y$ if $f(x)$ is a convex function of $x\in \mathbb{R}^n $?
There is a hint given: use the fact that both terms are convex.
$$\Phi(y)=\min_x g(x,y)$$ Assume $x_1$ and $x_2$ solves $argmin_x g(x,y)$ w.r.t $y_1$ and $y_2$. (Existence of solution is guaranteed by convexity of $f(x)$, can use a super divergent argument to prove it.) Let $x_3$ be a linear combination of $x_1$ and $x_2$, $y_3$ that of $y_1$ and $y_2$. Since $g$ is a jointly convex function for $(x,y)$, thus $\lambda\Phi(y_1)+(1-\lambda)\Phi(y_2)=\lambda g(x_1,y_1)+(1-\lambda)g(x_2,y_2)\geq g(x_3,y_3)\geq \min_xg(y_3)=\Phi(y_3)$