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 Cauchy-Schwarz Inequality for the Euclidean Dot Product, and the homogeneity and triangle inequality of the Euclidean norm are claims 5 and 6 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$; 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

by Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$, 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$,

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

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

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 §slack-above 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

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 Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$, Cauchy-Schwarz and claim 5 of Elementary Arithmetic in an Ordered Field,

so, using the subgradient inequality once more,

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,

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