Namespaces
Variants
Actions

Ekeland variational principle

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.


There are usually three ways for getting existence results in analysis, namely compactness, Hahn–Banach-type results and completeness properties (cf. Compactness; Hahn–Banach theorem; Completeness (in topology)). The Ekeland variational principle [a10] (which provides a characterization of complete metric spaces [a14], cf. also Complete metric space) illustrates the third method in the framework of optimization. Let $ f $ be a lower semi-continuous function defined on a complete metric space $ ( X,d ) $, with values in the extended line $ \mathbf R \cup \{ + \infty \} $, and bounded from below. It is well known that the lower bound of $ f $ over $ X $ need not be attained. Ekeland's basic principle asserts that there exists a slight perturbation of $ f $ which attains its minimum on $ X $. More precisely, there exists a point $ a \in X $ such that $ f ( a ) < f ( x ) + d ( a,x ) $ for all $ x \in X \setminus \{ a \} $; this says that the function $ f ( \cdot ) + d ( a, \cdot ) $ has a strict minimum on $ X $ at $ a $. It is interesting to observe that the conclusion of the basic principle is equivalent to the existence of a maximal element in the epigraph $ { \mathop{\rm epi} } f = \{ {( x,r ) \in X \times \mathbf R } : {f ( x ) \leq r } \} $ for the order defined on $ X \times \mathbf R $ by $ ( x _ {1} ,r _ {1} ) \cle ( x _ {2} ,r _ {2} ) $ if and only if $ r _ {2} - r _ {1} + d ( x _ {2} ,x _ {1} ) \leq 0 $[a3].

Figure: e110030a

From this basic principle one can deduce some variants which are in fact equivalent to the basic statement. The first one is as follows: given $ \epsilon > 0 $, $ x _ {0} \in X $ such that $ f ( x _ {0} ) < \inf _ {x \in X } f ( x ) + \epsilon $ and applying the basic principle to the complete metric space $ {\widetilde{X} } = \{ {z \in X } : {f ( z ) + d ( x _ {0} ,z ) \leq f ( x _ {0} ) } \} $, one obtains the existence of a point $ a \in X $ such that $ f ( a ) + d ( a,x _ {0} ) \leq f ( x _ {0} ) $ and $ f ( a ) < f ( x ) + d ( a,x ) $ for all $ x \in X \setminus \{ a \} $. In particular, this implies that $ | {f ( a ) - f ( x _ {0} ) } | \leq \epsilon $. Applying the previous result with the metric $ \gamma d $, $ \gamma > 0 $, yields the second variant: there exists an $ a \in X $ such that

$$ d ( a,x _ {0} ) \leq \gamma ^ {- 1 } \epsilon, $$

$$ \left | {f ( a ) - f ( x _ {0} ) } \right | \leq \epsilon, $$

$$ f ( a ) < f ( x ) + \gamma d ( a,x ) \textrm{ for all } x \in X \setminus \{ a \} . $$

This variational principle has several equivalent geometric formulations. For instance, the Phelps extremization principle and the Drop theorem [a7], [a12] (see [a13] for the versions as stated here). Let $ A $ be a closed subset of a Banach space $ X $, let $ x \in A $ and let $ C $ be a closed convex bounded subset of $ X $ such that $ A \cap ( x + C ) = \emptyset $. Then there exist a $ z \in A \cap ( x + [ 0,1 ] C ) $ and a $ \delta > 0 $ such that $ A \cap ( z + \left ] 0, \delta \right ] C ) = \emptyset $.

Among the great number of applications is the celebrated Bröndsted–Rockafellar theorem in convex analysis [a6]. Let $ f $ be a closed convex function defined on a real Banach space $ ( X, \| \cdot \| ) $ with values in $ \mathbf R \cup \{ + \infty \} $( cf. also Convex function (of a real variable)). Let $ x _ {0} \in { \mathop{\rm dom} } f = \{ {x \in X } : {f ( x ) < + \infty } \} $, $ \epsilon > 0 $, and let $ {\mathcal l} _ {0} \in X ^ {*} $ be such that $ f ( x ) \geq f ( x _ {0} ) + {\mathcal l} _ {0} ( x - x _ {0} ) - \epsilon $ for all $ x \in X $. One can apply the third version of the theorem, with $ \gamma = \sqrt \epsilon $, to the function $ g = f - {\mathcal l} _ {0} $ when endowing $ X $ with the equivalent norm $ \| \cdot \| + | { {\mathcal l} ( \cdot ) } | $[a4]. This yields the existence of an $ x _ \epsilon \in X $ and an

$$ {\mathcal l} _ \epsilon \in \partial f ( x _ \epsilon ) = $$

$$ = \left \{ { {\mathcal l} \in X ^ {*} } : {f ( x ) \geq f ( x _ \epsilon ) + {\mathcal l} ( x - x _ \epsilon ) \textrm{ for all } x \in X } \right \} $$

such that

$$ \left \| {x _ \epsilon - x _ {0} } \right \| \leq \sqrt \epsilon , $$

$$ \left | {f ( x _ \epsilon ) - f ( x _ {0} ) } \right | \leq 2 \epsilon + \sqrt \epsilon . $$

Hence the set

$$ { \mathop{\rm dom} } \partial f = \left \{ {x \in { \mathop{\rm dom} } f } : {\partial f ( x ) \neq \emptyset } \right \} $$

is dense in $ { \mathop{\rm dom} } f $ for the epigraph topology, i.e. the supremum of the norm topology on $ X $ and of the initial topology associated to $ f $.

Another easy consequence of the Ekeland variational principle is a generalization to multi-functions of the Kirk–Caristi fixed-point theorem [a2].

Finally, it should be mentioned that analogous results hold in Banach spaces with the perturbation $ d ( a, \cdot ) $ replaced by some smooth one [a5].

References

[a1] H. Attouch, H. Riahi, "Stability results for the Ekeland's variational principle and cone extremal solutions" Math. Oper. Res. , 18 (1993) pp. 173–201
[a2] J.-P. Aubin, I. Ekeland, "Applied nonlinear analysis" , Wiley (1984)
[a3] E. Bishop, R.R. Phelps, "The support functional of a convex set" P. Klee (ed.) , Convexity , Proc. Symp. Pure Math. , 7 , Amer. Math. Soc. (1963) pp. 27–35
[a4] J.M. Borwein, "A note on -subgradients and maximal monotonicity" Pacific J. Math. , 103 (1982) pp. 307–314
[a5] J.M. Borwein, R. Preiss, "Smooth variational principle" Trans. Amer. Math. Soc. , 303 (1987) pp. 517–527
[a6] A. Bröndsted, R.T. Rockafellar, "On the subdifferentiability of convex functions" Proc. Amer. Math. Soc. , 16 (1965) pp. 605–611
[a7] F.H. Clarke, "Optimization and nonsmooth analysis" , Wiley (1983)
[a8] J. Daneš, "A geometric theorem useful in nonlinear functional analysis" Boll. Un. Mat. Ital. , 4 (1972) pp. 369–375
[a9] D.G. de Figueiredo, "The Ekeland variational principle, tours and detours" , Lecture Notes Tata Inst. , Springer (1989)
[a10] I. Ekeland, "On the variational principle" J. Math. Anal. Appl. , 47 (1974) pp. 324–353
[a11] I. Ekeland, "Nonconvex minimization problems" Bull. Amer. Math. Soc. (N.S.) , 1 (1979) pp. 443–474
[a12] J.-P. Penot, "The drop theorem, the petal theorem and Ekeland's variational principle" Nonlinear Anal.: Theory, Methods, Appl. , 10 (1986) pp. 813–822
[a13] J.S. Treiman, "Characterization of Clarke's tangent and normal cones in finite and infinite dimensions" Nonlinear Anal.: Theory, Methods, Appl. , 7 (1983) pp. 771–783
[a14] J.D. Weston, "A characterization of metric completeness" Proc. Amer. Math. Soc. , 64 (1977) pp. 186–188
How to Cite This Entry:
Ekeland variational principle. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Ekeland_variational_principle&oldid=46797
This article was adapted from an original article by H. AttouchD. Azé (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article