Proof of Quadratic and Affine Functions of Class $C^2$, Translation, and Quadratic Perturbation of Semiconvexity

Throughout we use the notation of the statement. We first record an identity used twice below.

(P) Let $x,y\in\mathbb{R}^{n}$, let $t\in\mathbb{R}$, put $s=1-t$ and $w=t\,x+s\,y$. Then

Indeed, since $M^{\top}=M$, claim 5 of Elementary Properties of the Transpose of a Real Matrix together with claim 1 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$ gives $x\cdot(My)=y\cdot(Mx)$. By claim 3 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum we have $Mw=t(Mx)+s(My)$, so expanding with claims 2, 3, 4 and 5 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$,

Hence the left-hand side of the display equals $(t-t^{2})\,x\cdot(Mx)+(s-s^{2})\,y\cdot(My)-2ts\,x\cdot(My)$. Since $t+s=1$ we have $t-t^{2}=t(1-t)=ts$ and $s-s^{2}=s(1-s)=st$, so this equals

the last equality by expanding $(x-y)\cdot(M(x-y))$ in the same way and using $x\cdot(My)=y\cdot(Mx)$.

Claim 1. By claim 4 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum and the coordinate description of the dot product,

For $i\in[n]$ let $\pi_{i}:\mathbb{R}^{n}\to\mathbb{R}$ be the $i$th coordinate function, $\pi_{i}(z)=z_{i}$. The set $\mathbb{R}^{n}$ is open, every point being the centre of a ball contained in it. By claim 2 of Constants, Coordinate Functions, Sums and Products of $C^k$ Functions on a Euclidean Open Set the functions $\pi_{i}$ and the constant functions are smooth on $\mathbb{R}^{n}$, hence of class $C^{2}$, and by claim 3 of that lemma sums, scalar multiples and products of functions of class $C^{2}$ are again of class $C^{2}$. Since a finite sum is defined recursively, induction on the upper limit shows that a finite sum of functions of class $C^{2}$ is of class $C^{2}$. Applying this to the display shows that $Q$ is of class $C^{2}$ on $\mathbb{R}^{n}$.

We next compute the partial derivatives. Directly from Partial Derivative on a Euclidean Open Set, for $k,i\in[n]$ and $a\in\mathbb{R}^{n}$ the difference quotient of $\pi_{i}$ at $a$ with respect to the $k$th variable is constantly $1$ if $k=i$ and constantly $0$ otherwise, so $\partial_{k}\pi_{i}(a)=1$ if $k=i$ and $\partial_{k}\pi_{i}(a)=0$ otherwise. By claim 1 of Constants, Coordinate Functions, Sums and Products of $C^k$ Functions on a Euclidean Open Set, extended to finite sums by the same induction as above, and by the product rule there,

By claim 7 of Properties of Finite Sums the last sum equals $q_{k}$. Splitting the double sum by claim 2 of Properties of Finite Sums, applied to the inner and then the outer sum, gives two double sums. In the first, for fixed $i$ claim 3 of Properties of Finite Sums gives $\sum_{j}M_{ij}\partial_{k}\pi_{i}(z)z_{j}=\partial_{k}\pi_{i}(z)\sum_{j}M_{ij}z_{j}=\partial_{k}\pi_{i}(z)\,(Mz)_{i}$ by Matrix-Vector Product, and then claim 7 of Properties of Finite Sums over $i$ leaves only the term $i=k$, giving $(Mz)_{k}$. In the second, for fixed $i$ only the term $j=k$ survives, again by claim 7, giving $M_{ik}z_{i}$, and summing over $i$ and using $M_{ik}=M_{ki}$ gives $\sum_{i}M_{ki}z_{i}=(Mz)_{k}$. Hence

so $DQ(z)=Mz+q$ by Gradient of a Real-Valued Function on a Euclidean Open Set. Consequently $\partial_{l}Q$ is the function $z\mapsto\sum_{j=1}^{n}M_{lj}z_{j}+q_{l}$, whose partial derivative with respect to the $k$th variable is, by the same computation, $\partial_{k}\partial_{l}Q(z)=\sum_{j=1}^{n}M_{lj}\partial_{k}\pi_{j}(z)=M_{lk}$. By Hessian Matrix of a C^2 Function the entry of $D^{2}Q(z)$ in row $k$ and column $l$ is $\partial_{k}\partial_{l}Q(z)=M_{lk}=M_{kl}$, so $D^{2}Q(z)=M$.

Finally, for open $V\subseteq\mathbb{R}^{n}$ the restriction of $Q$ to $V$ is of class $C^{2}$ on $V$ by claim 3 of Restriction of a $C^k$ Map to an Open Subset, and its partial derivatives at points of $V$ agree with those of $Q$ by claim 1 of that lemma, so its gradient and Hessian at $z\in V$ are $Mz+q$ and $M$.

Claim 2. Let $z_{0}\in V-b$, so $z_{0}+b\in V$. Since $V$ is open there is a positive $\rho$ with $\{z':d_{E}(z',z_{0}+b)<\rho\}\subseteq V$. For $z\in\mathbb{R}^{n}$ we have $(z+b)-(z_{0}+b)=z-z_{0}$, so $d_{E}(z+b,z_{0}+b)=\lVert z-z_{0}\rVert=d_{E}(z,z_{0})$ by claim 2 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$; hence $d_{E}(z,z_{0})<\rho$ implies $z+b\in V$, that is $z\in V-b$. So $V-b$ is open.

Let $\psi$ be of class $C^{2}$ on $V$ and let $i\in[n]$ and $z\in V-b$. For $h\in\mathbb{R}$ the point obtained from $z$ by adding $h$ to its $i$th coordinate, translated by $b$, is the point obtained from $z+b$ by adding $h$ to its $i$th coordinate; therefore the difference quotients of $\psi_{b}$ at $z$ and of $\psi$ at $z+b$ with respect to the $i$th variable coincide, and Partial Derivative on a Euclidean Open Set gives that $\partial_{i}\psi_{b}(z)$ exists and equals $\partial_{i}\psi(z+b)$. In other words $\partial_{i}\psi_{b}=(\partial_{i}\psi)_{b}$, the translate of $\partial_{i}\psi$ in the same sense.

The translation map $T:V-b\to V$, $T(z)=z+b$, satisfies $d_{E}(T(z),T(z'))=d_{E}(z,z')$ as computed above, hence is Lipschitz and so continuous by A Lipschitz Map is Uniformly Continuous. Therefore, by claim 3 of Semicontinuity and Continuity Under Composition with a Continuous Map, the translate of any function continuous on $V$ is continuous on $V-b$. Since $\psi$ is of class $C^{2}$ on $V$, it is of class $C^{1}$ and each $\partial_{i}\psi$ is of class $C^{1}$ on $V$, by clauses 1 and 2 of C^k Maps on a Euclidean Open Set. Applying the two previous paragraphs, $\psi_{b}$ is continuous on $V-b$, its partial derivatives exist and equal the translates of those of $\psi$ and are continuous, so $\psi_{b}$ is of class $C^{1}$; and the same argument applied to each $\partial_{i}\psi$ shows that $\partial_{i}\psi_{b}=(\partial_{i}\psi)_{b}$ is of class $C^{1}$ on $V-b$. By clause 2 of C^k Maps on a Euclidean Open Set, $\psi_{b}$ is of class $C^{2}$ on $V-b$. Finally $D\psi_{b}(z)=\bigl(\partial_{1}\psi(z+b),\dots,\partial_{n}\psi(z+b)\bigr)=D\psi(z+b)$, and the entry of $D^{2}\psi_{b}(z)$ in row $i$ and column $j$ is $\partial_{i}\partial_{j}\psi_{b}(z)=\partial_{i}\bigl((\partial_{j}\psi)_{b}\bigr)(z)=\partial_{i}\partial_{j}\psi(z+b)$, so $D^{2}\psi_{b}(z)=D^{2}\psi(z+b)$.

Claim 3. Let $x,y\in C$ and let $t\in\mathbb{R}$ with $0\le t\le1$; put $s=1-t$, so $0\le s$, and $w=t\,x+s\,y$, which lies in $C$ because $C$ is convex. Since $t+s=1$, claims 2, 4 and 5 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$ give $t\,(q\cdot x+c)+s\,(q\cdot y+c)=q\cdot w+c$. Hence, by (P),

By hypothesis $0_{n}\preceq M$, which by The Positive Semidefinite Ordering on Symmetric Matrices means $\zeta\cdot(0_{n}\zeta)\le\zeta\cdot(M\zeta)$ for every $\zeta$; since $\zeta\cdot(0_{n}\zeta)=\sum_{i=1}^{n}\sum_{j=1}^{n}0\cdot\zeta_{i}\zeta_{j}=0$ by claim 4 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum together with two applications of claim 7 of Properties of Finite Sums, every summand being $0$, the quadratic form $(x-y)\cdot(M(x-y))$ is nonnegative. As $ts$ is nonnegative, the right-hand side is nonnegative, so $Q(w)\le t\,Q(x)+s\,Q(y)$. By Convex Real-Valued Function on a Convex Subset of $\mathbb{R}^n$ the restriction of $Q$ to $C$ is convex on $C$.

Claim 4. Write $L=\lVert M\rVert$, which is nonnegative by claim 1 of Properties of the Norm of a Symmetric Real Matrix; hence $0\le\lambda+L$. Let $x,y\in C$ and $t\in\mathbb{R}$ with $0\le t\le1$, put $s=1-t$ and $w=t\,x+s\,y\in C$. Since $f$ is semiconvex on $C$ with constant $\lambda$, Quadratic Increment Characterisation of Semiconvexity gives

Using $t\,(q\cdot x+c)+s\,(q\cdot y+c)=q\cdot w+c$ as in claim 3, we obtain

so by the previous display and (P),

By claim 2 of Properties of the Norm of a Symmetric Real Matrix and claim 3 of Properties of the Absolute Value in an Ordered Field, $(x-y)\cdot(M(x-y))\le L\,\lVert x-y\rVert^{2}$, and $ts$ is nonnegative, so

As $x,y\in C$ and $t$ were arbitrary, Quadratic Increment Characterisation of Semiconvexity shows that $g$ is semiconvex on $C$ with constant $\lambda+L=\lambda+\lVert M\rVert$.