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

${\displaystyle -\infty .}$

${\displaystyle \mathbb {R} \cup \{+\infty \}}$

${\displaystyle +\infty .}$

${\displaystyle f}$

${\displaystyle -\infty <\inf _{}f(X)\neq +\infty ,}$

${\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

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.