Proof of Second-Order Test Data at a Global Quadratic Maximum of a Semiconvex Function

Throughout, the notation is that of the statement. Closed and open balls $\bar{B}_{d_{E}}(x,r)$ and $B_{d_{E}}(x,r)$ of $(\mathbb{R}^{N},d_{E})$ are those of Closed Ball in a Metric Space and Open Ball in a Metric Space. We write $\mathcal{B}(\mathbb{R}^{N})$ for the Borel $\sigma$-algebra and $\lambda_{N}$ for Lebesgue measure on it, as in Jensen's Lemma: the Contact Set of a Semiconvex Function at a Strict Maximum has Positive Measure, and a subset of $\mathbb{R}^{N}$ is null if it is contained in a member of $\mathcal{B}(\mathbb{R}^{N})$ of $\lambda_{N}$-measure $0$, as fixed there.

Step 0 (two elementary observations).

(0a) Inverses reverse the order. If $a,b\in\mathbb{R}$ satisfy $0<a\le b$, then $b^{-1}\le a^{-1}$. Indeed $a^{-1}$ and $b^{-1}$ exist and are positive by claim 7 of Elementary Order Arithmetic in an Ordered Field, so $c=a^{-1}b^{-1}$ is positive by claim 5 there; if $a<b$ then $ca<cb$ by claim 10 there, and $ca=b^{-1}(a^{-1}a)=b^{-1}$ while $cb=a^{-1}(b^{-1}b)=a^{-1}$, so $b^{-1}<a^{-1}$; while if $a=b$ then $a^{-1}=b^{-1}$.

(0b) A null sequence. Let $\iota_{\mathbb{R}}:\mathbb{N}\to\mathbb{R}$ be the canonical map of $\mathbb{R}$ and put $\delta_{k}=\iota_{\mathbb{R}}(k)^{-1}$ for $k\in\mathbb{N}$. By claim 3 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field each $\delta_{k}$ exists and is positive, and by claim 2 there $1\le\iota_{\mathbb{R}}(k)$, so $\delta_{k}\le 1^{-1}=1$ by (0a). Moreover $(\delta_{k})_{k\in\mathbb{N}}$ converges to $0$ in $\mathbb{R}$: given a positive $\varepsilon\in\mathbb{R}$, claim 3 of The Archimedean Property of the Real Numbers provides $p\in\mathbb{N}$ with $0<\iota_{\mathbb{R}}(p)^{-1}<\varepsilon$, and for $k\in\mathbb{N}$ with $p\le k$ we have $\iota_{\mathbb{R}}(p)\le\iota_{\mathbb{R}}(k)$ by claim 6 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field when $p<k$ and trivially when $p=k$, whence $\delta_{k}\le\iota_{\mathbb{R}}(p)^{-1}<\varepsilon$ by (0a).

(0c) Enlarging a semiconvexity constant. Let $C\subseteq\mathbb{R}^{N}$ be convex, let $\mu,\mu'\in\mathbb{R}$ with $0\le\mu\le\mu'$, and let $g:C\to\mathbb{R}$ be semiconvex on $C$ with constant $\mu$. Then $g$ is semiconvex on $C$ with constant $\mu'$. Indeed, by Differential Calculus and Convexity on Euclidean Open Sets: Standing Notation (v) semiconvexity with constant $\mu$ is equivalent to

$$g\bigl(t\,x+(1-t)\,y\bigr)\le t\,g(x)+(1-t)\,g(y)+\frac{\mu}{2}\,t(1-t)\,\lVert x-y\rVert^{2}$$

for all $x,y\in C$ and all real $t$ with $0\le t\le1$, and likewise with $\mu$ replaced by $\mu'$. For such $t$ the numbers $t$ and $1-t$ are nonnegative, and $\lVert x-y\rVert^{2}$ is nonnegative 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, so $t(1-t)\lVert x-y\rVert^{2}$ is nonnegative; multiplying $\tfrac{\mu}{2}\le\tfrac{\mu'}{2}$ by this nonnegative number preserves the inequality: if the factor is $0$ both products are $0$, if $\mu=\mu'$ the two products are equal, and otherwise the factor is positive and $\tfrac{\mu}{2}<\tfrac{\mu'}{2}$, so claim 10 of Elementary Order Arithmetic in an Ordered Field applies. Hence the displayed inequality for $\mu$ implies the one for $\mu'$.

Step 1 (the perturbed function). Put $\Lambda=\lambda+\lVert B\rVert+1$; it is positive, since $0\le\lambda$, $0\le\lVert B\rVert$ by claim 1 of Properties of the Norm of a Symmetric Real Matrix, and $0<1$ by claim 6 of Elementary Order Arithmetic in an Ordered Field.

Let $\delta\in\mathbb{R}$ satisfy $0<\delta\le1$. By Euclidean Space and Real Matrices: Standing Notation (iii) the matrix $\delta I_{N}$ lies in $\mathcal{S}(N)$ and $\mathcal{S}(N)$ is closed under sums, so the matrix

$$B_{\delta}=B+\delta I_{N}$$

lies in $\mathcal{S}(N)$, and $\lVert B_{\delta}\rVert\le\lVert B\rVert+\lVert\delta I_{N}\rVert=\lVert B\rVert+\delta\le\lVert B\rVert+1$ by claim 5 of Properties of the Norm of a Symmetric Real Matrix and Vector, Entry and Comparison Bounds for the Norm of a Symmetric Real Matrix (vi). Define $g_{\delta}:\mathbb{R}^{N}\to\mathbb{R}$ by

$$g_{\delta}(\xi)=f(\xi)-\tfrac{1}{2}\,\xi\cdot(B_{\delta}\xi).$$

For every $\xi\in\mathbb{R}^{N}$ we have $B_{\delta}\xi=B\xi+(\delta I_{N})\xi$ by claim 1 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum, hence, by claim 5 of The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite and Vector, Entry and Comparison Bounds for the Norm of a Symmetric Real Matrix (vi),

$$\xi\cdot(B_{\delta}\xi)=\xi\cdot(B\xi)+\delta\,\lVert\xi\rVert^{2},\qquad\text{so}\qquad g_{\delta}(\xi)=f(\xi)-\tfrac{1}{2}\,\xi\cdot(B\xi)-\tfrac{\delta}{2}\,\lVert\xi\rVert^{2}.$$

Taking $\xi=0_{\mathbb{R}^{N}}$ and using $B_{\delta}0_{\mathbb{R}^{N}}=0_{\mathbb{R}^{N}}$, from claim 1 of Linearity, Compatibility with the Matrix Product, and a Norm Bound for the Matrix-Vector Product, together with $0_{\mathbb{R}^{N}}\cdot 0_{\mathbb{R}^{N}}=0$, we get $g_{\delta}(0_{\mathbb{R}^{N}})=f(0_{\mathbb{R}^{N}})$. If $\xi\ne 0_{\mathbb{R}^{N}}$ then $\lVert\xi\rVert\ne0$ 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 and $0\le\lVert\xi\rVert$ by claim 1 there, so $0<\lVert\xi\rVert$, the strict order of an ordered field being defined by $a\le b$ together with $a\ne b$; hence $0<\tfrac{\delta}{2}\lVert\xi\rVert^{2}$ by claims 5 and 8 of Elementary Order Arithmetic in an Ordered Field, and the hypothesis of the lemma gives

$$g_{\delta}(\xi)\le f\bigl(0_{\mathbb{R}^{N}}\bigr)-\tfrac{\delta}{2}\,\lVert\xi\rVert^{2}<f\bigl(0_{\mathbb{R}^{N}}\bigr)=g_{\delta}\bigl(0_{\mathbb{R}^{N}}\bigr).$$

Thus $g_{\delta}(\xi)<g_{\delta}(0_{\mathbb{R}^{N}})$ for every $\xi\in\mathbb{R}^{N}$ with $\xi\ne0_{\mathbb{R}^{N}}$; in particular $0_{\mathbb{R}^{N}}$ is a strict maximum point of $g_{\delta}$ on $\bar{B}_{d_{E}}(0_{\mathbb{R}^{N}},1)$ in the sense required by Jensen's Lemma: the Contact Set of a Semiconvex Function at a Strict Maximum has Positive Measure.

Finally, Quadratic and Affine Functions of Class $C^2$, Translation, and Quadratic Perturbation of Semiconvexity (iv), applied with $M=B_{\delta}$, $q=0_{\mathbb{R}^{N}}$, $c=0$ and $C=\mathbb{R}^{N}$ — for which $q\cdot z=0$ by claim 4 of The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite applied with the scalar $0$, so that the function it produces is exactly $g_{\delta}$ — shows that $g_{\delta}$ is semiconvex on $\mathbb{R}^{N}$ with constant $\lambda+\lVert B_{\delta}\rVert$. Since $\lambda+\lVert B_{\delta}\rVert\le\Lambda$, observation (0c) shows that $g_{\delta}$ is semiconvex on $\mathbb{R}^{N}$ with constant $\Lambda$.

Step 2 (Jensen's lemma and Alexandrov's theorem). Let $\delta\in\mathbb{R}$ with $0<\delta\le1$. The hypotheses of Jensen's Lemma: the Contact Set of a Semiconvex Function at a Strict Maximum has Positive Measure hold with $n=N$, with $U=\mathbb{R}^{N}$, which is convex and open, with the positive semiconvexity constant $\Lambda$, with the function $g_{\delta}$, with $\hat{x}=0_{\mathbb{R}^{N}}$ and with $r=1$; write $\bar{B}=\bar{B}_{d_{E}}(0_{\mathbb{R}^{N}},1)$ and, for positive $\sigma\in\mathbb{R}$,

$$K^{\delta}_{\sigma}=\Bigl\{x\in\bar{B}:\text{there is }p\in\mathbb{R}^{N}\text{ with }\lVert p\rVert\le\sigma\text{ and }g_{\delta}(y)+p\cdot y\le g_{\delta}(x)+p\cdot x\text{ for every }y\in\bar{B}\Bigr\}$$

for the contact sets of that lemma. It supplies a positive $\delta_{0}(\delta)\in\mathbb{R}$ for which its four claims hold.

Applying Alexandrov's Theorem for Semiconvex Functions on an Open Convex Set (i) with $U=\mathbb{R}^{N}$, $\mu=\lambda$ and the function $f$, the set $E$ of points of $\mathbb{R}^{N}$ at which $f$ is not twice differentiable is null, so there is $Z\in\mathcal{B}(\mathbb{R}^{N})$ with $E\subseteq Z$ and $\lambda_{N}(Z)=0$.

Step 3 (what holds at a contact point of twice differentiability). Let $\delta\in\mathbb{R}$ with $0<\delta\le1$, let $\sigma\in\mathbb{R}$ with $0<\sigma\le\delta_{0}(\delta)$, let $x\in K^{\delta}_{\sigma}$ be a point at which $f$ is twice differentiable, and let $p\in\mathbb{R}^{N}$ with $\lVert p\rVert\le\sigma$ be as in the definition of $K^{\delta}_{\sigma}$. We claim that

$$Df(x)=B_{\delta}x-p,\qquad -\lambda I_{N}\preceq D^{2}f(x)\preceq B_{\delta}.$$

Let $Q:\mathbb{R}^{N}\to\mathbb{R}$ be given by $Q(y)=\tfrac{1}{2}\,y\cdot(B_{\delta}y)-p\cdot y$, and let $h=f-Q$, so that $h(y)=g_{\delta}(y)+p\cdot y$ for every $y$. By Quadratic and Affine Functions of Class $C^2$, Translation, and Quadratic Perturbation of Semiconvexity (i), applied with $M=B_{\delta}$, $q=-p$ and $c=0$, the function $Q$ is of class $C^{2}$ on $\mathbb{R}^{N}$ with $DQ(y)=B_{\delta}y-p$ and $D^{2}Q(y)=B_{\delta}$ at every $y$; hence by Basic Properties of Twice Differentiability at a Point (ii) the function $Q$ is twice differentiable at $x$ with first-order coefficient $B_{\delta}x-p$ and Hessian $B_{\delta}$. Since $f$ is twice differentiable at $x$ with first-order coefficient $Df(x)$ and Hessian $D^{2}f(x)$, Sums, Differences and Scalar Multiples of Functions Twice Differentiable at a Point (iii) shows that $h$ is twice differentiable at $x$ with first-order coefficient $Df(x)-\bigl(B_{\delta}x-p\bigr)$ and Hessian $D^{2}f(x)-B_{\delta}$.

By claim 1 of Jensen's Lemma: the Contact Set of a Semiconvex Function at a Strict Maximum has Positive Measure we have $x\in\bar{B}_{d_{E}}\bigl(0_{\mathbb{R}^{N}},2^{-1}\bigr)$, that is $\lVert x\rVert\le2^{-1}$. Consequently $h$ has a local maximum at $x$ relative to $\mathbb{R}^{N}$: if $y\in\mathbb{R}^{N}$ satisfies $d_{E}(y,x)<2^{-1}$ then, 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,

$$\lVert y\rVert\le\lVert y-x\rVert+\lVert x\rVert<2^{-1}+2^{-1}=1,$$

so $y\in\bar{B}$ and therefore $h(y)\le h(x)$ by the defining property of $K^{\delta}_{\sigma}$. Now Basic Properties of Twice Differentiability at a Point (iii) gives

$$Df(x)-\bigl(B_{\delta}x-p\bigr)=0_{\mathbb{R}^{N}},\qquad D^{2}f(x)-B_{\delta}\preceq 0_{N},$$

whence $Df(x)=B_{\delta}x-p$, and, adding $B_{\delta}$ to both sides of the second relation as permitted by Euclidean Space and Real Matrices: Standing Notation (iv), $D^{2}f(x)\preceq B_{\delta}$. The remaining inequality $-\lambda I_{N}\preceq D^{2}f(x)$ is Alexandrov's Theorem for Semiconvex Functions on an Open Convex Set (ii), applied as in Step 2.

Two consequences will be used. First, by claims 6 and 5 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square and Vector, Entry and Comparison Bounds for the Norm of a Symmetric Real Matrix (iii),

$$\lVert Df(x)\rVert\le\lVert B_{\delta}x\rVert+\lVert p\rVert\le\lVert B_{\delta}\rVert\,\lVert x\rVert+\sigma\le\bigl(\lVert B\rVert+1\bigr)\lVert x\rVert+\sigma .$$

Second, by Limits and Bounded Sequences of Symmetric Real Matrices (iv), applied with $a=\lambda$ and $C=B_{\delta}$,

$$\lVert D^{2}f(x)\rVert\le\lambda+\lVert B_{\delta}\rVert\le\Lambda .$$

Step 4 (construction of the sequence; proof of claim 1). Let $(\delta_{k})_{k\in\mathbb{N}}$ be the sequence of observation (0b), so $0<\delta_{k}\le1$ for every $k$ and $(\delta_{k})$ converges to $0$. Fix $k\in\mathbb{N}$. Apply Step 2 with $\delta=\delta_{k}$, obtaining $\delta_{0}(\delta_{k})$, and then claim 4 of Jensen's Lemma: the Contact Set of a Semiconvex Function at a Strict Maximum has Positive Measure with $\rho=\delta_{k}$, obtaining a real $\delta_{1}^{(k)}$ with $0<\delta_{1}^{(k)}\le\delta_{0}(\delta_{k})$ such that $K^{\delta_{k}}_{\sigma}\subseteq B_{d_{E}}(0_{\mathbb{R}^{N}},\delta_{k})$ whenever $0<\sigma\le\delta_{1}^{(k)}$. Put $\sigma_{k}=\min\bigl\{\delta_{k},\delta_{1}^{(k)}\bigr\}$, which exists by claim 9 of Elementary Order Arithmetic in an Ordered Field and is positive.

By claim 1 of Jensen's Lemma: the Contact Set of a Semiconvex Function at a Strict Maximum has Positive Measure the set $K^{\delta_{k}}_{\sigma_{k}}$ is nonempty and belongs to $\mathcal{B}(\mathbb{R}^{N})$, and by claim 3 there, applied with the set $Z$ of Step 2, there is $x'_{k}\in K^{\delta_{k}}_{\sigma_{k}}$ with $x'_{k}\notin Z$. Since $E\subseteq Z$, the function $f$ is twice differentiable at $x'_{k}$. From $K^{\delta_{k}}_{\sigma_{k}}\subseteq B_{d_{E}}(0_{\mathbb{R}^{N}},\delta_{k})$ we get $\lVert x'_{k}\rVert<\delta_{k}$, and Step 3, applied with $\delta=\delta_{k}$, $\sigma=\sigma_{k}$ and $x=x'_{k}$, gives

$$\bigl\lVert Df(x'_{k})\bigr\rVert\le\bigl(\lVert B\rVert+1\bigr)\delta_{k}+\sigma_{k}\le\bigl(\lVert B\rVert+2\bigr)\delta_{k},\qquad -\lambda I_{N}\preceq D^{2}f(x'_{k})\preceq B+\delta_{k}I_{N},$$

and $\lVert D^{2}f(x'_{k})\rVert\le\Lambda$.

The sequence $(x'_{k})_{k\in\mathbb{N}}$ converges to $0_{\mathbb{R}^{N}}$: given a positive $\varepsilon\in\mathbb{R}$, there is $K\in\mathbb{N}$ with $\delta_{k}<\varepsilon$ for $k\ge K$, and then $d_{E}(x'_{k},0_{\mathbb{R}^{N}})=\lVert x'_{k}\rVert<\varepsilon$. Similarly $\bigl(Df(x'_{k})\bigr)_{k\in\mathbb{N}}$ converges to $0_{\mathbb{R}^{N}}$: the number $\lVert B\rVert+2$ is positive, so $\varepsilon\bigl(\lVert B\rVert+2\bigr)^{-1}$ is positive by claims 5 and 7 of Elementary Order Arithmetic in an Ordered Field, and choosing $K$ with $\delta_{k}<\varepsilon\bigl(\lVert B\rVert+2\bigr)^{-1}$ for $k\ge K$ gives $\lVert Df(x'_{k})\rVert<\varepsilon$ for such $k$.

By Limits and Bounded Sequences of Symmetric Real Matrices (i), applied to the sequence $\bigl(D^{2}f(x'_{k})\bigr)_{k\in\mathbb{N}}$ in $\mathcal{S}(N)$ with the bound $\Lambda$, there are a strictly increasing map $\kappa:\mathbb{N}\to\mathbb{N}$ and $X\in\mathcal{S}(N)$ such that $\bigl(D^{2}f(x'_{\kappa(j)})\bigr)_{j\in\mathbb{N}}$ converges to $X$ in $\mathcal{S}(N)$. Put $x_{j}=x'_{\kappa(j)}$ for $j\in\mathbb{N}$. Each $\bigl(x_{j}\bigr)_{j\in\mathbb{N}}$ and $\bigl(Df(x_{j})\bigr)_{j\in\mathbb{N}}$ is a subsequence of a sequence already shown to converge to $0_{\mathbb{R}^{N}}$, so both converge to $0_{\mathbb{R}^{N}}$ by A Subsequence of a Convergent Sequence Has the Same Limit; and $f$ is twice differentiable at every $x_{j}$.

It remains to prove the two matrix inequalities. The constant sequence with value $-\lambda I_{N}$ converges to $-\lambda I_{N}$ in $\mathcal{S}(N)$, and $-\lambda I_{N}\preceq D^{2}f(x_{j})$ for every $j$, so $-\lambda I_{N}\preceq X$ by Limits and Bounded Sequences of Symmetric Real Matrices (iii). Next, $\bigl(\delta_{\kappa(j)}\bigr)_{j\in\mathbb{N}}$ converges to $0$ in $\mathbb{R}$ by A Subsequence of a Convergent Sequence Has the Same Limit, and

$$d_{\mathcal{S}(N)}\bigl(B+\delta_{\kappa(j)}I_{N},\,B\bigr)=\bigl\lVert\delta_{\kappa(j)}I_{N}\bigr\rVert=\delta_{\kappa(j)}$$

by Vector, Entry and Comparison Bounds for the Norm of a Symmetric Real Matrix (vi), so $\bigl(B+\delta_{\kappa(j)}I_{N}\bigr)_{j\in\mathbb{N}}$ converges to $B$ in $\mathcal{S}(N)$. Since $D^{2}f(x_{j})\preceq B+\delta_{\kappa(j)}I_{N}$ for every $j$, Limits and Bounded Sequences of Symmetric Real Matrices (iii) gives $X\preceq B$. This proves claim 1.

Step 5 (proof of claim 2). Let $X\in\mathcal{S}(N)$ and $(x_{k})_{k\in\mathbb{N}}$ have the properties listed in claim 1. For each $k$ the function $f$ is twice differentiable at $x_{k}$ with first-order coefficient $Df(x_{k})$ and Hessian $D^{2}f(x_{k})$, so by Quadratic Test Functions, Limits, Translation and Locality for Approximability by Test Data (ii), applied with $U=\mathbb{R}^{N}$ and $u=f$, the quadruple

$$\bigl(x_{k},\,f(x_{k}),\,Df(x_{k}),\,D^{2}f(x_{k})\bigr)$$

is approximable by test data from above for $f$.

The sequence $\bigl(f(x_{k})\bigr)_{k\in\mathbb{N}}$ converges to $f(0_{\mathbb{R}^{N}})$ in $\mathbb{R}$. Indeed, $\mathbb{R}^{N}$ is open and convex and $f$ is semiconvex on it with the nonnegative constant $\lambda$, so claim 2 of Local Lipschitz Bound and Continuity for a Semiconvex Function on an Open Convex Set, applied with $S=U=\mathbb{R}^{N}$ and the point $0_{\mathbb{R}^{N}}$, provides for each positive $\varepsilon\in\mathbb{R}$ a positive $\delta\in\mathbb{R}$ such that $\lVert y-0_{\mathbb{R}^{N}}\rVert<\delta$ implies $|f(y)-f(0_{\mathbb{R}^{N}})|<\varepsilon$; since $(x_{k})$ converges to $0_{\mathbb{R}^{N}}$ there is $K\in\mathbb{N}$ with $\lVert x_{k}-0_{\mathbb{R}^{N}}\rVert=d_{E}(x_{k},0_{\mathbb{R}^{N}})<\delta$ for $k\ge K$, and then $|f(x_{k})-f(0_{\mathbb{R}^{N}})|<\varepsilon$.

Thus $(x_{k})$ converges to $0_{\mathbb{R}^{N}}$, $\bigl(f(x_{k})\bigr)$ converges to $f(0_{\mathbb{R}^{N}})$, $\bigl(Df(x_{k})\bigr)$ converges to $0_{\mathbb{R}^{N}}$ and $\bigl(D^{2}f(x_{k})\bigr)$ converges to $X$. By Quadratic Test Functions, Limits, Translation and Locality for Approximability by Test Data (iii), applied with $U=\mathbb{R}^{N}$, $u=f$, $x_{0}=0_{\mathbb{R}^{N}}$, $p=0_{\mathbb{R}^{N}}$ and the matrix $X$, the quadruple $\bigl(0_{\mathbb{R}^{N}},f(0_{\mathbb{R}^{N}}),0_{\mathbb{R}^{N}},X\bigr)$ is approximable by test data from above for $f$. The final assertion of claim 2 follows by taking the $X$ and the sequence produced in claim 1.