Proof of Ekeland's Variational Principle for Upper Semicontinuous Functions on a Complete Metric Space

Put $\alpha=\eta/\kappa$, a positive real, and $\beta=\sup_{x\in X}F(x)$, which exists by The Real Numbers: Standing Notation and Background §bounds since $X$ is nonempty (it contains $x_{0}$) and $F$ is bounded above. Natural numbers are read in $\mathbb{R}$ through the canonical map as in The Real Numbers: Standing Notation and Background §numbers, so $1/n$ is a positive real for every $n\in\mathbb{N}$; the successor of $n$ is written $n+1$. For $z\in X$ let

Step 1 (Properties of the sets $P(z)$). Let $z\in X$.

(a) $z\in P(z)$, since $d(z,z)=0$. Hence the set $\{F(y):y\in P(z)\}$ is nonempty, and it is bounded above by $\beta$; let $M(z)$ be its supremum (The Real Numbers: Standing Notation and Background §bounds).

(b) If $y\in P(z)$, then $P(y)\subseteq P(z)$: for $w\in P(y)$, the triangle inequality of Metric Space gives

(c) If $y\in X$ is such that for every real $\delta>0$ some $w\in P(z)$ satisfies $d(y,w)<\delta$, then $y\in P(z)$. Suppose not; then $\gamma=F(z)-F(y)+\alpha\,d(y,z)$ is positive. Since $F$ is upper semicontinuous at $y$ relative to $X$, there is $\delta_{0}>0$ with $F(w)<F(y)+\gamma/2$ for all $w\in X$ with $d(y,w)<\delta_{0}$. Let $\delta$ be the smaller of $\delta_{0}$ and $\gamma/(2\alpha)$, and take $w\in P(z)$ with $d(y,w)<\delta$. The triangle inequality gives $d(w,z)\ge d(y,z)-d(y,w)$, hence

contradicting $w\in P(z)$.

Step 2 (Construction of the sequence). Let $R$ be the relation on the nonempty set $\mathbb{N}\times X$ consisting of the pairs $\bigl((n,z),(n+1,y)\bigr)$ with $n\in\mathbb{N}$, $z\in X$, $y\in P(z)$ and $F(y)>M(z)-1/n$. Every $(n,z)$ has an $R$-successor: by claim 3 of Approximation Property of the Supremum and the Infimum in $\mathbb{R}$, applied to the set $\{F(y):y\in P(z)\}$ with $\varepsilon=1/n$, there is $y\in P(z)$ with $F(y)>M(z)-1/n$. By Axiom of Dependent Choice there is a sequence $(a_{m})_{m\in\mathbb{N}}$ in $\mathbb{N}\times X$ with $a_{1}=(1,x_{0})$ and $(a_{m},a_{m+1})\in R$ for every $m$. By the form of $R$ and induction on $m$, $a_{m}=(m,z_{m})$ for a sequence $(z_{m})_{m\in\mathbb{N}}$ in $X$ with

Step 3 (Nesting). We claim $P(z_{m})\subseteq P(z_{n})$ whenever $n\le m$, by induction on $m$. For $m=1$, $n\le1$ and $1\le n$ (claim 4 of Properties of the Order on the Natural Numbers) force $n=1$ by claim 2 there. If the claim holds for $m$ and $n\le m+1$, then either $n=m+1$, or $n\le m$ by claim 5 of Properties of the Order on the Natural Numbers; in the latter case Step 1(b) with $z_{m+1}\in P(z_{m})$ gives $P(z_{m+1})\subseteq P(z_{m})\subseteq P(z_{n})$. By Step 1(a) it follows that $z_{m}\in P(z_{n})$ whenever $n\le m$.

Step 4 (Small sets). Let $n\in\mathbb{N}$ and $y\in P(z_{n+1})$. Then $y\in P(z_{n})$ by Step 3, so $F(y)\le M(z_{n})<F(z_{n+1})+1/n$, while $y\in P(z_{n+1})$ gives $\alpha\,d(y,z_{n+1})\le F(y)-F(z_{n+1})$. Hence

Step 5 (Cauchy sequence and limit). Let a real $\varepsilon>0$ be given. By claim 3 of The Archimedean Property of the Real Numbers choose $n\in\mathbb{N}$ with $1/n<\alpha\varepsilon/2$. For $m,\ell\in\mathbb{N}$ with $m\ge n+1$ and $\ell\ge n+1$, Step 3 gives $z_{m},z_{\ell}\in P(z_{n+1})$, so by $(*)$ and the triangle inequality $d(z_{m},z_{\ell})\le d(z_{m},z_{n+1})+d(z_{n+1},z_{\ell})<2/(n\alpha)<\varepsilon$. Thus $(z_{m})$ is a Cauchy sequence, and since $(X,d)$ is complete it converges to some $\bar{x}\in X$.

We show $\bar{x}\in P(z_{n})$ for every $n\in\mathbb{N}$, using Step 1(c). Given a real $\delta>0$, convergence gives $N\in\mathbb{N}$ with $d(z_{m},\bar{x})<\delta$ for all $m\ge N$; let $m$ be the larger of $N$ and $n$ (trichotomy, claim 3 of Properties of the Order on the Natural Numbers). Then $z_{m}\in P(z_{n})$ by Step 3 and $d(\bar{x},z_{m})<\delta$, so Step 1(c) gives $\bar{x}\in P(z_{n})$.

Step 6 (Strict perturbed maximum). Let $y\in P(\bar{x})$. For each $n\in\mathbb{N}$, $\bar{x}\in P(z_{n+1})$ by Step 5, so $P(\bar{x})\subseteq P(z_{n+1})$ by Step 1(b), and $(*)$ applied to $y$ and to $\bar{x}$ gives $d(y,\bar{x})\le d(y,z_{n+1})+d(z_{n+1},\bar{x})<2/(n\alpha)$. Given a real $\varepsilon>0$, choosing $n$ with $1/n<\alpha\varepsilon/2$ by claim 3 of The Archimedean Property of the Real Numbers yields $d(y,\bar{x})<\varepsilon$; since $d(y,\bar{x})\ge0$, vanishing gives $d(y,\bar{x})=0$, so $y=\bar{x}$ by Metric Space. Therefore $P(\bar{x})=\{\bar{x}\}$. For $x\in X$ with $x\neq\bar{x}$ we thus have $x\notin P(\bar{x})$, that is, $F(x)-\frac{\eta}{\kappa}\,d(x,\bar{x})<F(\bar{x})$, which is property 3.

Step 7 (Value and distance). By Step 5, $\bar{x}\in P(z_{1})=P(x_{0})$, so $F(\bar{x})\ge F(x_{0})+\alpha\,d(\bar{x},x_{0})\ge F(x_{0})$, which is property 1. Moreover $F(\bar{x})\le\beta\le F(x_{0})+\eta$ by the hypothesis on $x_{0}$, so $\alpha\,d(\bar{x},x_{0})\le F(\bar{x})-F(x_{0})\le\eta$, and dividing by $\alpha=\eta/\kappa>0$ gives $d(\bar{x},x_{0})\le\kappa$, which is property 2.