Characterizations of Efficient Points in Convex Vector Optimization Problems

Kristin Winkler

We present a geometrical characterization of weakly efficient points which generalizes the characterization recently given by Carrizosa and Plastria for functions over real Banach spaces. Further we indicate some applications of the shown optimality criteria to location problems and we investigate approximately efficient solutions.

1 Motivation

The main intention of location theory is to place a facility x in some space 𝔛 (or more restricting in a subset S ⊂ 𝔛) such that it is optimal situated to m given facilities. For instance, in planar location theory (e. g. town planning) we will chose 𝔛 = IR^{2}, and the goal function will be composed by distances d_{i}(x, a_{i}) between the m fixed facilities and the new facility x and by weights or (monotone increasing) cost functions g_{i}(.). Then, the vector-valued problem formulation is

( g_{1}(d_{1}(x, a_{1})) ; ⋮ ; g_{m}(d_{m}(x, a_{m})) ) → V − min .

In a more general statement we allow 𝔛 to be an arbitrary real Banach space and we consider a probably not countable, but compact index set A. It suffices to preserve the convexity of the distance functions – we write f_{a}(.) instead of d_{i}(x, a_{i}). In case of monotone increase, the cost functions prove to be redundant, i. e. they do not change the set of efficient points. The considered problem reads now

{f_{a}(x)}_{a∈A} → V − min .

We investigate minimality in the sense of vector-valued optimization (namely Pareto optimality):

Definition. Let f_{a} : X → IR ∪ {+∞}, a ∈ A, and S ⊂ X. An element x ∈ S is called efficient, if there is no y ∈ S with f_{a}(y) ≤ f_{a}(x) ∀ a ∈ A and fā(y) < fā(x) for some ā ∈ A. x is called weakly efficient, if there is no y ∈ S with f_{a}(y) < f_{a}(x) ∀ a ∈ A.

The set of (weakly) efficient points for {f_{a}}_{a∈A} and S will be denoted by E(A, S) (resp. E_{w}(A, S)).

There are several situations which lead to a location problem with infinitely many fixed facilities. Imagine for instance the planned construction of a lifeguard tower at a certain beach area: Each place within the beach area should be reachable in minimal time; there is no reason (besides mathematics) to consider only finitely many ”reference points”. We will come back to this example later on.

On the other hand, for example, if we intent to localize streets of a mains system, we arrive at optimization over function spaces instead of the space IR^{2} or IR^{3}.

Subsequent, let 𝔛 be a real Banach space and 𝔛′ its topological dual. For two sets A, B let A + B = {a + b : a ∈ A, b ∈ B}; let int A resp. cl A denote the interior resp. the closure of A. B(0, r) is the closed ball with center 0 and radius r. Further, consider X ⊂ 𝔛 open, S ⊆ X (relatively) closed and convex.

A function f : X → IR is called lower semicontinuous, if the set {x ∈ X : f(x) ≤ r} is closed for each r ∈ IR. Further, for a convex function f : X → IR we denote by

∂f(x) = {p ∈ 𝔛′ : p(y − x) ≤ f(y) − f(x) ∀ y ∈ 𝔛}

the subdifferential in x. The normal cone at S in x is the set

N_{S}(x) = \{ \begin{matrix}\{p ∈ 𝔛′ : p(y − x) ≤ 0 ∀ y ∈ S\} & for x ∈ S \\ ∅ & else \end{matrix}

Concerning extended convex functions f : X → IR ∪ {+∞}, the subdifferential ist given by

∂f(x) = {p ∈ 𝔛′ : (p, −1) ∈ N_{epi f}(x, f(x))}
= {p ∈ 𝔛′ : p(y − x) ≤ r − f(x) ∀ y ∈ X, r ≥ f(y)}

where epi f denotes the epigraph of f. For properties and further details to these notions we refer to [2].

2 Optimality Criteria

In [1], Carrizosa and Plastria give a necessary and sufficient criterium for weak efficiency of the type

x ∈ E_{w}(A, S) ⟺ 0 ∈ conv ( ⋃_{a∈A} ∂f_{a}(x)) + N_{S}(x).

Beside convexity, they suppose 𝔛 = IR^{n}, compactness of A and continuity of the mapping a ↦ f_{a}(x) for each x ∈ X. Whereas the latter two conditions seem not to get moderated, we present the corresponding result in an arbitrary real Banach space 𝔛. The fundamental difference is that under this weaker assumption the convex hull of the subdifferentials has not to be closed anymore (in the case 𝔛 = IR^{n} it is even compact) and therefore we have to replace ”conv ” by ”cl conv ”.

Theorem 1 Let 𝔛 be a real Banach space, X ⊂ 𝔛 open and convex, let A be a compact subset of a complete space. Let {f_{a}}_{a∈A}, f_{a} : X → IR, denote a family of convex, locally bounded functions, where for each x ∈ X the mapping a ↦ f_{a}(x) is continuous. Then we have for x ∈ X

x ∈ E_{w}(A, X) ⟺ 0 ∈ cl conv ( ⋃_{a∈A} ∂f_{a}(x)) ,

where the closure is taken in the topology σ(𝔛′, 𝔛) of 𝔛′.

Proof. We start with the proof of

x ∉ E_{w}(A, X) ⟺ ∃ y ∈ X, ∃ M < 0 : f_{a}(y) − f_{a}(x) ≤ M ∀ a ∈ A. (1)

Assume x ∉ E_{w}(A, X). Then there exists some y ∈ X such that f_{a}(y)−f_{a}(x) < 0 for all a ∈ A. By the continuity of the mapping a ↦ f_{a}(x) and the compactness of A we get

sup_{a∈A} {f_{a}(y) − f_{a}(x)} = max_{a∈A} {f_{a}(y) − f_{a}(x)} =: M < 0.

On contrary, let exist some y ∈ X and M < 0 with

f_{a}(y) − f_{a}(x) ≤ M ∀ a ∈ A.

Then it is clear that x can not be weakly efficient. So we have proven (1). Now the definition of the subdifferential yields

x ∉ E_{w}(A, X) ⟺
∃ y ∈ X, ∃ M < 0 : p(y − x) ≤ M ∀ p ∈ ⋃_{a∈A} ∂f_{a}(x).  (2)

By the linearity of the functionals p, the equivalence in (2) remains valid if the inequality at the right-hand-side has to hold for all p ∈ cl_{σ(𝔛′,𝔛)} conv (⋃_{a∈A} ∂f_{a}(x)). Furthermore, since X is open, we can write 𝔛 instead of X. So we get

x ∉ E_{w}(A, X) ⟺

∃ z ∈ 𝔛 : p(z) ≤ M < 0 ∀ p ∈ cl_{σ(𝔛′,𝔛)} conv ( ⋃_{a∈A} ∂f_{a}(x)) .

Now we apply (in (𝔛′, σ(𝔛′, 𝔛)) with dual 𝔛) a classical separation theorem (separating a point and a closed convex set, cf. for instance [4, Theorem 3.18]) and get

x ∉ E_{w}(A, X) ⟺ 0 ∉ cl_{σ(𝔛′,𝔛)} conv ( ⋃_{a∈A} ∂f_{a}(x))

resp., after negation, the assertion.

As a corollary we state:

Theorem 2 Under the assumptions of the theorem above, for each closed convex S ⊂ X and each x ∈ S we have

x ∈ E_{w}(A, S) ⟺ 0 ∈ cl conv ( ⋃_{a∈A} ∂f_{a}(x)) + N_{S}(x),

where the closure is taken in the topology σ(𝔛′, 𝔛) of 𝔛′ again.

We need some rather technical results for the proof which will be included here.

Lemma 1 Under the assumptions of theorem 1, the set ⋃_{a∈A} ∂f_{a}(x) is bounded in 𝔛′ for each x ∈ X.

Proof. For each h ∈ 𝔛 with x + h ∈ X we can state

sup{p(h) : p ∈ ⋃_{a∈A} ∂f_{a}(x)} = sup_{a∈A} {p(h) : p ∈ ∂f_{a}(x)}
≤ sup_{a∈A} [f_{a}(x + h) − f_{a}(x)]
= max_{a∈A} [f_{a}(x + h) − f_{a}(x)]
< ∞.

As ⋃_{a∈A} ∂f_{a}(x) ⊂ 𝔛′, the function

q : h ↦ sup {p(h) : p ∈ ⋃_{a∈A} ∂f_{a}(x)}

is finite for h ∈ 𝔛. Furthermore q is convex (as the supremum of linear functions, cf. [2]) and so it is continuous. Thus, there exists a constant L ∈ IR with

sup {q(h) : ∥h∥_{𝔛} ≤ 1} ≤ L.

It follows that for each p ∈ ⋃_{a∈A} ∂f_{a}(x) we have

∥p∥_{𝔛′} = sup {p(h) : ∥h∥_{𝔛} ≤ 1} ≤ sup {q(h) : ∥h∥_{𝔛} ≤ 1} ≤ L,

e. g. the boundedness.

The idea of this proof is from the paper of Carrizosa and Plastria, [1].

Lemma 2 Let M_{1}, M_{2} two subsets of the dual 𝔛′ of a Banach space 𝔛, let M_{1} bounded. Then we have

cl_{σ(𝔛′,𝔛)} (M_{1} + M_{2}) = cl_{σ(𝔛′,𝔛)} M_{1} + cl_{σ(𝔛′,𝔛)} M_{2}

Proof. The statment cl_{σ(𝔛′,𝔛)} (M_{1} + M_{2}) ⊃ cl_{σ(𝔛′,𝔛)} M_{1} + cl_{σ(𝔛′,𝔛)} M_{2} is obvious.

On contrary, let {c_{n}}_{n∈IN} ⊂ cl_{σ(𝔛′,𝔛)} (M_{1} + M_{2}) a sequence with c_{n} →_{σ(𝔛′,𝔛)} c ∈ cl_{σ(𝔛′,𝔛)} (M_{1} + M_{2}). Then there exist sequences {a_{n}}_{n∈IN} in cl_{σ(𝔛′,𝔛)} M_{1} and {b_{n}}_{n∈IN} in cl_{σ(𝔛′,𝔛)} M_{2} with a_{n} + b_{n} = c_{n} ∀ n ∈ IN. By the boundedness of M_{1}, {a_{n}}_{n∈IN} contains some σ(𝔛′, 𝔛)-convergent subsequence {a_{k}}_{k∈IN}, a_{k} →_{σ(𝔛′,𝔛)} a, where a ∈ cl_{σ(𝔛′,𝔛)} M_{1}. Therefore b_{k} = c_{k} −a_{k} weakly* converges to some b, where b = c − a and b belongs to the set cl_{σ(𝔛′,𝔛)} M_{2}.

Proof of theorem 2. We adapt the proof of theorem 1 to the functions

f̂_{a}(x) := f_{a}(x) + χ_{S}(x), a ∈ A,

where χ_{S}(.) denotes the characteristic function of the set S,

χ_{S}(x) := \{ \begin{matrix}0 & bei x ∈ S \\ +∞ & sonst, \end{matrix}

It is well-known that

∂f̂_{a}(x) = ∂f_{a}(x) + N_{S}(x), a ∈ A.

Furthermore, by the same ideas as in the first part of the proof of theorem 1 we can prove

x ∉ E_{w}(A, S) ⟺ ∃ y ∈ S, ∃ M < 0 : f_{a}(y) − f_{a}(x) ≤ M ∀ a ∈ A,

and this is equivalent to

∃ y ∈ X, ∃ M < 0 : f̂_{a}(y) − f̂_{a}(x) ≤ M ∀ a ∈ A.

From the definition of the subdifferential we now get

x ∉ E_{w}(A, S) ⟺ ∃ y ∈ X, ∃ M < 0 : p(y − x) ≤ M ∀ p ∈ ⋃_{a∈A} ∂f̂_{a}(x).

With the cited separation theorem and the two lemmata above we can conclude: x ∉ E_{w}(A, S) ⟺

0 ∈ cl_{σ(𝔛′,𝔛)} conv ( ⋃_{a∈A} ∂f̂_{a}(x)) = cl_{σ(𝔛′,𝔛)} conv ( ⋃_{a∈A} ∂f_{a}(x)) + N_{S}(x).

The negation of this result completes the proof.

Remark. Carrizosa and Plastria use another idea for their proof: They scalarize the problem by the function

F (y) := sup_{a∈A} [f_{a}(y) − f_{a}(x)] = max_{a∈A} [f_{a}(y) − f_{a}(x)]

(x ∈ S fixed) and prove

∂F (x) = conv ⋃_{a∈A} ∂f_{a}(x).

It is well-known that the solution set of the problem

F (x) → min, x ∈ S

is exactly the set E_{w}(A, S) of weakly efficient points. So, we could have proceeded in the same way because Solovev has recently presented the required formula for the subdifferential of pointwise maxima (under much weaker assumptions) in [7].

In [6], Luu and Oettli investigate minimax problems

max_{a∈A} g_{a}(x) → min, x ∈ S,

where the sets A and S ⊆ X ⊂ 𝔛 are of the same nature as in our paper. They give necessary optimality conditions for a broad class of functions g_{a} which lead to the assertions of the theorems 1 and 2, too. Nevertheless, they did not investigate the relations of their results to multicriteria optimization.

The criteria from the theorems above do not apply to the set E(A, S) of efficient points, as the following example points out:

Example 1 Let A = {a_{1}, a_{2}, a_{3}} = {(0, 0), (1, 1), (−1, 1)} ⊂ IR^{2}, x = (0, 1/2). We consider the functions

f_{i}(y) = ∥y − a_{i}∥_{l^{2}} = \sqrt{(y^{1} − a_{i}^{1})^{2} + (y^{2} − a_{i}^{2})^{2}},  i = 1, 2, 3,
g_{i}(y) = ∥y − a_{i}∥_{l^{∞}} = max {|y^{1} − a_{i}^{1}|, |y^{2} − a_{i}^{2}|},  i = 1, 2, 3.

Then we have

∂f_{i}(x) = ∂g_{i}(x), i = 1, 2, 3,

but x is efficient with respect to f_{i} and not efficient with respect to g_{i}.

Remind that the set of efficient points coincides with the set of weakly efficient points if the goal function is strictly convex. The situation changes in case of ”normal” convexity, even though the gradients probably remain the same.

Now we return to our lifeguard tower example:

Example 2 Let A ⊂ IR^{2} = 𝔛 = X be an arbitrary closed and bounded set. We consider euclidean distances,

f_{a}(x) = ∥x − a∥ = \sqrt{(x_{1} − a_{1})^{2} + (x_{2} − a_{2})^{2}},

where x = (x_{1}, x_{2}) ∈ X, a = (a_{1}, a_{2}) ∈ A. Then we have

∂f_{a}(x) = \{ \begin{matrix}\{(x − a)/∥x − a∥\} & if x ≠ a \\ B(a, 1) & if x = a \end{matrix}

It follows immediately that

0 ∈ cl conv ⋃_{a∈A} ∂f_{a}(x) ⟺ x ∈ cl conv A.

So, the assertion of theorem 1 generalizes both the well-known result given by Kuhn in the late 60th (see [5]) and the result given by Carrizosa and Plastria (see [1]).

3 Approximate solutions

In the latter section we have assumed that there exists some weakly efficient points at all (otherwise optimality criteria make no sense). But in general this will not be given. Therefore, we now present an existence result for minimizing sequences, e. g. sequences of approximately (weakly) efficient points.

Definition. Let ε > 0 and k = {k_{a}}_{a∈A} be given, where k_{a} > 0 for all a ∈ A and a ↦ k_{a} is continuous. An element x ∈ S is called εk-efficent, if there is no y ∈ S with f_{a}(y) ≤ f_{a}(x) − εk_{a} ∀ a ∈ A and fā(y) < fā(x) − εkā for some ā ∈ A. x is called weakly εk-efficient, if there exist no y ∈ S with f_{a}(y) < f_{a}(x) − εk_{a} ∀ a ∈ A.

The set of all (weakly) εk-efficient points with respect to {f_{a}}_{a∈A} and S will be denoted by E^{εk}(A, S) (resp. E_{w}^{εk}(A, S)).

In the proof of our theorem below we use a vector-valued version of Ekeland’s variational principle as it has been presented by Tammer (cf. [3]):

Lemma 3 Let 𝔜 be a linear topological space, K ⊂ 𝔜 a convex cone with K ∩ (−K) = {0} and k ∈ int K, M ⊂ 𝔜 a set with int M ≠ ∅, cl M + (K\{0}) ⊂ int M and bd M + bd M ⊂ cl M. Further, let 𝔛 be a real Banach space, X ⊂ 𝔛 open, S ⊂ X closed and convex, F : X → 𝔜 a vector-valued mapping such that L_{r}(F) := {x ∈ S : F (x) ∈ rk −cl M} is closed for each r ∈ IR and F [S] ⊂ z +M is fulfilled for some z ∈ 𝔜. Let ε > 0 and x_{0} ∈ X with

F [S] ∩ (F (x_{0}) − M − εk) = ∅.

Then there exist some x_{ε} ∈ X such that

(i) F [S] ∩ (F (x_{ε}) − K\{0} − εk) = ∅,

(ii) ∥x_{ε} − x_{0}∥ ≤ \sqrt{ε},

(iii) F_{ε}[S] ∩ (F_{ε}(x_{ε}) − K\{0}) = ∅,

where F_{ε}(x) := F (x) + \sqrt{ε}∥x − x_{ε}∥k.

Now we still have to embed our problem into the context of optimiziation in abstract spaces.

The continuity of the mapping a ↦ f_{a}(x) suggests to consider {f_{a}}_{a∈A} as an element of the space 𝒞(A) of continuous functions on A: F ≡ {f_{a}} : X → 𝒞(A). 𝒞(A) endowed with the maximum norm

∥g∥ = max_{a∈A} |g(a)|

and the order cone

𝒞^{+}(A) = {g ∈ 𝒞(A) : g(a) ≥ 0 ∀ a ∈ A}

is a Banach lattice (but in general not order complete). Furthermore we have

int 𝒞^{+}(A) = {g ∈ 𝒞(A) : g(a) > 0 ∀ a ∈ A}.

So, we can rewrite our defintion of efficiency in the following, more common way:

x ∈ E^{εk}(A, S) ⟺ F [S] ∩ (F (x) − (𝒞^{+}(A)\{0}) − εk) = ∅

resp.

x ∈ E_{w}^{εk}(A, S) ⟺ F [S] ∩ (F (x) − int 𝒞^{+}(A) − εk) = ∅.

Here, we identify {k_{a}}_{a∈A} with the function k : A → IR, k(a) ≡ k_{a}.

Theorem 3 Let the assumptions of theorem 1 be fulfilled. Let S ⊂ X be closed and convex, let the functions f_{a} be lower semicontinuous and the family {f_{a}} uniformly bounded from below. Then there exist for each ε > 0, each k = {k_{a}}_{a∈A}, k_{a} > 0 ∀ a ∈ A and each x_{0} ∈ E^{εk}(A, S) some x_{ε} ∈ S ∩ B(x_{0}, \sqrt{ε}) with

x_{ε} ∈ E_{w}^{εk}(A, S)  (3)

und

0 ∈ cl conv ( ⋃_{a∈A}[∂f_{a}(x) + B(0, εk_{a})]) + N_{S}(x_{ε}).  (4)

Proof. We set 𝔜 = 𝒞(A), F ≡ {f_{a}}_{a∈A}, M = 𝒞^{+}(A),

K := int 𝒞^{+}(A) ∪ {0} = {g ∈ 𝒞(A) : g(a) > 0 ∀ a ∈ A} ∪ {0}

and we chose some k ∈ int 𝒞^{+}(A). By the lower semicontinuity and boundedness of the functions f_{a} we have the closedness of the sets L_{r}({f_{a}}_{a∈A}) as well as F [S] ⊂ g + M for some g ∈ 𝒞(A). Therefore, there exist some x_{ε} with the properties (i)-(iii) in lemma 3. From (i) the statement (3) follows immediately. From (iii) and theorem 1 we can derive

0 ∈ cl conv ( ⋃_{a∈A} ∂[f_{a}(.) + \sqrt{ε}∥. − x_{ε}∥k_{a} + χ_{S}(.)](x_{ε}))

= cl conv ( ⋃_{a∈A}[∂f_{a}(x_{ε}) + B(0, \sqrt{ε}k_{a})]) + N_{S}(x_{ε})

and so the proof is complete.

Remark. By the boundedness of the functions f_{a} there exist for each {k_{a}}_{a∈A}, k_{a} > 0, each ε > 0 and some fixed ā ∈ A a point x ∈ S such that

fā(x) ≤ inf_{y∈S} fā(y) + ε.

So we have x ∈ E^{εk}(A, S).

References

[1] E. Carrizosa and F. Plastria: Geometrical Characterization of Weakly Efficient Points. J. Optim. Theory Appl. 90 (1), 217-223, 1996.

[2] F. H. Clarke: Optimization and nonsmooth analysis. Reprint. Classics in Applied Mathematics, 5. Philadelphia, PA: SIAM, 1990.

[3] Chr. Tammer: A generalization of Ekeland’s variational principle. Optimization 25, 129-141, 1992.

[4] J. Jahn: Mathematical Vector Optimization in Partially Ordered Linear Spaces. Verlag Peter Lang, 1986.

[5] H. W. Kuhn: On a pair of dual nonlinear programs. In: J. Abadie (ed.), Nonlinear programming, 37-54, North-Holland, Amsterdam, 1967.

[6] D. V. Luu, W. Oettli: Necessary optimality conditions for non-smooth minimax problems. Z. Analysis Anwend. 12, 709-721, 1993.

[7] V. N. Solovev: The subdifferential und the directional derivatives of the maximum of a family of convex functions. Izv. Math., 62 (4), 807-832, 1998; transl. from Izv. Ross. Akad. Nauk., Ser. Mat. 62 (4), 173-200, 1998.