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 Π1
1CA0 over RCA0, 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
valued in the extended real numbers
is said to be bounded below if
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 \},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/979cc30070962731643344c412e507458354cecd)
and it is never equal to
![{\displaystyle -\infty .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bafcc356687548ee27fc561ccba697aaec95cb97)
In other words, a map is
proper if is valued in
![{\displaystyle \mathbb {R} \cup \{+\infty \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f5ee15b830c1d223d89dd5c92b99f213a8d88ba)
and not identically
![{\displaystyle +\infty .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/994b58d7a1a53febce2005c1f8cd1697c3458677)
The map
![{\displaystyle f}](https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61)
is proper and bounded below if and only if
![{\displaystyle -\infty <\inf _{}f(X)\neq +\infty ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8417b47d9371ce5da67bf4df5b1d0e6df88ec10e)
or equivalently, if and only if
A function
is lower semicontinuous at a given
if for every real
there exists a neighborhood
of
such that
for all
A function is called lower semicontinuous if it is lower semicontinuous at every point of
which happens if and only if
is an open set for every
or equivalently, if and only if all of its lower level sets
are closed.
Statement of the theorem
Proof Define a function
by
![{\displaystyle G(x,y)~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~f(x)+\varepsilon \;d(x,y)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a0bc30a275cb60a695cf933568b21b5f16052ed)
which is lower semicontinuous because it is the sum of the lower semicontinuous function
![{\displaystyle f}](https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61)
and the continuous function
![{\displaystyle (x,y)\mapsto \varepsilon \;d(x,y).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5eb210471877a4799574eca0e9a28cf7bf4536ec)
Given
![{\displaystyle z\in X,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bebbe97b6551af587e1751cca54d9c10bcb09ab)
denote the functions with one coordinate fixed at
![{\displaystyle z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf368e72c009decd9b6686ee84a375632e11de98)
by
![{\displaystyle G_{z}~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~G(z,\cdot ):X\to \mathbb {R} \cup \{+\infty \}\;{\text{ and }}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b83d332f04e2aa8c1f63abbda24b3b93d04d80c5)
![{\displaystyle G^{z}~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~G(\cdot ,z):X\to \mathbb {R} \cup \{+\infty \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/abe42d58e9568f9afb68034de224b95c0dab0ee0)
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)\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7936053241fcd312d72af772435ea60b942aa7bf)
which is not empty since
![{\displaystyle z\in F(z).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/faa59e7beda7275719aed12ee081e33bdae6acab)
An element
![{\displaystyle v\in X}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca4e5cf826d2f1533fb0bc987a41d5f68f7b0477)
satisfies the conclusion of this theorem if and only if
![{\displaystyle F(v)=\{v\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5123d82a5974f19d9a47811c01c83de12037d50b)
It remains to find such an element.
It may be verified that for every
is closed (because
is lower semicontinuous); - if
then ![{\displaystyle F(x)=X;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4bdd2993ad1afe000ee6a1a56adef487f16ba1b8)
- if
then
in particular, ![{\displaystyle x_{0}\in F\left(x_{0}\right)\subseteq \operatorname {dom} f;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19443ea35090a82092e7102ad920ccd3e4c62ba5)
- if
then ![{\displaystyle F(y)\subseteq F(x).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49282c085a6a18740615840b3ef07fbc58010f2c)
Let
which is a real number because
was assumed to be bounded below. Pick
such that
Having defined
and
let
![{\displaystyle s_{n}~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\inf _{x\in F\left(x_{n}\right)}f(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b7d7b4e9895817d8431eb81879f6316f6688c12)
and pick
![{\displaystyle x_{n+1}\in F\left(x_{n}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9cc8926a7e74d3bd5de2c43636c3f1afbafd54fd)
such that
![{\displaystyle f\left(x_{n+1}\right)<s_{n}+2^{-(n+1)}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cee6028853e87fd0c05ec1344863abc2802fc26)
For any
![{\displaystyle x_{n+1}\in F\left(x_{n}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9cc8926a7e74d3bd5de2c43636c3f1afbafd54fd)
guarantees that
![{\displaystyle s_{n}\leq f\left(x_{n+1}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05903f1d588ca83217567f5d5aa18ad7e8bb2728)
and
![{\displaystyle F\left(x_{n+1}\right)\subseteq F\left(x_{n}\right),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6793d117b2d9f96010fe4d1de81faaf614060e51)
which in turn implies
![{\displaystyle s_{n+1}\geq s_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/67f2a3ee460a1818441a1fda02c4d45d1cf9b130)
and thus also
![{\displaystyle f\left(x_{n+2}\right)\geq s_{n+1}\geq s_{n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/963b2e48c3be6701368433414e27841800e2004c)
So if
![{\displaystyle n\geq 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8ce9ce38d06f6bf5a3fe063118c09c2b6202bfe)
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\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab4c6c52be2742b2daa6d5cfe647aa28c719d042)
and
![{\displaystyle f\left(x_{n+1}\right)\geq s_{n-1},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eccfe06215e55ae51576ceab12b7e2054b6cc339)
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}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/64a388b8763fbe28d7bb79cad4cfcdfb9076d623)
It follows that for all positive integers
![{\displaystyle d\left(x_{n+p},x_{n}\right)~\leq ~2\;{\frac {\varepsilon ^{-1}}{2^{n}}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/046b5ee0833b2f3aeaf940689c7dbfdc6e114841)
which proves that
![{\displaystyle x_{\bullet }:=\left(x_{n}\right)_{n=0}^{\infty }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1db2d4d413922e0022f9365602716f2a3e4c0a43)
is a Cauchy sequence. Because
![{\displaystyle X}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab)
is a complete metric space, there exists some
![{\displaystyle v\in X}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca4e5cf826d2f1533fb0bc987a41d5f68f7b0477)
such that
![{\displaystyle x_{\bullet }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61fc088fd942f558f51cd6ff44fdc6498e024ae7)
converges to
![{\displaystyle v.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bb7b87f7afb1452b9d0e287f8ef746a9912c8333)
For any
![{\displaystyle n\geq 0,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d02d53378dc43f8e0ad4cd7634d2292118567321)
since
![{\displaystyle F\left(x_{n}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2bd10a36301269c7fb29dd18f7e3e7d655b835b5)
is a closed set that contain the sequence
![{\displaystyle x_{n},x_{n+1},x_{n+2},\ldots ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e61d599de8fa077176aae8b63b961ebb84ddb0e)
it must also contain this sequence's limit, which is
![{\displaystyle v;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/732399247c15284b9bd7c21f235e2d7a6766c190)
thus
![{\displaystyle v\in F\left(x_{n}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c279cfa70bcc72aa73f0b8972697c80f51b86111)
and in particular,
The theorem will follow once it is shown that
So let
and it remains to show
Because
for all
it follows as above that
which implies that
converges to
Because
also converges to
and limits in metric spaces are unique,
Q.E.D.
For example, if
and
are as in the theorem's statement and if
happens to be a global minimum point of
then the vector
from the theorem's conclusion is
Corollaries
Corollary — Let
be a complete metric space, and let
be a lower semicontinuous functional on
that is bounded below and not identically equal to
Fix
and a point
such that
![{\displaystyle f\left(x_{0}\right)~\leq ~\varepsilon +\inf _{x\in X}f(x).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b490025e2ec731f2986d3c1f9ed55d2c6776f865)
Then, for every
![{\displaystyle \lambda >0,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6f8621a2fb5c17fbf295fa1bac9b41c1aba3c4f0)
there exists a point
![{\displaystyle v\in X}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca4e5cf826d2f1533fb0bc987a41d5f68f7b0477)
such that
![{\displaystyle f(v)~\leq ~f\left(x_{0}\right),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5f9503eafcb9c0abf974ffa1d05e63f9d5ef4d9)
![{\displaystyle d\left(x_{0},v\right)~\leq ~\lambda ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df26fda65dcf6948bd7fd2515107b81a61f65798)
and, for all
![{\displaystyle f(x)+{\frac {\varepsilon }{\lambda }}d(v,x)~>~f(v).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c9fce9765dba73bd50c125c108d5f570a75fd57)
The principle could be thought of as follows: For any point
which nearly realizes the infimum, there exists another point
, which is at least as good as
, it is close to
and the perturbed function,
, has unique minimum at
. A good compromise is to take
in the preceding result.
See also
References
- ^ a b 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.
- ^ 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.
- ^ 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.
- ^ a b Kirk, William A.; Goebel, Kazimierz (1990). Topics in Metric Fixed Point Theory. Cambridge University Press. ISBN 0-521-38289-0.
- ^ 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.
- ^ 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.
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.
Basic concepts | |
---|
Topics (list) | |
---|
Maps | |
---|
Main results (list) | |
---|
Sets | |
---|
Series | |
---|
Duality | |
---|
Applications and related | |
---|
|
---|
Spaces | |
---|
Theorems | |
---|
Operators | |
---|
Algebras | |
---|
Open problems | |
---|
Applications | |
---|
Advanced topics | |
---|
Category |