NOVELTIES AROUND EKELAND’S VARIATIONAL PRINCIPLE

ALFRED GÖPFERT, MATTHIAS SEKATZEK, CHRISTIANE TAMMMER Martin–Luther–Universität Halle–Wittenberg Fachbereich Mathematik und Informatik Institut für Optimierung und Stochastik D-06099 Halle/Saale Germany

Abstract

More than 25 years ago I. Ekeland published the variational principle for approximate solutions of scalar functions. In this paper a slight extension of this principle, a connection with minimal point theorems in product spaces and two applications are given. \underline{Keywords:} Ekeland’s variational principle, partially ordered spaces, minimal points, derived sets, derived cones, approximate solutions

1 Introduction

Ekeland’s variational principle is, on the one hand, a theorem which ensures the existence of certain approximate solutions of a given minimization problem, which are exact solutions of a Lipschitz-perturbation of the original problem. On the other hand, the mentioned approximate solutions are really minimal points with respect to the epigraph of the function to be minimized, where the partial order for the case epif ⊂ X × R, X Banach space, is generated by a convex cone in X × R. In Section 2 we show that a ”non-complete” minimal point theorem is sufficient to derive Ekeland‘s principle (also in the form of Chr. Tammer [12], that means for vector valued mappings) under weaker assumptions as in [12]. In Section 3 it is shown that for a calculable domain the variational principle can be used in such a way that the generated approximate solution is really minimal with respect to the mentioned problem. Using the extremality definition of Mordukhovich and following ideas of Thibault and Jourani, we prove in Section 4 that Breckner’s multiplier rule follows with help of the variational principle. Finally in Section 5 an approximation problem is considered, for which solutions need not exist such that approximate solutions are of interest. Ekeland’s principle gives necessary optimality conditions for special approximate solutions.

2 A non–complete maximal point theorem

At first we recall Ekeland‘s principle:

Theorem 1 [4] Let X be a complete metric space, ρ its metric, f : X → R∪{+∞} a lower semicontinuous and proper function which is bounded from below, ε > 0, λ > 0 and x_{0} ∈ X with f(x_{0}) ≤ inf f + ε, then there is a point x_{ε} ∈ X such that

(i) f(x_{ε}) ≤ f(x_{0}) − ε/λρ(x_{ε}, x_{0}),

(ii) ρ(x_{ε}, x_{0}) ≤ λ,

(iii) f(x) > f(x_{ε}) − ε/λρ(x, x_{ε})∀ x ≠ x_{ε}.

Writing (iii) in the form

(iii)′ ∄x ≠ x_{ε} : f(x) − f(x_{ε}) + ε/λρ(x_{ε}, x) ≤ 0

and taking into account epif ⊂ X × R we conclude, that (x_{ε}, f(x_{ε})) is a minimal point in epif with respect to the binary relation

(x_{1}, t_{1}) ≻ (x_{2}, t_{2}) ⇔ t_{1} − t_{2} ≥ ε/λρ(x_{1}, x_{2})

Of course, if X is a normed space, then the relation is generated by the cone K = {(x, t) : t ≥ ε/λ∥x∥} :

(x_{1}, t_{1}) ≻ (x_{2}, t_{2}) ⇔ (x_{1} − x_{2}, t_{1} − t_{2}) ∈ K.

It is well-known that Ekeland’s principle is equivalent to a minimal point theorem using Phelps’ cone [10] (cf. [1]). But looking for a minimal point theorem using the cone K as above or with respect to the relation ≻, statement (iii) of the principle gives an other hint. We can rewrite (iii) in the equivalent form

(iii)′′ f(x) − f(x_{ε}) + ε/λρ(x_{ε}, x) ≤ 0 → x = x_{ε},

which gives us the idea to look for a minimal point theorem for sets in X ×R ordered by ≻ of the following kind: Let X × R be partially ordered by ≻, D a nonempty set in X × R, (x_{0}, y_{0}) ∈ D, then there is (x_{ε}, y_{ε}) ∈ D such that

(a) (x_{ε}, y_{ε}) ≺ (x_{0}, y_{0})

(b) (x′, y′) ≺ (x_{ε}, y_{ε}), (x′, y′) ∈ D ⇒ x′ = x_{ε}

And indeed, even for the multicriteria variant of Ekeland’s principle, such a minimal point theorem holds. Instead of R^{1} we consider a locally convex space Y partially ordered by a closed convex cone C and k^{0} ∈ C \(−cl C) and define the partial order in X × Y by

(x_{1}, y_{1}) ≻ (x_{2}, y_{2}) ⇔ y_{1} − y_{2} − ε/λk^{0}ρ(x_{1}, x_{2}) ∈ C.

It is clear, that a suitable hypothesis for A and ≺ must be assumed since C need not be Daniell (as R_{+}^{1} is). In the following theorem we use the hypothesis (H1): (H1): For every ≺ − decreasing sequence {(x_{n}, y_{n})} ⊂ A with {x_{n}} → x^{−} there is a

point y^{−} ∈ Y such that (x^{−}, y^{−}) ∈ A and (x^{−}, y^{−}) ≺ (x_{n}, y_{n})∀ n.

It is worth to note that for A = graphf, f : X → Y ∪ {+∞}, {x_{n}} → x^{−} hypothesis (H1) is fulfilled, if f(x_{n})−f(x^{−}) ∈ C holds for all ≺ − decreasing sequences {f(x_{n})}. Obviously, this is weaker than lower semicontinuity of f.

Theorem 2 [7]: Let X, Y, C, k^{0} be given as above, A ⊂ X × Y, A ≠ ∅, the Y - component of it order-bounded from below, (x_{0}, y_{0}) ∈ A. If (H1) is fulfilled, then there is (x_{ε}, y_{ε}) ∈ A such that (a), (b) hold.

3 An extension of Theorem 1

Motivated by the paper of Gajek and Zagrodny [5] and by personal communications with C. Zalinescu we can show the following extension of Ekeland’s principle.

Theorem 3 Let X, ρ, f, ε, λ, x_{0} be as in Theorem 1 but with (H1) instead of the lower semicontinuity for f and α ∈ (0, 1). Then a point x_{ε} can be found in such a way, that

(iv) f(x_{ε}) ≤ f(x) ∀x ∈ B_{α}(x_{ε}, x_{0})

holds together with (i)-(iii), where B_{α}(x_{ε}, x_{0}) = {x ∈ X : ρ(x, x_{0}) + αρ(x, x_{ε}) ≤ ρ(x_{ε′}, x_{0})}.

Proof: At first we decompose ελ^{−1} = β + δ such that β > 0, δ > 0, α = βδ^{−1} ≤ 1, and then consider instead of f the function

g(x) := f(x) + δρ(x, x_{0}),

which is also lower semicontinuous, bounded from below (here it is interesting, that g has to be bounded, the boundedness of f could be avoided; of course, then (ii) is to cancel and x_{0} is a point in domf) and proper, such that Theorem 1 holds for g. So using Theorem 1 with βρ instead of ρ there is a point x_{ε} such that especially (iii) is fulfilled for g:

(iii)′′′ : g(x_{ε}) < g(x) + βρ(x, x_{ε})∀ x ≠ x_{ε}.

Going back to f we find

f(x_{ε}) < f(x) + [δρ(x, x_{0}) + βρ(x, x_{ε}) − δρ(x_{ε}, x_{0})]

and if there is a point x such that the term in brackets is less or equal to zero (iv) follows. B_{α} is a convex set, which is (for 0 < α < 1) shaped at x_{ε} as a cone and in a normed space for α = 0 a ball around x_{0} with radius ∥x_{ε}−x_{0}∥.

4 A connection to derived sets

In this section we deal with a function f_{1} to be minimized on the set

S = {x ∈ X; f_{2}(x) ∈ −K_{2}},

where X is a nonempty subset of a topological space X, f_{1} : X → R^{m_{1}}, f_{2} : X → R^{m_{2}} are some functions, and K_{1} ⊆ R^{m_{1}}, K_{2} ⊆ R^{m_{2}} are convex cones with nonempty interior, of which K_{2} is closed. As usual, a point x_{0} ∈ X is called local weakly K_{1}–minimal for f_{1} over S if x_{0} ∈ S and if there is a neighbourhood U of x_{0} such that

[f_{1}(x_{0}) − int K_{1}] ∩ f_{1}(S ∩ V) = ∅.

To a convex cone K ⊆ R^{m}, we assign with K^{∗} the dual and with K^{o} the polar cone.

According to Breckner [2] we use the concept of derived sets as follows where m = m_{1} + m_{2}, f = (f_{1}, f_{2})^{⊤} : X → R^{m}, K = K_{1} × K_{2} ⊆ R^{m}.

Definition 1. A convex cone D ⊆ R^{m} is called a K–derived convex cone for f : X → R^{m} at x_{0} if for every (m + 1)–tuple {d^{1}, …, d^{m+1}} ⊂ D there exist a number r > 0, a function ω : B_{+}^{m+1}(r) → X (B_{+}^{m+1}(r) := {x ∈ R_{+}^{m+1}; ∥x∥ ≤ r}), and a function ρ = (ρ_{1}, ρ_{2})^{⊤} : B_{+}^{m+1}(r) → R^{m_{1}} × R^{m_{2}} such that the following conditions are satisfied:

(A) f(ω(t)) − f(x_{0}) − (t_{1}d^{1} + … + t_{m+1}d^{m+1}) − ∥t∥ρ(t) ∈ −K ∀t = (t_{1}, …, t_{m+1})^{⊤} ∈ B_{+}^{m+1}(r),

(B) ω(0) = x_{0} and ω is continuous at 0,

(C) there exists a point y^{0} ∈ K such that for each number ϵ > 0 there is a number r_{ϵ} (0 < r_{ϵ} ≤ r) such that ρ(t) ∈ ϵy^{0} − K ∀t ∈ B_{+}^{m+1}(r_{ϵ}).

Breckner’s main result is the following one (cf. [2], Theorem 4.1.):

Theorem 4 Let x_{0} ∈ X be local weakly K_{1}-minimal point for f over S and let D ∈ R^{m} be an K-derived convex cone for f at x_{0}. Then there exists a multiplier vector λ^{∗} = (λ_{1}^{∗}, λ_{2}^{∗})^{⊤} ∈ K_{1}^{∗} × K_{2}^{∗}, λ^{∗} ≠ 0, such that

⟨λ^{∗}, d⟩ ≤ 0  ∀d ∈ D,
⟨λ_{2}^{∗}, f_{2}(x_{0})⟩ = 0.

Our goal was to deduce the above multiplier rule in a way similar to Clarke’s idea, what means we choose a suitable function to be minimized, we find by Ekeland’s variational principle approximate solutions of that problem and, finally, we consider what happens if the approximation error goes to zero. In such a way, Jourani [8] got a result for sets with the so–called property of extremality. Kruger and Mordukhovich [9] introduced the following definition:

Definition 2. Let A and B be two nonempty subsets of a Banach space Y and let be ŷ ∈ A ∩ B. ŷ is said to be a locally extremal point of the system {A, B} if there are sequences {a_{k}} ⊂ Y, {b_{k}} ⊂ Y converging to zero, and a neighbourhood V of ŷ with

(A − a_{k}) ∩ (B − b_{k}) ∩ V = ∅.

In the case V = Y we say that ŷ is an extremal point of the system {A, B}.

It is well–known that if a point x_{0} ∈ X is local weakly K_{1}–minimal for f_{1} on S the point 0 ∈ R^{m} is a locally extremal point of the system {f(X) − f(x_{0}), (−K_{1}) × (−K_{2})}. But we show that also the derived cone has such an extremal property. In the following theorem of Jourani (cf. [8], Theorem 2.4.), a set A ⊆ Y is called locally ∂–compact at ŷ, if there exist a locally compact cone K_{A} ∈ Y^{∗} and a neighbourhood V of ŷ such that ∂ dist(y, A) ⊆ K_{A} ∀y ∈ A ∩ V. The subdifferential operator ∂ is to understood in the general sense of Thibault and Zagrodni [11] covering both Clarke’s subdifferential and the subifferential of convex analysis.

Theorem 5 [8] Let A and B be two nonempty closed subsets of a Banach space Y with ŷ ∈ A ∩ B. Suppose that ŷ is a locally extremal point of the system {A, B}, that the set A is locally ∂–compact at ŷ, and that the mappings ∂ dist(., A) and ∂ dist(., B) are closed at ŷ. Then there exists y^{∗} ∈ Y^{∗} \ {0}, such that

y^{∗} ∈ ∂ dist(ŷ, A) ∩ (−∂ dist(ŷ, B)).

Using the following two lemmata Theorem 4 can be shown as a consequence of Theorem 5.

In the finite dimensional case, needed for our consideration, all these constructions simplify:

Lemma 1 Let A ∈ R^{m} be a convex closed cone. Then A is locally ∂–compact at 0 ∈ A and the mapping ∂ dist(., A) is closed at 0. Furthermore, we have

∂ dist(y, A) ⊆ A^{o} ∀y ∈ A.

Now we will show that Breckner’s multiplier rule (Theorem 4) is a deduction of Theorem 5. First, we define

L = {y ∈ K_{2}^{∗}; ⟨y, f_{2}(x_{0})⟩ = 0}.

If we can prove that 0 ∈ R^{m} is a locally extremal point of the system {clD, (−clK_{1})× (−L^{∗})}, we get by Theorem 5 the existence of a multiplier λ^{∗} = (λ_{1}^{∗}, λ_{2}^{∗})^{⊤} ∈ R^{m}\{0}, such that

−λ^{∗} ∈ ∂ dist(0, D) ∩ (−∂ dist(0, (−cl K_{1}) × (−L^{∗}))) ⊆ D^{o} ∩ K_{1}^{o} × L^{∗o},

which means λ_{1}^{∗} ∈ K_{1}^{∗}, λ_{2}^{∗} ∈ L ⊆ K_{2}^{∗} and

⟨λ^{∗}, d⟩ ≤ 0 ∀d ∈ D,
⟨λ_{2}^{∗}, f_{2}(x_{0})⟩ = 0.

Lemma 2 Under the assumptions of Theorem 4, the point 0 ∈ R^{m} is an extremal point of the system {cl D, (−cl K_{1}) × (−L^{∗})}.

Proof. For every b = (b_{1}, b_{2})^{⊤} ∈ int K_{1} × int L^{∗} holds

cl D ∩ (−b + (−cl K_{1}) × (−L^{∗})) = ∅.

Otherwise, there would be a point d̂= (d̂_{1}, d̂_{2})^{⊤} in the closure of D with

d̂∈ −b + (−cl K_{1}) × (−L^{∗}) ⊆ (−int K_{1}) × (−int L^{∗}).

Without loss of the generality, we can assume that d̂∈ D. Now we use the fact that D is a K–derived convex cone for f at x_{0}. Consider the (m + 1)–tuple {d̂, …, d̂}. Then there exist a number r > 0, a function ω : B_{+}^{m+1}(r) → X, and a function ρ = (ρ_{1}, ρ_{2})^{⊤} : B_{+}^{m+1}(r) → R^{m_{1}} × R^{m_{2}} fulfilling conditions (A), (B), and (C) from Definition 1 for that tuple. Because of d̂_{1} ∈ −int K_{1}, we find to y^{0} = (y_{1}^{0}, y_{2}^{0})^{⊤} ∈ K occuring in (C) an ϵ > 0 with

(Σ t_{i})d̂_{1} + ϵ∥t∥y_{1}^{0} ∈ −int K_{1} ∀t = (t_{1}, …, t_{m+1})^{⊤} ∈ R_{+}^{m+1} \ {0}.

From (C), there is a constant r_{1} (0 < r_{1} ≤ r) with ρ_{1}(t) ∈ ϵy_{1}^{0} − K_{1} ∀t ∈ B_{+}^{m+1}(r_{1}). It follows

(Σ t_{i})d̂_{1} + ∥t∥ρ_{1}(t) ∈ (Σ t_{i})d̂_{1} + ϵ∥t∥y_{1}^{0} − K_{1} ⊆ −int K_{1} ∀t ∈ B_{+}^{m+1}(r_{1}) \ {0}.

So, we have with (A) from Definition 1

f_{1}(ω(t)) − f_{1}(x_{0}) ∈ (Σ t_{i})d̂_{1} + ∥t∥ρ_{1}(t) − K_{1} ⊆ −int K_{1} ∀t ∈ B_{+}^{m+1}(r_{1}) \ {0}.

Because of d̂_{2} ∈ −int L^{∗}, we find analogously a constant r′ (0 < r′ ≤ r) with

(Σ t_{i})d̂_{2} + ∥t∥ρ_{2}(t) ∈ −L^{∗} ∀t ∈ B_{+}^{m+1}(r′).

For every μ^{∗} ∈ L, therefore it holds ∀t ∈ B_{+}^{m+1}(r′) regarding the definition of L

⟨μ^{∗}, f_{2}(x_{0}) + (Σ t_{i})d̂_{2} + ∥t∥ρ_{2}(t)⟩ = ⟨μ^{∗}, f_{2}(x_{0})⟩ + ⟨μ^{∗}, (Σ t_{i})d̂_{2} + ∥t∥ρ_{2}(t)⟩ ≤ 0.

Also for every μ^{∗} ∈ K_{2}^{∗} \ L we find a sufficient small r_{μ^{∗}} such that ∀t ∈ B_{+}^{m+1}(r_{μ^{∗}})

⟨μ^{∗}, f_{2}(x_{0}) + (Σ t_{i})d̂_{2} + ∥t∥ρ_{2}(t)⟩ ⟨μ^{∗}, f_{2}(x_{0})⟩ + (Σ t_{i}) ⟨μ^{∗}, d̂_{2}⟩ + ∥t∥ ⟨μ^{∗}, ρ_{2}(t)⟩ ≤ 0.

Thus, there exists to every μ^{∗} ∈ K_{2}^{∗} a r_{μ^{∗}} > 0, such that the above inequality holds. Since the cone K_{2}^{∗} has a compact base, we can fix a r_{2} > 0 independent from μ^{∗} such that

⟨μ^{∗}, f_{2}(x_{0}) + (Σ t_{i})d̂_{2} + ∥t∥ρ_{2}(t)⟩ ≤ 0 ∀μ ∈ K_{2}^{∗} ∀t ∈ B_{+}^{m+1}(r_{2}).

It follows

f_{2}(x_{0}) + (Σ t_{i})d̂_{2} + ∥t∥ρ_{2}(t) ∈ −K_{2} ∀t ∈ B_{+}^{m+1}(r_{2}).

and by (A) from Definition 1

f_{2}(ω(t)) ∈ f_{2}(x_{0}) + (Σ t_{i})d̂_{2} + ∥t∥ρ_{2}(t) − K_{2} ⊂ −K_{2} ∀t ∈ B_{+}^{m+1}(r_{2}).

Due to (B), to every neigbourhood U of x_{0} we find a t̂ ∈ B_{+}^{m+1}(min(r_{1}, r_{2})) \ {0} such that ω(t̂) ∈ U ∩ X. As shown above, it is

f_{1}(ω(t̂)) − f_{1}(x_{0}) ∈ −int K_{1},
f_{2}(ω(t̂)) ∈ −K_{2},

implying ω(t̂) ∈ S. This contradicts the optimality of x_{0}.

So the assertion made in the beginning is true. Choosing the sequences {a_{k}} with a_{k} = 0 for all k and \{b_{k}\} with b_{k} = \frac{1}{k}b for an arbitrary fixed b ∈ intK_{1} ×intL^{∗}, we get the desired property.

Breckner’s complete multiplier rule for problems over the feasible set

S = {x ∈ X; f_{2}(x) ∈ −K_{2}, f_{3}(x) = 0}

(f_{3} : X → R^{m_{3}}), also can be obtained as a deduction of Theorem 5. For this, it is to show that the point 0 is an extremal point of the system {cl D, (−cl K_{1}) × (−L^{∗}) × {0^{m_{3}}}}. The proof uses an implicit function theorem, but cannot be given in a few lines. Note, that the above structure of S is not only a special case of the problem considered by Breckner, but an equivalent description (cf. [3]).

5 An approximation problem without solutions

Normally an initial value problem for an elliptic differential equation is not wellposed and solutions need not exist. But we come from an other point of view. We consider a usual boundary value problem, say the Dirichlet problem for the homogeneous Laplace equation in a ball B ⊂ R^{n}, and as boundary values we take all continuous functions along the sphere of the ball. So we get in the interior of the ball a linear manifold M of solutions of the Laplace equation. Now we restrict these solutions to a smooth (n − 1)-dimensional surface Γ (which doesn’t decompose B), where Γ ⊂ intB. This could be done also for the normal derivatives of the elements of M with respect to Γ. We want to approximate a pair of functions (u_{1}, u_{2}) given along Γ, which could be seen as the mentioned initial-value-problem, by the elements of M and their normal derivatives. Taking for simplicity L_{2}-norms to approximate, we get a linear vector approximation problem of the following kind:

( \begin{matrix}∥u_{1} − L(φ)∥_{2} \\ ∥u_{2} − \frac{∂}{∂n}L(φ)∥_{2} \end{matrix} ) → min_{φ∈C(B)}

where L is the Green’s operator of the Laplacean, shrinked to Γ, \frac{∂}{∂n}L is the normal derivative. It is well-known that L depends linearly on φ. So the ε-Kolmogorov conditions, derived by Chr. Tammer [13], [14] with help of Ekelands principle, are applicable and generate necessary optimality conditions. Clearly, exact solutions of the problem need not exist, since one only need to take u_{1} as a nondifferentiable function, while L(φ) along a sufficiently smooth surface has derivatives for all continuous φ ∈ C(B). Nevertheless, exploiting those Kolmogorov-conditions for the special case that we only approximate u_{1} (a scalar problem), then we get the side conditions of the dual problem to our scalar approximation problem as in [6], (13’).

References

[1] Attouch, H. and Riahi, H. (1993): Stability results for Ekeland ϵ - variational principle and cone extremal solutions. Math. Oper. Res.18, 173-201.

[2] Breckner, W.W. (1994): Derived sets in multiobjective optimization. Z. Anal. Anw., 13, 725–738.

[3] Breckner, W.W.; Göpfert, A.; Sekatzek, M.(1997): Lagrange Multipliers in Vector Optimization. ZAMM 77, 525-526.

[4] Ekeland, I. (1974): On the variational principle. J. Math. Anal. Appl. 47, 324 - 353.

[5] Gajek, L. and Zagrodny, D. (1995): Geometric Variational Principle. Dissertationes Mathematicae 340, 55-71.

[6] Göpfert, A. (1979): Über Wertannahme bei einer Klasse von Optimalproblemen. Optimization 10, 111-119.

[7] Göpfert, A.; Tammer, Chr. and Zalinescu, C. (1997): On the vectorial Ekeland’s variational principle and minimal points in product spaces. Report No. 46, Martin-Luther-University Halle-Wittenberg. To appear in Nonlin. Anal.

[8] Jourani, A.: Necessary conditions for extremality and separation theorems with applications to multiobjective optimization. To appear in Optimization.

[9] Kruger, A.Ya.; Mordukhovich, B.S. (1978): Minimization of nonsmooth functionals in optimal control problems. Engrg. Cybern., 16, 126–133.

[10] Phelps, R. R. (1993): Convex Functions, Monotone Operators and Differentiability (2nd Ed.). Lect. Notes Math. 1364, 1 - 118.

[11] Thibault, L.; Zagrodny, D. (1995): Integration of subdifferentials of lower semicontinuous functions in Banach spaces. J. Math. Anal. Appl., 189, 33–58.

[12] Tammer, Chr. (1992): A Generalization of Ekeland’s principle. Optimization 25, 129 - 141.

[13] Tammer, Chr. (1993): Existence results and necessary conditions for ϵ-efficient elements. In: Multicriteria Decision. (Eds.: B. Brosowski, J. Ester, S. Helbig and R. Nehse). Frankfurt am Main: Verlag P. Lang, 97 - 109.

[14] Tammer, Chr. (1993): Necessary conditions for approximately efficient elements. Approximation and Optimization.