Ekeland's variational principle

Ekeland's variational principle

Preliminary definitions

A function ${\displaystyle f:X\to \mathbb{R}\cup \{-\mathrm{\infty },+\mathrm{\infty }\}}$ valued in the extended real numbers ${\displaystyle \mathbb{R}\cup \{-\mathrm{\infty },+\mathrm{\infty }\}=[-\mathrm{\infty },+\mathrm{\infty }]}$ is said to be bounded below if ${\displaystyle \underset{}{inf}f(X)=\underset{x\in X}{inf}f(x)>-\mathrm{\infty }}$ and it is called proper if it has a non-empty effective domain, which by definition is the set $${\displaystyle \mathrm{dom}f\stackrel{\text{def}}{=}\{x\in X:f(x)\ne +\mathrm{\infty }\},}$$ and it is never equal to ${\displaystyle -\mathrm{\infty }.}$ In other words, a map is proper if is valued in ${\displaystyle \mathbb{R}\cup \{+\mathrm{\infty }\}}$ and not identically ${\displaystyle +\mathrm{\infty }.}$ The map ${\displaystyle f}$ is proper and bounded below if and only if ${\displaystyle -\mathrm{\infty }<\underset{}{inf}f(X)\ne +\mathrm{\infty },}$ or equivalently, if and only if ${\displaystyle \underset{}{inf}f(X)\in \mathbb{R}.}$

A function ${\displaystyle f:X\to [-\mathrm{\infty },+\mathrm{\infty }]}$ is lower semicontinuous at a given ${\displaystyle x_0\in X}$ if for every real ${\displaystyle y<f\left(x_0\right)}$ there exists a neighborhood ${\displaystyle U}$ of ${\displaystyle x_0}$ such that ${\displaystyle f(u)>y}$ for all ${\displaystyle u\in U.}$ A function is called lower semicontinuous if it is lower semicontinuous at every point of ${\displaystyle X,}$ which happens if and only if ${\displaystyle \{x\in X:f(x)>y\}}$ is an open set for every ${\displaystyle y\in \mathbb{R},}$ or equivalently, if and only if all of its lower level sets ${\displaystyle \{x\in X:f(x)\le y\}}$ are closed.

Statement of the theorem

Ekeland's variational principle — Let ${\displaystyle (X,d)}$ be a complete metric space and let ${\displaystyle f:X\to \mathbb{R}\cup \{+\mathrm{\infty }\}}$ be a proper lower semicontinuous function that is bounded below (so ${\displaystyle \underset{}{inf}f(X)\in \mathbb{R}}$). Pick ${\displaystyle x_0\in X}$ such that ${\displaystyle f(x_0)\in \mathbb{R}}$ (or equivalently, ${\displaystyle f(x_0)\ne +\mathrm{\infty }}$) and fix any real ${\displaystyle \epsilon >0.}$ There exists some ${\displaystyle v\in X}$ such that $${\displaystyle f(v)\le f\left(x_0\right)-\epsilon d\left(x_0,v\right)}$$ and for every ${\displaystyle x\in X}$ other than ${\displaystyle v}$ (that is, ${\displaystyle x\ne v}$), $${\displaystyle f(v)<f(x)+\epsilon d(v,x).}$$

Proof

Define a function ${\displaystyle G:X\times X\to \mathbb{R}\cup \{+\mathrm{\infty }\}}$ by $${\displaystyle G(x,y)\stackrel{\text{def}}{=}f(x)+\epsilon d(x,y)}$$ which is lower semicontinuous because it is the sum of the lower semicontinuous function ${\displaystyle f}$ and the continuous function ${\displaystyle (x,y)\mapsto \epsilon d(x,y).}$ Given ${\displaystyle z\in X,}$ denote the functions with one coordinate fixed at ${\displaystyle z}$ by $${\displaystyle G_z\stackrel{\text{def}}{=}G(z,\cdot ):X\to \mathbb{R}\cup \{+\mathrm{\infty }\}\text{ and }}$$ $${\displaystyle G^z\stackrel{\text{def}}{=}G(\cdot ,z):X\to \mathbb{R}\cup \{+\mathrm{\infty }\}}$$ and define the set $${\displaystyle F(z)\stackrel{\text{def}}{=}\left\{y\in X:G^z(y)\le f(z)\right\}=\{y\in X:f(y)+\epsilon d(y,z)\le f(z)\},}$$ which is not empty since ${\displaystyle z\in F(z).}$ An element ${\displaystyle v\in X}$ satisfies the conclusion of this theorem if and only if ${\displaystyle F(v)=\{v\}.}$ It remains to find such an element.

It may be verified that for every ${\displaystyle x\in X,}$

1. ${\displaystyle F(x)}$ is closed (because ${\displaystyle G^x\stackrel{\text{def}}{=}G(\cdot ,x):X\to \mathbb{R}\cup \{+\mathrm{\infty }\}}$ is lower semicontinuous);
2. if ${\displaystyle x\notin \mathrm{dom}f}$ then ${\displaystyle F(x)=X;}$
3. if ${\displaystyle x\in \mathrm{dom}f}$ then ${\displaystyle x\in F(x)\subseteq \mathrm{dom}f;}$ in particular, ${\displaystyle x_0\in F\left(x_0\right)\subseteq \mathrm{dom}f;}$
4. if ${\displaystyle y\in F(x)}$ then ${\displaystyle F(y)\subseteq F(x).}$

Let ${\displaystyle s_0=\underset{x\in F\left(x_0\right)}{inf}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\stackrel{\text{def}}{=}\underset{x\in F\left(x_n\right)}{inf}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)}.}$ For any ${\displaystyle n\ge 0,}$ ${\displaystyle x_{n+1}\in F\left(x_n\right)}$ guarantees that ${\displaystyle s_n\le f\left(x_{n+1}\right)}$ and ${\displaystyle F\left(x_{n+1}\right)\subseteq F\left(x_n\right),}$ which in turn implies ${\displaystyle s_{n+1}\ge s_n}$ and thus also $${\displaystyle f\left(x_{n+2}\right)\ge s_{n+1}\ge s_n.}$$ So if ${\displaystyle n\ge 1}$ then ${\displaystyle x_{n+1}\in F\left(x_n\right)\stackrel{\text{def}}{=}\left\{y\in X:f(y)+\epsilon d\left(y,x_n\right)\le f\left(x_n\right)\right\}}$ and ${\displaystyle f\left(x_{n+1}\right)\ge s_{n-1},}$ which guarantee $${\displaystyle \epsilon d\left(x_{n+1},x_n\right)\le f\left(x_n\right)-f\left(x_{n+1}\right)\le f\left(x_n\right)-s_{n-1}<\frac{1}{2^n}.}$$

It follows that for all positive integers ${\displaystyle n,p\ge 1,}$ $${\displaystyle d\left(x_{n+p},x_n\right)\le 2\frac{{\epsilon }^{-1}}{2^n},}$$ which proves that ${\displaystyle x_{\bullet }:={\left(x_n\right)}_{n=0}^{\mathrm{\infty }}}$ is a Cauchy sequence. Because ${\displaystyle X}$ is a complete metric space, there exists some ${\displaystyle v\in X}$ such that ${\displaystyle x_{\bullet }}$ converges to ${\displaystyle v.}$ For any ${\displaystyle n\ge 0,}$ since ${\displaystyle F\left(x_n\right)}$ is a closed set that contain the sequence ${\displaystyle x_n,x_{n+1},x_{n+2},\dots ,}$ it must also contain this sequence's limit, which is ${\displaystyle v;}$ thus ${\displaystyle v\in F\left(x_n\right)}$ and in particular, ${\displaystyle v\in F\left(x_0\right).}$

The theorem will follow once it is shown that ${\displaystyle F(v)=\{v\}.}$ So let ${\displaystyle x\in F(v)}$ and it remains to show ${\displaystyle x=v.}$ Because ${\displaystyle x\in F\left(x_n\right)}$ for all ${\displaystyle n\ge 0,}$ it follows as above that ${\displaystyle \epsilon d\left(x,x_n\right)\le 2^{-n},}$ which implies that ${\displaystyle x_{\bullet }}$ converges to ${\displaystyle x.}$ Because ${\displaystyle x_{\bullet }}$ also converges to ${\displaystyle v}$ and limits in metric spaces are unique, ${\displaystyle x=v.}$ ${\displaystyle ◼}$ Q.E.D.

For example, if ${\displaystyle f}$ and ${\displaystyle (X,d)}$ are as in the theorem's statement and if ${\displaystyle x_0\in X}$ happens to be a global minimum point of ${\displaystyle f,}$ then the vector ${\displaystyle v}$ from the theorem's conclusion is ${\displaystyle v:=x_0.}$

Corollaries

Corollary — Let ${\displaystyle (X,d)}$ be a complete metric space, and let ${\displaystyle f:X\to \mathbb{R}\cup \{+\mathrm{\infty }\}}$ be a lower semicontinuous functional on ${\displaystyle X}$ that is bounded below and not identically equal to ${\displaystyle +\mathrm{\infty }.}$ Fix ${\displaystyle \epsilon >0}$ and a point ${\displaystyle x_0\in X}$ such that $${\displaystyle f\left(x_0\right)\le \epsilon +\underset{x\in X}{inf}f(x).}$$ Then, for every ${\displaystyle \lambda >0,}$ there exists a point ${\displaystyle v\in X}$ such that $${\displaystyle f(v)\le f\left(x_0\right),}$$ $${\displaystyle d\left(x_0,v\right)\le \lambda ,}$$ and, for all ${\displaystyle x\ne v,}$ $${\displaystyle f(x)+\frac{\epsilon }{\lambda }d(v,x)>f(v).}$$

The principle could be thought of as follows: For any point ${\displaystyle x_0}$ which nearly realizes the infimum, there exists another point ${\displaystyle v}$, which is at least as good as ${\displaystyle x_0}$, it is close to ${\displaystyle x_0}$ and the perturbed function, ${\displaystyle f(x)+\frac{\epsilon }{\lambda }d(v,x)}$, has unique minimum at ${\displaystyle v}$. A good compromise is to take ${\displaystyle \lambda :=\sqrt{\epsilon }}$ in the preceding result.