Proof of Alexandrov's Theorem for Semiconvex Functions on an Open Convex Set

We use the notation of the statement. Algebraic manipulations of dot products use Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$, and $\lVert v\rVert^{2}=v\cdot v$ is claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$.

Preliminaries. Let $q:\mathbb{R}^{n}\to\mathbb{R}$ be given by $q(x)=\tfrac{\mu}{2}\,d_{E}(x,0)^{2}$, where $0$ is the zero vector. By claim 2 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$, $d_{E}(x,0)=\lVert x-0\rVert=\lVert x\rVert$, so $q(x)=\tfrac{\mu}{2}\lVert x\rVert^{2}$, and by Semiconvex Function on a Convex Subset of $\mathbb{R}^n$ the function $g:U\to\mathbb{R}$ given by

is convex on $U$. By claims 2 and 3 of A Scaled Squared Distance to a Point is of Class $C^2$, with Gradient and Hessian, applied with the open set $\mathbb{R}^{n}$, the point $a=0$ and the constant $\mu/2$, the function $q$ is of class $C^{2}$ on $\mathbb{R}^{n}$ with Hessian matrix $D^{2}q(x)=\mu I_{n}$ at every $x$. Hence, by claim 2 of Basic Properties of Twice Differentiability at a Point, $q$ is twice differentiable at every point of $\mathbb{R}^{n}$ with Hessian $\mu I_{n}$.

Sub-step (sums and differences). Let $V,V'\subseteq\mathbb{R}^{n}$ be open, let $y\in V\cap V'$, let $u:V\to\mathbb{R}$ be twice differentiable at $y$ with first-order coefficient $p_{u}$ and Hessian $B_{u}$, and let $v:V'\to\mathbb{R}$ be twice differentiable at $y$ with first-order coefficient $p_{v}$ and Hessian $B_{v}$. Then the functions $u+v$ and $u-v$, defined on the open set $V\cap V'$, are twice differentiable at $y$, with first-order coefficients $p_{u}+p_{v}$ and $p_{u}-p_{v}$ and Hessians $B_{u}+B_{v}$ and $B_{u}-B_{v}$ respectively. Indeed, given $\varepsilon>0$, let $\delta$ be the smaller of the two radii supplied by Twice Differentiability at a Point §twice-differentiable for $u$ and for $v$ with $\varepsilon/2$ in place of $\varepsilon$; adding or subtracting the two estimates and using claim 5 of Properties of the Absolute Value in an Ordered Field, together with $(B_{u}\pm B_{v})h=B_{u}h\pm B_{v}h$ from claim 1 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum and bilinearity, gives the required estimate with $\varepsilon$. The matrices $B_{u}\pm B_{v}$ are symmetric by claim 2 of Elementary Properties of the Transpose of a Real Matrix.

In particular, since $q$ is twice differentiable everywhere, a point $y\in U$ is a point of twice differentiability of $f$ if and only if it is one of $g=f+q$, and then $D^{2}g(y)=D^{2}f(y)+\mu I_{n}$.

Sub-step (locality). Let $V$ and $V'$ be open subsets of $\mathbb{R}^{n}$, let $u:V\to\mathbb{R}$ and $u':V'\to\mathbb{R}$, and suppose that $u$ and $u'$ agree on an open set $W$ with $y\in W\subseteq V\cap V'$. Then $u$ is twice differentiable at $y$ if and only if $u'$ is, and in that case the first-order coefficients agree and the Hessians agree. Indeed, since $W$ is open there is $\delta'>0$ with $y+h\in W$ whenever $\lVert h\rVert<\delta'$. Suppose one of the two functions is twice differentiable at $y$ with first-order coefficient $p$ and Hessian $B$; given $\varepsilon>0$, take for $\delta$ the smaller of $\delta'$ and the radius supplied for it by Twice Differentiability at a Point §twice-differentiable. For $\lVert h\rVert<\delta$ the two functions take the same values at $y$ and at $y+h$, both of which lie in $W$, so the same estimate holds for the other function; hence it too is twice differentiable at $y$ with first-order coefficient $p$ and Hessian $B$, and the coefficients are unique by A Symmetric Matrix is Determined by its Quadratic Form, and a Second-Order Expansion by its Coefficients §uniqueness.

Sub-step (a norm inequality). For $v=(v_{1},\dots,v_{n})\in\mathbb{R}^{n}$ one has $\lVert v\rVert\le\sigma_{n}\max_{1\le k\le n}|v_{k}|$: by claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ and Difference, Dot Product, and Orthogonality in $\mathbb{R}^n$, $\lVert v\rVert^{2}=\sum_{k}v_{k}^{2}\le n(\max_{k}|v_{k}|)^{2}=(\sigma_{n}\max_{k}|v_{k}|)^{2}$, and both sides of the asserted inequality are nonnegative, so it holds, since the reverse strict inequality would give the reverse inequality between the squares.

Claim 1. Write $\mathbb{Q}$ for the rational numbers, and let $\mathcal{C}$ be the set of pairs $(w,r)$ with $w\in\mathbb{R}^{n}$ having all coordinates rational, $r\in\mathbb{Q}$ with $0<r$, $\bar{B}(w,2r)\subseteq U$, and $g$ Lipschitz with some constant on $\bar{B}(w,2r)$. By The Integers and the Rational Numbers are Countable and Products and Powers of Countable Sets the set $\mathcal{C}$ is countable.

We claim $U=\bigcup_{(w,r)\in\mathcal{C}}B(w,r)$. Each $B(w,r)\subseteq\bar{B}(w,2r)\subseteq U$. Conversely let $y_{0}\in U$; since $U$ is open, $y_{0}$ is an interior point of $U$, so A Convex Function is Lipschitz on a Ball around an Interior Point, applied to the convex function $g$, provides $\rho,L\in\mathbb{R}$ with $0<\rho$, $0\le L$, $\bar{B}(y_{0},\rho)\subseteq U$ and $|g(z)-g(z')|\le L\lVert z-z'\rVert$ for $z,z'\in\bar{B}(y_{0},\rho)$. By The Rational Numbers are Dense in the Real Numbers choose $r\in\mathbb{Q}$ with $\rho/8<r<\rho/4$, and choose rational numbers $w_{1},\dots,w_{n}$ with $|w_{k}-(y_{0})_{k}|<\rho/(8\sigma_{n})$ for every $k$; by the norm inequality above, $w=(w_{1},\dots,w_{n})$ satisfies $\lVert w-y_{0}\rVert<\rho/8<r$, so $y_{0}\in B(w,r)$. If $z\in\bar{B}(w,2r)$ then, by claim 6 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$,

so $\bar{B}(w,2r)\subseteq\bar{B}(y_{0},\rho)\subseteq U$ and $g$ is Lipschitz with constant $L$ on $\bar{B}(w,2r)$. Hence $(w,r)\in\mathcal{C}$ and $y_{0}\in B(w,r)$.

Fix $(w,r)\in\mathcal{C}$ and a Lipschitz constant $M$ for $g$ on $\bar{B}(w,2r)$. By Extending a Convex Function from a Closed Ball to All of $\mathbb{R}^n$ §well-defined, Extending a Convex Function from a Closed Ball to All of $\mathbb{R}^n$ §convex and Extending a Convex Function from a Closed Ball to All of $\mathbb{R}^n$ §agrees, applied to $g$ on $U$ with the centre $w$ and radius $r$, there is a function $F:\mathbb{R}^{n}\to\mathbb{R}$ that is convex on $\mathbb{R}^{n}$ and agrees with $g$ on $\bar{B}(w,r)$. By Alexandrov's Theorem: a Convex Function on $\mathbb{R}^n$ is Twice Differentiable Almost Everywhere §ae there is a Borel set $N_{w,r}$ with $\lambda_{n}(N_{w,r})=0$ such that $F$ is twice differentiable at every point of $\mathbb{R}^{n}\setminus N_{w,r}$.

Let $y\in B(w,r)\setminus N_{w,r}$. The set $B(w,r)$ is open, is contained in $\bar{B}(w,r)$ and hence in $U$, and $F$ agrees with $g$ on it; so by the locality sub-step, $g$ is twice differentiable at $y$, and therefore so is $f=g-q$ by the sub-step on differences. Consequently the set of those $y\in U$ at which $f$ is not twice differentiable is contained in

a countable union of null sets, which is null by claim 5 of Elementary Properties of Lebesgue Outer Measure on $\mathbb{R}^n$.

Claim 2. Let $y\in U$ be a point at which $f$ is twice differentiable; then $g$ is twice differentiable at $y$ with $D^{2}g(y)=D^{2}f(y)+\mu I_{n}$. As in the proof of claim 1, A Convex Function is Lipschitz on a Ball around an Interior Point provides $\rho,L$ with $0<\rho$, $\bar{B}(y,\rho)\subseteq U$ and $g$ Lipschitz with constant $L$ on $\bar{B}(y,\rho)$. Put $r=\rho/2$, so that $\bar{B}(y,2r)=\bar{B}(y,\rho)\subseteq U$, and let $F$ be the function supplied by Extending a Convex Function from a Closed Ball to All of $\mathbb{R}^n$ §well-defined and Extending a Convex Function from a Closed Ball to All of $\mathbb{R}^n$ §convex, which is convex on $\mathbb{R}^{n}$ and agrees with $g$ on $\bar{B}(y,r)$ by Extending a Convex Function from a Closed Ball to All of $\mathbb{R}^n$ §agrees.

The set $B(y,r)$ is open and contains $y$, and $g$ agrees with $F$ on it; so by the locality sub-step, applied with $u'=g$ on $U$, with $u=F$ on $\mathbb{R}^{n}$ and with $W=B(y,r)$, the function $F$ is twice differentiable at $y$ with the same Hessian as $g$, namely $D^{2}f(y)+\mu I_{n}$. By Alexandrov's Theorem: a Convex Function on $\mathbb{R}^n$ is Twice Differentiable Almost Everywhere §hessian-psd,

where $0_{n}$ is the real $n\times n$ matrix all of whose entries are $0$. By The Positive Semidefinite Ordering on Symmetric Matrices this says $z\cdot(0_{n}z)\le z\cdot\bigl((D^{2}f(y)+\mu I_{n})z\bigr)$ for every $z\in\mathbb{R}^{n}$; since $0_{n}z=0$ by Matrix-Vector Product, and since claims 1 and 2 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum give $(D^{2}f(y)+\mu I_{n})z=D^{2}f(y)z+\mu z$ and $((-\mu)I_{n})z=(-\mu)z$, this reads

for every $z\in\mathbb{R}^{n}$. By The Positive Semidefinite Ordering on Symmetric Matrices again this is $(-\mu)I_{n}\preceq D^{2}f(y)$.