Proof of Hessian Lower Bound for a $C^2$ Test Function Touching a Semiconvex Function from Above

Throughout, $\partial_i\varphi$ is the partial derivative of $\varphi$ with respect to the $i$-th coordinate and $\partial_i\partial_j\varphi$ is the iterated partial derivative of clause 4 of C^k Maps on a Euclidean Open Set, defined on all of $U$ by clause 2 there. Sums are finite sums of real numbers, $t^{2}$ abbreviates $t\cdot t$, and $|t|$ is the absolute value. Write $2=1+1$ and $4=2\cdot 2$; then $0<2$ and $0<4$ by claims 8 and 5 of Elementary Order Arithmetic in an Ordered Field, so $2^{-1}$ and $4^{-1}$ exist, and we abbreviate $a\cdot 2^{-1}$ by $\tfrac{a}{2}$.

Convention on absolute values. If $a\in\mathbb{R}$ satisfies $0\le a$ then $|a|=a$. Indeed $|a|$ equals $a$ or $-a$ by claim 1 of Properties of the Absolute Value in an Ordered Field; in the second case $0\le|a|=-a$ gives $a\le 0$ by claim 4 of Elementary Order Arithmetic in an Ordered Field, so $a=0$ by antisymmetry of the total order and $|a|=-0=0=a$. In particular $|2|=2$, and $|-1|=|1|=1$ by claim 2 of Properties of the Absolute Value in an Ordered Field together with claim 6 of Elementary Order Arithmetic in an Ordered Field.

Symmetric points. For $h\in\mathbb{R}^{n}$ we have $x_{0}-h=x_{0}+(-1)h$ by claims 3 and 2 of Euclidean Space $\mathbb{R}^n$ is a Real Vector Space, and therefore, by 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,

$$\lVert -h\rVert=\lVert(-1)h\rVert=|-1|\,\lVert h\rVert=\lVert h\rVert .$$

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, $d(x_{0},x_{0}+h)=\lVert h\rVert$ and $d(x_{0},x_{0}-h)=\lVert -h\rVert=\lVert h\rVert$.

Step 1: a doubling inequality for $\varphi$.

Because the function $x\mapsto w(x)-\varphi(x)$ has a local maximum at $x_{0}$ relative to $U$, there is $\delta_{1}\in\mathbb{R}$ with $0<\delta_{1}$ such that every $y\in U$ with $d(x_{0},y)<\delta_{1}$ satisfies $w(y)-\varphi(y)\le w(x_{0})-\varphi(x_{0})$. Because $U$ is open in $(\mathbb{R}^{n},d)$ and $x_{0}\in U$, Open Subset of a Metric Space supplies $\delta_{2}\in\mathbb{R}$ with $0<\delta_{2}$ such that the open ball of centre $x_{0}$ and radius $\delta_{2}$, that is the set of $y\in\mathbb{R}^{n}$ with $d(x_{0},y)<\delta_{2}$, is contained in $U$. By claim 9 of Elementary Order Arithmetic in an Ordered Field there is $r\in\mathbb{R}$ with $r\le\delta_{1}$, $r\le\delta_{2}$, and $r$ equal to $\delta_{1}$ or to $\delta_{2}$; in either case $0<r$.

We claim that every $h\in\mathbb{R}^{n}$ with $\lVert h\rVert<r$ satisfies $x_{0}+h\in U$, $x_{0}-h\in U$ and

$$(-\mu)\lVert h\rVert^{2}\;\le\;\varphi(x_{0}+h)+\varphi(x_{0}-h)-2\varphi(x_{0}).$$

We call this the doubling inequality.

To prove it, fix such an $h$. By the computation of the distances above and mixed transitivity (claim 2 of Elementary Order Arithmetic in an Ordered Field) we have $d(x_{0},x_{0}\pm h)<\delta_{2}$, so both points lie in $U$, and $d(x_{0},x_{0}\pm h)<\delta_{1}$, so the local maximum property gives

$$w(x_{0}+h)-\varphi(x_{0}+h)\le w(x_{0})-\varphi(x_{0}),\qquad w(x_{0}-h)-\varphi(x_{0}-h)\le w(x_{0})-\varphi(x_{0}).$$

Adding these two inequalities — each is equivalent by claim 3 of Elementary Arithmetic in an Ordered Field to the statement that a certain difference is nonnegative, the two differences have nonnegative sum by claim 2 there, and claim 3 converts back — yields

$$w(x_{0}+h)+w(x_{0}-h)\;\le\;2w(x_{0})-2\varphi(x_{0})+\varphi(x_{0}+h)+\varphi(x_{0}-h).$$

Next, $x_{0}+h$ and $x_{0}-h$ lie in $U$, hence in $\Omega$. Computing coordinatewise with Euclidean Space $\mathbb{R}^n$: n-Tuples of Real Numbers with Their Componentwise Operations, Sum of Points of $\mathbb{R}^n$ and Scalar Multiple of a Point of $\mathbb{R}^n$,

$$\tfrac{1}{2}(x_{0}+h)+\bigl(1-\tfrac{1}{2}\bigr)(x_{0}-h)=x_{0},\qquad (x_{0}+h)-(x_{0}-h)=2h,$$

the first because $1-\tfrac12=\tfrac12$ and $\tfrac12(x_{0i}+h_i)+\tfrac12(x_{0i}-h_i)=x_{0i}$, the second because $(x_{0i}+h_i)-(x_{0i}-h_i)=h_i+h_i=2h_i$. Moreover $\lVert 2h\rVert=|2|\,\lVert h\rVert=2\lVert h\rVert$ by 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, so $\lVert 2h\rVert^{2}=4\lVert h\rVert^{2}$. Since $0\le\tfrac12$ and $\tfrac12\le1$ by claim 8 of Elementary Order Arithmetic in an Ordered Field applied with $\varepsilon=1$, Quadratic Increment Characterisation of Semiconvexity, applied to $w$ on $\Omega$ with $x=x_{0}+h$, $y=x_{0}-h$ and $t=\tfrac12$, gives

$$w(x_{0})\;\le\;\tfrac{1}{2}w(x_{0}+h)+\tfrac{1}{2}w(x_{0}-h)+\frac{\mu}{2}\cdot\tfrac{1}{2}\cdot\tfrac{1}{2}\cdot 4\lVert h\rVert^{2}.$$

Here $\tfrac12\cdot\tfrac12\cdot4=2^{-1}2^{-1}(2\cdot2)=1$, so the last term is $\tfrac{\mu}{2}\lVert h\rVert^{2}$. Multiplying the whole inequality by $2$, which is legitimate by claim 5 of Elementary Arithmetic in an Ordered Field because $0\le 2$, and using $2\cdot 2^{-1}=1$, we obtain

$$2w(x_{0})\;\le\;w(x_{0}+h)+w(x_{0}-h)+\mu\lVert h\rVert^{2}.$$

Adding $\mu\lVert h\rVert^{2}$ to both sides of the previous displayed inequality for $w(x_{0}+h)+w(x_{0}-h)$ (again claim 3 of Elementary Arithmetic in an Ordered Field, the two differences being equal) and chaining the two inequalities gives

$$2w(x_{0})\;\le\;2w(x_{0})-2\varphi(x_{0})+\varphi(x_{0}+h)+\varphi(x_{0}-h)+\mu\lVert h\rVert^{2}.$$

Cancelling the common summand $2w(x_{0})$, by two applications of claim 3 of Elementary Arithmetic in an Ordered Field, and then using claim 3 once more together with the identity $(-\mu)\lVert h\rVert^{2}=-\bigl(\mu\lVert h\rVert^{2}\bigr)$ of claim 2 of Zero Products and Elementary Identities in a Field, we arrive at the doubling inequality. This proves the claim.

Step 2: reduction to a quadratic form.

Let $z=(z_{1},\dots,z_{n})\in\mathbb{R}^{n}$. By The Positive Semidefinite Ordering on Symmetric Matrices it suffices to prove that

$$z\cdot\bigl((-\mu)I_{n}z\bigr)\;\le\;z\cdot\bigl(D^{2}\varphi(x_{0})z\bigr).$$

By Identity Matrix and Scalar Multiple of a Real Matrix the entry of $(-\mu)I_{n}$ in row $i$ and column $j$ is $(-\mu)$ when $i=j$ and is $(-\mu)\cdot 0=0$ otherwise, by claim 1 of Zero Products and Elementary Identities in a Field. Hence by Matrix-Vector Product and claim 7 of Properties of Finite Sums, $\bigl((-\mu)I_{n}z\bigr)_{i}=(-\mu)z_{i}$, and therefore, by the definition of the dot product, claim 3 of Properties of Finite Sums and claim 1 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square,

$$z\cdot\bigl((-\mu)I_{n}z\bigr)=\sum_{i=1}^{n}z_{i}\bigl((-\mu)z_{i}\bigr)=(-\mu)\sum_{i=1}^{n}z_{i}^{2}=(-\mu)\lVert z\rVert^{2}.$$

By Hessian Matrix of a C^2 Function and Matrix-Vector Product, $\bigl(D^{2}\varphi(x_{0})z\bigr)_{i}=\sum_{j=1}^{n}\partial_i\partial_j\varphi(x_{0})z_{j}$, so, writing $Q$ for the number $z\cdot\bigl(D^{2}\varphi(x_{0})z\bigr)$ and using claim 3 of Properties of Finite Sums on the inner sum,

$$Q=\sum_{i=1}^{n}\sum_{j=1}^{n}\partial_i\partial_j\varphi(x_{0})\,z_{i}z_{j} =\sum_{i=1}^{n}\sum_{j=1}^{n}\partial_j\partial_i\varphi(x_{0})\,z_{i}z_{j},$$

the second equality because $\partial_i\partial_j\varphi(x_{0})=\partial_j\partial_i\varphi(x_{0})$ for all $i,j$ by claim 1 of Equality of Mixed Second Partial Derivatives and Symmetry of the Hessian. Write also $L=\sum_{i=1}^{n}\partial_i\varphi(x_{0})z_{i}$. We must show $(-\mu)\lVert z\rVert^{2}\le Q$.

Suppose first that $z$ is the origin of $\mathbb{R}^{n}$. Then $\lVert z\rVert=0$ by claim 3 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square, so $(-\mu)\lVert z\rVert^{2}=0$ by claim 1 of Zero Products and Elementary Identities in a Field; and every $z_{i}=0$, so each summand of the sum defining $Q$ equals $0\cdot a_{i}$ with $a_{i}=\bigl(D^{2}\varphi(x_{0})z\bigr)_{i}$, whence $Q=0\cdot\sum_{i=1}^{n}a_{i}=0$ by claims 3 and 1 of Properties of Finite Sums and Zero Products and Elementary Identities in a Field respectively. The required inequality reads $0\le 0$ and holds.

Step 3: the case $z\ne 0$, by Taylor expansion.

Suppose now that $z$ is not the origin. By claims 3 and 1 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square we have $\lVert z\rVert\ne 0$ and $0\le\lVert z\rVert$, hence $0<\lVert z\rVert$ and, by claim 5 of Elementary Order Arithmetic in an Ordered Field, $0<\lVert z\rVert^{2}$; by claim 7 there, $\bigl(\lVert z\rVert^{2}\bigr)^{-1}$ exists and is positive.

Assume, seeking a contradiction, that the desired inequality fails. Since the order on $\mathbb{R}$ is total, this means $Q<(-\mu)\lVert z\rVert^{2}$. Put

$$c=(-\mu)\lVert z\rVert^{2}-Q,\qquad \varepsilon=\Bigl(\tfrac{1}{2}\cdot\tfrac{c}{2}\Bigr)\cdot\bigl(\lVert z\rVert^{2}\bigr)^{-1}.$$

By claim 1 of Elementary Order Arithmetic in an Ordered Field we have $0<c$, hence $0<\tfrac{c}{2}$ and $0<\tfrac12\cdot\tfrac{c}{2}$ by claim 8 there, and so $0<\varepsilon$ by claim 5 there.

Apply Second-Order Taylor Expansion with Peano Remainder to $\varphi$ at the point $x_{0}$ with this $\varepsilon$: there is $\delta\in\mathbb{R}$ with $0<\delta$ such that every $k\in\mathbb{R}^{n}$ with $\lVert k\rVert<\delta$ satisfies $x_{0}+k\in U$ and

$$\Bigl|\,\varphi(x_{0}+k)-\varphi(x_{0})-\sum_{i=1}^{n}\partial_i\varphi(x_{0})k_{i}-\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\partial_j\partial_i\varphi(x_{0})k_{i}k_{j}\,\Bigr|\;\le\;\varepsilon\lVert k\rVert^{2}.$$

By claim 9 of Elementary Order Arithmetic in an Ordered Field choose $\rho\in\mathbb{R}$ with $\rho\le r$, $\rho\le\delta$ and $\rho$ equal to $r$ or to $\delta$, so that $0<\rho$. Put

$$s=\tfrac{\rho}{2}\cdot\lVert z\rVert^{-1},\qquad h=s\,z .$$

Then $0<s$ by claims 8, 7 and 5 of Elementary Order Arithmetic in an Ordered Field, so $|s|=s$ by the convention above, and by 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 together with $\lVert z\rVert^{-1}\lVert z\rVert=1$,

$$\lVert h\rVert=|s|\,\lVert z\rVert=\tfrac{\rho}{2}<\rho ,$$

the last step by claim 8 of Elementary Order Arithmetic in an Ordered Field. Consequently $\lVert h\rVert<r$ and $\lVert h\rVert<\delta$ by mixed transitivity, and likewise $\lVert -h\rVert=\lVert h\rVert<\delta$.

By Scalar Multiple of a Point of $\mathbb{R}^n$ we have $h_{i}=s\,z_{i}$, and $-h=(-s)z$ with $(-h)_{i}=(-s)z_{i}$, by claim 2 of Zero Products and Elementary Identities in a Field applied coordinatewise. Claim 3 of Properties of Finite Sums, applied to the outer and the inner sums, therefore gives

$$\sum_{i=1}^{n}\partial_i\varphi(x_{0})h_{i}=sL,\qquad \sum_{i=1}^{n}\sum_{j=1}^{n}\partial_j\partial_i\varphi(x_{0})h_{i}h_{j}=s^{2}Q,$$

and, since $(-s)z_{i}(-s)z_{j}=s^{2}z_{i}z_{j}$ by claim 2 of Zero Products and Elementary Identities in a Field,

$$\sum_{i=1}^{n}\partial_i\varphi(x_{0})(-h)_{i}=-(sL),\qquad \sum_{i=1}^{n}\sum_{j=1}^{n}\partial_j\partial_i\varphi(x_{0})(-h)_{i}(-h)_{j}=s^{2}Q .$$

Also $\lVert h\rVert^{2}=\bigl(s\lVert z\rVert\bigr)^{2}=s^{2}\lVert z\rVert^{2}$ and $\lVert -h\rVert^{2}=s^{2}\lVert z\rVert^{2}$.

Write

$$A_{+}=\varphi(x_{0}+h)-\varphi(x_{0})-sL-\tfrac{1}{2}s^{2}Q,\qquad A_{-}=\varphi(x_{0}-h)-\varphi(x_{0})+sL-\tfrac{1}{2}s^{2}Q,$$

so that the two applications of the Taylor estimate, at $k=h$ and at $k=-h$, read $|A_{+}|\le\varepsilon s^{2}\lVert z\rVert^{2}$ and $|A_{-}|\le\varepsilon s^{2}\lVert z\rVert^{2}$. By claims 3 and 5 of Properties of the Absolute Value in an Ordered Field and the addition of inequalities as in Step 1,

$$A_{+}+A_{-}\;\le\;|A_{+}+A_{-}|\;\le\;|A_{+}|+|A_{-}|\;\le\;\varepsilon s^{2}\lVert z\rVert^{2}+\varepsilon s^{2}\lVert z\rVert^{2},$$

while $A_{+}+A_{-}=\varphi(x_{0}+h)+\varphi(x_{0}-h)-2\varphi(x_{0})-s^{2}Q$, the terms $\mp sL$ cancelling and $\tfrac12 s^{2}Q+\tfrac12 s^{2}Q=s^{2}Q$ by claim 8 of Elementary Order Arithmetic in an Ordered Field. Hence, by claim 3 of Elementary Arithmetic in an Ordered Field,

$$\varphi(x_{0}+h)+\varphi(x_{0}-h)-2\varphi(x_{0})\;\le\;s^{2}Q+\varepsilon s^{2}\lVert z\rVert^{2}+\varepsilon s^{2}\lVert z\rVert^{2}.$$

Since $\lVert h\rVert<r$, the doubling inequality of Step 1 applies to $h$ and gives

$$(-\mu)s^{2}\lVert z\rVert^{2}=(-\mu)\lVert h\rVert^{2}\;\le\;\varphi(x_{0}+h)+\varphi(x_{0}-h)-2\varphi(x_{0}).$$

Chaining the two displays and multiplying by $\bigl(s^{2}\bigr)^{-1}$, which is positive by claims 5 and 7 of Elementary Order Arithmetic in an Ordered Field and so may be applied by claim 5 of Elementary Arithmetic in an Ordered Field, we obtain

$$(-\mu)\lVert z\rVert^{2}\;\le\;Q+\varepsilon\lVert z\rVert^{2}+\varepsilon\lVert z\rVert^{2}.$$

By the choice of $\varepsilon$ and $\bigl(\lVert z\rVert^{2}\bigr)^{-1}\lVert z\rVert^{2}=1$ we have $\varepsilon\lVert z\rVert^{2}=\tfrac12\cdot\tfrac{c}{2}$, so $\varepsilon\lVert z\rVert^{2}+\varepsilon\lVert z\rVert^{2}=\tfrac{c}{2}$ by claim 8 of Elementary Order Arithmetic in an Ordered Field. Since $c=\tfrac{c}{2}+\tfrac{c}{2}$ and $Q+c=(-\mu)\lVert z\rVert^{2}$, the right-hand side equals $(-\mu)\lVert z\rVert^{2}-\tfrac{c}{2}$, so

$$(-\mu)\lVert z\rVert^{2}\;\le\;(-\mu)\lVert z\rVert^{2}-\tfrac{c}{2}.$$

By claim 3 of Elementary Arithmetic in an Ordered Field this gives $0\le-\tfrac{c}{2}$, hence $\tfrac{c}{2}\le 0$ by claim 4 of Elementary Order Arithmetic in an Ordered Field; combined with $0<\tfrac{c}{2}$ and mixed transitivity this yields $0<0$, which is false.

Therefore $(-\mu)\lVert z\rVert^{2}\le Q$ also when $z$ is not the origin. In both cases $z\cdot\bigl((-\mu)I_{n}z\bigr)\le z\cdot\bigl(D^{2}\varphi(x_{0})z\bigr)$, and since $z\in\mathbb{R}^{n}$ was arbitrary, $(-\mu)I_{n}\preceq D^{2}\varphi(x_{0})$.