Proof of The Lipschitz Truncation of a Convex Function: a Global Lipschitz Convex Minorant Agreeing with It Where the Slope is Small

Throughout, each result cited is universally quantified over the data appearing in its own statement and is applied to the data named here. The Cauchy-Schwarz inequality $|u\cdot v|\le\lVert u\rVert\lVert v\rVert$ is The Cauchy-Schwarz Inequality on $\mathbb{R}^n$, and the homogeneity and triangle inequality of the Euclidean norm are claims 5 and 6 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square; claim 2 of that lemma identifies $d_{E}(x,y)$ with $\lVert x-y\rVert$. Since $\lVert q_{0}\rVert\le L$ and norms are nonnegative, $0\le L$. Write $\partial\phi^{L}=\partial_{\mathbb{R}^{n}}\phi^{L}$.

Step 1 (Claim 1). Let $x\in\mathbb{R}^{n}$ and let $S_{x}=\{\phi(z)+L\lVert x-z\rVert:z\in G\}$. It is nonempty, $G$ being nonempty. It is bounded below: for $z\in G$ the subgradient inequality at $x_{0}$ gives $\phi(z)\ge\phi(x_{0})+q_{0}\cdot(z-x_{0})$, and

$$q_{0}\cdot(z-x_{0})=q_{0}\cdot(z-x)+q_{0}\cdot(x-x_{0})\ge-\lVert q_{0}\rVert\,\lVert z-x\rVert+q_{0}\cdot(x-x_{0})\ge-L\lVert x-z\rVert+q_{0}\cdot(x-x_{0})$$

by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite, Cauchy-Schwarz, claim 3 of Properties of the Absolute Value in an Ordered Field, and claim 5 of Elementary Arithmetic in an Ordered Field applied with the nonnegative factor $\lVert z-x\rVert$. Adding $L\lVert x-z\rVert$,

$$\phi(z)+L\lVert x-z\rVert\ge\phi(x_{0})+q_{0}\cdot(x-x_{0}),$$

a bound independent of $z$. Hence the infimum $\phi^{L}(x)$ exists in $\mathbb{R}$.

For $x\in G$ the choice $z=x$ gives $\phi^{L}(x)\le\phi(x)+L\lVert x-x\rVert=\phi(x)$.

Lipschitz. Let $x,y\in\mathbb{R}^{n}$ and $z\in G$. By the triangle inequality, $\lVert x-z\rVert\le\lVert y-z\rVert+\lVert x-y\rVert$, so $\phi^{L}(x)\le\phi(z)+L\lVert x-z\rVert\le\bigl(\phi(z)+L\lVert y-z\rVert\bigr)+L\lVert x-y\rVert$ by claim 5 of Elementary Arithmetic in an Ordered Field with the nonnegative factor $L$. Taking the infimum over $z\in G$ gives $\phi^{L}(x)-L\lVert x-y\rVert\le\phi^{L}(y)$, that is $\phi^{L}(x)-\phi^{L}(y)\le L\lVert x-y\rVert$; exchanging $x$ and $y$ and using claim 6 of Properties of the Absolute Value in an Ordered Field gives $|\phi^{L}(x)-\phi^{L}(y)|\le L\,d_{E}(x,y)$, so $\phi^{L}$ is Lipschitz with constant $L$.

Convexity. Let $u,v\in\mathbb{R}^{n}$, let $t$ be a real number with $0\le t\le1$, and let $\varepsilon$ be a positive real number. By claim 4 of Approximation Property of the Supremum and the Infimum in $\mathbb{R}$, applied to $S_{u}$ and to $S_{v}$, there are $z_{u},z_{v}\in G$ with

$$\phi(z_{u})+L\lVert u-z_{u}\rVert\le\phi^{L}(u)+\varepsilon,\qquad \phi(z_{v})+L\lVert v-z_{v}\rVert\le\phi^{L}(v)+\varepsilon .$$

The point $z_{t}=(1-t)z_{u}+tz_{v}$ lies in $G$, which is convex, and $\phi(z_{t})\le(1-t)\phi(z_{u})+t\phi(z_{v})$ by convexity of $\phi$. Writing $w=(1-t)u+tv$, one has $w-z_{t}=(1-t)(u-z_{u})+t(v-z_{v})$ by Euclidean Space $\mathbb{R}^n$ is a Real Vector Space, so the triangle inequality and homogeneity give $\lVert w-z_{t}\rVert\le(1-t)\lVert u-z_{u}\rVert+t\lVert v-z_{v}\rVert$. Therefore

$$\phi^{L}(w)\le\phi(z_{t})+L\lVert w-z_{t}\rVert\le(1-t)\bigl(\phi(z_{u})+L\lVert u-z_{u}\rVert\bigr)+t\bigl(\phi(z_{v})+L\lVert v-z_{v}\rVert\bigr)\le(1-t)\phi^{L}(u)+t\phi^{L}(v)+\varepsilon ,$$

using claim 5 of Elementary Arithmetic in an Ordered Field with the nonnegative factors $1-t$ and $t$. As $\varepsilon$ was an arbitrary positive real number, Comparison of Real Numbers with Arbitrary Positive Slack (i) gives $\phi^{L}(w)\le(1-t)\phi^{L}(u)+t\phi^{L}(v)$, so $\phi^{L}$ is convex on $\mathbb{R}^{n}$.

Step 2 (Claim 2). Let $x\in G$ and $p\in\partial_{G}\phi(x)$ with $\lVert p\rVert\le L$. For $z\in G$ the subgradient inequality and Cauchy-Schwarz give

$$\phi(z)+L\lVert x-z\rVert\ge\phi(x)+p\cdot(z-x)+L\lVert x-z\rVert\ge\phi(x)-\lVert p\rVert\lVert z-x\rVert+L\lVert x-z\rVert\ge\phi(x),$$

the last step by claim 5 of Elementary Arithmetic in an Ordered Field applied to $\lVert p\rVert\le L$ with the nonnegative factor $\lVert x-z\rVert$. Hence $\phi(x)$ is a lower bound for $S_{x}$ and $\phi^{L}(x)\ge\phi(x)$; with claim 1 this gives $\phi^{L}(x)=\phi(x)$.

Now let $y\in\mathbb{R}^{n}$ and $z\in G$. By The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite, Cauchy-Schwarz and claim 5 of Elementary Arithmetic in an Ordered Field,

$$p\cdot(z-x)=p\cdot(y-x)+p\cdot(z-y)\ge p\cdot(y-x)-L\lVert z-y\rVert ,$$

so, using the subgradient inequality once more,

$$\phi(z)+L\lVert y-z\rVert\ge\phi(x)+p\cdot(z-x)+L\lVert y-z\rVert\ge\phi(x)+p\cdot(y-x)=\phi^{L}(x)+p\cdot(y-x).$$

Taking the infimum over $z\in G$ gives $\phi^{L}(y)\ge\phi^{L}(x)+p\cdot(y-x)$ for every $y\in\mathbb{R}^{n}$, that is $p\in\partial\phi^{L}(x)$.

Step 3 (Claim 3). Let $x\in G$ with $\partial_{G}\phi(x)=\{p\}$ and $\lVert p\rVert\le L$. By claim 2, $p\in\partial\phi^{L}(x)$ and $\phi^{L}(x)=\phi(x)$. Conversely let $q\in\partial\phi^{L}(x)$ and let $y\in G$. Then, using $\phi^{L}\le\phi$ on $G$ from claim 1,

$$\phi(y)\ge\phi^{L}(y)\ge\phi^{L}(x)+q\cdot(y-x)=\phi(x)+q\cdot(y-x).$$

As $y\in G$ was arbitrary, $q\in\partial_{G}\phi(x)=\{p\}$, so $q=p$. Hence $\partial\phi^{L}(x)=\{p\}$.