Ekeland's variational principle

In mathematical analysis, Ekeland's variational principle, discovered by Ivar Ekeland, In proof theory, it is equivalent to Π11CA₀ over RCA₀, i.e. relatively strong.

It also leads to a quick proof of the Caristi fixed point theorem.

History

Ekeland was associated with the Paris Dauphine University when he proposed this theorem.

Ekeland's variational principle

Preliminary definitions

A function $f:X\to \mathbb{ℝ}\cup \{-\mathrm{\infty },+\mathrm{\infty }\}$ valued in the extended real numbers $\mathbb{ℝ}\cup \{-\mathrm{\infty },+\mathrm{\infty }\}=[-\mathrm{\infty },+\mathrm{\infty }]$ is said to be bounded below if $\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 $$\mathrm{dom}f\stackrel{\text{def}}{=}\{x\in X:f(x)\ne +\mathrm{\infty }\},$$ and it is never equal to $-\mathrm{\infty }.$ In other words, a map is proper if is valued in $\mathbb{ℝ}\cup \{+\mathrm{\infty }\}$ and not identically $+\mathrm{\infty }.$ The map $f$ is proper and bounded below if and only if $-\mathrm{\infty }<\underset{}{\inf }f(X)\ne +\mathrm{\infty },$ or equivalently, if and only if $\underset{}{\inf }f(X)\in \mathbb{ℝ}.$

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

Statement of the theorem

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

Proof

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

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

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

Let $s_0=\underset{x\in F\left(x_0\right)}{\inf }f(x),$ which is a real number because $f$ was assumed to be bounded below. Pick $x_1\in F\left(x_0\right)$ such that $f\left(x_1\right)<s_0+2^{-1}.$ Having defined $s_{n-1}$ and $x_n,$ let $$s_n\stackrel{\text{def}}{=}\underset{x\in F\left(x_n\right)}{\inf }f(x)$$ and pick $x_{n+1}\in F\left(x_n\right)$ such that $f\left(x_{n+1}\right)<s_n+2^{-(n+1)}.$ For any $n\ge 0,$ $x_{n+1}\in F\left(x_n\right)$ guarantees that $s_n\le f\left(x_{n+1}\right)$ and $F\left(x_{n+1}\right)\subseteq F\left(x_n\right),$ which in turn implies $s_{n+1}\ge s_n$ and thus also $$f\left(x_{n+2}\right)\ge s_{n+1}\ge s_n.$$ So if $n\ge 1$ then $x_{n+1}\in F\left(x_n\right)\stackrel{\text{def}}{=}\{y\in X:f(y)+\epsilon d(y,x_n)\le f\left(x_n\right)\}$ and $f\left(x_{n+1}\right)\ge s_{n-1},$ which guarantee $$\epsilon d(x_{n+1},x_n)\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 $n,p\ge 1,$ $$d(x_{n+p},x_n)\le 2\frac{{\epsilon }^{-1}}{2^n},$$ which proves that $x_{\bullet }:={\left(x_n\right)}_{n=0}^{\mathrm{\infty }}$ is a Cauchy sequence. Because $X$ is a complete metric space, there exists some $v\in X$ such that $x_{\bullet }$ converges to $v.$ For any $n\ge 0,$ since $F\left(x_n\right)$ is a closed set that contain the sequence $x_n,x_{n+1},x_{n+2},\dots ,$ it must also contain this sequence's limit, which is $v;$ thus $v\in F\left(x_n\right)$ and in particular, $v\in F\left(x_0\right).$

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

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

Corollaries

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

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

See also

• Caristi fixed-point theorem
• Physics:Variational principle – Scientific principles enabling the use of the calculus of variations

Bibliography

• Ekeland, Ivar (1979). "Nonconvex minimization problems". Bulletin of the American Mathematical Society. New Series 1 (3): 443–474. doi:10.1090/S0273-0979-1979-14595-6. 
• Kirk, William A.; Goebel, Kazimierz (1990). Topics in Metric Fixed Point Theory. Cambridge University Press. ISBN 0-521-38289-0. 
• Zalinescu, C (2002). Convex analysis in general vector spaces. River Edge, N.J. London: World Scientific. ISBN 981-238-067-1. OCLC 285163112. 
• Template:Zălinescu Convex Analysis in General Vector Spaces 2002