Proof of Ishii's Lemma: Test Data and Matrix Bounds at a Maximum of a Quadratically Penalised Difference

Throughout, $n$, $\Omega$, $u$, $v$, $\alpha$, $\hat{x}$, $\hat{y}$, $\delta$ and $p$ are as in the statement. Put $\hat{z}=\iota(\hat{x},\hat{y})$ and

which is open by Twice Differentiability of a Sum in Separated Variables §open.

Conventions. We use without further comment that $\le$ on $\mathbb{R}$ is transitive and compatible with addition, by the ordered field axioms and Total Order on a Set, and the weak compatibility with multiplication: if $0\le b$ and $s\le t$, then $sb\le tb$; this is immediate when $b=0$ or $s=t$, and otherwise follows from claim 10 of Elementary Order Arithmetic in an Ordered Field. Recall from Real Matrices, Symmetric Matrices and the Semidefinite Ordering: Standing Notation §ordering that $P\preceq Q$ means $w\cdot(Pw)\le w\cdot(Qw)$ for every $w$, and that $\preceq$ is transitive.

Step 1 (The doubled data). Let $-v:\Omega\to\mathbb{R}$ be the function whose value at $\eta\in\Omega$ is $-v(\eta)$; it is upper semicontinuous on $\Omega$ by claim 1 of Negation, Restriction, and Separated Differences of Semicontinuous Functions, applied at every point of $\Omega$. Let $w:\Omega^{\ast}\to\mathbb{R}$ be the function determined by

which is well defined because $\iota$ is injective.

By The Doubling Matrix and its Elementary Properties §scaled the matrix $\alpha J$ lies in $\mathcal{S}(2n)$, so claim 1 of Quadratic and Affine Functions of Class $C^2$, Translation, and Quadratic Perturbation of Semiconvexity, applied with $M=\alpha J$, $q=0_{\mathbb{R}^{2n}}$ and $c=0$, shows that the function $Q:\mathbb{R}^{2n}\to\mathbb{R}$ given by $Q(z)=\tfrac{1}{2}\,z\cdot\bigl((\alpha J)z\bigr)$ is of class $C^{2}$ on $\mathbb{R}^{2n}$, with

Moreover, for $\xi,\eta\in\mathbb{R}^{n}$, claim 1 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum, claim 5 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$ and The Doubling Matrix and its Elementary Properties §quadratic-form give

Step 2 (A local maximum of $w-Q$). Let $z\in\Omega^{\ast}$ satisfy $d_{E}(z,\hat{z})<\delta$, and let $(x,y)$ be the unique pair with $z=\iota(x,y)$, so that $x,y\in\Omega$. By claim 4 of Concatenation Identifies a Product of Euclidean Spaces with a Euclidean Space we have $d_{\times}\bigl((x,y),(\hat{x},\hat{y})\bigr)\le d_{E}(z,\hat{z})$, where $d_{\times}$ is the product metric obtained from $d_{E}$ and $d_{E}$, and by claim 2 of The Product Metric is a Metric both $d_{E}(x,\hat{x})$ and $d_{E}(y,\hat{y})$ are at most $d_{\times}\bigl((x,y),(\hat{x},\hat{y})\bigr)$. Hence $d_{E}(x,\hat{x})<\delta$ and $d_{E}(y,\hat{y})<\delta$ by claim 2 of Elementary Order Arithmetic in an Ordered Field, so the hypothesis of the statement applies to the pair $x$, $y$ and, by Step 1,

Thus $w-Q$ has a local maximum at $\hat{z}$ relative to $\Omega^{\ast}$.

Step 3 (The theorem on sums). Since $\alpha$ is positive, $\alpha^{-1}$ exists and is positive by claim 7 of Elementary Order Arithmetic in an Ordered Field, and $(\alpha^{-1})^{-1}=\alpha$. We apply Theorem on Sums for Two Upper Semicontinuous Functions with $n_{1}=n_{2}=n$, $\Omega_{1}=\Omega_{2}=\Omega$, $u_{1}=u$, $u_{2}=-v$, $V=\mathbb{R}^{2n}$, the test function $Q$, the point $\hat{z}$ of Step 2 and $\varepsilon=\alpha^{-1}$. Here $A=D^{2}Q(\hat{z})=\alpha J$, and the unique pair $(p_{1},p_{2})$ with $\iota(p_{1},p_{2})=DQ(\hat{z})$ is $(p,-p)$: indeed, by claim 1 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum, The Doubling Matrix and its Elementary Properties §action and claim 2 of Concatenation Identifies a Product of Euclidean Spaces with a Euclidean Space,

and $\alpha(\hat{y}-\hat{x})=\alpha\bigl((-1)(\hat{x}-\hat{y})\bigr)=(-1)\bigl(\alpha(\hat{x}-\hat{y})\bigr)=-p$ in the real vector space $\mathbb{R}^{n}$ of Euclidean Space $\mathbb{R}^n$ is a Real Vector Space.

We obtain $X_{1},X_{2}\in\mathcal{S}(n)$ such that the quadruple $\bigl(\hat{x},u(\hat{x}),p,X_{1}\bigr)$ is approximable by test data from above for $u$ and the quadruple $\bigl(\hat{y},(-v)(\hat{y}),-p,X_{2}\bigr)$ is approximable by test data from above for $-v$, the open set being $\Omega$ in both cases, and such that

Put $X=X_{1}$ and $Y=-X_{2}$, both elements of $\mathcal{S}(n)$ by Second-Order Equations on Euclidean Open Sets §matrices. Since the scalar multiple of a matrix is formed entrywise and two real matrices of the same size are equal exactly when all their entries agree, as recorded in Real Matrices, Symmetric Matrices and the Semidefinite Ordering: Standing Notation §matrices, we have $-Y=-(-X_{2})=X_{2}$ and hence $X\oplus(-Y)=X_{1}\oplus X_{2}$.

Step 4 (Claim 1). The first assertion of claim 1 is the statement about $X_{1}=X$ obtained in Step 3. For the second, apply claim 2 of Approximability by Test Data Under Negation with $v$ in place of $u$, the point $\hat{y}$, the vector $p$ and the matrix $Y$: it asserts that $\bigl(\hat{y},v(\hat{y}),p,Y\bigr)$ is approximable by test data from below for $v$ if and only if $\bigl(\hat{y},(-v)(\hat{y}),-p,-Y\bigr)$ is approximable by test data from above for $-v$. As $-Y=X_{2}$, the latter is exactly what Step 3 provides, so the former holds.

Step 5 (Claim 2). By The Doubling Matrix and its Elementary Properties §scaled we have $\alpha J+\alpha^{-1}(\alpha J)^{2}=3\alpha J$, so the upper bound of Step 3 is the upper bound of claim 2.

For the lower bound, The Doubling Matrix and its Elementary Properties §scaled gives $\lVert\alpha J\rVert\le 2\alpha$, whence $\alpha+\lVert\alpha J\rVert\le\alpha+2\alpha=3\alpha$. Let $z\in\mathbb{R}^{2n}$. By Vector, Entry and Comparison Bounds for the Norm of a Symmetric Real Matrix §identity,

Since $\lVert z\rVert^{2}$ is nonnegative by claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ and claim 2 of Monotonicity of Squaring on the Nonnegative Elements of an Ordered Field, multiplying $\alpha+\lVert\alpha J\rVert\le 3\alpha$ by $\lVert z\rVert^{2}$ and reversing signs with claim 4 of Elementary Order Arithmetic in an Ordered Field gives $-3\alpha\lVert z\rVert^{2}\le-\bigl(\alpha+\lVert\alpha J\rVert\bigr)\lVert z\rVert^{2}$. Hence $-3\alpha I_{2n}\preceq-\bigl(\alpha+\lVert\alpha J\rVert\bigr)I_{2n}$, and claim 2 follows from Step 3 by transitivity of $\preceq$.

Step 6 (Claim 3). Let $\xi,\eta\in\mathbb{R}^{n}$ and put $z=\iota(\xi,\eta)$. By Block Diagonal Symmetric Matrices and the Blocks of a Symmetric Matrix §quadratic-form, claim 1 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum and claim 5 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$,

By Vector, Entry and Comparison Bounds for the Norm of a Symmetric Real Matrix §identity and claim 3 of Concatenation Identifies a Product of Euclidean Spaces with a Euclidean Space,

and by claim 1 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum, claim 5 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$ and The Doubling Matrix and its Elementary Properties §quadratic-form, $z\cdot\bigl((3\alpha J)z\bigr)=3\alpha\lVert\xi-\eta\rVert^{2}$. Claim 3 is therefore claim 2 read through the description of $\preceq$ in Real Matrices, Symmetric Matrices and the Semidefinite Ordering: Standing Notation §ordering, every point of $\mathbb{R}^{2n}$ being of the form $\iota(\xi,\eta)$.

Step 7 (Claim 4). Immediate from claim 2 and The Doubling Matrix and its Elementary Properties §diagonal-comparison, applied with $c=3\alpha$.

Step 8 (Claim 5). By claim 2 and The Doubling Matrix and its Elementary Properties §scaled, $X\oplus(-Y)\preceq 3\alpha J\preceq 6\alpha I_{2n}$. Also $-6\alpha I_{2n}\preceq-3\alpha I_{2n}$: for $z\in\mathbb{R}^{2n}$ the two quadratic forms are $-6\alpha\lVert z\rVert^{2}$ and $-3\alpha\lVert z\rVert^{2}$ by Vector, Entry and Comparison Bounds for the Norm of a Symmetric Real Matrix §identity, and $3\alpha\le 3\alpha+3\alpha=6\alpha$ because $0\le 3\alpha$, so multiplying by the nonnegative number $\lVert z\rVert^{2}$ and reversing signs with claim 4 of Elementary Order Arithmetic in an Ordered Field gives the asserted inequality of quadratic forms. By transitivity, $-6\alpha I_{2n}\preceq X\oplus(-Y)\preceq 6\alpha I_{2n}$, so claim 3 of Properties of the Norm of a Symmetric Real Matrix, applicable since $0\le 6\alpha$, gives $\lVert X\oplus(-Y)\rVert\le 6\alpha$.

By Block Diagonal Symmetric Matrices and the Blocks of a Symmetric Matrix §norm, $\lVert X\oplus(-Y)\rVert$ is the larger of $\lVert X\rVert$ and $\lVert-Y\rVert$, and $\lVert-Y\rVert=|-1|\,\lVert Y\rVert=\lVert Y\rVert$ by claim 5 of Properties of the Norm of a Symmetric Real Matrix, since $|-1|=1$ by claims 2 and 1 of Properties of the Absolute Value in an Ordered Field together with claims 6 and 4 of Elementary Order Arithmetic in an Ordered Field. Hence $\lVert X\rVert\le 6\alpha$ and $\lVert Y\rVert\le 6\alpha$.