Journal of Convex Analysis Volume 1 (1994), No. 2, 143–150

Structure of Efficient Sets for Strictly Quasi Convex Objectives

C. Malivert, N. Boissard

LACO (URA 1586) - Département de Mathématiques, Faculté des Sciences, 123 Avenue Albert Thomas, F-87060 Limoges Cedex, France. e-mail: malivert@cict.fr, boissard@unilim.fr

Received 7 February 1994 Revised manuscript received 13 October 1994

This paper studies the weak efficient set (WEff P) of a minimization problem P with k objectives defined on a convex set X of IR^{n}. These objectives are continuous and belong to the class of so-called strictly quasiconvex functions, which contains, in particular, convex as well as linear fractional functions. When k is greater than n, it is of interest to replace the original problem by several subproblems, having at most n objectives. We show that if WEff P is bounded, the knowledge of the efficient sets of such subproblems, completely determines WEff P.

Keywords : Multiple objectives, Efficient sets, Quasiconvexity, Fractional programming.

1991 Mathematics Subject Classification: 90C31 90C32

1. Introduction

We consider the multiobjective problem

(P)  min_{x∈X}(f_{1}, ⋯, f_{k})

where X is a closed convex set in IR^{n}, f_{i} : X ⟶ IR, i = 1, ⋯, k and we focus our attention on the structure of the weak efficient set WEff P. In [7], it is shown that if the objectives are continuous and convex, the set WEff P is determinable from the spatial structure of the efficient sets of subproblems having at most n objectives. The purpose of this paper is to extend these results to a class of non convex objectives. Namely, we consider the class of strictly quasiconvex functions, which has been previously introduced in [2]. This class contains in particular convex functions as well as linear fractional functions, which gives a wide range of applications. See for instance [5][6] for many examples and an extensive bibliography on fractional programming in the scalar case. The paper is divided into two sections. In section 2 we state the problem and give definitions used in the sequel. In section 3 we extend several results, known in the convex case, to the strictly quasiconvex case. Then we deduce Theorem 3.7, which is the main result of this paper.

ISSN 0944-6532 / $ 2.50 ◯^{c} Heldermann Verlag

144 C. Malivert, N. Boissard / Structure of efficient sets

2. Basic concepts

Recall that X being a convex set in IR^{n}, a functional f : X ⟶ IR is quasiconvex on X iff for all points x, y in X and λ ∈ [0, 1]

f(λx + (1 − λ)y) ≤ max(f(x), f(y)).

This class has been extensively studied in the literature, see for instance [1] for many examples, properties and a bibliography. We say that f : X ⟶ IR is strictly quasiconvex [2] iff for every x, y in X and λ ∈]0, 1[ one has :

f(λx + (1 − λ)y) < max(f(x), f(y)) if f(x) ≠ f(y)

and

f(λx + (1 − λ)y) ≤ f(x) if f(x) = f(y)·

In particular, linear fractional functions of the form f(x) = \frac{a.x + s}{b.x + t} where a, b ∈ IR^{n} and

s, t ∈ IR, are strictly quasiconvex on every convex set X contained in their domain. (Here . stands for the scalar product in IR^{n}) Convexity implies strict quasiconvexity and strict quasiconvexity implies quasiconvexity.

As an immediate consequence of the definition, it is easy to prove that if x = ∑_{i=1}^{l} λ_{i}x_{i}, λ_{i} >

0, i = 1, ⋯, l, ∑_{i=1}^{l} λ_{i} = 1, and f(x_{i}) ≤ z for i = 1, ⋯, l then f(x) < z whenever

{f(x_{i}) : i = 1, ⋯, l} is not a singleton. Consider the problem

(P)  min_{x∈X} F (x)

with F = (f_{1}, ⋯, f_{k}), each f_{i}, i = 1, ⋯, k being strictly quasiconvex. We refer to a subproblem P_{I} of P when only a nonempty subset I ⊂ {1, ⋯, k} of all objectives, is considered. The notation |I| stands for the cardinality of I. Recall that the sets of minimal points and weakly minimal points of P are defined by

MinF (X) = {z ∈ F (X) : (z − F (X)) ∩ (IR_{+}^{k}\{0}) = ∅}
W MinF (X) = {z ∈ F (X) : (z − F (X)) ∩ int IR_{+}^{k} = ∅}·

The corresponding efficient sets in the argument space are:

Eff P = {x ∈ X : F (x) ∈ MinF (X)}
WEff P = {x ∈ X : F (x) ∈ W MinF (X)}.

3. Determination of WEff P

In 1984, Lowe et al.[3] showed that, when all objectives are convex, WEff P is the union of efficient sets of all subproblems P_{I} , I ⊂ {1, ⋯, k}, I ≠ ∅. At first we give a similar result in the strictly quasiconvex case.

Theorem 3.1. Suppose that all objectives f_{i}, i = 1, ⋯, k are strictly quasiconvex and upper semicontinuous along line segments in X then

WEff P = ∪{Eff P_{I} : I ⊂ {1, ⋯, k}, I ≠ ∅}

Proof. Consider x ∈ X such that x ∉ WEff P. There exists y ∈ X with f_{i}(y) < f_{i}(x) for all i and then, for each I ⊂ {1, ⋯, k}, x ∉ Eff P_{I}. Now, suppose that x ∉ ∪{Eff P_{I} : I ⊂ {1, ⋯, k}, I ≠ ∅}. Taking I = {1, ⋯, k}, there must exist i_{1} ∈ I and x_{1} ∈ X such that

f_{i_{1}}(x_{1}) < f_{i_{1}}(x) and f_{i}(x_{1}) ≤ f_{i}(x), i ∈ I.  (1)

Now if I = I_{1} = {1, ⋯, k}\{i_{1}}, there are i_{2} ∈ I_{1} and x_{2} ∈ X such that

f_{i_{2}}(x_{2}) < f_{i_{2}}(x) and f_{i}(x_{2}) ≤ f_{i}(x), i ∈ I_{1}.  (2)

Setting y_{2} = λx_{1} + (1 − λ)x_{2}, λ ∈]0, 1[, and using the upper semicontinuity of f_{i_{1}} on the segment [x_{1}, x_{2}] , we have by (1), for (1 − λ) small enough,

f_{i_{1}}(y_{2}) < f_{i_{1}}(x).

On the other hand, the strict quasiconvexity of f_{i_{2}} implies, for each λ ∈]0, 1[

f_{i_{2}}(y_{2}) < f_{i_{2}}(x).

Further from the quasiconvexity of f_{i} ’s , we have for each λ ∈]0, 1[

f_{i}(y_{2}) ≤ f_{i}(x), i ∈ I_{2} = {1, ⋯, k}\{i_{1}, i_{2}}·

Suppose now, that we have obtained y_{ℓ} and I_{ℓ} = I\{i_{1}, ⋯, i_{ℓ}} such that f_{i}(y_{ℓ}) < f_{i}(x), i ∈ {i_{1}, ⋯, i_{ℓ}} and f_{i}(y_{ℓ}) ≤ f_{i}(x), i ∈ I_{ℓ}. Using x ∉ Eff P_{I_{ℓ}} we get i_{ℓ+1} ∈ I_{ℓ} and x_{ℓ+1} ∈ X satisfying

f_{i_{ℓ+1}}(x_{ℓ+1}) < f_{i_{ℓ+1}}(x) and f_{i}(x_{ℓ+1}) ≤ f_{i}(x), i ∈ I_{ℓ}·

Then from the upper semicontinuity of f_{i_{1}}, ⋯, f_{i_{ℓ}} on the segment [y_{l}, x_{ℓ+1}], the strict quasiconvexity of f_{i_{ℓ+1}} and the quasiconvexity of other objectives, we obtain y_{ℓ+1}, a convex combination of y_{ℓ} and x_{ℓ+1}, such that

f_{i}(y_{ℓ+1}) < f_{i}(x), i ∈ {i_{1}, ⋯, i_{ℓ+1}}

and

f_{i}(y_{ℓ+1}) ≤ f_{i}(x), i ∈ I_{ℓ+1} = I\{i_{1}, ⋯, i_{ℓ+1}}.

As the number of objectives is k, we obtain finally y_{k} ∈ X such that f_{i}(y_{k}) < f_{i}(x), i ∈ {1, ⋯, k}, which means that x ∉ WEff P.

Note that convex functions are automatically upper semicontinuous along line segments and also that the previous theorem remains valid if X ⊂ E, where E is a linear space without topology. Now, following an idea developped by Ward [7] in the convex case, which uses Helly’s Theorem, we give an extension of Theorem 3.1 when n < k.

Helly’s Theorem : Let C_{i}, i = 1, ⋯, m be a collection of convex sets in IR^{n}. If every subcollection of n + 1 or fewer of these C_{i} has a nonempty intersection, then the entire collection of the m sets has a nonempty intersection.

Theorem 3.2. Suppose that f_{i}, i = 1, ⋯, k are strictly quasiconvex and upper semicontinuous along line segments, then

WEff P = ∪{Eff P_{I} : I ⊂ {1, ⋯, k}, I ≠ ∅, |I| ≤ n + 1}

Proof. From Theorem 3.1 it is sufficient to consider the case k > n + 1 and to prove the inclusion ⊂. Consider x ∉ ∪{Eff P_{I} : I ⊂ {1, ⋯, k}, I ≠ ∅, |I| ≤ n + 1}. Then for each J ⊂ {1, ⋯, k}, J ≠ ∅ with |J| ≤ n + 1, we have x ∉ ∪{Eff P_{I} : I ⊂ J, I ≠ ∅} and from Theorem 3.1, it follows that x ∉ WEff P_{J}. Therefore there exists

x_{J} ∈ X such that f_{j}(x_{J}) < f_{j}(x) for all j ∈ J.  (3)

For each i ∈ {1, ⋯, k} we define the closed convex set

C_{i} = conv{x_{J} : J ⊂ {1, ⋯, k}, J ≠ ∅, |J| ≤ n + 1, i ∈ J}.

It is clear from (3) that, for all J ⊂ {1, ⋯, k} with J ≠ ∅, |J| ≤ n + 1, i ∈ J, we have f_{i}(x_{J}) < f_{i}(x) and the quasiconvexity of f_{i} entails that for every y ∈ C_{i}

f_{i}(y) < f_{i}(x).  (4)

Now, for a fixed J with |J| ≤ n + 1, the collection {C_{i} , i ∈ J} has x_{J} in common and

from Helly’s Theorem, there exists some y^{∗} belonging to ⋂_{i=1}^{k} C_{i}. Thus from (4), for each

i ∈ {1, ⋯, k}

f_{i}(y^{∗}) < f_{i}(x)

and x ∉ WEff P.

Recall that if C ⊂ IR^{n}, dim C denotes the dimension of the affine space generated by C. The following lemma will be useful in the sequel.

Lemma 3.3. Let C = conv{y_{i} ∈ IR^{n} : i = 1, ⋯, n + 1}. Suppose that there exists x ∈ C which cannot be written as a convex combination of fewer than n + 1 points y_{i}, then dim C = n and x ∈ int C.

Proof. Suppose that dim C ≤ n − 1. By Carathéodory’s Theorem [4] , every point of C can be expressed as a convex combination of n elements y_{i}. This is a contradiction with

the assumption about x. It remains to prove that x ∈ int C. Suppose that x = ∑_{i=1}^{n+1} λ_{i}y_{i},

with all λ_{i} > 0. As dim C = n, the vectors y_{n+1} − y_{i}, i = 1, ⋯, n are independent. We consider the neighborhood of 0 in IR^{n} defined by

N = {z : z = ∑_{i=1}^{n} γ_{i}(y_{n+1} − y_{i}) , |γ_{i}| < λ_{i} i = 1, ⋯, n, | ∑_{i=1}^{n} γ_{i}| < λ_{n+1}}.

We have for every z ∈ N,

x + z = ∑_{i=1}^{n}(λ_{i} − γ_{i})y_{i} + (λ_{n+1} + ∑_{i=1}^{n} γ_{i})y_{n+1} ∈ C.

Thus x + N ⊂ C and x ∈ int C.

Lemma 3.4. Suppose that x ∈ WEff P_{J} and that for every j ∈ J there exists y_{j} such that

f_{i}(y_{j}) < f_{i}(x), i ∈ J\{j},  (5)

then

x ∈ int C where C = conv{y_{j} : j ∈ J}·

Proof. For each j ∈ J, consider the closed, convex subset of X,

C_{j} = conv{y_{k} : k ∈ J\{j}}.

Obviously, by (5), f_{j}(y_{k}) < f_{j}(x) for k ∈ J\{j} and the quasiconvexity of f_{j} implies

∀y ∈ C_{j}  f_{j}(y) < f_{j}(x).  (6)

From (6), for all j ∈ J , x ∉ C_{j} and since x ∈ WEff P_{J} we have ∩{C_{j} : j ∈ J} = ∅.

Now let us define C′_{j} = conv(C_{j}, {x}) for j ∈ J.

The intersection of n + 1 of the sets {(C′_{j})_{j∈J}, C} is nonempty. Indeed, all C′_{j} contain x and if we take a collection of the form {(C′_{j})_{j∈J\{j_{0}}}, C}, all of these sets contain y_{j_{0}}.

Applying Helly’s Theorem, there exists z ∈ (⋂_{j∈J} C′_{j}) ⋂ C. If z ≠ x, then for each

j ∈ J, z = λ_{j}x+(1−λ_{j})y, with λ_{j} ∈ [0, 1[, y ∈ C_{j}. From (6) and the strict quasiconvexity of f_{j}, for each j ∈ J, f_{j}(z) < f_{j}(x) which contradicts x ∈ WEff P_{J}. Thus z = x and

x ∈ C. Thus we can write x = ∑_{j∈J} λ_{j}y_{j}, λ_{j} ≥ 0, ∑_{j∈J} λ_{j} = 1.

Suppose that λ_{j_{0}} = 0 for some j_{0} ∈ J. By definition of y_{j}, f_{j_{0}}(y_{j}) < f_{j_{0}}(x), for all j ∈ J\{j_{0}} and f_{j_{0}} being quasiconvex, f_{j_{0}}(x) ≤ max(f_{j_{0}}(y_{j}), j ∈ J\{j_{0}}) < f_{j_{0}}(x), a contradiction. Thus every λ_{j} is strictly positive and using Lemma 3.3 we conclude x ∈ int C.

It is well known that the continuity of f_{i}’s implies that WEff P is a closed set. Let us denote by bd(WEff P) the boundary of WEff P.

Theorem 3.5. Suppose that f_{i}, i = 1, ⋯, k are strictly quasiconvex and continuous. Then

bd(WEff P) ⊂ ∪{Eff P_{I} : I ⊂ {1, ⋯, k}, I ≠ ∅, |I| ≤ n}.

Proof. By Theorem 3.1 it is sufficient to consider the case k > n. Suppose that x ∈ bd(WEff P) \ ∪ {Eff P_{I} : I ⊂ {1, ⋯, k}, I ≠ ∅, |I| ≤ n}. Using Theorem 3.2 we have x ∈ Eff P_{J} for some J ⊂ {1, ⋯, k}, with |J| = n+1 and x ∉ Eff P_{J′} for all J′ ⊂ J, J′ ≠ ∅, J′ ≠ J. In particular for every j ∈ J, x ∉ ∪{Eff P_{J′} : J′ ⊂ J\{j}, J′ ≠ ∅}. But from Theorem 3.1 , this latter set is WEff P_{J\{j}}. Thus

∀j ∈ J ∃y_{j} ∈ X f_{i}(y_{j}) < f_{i}(x), i ∈ J\{j}.

It follows from Lemma 3.4 that x ∈ int C, where C = conv{y_{j} : j ∈ J}. From Lemma 3.3, each y ∈ bd C can be written as a convex combination of only n points y_{j}, say {y_{j} : j ∈ J\{i}} and by the quasiconvexity of f_{i}, f_{i}(y) < f_{i}(x). It follows that

∀y ∈ bd C max_{j∈J}(f_{j}(x) − f_{j}(y)) > 0·  (7)

As max_{j∈J}(f_{j}(x) − f_{j}(y)) is continuous with respect to y, it achieves its minimum on the

compact set bd C. Denote by m = min_{y∈bd C} max_{j∈J}(f_{j}(x) − f_{j}(y)) , we have m > 0.

Now consider the neighborhood of x in IR^{n} defined by

V = {y ∈ C : max_{j∈J}(f_{j}(x) − f_{j}(y)) < m}·

Note that by the definition of m, V ∩ bd C = ∅ and then V ⊂ int C. We show that V ⊂ Eff P_{J}. Suppose on the contrary that y ∈ V \Eff P_{J}. Then

∃u ∈ X (f_{i}(y) − f_{i}(u))_{i∈J} ∈ IR_{+}^{n}\{0}·  (8)

As y ∈ int C and C being a compact set, we can find t_{0} = max{t > 0 : y + t(y − u) ∈ C}. We have z = y + t_{0}(y − u) ∈ bd C and by (7), there exists i_{0} ∈ J such that

f_{i_{0}}(x) − f_{i_{0}}(z) ≥ m > 0·  (9)

As y ∈ V we have also f_{i_{0}}(x) − f_{i_{0}}(y) < m and with (9)

f_{i_{0}}(y) − f_{i_{0}}(z) > 0·  (10)

Now using the fact that y is a convex combination of u and z, and the strict quasiconvexity of f_{i_{0}}, we get either f_{i_{0}}(u) = f_{i_{0}}(z) ≥ f_{i_{0}}(y), which contradicts (10), or

f_{i_{0}}(u) ≠ f_{i_{0}}(z) and f_{i_{0}}(y) < max(f_{i_{0}}(u), f_{i_{0}}(z)).  (11)

But f_{i_{0}}(y) > f_{i_{0}}(z) by (10) and then (11) entails f_{i_{0}}(y) < f_{i_{0}}(u), a contradiction with (8).

Thus we have proved that V ⊂ Eff P_{J}, which means that x ∈ int(Eff P_{J}). As Eff P_{J} ⊂ WEff P_{J}, we have got a contradiction with the assumption x ∈ bd(WEff P_{J}) and the proof is complete.

In the following we adopt the notations of Ward [7] :

r[x, v] = {x + tv : t ≥ 0} x ∈ X, v ∈ IR^{n},
U(P, n) = ∪{Eff P_{I} : I ⊂ {1, ⋯, k}, I ≠ ∅, |I| ≤ n}
S(P, n) = {x ∈ X\U(P, n) : ∀v ≠ 0, r[x, v] ∩ U(P, n) ≠ ∅}.

The result of (lemma 4, [7]) remains true in the strictly quasiconvex case.

Lemma 3.6. Suppose that f_{i}, i = 1, ⋯, k are strictly quasiconvex, then S(P, n) ⊂ Eff P.

Proof. Assume that x ∈ S(P, n)\Eff P. Then, there exists y ∈ X such that

(f_{i}(x) − f_{i}(y))_{i=1,···,k} ∈ IR_{+}^{k}\{0}

and we can find z ∈ r[x, x − y] ∩ U(P, n). As x ≠ z and x ≠ y, x = λz + (1 − λ)y with λ ∈]0, 1[. If f_{i}(y) = f_{i}(z) then the strict quasiconvexity of f_{i} implies f_{i}(x) ≤ f_{i}(z). If f_{i}(y) ≠ f_{i}(z) the strict quasiconvexity of f_{i} implies f_{i}(x) < max(f_{i}(y), f_{i}(z)) and with f_{i}(x) ≥ f_{i}(y) one has f_{i}(x) < f_{i}(z). Therefore, in all cases, f_{i}(x) ≤ f_{i}(z), i = 1, ⋯, k. As z ∈ Eff P_{I} for some I such that |I| ≤ n, we get also x ∈ Eff P_{I} , contradicting x ∉ U(P, n).

Theorem 3.7. Let f_{i}, i = 1, ⋯, k be strictly quasiconvex, continuous functions and suppose that WEff P is bounded, then WEff P = U(P, n) ∪ S(P, n).

Proof. The inclusion ⊃ is clear from Lemma 3.6 and Theorem 3.2. For ⊂ observe that WEff P = bd(WEff P) ∪ int(WEff P). From Theorem 3.5 follows bd(WEff P) ⊂ U(P, n). Now we prove that int(WEff P)\U(P, n) ⊂ S(P, n). Consider x ∈ int(WEff P)\U(P, n) and an halfline r[x, v]. Since WEff P is bounded, there exists z ∈ r[x, v] ∩ bd(WEff(P)), z ≠ x. By Theorem 3.5, z ∈ r[x, v] ∩ U(P, n) and then x ∈ S(P, n).

4. Conclusion

The subset S(P, n) is a kind of convex hull of U(P, n) and the knowledge of U(P, n) completely determines S(P, n). Thus it is sufficient to solve subproblems P_{I} with at most n criteria, to obtain WEff P. In IR^{2} a graphical representation of WEff P can be obtained, even with a great number of criteria, as soon as bicriteria subproblems can be solved.

Acknowledgment. The authors wish to thank anonymous referees for their careful checking and their helpful suggestions that improved the quality of this paper.

References

[1] J.P. Crouzeix: Contribution à l’étude des fonctions quasi-convexes, Thèse de doctorat, U.E.R. des Sciences, Université de Clermont-Ferrand II, 1977, France.

[2] N. Popovici: Sur une notion de quasi-convexité pour des fonctions vectorielles, (préprint)

[3] T.J. Lowe, J.-F. Thisse, J.E. Ward and R.E. Wendell: On efficient solutions to multiple objective mathematical programs. Management Sci. 30, 1984, 1346–1349.

[4] R.T. Rockafellar: Convex Analysis. Princeton University Press, 1970, Princeton N.J.

[5] S. Schaible: Bibliography in fractional programming. Zeitschrift für Operations Research 26, 1982, 211–241.

[6] S. Schaible: A survey of fractional programming in : S. Schaible and W.T. Ziemba eds., Generalized Concavity in Optimization and Economics, (Acad. Press, New York 1981), 417–440.

[7] J. Ward: Structure of efficient sets for convex objectives. Math. of Oper. Res. 14, 1989, 249–257.