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 [math]\displaystyle{ f : X \to \R \cup \{-\infty, +\infty\} }[/math] valued in the extended real numbers [math]\displaystyle{ \R \cup \{-\infty, +\infty\} = [-\infty, +\infty] }[/math] is said to be bounded below if [math]\displaystyle{ \inf_{} f(X) = \inf_{x \in X} f(x) \gt -\infty }[/math] and it is called proper if it has a non-empty effective domain, which by definition is the set [math]\displaystyle{ \operatorname{dom} f ~\stackrel{\scriptscriptstyle\text{def}}{=}~ \{x \in X : f(x) \neq +\infty\}, }[/math] and it is never equal to [math]\displaystyle{ -\infty. }[/math] In other words, a map is proper if is valued in [math]\displaystyle{ \R \cup \{+\infty\} }[/math] and not identically [math]\displaystyle{ +\infty. }[/math] The map [math]\displaystyle{ f }[/math] is proper and bounded below if and only if [math]\displaystyle{ -\infty \lt \inf_{} f(X) \neq +\infty, }[/math] or equivalently, if and only if [math]\displaystyle{ \inf_{} f(X) \in \R. }[/math]

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

Statement of the theorem

Ekeland's variational principle — Let [math]\displaystyle{ (X, d) }[/math] be a complete metric space and let [math]\displaystyle{ f : X \to \R \cup \{+\infty\} }[/math] be a proper lower semicontinuous function that is bounded below (so [math]\displaystyle{ \inf_{} f(X) \in \R }[/math]). Pick [math]\displaystyle{ x_0 \in X }[/math] such that [math]\displaystyle{ f(x_0) \in \R }[/math] (or equivalently, [math]\displaystyle{ f(x_0) \neq +\infty }[/math]) and fix any real [math]\displaystyle{ \varepsilon \gt 0. }[/math] There exists some [math]\displaystyle{ v \in X }[/math] such that [math]\displaystyle{ f(v) ~\leq~ f\left(x_0\right) - \varepsilon \; d \left(x_0, v\right) }[/math] and for every [math]\displaystyle{ x \in X }[/math] other than [math]\displaystyle{ v }[/math] (that is, [math]\displaystyle{ x \neq v }[/math]), [math]\displaystyle{ f(v) ~\lt ~ f(x) + \varepsilon \; d(v, x). }[/math]

Proof

Define a function [math]\displaystyle{ G : X \times X \to \R \cup \{+\infty\} }[/math] by [math]\displaystyle{ G(x, y) ~\stackrel{\scriptscriptstyle\text{def}}{=}~ f(x) + \varepsilon \; d(x, y) }[/math] which is lower semicontinuous because it is the sum of the lower semicontinuous function [math]\displaystyle{ f }[/math] and the continuous function [math]\displaystyle{ (x, y) \mapsto \varepsilon \; d(x, y). }[/math] Given [math]\displaystyle{ z \in X, }[/math] denote the functions with one coordinate fixed at [math]\displaystyle{ z }[/math] by [math]\displaystyle{ G_z ~\stackrel{\scriptscriptstyle\text{def}}{=}~ G(z, \cdot) : X \to \R \cup \{+\infty\} \; \text{ and } }[/math] [math]\displaystyle{ G^z~ \stackrel{\scriptscriptstyle\text{def}}{=}~ G(\cdot, z) : X \to \R \cup \{+\infty\} }[/math] and define the set [math]\displaystyle{ 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)\}. }[/math] which is not empty since [math]\displaystyle{ z \in F(z). }[/math] An element [math]\displaystyle{ v \in X }[/math] satisfies the conclusion of this theorem if and only if [math]\displaystyle{ F(v) = \{v\}. }[/math] It remains to find such an element.

It may be verified that for every [math]\displaystyle{ x \in X, }[/math]

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

Let [math]\displaystyle{ s_0 = \inf_{x \in F\left(x_0\right)} f(x), }[/math] which is a real number because [math]\displaystyle{ f }[/math] was assumed to be bounded below. Pick [math]\displaystyle{ x_1 \in F\left(x_0\right) }[/math] such that [math]\displaystyle{ f\left(x_1\right) \lt s_0 + 2^{-1}. }[/math] Having defined [math]\displaystyle{ s_{n-1} }[/math] and [math]\displaystyle{ x_n, }[/math] let [math]\displaystyle{ s_n ~\stackrel{\scriptscriptstyle\text{def}}{=}~ \inf_{x \in F\left(x_n\right)} f(x) }[/math] and pick [math]\displaystyle{ x_{n+1} \in F\left(x_n\right) }[/math] such that [math]\displaystyle{ f\left(x_{n+1}\right) \lt s_n + 2^{-(n+1)}. }[/math] For any [math]\displaystyle{ n \geq 0, }[/math] [math]\displaystyle{ x_{n+1} \in F\left(x_n\right) }[/math] guarantees that [math]\displaystyle{ s_n \leq f\left(x_{n+1}\right) }[/math] and [math]\displaystyle{ F\left(x_{n+1}\right) \subseteq F\left(x_n\right), }[/math] which in turn implies [math]\displaystyle{ s_{n+1} \geq s_n }[/math] and thus also [math]\displaystyle{ f\left(x_{n+2}\right) \geq s_{n+1} \geq s_n. }[/math] So if [math]\displaystyle{ n \geq 1 }[/math] then [math]\displaystyle{ 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\} }[/math] and [math]\displaystyle{ f\left(x_{n+1}\right) \geq s_{n-1}, }[/math] which guarantee [math]\displaystyle{ \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} ~\lt ~ \frac{1}{2^n}. }[/math]

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

The theorem will follow once it is shown that [math]\displaystyle{ F(v) = \{v\}. }[/math] So let [math]\displaystyle{ x \in F(v) }[/math] and it remains to show [math]\displaystyle{ x = v. }[/math] Because [math]\displaystyle{ x \in F\left(x_n\right) }[/math] for all [math]\displaystyle{ n \geq 0, }[/math] it follows as above that [math]\displaystyle{ \varepsilon \; d\left(x, x_n\right) \leq 2^{-n}, }[/math] which implies that [math]\displaystyle{ x_{\bull} }[/math] converges to [math]\displaystyle{ x. }[/math] Because [math]\displaystyle{ x_\bull }[/math] also converges to [math]\displaystyle{ v }[/math] and limits in metric spaces are unique, [math]\displaystyle{ x = v. }[/math] [math]\displaystyle{ \blacksquare }[/math] Q.E.D.

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

Corollaries

Corollary — Let [math]\displaystyle{ (X, d) }[/math] be a complete metric space, and let [math]\displaystyle{ f : X \to \R \cup \{+\infty\} }[/math] be a lower semicontinuous functional on [math]\displaystyle{ X }[/math] that is bounded below and not identically equal to [math]\displaystyle{ +\infty. }[/math] Fix [math]\displaystyle{ \varepsilon \gt 0 }[/math] and a point [math]\displaystyle{ x_0 \in X }[/math] such that [math]\displaystyle{ f\left(x_0\right) ~\leq~ \varepsilon + \inf_{x \in X} f(x). }[/math] Then, for every [math]\displaystyle{ \lambda \gt 0, }[/math] there exists a point [math]\displaystyle{ v \in X }[/math] such that [math]\displaystyle{ f(v) ~\leq~ f\left(x_0\right), }[/math] [math]\displaystyle{ d\left(x_0, v\right) ~\leq~ \lambda, }[/math] and, for all [math]\displaystyle{ x \neq v, }[/math] [math]\displaystyle{ f(x)+ \frac{\varepsilon}{\lambda} d(v, x) ~\gt ~ f(v) . }[/math]

The principle could be thought of as follows: For any point [math]\displaystyle{ x_0 }[/math] which nearly realizes the infimum, there exists another point [math]\displaystyle{ v }[/math], which is at least as good as [math]\displaystyle{ x_0 }[/math], it is close to [math]\displaystyle{ x_0 }[/math] and the perturbed function, [math]\displaystyle{ f(x)+\frac{\varepsilon}{\lambda} d(v, x) }[/math], has unique minimum at [math]\displaystyle{ v }[/math]. A good compromise is to take [math]\displaystyle{ \lambda := \sqrt{\varepsilon} }[/math] 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