Proof of Existence and Uniqueness of the Proximal Minimiser of a Convex Function

We use the notation of the statement. Algebraic manipulations of dot products use Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$, and $\lVert v\rVert^{2}=v\cdot v$ is claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$.

A norm estimate. For $u,v\in\mathbb{R}^{n}$ we have

Indeed, claim 6 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ applied to $u=v+(u-v)$ gives $\lVert u\rVert-\lVert v\rVert\le\lVert u-v\rVert$; exchanging $u$ and $v$ and using $\lVert v-u\rVert=\lVert u-v\rVert$, which is claim 5 of that lemma with the scalar $-1$, gives $\lVert v\rVert-\lVert u\rVert\le\lVert u-v\rVert$; and claim 6 of Properties of the Absolute Value in an Ordered Field combines the two.

Step 1 ($\phi_{x}$ is continuous on every closed ball). Let $R\in\mathbb{R}$ with $0<R$, let $z_{0}\in\bar{B}(0,R)$ and let $\varepsilon>0$. Since $\mathbb{R}^{n}$ is open and convex and $z_{0}$ is an interior point of it, A Convex Function is Lipschitz on a Ball around an Interior Point provides $\rho,L\in\mathbb{R}$ with $0<\rho$, $0\le L$ and $|f(z)-f(z_{0})|\le L\lVert z-z_{0}\rVert$ for every $z\in\bar{B}(z_{0},\rho)$. Put $P=\lVert x\rVert+R$. For $z\in\bar{B}(0,R)$ we have $\lVert x-z\rVert\le\lVert x\rVert+\lVert z\rVert\le P$ by claim 6 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$, and likewise $\lVert x-z_{0}\rVert\le P$; hence, since both numbers are nonnegative and $(x-z)-(x-z_{0})=z_{0}-z$, the identity $|a^{2}-b^{2}|=|a-b|\,(a+b)$ for nonnegative $a,b$ together with (R) gives

Therefore $|\phi_{x}(z)-\phi_{x}(z_{0})|\le(L+P)\lVert z-z_{0}\rVert$ for every $z\in\bar{B}(0,R)\cap\bar{B}(z_{0},\rho)$, and taking for $\delta$ the smaller of $\rho$ and $\varepsilon/(L+P+1)$ shows that $\phi_{x}$ has, on $\bar{B}(0,R)$, the continuity property required in Extreme Value Theorem on a Compact Subset of a Metric Space.

Step 2 (Growth outside a large ball). The set $\mathbb{R}^{n}$ is open and convex, so The Subdifferential of a Convex Function on an Open Convex Set is Nonempty §nonempty provides $p\in\partial_{\mathbb{R}^{n}}f(0)$; thus $f(z)\ge f(0)+p\cdot z$ for every $z$, and $p\cdot z\ge-\lVert p\rVert\lVert z\rVert$ by Cauchy-Schwarz Inequality for the Euclidean Dot Product and claim 6 of Properties of the Absolute Value in an Ordered Field. By The Archimedean Property of the Real Numbers, applied to the largest of the three real numbers $1$, $4\lVert p\rVert$ and $4\bigl(|f(x)|+|f(0)|+\lVert p\rVert\lVert x\rVert+1\bigr)$, choose $m\in\mathbb{N}$ with $1\le m$, $4\lVert p\rVert\le m$ and

and put $R=\lVert x\rVert+m$.

Let $z\in\mathbb{R}^{n}$ with $R\le\lVert z\rVert$, and put $\tau=\lVert z\rVert-\lVert x\rVert$, so that $m\le\tau$ and in particular $1\le\tau$ and $4\lVert p\rVert\le\tau$. By (R) with $u=z$ and $v=x$ we have $\tau\le\lVert z-x\rVert$, and both are nonnegative, so $\tau^{2}\le\lVert x-z\rVert^{2}$. Hence

using $\lVert z\rVert=\tau+\lVert x\rVert$. Since $4\lVert p\rVert\le\tau$ we have $\tfrac{1}{4}\tau^{2}-\lVert p\rVert\tau=\tau(\tfrac{1}{4}\tau-\lVert p\rVert)\ge0$, so $\tfrac{1}{2}\tau^{2}-\lVert p\rVert\tau\ge\tfrac{1}{4}\tau^{2}$; and $1\le\tau$ with $m\le\tau$ gives $\tau^{2}\ge\tau\ge m$. Therefore

where $|f(0)|+f(0)\ge0$ and $f(x)\le|f(x)|$ by claim 3 of Properties of the Absolute Value in an Ordered Field.

Step 3 (Existence). The closed ball $\bar{B}(0,R)$ is closed by claim 3 of Elementary Properties of the Closed Ball in a Metric Space and bounded by claim 2 of that lemma, hence compact by Heine-Borel Theorem in $\mathbb{R}^n$; and it is nonempty, since it contains its centre by claim 1 of Elementary Properties of the Closed Ball in a Metric Space. By Step 1 and Extreme Value Theorem on a Compact Subset of a Metric Space there is $y\in\bar{B}(0,R)$ with $\phi_{x}(y)\le\phi_{x}(z)$ for every $z\in\bar{B}(0,R)$. Since $\lVert x\rVert\le R$ we have $x\in\bar{B}(0,R)$ and hence $\phi_{x}(y)\le\phi_{x}(x)$. If $z\notin\bar{B}(0,R)$ then $R<\lVert z\rVert$, so Step 2 gives $\phi_{x}(z)>\phi_{x}(x)\ge\phi_{x}(y)$. Therefore $\phi_{x}(y)\le\phi_{x}(z)$ for every $z\in\mathbb{R}^{n}$.

Step 4 (Uniqueness). Suppose $y_{1}$ and $y_{2}$ both have this property and $y_{1}\neq y_{2}$; then $\phi_{x}(y_{1})=\phi_{x}(y_{2})$, and we call this common value $\mu$. Put $y=\tfrac{1}{2}y_{1}+\tfrac{1}{2}y_{2}$, $u=x-y_{1}$ and $v=x-y_{2}$, so that $x-y=\tfrac{1}{2}(u+v)$ and $u-v=y_{2}-y_{1}\neq0$. Expanding both sides with Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$,

and $\lVert u-v\rVert^{2}>0$ by claim 3 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$. Hence

while convexity of $f$ gives $f(y)\le\tfrac{1}{2}f(y_{1})+\tfrac{1}{2}f(y_{2})$. Adding, $\phi_{x}(y)<\tfrac{1}{2}\phi_{x}(y_{1})+\tfrac{1}{2}\phi_{x}(y_{2})=\mu$, contradicting the minimality of $\mu$. Therefore the minimiser is unique.