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
The principle has been shown to be equivalent to completeness of metric spaces.[5]
In proof theory , it is equivalent to Π1 1 CA0 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
f
:
X
→
R
∪
{
−
∞
,
+
∞
}
{\displaystyle f:X\to \mathbb {R} \cup \{-\infty ,+\infty \}}
valued in the
extended real numbers
R
∪
{
−
∞
,
+
∞
}
=
[
−
∞
,
+
∞
]
{\displaystyle \mathbb {R} \cup \{-\infty ,+\infty \}=[-\infty ,+\infty ]}
is said to be
bounded below if
inf
f
(
X
)
=
inf
x
∈
X
f
(
x
)
>
−
∞
{\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
dom
f
=
def
{
x
∈
X
:
f
(
x
)
≠
+
∞
}
,
{\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
R
∪
{
+
∞
}
{\displaystyle \mathbb {R} \cup \{+\infty \}}
and not identically
+
∞
.
{\displaystyle +\infty .}
The map
f
{\displaystyle f}
is proper and bounded below if and only if
−
∞
<
inf
f
(
X
)
≠
+
∞
,
{\displaystyle -\infty <\inf _{}f(X)\neq +\infty ,}
or equivalently, if and only if
inf
f
(
X
)
∈
R
.
{\displaystyle \inf _{}f(X)\in \mathbb {R} .}
A function
f
:
X
→
[
−
∞
,
+
∞
]
{\displaystyle f:X\to [-\infty ,+\infty ]}
is lower semicontinuous
at a given
x
0
∈
X
{\displaystyle x_{0}\in X}
if for every real
y
<
f
(
x
0
)
{\displaystyle y<f\left(x_{0}\right)}
there exists a
neighborhood
U
{\displaystyle U}
of
x
0
{\displaystyle x_{0}}
such that
f
(
u
)
>
y
{\displaystyle f(u)>y}
for all
u
∈
U
.
{\displaystyle u\in U.}
A function is called
lower semicontinuous
if it is lower semicontinuous at every point of
X
,
{\displaystyle X,}
which happens if and only if
{
x
∈
X
:
f
(
x
)
>
y
}
{\displaystyle \{x\in X:~f(x)>y\}}
is an
open set for every
y
∈
R
,
{\displaystyle y\in \mathbb {R} ,}
or equivalently, if and only if all of its lower
level sets
{
x
∈
X
:
f
(
x
)
≤
y
}
{\displaystyle \{x\in X:~f(x)\leq y\}}
are
closed .
Statement of the theorem
Ekeland's variational principle — Let
(
X
,
d
)
{\displaystyle (X,d)}
be a complete metric space and let
f
:
X
→
R
∪
{
+
∞
}
{\displaystyle f:X\to \mathbb {R} \cup \{+\infty \}}
be a
(so
inf
f
(
X
)
∈
R
{\displaystyle \inf _{}f(X)\in \mathbb {R} }
).
Pick
x
0
∈
X
{\displaystyle x_{0}\in X}
such that
f
(
x
0
)
∈
R
{\displaystyle f(x_{0})\in \mathbb {R} }
(or equivalently,
f
(
x
0
)
≠
+
∞
{\displaystyle f(x_{0})\neq +\infty }
) and fix any real
ε
>
0.
{\displaystyle \varepsilon >0.}
There exists some
v
∈
X
{\displaystyle v\in X}
such that
f
(
v
)
≤
f
(
x
0
)
−
ε
d
(
x
0
,
v
)
{\displaystyle f(v)~\leq ~f\left(x_{0}\right)-\varepsilon \;d\left(x_{0},v\right)}
and for every
x
∈
X
{\displaystyle x\in X}
other than
v
{\displaystyle v}
(that is,
x
≠
v
{\displaystyle x\neq v}
),
f
(
v
)
<
f
(
x
)
+
ε
d
(
v
,
x
)
.
{\displaystyle f(v)~<~f(x)+\varepsilon \;d(v,x).}
Proof
Define a function
G
:
X
×
X
→
R
∪
{
+
∞
}
{\displaystyle G:X\times X\to \mathbb {R} \cup \{+\infty \}}
by
G
(
x
,
y
)
=
def
f
(
x
)
+
ε
d
(
x
,
y
)
{\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
f
{\displaystyle f}
and the continuous function
(
x
,
y
)
↦
ε
d
(
x
,
y
)
.
{\displaystyle (x,y)\mapsto \varepsilon \;d(x,y).}
Given
z
∈
X
,
{\displaystyle z\in X,}
denote the functions with one coordinate fixed at
z
{\displaystyle z}
by
G
z
=
def
G
(
z
,
⋅
)
:
X
→
R
∪
{
+
∞
}
and
{\displaystyle G_{z}~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~G(z,\cdot ):X\to \mathbb {R} \cup \{+\infty \}\;{\text{ and }}}
G
z
=
def
G
(
⋅
,
z
)
:
X
→
R
∪
{
+
∞
}
{\displaystyle G^{z}~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~G(\cdot ,z):X\to \mathbb {R} \cup \{+\infty \}}
and define the set
F
(
z
)
=
def
{
y
∈
X
:
G
z
(
y
)
≤
f
(
z
)
}
=
{
y
∈
X
:
f
(
y
)
+
ε
d
(
y
,
z
)
≤
f
(
z
)
}
,
{\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
z
∈
F
(
z
)
.
{\displaystyle z\in F(z).}
An element
v
∈
X
{\displaystyle v\in X}
satisfies the conclusion of this theorem if and only if
F
(
v
)
=
{
v
}
.
{\displaystyle F(v)=\{v\}.}
It remains to find such an element.
It may be verified that for every
x
∈
X
,
{\displaystyle x\in X,}
F
(
x
)
{\displaystyle F(x)}
is closed (because
G
x
=
def
G
(
⋅
,
x
)
:
X
→
R
∪
{
+
∞
}
{\displaystyle G^{x}\,{\stackrel {\scriptscriptstyle {\text{def}}}{=}}\,G(\cdot ,x):X\to \mathbb {R} \cup \{+\infty \}}
is lower semicontinuous);
if
x
∉
dom
f
{\displaystyle x\notin \operatorname {dom} f}
then
F
(
x
)
=
X
;
{\displaystyle F(x)=X;}
if
x
∈
dom
f
{\displaystyle x\in \operatorname {dom} f}
then
x
∈
F
(
x
)
⊆
dom
f
;
{\displaystyle x\in F(x)\subseteq \operatorname {dom} f;}
in particular,
x
0
∈
F
(
x
0
)
⊆
dom
f
;
{\displaystyle x_{0}\in F\left(x_{0}\right)\subseteq \operatorname {dom} f;}
if
y
∈
F
(
x
)
{\displaystyle y\in F(x)}
then
F
(
y
)
⊆
F
(
x
)
.
{\displaystyle F(y)\subseteq F(x).}
Let
s
0
=
inf
x
∈
F
(
x
0
)
f
(
x
)
,
{\displaystyle s_{0}=\inf _{x\in F\left(x_{0}\right)}f(x),}
which is a real number because
f
{\displaystyle f}
was assumed to be bounded below.
Pick
x
1
∈
F
(
x
0
)
{\displaystyle x_{1}\in F\left(x_{0}\right)}
such that
f
(
x
1
)
<
s
0
+
2
−
1
.
{\displaystyle f\left(x_{1}\right)<s_{0}+2^{-1}.}
Having defined
s
n
−
1
{\displaystyle s_{n-1}}
and
x
n
,
{\displaystyle x_{n},}
let
s
n
=
def
inf
x
∈
F
(
x
n
)
f
(
x
)
{\displaystyle s_{n}~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\inf _{x\in F\left(x_{n}\right)}f(x)}
and pick
x
n
+
1
∈
F
(
x
n
)
{\displaystyle x_{n+1}\in F\left(x_{n}\right)}
such that
f
(
x
n
+
1
)
<
s
n
+
2
−
(
n
+
1
)
.
{\displaystyle f\left(x_{n+1}\right)<s_{n}+2^{-(n+1)}.}
For any
n
≥
0
,
{\displaystyle n\geq 0,}
x
n
+
1
∈
F
(
x
n
)
{\displaystyle x_{n+1}\in F\left(x_{n}\right)}
guarantees that
s
n
≤
f
(
x
n
+
1
)
{\displaystyle s_{n}\leq f\left(x_{n+1}\right)}
and
F
(
x
n
+
1
)
⊆
F
(
x
n
)
,
{\displaystyle F\left(x_{n+1}\right)\subseteq F\left(x_{n}\right),}
which in turn implies
s
n
+
1
≥
s
n
{\displaystyle s_{n+1}\geq s_{n}}
and thus also
f
(
x
n
+
2
)
≥
s
n
+
1
≥
s
n
.
{\displaystyle f\left(x_{n+2}\right)\geq s_{n+1}\geq s_{n}.}
So if
n
≥
1
{\displaystyle n\geq 1}
then
x
n
+
1
∈
F
(
x
n
)
=
def
{
y
∈
X
:
f
(
y
)
+
ε
d
(
y
,
x
n
)
≤
f
(
x
n
)
}
{\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
f
(
x
n
+
1
)
≥
s
n
−
1
,
{\displaystyle f\left(x_{n+1}\right)\geq s_{n-1},}
which guarantee
ε
d
(
x
n
+
1
,
x
n
)
≤
f
(
x
n
)
−
f
(
x
n
+
1
)
≤
f
(
x
n
)
−
s
n
−
1
<
1
2
n
.
{\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
n
,
p
≥
1
,
{\displaystyle n,p\geq 1,}
d
(
x
n
+
p
,
x
n
)
≤
2
ε
−
1
2
n
,
{\displaystyle d\left(x_{n+p},x_{n}\right)~\leq ~2\;{\frac {\varepsilon ^{-1}}{2^{n}}},}
which proves that
x
∙
:=
(
x
n
)
n
=
0
∞
{\displaystyle x_{\bullet }:=\left(x_{n}\right)_{n=0}^{\infty }}
is a Cauchy sequence.
Because
X
{\displaystyle X}
is a complete metric space, there exists some
v
∈
X
{\displaystyle v\in X}
such that
x
∙
{\displaystyle x_{\bullet }}
converges to
v
.
{\displaystyle v.}
For any
n
≥
0
,
{\displaystyle n\geq 0,}
since
F
(
x
n
)
{\displaystyle F\left(x_{n}\right)}
is a closed set that contain the sequence
x
n
,
x
n
+
1
,
x
n
+
2
,
…
,
{\displaystyle x_{n},x_{n+1},x_{n+2},\ldots ,}
it must also contain this sequence's limit, which is
v
;
{\displaystyle v;}
thus
v
∈
F
(
x
n
)
{\displaystyle v\in F\left(x_{n}\right)}
and in particular,
v
∈
F
(
x
0
)
.
{\displaystyle v\in F\left(x_{0}\right).}
The theorem will follow once it is shown that
F
(
v
)
=
{
v
}
.
{\displaystyle F(v)=\{v\}.}
So let
x
∈
F
(
v
)
{\displaystyle x\in F(v)}
and it remains to show
x
=
v
.
{\displaystyle x=v.}
Because
x
∈
F
(
x
n
)
{\displaystyle x\in F\left(x_{n}\right)}
for all
n
≥
0
,
{\displaystyle n\geq 0,}
it follows as above that
ε
d
(
x
,
x
n
)
≤
2
−
n
,
{\displaystyle \varepsilon \;d\left(x,x_{n}\right)\leq 2^{-n},}
which implies that
x
∙
{\displaystyle x_{\bullet }}
converges to
x
.
{\displaystyle x.}
Because
x
∙
{\displaystyle x_{\bullet }}
also converges to
v
{\displaystyle v}
and limits in metric spaces are unique,
x
=
v
.
{\displaystyle x=v.}
◼
{\displaystyle \blacksquare }
Q.E.D.
For example, if
f
{\displaystyle f}
and
(
X
,
d
)
{\displaystyle (X,d)}
are as in the theorem's statement and if
x
0
∈
X
{\displaystyle x_{0}\in X}
happens to be a global minimum point of
f
,
{\displaystyle f,}
then the vector
v
{\displaystyle v}
from the theorem's conclusion is
v
:=
x
0
.
{\displaystyle v:=x_{0}.}
Corollaries
Corollary — Let
(
X
,
d
)
{\displaystyle (X,d)}
be a complete metric space , and let
f
:
X
→
R
∪
{
+
∞
}
{\displaystyle f:X\to \mathbb {R} \cup \{+\infty \}}
be a
lower semicontinuous
functional on
X
{\displaystyle X}
that is bounded below and not identically equal to
+
∞
.
{\displaystyle +\infty .}
Fix
ε
>
0
{\displaystyle \varepsilon >0}
and a point
x
0
∈
X
{\displaystyle x_{0}\in X}
such that
f
(
x
0
)
≤
ε
+
inf
x
∈
X
f
(
x
)
.
{\displaystyle f\left(x_{0}\right)~\leq ~\varepsilon +\inf _{x\in X}f(x).}
Then, for every
λ
>
0
,
{\displaystyle \lambda >0,}
there exists a point
v
∈
X
{\displaystyle v\in X}
such that
f
(
v
)
≤
f
(
x
0
)
,
{\displaystyle f(v)~\leq ~f\left(x_{0}\right),}
d
(
x
0
,
v
)
≤
λ
,
{\displaystyle d\left(x_{0},v\right)~\leq ~\lambda ,}
and, for all
x
≠
v
,
{\displaystyle x\neq v,}
f
(
x
)
+
ε
λ
d
(
v
,
x
)
>
f
(
v
)
.
{\displaystyle f(x)+{\frac {\varepsilon }{\lambda }}d(v,x)~>~f(v).}
The principle could be thought of as follows: For any point
x
0
{\displaystyle x_{0}}
which nearly realizes the infimum, there exists another point
v
{\displaystyle v}
, which is at least as good as
x
0
{\displaystyle x_{0}}
, it is close to
x
0
{\displaystyle x_{0}}
and the perturbed function,
f
(
x
)
+
ε
λ
d
(
v
,
x
)
{\displaystyle f(x)+{\frac {\varepsilon }{\lambda }}d(v,x)}
, has unique minimum at
v
{\displaystyle v}
.
A good compromise is to take
λ
:=
ε
{\displaystyle \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
References
^ .
.
.
^ .
.
. Retrieved January 31, 2009 .
Bibliography
.
Kirk, William A.; Goebel, Kazimierz (1990). Topics in Metric Fixed Point Theory . Cambridge University Press. .
Zalinescu, C (2002). Convex analysis in general vector spaces . River Edge, N.J. London: World Scientific. .
.
Spaces
Theorems Operators Algebras Open problems Applications Advanced topics