Proof of A First-Order Expansion of the Subdifferential Gives a Second-Order Expansion of the Function

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 $M(\lambda v+\mu w)=\lambda\,Mv+\mu\,Mw$ is claim 1 of Linearity, Compatibility with the Matrix Product, and a Norm Bound for the Matrix-Vector Product. Membership in a subdifferential always refers to Subdifferential of a Real-Valued Function on a Convex Subset of $\mathbb{R}^n$ §subdifferential.

The matrix $S$. By claim 2 of Elementary Properties of the Transpose of a Real Matrix, $(M+M^{\top})^{\top}=M^{\top}+(M^{\top})^{\top}$, and $(M^{\top})^{\top}=M$ by claim 1 of that lemma; hence $(M+M^{\top})^{\top}=M+M^{\top}$ and, again by claim 2, $S^{\top}=S$, so $S\in\mathcal{S}(n)$. Moreover, for $h\in\mathbb{R}^{n}$, claim 5 of Elementary Properties of the Transpose of a Real Matrix with $v=w=h$ gives $h\cdot(Mh)=(M^{\top}h)\cdot h=h\cdot(M^{\top}h)$, the last step by claim 1 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$; hence, by claim 1 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum,

Claim 1. Let $h\in\mathbb{R}^{n}$ with $\lVert h\rVert<\delta$. If $h=0$ the asserted inequality reads $0\le0$, so assume $h\neq0$. Let $N\in\mathbb{N}$, and for $k\in\{0,1,\dots,N\}$ put $t_{k}=k/N$ and $y_{k}=y+t_{k}h$, so that $y_{0}=y$ and $y_{N}=y+h$. Since $0\le t_{k}\le1$, claim 5 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ gives $\lVert y_{k}-y\rVert=t_{k}\lVert h\rVert\le\lVert h\rVert<\delta$.

Because $\mathbb{R}^{n}$ is open and convex, The Subdifferential of a Convex Function on an Open Convex Set is Nonempty §nonempty shows that $\partial f(y_{k})$ is nonempty; choose $q_{k}\in\partial f(y_{k})$ for each of the finitely many indices $k$, and take $q_{0}=p$, which is legitimate since $p\in\partial f(y)=\partial f(y_{0})$.

The subgradient inequality at $y_{k}$ tested at $y_{k+1}$, and at $y_{k+1}$ tested at $y_{k}$, give

since $y_{k+1}-y_{k}=\tfrac{1}{N}h$. Summing over $k$ and noting that the middle terms telescope to $f(y+h)-f(y)$,

Put $r_{k}=q_{k}-p-M(y_{k}-y)$. Since $\lVert y_{k}-y\rVert<\delta$, the hypothesis gives $\lVert r_{k}\rVert\le\varepsilon\lVert y_{k}-y\rVert=\varepsilon t_{k}\lVert h\rVert\le\varepsilon\lVert h\rVert$, so by Cauchy-Schwarz Inequality for the Euclidean Dot Product

Since $M(y_{k}-y)=t_{k}\,Mh$, we get $q_{k}\cdot h=p\cdot h+t_{k}\,(Mh)\cdot h+r_{k}\cdot h$. Using $\sum_{k=0}^{N-1}k=\tfrac{1}{2}N(N-1)$ and $\sum_{k=1}^{N}k=\tfrac{1}{2}N(N+1)$,

and each of the two averages of the $r_{k}\cdot h$ has absolute value at most $\varepsilon\lVert h\rVert^{2}$, by claim 5 of Properties of the Absolute Value in an Ordered Field. Hence (T) becomes

Writing $\Theta=f(y+h)-f(y)-p\cdot h-\tfrac{1}{2}(Mh)\cdot h$ and using $\frac{N\pm1}{2N}-\frac{1}{2}=\pm\frac{1}{2N}$, this says

The number $|(Mh)\cdot h|$ does not depend on $N$, so by The Archimedean Property of the Real Numbers the quantity $\frac{1}{2N}|(Mh)\cdot h|$ is smaller than any prescribed positive real for $N$ large. Hence $|\Theta|\le\varepsilon\lVert h\rVert^{2}$ by claim 6 of Properties of the Absolute Value in an Ordered Field, and by (S) together with claim 1 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$ this is the asserted inequality.

Claim 2. Let $\varepsilon>0$ and let $\delta>0$ be as supplied by the hypothesis for this $\varepsilon$. By claim 1, every $h$ with $\lVert h\rVert<\delta$ satisfies $y+h\in\mathbb{R}^{n}$ and

Since $S\in\mathcal{S}(n)$, this is precisely the condition of Twice Differentiability at a Point §twice-differentiable with $U=\mathbb{R}^{n}$, first-order coefficient $p$ and Hessian $S$.