Proof of Alexandrov's Theorem: a Convex Function on $\mathbb{R}^n$ is Twice Differentiable Almost Everywhere

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\lambda v\rVert=|\lambda|\lVert v\rVert$ and the triangle inequality are claims 5 and 6 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$. Write $\partial f=\partial_{\mathbb{R}^{n}}f$ for the subdifferential and $J=J_{f}$ for the proximal map of $f$.

Step 1 (The exceptional set). Every point of $\mathbb{R}^{n}$ is an interior point of it, so A Convex Function is Lipschitz on a Ball around an Interior Point provides, for each $x_{0}$, numbers $\rho,L$ with $0<\rho$, $0\le L$ and $|f(z)-f(w)|\le L\lVert z-w\rVert$ for $z,w\in\bar{B}(x_{0},\rho)$; that is, $f$ is locally Lipschitz on $\mathbb{R}^{n}$. By Rademacher's Theorem in $\mathbb{R}^n$ §locally-lipschitz, applied with $m=1$, the set $D$ of those $x\in\mathbb{R}^{n}$ at which $f$ is not differentiable is null.

By Properties of the Proximal Map of a Convex Function §nonexpansive the map $J:\mathbb{R}^{n}\to\mathbb{R}^{n}$ is Lipschitz with constant $1$; in particular, for every $x_{0}$ its restriction to $\bar{B}(x_{0},1)$ is Lipschitz with constant $1$, so $J$ is locally Lipschitz on $\mathbb{R}^{n}$. By Rademacher's Theorem in $\mathbb{R}^n$ §locally-lipschitz, applied with $m=n$, the set

is null, and by Lipschitz Images and Lebesgue Outer Measure in $\mathbb{R}^n$ §locally-lipschitz the image $J(N_{J})$ is null. Let $S$ be the set attached to $J$ by The Degenerate-Derivative Values of a Locally Lipschitz Map of $\mathbb{R}^n$ Form a Null Set §degenerate-set, taken with $U=\mathbb{R}^{n}$ and $T=J$; by The Degenerate-Derivative Values of a Locally Lipschitz Map of $\mathbb{R}^n$ Form a Null Set §null-image the image $J(S)$ is null.

The union $D\cup J(N_{J})\cup J(S)$ is null by claim 5 of Elementary Properties of Lebesgue Outer Measure on $\mathbb{R}^n$, so by Null Set of a Measure there is $N\in\mathcal{B}(\mathbb{R}^{n})$ with $D\cup J(N_{J})\cup J(S)\subseteq N$ and $\lambda_{n}(N)=0$. We show that $f$ is twice differentiable at every $y\in\mathbb{R}^{n}\setminus N$, which proves claim 1.

Step 2 (The situation at a point off $N$). Fix $y\in\mathbb{R}^{n}\setminus N$. Since $y\notin D$, the function $f$ is differentiable at $y$; let $p\in\mathbb{R}^{n}$ be the point whose $i$th coordinate is the entry in row $1$ and column $i$ of the derivative matrix of $f$ at $y$. By claim 4 of Elementary Calculus of the Subdifferential of a Convex Function, applied with $U=\mathbb{R}^{n}$,

Put $x=y+p$. Then $x-y=p\in\partial f(y)$, so Properties of the Proximal Map of a Convex Function §fiber gives $J(x)=y$.

If $x$ belonged to $N_{J}$ then $y=J(x)$ would lie in $J(N_{J})\subseteq N$; hence $x\notin N_{J}$ and $J$ is differentiable at $x$. Let $A$ be its derivative matrix there, a real matrix with $n$ rows and $n$ columns. Likewise, if $x$ belonged to $S$ then $y=J(x)$ would lie in $J(S)\subseteq N$; hence $x\notin S$. Since $J$ is differentiable at $x$, the description of $S$ in The Degenerate-Derivative Values of a Locally Lipschitz Map of $\mathbb{R}^n$ Form a Null Set §degenerate-set shows that there is no $\nu\in\mathbb{R}^{n}$ with $\lVert\nu\rVert=1$ and $\nu\cdot(Ah)=0$ for every $h\in\mathbb{R}^{n}$.

By Properties of the Proximal Map of a Convex Function §derivative the map $h\mapsto Ah$ is therefore injective. By An Injective Nondegenerate Square Matrix is Invertible §lower-bound there is $c\in\mathbb{R}$ with $0<c$ and $\lVert Ah\rVert\ge c\lVert h\rVert$ for every $h$, and by An Injective Nondegenerate Square Matrix is Invertible §invertible the matrix $A$ is invertible with

Put $M=A^{-1}-I_{n}$, the difference of $A^{-1}$ and the identity matrix.

Step 3 (A first-order expansion of the subdifferential). Let $\varepsilon\in\mathbb{R}$ with $0<\varepsilon$, and let $\eta$ be the smaller of $c/2$ and $\varepsilon c^{2}/2$, a positive real number. By Differentiability at a Point for Maps Between Euclidean Spaces, applied to $J$ at $x$ with $\eta$ in place of $\varepsilon$, there is $\delta_{2}>0$ such that

the case $x'=x$ holding trivially because both sides are then $0$. Since $\partial f(y)=\{p\}$, claim 5 of Elementary Calculus of the Subdifferential of a Convex Function, applied with the positive number $\delta_{2}/2$, provides $\delta_{1}>0$ such that every $y'\in\mathbb{R}^{n}$ with $\lVert y'-y\rVert<\delta_{1}$ and every $q'\in\partial f(y')$ satisfy $\lVert q'-p\rVert<\delta_{2}/2$. Let $\delta$ be the smaller of $\delta_{1}$ and $\delta_{2}/2$.

Let $y'\in\mathbb{R}^{n}$ with $\lVert y'-y\rVert<\delta$ and let $q'\in\partial f(y')$; put $x'=y'+q'$. Then $x'-y'=q'\in\partial f(y')$, so $J(x')=y'$ by Properties of the Proximal Map of a Convex Function §fiber. Moreover $x'-x=(y'-y)+(q'-p)$, so

and (J) applies. Put $R=(y'-y)-A(x'-x)$, so that $\lVert R\rVert\le\eta\lVert x'-x\rVert$ because $J(x')-J(x)=y'-y$.

We first bound $\lVert x'-x\rVert$. Since $A(x'-x)=(y'-y)-R$,

using $\eta\le c/2$; hence $\tfrac{c}{2}\lVert x'-x\rVert\le\lVert y'-y\rVert$ and $\lVert x'-x\rVert\le\tfrac{2}{c}\lVert y'-y\rVert$.

Next we identify $q'-p-M(y'-y)$. From $q'=x'-y'$ and $p=x-y$ we get $q'-p=(x'-x)-(y'-y)$, and by claims 1 and 2 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum, $M(y'-y)=A^{-1}(y'-y)-(y'-y)$. Hence

Applying $A^{-1}$ to $y'-y=A(x'-x)+R$ and using claim 1 of Linearity, Compatibility with the Matrix Product, and a Norm Bound for the Matrix-Vector Product, claim 2 of that lemma, the identity $A^{-1}A=I_{n}$ furnished by Inverse Matrix and Invertible Real Square Matrix, and claim 2 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum, we get $A^{-1}(y'-y)=(x'-x)+A^{-1}R$. Therefore

and consequently

the last step because $\eta\le\varepsilon c^{2}/2$.

Step 4 (Conclusion of claim 1). Step 3 shows that for every $\varepsilon>0$ there is $\delta>0$ such that $\lVert q'-p-M(y'-y)\rVert\le\varepsilon\lVert y'-y\rVert$ for every $y'$ with $\lVert y'-y\rVert<\delta$ and every $q'\in\partial f(y')$. Since $p\in\partial f(y)$, A First-Order Expansion of the Subdifferential Gives a Second-Order Expansion of the Function §twice-differentiable applies with this $M$ and shows that $f$ is twice differentiable at $y$, with first-order coefficient $p$ and Hessian $\tfrac{1}{2}(M+M^{\top})$. As $y\in\mathbb{R}^{n}\setminus N$ was arbitrary, claim 1 is proved.

Step 5 (Claim 2). Let $y\in\mathbb{R}^{n}$ be a point at which $f$ is twice differentiable, with first-order coefficient $p$ and Hessian $B=D^{2}f(y)$, and let $h\in\mathbb{R}^{n}$. If $h=0$ then $h\cdot(Bh)=0$, so assume $h\neq0$.

Let $\varepsilon>0$ and let $\delta>0$ be as in Twice Differentiability at a Point §twice-differentiable for this $\varepsilon$. Put $t=\delta/(2\lVert h\rVert)$, a positive real number, so that $\lVert th\rVert=\lVert -th\rVert=t\lVert h\rVert<\delta$. Applying the defining estimate to $th$ and to $-th$, and using $p\cdot(-th)=-t\,p\cdot h$ and $(-th)\cdot(B(-th))=t^{2}\,h\cdot(Bh)=(th)\cdot(B(th))$,

and the same with $-t$ in place of $t$. Adding the two, and using claim 5 of Properties of the Absolute Value in an Ordered Field,

On the other hand $y=\tfrac{1}{2}(y+th)+\tfrac{1}{2}(y-th)$, so Convex Real-Valued Function on a Convex Subset of $\mathbb{R}^n$, applied with the parameter $\tfrac{1}{2}$ and the points $y+th$ and $y-th$, gives $f(y)\le\tfrac{1}{2}f(y+th)+\tfrac{1}{2}f(y-th)$, that is $0\le f(y+th)+f(y-th)-2f(y)$. Combining with the previous display and claim 6 of Properties of the Absolute Value in an Ordered Field,

and dividing by the positive number $t^{2}$ gives $h\cdot(Bh)\ge-2\varepsilon\lVert h\rVert^{2}$. As $\varepsilon>0$ was arbitrary, $h\cdot(Bh)\ge0$.

Since every entry of $0_{n}$ is $0$, Matrix-Vector Product gives $0_{n}h=0$ and hence $h\cdot(0_{n}h)=0$. Thus $h\cdot(0_{n}h)\le h\cdot(Bh)$ for every $h\in\mathbb{R}^{n}$, which is $0_{n}\preceq B$ by The Positive Semidefinite Ordering on Symmetric Matrices.