Proof of Domination, Monotonicity and Semiconvexity of the Sup-Convolution

Throughout, $S_{\lambda,v}(\xi)$ denotes the set introduced in Sup-Convolution of a Function on $\mathbb{R}^M$, so that $v^{\lambda}(\xi)$ is its least upper bound, and similarly $S_{\lambda',v}(\xi)$ for the parameter $\lambda'$. Order arithmetic in the ordered field of real numbers is taken from Elementary Arithmetic in an Ordered Field and Elementary Order Arithmetic in an Ordered Field. Fix $\xi\in\mathbb{R}^{M}$.

Claim 1. Taking $x=\xi$ in the description of $S_{\lambda,v}(\xi)$: the difference $\xi-\xi$ is the origin of $\mathbb{R}^{M}$, whose norm is $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, so $\frac{\lambda}{2}\lVert\xi-\xi\rVert^{2}=0$ by claim 1 of Zero Products and Elementary Identities in a Field and therefore $v(\xi)=v(\xi)-\frac{\lambda}{2}\lVert\xi-\xi\rVert^{2}\in S_{\lambda,v}(\xi)$. A least upper bound is in particular an upper bound, so $v(\xi)\le v^{\lambda}(\xi)$. As observed in Sup-Convolution of a Function on $\mathbb{R}^M$, $C$ is an upper bound for $S_{\lambda,v}(\xi)$, and $v^{\lambda}(\xi)$ is the least one, so $v^{\lambda}(\xi)\le C$.

Claim 2. Let $\lambda'\in\mathbb{R}$ satisfy $\lambda\le\lambda'$; then $0<\lambda'$ by mixed transitivity (claim 2 of Elementary Order Arithmetic in an Ordered Field), so $v^{\lambda'}$ is defined. Let $x\in\mathbb{R}^{M}$ and put $a=\lVert x-\xi\rVert^{2}$, a nonnegative real number as observed in Sup-Convolution of a Function on $\mathbb{R}^M$. From $0<2$ we get $0<2^{-1}$ by claim 7 of Elementary Order Arithmetic in an Ordered Field, so $\lambda\le\lambda'$ gives $\frac{\lambda}{2}\le\frac{\lambda'}{2}$ by claim 5 of Elementary Arithmetic in an Ordered Field, and a second application of that claim, with the nonnegative factor $a$, gives $\frac{\lambda}{2}a\le\frac{\lambda'}{2}a$. Reversing signs (claim 4 of Elementary Order Arithmetic in an Ordered Field) and adding $v(x)$ to both sides (claim 3 of Elementary Arithmetic in an Ordered Field, both sides having the same difference) yields

$$v(x)-\frac{\lambda'}{2}\,a\ \le\ v(x)-\frac{\lambda}{2}\,a\ \le\ v^{\lambda}(\xi),$$

the second inequality because $v^{\lambda}(\xi)$ is an upper bound for $S_{\lambda,v}(\xi)$. As $x$ was arbitrary, $v^{\lambda}(\xi)$ is an upper bound for $S_{\lambda',v}(\xi)$, and $v^{\lambda'}(\xi)$ is the least upper bound of that set, so $v^{\lambda'}(\xi)\le v^{\lambda}(\xi)$.

Claim 3. Let $g:\mathbb{R}^{M}\to\mathbb{R}$ be given by $g(\eta)=v^{\lambda}(\eta)+\frac{\lambda}{2}\lVert\eta\rVert^{2}$. Since $0<\lambda$, by Semiconvex Function on a Convex Subset of $\mathbb{R}^n$ it suffices to prove that $g$ is convex on $\mathbb{R}^{M}$.

Step (a). Let $x,\eta\in\mathbb{R}^{M}$. By 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 squared norm is the dot product of a point with itself, so claims 1, 3 and 5 of The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite give

$$\lVert x-\eta\rVert^{2}=(x-\eta)\cdot(x-\eta)=\lVert x\rVert^{2}-\bigl((x\cdot\eta)+(x\cdot\eta)\bigr)+\lVert\eta\rVert^{2}.$$

Multiplying by $-\frac{\lambda}{2}$, adding $\frac{\lambda}{2}\lVert\eta\rVert^{2}$ and using claim 4 of The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite to write $\lambda\,(x\cdot\eta)=(\lambda x)\cdot\eta$, we obtain

$$v(x)-\frac{\lambda}{2}\lVert x-\eta\rVert^{2}+\frac{\lambda}{2}\lVert\eta\rVert^{2}=(\lambda x)\cdot\eta+\Bigl(v(x)-\frac{\lambda}{2}\lVert x\rVert^{2}\Bigr).$$

Let $\ell_{x}:\mathbb{R}^{M}\to\mathbb{R}$ be the function whose value at $\eta$ is the right-hand side.

Step (b). Each $\ell_{x}$ has the form $\eta\mapsto p\cdot\eta+c$ with $p=\lambda x$ and $c=v(x)-\frac{\lambda}{2}\lVert x\rVert^{2}$, so it is convex on $\mathbb{R}^{M}$ by claim 1 of Affine Functions, Sums, Nonnegative Multiples and Pointwise Suprema of Convex Functions.

Step (c). Let $\mathcal{F}=\{\ell_{x}:x\in\mathbb{R}^{M}\}$, a nonempty set of convex functions on $\mathbb{R}^{M}$. Fix $\eta\in\mathbb{R}^{M}$ and put $\kappa=\frac{\lambda}{2}\lVert\eta\rVert^{2}$. By Step (a) the set of values $\{f(\eta):f\in\mathcal{F}\}$ is exactly $\{s+\kappa:s\in S_{\lambda,v}(\eta)\}$. We claim that $g(\eta)=v^{\lambda}(\eta)+\kappa$ is its least upper bound. It is an upper bound: every $s\in S_{\lambda,v}(\eta)$ satisfies $s\le v^{\lambda}(\eta)$, and adding $\kappa$ to both sides preserves this by claim 3 of Elementary Arithmetic in an Ordered Field. If $b$ is any upper bound of it, then $s+\kappa\le b$ for every such $s$, hence $s\le b-\kappa$ by the same claim, so $b-\kappa$ is an upper bound for $S_{\lambda,v}(\eta)$ and therefore $v^{\lambda}(\eta)\le b-\kappa$, that is, $g(\eta)\le b$.

In particular $\{f(\eta):f\in\mathcal{F}\}$ is bounded above for every $\eta\in\mathbb{R}^{M}$, so claim 4 of Affine Functions, Sums, Nonnegative Multiples and Pointwise Suprema of Convex Functions applies and shows that the function sending $\eta$ to the least upper bound of that set is convex on $\mathbb{R}^{M}$. By the previous paragraph this function is $g$, so $g$ is convex and $v^{\lambda}$ is semiconvex on $\mathbb{R}^{M}$ with constant $\lambda$.