The existence of proximal operator

Question

My problem: Consider a nonempty closed convex set $C \subset \mathbb{R}^n$ and a continuous convex function $f: \mathbb{R}^n \rightarrow \mathbb{R}$.
For $x \in \mathbb{R}^n$, we define $\Phi_{f, x} \mathbb{R}^n \rightarrow \mathbb{R}$, by $$ \forall y \in \mathbb{R}^n, \quad \Phi_{f, x}(y)=f(y)+\frac{1}{2}\|x-y\|^2 . $$ Show that there exists a unique $x^* \in C$ such that $\Phi_{f, x}\left(x^*\right)=\inf \left\{\Phi_{f, x}(y), y \in C\right\}$.
My attempt: I know that $x^*$ and $\phi$ will be an proximal operator and proximal mapping respectively. I can prove its uniqueness (Because $\phi_{f,x}$ is stricly convex). But i don't know how to prove its existence. I tried to read to lecture note (which is http://seas.ucla.edu/~vandenbe/236C/lectures/proxop.pdf?fbclid=IwAR0PUTOg2PxHP8Zgcj2tKVDwwKAocQkg80pK7UraP-jBNPa9jMHlfNBr7t0) but i don't understand. Can you help me to explain it?

Answer 1

Let us take $x = 0$ in $\mathbb R^n$, the general case is the same. As $f$ is convex, there exists an affine minorant, i.e. there is $a \in \mathbb R^n$ and $b \in \mathbb R$ such that \begin{align} g(y) := f(y) + \frac{1}{2}\|y\|^2 &\ge \langle a, y \rangle + b + \frac{1}{2}\|y\|^2\\ &= \frac{1}{2}\|y + a\|^2 + b - \frac{1}{2}\|a\|^2 \end{align} Let us fix $y_0 \in \mathbb R^n$ and take $R > 0$ sufficiently large such that $$\frac{1}{2}R^2 + b - \frac{1}{2}\|a\|^2 \ge g(y_0).$$ Let $$B = \{y \in \mathbb R^n~|~ \|y + a\| \le R\}.$$ For $y \notin B,$ (i.e. $\|y + a\| > R$), we have \begin{align} g(y) &\ge \frac{1}{2}\|y + a\|^2 + b - \frac{1}{2}\|a\|^2\\ &> \frac{1}{2}R^2 + b - \frac{1}{2}\|a\|^2\\ &\ge g(y_0). \end{align} This implies that $y_0 \in B$ and that $$\inf_{y \in B} g(y) = \inf_y g(y).$$ The function $g$ is bounded from below on $B$ as \begin{align} g(y) &\ge \langle a, y \rangle + b + \frac{1}{2}\|y\|^2\\ &\ge - \|a\|\|y\| + b\\ &\ge - \|a\|(\|a\| + R) + b \end{align} where the last inequality comes from the fact that $y \in B$. Therefore the infimum is a real number and you can consider a sequence $(y_n)_n \subset B$ such that $$\lim_{n \to \infty}g(y_n) = \inf_B g(y).$$ By compactness of $B$, we deduce the existence of a subsequence of $(y_n)_n$ (still denoted $y_n$) converging toward some $\hat y \in B$. By continuity of $g$, we deduce that $$\lim_n g(y_n) = \inf_B g(y) = g(\hat y).$$

Answer 2

We just need to prove that $\Phi_{f,x}$ is bounded below. Clearly, $\text{epi} f:=\{(x,\alpha):\in\mathbb R^n\times \mathbb R~|~\alpha\geq f(x)\}$ is closed and convex. Take any $(x_0,\alpha_0)\notin\text{epi} f$, by Separation theorems, there exist $(\xi,\beta)\in\mathbb R^n\times \mathbb R$ such that $$ \langle (\xi,\beta),(x_0,\alpha_0)\rangle<\inf\limits_{(x,\alpha)\in\text{epi} f}\langle (\xi,\beta),(x,\alpha)\rangle\leq\inf\limits_{x\in\mathbb R^n}\langle (\xi,\beta),(x,f(x))\rangle. $$ Clearly, $\beta>0$, since $\alpha_0<f(x_0)$ and $$ \langle (\xi,\beta),(x_0,\alpha_0)\rangle<\langle (\xi,\beta),(x_0,f(x_0))\rangle. $$ Thus $$ \beta f(x)>\langle \xi,x_0-x\rangle+\beta\alpha_0,~~~\forall x\in\mathbb R^n, $$ which implies $\Phi_{f,x}$ is bounded below.