Proof of Quadratic Test Functions, Limits, Translation and Locality for Approximability by Test Data

Throughout we use the notation of the statement. We record that $\varepsilon I_{n}\in\mathcal{S}(n)$ with $\lVert\varepsilon I_{n}\rVert=|\varepsilon|$ for every $\varepsilon\in\mathbb{R}$, by Vector, Entry and Comparison Bounds for the Norm of a Symmetric Real Matrix (vi), and that $h\cdot\bigl((\varepsilon I_{n})h\bigr)=\varepsilon\lVert h\rVert^{2}$ for every $h\in\mathbb{R}^{n}$, by claims 1 and 2 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum, claim 5 of The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite 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.

Claim 1. Suppose first that $\bigl(x_{0},u(x_{0}),p,X\bigr)$ is approximable by test data from above for $u$, and let $\varepsilon$ be positive. Put $\varepsilon'=\tfrac{\varepsilon}{2}$, positive by claim 8 of Elementary Order Arithmetic in an Ordered Field. By Quadruple Approximable by Test-Function Data (i) applied with $\varepsilon'$ there are $y\in U$ and $\varphi:U\to\mathbb{R}$ of class $C^{2}$ on $U$ such that $u-\varphi$ has a local maximum at $y$ relative to $U$ and

$$d_{E}(y,x_{0})<\varepsilon',\quad |u(y)-u(x_{0})|<\varepsilon',\quad \lVert D\varphi(y)-p\rVert<\varepsilon',\quad d_{\mathcal{S}(n)}\bigl(D^{2}\varphi(y),X\bigr)<\varepsilon'.$$

Put $r=D\varphi(y)$ and $Y=D^{2}\varphi(y)+\varepsilon'I_{n}$, which lies in $\mathcal{S}(n)$ by claim 1 of The Positive Semidefinite Ordering is a Partial Order Compatible with the Linear Structure. Since $Y-X=\bigl(D^{2}\varphi(y)-X\bigr)+\varepsilon'I_{n}$, claim 5 of Properties of the Norm of a Symmetric Real Matrix gives

$$d_{\mathcal{S}(n)}(Y,X)=\lVert Y-X\rVert\le d_{\mathcal{S}(n)}\bigl(D^{2}\varphi(y),X\bigr)+\varepsilon'<\varepsilon'+\varepsilon'=\varepsilon,$$

and the first three displayed inequalities hold a fortiori with $\varepsilon$ in place of $\varepsilon'$, since $\varepsilon'<\varepsilon$.

By Basic Properties of Twice Differentiability at a Point (ii) the function $\varphi$ is twice differentiable at $y$ with first-order coefficient $D\varphi(y)=r$ and Hessian $D^{2}\varphi(y)$. Applying Twice Differentiability at a Point (i) with the positive parameter $\tfrac{\varepsilon'}{2}$, there is a positive $\delta_{1}$ such that every $h\in\mathbb{R}^{n}$ with $\lVert h\rVert<\delta_{1}$ satisfies $y+h\in U$ and

$$\varphi(y+h)-\varphi(y)-r\cdot h-\tfrac{1}{2}h\cdot\bigl(D^{2}\varphi(y)h\bigr)\le\tfrac{\varepsilon'}{2}\lVert h\rVert^{2},$$

using claim 3 of Properties of the Absolute Value in an Ordered Field. Since $\tfrac{1}{2}h\cdot(Yh)=\tfrac{1}{2}h\cdot\bigl(D^{2}\varphi(y)h\bigr)+\tfrac{\varepsilon'}{2}\lVert h\rVert^{2}$ by claim 1 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum, claim 5 of The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite and the identity recorded at the start, this reads

$$\varphi(y+h)-\varphi(y)\le r\cdot h+\tfrac{1}{2}h\cdot(Yh)\qquad\text{whenever }\lVert h\rVert<\delta_{1}.$$

Let $\delta_{2}$ be positive with the property that every $z\in U$ with $d_{E}(z,y)<\delta_{2}$ satisfies $u(z)-\varphi(z)\le u(y)-\varphi(y)$, as provided by Local Maximum of a Function Relative to a Subset of a Metric Space, and let $\delta$ be the smaller of $\delta_{1}$ and $\delta_{2}$. For $z\in U$ with $d_{E}(z,y)<\delta$, put $h=z-y$, so that $\lVert h\rVert=d_{E}(z,y)<\delta_{1}$ 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; then

$$u(z)\le u(y)+\varphi(z)-\varphi(y)\le u(y)+r\cdot(z-y)+\tfrac{1}{2}(z-y)\cdot\bigl(Y(z-y)\bigr),$$

which is the required inequality.

Conversely, suppose the stated condition holds and let $\varepsilon$ be positive; take $y$, $r$, $Y$ and $\delta$ as provided. By Quadratic and Affine Functions of Class $C^2$, Translation, and Quadratic Perturbation of Semiconvexity (i) the function $\Psi:\mathbb{R}^{n}\to\mathbb{R}$ with $\Psi(\zeta)=\tfrac{1}{2}\zeta\cdot(Y\zeta)+r\cdot\zeta+u(y)$ is of class $C^{2}$ on $\mathbb{R}^{n}$ with $D\Psi(\zeta)=Y\zeta+r$ and $D^{2}\Psi(\zeta)=Y$. By Quadratic and Affine Functions of Class $C^2$, Translation, and Quadratic Perturbation of Semiconvexity (ii), applied with the vector $-y$, for which $\mathbb{R}^{n}-(-y)=\mathbb{R}^{n}$, the function $\varphi_{0}:\mathbb{R}^{n}\to\mathbb{R}$ with $\varphi_{0}(z)=\Psi(z-y)$ is of class $C^{2}$ on $\mathbb{R}^{n}$ with $D\varphi_{0}(z)=Y(z-y)+r$ and $D^{2}\varphi_{0}(z)=Y$; explicitly

$$\varphi_{0}(z)=u(y)+r\cdot(z-y)+\tfrac{1}{2}(z-y)\cdot\bigl(Y(z-y)\bigr),$$

so that $\varphi_{0}(y)=u(y)$, $D\varphi_{0}(y)=r$ and $D^{2}\varphi_{0}(y)=Y$. Let $\varphi$ be the restriction of $\varphi_{0}$ to $U$, which is of class $C^{2}$ on $U$ with the same gradient and Hessian at points of $U$, by claims 1 and 3 of Restriction of a Cᵏ Function to an Open Subset. For $z\in U$ with $d_{E}(z,y)<\delta$ the hypothesis gives $u(z)\le\varphi(z)$, hence

$$u(z)-\varphi(z)\le0=u(y)-\varphi(y),$$

so $u-\varphi$ has a local maximum at $y$ relative to $U$. Since $D\varphi(y)=r$ and $D^{2}\varphi(y)=Y$, the four numerical inequalities of Quadruple Approximable by Test-Function Data (i) are exactly those assumed, and the quadruple is approximable by test data from above for $u$.

For approximability from below the argument is the same with $Y=D^{2}\varphi(y)-\varepsilon'I_{n}$ in the first direction, all the inequalities between values of $u$ and of $\varphi$ reversed, local minima in place of local maxima, and $\lVert-\varepsilon'I_{n}\rVert=\varepsilon'$ used in the estimate of $d_{\mathcal{S}(n)}(Y,X)$.

Claim 2. Let $\varepsilon$ be positive. Take $y=x_{0}$, $r=p$ and $Y=X+\tfrac{\varepsilon}{2}I_{n}\in\mathcal{S}(n)$. Then $d_{E}(y,x_{0})=0<\varepsilon$ and $|u(y)-u(x_{0})|=0<\varepsilon$ and $\lVert r-p\rVert=0<\varepsilon$, 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, while $d_{\mathcal{S}(n)}(Y,X)=\lVert\tfrac{\varepsilon}{2}I_{n}\rVert=\tfrac{\varepsilon}{2}<\varepsilon$. Applying Twice Differentiability at a Point (i) with the positive parameter $\tfrac{\varepsilon}{4}$, there is a positive $\delta$ such that $\lVert h\rVert<\delta$ implies $x_{0}+h\in U$ and

$$u(x_{0}+h)-u(x_{0})-p\cdot h-\tfrac{1}{2}h\cdot(Xh)\le\tfrac{\varepsilon}{4}\lVert h\rVert^{2}.$$

Since $\tfrac{1}{2}h\cdot(Yh)=\tfrac{1}{2}h\cdot(Xh)+\tfrac{\varepsilon}{4}\lVert h\rVert^{2}$, this gives, for $z\in U$ with $d_{E}(z,x_{0})<\delta$ and $h=z-y$,

$$u(z)\le u(y)+r\cdot(z-y)+\tfrac{1}{2}(z-y)\cdot\bigl(Y(z-y)\bigr),$$

so claim 1 gives approximability from above. Taking instead $Y=X-\tfrac{\varepsilon}{2}I_{n}$ and using the lower estimate supplied by the same application of Twice Differentiability at a Point (i) gives approximability from below.

Claim 3. Let $\varepsilon$ be positive and put $\varepsilon'=\tfrac{\varepsilon}{2}$. By the four convergence hypotheses there are $N_{1},N_{2},N_{3},N_{4}\in\mathbb{N}$ beyond which the corresponding distances are smaller than $\varepsilon'$; put $k=N_{1}+N_{2}+N_{3}+N_{4}$, which is at least each of them since natural numbers are nonnegative, so that

$$d_{E}(y_{k},x_{0})<\varepsilon',\quad |u(y_{k})-u(x_{0})|<\varepsilon',\quad \lVert p_{k}-p\rVert<\varepsilon',\quad d_{\mathcal{S}(n)}(X_{k},X)<\varepsilon' .$$

Since $\bigl(y_{k},u(y_{k}),p_{k},X_{k}\bigr)$ is approximable by test data from above for $u$, claim 1 applied with $\varepsilon'$ yields $y\in U$, $r\in\mathbb{R}^{n}$, $Y\in\mathcal{S}(n)$ and a positive $\delta$ with

$$d_{E}(y,y_{k})<\varepsilon',\quad |u(y)-u(y_{k})|<\varepsilon',\quad \lVert r-p_{k}\rVert<\varepsilon',\quad d_{\mathcal{S}(n)}(Y,X_{k})<\varepsilon'$$

and $u(z)\le u(y)+r\cdot(z-y)+\tfrac{1}{2}(z-y)\cdot(Y(z-y))$ for every $z\in U$ with $d_{E}(z,y)<\delta$. The triangle inequality for the metric $d_{E}$, for the absolute value (claim 5 of Properties of the Absolute Value in an Ordered Field), for the Euclidean norm (claim 6 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square) and for the metric $d_{\mathcal{S}(n)}$ gives

$$d_{E}(y,x_{0})<\varepsilon,\quad |u(y)-u(x_{0})|<\varepsilon,\quad \lVert r-p\rVert<\varepsilon,\quad d_{\mathcal{S}(n)}(Y,X)<\varepsilon .$$

As $\varepsilon$ was arbitrary, claim 1 shows that $\bigl(x_{0},u(x_{0}),p,X\bigr)$ is approximable by test data from above for $u$. The argument for approximability from below is identical.

Claim 4. Note that $x_{0}-b\in U-b$ and that $\tilde{u}(x_{0}-b)=u(x_{0})+q\cdot(x_{0}-b)+c$.

Assume $\bigl(x_{0},u(x_{0}),p,X\bigr)$ is approximable by test data from above for $u$ and let $\varepsilon$ be positive. The number $1+\lVert q\rVert$ is positive, so $\varepsilon_{1}=\varepsilon\,(1+\lVert q\rVert)^{-1}$ is positive, and $\varepsilon_{1}\le\varepsilon$ because $1\le1+\lVert q\rVert$. Apply claim 1 with $\varepsilon_{1}$ to obtain $y\in U$, $r$, $Y$ and a positive $\delta$. Put $\tilde{y}=y-b\in U-b$ and $\tilde{r}=r+q$. Then, 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 and the vector space identities,

$$d_{E}(\tilde{y},x_{0}-b)=\lVert y-x_{0}\rVert=d_{E}(y,x_{0})<\varepsilon_{1}\le\varepsilon,$$

and $\lVert\tilde{r}-(p+q)\rVert=\lVert r-p\rVert<\varepsilon$, and $d_{\mathcal{S}(n)}(Y,X)<\varepsilon$. Moreover

$$\tilde{u}(\tilde{y})-\tilde{u}(x_{0}-b)=\bigl(u(y)-u(x_{0})\bigr)+q\cdot(y-x_{0}),$$

so by claim 5 of Properties of the Absolute Value in an Ordered Field and The Cauchy-Schwarz Inequality on $\mathbb{R}^n$,

$$\bigl|\tilde{u}(\tilde{y})-\tilde{u}(x_{0}-b)\bigr|<\varepsilon_{1}+\lVert q\rVert\,\varepsilon_{1}=\varepsilon_{1}\bigl(1+\lVert q\rVert\bigr)=\varepsilon .$$

Finally let $z\in U-b$ with $d_{E}(z,\tilde{y})<\delta$. Then $z+b\in U$ and $d_{E}(z+b,y)=\lVert z-\tilde{y}\rVert=d_{E}(z,\tilde{y})<\delta$, so

$$u(z+b)\le u(y)+r\cdot\bigl((z+b)-y\bigr)+\tfrac{1}{2}\bigl((z+b)-y\bigr)\cdot\Bigl(Y\bigl((z+b)-y\bigr)\Bigr),$$

and $(z+b)-y=z-\tilde{y}$. Adding $q\cdot z+c$ to both sides and using

$$u(y)+q\cdot z+c=\bigl(u(y)+q\cdot\tilde{y}+c\bigr)+q\cdot(z-\tilde{y})=\tilde{u}(\tilde{y})+q\cdot(z-\tilde{y}),$$

which holds by claims 2 and 5 of The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite, we obtain

$$\tilde{u}(z)\le\tilde{u}(\tilde{y})+\tilde{r}\cdot(z-\tilde{y})+\tfrac{1}{2}(z-\tilde{y})\cdot\bigl(Y(z-\tilde{y})\bigr).$$

By claim 1, applied on the open set $U-b$ to the function $\tilde{u}$, the quadruple $\bigl(x_{0}-b,\tilde{u}(x_{0}-b),p+q,X\bigr)$ is approximable by test data from above for $\tilde{u}$.

For the converse, apply what has just been proved to the function $\tilde{u}$ on $U-b$ with the vector $-b$, the vector $-q$ and the constant $q\cdot b-c$. The resulting set is $(U-b)-(-b)=U$ and the resulting function is

$$z\mapsto\tilde{u}(z-b)+(-q)\cdot z+\bigl(q\cdot b-c\bigr)=u(z)+q\cdot(z-b)+c-q\cdot z+q\cdot b-c=u(z),$$

so the conclusion reads that $\bigl((x_{0}-b)-(-b),\,u(x_{0}),\,(p+q)+(-q),\,X\bigr)=\bigl(x_{0},u(x_{0}),p,X\bigr)$ is approximable by test data from above for $u$, as required. The argument for approximability from below is identical throughout.

Claim 5. Assume $\bigl(x_{0},u(x_{0}),p,X\bigr)$ is approximable by test data from above for $u$ and let $\varepsilon$ be positive. Since $W$ is open and $x_{0}\in W$ there is a positive $\rho$ with $\{z:d_{E}(z,x_{0})<\rho\}\subseteq W$. Let $\varepsilon_{1}$ be the smaller of $\varepsilon$ and $\tfrac{\rho}{2}$, which is positive, and apply claim 1 with $\varepsilon_{1}$ to obtain $y\in U$, $r$, $Y$ and a positive $\delta$; let $\delta'$ be the smaller of $\delta$ and $\tfrac{\rho}{2}$. Since $d_{E}(y,x_{0})<\varepsilon_{1}\le\tfrac{\rho}{2}<\rho$ we have $y\in W$, hence $y\in U'$ and $u'(y)=u(y)$; and $u'(x_{0})=u(x_{0})$ because $x_{0}\in W$. Therefore the four numerical inequalities hold for $u'$ with $\varepsilon_{1}\le\varepsilon$ in place of $\varepsilon$.

Let $z\in U'$ with $d_{E}(z,y)<\delta'$. By the triangle inequality for $d_{E}$,

$$d_{E}(z,x_{0})\le d_{E}(z,y)+d_{E}(y,x_{0})<\tfrac{\rho}{2}+\tfrac{\rho}{2}=\rho,$$

so $z\in W$, whence $z\in U$ and $u'(z)=u(z)$; and $d_{E}(z,y)<\delta$, so

$$u'(z)=u(z)\le u(y)+r\cdot(z-y)+\tfrac{1}{2}(z-y)\cdot\bigl(Y(z-y)\bigr)=u'(y)+r\cdot(z-y)+\tfrac{1}{2}(z-y)\cdot\bigl(Y(z-y)\bigr).$$

By claim 1, applied on $U'$ to $u'$, the quadruple $\bigl(x_{0},u'(x_{0}),p,X\bigr)$ is approximable by test data from above for $u'$. The argument for approximability from below is identical.