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 The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite, and $\lVert v\rVert^{2}=v\cdot v$ is claim 1 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square.

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

$$\bigl|\lVert u\rVert-\lVert v\rVert\bigr|\le\lVert u-v\rVert . \tag{R}$$

Indeed, claim 6 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square 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 Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square, 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

$$\bigl|\lVert x-z\rVert^{2}-\lVert x-z_{0}\rVert^{2}\bigr|\le\lVert z-z_{0}\rVert\cdot 2P .$$

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 (ii) 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 The Cauchy-Schwarz Inequality on $\mathbb{R}^n$ 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

$$|f(x)|+|f(0)|+\lVert p\rVert\,\lVert x\rVert+1\le\tfrac{1}{4}m ,$$

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

$$\phi_{x}(z)\ge f(0)-\lVert p\rVert\,\lVert z\rVert+\tfrac{1}{2}\tau^{2}=\tfrac{1}{2}\tau^{2}-\lVert p\rVert\tau+f(0)-\lVert p\rVert\,\lVert x\rVert ,$$

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

$$\phi_{x}(z)\ge\tfrac{1}{4}m+f(0)-\lVert p\rVert\,\lVert x\rVert\ge|f(x)|+1+\bigl(|f(0)|+f(0)\bigr)\ge|f(x)|+1>f(x)=\phi_{x}(x),$$

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 The Heine-Borel Theorem in $\mathbb{R}^n$, and Compactness of Closed Balls and the Unit Sphere; 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 The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite,

$$\bigl\lVert\tfrac{1}{2}(u+v)\bigr\rVert^{2}=\tfrac{1}{4}\lVert u\rVert^{2}+\tfrac{1}{2}\,u\cdot v+\tfrac{1}{4}\lVert v\rVert^{2}=\tfrac{1}{2}\lVert u\rVert^{2}+\tfrac{1}{2}\lVert v\rVert^{2}-\tfrac{1}{4}\lVert u-v\rVert^{2},$$

and $\lVert u-v\rVert^{2}>0$ by claim 3 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square. Hence

$$\tfrac{1}{2}\lVert x-y\rVert^{2}<\tfrac{1}{2}\Bigl(\tfrac{1}{2}\lVert x-y_{1}\rVert^{2}+\tfrac{1}{2}\lVert x-y_{2}\rVert^{2}\Bigr),$$

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.