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 The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite, 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$ (i).

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 The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite; hence, by claim 1 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum,

$$h\cdot(Sh)=\tfrac{1}{2}\bigl(h\cdot(Mh)+h\cdot(M^{\top}h)\bigr)=h\cdot(Mh). \tag{S}$$

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 Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square 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 (ii) 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

$$\tfrac{1}{N}\,q_{k}\cdot h\le f(y_{k+1})-f(y_{k})\le\tfrac{1}{N}\,q_{k+1}\cdot h\qquad(0\le k\le N-1),$$

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

$$\tfrac{1}{N}\sum_{k=0}^{N-1}q_{k}\cdot h\;\le\;f(y+h)-f(y)\;\le\;\tfrac{1}{N}\sum_{k=1}^{N}q_{k}\cdot h. \tag{T}$$

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 The Cauchy-Schwarz Inequality on $\mathbb{R}^n$

$$|r_{k}\cdot h|\le\varepsilon\lVert h\rVert^{2}.$$

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

$$\tfrac{1}{N}\sum_{k=0}^{N-1}t_{k}=\frac{N-1}{2N},\qquad\tfrac{1}{N}\sum_{k=1}^{N}t_{k}=\frac{N+1}{2N},$$

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

$$p\cdot h+\frac{N-1}{2N}(Mh)\cdot h-\varepsilon\lVert h\rVert^{2}\;\le\;f(y+h)-f(y)\;\le\;p\cdot h+\frac{N+1}{2N}(Mh)\cdot h+\varepsilon\lVert h\rVert^{2}.$$

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

$$-\frac{1}{2N}\bigl|(Mh)\cdot h\bigr|-\varepsilon\lVert h\rVert^{2}\;\le\;\Theta\;\le\;\frac{1}{2N}\bigl|(Mh)\cdot h\bigr|+\varepsilon\lVert h\rVert^{2}.$$

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 The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite 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

$$\Bigl|f(y+h)-f(y)-p\cdot h-\tfrac{1}{2}h\cdot(Sh)\Bigr|\le\varepsilon\lVert h\rVert^{2}.$$

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