Proof of The Theorem on Sums for a Global Quadratic Bound, in Two Groups of Variables

Throughout, the notation is that of the statement. Put

$$\lambda=\varepsilon^{-1}+\lVert A\rVert ,$$

which is positive, since $\varepsilon^{-1}$ is positive and $0\le\lVert A\rVert$ by claim 1 of Properties of the Norm of a Symmetric Real Matrix. Recall $B=A+\varepsilon A^{2}\in\mathcal{S}(N)$.

Let $w:\mathbb{R}^{N}\to\mathbb{R}$ be the function determined by

$$w\bigl(\iota(\xi,\eta)\bigr)=u_{1}(\xi)+u_{2}(\eta)\qquad(\xi\in\mathbb{R}^{m},\ \eta\in\mathbb{R}^{n}),$$

which is well defined and defined at every point of $\mathbb{R}^{N}$ because $\iota$ is a bijection. By Concatenation and the Sup-Convolution of a Sum in Separated Variables (ii), applied with the parameter $\lambda$, the number $C_{1}+C_{2}$ is an upper bound for the set of values of $w$ and the sup-convolutions $u_{1}^{\lambda}$, $u_{2}^{\lambda}$ and $w^{\lambda}$ are defined; and by Concatenation and the Sup-Convolution of a Sum in Separated Variables (iii),

$$w^{\lambda}\bigl(\iota(\xi,\eta)\bigr)=u_{1}^{\lambda}(\xi)+u_{2}^{\lambda}(\eta)\qquad(\xi\in\mathbb{R}^{m},\ \eta\in\mathbb{R}^{n}).$$

Step 1 (a global quadratic bound for the sup-convolution). Every $x\in\mathbb{R}^{N}$ is of the form $\iota(\xi,\eta)$, so the hypothesis of the theorem says exactly that

$$w(x)\le\tfrac{1}{2}\,x\cdot(Ax)\qquad\text{for every }x\in\mathbb{R}^{N}.$$

By A Weighted Young Inequality and the Splitting of a Quadratic Form (iii), applied in dimension $N$ with the matrix $A$ and the given positive $\varepsilon$, we have for all $x,z\in\mathbb{R}^{N}$

$$x\cdot(Ax)\le z\cdot(Bz)+\lambda\,\lVert x-z\rVert^{2}.$$

Multiplying by the positive number $2^{-1}$ preserves this inequality: if the two sides are equal so are their products with $2^{-1}$, and otherwise the inequality is strict and claim 10 of Elementary Order Arithmetic in an Ordered Field applies. Combining with the previous display,

$$w(x)-\frac{\lambda}{2}\,\lVert x-z\rVert^{2}\le\tfrac{1}{2}\,z\cdot(Bz)\qquad\text{for all }x,z\in\mathbb{R}^{N}.$$

For fixed $z$ this says that $\tfrac{1}{2}\,z\cdot(Bz)$ is an upper bound for the set $S_{\lambda,w}(z)$ of Sup-Convolution of a Function on $\mathbb{R}^M$, whose least upper bound is $w^{\lambda}(z)$. Hence

$$w^{\lambda}(z)\le\tfrac{1}{2}\,z\cdot(Bz)\qquad\text{for every }z\in\mathbb{R}^{N}.$$

Step 2 (the values at the origins). By Concatenation and the Sup-Convolution of a Sum in Separated Variables (i) we have $\iota\bigl(0_{\mathbb{R}^{m}},0_{\mathbb{R}^{n}}\bigr)=0_{\mathbb{R}^{N}}$, so

$$w\bigl(0_{\mathbb{R}^{N}}\bigr)=u_{1}\bigl(0_{\mathbb{R}^{m}}\bigr)+u_{2}\bigl(0_{\mathbb{R}^{n}}\bigr)=0 .$$

By claim 1 of Domination, Monotonicity and Semiconvexity of the Sup-Convolution we have $w(0_{\mathbb{R}^{N}})\le w^{\lambda}(0_{\mathbb{R}^{N}})$, that is $0\le w^{\lambda}(0_{\mathbb{R}^{N}})$. On the other hand Step 1 with $z=0_{\mathbb{R}^{N}}$, together with $B\,0_{\mathbb{R}^{N}}=0_{\mathbb{R}^{N}}$ from claim 1 of Linearity, Compatibility with the Matrix Product, and a Norm Bound for the Matrix-Vector Product and $0_{\mathbb{R}^{N}}\cdot 0_{\mathbb{R}^{N}}=0$, gives $w^{\lambda}(0_{\mathbb{R}^{N}})\le0$. Hence $w^{\lambda}(0_{\mathbb{R}^{N}})=0$.

Applying claim 1 of Domination, Monotonicity and Semiconvexity of the Sup-Convolution to $u_{1}$ and to $u_{2}$ gives $0=u_{1}(0_{\mathbb{R}^{m}})\le u_{1}^{\lambda}(0_{\mathbb{R}^{m}})$ and $0\le u_{2}^{\lambda}(0_{\mathbb{R}^{n}})$, while the separation identity at $\xi=0_{\mathbb{R}^{m}}$, $\eta=0_{\mathbb{R}^{n}}$ gives

$$u_{1}^{\lambda}\bigl(0_{\mathbb{R}^{m}}\bigr)+u_{2}^{\lambda}\bigl(0_{\mathbb{R}^{n}}\bigr)=w^{\lambda}\bigl(0_{\mathbb{R}^{N}}\bigr)=0 .$$

Suppose $u_{1}^{\lambda}(0_{\mathbb{R}^{m}})\ne0$. Then $0<u_{1}^{\lambda}(0_{\mathbb{R}^{m}})$, the strict order of an ordered field being defined by $a\le b$ together with $a\ne b$. By the last display, $u_{2}^{\lambda}(0_{\mathbb{R}^{n}})$ is the additive inverse of $u_{1}^{\lambda}(0_{\mathbb{R}^{m}})$, so $u_{2}^{\lambda}(0_{\mathbb{R}^{n}})<0$ by claim 4 of Elementary Order Arithmetic in an Ordered Field applied to $0<u_{1}^{\lambda}(0_{\mathbb{R}^{m}})$, contradicting $0\le u_{2}^{\lambda}(0_{\mathbb{R}^{n}})$. Hence $u_{1}^{\lambda}(0_{\mathbb{R}^{m}})=0$, and then $u_{2}^{\lambda}(0_{\mathbb{R}^{n}})=0$ as well.

Step 3 (the semiconvex quadratic-maximum lemma). By claim 3 of Domination, Monotonicity and Semiconvexity of the Sup-Convolution the function $w^{\lambda}$ is semiconvex on $\mathbb{R}^{N}$ with constant $\lambda$, and by Steps 1 and 2,

$$w^{\lambda}(z)-\tfrac{1}{2}\,z\cdot(Bz)\le 0=w^{\lambda}\bigl(0_{\mathbb{R}^{N}}\bigr)\qquad\text{for every }z\in\mathbb{R}^{N}.$$

Thus Second-Order Test Data at a Global Quadratic Maximum of a Semiconvex Function (i) applies in dimension $N$ with the constant $\lambda$, the function $w^{\lambda}$ and the matrix $B$: there are $Z\in\mathcal{S}(N)$ and a sequence $(z_{k})_{k\in\mathbb{N}}$ in $\mathbb{R}^{N}$ such that $w^{\lambda}$ is twice differentiable at every $z_{k}$, the sequences $(z_{k})$ and $\bigl(Dw^{\lambda}(z_{k})\bigr)$ converge to $0_{\mathbb{R}^{N}}$, the sequence $\bigl(D^{2}w^{\lambda}(z_{k})\bigr)$ converges to $Z$ in $\mathcal{S}(N)$, and

$$-\lambda I_{N}\preceq Z\preceq B .$$

Write $Z_{k}=D^{2}w^{\lambda}(z_{k})$.

Step 4 (splitting the data). Since $\iota$ is a bijection, for each $k$ there is a unique pair $(\xi_{k},\eta_{k})\in\mathbb{R}^{m}\times\mathbb{R}^{n}$ with $z_{k}=\iota(\xi_{k},\eta_{k})$, and there is a unique pair $(p^{1}_{k},p^{2}_{k})$ with $\iota(p^{1}_{k},p^{2}_{k})=Dw^{\lambda}(z_{k})$. Because $\iota$ is surjective, the set $\{\iota(\xi,\eta):\xi\in\mathbb{R}^{m},\ \eta\in\mathbb{R}^{n}\}$ is all of $\mathbb{R}^{N}$, and by the separation identity displayed at the start of this proof the function determined on it by $u_{1}^{\lambda}$ and $u_{2}^{\lambda}$ in the sense of Twice Differentiability of a Sum in Separated Variables is exactly $w^{\lambda}$. Applying Twice Differentiability of a Sum in Separated Variables (iii) with $U_{1}=\mathbb{R}^{m}$, $U_{2}=\mathbb{R}^{n}$, $v_{1}=u_{1}^{\lambda}$, $v_{2}=u_{2}^{\lambda}$ and the point $z_{k}$, we obtain: $u_{1}^{\lambda}$ is twice differentiable at $\xi_{k}$ with first-order coefficient $p^{1}_{k}$ and Hessian $Z_{k}^{11}$; $u_{2}^{\lambda}$ is twice differentiable at $\eta_{k}$ with first-order coefficient $p^{2}_{k}$ and Hessian $Z_{k}^{22}$; every entry of $Z_{k}^{12}$ equals $0$; and $Z_{k}=Z_{k}^{11}\oplus Z_{k}^{22}$. Here the blocks are those of Block Diagonal Symmetric Matrices and the Blocks of a Symmetric Matrix (v).

Step 5 (passing to the limit). By Concatenation and the Sup-Convolution of a Sum in Separated Variables (i), from $\bigl(\iota(\xi_{k},\eta_{k})\bigr)=(z_{k})$ converging to $0_{\mathbb{R}^{N}}=\iota\bigl(0_{\mathbb{R}^{m}},0_{\mathbb{R}^{n}}\bigr)$ we get that $(\xi_{k})$ converges to $0_{\mathbb{R}^{m}}$ and $(\eta_{k})$ converges to $0_{\mathbb{R}^{n}}$; likewise, from $\bigl(\iota(p^{1}_{k},p^{2}_{k})\bigr)=\bigl(Dw^{\lambda}(z_{k})\bigr)$ converging to $0_{\mathbb{R}^{N}}$ we get that $(p^{1}_{k})$ converges to $0_{\mathbb{R}^{m}}$ and $(p^{2}_{k})$ converges to $0_{\mathbb{R}^{n}}$.

Next we show that every entry of $Z^{12}$ equals $0$. Let $i\in[m]$ and $j\in[n]$. By Block Diagonal Symmetric Matrices and the Blocks of a Symmetric Matrix (v) we have $(Z_{k}^{12})_{ij}=(Z_{k})_{i,m+j}=0$ and $(Z^{12})_{ij}=Z_{i,m+j}$. The matrix $Z_{k}-Z$ lies in $\mathcal{S}(N)$ and its entry in row $i$ and column $m+j$ is $(Z_{k})_{i,m+j}-Z_{i,m+j}=-Z_{i,m+j}$, so Vector, Entry and Comparison Bounds for the Norm of a Symmetric Real Matrix (iv) gives

$$\bigl|Z_{i,m+j}\bigr|\le\lVert Z_{k}-Z\rVert=d_{\mathcal{S}(N)}(Z_{k},Z)\qquad\text{for every }k\in\mathbb{N},$$

using claim 2 of Properties of the Absolute Value in an Ordered Field for the sign. If $Z_{i,m+j}\ne0$ then $\bigl|Z_{i,m+j}\bigr|$ is positive by claim 1 of Properties of the Absolute Value in an Ordered Field together with claim 6 there applied with $c=0$; but $(Z_{k})$ converges to $Z$, so there is $k$ with $d_{\mathcal{S}(N)}(Z_{k},Z)<\bigl|Z_{i,m+j}\bigr|$, contradicting the display. Hence $Z_{i,m+j}=0$, and by Block Diagonal Symmetric Matrices and the Blocks of a Symmetric Matrix (v) we conclude $Z=Z^{11}\oplus Z^{22}$.

Put $X_{1}=Z^{11}\in\mathcal{S}(m)$ and $X_{2}=Z^{22}\in\mathcal{S}(n)$, so that $Z=X_{1}\oplus X_{2}$. Since $Z_{k}=Z_{k}^{11}\oplus Z_{k}^{22}$ converges to $X_{1}\oplus X_{2}$ in $\mathcal{S}(N)$, Block Diagonal Symmetric Matrices and the Blocks of a Symmetric Matrix (iii) gives that $(Z_{k}^{11})$ converges to $X_{1}$ in $\mathcal{S}(m)$ and $(Z_{k}^{22})$ converges to $X_{2}$ in $\mathcal{S}(n)$.

Finally, $\bigl(u_{1}^{\lambda}(\xi_{k})\bigr)$ converges to $u_{1}^{\lambda}(0_{\mathbb{R}^{m}})$. Indeed $\mathbb{R}^{m}$ is open and convex and $u_{1}^{\lambda}$ is semiconvex on it with the nonnegative constant $\lambda$, by claim 3 of Domination, Monotonicity and Semiconvexity of the Sup-Convolution, so claim 2 of Local Lipschitz Bound and Continuity for a Semiconvex Function on an Open Convex Set, applied with $S=U=\mathbb{R}^{m}$ at the point $0_{\mathbb{R}^{m}}$, provides for each positive $\varepsilon'\in\mathbb{R}$ a positive $\delta\in\mathbb{R}$ such that $\lVert y-0_{\mathbb{R}^{m}}\rVert<\delta$ implies $\bigl|u_{1}^{\lambda}(y)-u_{1}^{\lambda}(0_{\mathbb{R}^{m}})\bigr|<\varepsilon'$; choosing $K$ with $d_{E}(\xi_{k},0_{\mathbb{R}^{m}})<\delta$ for $k\ge K$ gives the assertion. The same argument gives that $\bigl(u_{2}^{\lambda}(\eta_{k})\bigr)$ converges to $u_{2}^{\lambda}(0_{\mathbb{R}^{n}})$.

Step 6 (test data for the sup-convolutions). For each $k$ the function $u_{1}^{\lambda}$ is twice differentiable at $\xi_{k}$ with first-order coefficient $p^{1}_{k}$ and Hessian $Z_{k}^{11}$, so by Quadratic Test Functions, Limits, Translation and Locality for Approximability by Test Data (ii), applied with $U=\mathbb{R}^{m}$ and $u=u_{1}^{\lambda}$, the quadruple $\bigl(\xi_{k},u_{1}^{\lambda}(\xi_{k}),p^{1}_{k},Z_{k}^{11}\bigr)$ is approximable by test data from above for $u_{1}^{\lambda}$. By Step 5 the sequences $(\xi_{k})$, $\bigl(u_{1}^{\lambda}(\xi_{k})\bigr)$, $(p^{1}_{k})$ and $(Z_{k}^{11})$ converge to $0_{\mathbb{R}^{m}}$, $u_{1}^{\lambda}(0_{\mathbb{R}^{m}})$, $0_{\mathbb{R}^{m}}$ and $X_{1}$ respectively, so Quadratic Test Functions, Limits, Translation and Locality for Approximability by Test Data (iii) shows that

$$\bigl(0_{\mathbb{R}^{m}},\,u_{1}^{\lambda}(0_{\mathbb{R}^{m}}),\,0_{\mathbb{R}^{m}},\,X_{1}\bigr)$$

is approximable by test data from above for $u_{1}^{\lambda}$. The same argument gives that $\bigl(0_{\mathbb{R}^{n}},u_{2}^{\lambda}(0_{\mathbb{R}^{n}}),0_{\mathbb{R}^{n}},X_{2}\bigr)$ is approximable by test data from above for $u_{2}^{\lambda}$.

Step 7 (transfer to $u_{1}$ and $u_{2}$; proof of claim 1). The hypotheses of Transfer of Approximating Test Data from the Sup-Convolution to the Original Function hold with $M=m$, with $v=u_{1}$, which is upper semicontinuous on $\mathbb{R}^{m}$ and has the upper bound $C_{1}$, with the parameter $\lambda$, whose sup-convolution is $u_{1}^{\lambda}$, and with $\eta_{0}=0_{\mathbb{R}^{m}}$, $q_{0}=0_{\mathbb{R}^{m}}$ and $Y=X_{1}$, by Step 6. Here

$$z_{0}=0_{\mathbb{R}^{m}}+\lambda^{-1}\,0_{\mathbb{R}^{m}}=0_{\mathbb{R}^{m}}$$

by the vector space identities of Euclidean Space $\mathbb{R}^n$ is a Real Vector Space, so Transfer of Approximating Test Data from the Sup-Convolution to the Original Function (ii) gives that

$$\bigl(0_{\mathbb{R}^{m}},\,u_{1}(0_{\mathbb{R}^{m}}),\,0_{\mathbb{R}^{m}},\,X_{1}\bigr)$$

is approximable by test data from above for $u_{1}$. The same argument with $M=n$, $v=u_{2}$, $C_{2}$ and $Y=X_{2}$ gives that $\bigl(0_{\mathbb{R}^{n}},u_{2}(0_{\mathbb{R}^{n}}),0_{\mathbb{R}^{n}},X_{2}\bigr)$ is approximable by test data from above for $u_{2}$. This is claim 1.

Step 8 (proof of claim 2). By Steps 3 and 5, $X_{1}\oplus X_{2}=Z$ and

$$-\bigl(\varepsilon^{-1}+\lVert A\rVert\bigr)I_{N}=-\lambda I_{N}\preceq Z\preceq B=A+\varepsilon A^{2},$$

which is claim 2.