Q:

Prove that proximal function is convex

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.

A:

$$\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)$

