Proof of Comparison Principle for Slope-Based Solutions of the Discounted Hopf-Lax Equation on a Complete Metric Space with Interpolation Points

Each result cited below is universally quantified over the data in its own statement.

Throughout, $H(x,r,p)=\rho\,r+\frac{1}{2}p^{2}-f(x)$ for $x\in X$, $r\in\mathbb{R}$ and $p\in T$ is the Hamiltonian $H_{\rho,f}$ on $X$ of The Discounted Stationary Hopf-Lax Equation on an Open Subset of a Metric Space, so that by The Discounted Stationary Hopf-Lax Equation on an Open Subset of a Metric Space §discounted-hopf-lax the hypotheses say that $u$ is an s-subsolution and $v$ an s-supersolution of $H=0$ in $X$. In particular, by Slope-Based Viscosity Subsolutions, Supersolutions and Solutions on a Metric Space §subsolution and Slope-Based Viscosity Subsolutions, Supersolutions and Solutions on a Metric Space §supersolution, $u$ is upper semicontinuous on $X$ and $v$ is lower semicontinuous on $X$, and by Slope-Based Viscosity Subsolutions, Supersolutions and Solutions on a Metric Space §hamiltonian we have $H(x,r,p)\le H(x,r,p')$ whenever $p,p'\in T$ and $p\le p'$.

We argue by contradiction. Suppose that there is $z\in X$ with $v(z)<u(z)$, and put $\theta=u(z)-v(z)$, a positive real. The constants are chosen in the order $M$, $\beta$, $\sigma$, $\gamma$, $\varepsilon$ of Step 2; the points $(x_{0},y_{0})$ and $(x_{\varepsilon},y_{\varepsilon})$ of Step 3 are chosen after $\varepsilon$.

Step 1 (the doubled space). Let $Z=X\times X$ and $\varrho\bigl((x,y),(x',y')\bigr)=d(x,x')+d(y,y')$. Conditions 1, 3 and 4 of Metric Space for $\varrho$ follow by adding the same conditions for $d$ in the two coordinates; and since both summands are nonnegative, $\varrho\bigl((x,y),(x',y')\bigr)=0$ holds exactly when $d(x,x')=0$ and $d(y,y')=0$, that is, by condition 2 for $d$, exactly when $(x,y)=(x',y')$. So $(Z,\varrho)$ is a metric space.

It is complete: let $\bigl((x_{m},y_{m})\bigr)$ be a Cauchy sequence in $(Z,\varrho)$. Since $d(x_{m},x_{\ell})\le\varrho\bigl((x_{m},y_{m}),(x_{\ell},y_{\ell})\bigr)$ and $d(y_{m},y_{\ell})\le\varrho\bigl((x_{m},y_{m}),(x_{\ell},y_{\ell})\bigr)$, the sequences $(x_{m})$ and $(y_{m})$ are Cauchy sequences in $(X,d)$, so by completeness of $(X,d)$ they converge to some $\bar{x}\in X$ and $\bar{y}\in X$. Given a real $\tau>0$, take $N_{1},N_{2}\in\mathbb{N}$ with $d(x_{m},\bar{x})<\tau/2$ for $m\ge N_{1}$ and $d(y_{m},\bar{y})<\tau/2$ for $m\ge N_{2}$; then $\varrho\bigl((x_{m},y_{m}),(\bar{x},\bar{y})\bigr)<\tau$ for $m\ge\max\{N_{1},N_{2}\}$, so $\bigl((x_{m},y_{m})\bigr)$ converges to $(\bar{x},\bar{y})$ in $(Z,\varrho)$.

Now let $\varepsilon$ be a positive real and $\Phi(x,y)=u(x)-v(y)-\frac{1}{\varepsilon}d(x,y)^{2}$ on $Z$. Then $\Phi$ is upper semicontinuous on $Z$ in the sense of Upper Semicontinuous Function on a Subset of a Metric Space (for the metric space $(Z,\varrho)$). Indeed, fix $(\bar{x},\bar{y})\in Z$ and a real $\tau>0$, and put $\ell=d(\bar{x},\bar{y})$. Upper semicontinuity of $u$ at $\bar{x}$ gives a real $\delta_{1}>0$ with $u(x)<u(\bar{x})+\tau/3$ for all $x\in X$ with $d(\bar{x},x)<\delta_{1}$; lower semicontinuity of $v$ at $\bar{y}$ gives a real $\delta_{2}>0$ with $v(\bar{y})-\tau/3<v(y)$ for all $y\in X$ with $d(\bar{y},y)<\delta_{2}$. Let $\delta_{3}=\min\{1,\varepsilon\tau/(3(2\ell+1))\}$ and $\delta_{0}=\min\{\delta_{1},\delta_{2},\delta_{3}\}$, and let $(x,y)\in Z$ with $s=\varrho\bigl((x,y),(\bar{x},\bar{y})\bigr)<\delta_{0}$. Then $d(\bar{x},x)\le s$ and $d(\bar{y},y)\le s$, and the triangle inequality (condition 4 of Metric Space) gives $\ell\le d(\bar{x},x)+d(x,y)+d(y,\bar{y})$ and $d(x,y)\le d(x,\bar{x})+\ell+d(\bar{y},y)$, so $|d(x,y)-\ell|\le s$. If $d(x,y)\le\ell$ then

and if $\ell<d(x,y)$ then $\ell^{2}-d(x,y)^{2}<0<\varepsilon\tau/3$. Adding the three estimates, $\Phi(x,y)<\Phi(\bar{x},\bar{y})+\tau$.

Step 2 (constants). Since $u$ and $v$ are bounded above and below in the sense of The Real Numbers: Standing Notation and Background §bounds, there are reals $a_{1},b_{1},a_{2},b_{2}$ with $a_{1}\le u(x)\le b_{1}$ and $a_{2}\le v(x)\le b_{2}$ for every $x\in X$; with $M=1+|a_{1}|+|b_{1}|+|a_{2}|+|b_{2}|$, a positive real, we get $|u(x)|\le M$ and $|v(x)|\le M$ for every $x\in X$, hence $u(x)-v(y)\le 2M$ for all $x,y\in X$. Let $\beta=\rho\theta/4$, a positive real. By uniform continuity of $f$ on $X$ there is a real $\sigma>0$ with $|f(x)-f(y)|<\beta$ for all $x,y\in X$ with $d(x,y)<\sigma$. Let $\gamma=\min\{\sigma,\beta/4\}$, and finally

Then $0<\varepsilon<1$, so $\varepsilon^{2}\le\varepsilon$, and

Step 3 (doubling of variables and Ekeland's principle). Let $\Phi$ be the function of Step 1 for this $\varepsilon$. For all $(x,y)\in Z$ we have $\Phi(x,y)\le u(x)-v(y)\le 2M$, so the nonempty set $\Phi(Z)$ is bounded above and $S=\sup_{(x,y)\in Z}\Phi(x,y)$ exists by The Real Numbers: Standing Notation and Background §bounds, with $\theta=\Phi(z,z)\le S$. By claim 3 of Approximation Property of the Supremum and the Infimum in $\mathbb{R}$, applied with the positive real $\varepsilon^{2}$, there is $(x_{0},y_{0})\in Z$ with $S-\varepsilon^{2}<\Phi(x_{0},y_{0})$. By Step 1, Ekeland's Variational Principle for Upper Semicontinuous Functions on a Complete Metric Space applies to $F=\Phi$ on the complete metric space $(Z,\varrho)$ with $\eta=\varepsilon^{2}$ and $\kappa=\varepsilon$, so that $\eta/\kappa=\varepsilon$; it gives $(x_{\varepsilon},y_{\varepsilon})\in Z$ such that, by Ekeland's Variational Principle for Upper Semicontinuous Functions on a Complete Metric Space §value,

and, by Ekeland's Variational Principle for Upper Semicontinuous Functions on a Complete Metric Space §perturbed, $\Phi(x,y)-\varepsilon\,d(x,x_{\varepsilon})-\varepsilon\,d(y,y_{\varepsilon})<\Phi(x_{\varepsilon},y_{\varepsilon})$ for every $(x,y)\ne(x_{\varepsilon},y_{\varepsilon})$. Since the left-hand side equals $\Phi(x_{\varepsilon},y_{\varepsilon})$ at $(x,y)=(x_{\varepsilon},y_{\varepsilon})$, we get

Put $\delta=d(x_{\varepsilon},y_{\varepsilon})$ and $p=2\delta/\varepsilon$, a nonnegative real. From $\theta-\varepsilon^{2}\le\Phi(x_{\varepsilon},y_{\varepsilon})=u(x_{\varepsilon})-v(y_{\varepsilon})-\delta^{2}/\varepsilon$ we get

and $\delta^{2}/\varepsilon\le u(x_{\varepsilon})-v(y_{\varepsilon})-\theta+\varepsilon^{2}\le 2M+1$, because $0<\theta$ and $\varepsilon^{2}<1$. Hence $\delta^{2}\le\varepsilon(2M+1)<\gamma^{2}$ by (2.1), and since $\delta$ and $\gamma$ are nonnegative, claim 1 of Monotonicity of Squaring on the Nonnegative Elements of an Ordered Field gives

Step 4 (subsolution test at $x_{\varepsilon}$). Define $\psi_{1},\psi_{2}:X\to\mathbb{R}$ by $\psi_{1}(x)=\frac{1}{\varepsilon}d(x,y_{\varepsilon})^{2}+v(y_{\varepsilon})$ and $\psi_{2}(x)=\varepsilon\,d(x,x_{\varepsilon})$. Since $(X,d)$ has interpolation points, Elementary Properties of Local Slopes: Order, Negation, Bounds from Difference Quotients, Lipschitz Functions and Squared Distances §squared-distance, applied with $\Omega=X$, $x_{0}=y_{\varepsilon}$, $k=1/\varepsilon$ and $C=v(y_{\varepsilon})$, shows that $\psi_{1}\in\underline{\mathcal{C}}(X)$ and $|\nabla\psi_{1}|(x_{\varepsilon})=2\,d(x_{\varepsilon},y_{\varepsilon})/\varepsilon=p$. For $y,w\in X$ the triangle inequality gives $|d(y,x_{\varepsilon})-d(w,x_{\varepsilon})|\le d(y,w)$, so $|\psi_{2}(y)-\psi_{2}(w)|\le\varepsilon\,d(y,w)$; by Elementary Properties of Local Slopes: Order, Negation, Bounds from Difference Quotients, Lipschitz Functions and Squared Distances §lipschitz with $L=\varepsilon$, $\psi_{2}$ is locally Lipschitz on $X$ and $e_{1}=|\nabla\psi_{2}|^{*}(x_{\varepsilon})$ satisfies $e_{1}\le\varepsilon$. Taking $y=y_{\varepsilon}$ in (3.1) and noting $\psi_{2}(x_{\varepsilon})=0$, we get $u(x)-\psi_{1}(x)-\psi_{2}(x)\le u(x_{\varepsilon})-\psi_{1}(x_{\varepsilon})-\psi_{2}(x_{\varepsilon})$ for every $x\in X$, so $u-\psi_{1}-\psi_{2}$ has a local maximum at $x_{\varepsilon}$ relative to $X$ (with any radius). By Slope-Based Viscosity Subsolutions, Supersolutions and Solutions on a Metric Space §subsolution,

Let $p_{-}=\max\{p-\varepsilon,0\}\in T$. Since $p-\varepsilon\le p-e_{1}$, claim 1 of Elementary Properties of the Maximum of Two Elements gives $p-\varepsilon\le\max\{p-e_{1},0\}$ and $0\le\max\{p-e_{1},0\}$, so claim 3 of the same lemma gives $p_{-}\le\max\{p-e_{1},0\}$. By the monotonicity of $H$ recalled above, $H(x_{\varepsilon},u(x_{\varepsilon}),p_{-})\le0$, that is,

Step 5 (supersolution test at $y_{\varepsilon}$). Define $\psi_{3},\psi_{4}:X\to\mathbb{R}$ by $\psi_{3}(y)=-\frac{1}{\varepsilon}d(y,x_{\varepsilon})^{2}+u(x_{\varepsilon})$ and $\psi_{4}(y)=-\varepsilon\,d(y,y_{\varepsilon})$. Then $\psi_{3}=-\varphi$ with $\varphi(y)=\frac{1}{\varepsilon}d(y,x_{\varepsilon})^{2}-u(x_{\varepsilon})$, so the last sentence of Elementary Properties of Local Slopes: Order, Negation, Bounds from Difference Quotients, Lipschitz Functions and Squared Distances §squared-distance (with $\Omega=X$, $x_{0}=x_{\varepsilon}$, $k=1/\varepsilon$, $C=-u(x_{\varepsilon})$) shows that $\psi_{3}\in\overline{\mathcal{C}}(X)$ and $|\nabla\psi_{3}|(y_{\varepsilon})=2\,d(y_{\varepsilon},x_{\varepsilon})/\varepsilon=p$. As in Step 4, $|\psi_{4}(y)-\psi_{4}(w)|\le\varepsilon\,d(y,w)$ for $y,w\in X$, so by Elementary Properties of Local Slopes: Order, Negation, Bounds from Difference Quotients, Lipschitz Functions and Squared Distances §lipschitz $\psi_{4}$ is locally Lipschitz on $X$ and $e_{2}=|\nabla\psi_{4}|^{*}(y_{\varepsilon})$ satisfies $e_{2}\le\varepsilon$. Taking $x=x_{\varepsilon}$ in (3.1) and using $d(x_{\varepsilon},y)=d(y,x_{\varepsilon})$, we get $u(x_{\varepsilon})-v(y)-\frac{1}{\varepsilon}d(y,x_{\varepsilon})^{2}-\varepsilon\,d(y,y_{\varepsilon})\le u(x_{\varepsilon})-v(y_{\varepsilon})-\frac{1}{\varepsilon}\delta^{2}$, which rearranges to $v(y_{\varepsilon})-\psi_{3}(y_{\varepsilon})-\psi_{4}(y_{\varepsilon})\le v(y)-\psi_{3}(y)-\psi_{4}(y)$ for every $y\in X$. So $v-\psi_{3}-\psi_{4}$ has a local minimum at $y_{\varepsilon}$ relative to $X$, and Slope-Based Viscosity Subsolutions, Supersolutions and Solutions on a Metric Space §supersolution gives $H(y_{\varepsilon},v(y_{\varepsilon}),p+e_{2})\ge0$. Since $p+e_{2}\le p+\varepsilon$ and both lie in $T$, monotonicity of $H$ gives $H(y_{\varepsilon},v(y_{\varepsilon}),p+\varepsilon)\ge0$, that is,

Step 6 (the quadratic terms). We show $\frac{1}{2}(p+\varepsilon)^{2}-\frac{1}{2}p_{-}^{2}\le 2\varepsilon p+2\varepsilon^{2}$. If $\varepsilon\le p$, then $0\le p-\varepsilon\le p_{-}$ by claim 1 of Elementary Properties of the Maximum of Two Elements, so $(p-\varepsilon)^{2}\le p_{-}^{2}$ by claim 2 of Monotonicity of Squaring on the Nonnegative Elements of an Ordered Field, and $\frac{1}{2}(p+\varepsilon)^{2}-\frac{1}{2}(p-\varepsilon)^{2}=2\varepsilon p$. If $p<\varepsilon$, then $0\le p+\varepsilon\le2\varepsilon$, so $(p+\varepsilon)^{2}\le4\varepsilon^{2}$ by claim 2 of Monotonicity of Squaring on the Nonnegative Elements of an Ordered Field, and with $0\le p_{-}^{2}$ we get $\frac{1}{2}(p+\varepsilon)^{2}-\frac{1}{2}p_{-}^{2}\le2\varepsilon^{2}\le2\varepsilon p+2\varepsilon^{2}$. Since $\varepsilon p=2\delta$,

Step 7 (contradiction). Adding (4.1) and (5.1) and using (6.1),

Since $0<\rho$, (3.2) gives $\rho\theta-\rho\varepsilon^{2}\le\rho\bigl(u(x_{\varepsilon})-v(y_{\varepsilon})\bigr)$. By (3.3), $d(x_{\varepsilon},y_{\varepsilon})=\delta<\sigma$, so $|f(x_{\varepsilon})-f(y_{\varepsilon})|<\beta$ by the choice of $\sigma$, and $4\delta<\beta$. Together with (2.1),

which is impossible because $0<\beta$. Hence there is no $z\in X$ with $v(z)<u(z)$, that is, $u(x)\le v(x)$ for every $x\in X$.