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 The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite, and $\lVert\lambda v\rVert=|\lambda|\lVert v\rVert$ and the triangle inequality are claims 5 and 6 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square. 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$ (iv), 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 (iv) 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$ (iv), applied with $m=n$, the set

$$N_{J}=\{\,x\in\mathbb{R}^{n}:J\text{ is not differentiable at }x\,\}$$

is null, and by Lipschitz Images and Lebesgue Outer Measure in $\mathbb{R}^n$ (iii) 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 (i), 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 (ii) 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}$,

$$\partial f(y)=\{p\}.$$

Put $x=y+p$. Then $x-y=p\in\partial f(y)$, so Properties of the Proximal Map of a Convex Function (i) 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 (i) 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 (v) the map $h\mapsto Ah$ is therefore injective. By An Injective Nondegenerate Square Matrix is Invertible (i) 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 (iv) the matrix $A$ is invertible with

$$\lVert A^{-1}k\rVert\le c^{-1}\lVert k\rVert\qquad\text{for every }k\in\mathbb{R}^{n}.$$

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 Functions Between Euclidean Spaces, applied to $J$ at $x$ with $\eta$ in place of $\varepsilon$, there is $\delta_{2}>0$ such that

$$\lVert J(x')-J(x)-A(x'-x)\rVert\le\eta\,\lVert x'-x\rVert\qquad\text{whenever }\lVert x'-x\rVert<\delta_{2}, \tag{J}$$

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 (i). Moreover $x'-x=(y'-y)+(q'-p)$, so

$$\lVert x'-x\rVert\le\lVert y'-y\rVert+\lVert q'-p\rVert<\tfrac{1}{2}\delta_{2}+\tfrac{1}{2}\delta_{2}=\delta_{2},$$

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$,

$$c\,\lVert x'-x\rVert\le\lVert A(x'-x)\rVert\le\lVert y'-y\rVert+\lVert R\rVert\le\lVert y'-y\rVert+\tfrac{c}{2}\lVert x'-x\rVert,$$

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

$$q'-p-M(y'-y)=(x'-x)-A^{-1}(y'-y).$$

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

$$q'-p-M(y'-y)=-A^{-1}R,$$

and consequently

$$\bigl\lVert q'-p-M(y'-y)\bigr\rVert=\lVert A^{-1}R\rVert\le c^{-1}\lVert R\rVert\le c^{-1}\eta\,\lVert x'-x\rVert\le\frac{2\eta}{c^{2}}\,\lVert y'-y\rVert\le\varepsilon\,\lVert y'-y\rVert,$$

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 (ii) 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 (i) 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))$,

$$\bigl|f(y+th)-f(y)-t\,p\cdot h-\tfrac{1}{2}t^{2}h\cdot(Bh)\bigr|\le\varepsilon t^{2}\lVert h\rVert^{2}$$

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,

$$\bigl|f(y+th)+f(y-th)-2f(y)-t^{2}h\cdot(Bh)\bigr|\le2\varepsilon t^{2}\lVert h\rVert^{2}.$$

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,

$$0\le t^{2}h\cdot(Bh)+2\varepsilon t^{2}\lVert h\rVert^{2},$$

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.