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

$$t\,\bigl(x\cdot(Mx)\bigr)+s\,\bigl(y\cdot(My)\bigr)-w\cdot(Mw)=t\,s\,\bigl((x-y)\cdot\bigl(M(x-y)\bigr)\bigr).$$

Indeed, since $M^{\top}=M$, claim 5 of Elementary Properties of the Transpose of a Real Matrix together with claim 1 of The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite 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 The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite,

$$w\cdot(Mw)=t^{2}\,x\cdot(Mx)+2ts\,x\cdot(My)+s^{2}\,y\cdot(My).$$

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

$$ts\Bigl(x\cdot(Mx)-2\,x\cdot(My)+y\cdot(My)\Bigr)=ts\,\bigl((x-y)\cdot\bigl(M(x-y)\bigr)\bigr),$$

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,

$$Q(z)=\tfrac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}M_{ij}z_{i}z_{j}+\sum_{i=1}^{n}q_{i}z_{i}+c .$$

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, Affine Functions, Sums, Products and Quotients of Cᵏ Functions 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 of a Real-Valued Function on an Open Subset of $\mathbb{R}^n$, 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, Affine Functions, Sums, Products and Quotients of Cᵏ Functions, extended to finite sums by the same induction as above, and by the product rule there,

$$\partial_{k}Q(z)=\tfrac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}M_{ij}\Bigl(\partial_{k}\pi_{i}(z)\,z_{j}+z_{i}\,\partial_{k}\pi_{j}(z)\Bigr)+\sum_{i=1}^{n}q_{i}\,\partial_{k}\pi_{i}(z).$$

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

$$\partial_{k}Q(z)=\tfrac{1}{2}\bigl((Mz)_{k}+(Mz)_{k}\bigr)+q_{k}=(Mz)_{k}+q_{k}=(Mz+q)_{k},$$

so $DQ(z)=Mz+q$ by Gradient of a Real-Valued Function on an Open Subset of $\mathbb{R}^n$. 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 The Hessian Matrix of a Function of Class C² 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ᵏ Function 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 Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square; 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 of a Real-Valued Function on an Open Subset of $\mathbb{R}^n$ 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 and 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 Functions of Class Cᵏ on an Open Subset of ℝⁿ. 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 Functions of Class Cᵏ on an Open Subset of ℝⁿ, $\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 The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite give $t\,(q\cdot x+c)+s\,(q\cdot y+c)=q\cdot w+c$. Hence, by (P),

$$t\,Q(x)+s\,Q(y)-Q(w)=\tfrac{1}{2}\Bigl(t\,x\cdot(Mx)+s\,y\cdot(My)-w\cdot(Mw)\Bigr)=\tfrac{1}{2}\,ts\,\bigl((x-y)\cdot\bigl(M(x-y)\bigr)\bigr).$$

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

$$f(w)\le t\,f(x)+s\,f(y)+\tfrac{\lambda}{2}\,ts\,\lVert x-y\rVert^{2}.$$

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

$$g(w)-\bigl(t\,g(x)+s\,g(y)\bigr)=\Bigl(f(w)-t f(x)-s f(y)\Bigr)+\tfrac{1}{2}\Bigl(t\,x\cdot(Mx)+s\,y\cdot(My)-w\cdot(Mw)\Bigr),$$

so by the previous display and (P),

$$g(w)-\bigl(t\,g(x)+s\,g(y)\bigr)\le\tfrac{\lambda}{2}\,ts\,\lVert x-y\rVert^{2}+\tfrac{1}{2}\,ts\,\bigl((x-y)\cdot\bigl(M(x-y)\bigr)\bigr).$$

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

$$g(w)\le t\,g(x)+s\,g(y)+\frac{\lambda+L}{2}\,ts\,\lVert x-y\rVert^{2}.$$

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