Ekeland's variational principle

In mathematical analysis, Ekeland's variational principle, discovered by Ivar Ekeland, ^{[1] [2] [3]} 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. ^[4]

The principle has been shown to be equivalent to completeness of metric spaces. ^[5] 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. ^{[4] [6]}

History

Ekeland was associated with the Paris Dauphine University when he proposed this theorem. ^[1]

Ekeland's variational principle

Preliminary definitions

A function ${\displaystyle f:X\to \mathbb {R} \cup \{-\infty ,+\infty \}}$ valued in the extended real numbers ${\displaystyle \mathbb {R} \cup \{-\infty ,+\infty \}=[-\infty ,+\infty ]}$ is said to be bounded below if ${\displaystyle \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

$${\displaystyle \operatorname {dom} f~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\{x\in X:f(x)\neq +\infty \},}$$

and it is never equal to ${\displaystyle -\infty .}$ In other words, a map is proper if is valued in ${\displaystyle \mathbb {R} \cup \{+\infty \}}$ and not identically ${\displaystyle +\infty .}$ The map ${\displaystyle f}$ is proper and bounded below if and only if ${\displaystyle -\infty <\inf _{}f(X)\neq +\infty ,}$ or equivalently, if and only if ${\displaystyle \inf _{}f(X)\in \mathbb {R} .}$

A function ${\displaystyle f:X\to [-\infty ,+\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)\leq y\}}$ are closed.

Statement of the theorem

Ekeland's variational principle ^[7]  — Let ${\displaystyle (X,d)}$ be a complete metric space and let ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \}}$ be a proper lower semicontinuous function that is bounded below (so ${\displaystyle \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})\neq +\infty }$) and fix any real ${\displaystyle \varepsilon >0.}$ There exists some ${\displaystyle v\in X}$ such that

$${\displaystyle f(v)~\leq ~f\left(x_{0}\right)-\varepsilon \;d\left(x_{0},v\right)}$$

and for every ${\displaystyle x\in X}$ other than ${\displaystyle v}$ (that is, ${\displaystyle x\neq v}$),

$${\displaystyle f(v)~<~f(x)+\varepsilon \;d(v,x).}$$

Proof

Define a function ${\displaystyle G:X\times X\to \mathbb {R} \cup \{+\infty \}}$ by

$${\displaystyle 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 ${\displaystyle f}$ and the continuous function ${\displaystyle (x,y)\mapsto \varepsilon \;d(x,y).}$ Given ${\displaystyle z\in X,}$ denote the functions with one coordinate fixed at ${\displaystyle z}$ by

$${\displaystyle G_{z}~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~G(z,\cdot ):X\to \mathbb {R} \cup \{+\infty \}\;{\text{ and }}}$$

$${\displaystyle G^{z}~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~G(\cdot ,z):X\to \mathbb {R} \cup \{+\infty \}}$$

and define the set

$${\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)\},}$$

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 {\scriptscriptstyle {\text{def}}}{=}}\,G(\cdot ,x):X\to \mathbb {R} \cup \{+\infty \}}$ is lower semicontinuous);
2. if ${\displaystyle x\notin \operatorname {dom} f}$ then ${\displaystyle F(x)=X;}$
3. if ${\displaystyle x\in \operatorname {dom} f}$ then ${\displaystyle x\in F(x)\subseteq \operatorname {dom} f;}$ in particular, ${\displaystyle x_{0}\in F\left(x_{0}\right)\subseteq \operatorname {dom} f;}$
4. if ${\displaystyle y\in F(x)}$ then ${\displaystyle F(y)\subseteq F(x).}$

Let ${\displaystyle s_{0}=\inf _{x\in F\left(x_{0}\right)}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 {\scriptscriptstyle {\text{def}}}{=}}~\inf _{x\in F\left(x_{n}\right)}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\geq 0,}$${\displaystyle x_{n+1}\in F\left(x_{n}\right)}$ guarantees that ${\displaystyle s_{n}\leq 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}\geq s_{n}}$ and thus also

$${\displaystyle f\left(x_{n+2}\right)\geq s_{n+1}\geq s_{n}.}$$

So if ${\displaystyle n\geq 1}$ then ${\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\}}$ and ${\displaystyle f\left(x_{n+1}\right)\geq s_{n-1},}$ which guarantee

$${\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}~<~{\frac {1}{2^{n}}}.}$$

It follows that for all positive integers ${\displaystyle n,p\geq 1,}$

$${\displaystyle d\left(x_{n+p},x_{n}\right)~\leq ~2\;{\frac {\varepsilon ^{-1}}{2^{n}}},}$$

which proves that ${\displaystyle x_{\bullet }:=\left(x_{n}\right)_{n=0}^{\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\geq 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},\ldots ,}$ 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\geq 0,}$ it follows as above that ${\displaystyle \varepsilon \;d\left(x,x_{n}\right)\leq 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 \blacksquare }$ 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 ^[8]  — Let ${\displaystyle (X,d)}$ be a complete metric space, and let ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \}}$ be a lower semicontinuous functional on ${\displaystyle X}$ that is bounded below and not identically equal to ${\displaystyle +\infty .}$ Fix ${\displaystyle \varepsilon >0}$ and a point ${\displaystyle x_{0}\in X}$ such that

$${\displaystyle f\left(x_{0}\right)~\leq ~\varepsilon +\inf _{x\in X}f(x).}$$

Then, for every ${\displaystyle \lambda >0,}$ there exists a point ${\displaystyle v\in X}$ such that

$${\displaystyle f(v)~\leq ~f\left(x_{0}\right),}$$

$${\displaystyle d\left(x_{0},v\right)~\leq ~\lambda ,}$$

and, for all ${\displaystyle x\neq v,}$

$${\displaystyle f(x)+{\frac {\varepsilon }{\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 {\varepsilon }{\lambda }}d(v,x)}$, has unique minimum at ${\displaystyle v}$. A good compromise is to take ${\displaystyle \lambda$ :={\sqrt {\varepsilon }}} in the preceding result. ^[8]

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

References

1. Ekeland, Ivar (1974). "On the variational principle". J. Math. Anal. Appl. 47 (2): 324–353. doi: 10.1016/0022-247X(74)90025-0 . ISSN   0022-247X.
2. 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.
3. Ekeland, Ivar; Temam, Roger (1999). Convex analysis and variational problems. Classics in applied mathematics. Vol. 28 (Corrected reprinting of the (1976) North-Holland ed.). Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). pp. 357–373. ISBN   0-89871-450-8. MR   1727362.
4. Kirk, William A.; Goebel, Kazimierz (1990). Topics in Metric Fixed Point Theory. Cambridge University Press. ISBN   0-521-38289-0.
5. Sullivan, Francis (October 1981). "A characterization of complete metric spaces". Proceedings of the American Mathematical Society. 83 (2): 345–346. doi: 10.1090/S0002-9939-1981-0624927-9 . MR   0624927.
6. Ok, Efe (2007). "D: Continuity I". Real Analysis with Economic Applications (PDF). Princeton University Press. p. 664. ISBN   978-0-691-11768-3 . Retrieved January 31, 2009.
7. Zalinescu 2002, p. 29.
8. Zalinescu 2002, p. 30.

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.