Ekeland's variational principle

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 \R \cup {-\infty, +\infty} valued in the extended real numbers \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 **** 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 \R \cup {+\infty} and not identically +\infty. The map f is proper and bounded below if and only if -\infty or equivalently, if and only if \inf_{} f(X) \in \R.

A function f :X \to [-\infty, +\infty] is lower semicontinuous at a given x_0 \in X if for every real y 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 \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

Let (X, d) be a complete metric space and let f : X \to \R \cup {+\infty} be a proper lower semicontinuous function that is bounded below (so \inf_{} f(X) \in \R). Pick x_0 \in X such that f(x_0) \in \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) ~

Define a function G : X \times X \to \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 \R \cup {+\infty} ; \text{ and } G^z~ \stackrel{\scriptscriptstyle\text{def}}{=}~ G(\cdot, z) : X \to \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 \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) 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) 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} ~

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_\bull := \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\bull 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_{\bull} converges to x. Because x_\bull 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

Let (X, d) be a complete metric space, and let f : X \to \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.

References

Bibliography

References

1. Ekeland, Ivar. (1979). "Nonconvex minimization problems". Bulletin of the American Mathematical Society.
2. (1999). "Convex analysis and variational problems". Society for Industrial and Applied Mathematics (SIAM).
3. Sullivan, Francis. (October 1981). "A characterization of complete metric spaces". Proceedings of the American Mathematical Society.
4. (1990). "Topics in Metric Fixed Point Theory". Cambridge University Press.
5. Ok, Efe. (2007). "Real Analysis with Economic Applications". Princeton University Press.