Dominators for multiple-objective quasiconvex maximization problems

Journal of Global Optimization 18: 35–58, 2000. 35 2000 Kluwer Academic Publishers.Printed in the Netherlands. Dominators for Multiple-objective Quasiconvex Maximization Problems 1, 2 * EMILIO CARRIZOSA and FRANK PLASTRIA 1 ´ Facultad de Matematicas,Universidad de Sevilla,C/Tarfia s/n, 41012 Sevilla,Spain E-mail : [email protected] 2 Department of Management Informatics,Vrije Universiteit Brussel,Pleinlaan, 2, B1050 Brussels, Belgium (E-mail : [email protected]) (Received 19 January 1998; accepted in revised form 6 January 2000) Abstract. In this paper we address the problem of finding a dominator for a multiple-objective maximization problem with quasiconvex functions. The one-dimensional case is discussed in some detail, showing how a Branch-and-Bound procedure leads to a dominator with certain minimality properties. Then, the well-known result stating that the set of vertices of a polytope Scontains an optimal solution for single-objective quasiconvex maximization problems is extended to multipleobjective problems, showing that, under upper-semicontinuity assumptions, the set of (k⫺1)- dimensional faces is a dominator for k-objective problems. In particular, for biobjective quasiconvex problems on a polytope S, the edges of Sconstitute a dominator, from which a dominator with minimality properties can be extracted by Branch-and Bound methods. Key words: Multiple-objective problems; Quasiconvex maximization; Dominators 1. Introduction nnk Given a nonempty closed subset Sof ⺢and a function F:S傺⺢→⺢, define the multiple-objective problem (P[F;S]), max F(x), (P[F;S]) x僆S which seeks those alternatives maximizing simultaneously the components F,F,...,Fof F, [7, 28, 31]. 12 k Although the term simultaneous maximization is not uniquely defined, it customarily means finding the set Ᏹ [F;S]ofefficient or Pareto-optimal solutions to (P[F;S]), Ᏹ [F;S]⫽兵x僆S:noy僆Sverifies F(y)⭓F(x)᭙i⫽1, 2, . . . , k ii with at least one inequality strict其 In general Ᏹ [F;S] lacks many desirable properties such as being connected or closed, and this seems to be quite often the case and not only in pathological ´ * The research of this author is partially supported by Grant PB96-1416-C02-02 of Direccion General de ˜ Ensenanza Superior, Spain. 36 EMILIO CARRIZOSA AND FRANK PLASTRIA Figure 1 . Biobjective convex maximization. examples: take, for instance, the biobjective convex maximization problem in one 22 variable (n⫽1, k⫽2) with F(x)⫽((x⫹1) , (x⫺1) ) and S⫽[⫺2, 1.5], plotted in Figure 1. Since F(⫺2)⭓F(x)᭙x僆]⫺2, 0], with at least one inequality strict, and F(1.5)⭓F(x)᭙x僆[0.5, 1.5[, with at least one ineuality strict too, it follows that the set of Pareto-optimal points must be contained in 兵⫺2其傼]0, 0.5[傼兵1.5其. In fact, it is readily seen from the plot that Ᏹ [F;S]⫽兵⫺2其傼]0, 0.5[傼兵1.5其, which is a disconnected non-closed set. See following sections and also e.g. [3] for other instances. Moreover, although there exist procedures to check whether a given point is efficient or not, e.g. [7, 31], an algorithm to construct Ᏹ [F;S] is only available for a few classes of problems, such as multiple-objective linear problems, [28]. This drawback has been overcome in the literature by means of two strategies: either Ᏹ [F;S] is sought, but, due to the unability for obtaining it, an approximation (sometimes with unknown degree of precision) is provided, e.g. [8, 18], or else the concept of efficiency is relaxed and replaced by a manageable surrogate of it. In this paper we follow the second approach by using the concept of dominator, [5, 16, 21, 30], also called weak kernel, e.g. in [31] which is defined as any subset S傺Ssuch that, for any feasible x僆 ⁄ S,Scontains a feasible alternative at least as 000 good as xwith respect to all objectives. See Section 2 for a formal definition. It should be remarked that this concept is not only useful as a surrogate of the idea of Pareto-efficiency, but also as a tool in the resolution of some single-objective problems. Indeed, some of the most popular optimization methods for singleobjective problems of the form MULTIPLE-OBJECTIVE QUASICONVEX MAXIMIZATION 37 max ⌿(x) (1.1) x僆S require the feasible region Sto be bounded. Such is the case, among others, of the Branch and Bound methods for global optimization, e.g. [15], which, in their simplest version, require, as pre-processing, the construction of a bounded polyhedron P(usually a hyper-rectangle, or a simplex) including either the whole feasible region, or, at least a bounded subset S傺Sknown to contain an optimal 0 solution. Moreover, the speed of convergence of the procedure is known to deteriorate with the volume of P,soPshould be as small as possible in order to obtain reasonable computation times. How to construct Pwill depend, of course, on the specific properties of the problem at hand. In particular, if (1.1) has the form max ⌽(F(x)) , (1.2) x僆S for some ⌽:F(S)→⺢componentwise non-decreasing, then it is well known that, if (1.1) has optimal solutions, then any dominator for the multiple-objective problem max F(x) also contains optimal solutions for (1.1), [21]. In other words, we can x僆S take as Sany bounded dominator for the multiple-objective problem, and as Pany 0 superset of Swith the required geometry. 0 This property has been successfully exploited, among others, in [5, 21, 22, 30] for problems of Linear Regression and Continuous Location, in which the globalizing function ⌽is an arbitrary non-decreasing function and the function Fis componentwise concave. Our aim here is to address the (harder) problem in which the function Fis componentwise (quasi)-convex, showing as main result (Proposition 19) that, under upper-semicontinuity assumptions, the search of a dominator can be restricted to the (k⫺1)-dimensional faces of S. The rest of this paper is structured as follows. In Section 2 we formally introduce the concept of dominators and discuss some general properties. These properties are used in Section 3 to address the one-dimensional case, for which dominators with certain minimality properties can be obtained. Section 4 is devoted to show that, for multiple-objective multi-dimensional problems, one can construct dominators contained in low dimensional faces of the polytope S. The paper ends with an application of these results to the construction of a dominator for a biobjective problem in Continuous Location. The reader is referred also to [25] for another successful application of the technique developed in this paper. 2. Dominators ⭓ Defining for each x僆Sthe upper level set at xof Fon S, ᏿ (x)as ⭓ ᏿ (x)⫽兵y僆S:F(y)⭓F(x) for all i⫽1,2,...,k其, ii 38 EMILIO CARRIZOSA AND FRANK PLASTRIA the set Ᏹ [F;S] of efficient solutions may be defined by ⭓⭓ Ᏹ [F;S]⫽兵x僆S:Ify僆 ᏿ (x) then x僆 ᏿ (y)其 ⭓ ⫽兵x僆S:Ify僆 ᏿ (x) then F(x)⫽F(y)其 DEFINITION 1. A set S*傺S is said to be a dominator for (P[F;S]) iff for each x僆S there exists some x*僆S*which has,componentwise,a value not smaller than x.In other words,S*is a dominator iff ⭓ (᭙x僆S)᭚x*僆 ᏿ (x)傽S* Hereafter,the class of dominators for (P[F;S]) will be denoted by Ᏸ [F;S]. A direct consequence of the definition is the following: PROPOSITION 2. One has 1. S僆 Ᏸ [F;S]. In particular, Ᏸ [F;S]is nonempty. 2. If D 僆 Ᏸ [F;S]and D*satisfies D 傺D*傺S,then D*僆 Ᏸ [F;S]. n 3. For any class 兵S:j僆J其of nonempty sets in ⺢, j If S*僆 Ᏸ [F;S](᭙j僆J)then 傼S*僆 Ᏸ F;傼S 冋册 jj j j j僆Jj僆J n 4. For any class 兵S:j僆J其of nonempty sets in ⺢, j 傽 Ᏸ [F;S]傺 Ᏸ F;傼S 冋册 jj j僆Jj僆J 5. If D 僆 Ᏸ [F;S], then Ᏸ [F;D]傺 Ᏸ [F;S]. By Proposition 2, the class Ᏸ [F;S] is nonempty since the whole feasible set Sis one of its elements. However Sdoes not seem to be the most appropriate dominator since it possibly contains (too) many dominated alternatives, being too far from the ideal aim of a smallest possible dominator. PROPOSITION 3. Suppose each F is upper-semicontinuous on S,then any class of j compact nested dominators is closed under intersections.In other words : if (I,Ɱ)is ᎐ a totally ordered set,and 兵D其is a class of compact dominators with D 傺D, ii僆Iij j僆I,iⱮj,then ᎐ 傽D僆 Ᏸ [F;S]. i i僆I Proof. Take any x僆S. By the upper-semicontinuity of the functions F, all upper j level sets 兵y僆S:F(y)⭓F(x)其are closed, so their intersection ᏿ ⭓(x) is also jj closed. By the definition of dominators and their compactness, it follows for each ⭓⭓ i僆Ithat ᏿ (x)傽Dis a nonempty compact set, thus 兵 ᏿ (x)傽D其constitutes a iii僆I MULTIPLE-OBJECTIVE QUASICONVEX MAXIMIZATION 39 ⭓ class of nested compact sets. By compactness their intersection (i.e., ᏿ (x)傽 傽D) is nonempty. i僆Ii However, it is evident that the whole class Ᏸ [F;S] is not closed under intersections (take constant functions F,...,F, then any singletons 兵x其,兵y其傺Sare 1k dominators, with empty intersection). Hence, a unique smallest dominator is unlikely to exist. We then relax the idea of smallest dominator by introducing the concept of (weak) minimal dominators. First define for each x僆Sthe strict upper ⬎ level set of Fon S, ᏿ (x)as ⬎ ᏿ (x)⫽兵y僆S:F(y)⬎F(x) for all i⫽1,2,...,k其. ii DEFINITION 4. A dominator S*is said to be minimal for (P[F;S]) iff no proper subset of S*belongs to Ᏸ [F;S]. In other words,S*傺S is minimal iff ⭓ (x,y僆S*, x⫽ ⁄ y)⇒x僆 ⁄᏿ (y) A dominator S*傺S is said to be weak minimal for (P[F;S]) iff ⬎ (x,y僆S*)⇒x僆 ⁄᏿ (y) The class of minimal ( respectively weak minimal ) dominators for problem (P[F;S]) will be denoted by Ᏸ [F;S](respectively Ᏸ [F;S]). MWM As a simple illustration of the concepts, consider the 2-dimensional 2-objective optimization problem max F(x), depicted in Figure 2, where the feasible region S x僆S 2 is the polyhedron in ⺢with vertices a⫽(0, ⫺3), b⫽(4, ⫺1), c⫽(4, 0), d⫽(0,3), and Fis given by F(x,x)⫽x 11 2 1 F(x,x)⫽兩x兩 21 2 2 Then, the Pareto optimal set is given by Ᏹ [F;S]⫽兵d其傼[a,b], Figure 2 .Sand F(S). 40 EMILIO CARRIZOSA AND FRANK PLASTRIA only two minimal dominators exist, namely S⫽[a,b] 1 S⫽]a,b]傼兵d其, 2 whereas the polygonal S, 3 S⫽兵d其傼[a,b]傼[b,c] 3 is also weak minimal. We observe in this example that the two minimal dominators are proper subsets of Ᏹ [F;S]. This result is more general, as stated in the following: PROPOSITION 5. Suppose that S is compact and each F is upper semicontinuous i on S.Then 1. Ᏹ [F;S]is a weak minimal dominator. 2. Minimal dominators exist. 3. Ᏹ [F;S]⫽傼S*. S*僆 Ᏸ [F;S] M ⭓ Proof. By the upper-semicontinuity assumption, for each x僆Sthe set ᏿ (x)is compact. Hence, by Theorem 6 of Chapter 2 of [31] Ᏹ [F;S] is a dominator, which, by construction, is also weak minimal. Hence 1 holds. To show 2, define on Ᏹ [F,S] the equivalence relation ␳ ⫽兵(x,y)僆 Ᏹ [F;S]⫻ Ᏹ [F;S]:F(x)⫽F(y)其. Taking exactly one element in every equivalence class, we obtain a set S* which is, by construction, a minimal dominator. Indeed, it is a dominator because Ᏹ [F;S]isa dominator, as shown in Part 1. Moreover it is minimal: if there exists some dominator M傺S*, M苷S*, for any x僆S*\Mthere would exist some y僆Mwith F(y)⭓F(x). But by construction of S* we would have F(y)苷F(x) contradicting the fact that xis efficient. Hence, minimal dominators exist. For Part 3, we first show that every efficient point is in some minimal dominator: let x*僆 Ᏹ [F;S], and construct a subset S*of Ᏹ [F;S] taking exactly one element of every equivalence class (with respect to the equivalence relation ␳ above), x* being the element chosen from its equivalence class. Using the reasoning above, it is seen that S* is a minimal dominator, and x*僆S*. Finally to show that any minimal dominator is included in the efficient set, take x*僆S*, for some S*僆 Ᏸ [F;S], and assume x*僆 ⁄Ᏹ [F;S]. Then, there exists M some y僆Swith F(y)⭓F(x), and at least one inequality strict. Since S*僆 Ᏸ [F;S], M there must exist some y*僆S* with F(y*)⭓F(y)⭓F(x*), thus the set S*\兵x*其will also be a dominator, contradicting the minimality of S*. Hence, x*僆 Ᏹ [F;S]. 䊐 REMARK 6. The upper-semicontinuity assumption is needed in order to guarantee 2 the nonvoidness of Ᏸ [F;S], as the following counterexample shows: Let S傺⺢ WM be the triangle whose endpoints are (⫺1, 0), (1, 0), (0, 1), and let F:S→⺢be 1 MULTIPLE-OBJECTIVE QUASICONVEX MAXIMIZATION 41 defined as 1/(1⫺x) on the relative interior of the two top-edges, and zero 2 elsewhere. Since lim F(x,x)⫽⫹⬁, 11 2 (x,x)→(0, 1), 12 (x,x)僆bd(S) 12 the maximum of Fon Sis not attained, thus any D僆 Ᏸ [F;S] must contain a 11 sequence of boundary points converging to (0, 1), implying that Dcontains points x,ywith F(x)⬎F(y). Hence, no weak minimal dominator exists. 䊐 11 3. Multiple-objective one-dimensional problems In this section we address the multiple-objective problem (P[F;S]) when Sis given as a finite union of compact intervals in ⺢, and each Fis quasiconvex on each i interval. We first discuss some properties of one-dimensional single-objective quasiconvex minimization problems, which are then used to tackle (P[F;S]), first when Sreduces to a single compact interval and then in the general case. For the basic properties of quasiconvex functions we refer the reader to [1]. 3.1. SINGLE-OBJECTIVE QUASICONVEX MINIMIZATION PROBLEMS ON AN INTERVAL Let I傺⺢be a nonempty compact interval, and let g:I→⺢be quasiconvex. We will denote by cl gthe closure of grelative to I, namely I cl g(x)⫽inf 兵t:᭚兵x其傺I, such that x→x,g(x)→t其 Irr r r (3.3) ⫽lim inf g(x) r x→x r LEMMA 7. One has : 1. g(x)⭓cl g(x)for all x 僆I. I 2 . inf g(x)⫽inf cl g(x). x僆Ix僆II 3. cl g is quasiconvex and lower-semicontinuous. I 4. The set arg min cl g(x)of optimal solutions to min cl g(x)is a x僆IIx僆II nonempty compact subinterval of I. Proof. 1 to 3 immediately follow from the definition of quasiconvexity and (3.3). By the lower semicontinuity of cl g, the set arg min g(x) is compact and Ix僆I nonempty; since cl gis also quasiconvex, it follows that arg min cl g(x) is also Ix僆II convex, thus it is a compact interval, and Part 4 follows. 䊐 We recall that a function gis said to be semistrictly quasiconvex, [1], if it satisfies the following: g(a)⬍g(b)⇒g(c)⬍g(b) 冎 c僆]a,b[ The next lemma shows that, due to the quasiconvexity of g, the behavior of gand 42 EMILIO CARRIZOSA AND FRANK PLASTRIA cl gare closely related, the relationship being stronger for semistrictly quasiconvex I g: LEMMA 8. Let x*僆arg min cl g(x), and let z ,z僆I such that z 僆]x*, z[. x僆II12 12 One has : 1. g(z)⭐g(z). 12 2. If g is also semistrictly quasiconvex and g(z)⫽g(z), then 12 ]x*, z[傺arg min g(x). 2x僆I Proof. By definition of cl gand Part 2 of Lemma 7, one can take a sequence 兵x其 Ir in Iconverging to x* such that inf g(x)⫽inf g(x)⫽cl g(x*). rr x僆II Since z⬎x*, there exists rsuch that x⬍zfor all r⭓r, thus 10r10 z僆]x,z[ for all r⭓r 1r20 Given r⭓r, if it were the case that g(z)⬍g(z), then 021 g(z)⬍g(z) 21 ⭐max兵g(z), g(x)其 2r Hence, g(z)⭐g(x) for each r⭓rthus one would have 1r0 g(z)⬍g(z) 21 ⭐inf g(x) r r ⫽inf g(x), x僆I which is a contradiction. Hence, g(z)⭓g(z), which shows 1. 21 To show 2, by the quasiconvexity of git is enough to show that, if g(z)⫽g(z), 12 then 兵z,z其傺arg min g(x). Suppose that, on the contrary, g(z)⫽g(z)⬎ 12 x僆I12 inf g(x). Then, by Lemma 7, x僆I g(z)⫽g(z) 12 ⬎cl g(x*) , I and we could take a sequence 兵x其converging to x* with g(x) converging to rr cl g(x*) and g(x)⬍g(z) for each r. Since z僆]x*, z[, it would follow that Ir212 z僆]x,z[ for some r, thus, by the strict quasiconvexity of g,g(z)⬍g(z), which 1r212 would be a contradiction. Hence g(z)⫽g(z)⫽cl g(x*), showing that 12I [z,z]傺arg min g(x). 12 x僆I By the quasiconvexity of both gand cl g, and the optimality of x* and [z,z] for I12 min cl g(x), it then follows that x僆II [x*, z]傺arg min g(x), 1x僆I and the result holds. 䊐 MULTIPLE-OBJECTIVE QUASICONVEX MAXIMIZATION 43 Another interesting property, which will be exploited in the sequel, states that, once problem min cl g(x) has been solved, any problem inf g(x) with nested x僆IIx僆J feasible interval J傺Iis immediately solved. Indeed, denoting by i(J) the interior of J, one has: : PROPOSITION 9. Let J ⫽[a,b]傺I be two compact intervals in ⺢.One has : 1. cl g⭐cl gonJ,and IJ cl g(x)⫽cl g(x)for all x 僆i(J) (3.4) IJ 2. If (arg min cl g(x)) 傽i(J)苷5,then x僆II inf g(x)⫽min cl g(x) (3.5) I x僆Jx僆I 3. If (arg min cl g(x)) 傽i(J)⫽5,then x僆II inf g(x)⫽min兵g(a), g(b)其(3.6) x僆J Proof. Part 1 is a direct consequence of the definition of the closure of gand Lemma 7. For Part 2, let x*僆arg min cl g(x)傽i(J); then, by Parts 1, 2 of Lemma 7 and x僆II Part 1 of this proposition, min cl g(x)⫽cl g(x*) II x僆I ⫽cl g(x*) J ⫽min cl g(x) J x僆J ⫽inf g(x) x僆J ⭓inf g(x) x僆I ⫽min cl g(x) I x僆I Part 3 immediately follows from Lemma 8 if arg min cl g(x) contains points x僆II in I\J. In the remaining case, arg min cl g(x) consists of just one endpoint of J, x僆II say a. If a sequence 兵x其傺Jexists converging to awith g(x) converging to ii min cl g(x)⫽cl g(a), then the result follows from the definition of cl g. x僆III I Otherwise there exists x*⬍awith g(x*)⬍g(a) and then the quasiconvexity of g implies that, for any x僆J, g(x*)⬍g(a) ⭐max兵g(a), g(x)其, thus g(x)⭓g(a), showing (3.6). 䊐 50 EMILIO CARRIZOSA AND FRANK PLASTRIA F(0)⫽(2, 1.8000, 1) F(5)⫽(1.9730, 1.6000, 1) F(7)⫽(1.9964, 1.8824, 0.6000) F(9)⫽(1.9995, 1.9459, 0.2000) We then obtain IM(I)UB(I) 兵0其(2, 1.8000, 1) (2, 1.8000, 1) [5, 9] (1.9964, 1.8824, 0.6000) (1.9995, 1.9459, 1) We will only use the simplest test, namely, (3.8) in the algorithm. Since no pair of intervals in ᏸ satisfies condition (3.8), we go to Iteration 2 with the list of intervals ᏸ ⫽兵兵0其, [5, 7], [7, 9]其. Two new midpoints appear, namely, 6 and 8, with objective values F(6)⫽(1.9901, 1.8000, 0.8000) F(8)⫽(1.9987, 1.9231, 0.4000) . This enables us to update the table of vectors M,UB yielding IM(I)UB(I) 兵0其(2, 1.8000, 1) (2, 1.8000, 1) [5, 7] (1.9901, 1.8000, 0.8000) (1.9964, 1.8824, 1) [7, 9] (1.9987, 1.9231, 0.4000) (1.9995, 1.9459, 0.6000) As in the previous iteration, no pair of intervals satisfies condition (3.8), and we go to Iteration 3 with the updated list of intervals ᏸ ⫽兵兵0其, [5, 6], [6, 7], [7, 8], [8, 9]其 The new midpoints give objective values F(5.5)⫽(1.9837, 1.7241, 0.9000) F(6.5)⫽(1.9940, 1.8491, 0.7000) F(7.5)⫽(1.9978, 1.9059, 0.5000) F(8.5)⫽(1.9992, 1.9360, 0.3000) MULTIPLE-OBJECTIVE QUASICONVEX MAXIMIZATION 51 With this, our new table of vectors M,UB is given by IM(I)UB(I) 兵0其(2, 1.8000, 1) (2, 1.8000, 1) [5, 6] (1.9837, 1.7241, 0.9000) (1.9901, 1.8000, 1) [6, 7] (1.9940, 1.8491, 0.7000) (1.9964, 1.8824, 0.8000) [7, 8] (1.9978, 1.9059, 0.5000) (1.9987, 1.9231, 0.6000) [8, 9] (1.9992, 1.9360, 0.3000) (1.9995, 1.9459, 0.4000) In this case, the sufficient condition for dominance is satisfied for the pair of intervals 兵0其and [5, 6], so the interval [5, 6] can be excluded for further considerations. We would then obtain a reduced list ᏸ ⫽兵兵0其, [6, 7], [7, 8], [8, 9]其 to start Iteration 4, if desired. 䊐 The following theorem shows that the successive steps of the algorithm above provide a sequence of nested compact dominators, converging to a dominator which, under mild further assumptions on the functions F, enjoys minimality properties: i PROPOSITION 17. Denote by D the union of all intervals of ᏸ at the end of r iteration r,and by D*the compact set ⬁ D*⫽傽D r r⫽1 1. D⫽X⫽傼I and D 傺D for all r. 11⭐i⭐ti r⫹1r 2. If F is upper-semicontinuous,then D*僆 Ᏸ [F;X] (3.10) 3. Moreover,if F is continuous,then D*僆 Ᏸ [F;X] . (3.11) ᐃᏹ Proof. The first property is evident from the algorithm. By construction, each Dis compact, thus their intersection is also compact. r Moreover, D僆 Ᏸ [F;X], thus, by Proposition 3, (3.10) follows. r To show (3.11), suppose, on the contrary, that there exist x,x僆D* with 12 ⬎r x僆 ᏿ (x). If, for each i⫽1, 2 and r⫽1, 2, . . . , we denote by Ᏽ the class of 12 i rr intervals Iin the list at stage rwith x僆I, it will follow from the splitting process iii rr that there exists some rsuch that, for each r⭓r, and each I僆 Ᏽ 00ii rr x僆 ⁄ I, and x僆 ⁄ I 12 21 52 EMILIO CARRIZOSA AND FRANK PLASTRIA Since the functions Fare continuous, thus uniformly continuous on X, there would irr exist some rsuch that for each I僆 Ᏽ ii rr F(x)⬎F(y) for all x僆Iand y僆I,j⫽1, 2, . . . , k jj 12 rr r Hence UB(I)⬍M(I), implying that I(thus x) would have been deleted prior to 21 2 2 stage rby (3.8), thus x僆 ⁄ D*, which is a contradiction. 䊐 2 4. Multiple-objective multi-dimensional problems For the single-objective case (i.e., if k⫽1in(P[F;S])), it is a well-known result of 1 Global Optimization that, if Sis a polytope and Fis quasiconvex on S, then the set 1 of vertices of Sis a dominator for (P[F;S]), [15]. 1j In other words, if, for j⫽0, 1, . . . , n, Ᏺ denotes the set of points of a polytope Scontained in some j-dimensional face of S, then 0 Ᏺ 僆 Ᏸ [F;S] (4.12) 1 The next proposition extends assertion (4.12) to multiple-objective quasiconvex problems. To show it, we will use the following n LEMMA 18. Let P be a polyhedron in ⺢,and let H ,H,...,H be closed 12 t n halfspaces in ⺢.If x*is an extreme point of P 傽傽H,then x*belongs to 1⭐i⭐ti some face of P with dimension not greater than t. Proof. Let Pbe represented as n P⫽兵x僆⺢:a⬘x⭐bfor all r僆R其 rr for some finite index set R, and let each Hbe given as i n 兵x僆⺢:c⬘x⭐d其 ii Define the sets of active indices R(x*) and T(x*) as R(x*)⫽兵r僆R:a⬘x*⫽b其 rr T(x*)⫽兵i,1⭐i⭐t:c⬘x*⫽d其 ii Then x* belongs to the face Fof P, n F⫽P傽兵x僆⺢:a⬘x⫽b᭙r僆R(x*)其 rr We will show that Fhas dimension not greater than t. Indeed, since x* is, by assumption, an extreme point of P傽傽H, then the set of vectors 兵a其傼 1⭐i⭐ti rr僆R(x*) 兵c其has rank ii僆T(x*) rank(兵a其傼兵c其)⫽n rr僆R(x*) ii僆T(x*) MULTIPLE-OBJECTIVE QUASICONVEX MAXIMIZATION 53 Hence, denoting by 兩T(x*)兩the cardinality of T(x*), one obtains rank(兵a其)⭓n⫺兩T(x*)兩 rr僆R(x*) ⭓n⫺t, thus the dimension of Fcannot be greater than t.䊐 n PROPOSITION 19. Let S be a polytope in ⺢,let k ⭐n⫹1, and let F ,...,Fbe 1k quasiconvex functions on S,all but possibly one of which are upper-semicontinuous. Then k⫺1 Ᏺ 僆 Ᏸ [F;S] (4.13) Proof. Without loss of generality we assume that F,F,...,Fare upper12 k⫺1 semicontinuous on S. We will show that, for any x僆S, ⭓k⫺1 ᏿ (x)傽 Ᏺ 苷5(4.14) Let x僆S, and denote by Ꮽ (x) the index set Ꮽ (x)⫽兵i,1⭐i⭐k⫺1, F(y)⬍F(x) for some y僆S其. ii If Ꮽ (x) is empty, we would have F(y)⭓F(x)᭙y僆S, ⭓ thus any vertex y*ofSsatisfies y*僆 ᏿ (x). Hence ⭓0⭓k⫺1 5苷 ᏿ (x)傽 Ᏺ 傺 ᏿ (x)傽 Ᏺ , showing (4.14). We consider now the case Ꮽ (x)苷5. For each i僆 Ꮽ (x), the convex set 兵y僆S:F(y)⬍F(x)其is open in S(its complement is closed due to the upperii semicontinuity of F) and does not contain x. Hence, there exists some nonzero i i vector usuch that i 具u,y⫺x典⬎0 for all y僆Swith F(y)⬍F(x) , (4.15) ii n where 具⭈,⭈典stands for the usual scalar product in ⺢. Consider the polyhedron S(x), ni S(x)⫽S傽兵y僆⺢:具u,y⫺x典⭐0, ᭙i僆 Ꮽ (x)其, which is nonempty because x僆S(x). Consider the optimization problem max F(y) (4.16) k y僆S(x) Since Fis quasiconvex on the nonempty polyhedron S(x), (4.16) has an optimal k solution at some vertex y*ofS(x). We will show that k⫺1⭓ y*僆 Ᏺ 傽 ᏿ (x) (4.17) 54 EMILIO CARRIZOSA AND FRANK PLASTRIA Since y* is a vertex of S(x), Lemma 18 implies that 兩 Ꮽ (x)兩k⫺1 y*僆 Ᏺ 傺 Ᏺ (4.18) Since x僆S(x) and y* is optimal for (4.16), F(y*)⭓F(x) (4.19) kk By definition of Ꮽ (x), F(y*)⭓F(x)᭙i僆兵1, 2, . . . , k⫺1其\ Ꮽ (x) (4.20) ii and by (4.15) and the fact that y*僆S(x), F(y*)⭓F(x)᭙i僆 Ꮽ (x) (4.21) ii ⭓k⫺1 Joining (4.18–4.21), (4.17) holds, thus ᏿ (x)傽 Ᏺ 苷5, as asserted. 䊐 REMARK 20. The assumption of upper-semicontinuity of at least k⫺1 functions is not superfluous, as the following example shows: let k⫽2, n⫽2, S⫽[0, 1]⫻[0, 1], and the functions F,Fdefined as 12 11 11 ᎐᎐ ᎐᎐ 0, if x⬎or x⫽0, 0, if x⬎or x⫽1, 共兲 共兲 22 22 22 F(x)⫽F(x)⫽ 再再 12 1, otherwise 1, otherwise 11 ᎐᎐ Both functions are quasiconvex but are not upper-semicontinuous; let x*⫽( , ). It 22 is easily seen that ⭓1 ᎐ ᏿ (x*)⫽ ␭ ,:0⬍ ␭ ⬍1 兵共 兲 其 2 ⭓11 thus ᏿ (x*)傽 Ᏺ ⫽5, showing that Ᏺ is not a dominator. 䊐 As a consequence of Propositions 19 and 2, one obtains n COROLLARY 21. Let S be the union of t polytopes S ,...,Sin⺢.Let F ,...,F 1t1k be k ⭐n⫹1real-valued functions on S.On each S ,let all F be quasiconvex and ji all but possibly one F be lower-semicontinuous.Then the union of all k ⫺1-faces of i all S is a dominator for P[F;S]. j Proposition 19 also enables us to derive localization results for single-objective problems. n COROLLARY 22. Let S be the union of t polytopes S ,...,Sin⺢.Let F ,...,F 1t1k be k ⭐n⫹1real-valued functions on S,quasiconvex on each S .For any j componentwise nondecreasing ⌽:F(S)→⺢such that Problem max ⌽(F(x), F(x),...,F(x)) 12 k x僆S MULTIPLE-OBJECTIVE QUASICONVEX MAXIMIZATION 55 has an optimal solution,the union of the set of k ⫺1-faces of all S also contains an j optimal solution. In particular, for F,F,...,Flinear fractional functions with positive de12 k nominators on a polytope S, which are well-known to be quasiconvex (see e.g. [1], p. 165) and ⌽(s,s,...,s)⫽s⫹s⫹⭈⭈⭈⫹s,or⌽(s,s,...,s)⫽ 12 k12 k12 k max兵s,s,...,s其, we obtain 12 k COROLLARY 23. The minimum of the sum ( respect.the maximum ) of k linear fractional functions with positive denominators over a polytope S in dimension n⭓k⫺1is attained at some k ⫺1-face of S. This generalizes the results known for the case k⫽2 (see the review of [27] and the references therein). For an application see [25]. REMARK 24. For biobjective problems (k⫽2), since both Fare quasiconvex on j each edge, after embedding such edges as compact intervals of the real line, one can use the results in Section 3 to design an algorithm converging to a weak minimal dominator. For the case of general k, Proposition 19 seems at the moment to be mainly of theoretical interest: In principle, Algorithm 1 can be generalized to the k-dimensional case, by replacing intervals by e.g. simplices, although the corresponding bounding scheme does not extend to the general case, and less efficient schemes, such as those proposed in [4, 14], should be used. Nevertheless, this kind of localization results can be used to design new heuristic resolution methods of problems of the form min ⌽(F(x)), where k, the number of x僆S components of F, is very small, and, in particular, much smaller than the dimension nof the space. We know then that the search for optimal solutions can be reduced to the k⫺1-dimensional faces of S, so that algorithms which alternate a global search in a given low-dimensional face with moves to adjacent low-dimensional faces, can be used. 5. Application: Location of a semi-obnoxious facility 2 Let S⫽S傼S傼⭈⭈⭈傼S, each Sbeing a convex polygon in ⺢. Two finite 12 ti ⫹⫺ 2⫹ subsets Ꮽ , Ꮽ of ⺢are given. Associated with each a僆 Ꮽ we have a concave function g: [0, ⫹⬁)→⺢and a polyhedral gauge ␥ , [9, 10, 19], i.e., a Minkowski aa functional whose unit ball is a polytope. Let h: [0, ⫹⬁)→⺢be a nonincreasing function, and consider the biobjective problem min (F(x), F(x)) , (5.22) 12 x僆S 56 EMILIO CARRIZOSA AND FRANK PLASTRIA where F(x)⫽冘g( ␥ (x⫺a)) 1aa ⫹ a僆 Ꮽ F(x)⫽max h(储x⫺a储), 2 ⫺ a僆 Ꮽ 储⭈储being the euclidean norm. This problem has its motivation in Continuous Location of semidesirable facilities, see [17, 23] for an introduction to Continuous Location in general and [6, 24] for semidesirable facility location models: A facility is to be located within region S, and will interact with individuals who want the facility close (those in ⫹⫺⫹ Ꮽ ) and others who want the facility far (those in Ꮽ ). Interactions with Ꮽ provide the first objective in (5.22): the minimization of the total transportation cost ⫹ F(x), where transportation cost from a僆 Ꮽ to xis given by a concave function g 1a of the distance from ato x, the latter measured by the polyhedral gauge ␥ , [29]. a ⫺ On the other hand, interactions of the facility with Ꮽ provide the second ⫺ objective F, which measures the highest damage suffered by points in Ꮽ , where 2⫺ the damage suffered by a僆 Ꮽ is assumed to be given by a nonincreasing function hof the Euclidean distance from ato x, see [11, 24]. In practice, the two objectives of (5.22) are aggregated into a single criterion, yielding a problem of the form max ⌽⫺冘g( ␥ (x⫺a)), max h(储x⫺a储) , (5.23) aa 冉冊 ⫺ a僆 Ꮽ ⫹ a僆 Ꮽ [6, 24] for some globalizing ⌽, and the resulting problem (multimodal, as a rule), can be tackled e.g. by the 2-dimensional Branch and Bound method described in [13]. However, as shown below (Proposition 25), the search of an optimal solution for (5.23) can be restricted to a series of segments, thus (5.23) can be solved by simply using single-variable Global-Optimization techniques, [2, 12], which are usually much faster than their two-variable counterparts. In order to obtain a dominator for (5.22) one should observe first that, since his assumed to be nonincreasing, it suffices to obtain a dominator for problem max (⫺F(x), min 储x⫺a储) (5.24) 1 ⫺ x僆Sa僆 Ꮽ (in fact, if his decreasing, both problems are equivalent). Let us rewrite now (5.24) within our framework. For polyhedral gauges, using the concept of elementary convex set of [10], one can obtain a subdivision Ꮿ of the plane into polyhedra in such a way that, within each C僆 Ꮿ , each gauge ␥ is affine, see [9, 10] for further a details. For instance, if each ␥ is the lnorm, then the polyhedral subdivision of the a1 plane is obtained after constructing horizontal and vertical lines through each ⫹⫹2 a僆 Ꮽ , yielding a total of O(兩 Ꮽ 兩) cells. ⫺ Moreover, defining, for each a僆 Ꮽ , the Voronoi cell V(a) associated with aas 2⫺ V(a)⫽兵x僆⺢:储x⫺a储⭐储x⫺b储for all b僆 Ꮽ 其, MULTIPLE-OBJECTIVE QUASICONVEX MAXIMIZATION 57 ⫺2 the class ᐂ ⫽兵V(a):a僆 Ꮽ 其also constitutes a polyhedral subdivision of ⺢in ⫺⫺⫺ O(兩 Ꮽ 兩) polyhedra, which can be efficiently constructed in O(兩 Ꮽ 兩log 兩 Ꮽ 兩), see e.g. [20, 26]. Consider now the class ᐆ of all Zof the form S傽C傽V(a) i ⫺ for some i,1⭐i⭐t,C僆 Ꮿ and a僆 Ꮽ which are nonempty. On each Z僆 ᐆ ,we have that ⫺Fis convex (it is the composition of the convex function ⫺兺g ⫹ 1a僆 Ꮽ a with the affine functions (within Z!) ␥ , and Fis also convex (recall that, for Z僆 ᐆ a2 ⫺ fixed, there exists some a*僆 Ꮽ such that min 储x⫺a储⫽储x⫺a*储). Hence, ⫺ a僆 Ꮽ rewriting (5.24) as max (⫺F(x), min 储x⫺a储), 1 ⫺ x僆傼 Za僆 Ꮽ Z僆 ᐆ we can use Corollary 21 to obtain PROPOSITION 25. The edges of the sets in ᐆ constitute a dominator for Problem (5.22) . After embedding the edges of polytopes in ᐆ as compact intervals of the real line, one can use the algorithm described in Section 3.3 to reduce the size of such dominator, converging (in case of decreasing h) to a weak minimal dominator. References 1. Avriel, M., Diewert, W.E., Schaible, S. and Zang, I. (1988), Generalized Concavity, Plenum Press, New York/London. ´´ 2. Blanquero, R. (1999), Localizacion de servicios en el plano mediante tecnicas de op- ´ timizacion d.c. Unpublished Ph.D., Universidad de Sevilla, Spain. ¯ 3. Carrizosa, E., Conde, E., Munoz, M. and Puerto, J. (1995), Planar point-objective location problems with nonconvex constraints: a geometrical construction. Journal of Global Optimization 6: 77–86. 4. Carrizosa, E., Conde, E. and Romero-Morales, D. (1997), Location of a semiobnoxious facility. A biobjective approach. In Advances in Multiple Objective and Goal Programming. Lecture Notes in Economics and Math.Systems 455, Springer, Berlin, 274–281. 5. Carrizosa, E. and Frenk, J.B.G. (1998), Dominating sets for convex functions with some applications. Journal of Optimization Theory and Applications 96: 281–295. 6. Carrizosa, E. and Plastria, F. (1999), Location of semi-obnoxious facilities. Studies in Locational Analysis 12: 1–27. 7. Chankong, V. and Haimes, Y. (1983), Multiobjective Decision Making, North-Holland. 8. Das, I. and Dennis, J.E. (1998), Normal-Boundary Intersection: A New Method for Generating the Pareto Surface in Nonlinear Multicriteria Optimization Problems. SIAM J.on Optimization 8: 631–657. 9. Durier, R. (1990), On Pareto optima, the Fermat-Weber problem and polyhedral gauges, Mathematical Programming 47: 65–79. 58 EMILIO CARRIZOSA AND FRANK PLASTRIA 10. Durier, R. and Michelot, C. (1985), Geometrical Properties of the Fermat-Weber problem, European Journal of Operational Research 20: 332–343. 11. Erkut, E. and Neuman, S. (1989), Analytical Models for Locating Undesirable Facilities, European Journal of Operational Research 40: 275–291. 12. Hansen, P., Jaumard, B. and Lu, S.H. (1992), Global optimization of univariate Lipschitz functions. II. New algorithms and computational comparison. Mathematical Programming 55: 273–292. 13. Hansen, P., Peeters, D., Richard, D. and Thisse, J.F. (1985), The minisum and mimimax location problems revisited. Operations Research 33: 125–126. 14. Hansen, P. and Thisse, J.F. (1981), The Generalized Weber-Rawls Problem, Operations Research (J.P. Brans, ed.). North Holland, pp. 487–495. 15. Horst, R. and Tuy, H. (1990), Global Optimization.Deterministic Approaches. SpringerVerlag. 16. Kuhn, H.W. (1967), On a pair of dual nonlinear programs, in J. Abadie (ed.), Methods of Nonlinear Programming. North-Holland, pp. 37–54. 17. Love, R.F., Morris, J.G. and Wesolowsky, G.O. (1988), Facilities location : models and methods, North-Holland, New York. ´ 18. Mateos, A. and Rıos-Insua, S. (1996), Utility efficiency and its approximation. Top 4: 285–299. 19. Michelot, C. (1993), The mathematics of Continuous Location, Studies in Locational Analysis 5: 59–83. 20. Okabe, A., Boots, B. and Sugihara, K. (1992), Spatial tesselations.Concepts and applications of Voronoi diagrams. Wiley. 21. Plastria, F. (1983), Continuous location problems and cutting plane algorithms, Ph.D. dissertation, Vrije Universiteit Brussel, Brussels. 22. Plastria, F. (1984), Localization in single facility location, European Journal of Operational Research 18: 215–219. 23. Plastria, F. (1995), Continuous Location Problems, in Facility Location : A Survey of Applications and Methods, Springer-Verlag, New York, pp. 225–262. 24. Plastria, F. (1996), Optimal location of undesirable facilities: A selective overview, JORBEL : Belgian Journal of Operations Research,Statistics and Computer Science 36: 109–127. 25. Plastria, F. and Carrizosa, E. (1999), On gauges and median hyperplanes. Working paper BEIF/112. Vrije Universiteit Brussel, Brussels, Belgium. 26. Preparata, F.P. and Shamos, M.I. (1985), Computational Geometry –An Introduction, Springer Verlag. 27. Schaible, S. (1995), Fractional Programming, in R. Horst and P.M. Pardalos (eds.), Handbook of Global Optimization, Kluwer. 28. Steuer, R. (1986), Multiple criteria optimization : Theory,Computation,Application, Wiley. 29. Thisse, J.F., Ward, J.E. and Wendell, R.E. (1984), Some Properties of Location Problems with Block and Round Norms, Operations Research 32: 1309–1327. 30. Wendell, R.E. and Hurter, A.P. (1973), Location theory, dominance, and convexity, Operations Research 21: 314–320. 31. White, D.J. (1982), Optimality and Efficiency. Wiley.