Ekeland's variational principle

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

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

${\displaystyle f}$

${\displaystyle (x,y)\mapsto \epsilon \;d(x,y).}$

${\displaystyle z\in X,}$

$${\displaystyle G_{z}:=G(z,\cdot ):X\to \mathbb {R} \cup \{+\infty \}\qquad {\text{ and }}\qquad G^{z}:=G(\cdot ,z):X\to \mathbb {R} \cup \{+\infty \}}$$

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

It may be verified 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\left(x_{0}\right)\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\left(x_{0}\right)}f(x),}$ which is a real number because ${\displaystyle 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},}$ let

$${\displaystyle s_{n}:=\inf _{x\in F\left(x_{n}\right)}f(x)}$$

${\displaystyle x_{n+1}\in F\left(x_{n}\right)}$

${\displaystyle f\left(x_{n+1}\right)<s_{n}+2^{-(n+1)}.}$

These sequences have the following properties:

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

${\displaystyle x_{\bullet }:=\left(x_{n}\right)_{n=0}^{\infty }}$

${\displaystyle X}$

${\displaystyle v\in X}$

${\displaystyle x_{\bullet }}$

${\displaystyle v.}$

${\displaystyle x_{m}\in F\left(x_{n}\right)}$

${\displaystyle m\geq n}$

${\displaystyle v\in \operatorname {cl} _{Y}F\left(x_{n}\right)=F\left(x_{n}\right)}$

${\displaystyle n\geq 0,}$

${\displaystyle v\in F\left(x_{0}\right).}$

The conclusion of the theorem will follow once it is shown that ${\displaystyle F(v)=\{v\}.}$ So let ${\displaystyle x\in F(v).}$ Because ${\displaystyle x\in F\left(x_{n}\right)}$ for all ${\displaystyle n\geq 0,}$ it follows as above that ${\displaystyle \epsilon \;d\left(x,x_{n}\right)\leq 2^{-n},}$ which implies that ${\displaystyle x_{\bullet }}$ converges to ${\displaystyle x.}$ Since the limit of ${\displaystyle x_{\bullet }}$ is unique, it follows that ${\displaystyle x=v.}$ Thus ${\displaystyle F(v)=\{v\},}$ as desired. ${\displaystyle \blacksquare }$