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 §identity, 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 Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$ and claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$.

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 §above 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

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

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 §c2 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 §twice-differentiable 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

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 Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$ and the identity recorded at the start, this reads

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 Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$; then

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 §quadratic 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 §translation, 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

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^k$ Map to an Open Subset. For $z\in U$ with $d_{E}(z,y)<\delta$ the hypothesis gives $u(z)\le\varphi(z)$, hence

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 §above 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 Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$, while $d_{\mathcal{S}(n)}(Y,X)=\lVert\tfrac{\varepsilon}{2}I_{n}\rVert=\tfrac{\varepsilon}{2}<\varepsilon$. Applying Twice Differentiability at a Point §twice-differentiable 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

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

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 §twice-differentiable 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

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

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 Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$) and for the metric $d_{\mathcal{S}(n)}$ gives

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 Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ and the vector space identities,

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

so by claim 5 of Properties of the Absolute Value in an Ordered Field and Cauchy-Schwarz Inequality for the Euclidean Dot Product,

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

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

which holds by claims 2 and 5 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$, we obtain

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

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}$,

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

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.