Ekeland variational principle

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