Ekeland's variational principle

In mathematical analysis, Ekeland's variational principle, discovered by Ivar Ekeland, is a theorem that asserts that there exist nearly optimal solutions to some optimization problems.

Ekeland's principle can be used when the lower level set of a minimization problems is not compact, so that the Bolzano–Weierstrass theorem cannot be applied. The principle relies on the completeness of the metric space.

The principle has been shown to be equivalent to completeness of metric spaces. In proof theory, it is equivalent to Π¹
₁CA₀ 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 {R} \cup \{-\infty ,+\infty \}$ valued in the extended real numbers $\mathbb {R} \cup \{-\infty ,+\infty \}=[-\infty ,+\infty ]$ is said to be bounded below if $\inf _{}f(X)=\inf _{x\in X}f(x)>-\infty$ and it is called proper if it has a non-empty effective domain, which by definition is the set $$\operatorname {dom} f~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\{x\in X:f(x)\neq +\infty \},$$ and it is never equal to $-\infty .$ In other words, a map is proper if is valued in $\mathbb {R} \cup \{+\infty \}$ and not identically $+\infty .$ The map $f$ is proper and bounded below if and only if $-\infty <\inf _{}f(X)\neq +\infty ,$ or equivalently, if and only if $\inf _{}f(X)\in \mathbb {R} .$

A function $f:X\to [-\infty ,+\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 {R} ,$ or equivalently, if and only if all of its lower level sets $\{x\in X:~f(x)\leq 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 {R} \cup \{+\infty \}$ be a proper lower semicontinuous function that is bounded below (so $\inf _{}f(X)\in \mathbb {R}$). Pick $x_{0}\in X$ such that $f(x_{0})\in \mathbb {R}$ (or equivalently, $f(x_{0})\neq +\infty$) and fix any real $\varepsilon >0.$ There exists some $v\in X$ such that $$f(v)~\leq ~f\left(x_{0}\right)-\varepsilon \;d\left(x_{0},v\right)$$ and for every $x\in X$ other than $v$ (that is, $x\neq v$), $$f(v)~<~f(x)+\varepsilon \;d(v,x).$$

Proof

Define a function $G:X\times X\to \mathbb {R} \cup \{+\infty \}$ by $$G(x,y)~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~f(x)+\varepsilon \;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 \varepsilon \;d(x,y).$ Given $z\in X,$ denote the functions with one coordinate fixed at $z$ by $$G_{z}~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~G(z,\cdot ):X\to \mathbb {R} \cup \{+\infty \}\;{\text{ and }}$$ $$G^{z}~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~G(\cdot ,z):X\to \mathbb {R} \cup \{+\infty \}$$ and define the set $$F(z)~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\left\{y\in X:G^{z}(y)\leq f(z)\right\}~=~\{y\in X:f(y)+\varepsilon \;d(y,z)\leq 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 {\scriptscriptstyle {\text{def}}}{=}}\,G(\cdot ,x):X\to \mathbb {R} \cup \{+\infty \}$ is lower semicontinuous);
2. if $x\notin \operatorname {dom} f$ then $F(x)=X;$
3. if $x\in \operatorname {dom} f$ then $x\in F(x)\subseteq \operatorname {dom} f;$ in particular, $x_{0}\in F\left(x_{0}\right)\subseteq \operatorname {dom} f;$
4. if $y\in F(x)$ then $F(y)\subseteq F(x).$

Let $s_{0}=\inf _{x\in F\left(x_{0}\right)}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 {\scriptscriptstyle {\text{def}}}{=}}~\inf _{x\in F\left(x_{n}\right)}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\geq 0,$ $x_{n+1}\in F\left(x_{n}\right)$ guarantees that $s_{n}\leq 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}\geq s_{n}$ and thus also $$f\left(x_{n+2}\right)\geq s_{n+1}\geq s_{n}.$$ So if $n\geq 1$ then $x_{n+1}\in F\left(x_{n}\right){\stackrel {\scriptscriptstyle {\text{def}}}{=}}\left\{y\in X:f(y)+\varepsilon \;d\left(y,x_{n}\right)\leq f\left(x_{n}\right)\right\}$ and $f\left(x_{n+1}\right)\geq s_{n-1},$ which guarantee $$\varepsilon \;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-1}~<~{\frac {1}{2^{n}}}.$$

It follows that for all positive integers $n,p\geq 1,$ $$d\left(x_{n+p},x_{n}\right)~\leq ~2\;{\frac {\varepsilon ^{-1}}{2^{n}}},$$ which proves that $x_{\bullet }:=\left(x_{n}\right)_{n=0}^{\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\geq 0,$ since $F\left(x_{n}\right)$ is a closed set that contain the sequence $x_{n},x_{n+1},x_{n+2},\ldots ,$ 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\geq 0,$ it follows as above that $\varepsilon \;d\left(x,x_{n}\right)\leq 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.$ $\blacksquare$ 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 {R} \cup \{+\infty \}$ be a lower semicontinuous functional on $X$ that is bounded below and not identically equal to $+\infty .$ Fix $\varepsilon >0$ and a point $x_{0}\in X$ such that $$f\left(x_{0}\right)~\leq ~\varepsilon +\inf _{x\in X}f(x).$$ Then, for every $\lambda >0,$ there exists a point $v\in X$ such that $$f(v)~\leq ~f\left(x_{0}\right),$$ $$d\left(x_{0},v\right)~\leq ~\lambda ,$$ and, for all $x\neq v,$ $$f(x)+{\frac {\varepsilon }{\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 {\varepsilon }{\lambda }}d(v,x)$, has unique minimum at $v$. A good compromise is to take $\lambda :={\sqrt {\varepsilon }}$ in the preceding result.

See also

• Caristi fixed-point theorem
• Fenchel-Young inequality – Generalization of the Legendre transformationPages displaying short descriptions of redirect targets
• 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. MR 0526967.
• 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.
• Zălinescu, Constantin (30 July 2002). Convex Analysis in General Vector Spaces. River Edge, N.J. London: World Scientific Publishing. ISBN 978-981-4488-15-0. MR 1921556. OCLC 285163112 – via Internet Archive.