Ekeland's variational principle

Let ${\displaystyle f:X\to \mathbb {R} \cup \{-\infty ,+\infty \}}$ be a function. Then,

• ${\displaystyle \operatorname {dom} f:=\left\{x\in X:f(x)\neq +\infty \right\}}$.
• f is proper if ${\displaystyle \operatorname {dom} f\neq \emptyset }$ (i.e. if f is not identically ${\displaystyle +\infty }$).
• f is bounded below if ${\displaystyle \inf _{x\in X}f(x)>-\infty }$.
• given ${\displaystyle x_{0}\in X}$, say that f is lower semicontinuous at ${\displaystyle x_{0}}$ if for every ${\displaystyle y<f(x_{0})}$ there exists a neighborhood ${\displaystyle U}$ of ${\displaystyle x_{0}}$ such that ${\displaystyle f(x)>y}$ for all ${\displaystyle x}$ in ${\displaystyle U}$.
• f is lower semicontinuous if it is lower semicontinuous at every point of X.
  • A function is lower semi-continuous if and only if ${\displaystyle \{x\in X:~f(x)>y\}}$ is an open set for every ${\displaystyle y\in \mathbb {R} }$; alternatively, a function is lower semi-continuous if and only if all of its lower level sets ${\displaystyle \{x\in X:~f(x)\leq y\}}$ are closed.

Theorem (Ekeland):[7] Let ${\displaystyle (X,d)}$ be a complete metric space and ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \}}$ a proper (i.e. not identically ${\displaystyle +\infty }$) lower semicontinuous function that is bounded below. Pick ${\displaystyle \epsilon >0}$ and ${\displaystyle x_{0}\in X}$ such that ${\displaystyle f(x_{0})\neq +\infty }$ (or equivalently, ${\displaystyle f(x_{0})\in \mathbb {R} }$). There exists some ${\displaystyle v\in X}$ such that

${\displaystyle f(v)\leq f\left(x_{0}\right)-\epsilon d\left(x_{0},v\right)}$

and for all ${\displaystyle x\neq v}$,

${\displaystyle f(v)<f(x)+\epsilon d\left(v,x\right)}$.

Define a function ${\displaystyle G:X\times X\to \mathbb {R} \cup \{+\infty \}}$ by

${\displaystyle G\left(x,y\right):=f(x)+\epsilon d(x,y)}$

and note that G is lower semicontinuous (being the sum of the lower semicontinuous function f and the continuous function ${\displaystyle (x,y)\mapsto \epsilon d(x,y)}$). Given ${\displaystyle z\in X}$, define the functions ${\displaystyle G_{z}:=G(z,\cdot ):X\to \mathbb {R} \cup \{+\infty \}}$ and ${\displaystyle G^{z}:=G(\cdot ,z):X\to \mathbb {R} \cup \{+\infty \}}$ and define the set

${\displaystyle F(z):=\left\{y\in Y:G_{z}(y)\leq f(z)\right\}=\left\{y\in Y:f(z)+\epsilon d(z,y)\leq f(z)\right\}}$.

It is straightforward to show that for all ${\displaystyle x\in X}$,

1. ${\displaystyle F(x)}$ is closed (because ${\displaystyle G_{x}:=G(x,\cdot ):X\to \mathbb {R} \cup \{+\infty \}}$ is lower semicontinuous);
2. if ${\displaystyle x\not \in \operatorname {dom} f}$ then ${\displaystyle F(x)=X}$;
3. if ${\displaystyle x\in \operatorname {dom} f}$ then ${\displaystyle x\in F(x)\subseteq \operatorname {dom} f}$; in particular, ${\displaystyle x_{0}\in F(x_{0})\subseteq \operatorname {dom} f}$;
4. if ${\displaystyle y\in F(x)}$ then ${\displaystyle F(y)\subseteq F(x)}$.

Let ${\displaystyle s_{0}=\inf _{x\in F(x_{0})}f(x)}$, which is a real number since f was assumed to be bounded below. Pick ${\displaystyle x_{1}\in F\left(x_{0}\right)}$ such that ${\displaystyle f\left(x_{1}\right)<s_{0}+2^{-1}}$. Having defined ${\displaystyle s_{n-1}}$ and ${\displaystyle x_{n}}$, define ${\displaystyle s_{n}:=\inf _{x\in F\left(x_{n}\right)}f(x)}$ and pick ${\displaystyle x_{n+1}\in F\left(x_{n}\right)}$ such that ${\displaystyle f\left(x_{n+1}\right)<s_{n}+2^{-(n+1)}}$.

Observe the following:

• for all ${\displaystyle n\geq 0}$, ${\displaystyle F\left(x_{n+1}\right)\subseteq F\left(x_{n}\right)}$ (because ${\displaystyle x_{n+1}\in F\left(x_{n}\right)}$, where this now implies that ${\displaystyle s_{n+1}\geq s_{n}}$;
• for all ${\displaystyle n\geq 1}$, because ${\displaystyle x_{n+1}\in F\left(x_{n}\right)}$

${\displaystyle \epsilon d\left(x_{n+1},x_{n}\right)\leq f\left(x_{n}\right)-f\left(x_{n+1}\right)\leq f\left(x_{n}\right)-s_{n}\leq f\left(x_{n}\right)-s_{n-1}<2^{-n}}$

It follows that for all ${\displaystyle n,p\geq 1}$, ${\displaystyle d\left(x_{n+1},x_{n}\right)\leq \epsilon 2^{1-n}}$, thus showing that ${\displaystyle \left(x_{n}\right)_{n=0}^{\infty }}$ is a Cauchy sequence. Since X is a complete metric space, there exists some ${\displaystyle v\in X}$ such that ${\displaystyle \left(x_{n}\right)_{n=0}^{\infty }}$ converges to v. Since ${\displaystyle x_{m}\in F\left(x_{n}\right)}$ for all ${\displaystyle m\geq n}$, we have ${\displaystyle v\in \operatorname {cl} F(x_{n})=F(x_{n})}$ for all ${\displaystyle n\geq 0}$, where in particular, ${\displaystyle v\in F(x_{0})}$.

We will show that ${\displaystyle F\left(v\right)=\left\{v\right\}}$ from which the conclusion of the theorem will follow. Let ${\displaystyle x\in F(v)}$ and note that since ${\displaystyle x\in F(x_{n})}$ for all ${\displaystyle n\geq 0}$, we have as above that ${\displaystyle \epsilon d\left(x,x_{n}\right)\leq 2^{-n}}$ and note that this implies that ${\displaystyle \left(x_{n}\right)_{n=0}^{\infty }}$ converges to x. Since the limit of ${\displaystyle \left(x_{n}\right)_{n=0}^{\infty }}$ is unique, we must have ${\displaystyle x=v}$. Thus ${\displaystyle F\left(v\right)=\left\{v\right\}}$, as desired. Q.E.D.

Corollary:[8] Let (X, d) be a complete metric space, and let f: X → R ∪ {+∞} be a lower semicontinuous functional on X that is bounded below and not identically equal to +∞. Fix ε > 0 and a point ${\displaystyle x_{0}}$ ∈ X such that

${\displaystyle f\left(x_{0}\right)\leq \varepsilon +\inf _{x\in X}f(x).}$

Then, for every λ > 0, there exists a point v ∈ X such that

${\displaystyle f(v)\leq f\left(x_{0}\right),}$

${\displaystyle d\left(x_{0},v\right)\leq \lambda ,}$

and, for all x ≠ v,

${\displaystyle f(x)>f(v)-{\frac {\varepsilon }{\lambda }}d(v,x).}$

Note that a good compromise is to take ${\displaystyle \lambda$ :={\sqrt {\epsilon }}} in the preceding result.[8]