TOPICS IN MULTIPLE CRITERIA OPTIMIZATION by ARTHUR RAYMOND WARBURTON B.A. , The University of Br i t ish Columbia, 1967 M . S c , The University of Montreal, 1968 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE STUDIES (Faculty of Commerce and Business Administration) We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA July, 1981 (T) . Arthur Raymond Warburton, 1981 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t of the requirements f o r an advanced degree at the U n i v e r s i t y o f B r i t i s h Columbia, I agree t h a t the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and study. I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e copying of t h i s t h e s i s f o r s c h o l a r l y purposes may be granted by the head o f my department o r by h i s or her r e p r e s e n t a t i v e s . I t i s understood t h a t copying or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be allowed without my w r i t t e n p e r m i s s i o n . Department of Commerce & Business Administration The U n i v e r s i t y of B r i t i s h Columbia 2075 Wesbrook P l a c e Vancouver, Canada V6T 1W5 Date August 20, 1981 DE-6 (2/79) ( i i ) Abstract « Several aspects of multiple c r i te r ia optimization are investigated. F i r s t , suff ic ient conditions are obtained for the upper semi-continuity of the set of maximal alternatives for a nonscalar parametric optimization problem in which the set of alternatives, the objective functions, and a partial order defined on the set of outcomes may a l l vary. One of the conditions involves continuity of a function f on a product space and the relationship between various continuity condi-tions on f that have appeared on the l i terature are investigated. Second, we study the set of Pareto optimal and weakly Pareto optimal solutions to a vector maximization problem defined by continuous vector valued quasiconcave cr i ter ion functions and a closed convex set of decisions, S. If S is compact, i t is shown that the set of weakly Pareto optimal decisions is connected, but that the set of Pareto optimal decisions is not necessarily connected. However, the set of Pareto optima is shown to be connected for some important sub-classes of quasiconcave c r i t e r i a . Under reasonable conditions the compactness assumption on S may be relaxed and connectedness maintained. Connecti-vity may f a i l i f preferences are given by cones other than the Pareto cone. F ina l ly , b icr i ter ion mathematical programs of the form P: max {u(f^(x), f2(x)) |xeS} are considered, where S is a bounded polyhedral set , f j and f2 are l inear fractional functions, and u is ( I i i ) a real valued function, non-decreasing in each argument. It is shown that the solution of P may be essential ly reduced to a one parameter l inear program. Simple, computationally ef fect ive, f in i te algorithms are obtained for the cases where u is a weighted sum of f j and f g , and where u is the Chebychev function min [f j (x) , f2(x)]. It is also shown how a simple sequence of quasiconcave problems may be constructed whose solutions converge to the solution of max {tnin[f j ( x ) , . . . ,fp(x)] |xe S) i f ^ • • • ' f p a r e quasiconcave and S is convex. (iv) TABLE OF CONTENTS Page ABSTRACT , ( i i) ACKNOWLEDGEMENTS (vi) CHAPTER 1 INTRODUCTION 1 1.1 Preliminaries 1 1.2 Outline of Results 5 CHAPTER 2 STABILITY 8 2.1 Preliminaries 8 2.2 Stability 9 2.3 Continuity on Product Spaces 24 CHAPTER 3 CONNECTEDNESS 27 3.1 Preliminaries 27 3.2 Basic Definitions and Notation 30 3.3 Upper Semicontinuity and Parametric Representations 31 3.4 Connectedness Results 38 3.5 Extension to Non-compact Sets 42 CHAPTER 4 APPLICATIONS TO MATHEMATICAL PROGRAMMING 51 4.1 Preliminaries 51 4.2 Basic Results 54 4.3 The Algorithm and its Application to Maximizing the Sum o f Two Fractional Functions 58 (v) Page 4.4 Chebychev Problems 64 4.5 Numerical Example and Computational 4 Results 6 9 B I B L I O G R A P H Y 7 8 ( v i ) Acknowledgments I am g r e a t l y indebted to P ro fesso r D. Granot f o r h i s va l uab le and generous a s s i s t a n c e dur ing the p repara t i on o f t h i s t h e s i s . I would a l s o l i k e to thank P ro fesso r I. V e r t i n s k y f o r h is encouragement and many h e l p f u l s u g g e s t i o n s . Many thanks a l s o to Barbara S t r o u t s , f o r her pat ience and perseverence through the t y p i n g o f seve ra l ve rs i ons o f t h i s manuscr ip t . The f i n a n c i a l support from the Humanit ies and S o c i a l Sc ience Research Counc i l o f Canada i s g r a t e f u l l y acknowledged, as we l l as some support r ece i ved from Nat iona l Research Counci l Grant 67-4181. 1 Chapter I I n t roduc t i on 1.1 P r e ! i m i n a r i e s A c e n t r a l concept i n many m u l t i p l e c r i t e r i o n d e c i s i o n models i s tha t o f an e f f i c i e n t (Pare to o p t i m a l , non-dominated) a l t e r n a t i v e ; tha t i s , an a l t e r n a t i v e which i s maximal w i th respec t to some order r e l a t i o n on the se t o f a v a i l a b l e a c t i o n s . The main ob jec t o f t h i s t h e s i s i s t o i n v e s t i g a t e c e r t a i n s t r u c t u r a l p r o p e r t i e s o f the se t o f e f f i c i e n t a l t e r n a t i v e s w i t h i n the contex t o f the vec to r max imizat ion problem and i t s g e n e r a l i z a t i o n s . Some o f the r e s u l t s t ha t are obta ined w i l l be a p p l i e d to some mathematical programming problems. To prov ide a framework f o r i n t r o d u c i n g the issues tha t w i l l be t r e a t e d h e r e , we w i l l now de f i ne the most common form o f the vec to r max imizat ion problem. Let X be a se t o f alternatives, and l e t f j , . . . , f be p r e a l va lued criterion functions de f i ned on X. Def ine f = ( f j , . . - . , f ) , so tha t f ( X ) , the image o f X under f , i s a subset o f Euc l idean p-space E*\ f (X ) can be p a r t i a l l y ordered by the o r d e r i n g on the s c a l a r va lued f unc t i ons f . . I f a = ( a p . . . ^ ) and b = ( b j , . . . , b ) belong to E P and we write a > b. If (1) holds with strict inequality for at least one i , write a > b, and let a > b mean that (1) holds with strict inequality for each i . A decision x e X is said to be Pareto efficient i f f(y) = f(x) whenever y e X and f(y) > f(x). Equivalently; x is Pareto efficient i f there is no y e X such that f(y) > f(x). If x e X and there exists no y e X such that f(y) > f(x) then x is said to be weakly Pareto efficient. In such a context, the vector maximization problem is to find the set of Pareto efficient alternatives, or possibly to find the set of weakly Pareto efficient alternatives. More general forms of the vector maximization problem can be obtained by considering orders other than the Pareto order. In particular, one may consider orders induced by cones (e.g. Yu (1974), Bitran and Magnanti (1979)). We can also consider vector maximization problems in which the data and preference structure are subject to perturbations (e.g. Hildenbrand and Kirman (1976), Tanino and Sarawagi (1980)). Further, i t is often important to pay particular attention to so called properly Pareto efficient alternatives, in that it may be possible to chracterize such alternatives as solutions to certain families of scalar maximization problems (Geoffrion (1968)). Properties of the set of efficient alternatives have been investi-gated by many authors, and Bitran and Magnanti (.1979) provide a com-prehensive l i s t of references. In particular, the issues below (for 3 which we prov ide some r e p r e s e n t a t i v e re fe rences ) have been cons idered in a v a r i e t y o f c o n t e x t s . ' ( i ) When do e f f i c i e n t a l t e r n a t i v e s e x i s t ? (Yu (1974) , Naccache (1978) , B i t r a n and Magnanti (1979) ) . ( i i ) Is the se t o f e f f i c i e n t a l t e r n a t i v e s s t a b l e under changing environments and pre ference s t r u c t u r e s ? (Hi ldenbrand and Kirman (1976) , Tanino and Sarawagi (1980) ) . ( i i i ) Is the set o f e f f i c i e n t a l t e r n a t i v e s connected? (Yu and Zeleny (1974) , Naccache (1978) , B i t r a n and Magnanti (1979) , Choo (1980) ) . ( i v ) Can the s t r u c t u r e o f the se t o f e f f i c i e n t a l t e r n a t i v e s be used to s i m p l i f y the s o l u t i o n o f mathematical programs? (Geo f f r i on (1967) , Pasternak and Passy (1973) ) . (v) Are there r ep resen ta t i on theorems which c h a r a c t e r i z e the se t o f e f f i c i e n t or weakly e f f i c i e n t a l t e r n a t i v e s ? (Arrow, B r a n a k i n , and B l a c k w e l l (1953) , Geo f f r i on (1968) , Bowman (1975) , B i t r a n and Magnanti (1979) , Choo (1980) ) . I t i s easy to j u s t i f y c o n s i d e r a t i o n o f the above q u e s t i o n s . The ex i s t ence o f e f f i c i e n t a l t e r n a t i v e s i s c e r t a i n l y d e s i r a b l e ; s u i t a b l e r ep resen ta t i on theorems may prov ide a means o f computing e f f i c i e n t a l t e r n a t i v e s (and prov ing o ther theorems) ; c o n n e c t i v i t y i m p l i e s tha t a " b e s t " e f f i c i e n t a l t e r n a t i v e (w i th respec t to some a u x i l a r y pre ference r e l a t i o n ) may be found by a l o c a l search among e f f i c i e n t s o l u t i o n s on l y ( B i t r a n and Magnanti (1979) ) . Quest ions concern ing s t a b i l i t y a r i s e n a t u r a l l y i n vec to r max imizat ion problems i n which the data and 4 and preference structures may vary. We will consider the above questions for vector maximization problems in which the cr i te r ia are not necessarily concave, emphasizing s t a b i l i t y , connectivity and applications to fractional programming. Some representation and existence theorems will also be developed or applied, and used as tools for proving the connectivity results and for developing algorithms for fractional programs. The question of local characterization of e f f ic ient solutions for non-concave problems will not be considered here. The reader is referred to Craven (1980) who observes that the Kuhn Tucker (.1951) typ e conditions are suff ic ient for eff ic iency and weak eff iciency in vector maximization problems having pseudoconcave c r i te r ia and differentiable quasiconcave constraints. We also note that certain duality relat ion-ships for non-concave vector maximization problems have recently been developed by di Guglielmo (1977). 5 1.2 Ou t l i ne o f Resu l t s In t h i s s e c t i o n we g ive an in formal d e s c r i p t i o n o f our wain r e s u l t s . For b r e v i t y , many o f the d e f i n i t i o n s w i l l be de fe r red u n t i l the r e l evan t chap te r . S t a b i l i t y and r e l a t e d quest ions are t r e a t e d i n Chapter 2 . Consider the opt imal s o l u t i o n s e t s , M(y), to the paramet r ic f am i l y o f o p t i m i z a t i o n problems ' max { f ( x , y ) | x e n ( y ) } , where f i s a rea l va lued f u n c t i o n , and y belongs to a space o f parameters. Numerous authors have cons idered the c o n t i n u i t y p r o p e r t i e s o f the correspondence y ->- M(y) ( e . g . Berge (1963) , D a n t z i g , Folkman and Shap i ro (1967) , Evans (1970) , Meyer (1970) , Hogan (1973) , see a l s o Huard (1979) ) . Under s u i t a b l e c o n t i n u i t y c o n d i t i o n s on f and ti, i t has been shown tha t the map y M(y) i s an upper semicont inuous po in t t o se t map. I f f i s not s c a l a r v a l u e d , then M(y) may be taken to represen t the se t o f Pareto e f f i c i e n t or weakly Pareto e f f i c i e n t a l t e r n a t i v e s (or some more general e f f i c i e n t s e t ) . In such a s e t t i n g , the problem has been i n v e s t i g a t e d by Tanino and Sawaragi (1980) and i n d i r e c t l y , by Hi ldenbrand and Kirman (1976) . We extend these r e s u l t s , and prove a general theorem concern ing the upper s e m i c o n t i n u i t y o f y -*• M(y) f o r a g e n e r a l i z e d vec to r max imizat ion problem i n which the c r i t e r i o n f u n c t i o n s , the se t o f a l t e r n a t i v e s , and the pre ference s t r u c t u r e a l l may v a r y . The s t a b i l i t y o f the se t o f weak Pareto e f f i c i e n t a l t e r n a t i v e s and o f more general se t s o f e f f i c i e n t a l t e r n a t i v e s ( i n the sense of upper 6 semicontinuity), as well as the usual scalar results, follow as special cases, and i t is shown that the set of Pareto efficient alternatives may be unstable. Theorems concerning the upper-semi continuity of y -»- M(y) invariably involve hypotheses regarding the continuity of f(x,y). These hypotheses have been of two kinds; one involving continuity of f on the product space, and the other involving certain uniformity properties of the maps obtained by fixing the variable y. The relationship between the two types of hypotheses is investigated, and it will be seen that under mild conditions a well known result implies that the hypotheses are equivalent. In Chapter 3 we consider the connectivity of the sets of Pareto efficient and weakly Pareto efficient alternatives for vector maximization problems in which the criteria are quasiconcave ( i .e. have convex upper level sets). In the case of concave criteria and compact decision sets, Naccache (1978) and Bitran and Magnanti (1979) have shown that the set of Pareto efficient alternatives (and more general sets of efficient alternatives) is connected, and that connectivity s t i l l holds in certain non-compact settings. If the criteria are not concave, the only result of which we are aware is that of Choo (1980) - namely, that the set of weak Pareto efficient alternatives is linearly connected for linearly constrained linear fractional programming problems. We show that i f the criteria are quasiconcave then the set of Pareto efficient alternatives may fail to be connected, but that the set of weak Pareto efficient alternatives is connected. Further, i t is 7 shown tha t the se t o f Pareto e f f i c i e n t a l t e r n a t i v e s i s connected f o r some important subc lasses o f quasiconcave f u n c t i o n s ; namely, the c l a s s e s o f concave t rans fo rmab le and s t r o n g l y quasiconcave f u n c t i o n s . Under reasonab le hypotheses the c o n n e c t i v i t y r e s u l t s are extended to the non-compact c a s e . I t i s a l s o shown tha t the c o n n e c t i v i t y r e s u l t s do not n e c e s s a r i l y extend to dominat ion s t r u c t u r e s o ther than those g iven by Pareto or weak Pareto e f f i c i e n c y . In Chapter 4 , i t i s shown how some s t r u c t u r a l p rope r t i es o f the se t o f Pareto e f f i c i e n t a l t e r n a t i v e s may be e x p l o i t e d i n the s o l u t i o n o f c e r t a i n mathematical programming problems. In p a r t i c u l a r , we app ly some r e s u l t s o f Choo (1980) and show tha t the s o l u t i o n o f the problem max { f j ( x ) + f 2 ( x ) | x e S} , where f j and f^ are l i n e a r f r a c t i o n a l f unc t i ons and S i s a bounded po lyhedra l s e t , may be reduced to the s o l u t i o n o f a s imp le one parameter l i n e a r program. I n t e r e s t i n g l y , the opt imal s o l u t i o n x * i s found i n f i n i t e l y many s t e p s , even though f j + f 2 may be n e i t h e r quasiconvex nor quas iconcave , and x * may l i e i n the i n t e r i o r o f S. Computat ional s t ud ies i n d i c a t e tha t our procedure so lves problems having up to 300 v a r i a b l e s and 150 c o n s t r a i n t s w i th no more than tw ice the number o f p i vo t s r equ i r ed to so l ve a s imp le f r a c t i o n a l l i n e a r program. We a l s o app ly some o f the c o n n e c t i v i t y r e s u l t s to Chebychev problems o f the form max (min [ f ^ ( x ) , . . . , f ( x ) ] | x e S ) , where each f.. i s quas iconcave. 8 Chapter 2 Stabi l i ty 2.1 Preliminaries In multiple objective decision problems, a decision maker's al ter-natives and preferences may change according to his environment and over time, and i t is natural to consider the s tab i l i ty properties of his set of "preferred" decisions. In this chapter we formulate a generalized vector maximization problem in which the decision maker's set of al ternatives, ft(y), the cr i ter ion functions, f ( * , y ) , and the preference structure > y may vary with some parameter y. We then prove a theorem which gives suff ic ient conditions for s tabi l i ty (in the sense of upper-semicontinuity) of the set of preferred alternatives M(y). The standard results on continuity of the optimal value function and the upper continuity of the optimal solution set for scalar maxi-mization problems follow as special cases. Further, upper semi-continuity of the set of weak Pareto ef f ic ient alternatives also follows direct ly from our resul t . The theorem generalizes recent results of Tanino and Sarawagi (1980), and is an extension of a result of Hildenbrand and Kirman (1972) that arises in the context of the general problem of choice in economics. In the f inal section of this chapter we investigate the exact nature of the relationship between two continuity hypotheses that have appeared in upper semi continuity theorems for parametric optimization problems. 9 2 .2 S t a b i l i t y In order to s t a t e and prove our s t a b i l i t y r e s u l t s i t w i l l be necessary to rev iew some d e f i n i t i o n s and theorems concern ing se t va lued correspondences and t h e i r c o n t i n u i t y p r o p e r t i e s , as we l l as to r e c a l l the d e f i n i t i o n o f the product topo logy . Let T ^ , . . . , T p be t o p o l o g i c a l s p a c e s , and l e t T = T ^ x , . . . x T n . A bas i s o f neighborhoods a t t = ( t j , . . . , t ) e T i n the product topology i s g iven by a l l se ts o f the form U ( t ^ ) x . . . x U ( t n ) , where U ( t . ) i s a neighborhood o f t . e T . , 1 < i < n . A correspondence T from a se t A i n t o a se t B i s a " r u l e " which a s s o c i a t e s to each a e A a non-empty subset r ( a ) c B . Thus a f u n c t i o n i s a s i n g l e va lued correspondence. The graph o f r i s the subset o f A x B g iven by G(r) = { (a ,b) e AxB|b e r ( a ) h A v a r i e t y o f c l o s e l y r e l a t e d no t ions o f c o n t i n u i t y f o r correspondences have been deve loped , and Huard (1979) g i ves the r e l a t i o n s h i p among t h e s e . We use the d e f i n i t i o n s o f Berge (1963) and say t ha t the correspondence r from A to B i s upper semicontinuous (u.s.c.) a t a e A i f f o r every neighborhood N o f r ( a ) there e x i s t s a neighborhood M o f a such tha t r ( a ' ) c N whenever a" e M. The correspondence r i s lower semi continuous (I. s. c.) a t a e A i f f o r every neighborhood N such t h a t r ( a ) n N f 4> the re e x i s t s a neighborhood M o f a such t ha t r ( a ' ) n N f <j> whenever a ' e M. r i s continuous a t a i f r i s u . s . c . and l . s . c . at a ; r i s u . s . c . ( r e s p . l . s . c , con t inuous) on A i f r i s u . s . c . ( r e s p . l . s . c , cont inuous) at each a e A. F i n a l l y , r i s compact valued i f r ( a ) i s compact f o r each a £ A. 10 Hildenbrand and Kirman (1976) provide the following sequential characterization of upper and lower semicontinuity. Theorem 2.2.1 Suppose A and B are complete metric spaces and that r is a correspondence from A to B. Then r is l . s . c . at a e A i f f for every sequence {an> converging to a, and every b e r(a), there exists a sequence {bnl converging to b with bR e r(a n) . If r is compact valued, then r is u.s.c. at a e A i f f for every sequence {a 1 converging to a, and every sequence {b } with b e r(a ), there n J n n n exists a convergent subsequence of {bn> whose limit belongs to r(a). Observe that i f r is single valued and satisfies any of the above definitions then r is a continuous function. Closely related to the notion of upper semicontinuity is the concept of closedness. The correspondence r is said to be closed at a e A i f for every sequence {an> converging to a and every sequence {b^} converging to b such that bn e r ( a n ) » w e n a v e D e r( a)> ^ follows directly from the definitions that r is closed on A i f and only i f its graph, G(r) , is closed in AxB. The following properties of correspondences will be required. For proofs and a more complete discussion of the continuity properties of correspondences see Hildenbrand and Kirman (1976) or Berge (1963). Theorem 2.2.2 Let X, Y, and Z be complete metric spaces. (i) I f f i : Y - * - X i s a correspondence continuous at y e Y, and g is a function from X to Z which is continuous on n(y), then the correspondence $: Y Z given by 11 * (y ) = u ( g ( x ) | x G n(y)} = g(n(y) ) i s cont inuous a t y . ( i i ) Suppose tha t n : Y-> X i s u . s . c . and compact va lued a t y e Y and tha t V: Y -*• X i s c l osed at y . I f n(y) n v (y ) ^ c}> then the correspondence y n (y ) n v (y ) i s compact va lued and u . s . c . at y . ( i i i ) I f fi: Y -> X i s u . s . c . and c l osed va lued at y e Y , then n i s c l osed a t y . Remark 2 .2 .1 Observe tha t n may be viewed as a f u n c t i o n from Y to the power se t o f X. Berge (1963) shows t ha t c o n t i n u i t y o f the compact va lued correspondence fi: Y -* X i s e q u i v a l e n t t o c o n t i n u i t y o f the f unc t i on fi: Y •* X , where X i s the space o f compact subsets o f X w i th the Hausdorff metric g i v e n , f o r A , B e X , by 6(A,B) = max [ p ( A , B ) , P ( B , A ) ] , where p (A ,B) = sup { d ( a , B ) | a E A } , P ( B , A ) = sup {d (b ,A ) |b e B ) , and d i s the me t r i c on X. Our upper semi c o n t i n u i t y theorem can now be deve loped. To mot ivate i t , we expand upon a p resen ta t i on o f H i ldenbrand and Kirman (1976) . Consider the f o l l o w i n g s i t u a t i o n : Suppose we have a se t Y rep resen t i ng va r ious p o s s i b l e s t a t e s o f the w o r l d , and a se t X rep resen t i ng a se t o f conce i vab le a c t i o n s . For a p a r t i c u l a r s t a t e o f the wor ld y e Y , 12 assume tha t the se t o f a v a i l a b l e a c t i o n s i s r e s t r i c t e d to a subset n (y ) o f X. To a i d i n comparing a l t e r n a t i v e a c t i o n s i n n ( y ) , suppose t h a t a s e t o f a t t r i b u t e measurements i s g iven f o r each a l t e r n a t i v e x i n ft(y) by a measurement f u n c t i o n f t a k i n g va lues i n some s e t o f outcomes Z. Thus f i s a f u n c t i o n from X x Y to Z , and f ( x , y ) represen ts the measurements (outcomes) f o r a l t e r n a t i v e x i n s t a t e o f the wor ld y . One i s i n t e r e s t e d i n the ac t i ons M(y) c n[y) t ha t are i n some sense " b e s t " . The r e l a t i v e d e s i r a b i l i t y o f the a l t e r n a t i v e ac t i ons i n the g iven s t a t e o f the wor ld i s summarized by the cu r ren t se t o f measurements $ ( y ) = f ( f i ( y ) , y ) c Z , upon which some pre ference > i s d e f i n e d . The " b e s t " ac t i ons M(y) are those ac t i ons whose measurements are best w i th respec t to the cu r ren t p re fe rence s t r u c t u r e > on the se t o f outcomes $ ( y ) . Both the f u n c t i o n f ( - , y ) measuring the a t t r i b u t e s and the pre fe rence s t r u c t u r e > y may change w i th y , and one wishes to cons ide r the c o n t i n u i t y p r o p e r t i e s o f M(y ) . I t may a l s o be d e s i r a b l e to cons ide r the c o n t i n u i t y p r o p e r t i e s o f the set o f p re fe r red outcomes M(y) = f ( M ( y ) , y ) . For example, i f f i s a r e a l va lued f u n c t i o n , then M(y) rep resen ts the se t o f opt imal s o l u t i o n s to the paramet r ic o p t i m i z a t i o n problem max { f ( x , y ) | x e n ( y ) } , and M(y) represen ts the opt imal va lue f unc t i on ky) = f ( x * , y ) where x * e M(y ) . In such a case the c o n t i n u i t y p r o p e r t i e s o f M(y) and M(y) have been e x t e n s i v e l y s tud ied ( e . g . Hogan (1973) , D a n t z i g , 13 Folkman, and Shap i ro (1967) , Evans and Gould (1970) , Meyer (1970) , Berge (1963) ) . The case i n which f i s not s c a l a r va lued has been cons ide red by Tanino and Sarawagi (1980) and i n d i r e c t l y , by H i ldenbrand and Kirman (1976) . We w i l l s tudy M(y) and M(y) i n the n o n - s c a l a r s e t t i n g , and ob ta in r e s u l t s based on a theorem appear ing i n H i ldenbrand and Kirman (1976) . In order to s t a t e and prove our theorem i t w i l l be necessary to f o r m a l i z e the framework tha t has been o u t l i n e d above. F i r s t observe tha t correspondences can be used to de f ine order r e l a t i o n s on a se t A. Suppose r maps A i n t o subsets o f A. Then r de f i nes an o rder > on A by a i > a 2 i f f a l G r ^ a 2 ^ * The order > i s s a i d to be transitive i f a^ > a£ , a^ > a^ imply a j > a 3 , and i r r e f l e x i v e i f a^ >^ a^ ( tha t i s , i f ^v{a^)). The element a^ e A i s maximal on A w i th respec t to > i f there i s no a^ G A such tha t &2 > a i * More g e n e r a l l y , l e t Y be a se t o f parameters r e p r e s e n t i n g s t a tes o f the wor ld and Z be a se t r ep resen t i ng outcomes. Suppose e i s a correspondence from Y x Z to Z which a s s o c i a t e s a subset e ( y , z ) o f Z w i th each ( y , z ) e y x Z. Then e de f i nes a f a m i l y o f o rder r e l a t i o n s > y on Z by Z l > y z 2 i f f Z l E 0 ( y , z 2 ^ Now l e t X be a s e t o f a c t i o n s , and l e t f be a f u n c t i o n from X x Y to Z. 14 Then the order >^ on Z induces an order > on X by defining X l * y X 2 i f f f( xi»y) >y f(x 2.y)-Now suppose that is a set valued correspondence that associates a subset of available actions n(y) c X with element y € Y. Define a set valued outcome correspondence $ from Y to Z by *(y) = f(n(y),y), where f(ft(y),y)is the image of a{y) under f(• ,y); that is »(y) = u tf(x,y)|x e n( y)}. It is clear that x is a maximal element of fi(y) with respect to >y i f and only i f f(x,y) is a maximal element of *(y) with respect to > . Moreover, > is transitive and irreflexive i f and only i f y y J the same is true of > . y Denote the set of maximal elements of ft(y) by M(y), and let M(y) be the set of maximal elements of *(y). Thus M(y) = f(M(y),y), and -1 ' -1 M(y) = f (M(y),y) n fi(y), where f denotes the inverse image of f. If we set X = Z and let f be the projection (x,y) x, we obtain fi(y) = $(y). In such a case > y and > coincide, so that M(y) = M(y), and preferences are measured directly with respect to actions. For such a case Hildenbrand and Kirman (1976) prove Theorem 2.2.3 below. It will be convenient to state the theorem in terms of outcomes $(y) and maximal outcomes M(y), even though i t could be stated equivalently in terms of actions fi(y) and maximal actions M(y). 15 Theorem 2 . 2 . 3 Let Y and Z be complete me t r i c spaces o f parameters and outcomes r e s p e c t i v e l y , and l e t $ be a correspondence from Y to Z. Let e be a correspondence from Y x Z to Z whose g raph , G(e), ; i s open i n Y x Z x Z. Suppose tha t each member o f the f a m i l y o f order r e l a t i o n s { > |y e Y} de f i ned by e i s t r a n s i t i v e and i r r e f l e x i v e . I f the se t $(y) i s compact, then the se t M(y) o f maximal elements o f $(y) w i th respec t to > ^ i s non-empty and compact. F u r t h e r , the correspondence y -»• M(y) i s u . s . c . a t y i f $ i s cont inuous a t y . Remark 2 . 2 . 2 The openness o f G(e) means tha t i f ( y . z ^ z ^ ) e G(e) then ( y i Zj.z^) G 6(e) f o r s u f f i c i e n t l y smal l pe r tu rba t i ons y y ' , Zj z ^ , z 2 •+ z ^ . That i s , i f Zj > y z 2 , then z^ > y i , z£ f o r such p e r t u r b a t i o n s . Proof (H i ldenbrand and Kirman (1976)) F i r s t we show t ha t M(y) f For each z e * (y ) l e t r ( z ) = { z ' e $ ( 7 ) | z e e ( y , z ' ) } . S ince the graph o f 0 i s open in Y x Z x Z , the se t r ( z ) i s open r e l a t i v e to $ ( y ) . F u r t h e r , i f M(y) = <|>, then f o r every z 1 e $(y) there e x i s t s z G $(y) such t ha t z e o ( y , z ' ) . Thus the c o l l e c t i o n { r ( z ) | z 6 $(y)} forms an open cove r i ng o f $ ( y ) . S ince $(y) i s assumed to be compact, t he re e x i s t s a f i n i t e subcover ing r ( Z j ) , . . . , r ( z n ) . Now the f i n i t e se t { Z j , . . . , z n ) has a maximal e lement , say z^, s i nce the r e l a t i o n > ~ i s assumed to be t r a n s i t i v e and i r r e f l e x i v e . Hence z n ^ rU^), 1 < i < n - l , and a l s o z £ r ( z ) s i nce > - 1 s i r r e f l e x i v e . S ince the se ts n ' n y 16 r ( z 1 , . . . , r ( z n ) cover $(y) and z^ G $(y), we obtain a contradiction. A Hence M(y) ^ <|>. To show that M(y) is compact i t is sufficient to show that M(y) is A closed, since M(y) is a subset of the compact set $(y). Thus let z n -»- z with z n G M(y). We want to show z G M(y). If not, then there exists an element z e $(y) such that z G e(y,z). Since the graph of 0 is open i t then follows that z e 0(y,z n) for a l l sufficiently large n, contradicting Z R G M(y). Finally we show that y + M(y) is u.s.c. at y. Since A A M(y) = $(y) n M(y) f and $ is u.s.c. at y by assumption, i t is sufficient A by Theorem 2.2.2 ( i i ) to show that M is closed at y. Thus let ___ A A y n -»• y, z n -v z, with z n ^ M(y n). It must be shown that z e M(y). Assume the contrary; that i s , there exists z' e $(y) such that z' e 0(y,z"). Since $ is assumed to be l.s.c. at y there exists by Theorem 2.2.1 a sequence z' + z' with z 1 e $(y ). Thus we have n n n zp •*• z' , y y, z p z", and z' G ©(y,z"), implying, by the openness of G(0) that z^ G ©(y n,z n) for a l l sufficiently large n, contradicting z N G M ( y n ) . • One of the main results of the section is the extension of Theorem 2.2.3 to the case where f is not the projection map. Theorem 2.2.4 Let Y, X, and Z be complete metric spaces of parameters, alternatives, and outcomes, respectively. Let be a correspondence from Y to X, and let f be a function from X x Y to Z. Let 0 be a correspondence from Y x Z to Z, such that each member of the family 17 { > y | y G Y} o f o rder r e l a t i o n s de f i ned by e i s t r a n s i t i v e and i r r e f l e x i v e . Suppose tha t G ( e ) , the graph o f 0 , i s open i n Y x Z x Z. I f the se t n(y) i s compact at y e Y and f i s cont inuous on fi(y) x y , then the se t s o f maximal e lements , M(y) and M ( y ) , o f n{y) and $(y) r e s p e c t i v e l y , are non-empty and compact. Moreover , i f n i s cont inuous a t y then the correspondences y M(y) and y M(y) are u . s . c . a t y . Proof By compactness o f ft(y) and c o n t i n u i t y o f f on n (y ) x y , we have tha t $(y) = f ( n ( y ) , y) i s compact. The assumptions o f Theorem 2 . 2 . 3 are then s a t i s f i e d , imp l y i ng tha t M(y) i s non-empty and compact. But _ i ~ _ _ f i s cont inuous on n(y) x y . Thus M(y) = f (M(y ) , y) n n(y) i s c l o s e d , and so i s a l s o compact, being a c l osed subset o f the compact se t n ( y ) . Now $(y) = f ( n ( y ) , y ) i s the composi t ion o f the correspondence n, cont inuous at y , and the f u n c t i o n f ( - , y ) , cont inuous on ft(y). Hence * i s cont inuous a t y by Theorem 2 . 2 . 2 ( i ) . I t then f o l l ows from Theorem 2 . 2 . 3 t ha t the correspondence y -> M(y) i s u . s . c . at y . I t remains to show tha t y -»• M(y) i s u . s . c . at y . S ince M(y) = n(y) n M(y) ^ <j> and n(y) i s u . s . c . at y by assumpt ion , i t w i l l be s u f f i c i e n t by Theorem 2 . 2 . 2 ( i i ) to v e r i f y tha t M i s c l osed at y . Let y „ -> y , x x" and suppose t ha t x G M(y ) f o r each n. We have n n n n to show tha t x G M(y ) . Now 7 G n(y) s i n c e x n G ft(yn) and n, be ing u . s . c . at y , i s c l o s e d at y by Theorem 2 . 2 . 2 ( i i i ) . A l s o , z n ° f ^ x n ' y n ^ - z by c o n t i n u i t y o f f a t ( x . y ) . Thus we have y y and z -»- z". Moreover, z „ G M(y ) by cho ice o f x . But n n n w n n M i s u . s . c . a t y , imp ly ing v i a Theorem 2 . 2 . 2 ( i i i ) t ha t M i s c l osed a t y . Hence z € M(y"), so t h a t x G f _ 1 ( M ( y ) , y ) n n (y ) = M(y ) , as 18 r e q u i r e d . • The content o f Theorem 2 .2 .4 i s c l o s e l y r e l a t e d to t h a t . o f Theorems 5 . 1 , 6 . 1 , 7 . 1 , and 7.3 o f Tanino and Sarawagi (1980) , where upper s e m i c o n t i n u i t y i s t r ea ted i n the contex t o f the dominat ion s t r u c t u r e s de f i ned by Yu (1974) . Tanino and Sarawagi develop a model i n which there are two parameters , one f o r the f u n c t i o n f and correspondence ft, and a second f o r the pre fe rence s t r u c t u r e g iven by 0. They then cons ide r the case where one parameter v a r i e s wh i l e the o ther remains f i x e d . As a r e s u l t , s l i g h t l y weaker c o n t i n u i t y assumptions than those o f Theorem 2 .2 .4 can be made. However, the more general s i t u a t i o n i n which both parameters may vary s imu l taneous l y i s not covered . Observe tha t i n Theorem 2 . 2 . 4 both separa te and j o i n t l y va r y i ng parameters can be hand led. For example we can se t y = (yj.ygK where y^. i s a parameter f o r f and ft, and y^ i s a parameter f o r 0. A f u r t h e r d i f f e r e n c e i s t ha t A. we prove upper s e m i c o n t i n u i t y o f M and M , whereas Tanino and Sarawagi e s t a b l i s h the weaker p roper ty o f c l o s e d n e s s . The i r weaker conc lus i ons are o f f s e t by the f a c t tha t the compactness hypothes is on ft may be re l axed i n some o f t h e i r r e s u l t s . We now tu rn to a d i s c u s s i o n o f c o n d i t i o n s under which the hypotheses o f Theorem 2 .2 .4 are s a t i s f i e d . F i r s t , c o n d i t i o n s imp ly ing the openness o f G(o) w i l l be deve loped. The f o l l o w i n g lemma o f Tanino and Sarawagi (1980) i s very u s e f u l . Lemma 2 .2 .1 Let r be a correspondence from a complete met r i c space A i n t o Euc l i dean space E* \ Suppose tha t r i s l . s . c . at a e A 19 and tha t r ( a ) i s a convex set fo r each a e A near a". Suppose that the i n t e r i o r o f r ( a ) , i n t rCa), i s non-empty, and tha t b e i n t r(a~). Let a n a in A and b n ->- b in E p . Then b k e r ( a k ) f o r a l l but f i n i t e l y many i n d i c e s k. S u f f i c i e n t c o n d i t i o n s f o r G to be open f o l l o w e a s i l y from Lemma 2 . 2 . 1 . C o r o l l a r y 2 .2 .1 Let Y be a complete met r i c space and l e t 0 be a l . s . c . correspondence from Y x E p to E p . Suppose tha t 0 ( y , z ) i s open, non-empty, and convex i n E p f o r each ( y , z ) e Y x E p . Then G(e), the graph o f 0, i s open i n Y x E p x E p . Proof Let B(a,n) and C(b,n) denote the open b a l l s o f rad ius 1/n about a e Y and b e E P , r e s p e c t i v e l y . Suppose ( y , z , z ' ) e G(©). We want neighborhoods N ( y ) , M ( z ) , M (z ' ) o f y , z , and z 1 such tha t N(y) x M(z) x M(z ' ) c G(0). I f such neighborhoods do not e x i s t , then f o r each n there e x i s t y n e B (y,n), z^ e C(z,n), and z^ e C(z ',n) such tha t ( y n , z n , z ^ ) G(e ) , i . e . z ^ $ 0 ( y n , z n ) . Now c l e a r l y y R + y , z n -y z , z'n + z'. A l s o , by assumption 0 i s l . s . c . at ( y , z ) ; 0 ( y , z ) and a l l © ( y n » z n ) are non-empty, open and convex, and z ' e 0 ( y , z ) = i n t 0 ( y , z ) , where i n t s i g n i f i e s i n t e r i o r . Hence by Lemma 2 . 2 . 1 , z ^ e 0 ( y n , z n ) f o r a l l but f i n i t e l y many n, a c o n t r a d i c t i o n . Thus G(0) i s open. • C o r o l l a r y 2 .2 .1 e s t a b l i s h e s tha t G(0) i s open under c o n d i t i o n s which i n c l u d e convex i t y o f e ( y , z ) . In order to app ly Theorem 2 . 2 . 3 we a l so r e q u i r e t ha t the orders > be t r a n s i t i v e and i r r e f l e x i v e . A s u f f i c i e n t c o n d i t i o n f o r t h i s i s t ha t > be g iven by a f i x e d , acute I 20 convex c o n e . K , f o r each y e Y (see Yu (1974) ) . The order > i s then de f ined by z1 > z 2 i f f z1 e ( z 2 + K ) and zx f z v where we r e c a l l t h a t , f o r any se t A c E P and any po in t b e E p , the se t b + A i s de f i ned by b + A - {b + a |a e A}. The most common examples o f orders on E p g iven by a convex cone are Pareto and weak Pareto e f f i c i e n c y . Pareto e f f i c i e n c y i s de f i ned by the non-negat ive o r than t E p = {z e E p | z > 0}. Weak Pareto e f f i c i e n c y i s de f i ned by the cone E p u {0} , where E $ P = (z 6 E P | z > 0}. i s the s t r i c t l y p o s i t i v e o r t h a n t , and " 0 " i s the zero v e c t o r . For weak Pareto e f f i c i e n c y we have the f o l l o w i n g consequence o f Theorem 2 .2 .4 and C o r o l l a r y 2 . 2 . 1 . C o r o l l a r y 2 . 2 . 2 Let X and Y be complete me t r i c spaces . Let ft be a correspondence from Y to X and l e t f ^ , . . . , f p be r e a l va lued c r i t e r i o n func t i ons de f i ned on X x Y. Set f = ( f j , . . . , f p ) . I f n i s cont inuous a t y e Y , and each f^ i s cont inuous a t each po in t of y x ft(y), then the s e t o f weakly Pareto e f f i c i e n t a l t e r n a t i v e s M(y ) , and the se t o f weakly Pareto outcomes M(y) = f ( y , M ( y ) ) , are non-empty and compact. 21 F u r t h e r , the maps y M(y ) , and y -»• M(y) are u . s . c . at y . Proof The correspondence from Y x E p to E p g iven by ©(y ,z ) = z + E i s convex and open v a l u e d . F u r t h e r , i t i s l . s . c . To see t h i s , l e t ZQ G e ( y , z ) . Then we can w r i t e z Q = z + w, where w > 0. Let z n -v z , y n ->- y and observe tha t ( z n + w) e e ( y n , z n ) . But z n + w -»• z + w e s t a b l i s h i n g the lower s e m i c o n t i n u i t y o f e . Thus a l l hypotheses o f Theorem 2.2.4 and C o r o l l a r y 2 .2 .1 are s a t i s f i e d , imp ly ing the r e s u l t . • Taking p = 1 i n C o r o l l a r y 2 . 2 . 2 g ives the usual s c a l a r theorem. C o r o l l a r y 2 . 2 . 3 Let X and Y be complete me t r i c spaces . Let f be a r e a l va lued f u n c t i o n de f ined on X x Y , and l e t ft be a correspondence from X to Y. Suppose tha t n i s cont inuous a t y and tha t f i s cont inuous on y x n ( y ) . Then the opt imal va lue f unc t i on given by v (y ) ='max { f ( x , y ) | x e n ( y ) } i s cont inuous at y , and the map y M(y) g iven by M(y) = {x e n ( y ) | f ( x , y ) = v(y) } i s u . s . c . at y . We w i l l need the f o l l o w i n g s p e c i a l i z a t i o n o f C o r o l l a r y 2 . 2 . 3 in Chapter 3. C o r o l l a r y 2.2.4 Suppose tha t S i s a compact subset o f E p , and f i s a r e a l va lued f u n c t i o n cont inuous on S x E p . Let M(y) be the se t o f opt imal s o l u t i o n s to the problem 22 max (f(x,y)|x e S). Then the correspondence y M(y) i s u.s.c. on E p . The following example shows that upper semicontinuity may not hold i f G(o) f a i l s to be open. Example 2.2.1 In Figure 1, let n(y) be the quadrilateral enclosed by (A,D,C,y). Let the preference r e l a t i o n be Pareto e f f i c i e n c y and l e t f 1 ( x 1 > x 2 ) = X j , f 2 ( x 1 > x 2 ) = x 2. Then M(B) = M(B) = {A}, and M(y) = M(y) = [ A,y] for B < y < B . The maps y •+ M(y), y •*• M(y) are not u.s.c. at y = B . Figure 1 23 To close this section we wil l consider conditions under which the map y ->- ft(y) is continuous, br ie f ly reviewing some results contained in the paper of Hogan (1973). Suppose that fi is defined by a set of functional inequalities fi(y) = {x G X|g(x,y) < 0}, where g = (g^ . - . - .g ): X-»• E m . Suff icient conditions for ft to be closed are easily obtained. Theorem 2.2.5 (Theorem 10, Hogan (1973)) If each component of g is a lower semicontinuous function on X x(y} then Q is closed at y . To obtain upper semicontinuity of fi some sort of compactness condition is required in order to ensure that i f y^ y and x n G fi(yn), then x n has a subsequence converging to some x in fi(y). For example, i t is easy to see that the assumption that u{ft(y)|y G V} is contained in a compact set is suf f ic ient , where V is a neighborhood of y. Suff icient conditions for lower semicontinuity of fi are more d i f f i c u l t to obtain. A typical result is the following one, proved by Geoffrion and appearing in Hogan's paper. Theorem 2.2.6 (Theorem 12, Hogan (1973)) If X is convex and normed, i f each component of g is continuous on y x n[y) and concave in x for each fixed y e Y, and i f there exists an x such that g(x,y) < 0, then fi is l . s . c . at y. Theorem 2.2.6 contains the Slater type condition g(.x",y) < 0. Some other conditions not requiring s t r ic t inequality are discussed in Hogan (1973). See also Evans and Gould (1970). 2.3 Continuity on Product Spaces The results of the previous section proving upper semicontinuity of the map M at a point y assumed continuity of the function f on y x fi(y). Such an assumption is standard. In fact , a l l but one of the papers cited in Section 2 make that assumption. The sole exception is the paper of Dantzig, Folkman, and Shapiro (1967), where the basic supposition is that i f each f ( - ,y) and f (• ,y) are continuous on X, and y ->• y , then f ( * » y ) ->• f ( * » y ) uniformly on compact subsets of X. The authors then show that functions f continuous on X x y have the uniform convergence property, and i t is seen that uniform convergence on compact sets and continuity on a product space are closely related. If one is interested in the continuity properties of M over a l l of Y, and not just at a single point y , then the above assumptions become f is continuous on X x Y; (1) f (* ,y) is continuous on X for each y e Y and f ( - » y ) •*• f ( * .7) uniformly on compact subsets of X whenever y y. (2) Conditions (1) and (2) are well known to be equivalent i f X and Y are local ly compact, although we have not seen a formal state-ment of that fact . For completeness, the exact nature of the relat ion-25 ship between (1) and (2) wi l l now be established. The next lemma shows that (1) implies (2) in general topological spaces Lemma 2.3.1 Let and X 2 be topological spaces and let (M,d) be a metric space. Suppose that g : Xj x X 2 M is continuous on XjxX,,. Let X j e Xj and suppose C 2 is a compact subset of X 2 . Then, gU-p* ) -> g ( x p ' ) uniformly on C 2 whenever X j ->• X j . Proof Let e > 0. It must be shown that there exists a neighbor-hood U(x^) of X j such that d [ g ( x ^ , x 2 ) , g ( x p X 2 ) ] < e whenever e UCxj) and x 2 e C 2 > From the continuity of g on Xj x X 2 i t follows that for each x 2 e C 2 there exist open neighborhoods V(x~2) of x"2 and U(x^ ;><2) of x^ such that d [g (x 1 , x 2 ) , g(x 1 ,x 2 ) ] < e/2 (3) whenever X j e u ^ ; ^ ) and x 2 e V(x"2). The family {vCx 2) |x 2 e C2> forms an open cover of the compact set C 2 > so there exists a f in i te 1 n subcover, say v(x 2 ) , . . . ,V(x^ ). Consider the corresponding neighborhoods U C x -^Xg 1 ) , 1 < i < n , and let Ufxj) = U(x"j ; x 2 1 ) n . . .n U tx j .x^ ) . Then U(7j) is a neighborhood of X j . Now let x 2 e c . Then x 2 e Vfx,,1) for some i , 1 < i < n. The tr iangle inequality and (3) then yield d [g (x 1 , x 2 ) , g(x"1,x2)] <d[g(x j ,x 2 ) , g(x" 1,x 2 1)] + d [ g ( x 1 , x 2 1 ) , g(x 1 ,x 2 ) ] < e for a l l X j 6 U(xj). • 26 Remark If Xj and X 2 are metric spaces, then Lemma 2.3.1 follows 1 direct ly from the uniform continuity of f on compact subsets Xj x X 2 > It is easy to show that (2) implies (1) in local ly compact spaces. Lemma 2.3.2 Let Xj and X 2 be local ly compact and let (M,d) be a metric space. Suppose g : Xj x X 2 M. Assume that g{x^,') is con-tinuous on X 2 for each Xj in X ^ and that g(x^,-) -*• g ^ , * ) uniformly, on compact subsets of X 2 whenever x^ -»- x^. Then g is continuous on Proof Fix ( ^ , x 2 ) e X j x X 2 and let e > 0. By the triangle in-equality d[g(x 1 ,x 2 ) ,g(x ' 1 ,x ' 2 ) ] < d [g (x 1 , x 2 ) ,g (x 1 , x 2 ) ] + d[g(xl,x2),g(xl,x2)] Since g(Xj,») is continuous at 3T2 and X 2 is local ly compact, there is a compact neighborhood NCx"2) of x^ such that d [g (x 1 5 x 2 ) ,g(-x^,x2)] < e/2 whenever X 2 G N ( 7 2 ) . By assumption g(xj,*) -*• g(x, # ) uniformly on NCx2) whenever Xj -> x^. That i s , there exists a neighborhood M(xj) of Xj such that d [g(x l s x 2 ) . g ^ . x , ? ) ] < e/2 whenever Xj £ M(Xj) and x 2 eN("x 2 ) . Combining the above inequalit ies gives d[g(xj,x 2 ) .glx^x^)] < e whenever X J 6 H ( X J ) and x 2 eN(x" 2 ) . • 2 7 Chapter 3 Connectedness 3.1 P r e l i m i n a r i e s Our main o b j e c t i v e i n t h i s chapter i s to i n v e s t i g a t e the connected-ness o f the se t o f Pareto e f f i c i e n t and weakly Pareto e f f i c i e n t a l t e r -na t i ves f o r the vec to r maximizat ion problem "max" ( f 1 , ( x ) , . . . , f (x ) ) x e S i n which the c r i t e r i o n func t i ons f j , . . . , f are cont inuous and quasiconcave and S i s a compact convex s e t . We show tha t f o r t h i s c l a s s o f c r i t e r i o n func t i ons the se t o f weakly Pareto e f f i c i e n t a l t e r n a t i v e s i s connec ted , but t ha t the se t o f Pareto e f f i c i e n t a l t e r n a t i v e s i s not n e c e s s a r i l y connec ted . However, i t i s shown tha t the set o f Pareto e f f i c i e n t a l t e r n a t i v e s i s connected f o r some important subc lasses o f quas i -concave f u n c t i o n s . F u r t h e r , the r e s u l t s extend to the non-compact case under reasonable c o n d i t i o n s . Current knowledge regard ing c o n n e c t i v i t y i s e s s e n t i a l l y l i m i t e d to the case o f concave o b j e c t i v e f u n c t i o n s , i n which i t i s known tha t the se t o f Pareto e f f i c i e n t a l t e r n a t i v e s i s connec ted , as we l l as the se ts o f a l t e r n a t i v e s maximal w i th respec t to orders de f ined by more general cones (see Naccache ( 1 9 7 8 ) and B i t r a n and Magnanti ( 1 9 7 9 ) ) . In the s p e c i a l case o f l i n e a r c r i t e r i a , parametr ic l i n e a r programming shows tha t the se t o f Pareto e f f i c i e n t a l t e r n a t i v e s i s connected by l i n e segments. 28 For non-concave c r i t e r i a , the on l y r e s u l t o f which we a re aware i s tha t o f Choo (1980) ; namely, t ha t the se t o f weakly Pareto e f f i c i e n t a l t e r n a t i v e s i s connected by l i n e segments f o r the 1 i n e a r l y ' c o n s t r a i n e d , m u l t i - c r i t e r i o n l i n e a r f r a c t i o n a l programming program w i th a bounded se t o f a l t e r n a t i v e s . B i t r a n and Magnanti (1979) note tha t one reason fo r s tudy ing c o n n e c t i v i t y i s tha t a vec to r max imizat ion problem may have many d i f f e r e n t Pareto a l t e r n a t i v e s , and i t may be necessary to s e l e c t one or severa l o f these which are best w i th respec t to some a u x i l i a r y c r i t e r i o n . In such a s i t u a t i o n one p a r t i c u l a r l y d e s i r a b l e proper ty o f the se t o f Pareto a l t e r n a t i v e s i s tha t o f connectedness , f o r i t imp l i es t ha t to move from one Pareto e f f i c i e n t a l t e r n a t i v e to any o ther we may r e s t r i c t ou rse l ves to l o c a l movements among the se t o f Pareto e f f i c i e n t a l t e r -na t i ves o n l y . Examples o f procedures tha t i nvo l ve a l o c a l search o f Pareto opt ima i nc l ude an i n t e r a c t i v e programming a l go r i t hm due to G e o f f r i o n , Dyer , and Feinberg (1 973.), and some mathematical programming a lgor i thms to be presented in Chapter 4 . The remainder o f t h i s chapter c o n s i s t s o f four s e c t i o n s . Some bas i c d e f i n i t i o n s and no ta t i on are presented in Sec t i on 2. In the t h i r d s e c t i o n the t o o l s necessary f o r the c o n n e c t i v i t y proofs are deve loped. They i n c l u d e a parametr ic r ep resen ta t i on o f the set o f weakly Pareto e f f i c i e n t a l t e r n a t i v e s , some theorems about upper semicont inuous po in t to se t maps, and a b r i e f rev iew o f c o n n e c t i v i t y r e s u l t s f o r concave c r i t e r i o n f u n c t i o n s . S e c t i o n 4 a p p l i e s the r e s u l t s o f S e c t i o n 3 to the case o f a compact se t o f d e c i s i o n s . The f i n a l s e c t i o n extends some o f the theorems o f Sec t i on 4 to the non-compact c a s e , and b r i e f l y 29 considers possible extensions to more general preference structures. The approach taken in this chapter is similar to that of Naccache (1978) and Bitran and Magnanti (1979), except that we no longer have access to a l l the convexity properties available there. 30 3.2 B a s i c D e f i n i t i o n s and Nota t ion In t h i s chapter we w i l l r e s t r i c t a t t e n t i o n to E n , a l though some o f the r e s u l t s a re v a l i d i n much more general s e t t i n g s . I t w i l l be assumed t h a t the p r e a l va lued c r i t e r i o n f u n c t i o n s f j,...,f are quas icon -cave on a convex se t S c E n . A f u n c t i o n f . i s s a i d to be quasiconcave i f i t s upper level sets, {x | f . . (x ) > a}, are convex f o r each rea l number a. E q u i v a l e n t l y , f . i s quasiconcave i f f ^ e x j + ( l - e ) x 2 ) > min [ f . ( x j ) , f . ( x 2 ) ] whenever x 2 e S and 0 < 6 < 1. f . i s s a i d to be strongly quasiconcave i f f . ( ex j + ( l - e ) x 2 ) > min [ f ^ X j ) , f . ( x 2 ) ] whenever X j , x 2 e s and 0 < e < 1. I t i s obvious t ha t s t rong q u a s i c o n c a v i t y i m p l i e s q u a s i c o n c a v i t y . We note by E ( S , f ) ( r e s p . E ( S , f ) ) t h e se t o f Pareto e f f i c i e n t ( r e s p . weakly Pareto e f f i c i e n t ) a l t e r n a t i v e s f o r the vec to r max imiza t ion problem wi th se t o f a l t e r n a t i v e s S , and c r i t e r i a f = ( f ^ , . . . , ^ ) . P' .n . A se t A c E " i s separated i f i t can be w r i t t e n as A = Aj u A 2 , where Aj n A 2 = Aj n A 2 = ((>, and the bar denotes the c l o s u r e o p e r a t i o n . E q u i v a l e n t l y , A i s separated i f t he re e x i s t open se t s Oj and 0 2 such tha t A c Oj u 0 2 , A n 0. / A n 0 2 and A n Oj n 0 2 = I f A i s not separated then A i s s a i d to be connected. I t i s we l l known t ha t i f A i s connected and A c B c A , then B i s connected. A l s o , i f {A^|1 e 1} i s a f a m i l y o f connected s e t s such t h a t n {A^ | i e 1} ^ , then u {A. | i e 1} i s connected. 31 3.3 Upper Sem icon t i nu i t y and Paramet r ic Representa t ions The c o n n e c t i v i t y proofs w i l l r e q u i r e some r e s u l t s concern ing upper semicont inuous po in t to se t maps and the s t a b i l i t y p rope r t i es o f parametr ic o p t i m i z a t i o n problems. In a d d i t i o n , i t w i l l be necessary to ob ta in a parametr ic r e p r e s e n t a t i o n o f the se t o f weak Pareto or Pareto e f f i c i e n t a l t e r n a t i v e s . F i r s t , the necessary upper s e m i c o n t i n u i t y r e s u l t s w i l l be deve loped. We begin by showing t ha t cont inuous f unc t i ons and upper semicont inuous maps share the p roper ty o f p rese rv i ng connectedness. We have not seen a s e l f conta ined proof o f t h i s b a s i c f a c t and present a s imple one below ( the r e s u l t has appeared i n Naccache (1978) and , i n a r e s t r i c t e d fo rm, i n B i t r a n and Magnanti (1979) ) . I f \> i s a po in t to se t map, i t i s necessary to assume t ha t i|/(w) i s connected fo r each w i n i t s domain, an assumption tha t i s always s a t i s f i e d i n the s i n g l e va lued case . Theorem 3.3.1 Let V c E n , W c E p , and suppose W i s connected. Let \p be an upper semicont inuous po in t to se t map from W to V such tha t ij>(w) i s connected f o r each w e w. Then ij>(W) = u U (w) |w e W} i s connec ted . Proof Suppose tha t i|>(W) i s s e p a r a t e d ; tha t i s , t he re e x i s t open s e t s A and B such tha t i^ (W) c A u B , Aj = A n ^(W) f <p, Bl = B n ^(W) f <p, and Aj <~> B j = <j>. Let w e w. S ince ^(w) i s connected by hypo thes is and cp f ^(w) c ifi(W), i t f o l l ows tha t e i t h e r ^(w) c Aj or ijj(w) c B j , but not bo th . Let W A = {w € W|<Kw) c A j } , and W& = {w e W|^(w) c B 1 > . C l e a r l y W = W A u Wg. 32 Let w belong to the closure of W .^ If w e Wg, we have if>(w) c Bj c B. Thus by the upper semicontinuity of ^ and the fact that W = WA u WB there exists a neighborhood H of w such that (^w) c Bj for a l l w e H nw . .But H must contain points w of since w is in the closure of W .^ But (^w) c Aj for such points, contradicting ip(w) c B^. Hence <j/(w) c A^; that i s , w e w^ . Simi lar ly , no point of the closure of Wg belongs to W .^ We then have that W = W^ u Wg is separated, establishing the theorem. • Combining Theorem 3.3.1 and Corollary 2.2.4 yields the following key result . Theorem 3.3.2 Let V c E n be compact and W c E p be connected, and suppose that g(v,w) is a real valued function continuous on V x W. Let X(w) be the solution set to the problem max (g(v,w)|v e V} and suppose that X(w) is connected for each w e W. Then u {X(w)|w e W} is connected. Proof The map i|> : w X(w) is upper semicontinuous by Corollary 2.2.4 and X(w) is non-empty and connected for each w in the connected set W. Hence i|»(W) = u {X(w)|w e w> is connected by Theorem 3.3.1. • 33 The connectedness of E (S,f) for general continuous quasiconcave W cr i te r ia may be established using Theorem 3.3.2 and a representation of E (S,f) as the union of the solution sets of a certain parametrized w family of optimization problems to be developed later in this section. It wil l be seen in Section 4 that E(S,f) may be disconnected for quasiconcave c r i t e r i a , and i t is of interest to determine some sub-classes of quasiconcave c r i te r ia for which E(S,f) is connected. To this end, we now br ief ly review some connectivity results for the case in which the cr i ter ion functions are concave. Suppose X = ) e E p , and let E p denote the positive orthant in E P ; that i s , E p ={X e E p | x . > 0, 1 < i < p}. Assume that the cr i ter ion functions f^,...,f^ are concave and continuous on the compact convex set S. For each X e E P define the problem P Q(x) max { 2 X - f . (x) |x e S). i= l 1 1 Geoffrion (1968) shows that i f x solves Q(x) then x is properly Pareto efficient; that i s , there exists a scalar M > 0 such that for every x e S and each index i satisfying ^.(x) >f . . (x) , the inequality Mx)'- f,(x) _J ] < M f j ( x ) - f j ( x ) is valid for at least one index j such that f.(x) < f.(.x). Further, he v J shows that 7 is properly Pareto e f f ic ient only i f x solves Q(x) for some 34 Now, the solution set to each problem Q(x) is non-empty and convex, hence connected. Moreover,Ep is connected. From these facts and Theorem 3.3.2 i t follows easi ly that the set of properly Pareto ef f ic ient al ternatives, E* (S , f ) , for a concave vector maximization problem is connected. It can then be shown (e.g. Bitran and Magnanti (1979)) that E*(S,f) c E (S , f ) c E* (S , f ) , whence E(S,f) is connected. Connectedness of E(S,f) for concave cr i te r ia implies that the same is true for an important subclass of quasiconcave cri ter ion functions; namely, the class of concave transformable functions. A function f^ is said to be eonoave transformable i f there exists a s t r i c t l y increasing function g.. defined on the range of f. such that h.. = g: o f . is a concave function. It can be easi ly shown that i f f.. is concave transfor-mable then f.j is quasiconcave (e.g. Zang (1980)). Now consider the following simple lemma. Lemma 3.3.1 Let fj f be real valued functions defined on S, and let g ^ , . . . , g be s t r i c t l y increasing functions of a real variable such that g i is defined on the range of f . , 1 < i < p. Define h.. = g.. «• f 1 < i < p, and let f = (fj f ) and h = ( h j , . . . , h p ) . Then E ( S , f ) = E(S,h) and E w (S, f ) = E w (S,h) . Proof Suppose x € E(S,f) and h(y) > h(x). Then f(y) > f(x) by the s t r i c t l y increasing property of each g.. But then f(y) = f(x) 35 since x e E(S, f ) . Hence h(y) = h(x) since the g i are s t r i c t l y increasing. Thus x e.E(S.h) . This establishes E(S,f) c E(S,h). Similarly E(S,h) c E(S, To see that E w (S, f ) = Ew(S,h) observe that the s t r i c t l y increasing property of each g^ implies that i f x and y belong to S, then f(y) > f(x) i f f h(y) > h(x). Thus i f x e E ( S , f ) and h(y) > h(x) we have f(y) > f (x ) , a contradiction. So x e E (S,h). Similarly x e E (S,h) implies x e E (S , f ) . • w From Lemma 3.3.1 we conclude that E(S,f) is connected for quasiconcave c r i te r ia which are concave transformable. In the absence of concavity of the cr i ter ion functions, i t is well known that the family (Q(x)} may not generate a l l Pareto (or weakly Pareto) ef f ic ient solutions. Moreover, the solution sets , X(x), may not be connected, and E(S,f) may be disconnected (see Example 3.4.1). Thus, Theorem 3.3.2 cannot be used in conjunction with Q(x) to show connectivity of E(S,f) i f the c r i te r ia fa i l to be concave transformable. We now develop a parametric representation of E ( J(S,f) to which w Theorem 3.3.2 may be applied when the c r i te r ia are merely quasiconcave. To develop the parametrization we need a boundedness condition on the cr i ter ion functions. Assume that 0 < inf { f i (x) |x e S) for each i , 1 < i < p. For each x = ( x ^ - . - . X ) e E p define function L(x,x) = min IX.f.(.x)}. 1<1< p 1 1 Observe that L(x,x) is well defined and s t r i c t l y positive on S. For each X e E P define the optimization problem P(x ) max { L ( x , x ) | x e S}. Then our f am i l y o f o p t i m i z a t i o n problems i s { P ( x ) | X e E P } . Theorem 3 .3 .3 Suppose f = ( f , , . . . , f ) i s such tha t 0 < i n f { f . ( x ) | x e S } , 1 < i < p. Then x e S i s weakly Pareto e f f i c i e n t i f and on l y i f x so l ves P (x ) f o r some x e E p . Proof Suppose x f E w ( S , f ) . Then the re e x i s t s x* e S such tha t f ( x J ) > f ( x ) . Let x e E p . By p o s i t i v i t y o f f and x i t f o l l ows t ha t A j f j (x1) > A-f j(x), 1 < 1 < p. Thus Kx1,*) > L ( x , x ) , imp ly ing tha t x does not s o l v e P ( x ) . Conve rse l y , suppose x e E ( S , f ) and d e f i n e X by X. = l / f - ( x ) , 1 < i < p. C l e a r l y X e E P . Moreover, x so l ves P ( x ) . I f n o t , there e x i s t s x* e S such t ha t L f x ^ x ) > L ( x , x ) = 1. I t then f o l l ows from the d e f i n i t i o n o f L ( x 1 , x ) t ha t 1 < f ^ x 1 ) X. = f1(x1)/f.(x)> 1 < i < p. That i s , f ^ (x ) < f ^ ( x ^ ) , l < i < p, a c o n t r a d i c t i o n . • Observe t ha t i f f i s assumed to be bounded from below then there i s no l o s s o f g e n e r a l i t y i n assuming tha t 0 < i n f { f ^ ( x ) | x e S} i n Theorem 3 . 3 . 3 . This i s t r ue because E ( S , f ) i s i n v a r i a n t under the a d d i t i o n o f cons tan ts w to the func t i ons f... A l s o , i f S i s compact and f i s cont inuous on S then a boundness c o n d i t i o n i s always s a t i s f i e d . Theorem 3 . 3 . 3 i s very s i m i l a r to r e s u l t s ob ta ined by Bowman (1975) and Choo (1980) . In g e n e r a l , o f c o u r s e , E ( S , f ) and E ( S , f ) do not c o i n c i d e . The f o l l o w i n g r e s u l t g ives c o n d i t i o n s under which E ( S , f ) = E w ( S , f ) , and w i l l be use fu l i n e s t a b l i s h i n g the connectedness o f E ( S , f ) f o r the c l a s s o f s t r o n g l y quasiconcave c r i t e r i o n f u n c t i o n s . 37 Theorem 3 .3 .4 Suppose 0 < i n f { ^ ( x ) |x e S } , 1 < 1 < p, and tha t whenever P (x ) admits a s o l u t i o n the s o l u t i o n i s un ique. Then x € S i s weakly Pareto e f f i c i e n t i f and on l y i f x i s Pareto e f f i c i e n t . Proof C l e a r l y E ( S , f ) c E ( S , f ) . Conve rse l y , l e t x e E w ( S , f ) . w w Suppose x 1 e S and f ( x 1 ) ^ f ( x ) . We want to show fix1) = f ( x ) . Wr i te f ^ x 1 ) = ^ . ( x ) + Q l - , 1 < 1 < p. Then > 0 f o r each i and a t l e a s t one a . = 0 s i nce x i s weakly Pareto e f f i c i e n t . S a y a = 0 . As i n the proof o f Theorem 3 . 3 . 3 we have tha t x so l ves P ( x ) , where \ . = l / f^x) , and L ( x , x ) = 1. Thus, f o r each i , X ^ - U 1 ) = x . ( f . ( x ) + c^.) = 1 + x^a.. Since X r = 0 and a l l q u a n t i t i e s i nvo l ved are non n e g a t i v e , i t f o l l ows t ha t Ux ^ X ) = 1. Thus x 1 so l ves P ( x ) . But the s o l u t i o n to P (x ) i s unique by assumpt ion ; so x 1 = x and f ( x * ) = f ( x ) , as r e q u i r e d . • We c l o s e t h i s s e c t i o n by no t ing the f o l l o w i n g d i r e c t consequence o f Theorems 3 . 3 . 3 and 3 . 3 . 4 . Let T c EN be bounded and d e f i n e x e T to be Pareto e f f i c i e n t i f the re e x i s t s no y e T such tha t y > x and y f x. Def ine weak Pareto e f f i c i e n t po in t s to be those po in t s x e T such t h a t t he re i s no y G T such tha t y > x . By t a k i n g f^ : x -> x ^ , 1 < i < n , we immediate ly ob ta i n tha t the se t o f Pareto e f f i c i e n t ( r e s p . weakly Pareto e f f i c i e n t ) po in t s o f T i s connected i f the s o l u t i o n se t to the problem max min ( X . x . ) x e S 1 < i < n 1 i s unique ( r e s p . connected) f o r each ( x . , , . . . , x „ ) G E". 38 3.4 Connectedness Results Unless stated otherwise, i t wil l be assumed for the rest of the chapter that a l l functions are continuous and quasiconcave on the closed convex set S. In this section i t is also assumed that S is compact. Under such assumptions the connectedness of E..(S,f) for quasiconcave w functions, and of E(S,f) for strongly quasiconcave functions, follow easily from the results of the previous section. Before proving connectedness of the Pareto sets we need to present some elementary properties of quasiconcave functions. For a proof of the next lemma see Avriel (1980). Lemma 3.4.1 Let g be a continuous quasiconcave function defined on the closed convex set S. Then the set of points at which g achieves i ts global maximum is closed and convex. If g is strongly quasiconcave and achieves i ts maximum on S then i t does so at exactly one point of S. We also need some special results concerning L(x,A). Lemma 3.4.2 Suppose fj f are quasiconcave (resp. strongly quasiconcave) on S. Then L(x,A) is quasiconcave (resp. strongly quasiconcave) on S. Proof Let Xj ,x 2 e S and 0 < e < 1. Assume that f ^ , . . . , f are strongly quasiconcave. Then L(ex ,+ ( l -e )x 9,x) = min {x.f . ( e x - . + d - e J x J } 1 c 1 < i < p 1 1 1 c > min {mint x.f , ( x , ) ,x,f . ( x ? ) ] y 1 < i < p 1 1 1 1 1 c = min[ min { X . f . - U j } , min {X.f . ( x 9 ) } ] 1 < i < p 1 1 1 1 < i < p 1 1 2 . = mini L(x A) ,L(x 2 ) l » where the i n e q u a l i t y f o l l ows from s t rong q u a s i c o n c a v i t y and p o s i t i v i t y o f the X.. The proof f o r merely quasiconcave f . i s i d e n t i c a l , except t ha t the s t r i c t i n e q u a l i t y may be r e l a x e d to an i n e q u a l i t y . • The connectedness r e s u l t s may now be proved. Observe tha t i t f o l l o w s from the c o n t i n u i t y o f f and the compactness o f S tha t both E (S,f) and E ( S , f ) a re non-empty. Moreover , i f E ( S , f ) o r Eu(S,f) i s connected then c o n t i n u i t y o f f imp l i es t ha t the cor respond ing w se t o f (weak) Pareto e f f i c i e n t outcomes i s connected. Theorem 3 .4 .1 Suppose fj,...,f are quasiconcave on the convex compact se t S . Then E ( S , f ) i s connected. w Proof By c o n t i n u i t y o f f and compactness o f S , we have tha t f ( S ) i s compact, so w i thout l o s s o f g e n e r a l i t y i t can be assumed tha t 0 < i n f { f . ( x ) | x e S } , 1 < i < p. By Theorem 3 . 3 . 3 . E ( S , f ) = u{X(x)|x e E P } , 1 W 5 where X(x) i s the s o l u t i o n to P(x). I t w i l l be s u f f i c i e n t t o v e r i f y t ha t Theorem 3 .3 .2 a p p l i e s . Let X e E p . Then L(x,x), the minimum o f p cont inuous f u n c t i o n s , i s cont inuous on S . By Lemma 3 . 4 . 2 L(x,x) i s quasiconcave on S . 40 By Lemma 3.4.1 and compactness o f S , X(x) i s non-empty and convex.,, hence connected. I t remains on l y to v e r i f y tha t L(x,x), cons idered as a f u n c t i o n on S x E p , i s cont inuous t h e r e . To see t h i s observe tha t f o r s each i , x . f . ( x ) i s cont inuous on S x E p s i n c e i t i s the product o f the two func t i ons X X. and x f . ( x ) , each cont inuous on S x E p . Hence L(x,x) = min ( X . f . ( x ) } i s cont inuous on the product s e t . Thus 1 < i < p 1 1 a l l the c o n d i t i o n s o f Theorem 3 .3 .2 are s a t i s f i e d , imp ly ing tha t u {X (X ) |X € E p }= E ( S , f ) i s connected. • C o r o l l a r y 3 .4 .1 Suppose f j f are s t r o n g l y quasiconcave on the convex compact se t S . Then E ( S , f ) i s connected. Proof By Theorem 3.4.1 E ( S , f ) i s connected. L(x,x) i s s t r o n g l y quasiconcave by Lemma 3 . 4 . 2 , whence i t f o l l ows from Lemma 3.4 .1 tha t the s o l u t i o n to each problem P(x) i s un ique. But then E ( S , f ) = E ( S , f ) w by Theorem 3 . 3 . 4 , imp ly ing the c o n n e c t i v i t y o f E ( S , f ) . • The f o l l o w i n g example shows t ha t E ( S , f ) may be d isconnected when f i s merely quas iconcave. Example 3 .4 .1 L e t s = [ - 1 , 1 ] . Def ine f 2 ( x ) 0 1 f -1 < x < 0 x i f 0 < x < 1 f 2 ( x ) « < -x i f -1 < x < 0 0 i f 0 < x < 1 Then f1 and f 2 are quasiconcave on S , and E w ( S , f ) i s the e n t i r e i n t e r v a l [ - 1 , 1 ] . However, E ( S , f ) c o n s i s t s o f the two po in ts -1 and 1. A l s o , the 41 solution set , {-1,1}, to max {.5(f 1(x)+f 2(x))|x e S} is disconnected (see Figure 2). Figure 2 The next example shows that strong quasiconcavity of the cr i te r ia is not suff ic ient for connectivity of the set of properly Pareto ef f ic ient alternatives. Example 3.4.2 Let fj(x) = x and f 2 (x) = -x . Then fj and f 2 are strongly quasiconcave and E(S,f) is the entire interval [-1,1]. However, x = 0 is not properly Pareto ef f ic ient since f^(x)/f 2(x) = -1/x becomes unbounded as x approaches 0. 42 3.5 Extension to Non-Compact Sets When the compactness assumption on S is dropped, connectedness may no longer hold. We derive suff ic ient conditions for the non-emptyness and connectedness of E ( S , f ) and E(S,f) when S is not compact, and give an example showing that E (S,f) and E(S,f) may be disconnected w when these conditions are not sa t is f ied . Some additional notation wil l be required. Let a e E p . Define S(a) = {x e S|f(x) > a}, Eu((a) = E (S(a) ,f) and — w w E(a) = E(S(a) , f ) . Let A. = f ^ S ) be the range of f . , 1 < i < p, and S6^ A A*x»«»xA_« i p 2 1 1 2 Lemma 3.5.1 E(a ) c E(a ) whenever a < a . Moreover, i f there exists a" G A such that E(a~) f <p, then E(S,f) f <f>, and E(S,f) = u{E(a)|a < a , a E A}. The same assertions hold i f we replace "E" by " E w " . 2 1 1 2 Proof First we show that E(a ) c E(a ) whenever a < a . Let x e E(a 2) c S(a 2) c S U 1 ) . If x $ E(a ! ) there exists y G Sta 1) 2 2 2 such that f(y) > f(x) > a , implying y G S(a ) and x ^ E(a ), a 2 1 contradiction. Hence E(a ) c E(a ). Now suppose x e E(a). If 7^ E(S,f) there exists y e s such that f(y) > f(x") I a , implying x" ^ E(a"), a contradiction. Thus E(S,f) f <p. Let a < ¥ . Then we have E(a") c E(a). Moreover, i f x G E(a) then x G E(S,f) as above. Thus E(a) c E(S,f) for each a < a , establishing that u {E(a)|a < a} c E(S, f ) . F ina l ly , suppose y G E(S, f ) . We have to show that there exists an a G A, a < a", such that y G E(a). Let x" G E(a") and let 43 = min [ ^ . ( x ) , f ^ y ) ] , 1 < 1 < p. Then a . . , a p ) G A , a < f (x") , and f ( y ) > a . Hence y G S ( a ) . I f y ^ E(a) there e x i s t s z e S(a) c S such t ha t f ( z ) > f ( y ) > a . Th is i m p l i e s y 4 E ( S , f ) , a 4 c o n t r a d i c t i o n . Hence y e E ( a ) . The a s s e r t i o n s f o r " E w " are proved i n an i d e n t i c a l f a s h i o n , except tha t " > " r ep laces " > " whenever the l a t t e r appears . • Theorem 3.5 .1 Suppose f j , . . . , f are quasiconcave ( r e s p . s t r o n g l y quasiconcave) on the c losed convex se t S , and tha t S(a) i s compact f o r each a G A. Then E ( S , f ) ( r e s p . E ( S , f ) ) i s non-empty and connected. w Proof Let a e A be such tha t S(a) f 4>. S(a~) i s compact by assumption and convex by q u a s i c o n c a v i t y o f the components o f f . From Theorem 3.4 .1 i t f o l l ows t ha t E w ( a ) i s non-empty and connected. Let a < a . By Lemma 3.5.1 E (a) 3 E ( a " ) , and E (a) i s connected by the •~ W W W same arguments as above. Again us ing Lemma 3 . 5 . 1 , we can w r i t e E w ( S , f ) = u { E w ( a ) | a < a} , thus exp ress ing E, . (S, f ) as a union o f connected se ts having the non-w empty i n t e r s e c t i o n E (a"). Hence E ( S , f ) i s connected. I f the c r i t e r i a w w are s t r o n g l y quas iconcave , we can argue as above to e s t a b l i s h the c o n n e c t i v i t y o f E ( S , f ) , the on l y d i f f e r e n c e being tha t C o r o l l a r y 3 .4 .1 i s used in p lace o f Theorem 3 . 4 . 1 . • 44 In order to app ly Theorem 3.5.1 i t would be d e s i r a b l e to have some c o n d i t i o n , independent o f S , which ensures the compactness o f S ( a ) . The f o l l o w i n g c o r o l l a r y p rov ides such a c o n d i t i o n . C o r o l l a r y 3 .5 .1 Suppose tha t f .,...,f are quasiconcave ( r e s p . s t r o n g l y quasiconcave) on the c l osed convex se t S , and tha t at l e a s t one o f the c r i t e r i o n func t i ons has compact upper l e v e l s e t s . Then E ( S , f ) ( r e s p . E ( S , f ) ) i s connected, w Proof Suppose tha t f j has compact upper l e v e l s e t s . Let a = ( a j , . . . , a p ) . Then P S(a) = {x e s | f ( x ) > a} = S n [ n { x | f . ( x ) > a.}] . 1=1 1 1 Now S i s c l osed by assumpt ion , and each se t { x | f . ( x ) > a.} i s c l osed by c o n t i n u i t y o f f . , 1 < i < p. Hence S(a) i s c l o s e d . But ( x | f j ( x ) > a^} i s compact. Thus S(a) i s a c l osed subset o f a compact se t and must be compact. The r e s u l t now f o l l ows from Theorem 3 . 5 . 1 . • Observe tha t the compactness o f S(a) imp l i es the compactness o f f ( S ( a ) ) . I f i t i s assumed on ly t ha t f ( S ( a ) ) i s compact, then c o n n e c t i v i t y o f the se t o f Pareto outcomes can be e s t a b l i s h e d . Theorem 3 .5 .2 Suppose f^,...,f^ are quasiconcave ( r e s p . s t r o n g l y quas iconcave) on the c l osed convex se t S and tha t f ( S ( a ) ) i s compact f o r each a e A. Then the se t o f weakly Pareto e f f i c i e n t ( r e s p . Pareto e f f i c i e n t ) outcomes, f ( E ( S , f ) ( r e s p . f ( E ( S , f ) ) , i s non-empty and connected. 45 Proof F i rst we show that f(E (a)) is connected for each a e A. w If E (a) = cp there is nothing to prove, so assume E (a) f <j>. w w Let X = ( A j , . . . , X ) G E P and consider the problem * P'(x.a) max {L'(y,x)|y e f(S(a))}, where L'(y,x) = min {X^y^l < i < p}. It follows from the continuity of L'(y,x) and the compactness of f(S(a)) that the solution set , X'(x,a), to P'(x,a) is non-empty compact. Now y e X'(x,a) i f and only i f y = f(x) where x e X(x .a), the solution set to the problem P(x,a) max {L(x,x)|x e S(a)} , having the objective function L(x,x) = min { f ^( x ) j 1 < i < p}. Because L(x,x) is quasiconcave by Lemma 3.4.2 and S(a) is convex by quasiconcavity of the f.., we have from Lemma 3.4.1 that X(x,a) is convex, hence connected. It then follows from the continuity of f that X'(x,a) is connected. Since L'(y,x) is clearly continuous on E p x E p , Theorem 3.3.2 then implies that T(a) = u {X'(x,a)|x € E P } is connected. But X'(x,a) = f(X(x ,a)). Hence T(a) = u {f(X(x,a))|x e E p ) (3) = f(u{X(x,a)|x e E p}). Now Theorem 3.3.3 and the invariance of E (a) under translation of the w components of f imply that Ew(a) = u {X(A,a)|x e Ep}. Thus (3) yields f(E (a)) = T(a), whence f(E(a~)) is connected. Now w w choose a e A such that S(a) f Then f(S(a~)) is compact by assumption, implying that E (a) f By Lemma 3.5.1 we can write Ew(S,f) = u {Ew(a)|a < a}. Therefore f(E w(S,f)) = f(u{Ew(a)|a < I}) (4) = u{f(Ew(a))|a < ?}. Now (4) expresses the set of weakly Pareto outcomes, f(E (S,f)), as the w union of a family of connected sets, f(E (a)), having the non-empty intersection f(E (a")). Therefore f(E (S,f)) is connected. If the w w criteria are strongly quasiconcave, i t follows from Lemma 3.4.2 and Theorem 3.3.4 that E (a) = E(a) for each a € A. Then, using Lemma w 3.5.1 and arguing as above, we establish that f(E(S,f)) is connected. • If the criterion functions are concave, then a result of Naccache (1978) establishes the connectedness of the set of Pareto optimal outcomes under an equivalent hypotheses to that of Theorem 3.5.2; namely, that f(S) is EP-compact. The following example of Choo (1980) shows that the sets of weakly Pareto efficient alternatives and outcomes can be disconnected i f S(a) of f(S(a)) fails to be compact for some a e A. In the example we also have E(S,f) = EjS.f). 47 Example 3.5.1 Let S = {x e E 2 | x 1 > 2, 0 < x £ < 4} and let the cr i ter ion functions be given by f^(x) = Xjy(xj+x 2-l) and f 2 (x) = x^/(x^-x 2 By observing that the level sets of fj and f 2 form pencils o.f l ines emanating from (0,1) and (0,3), respectively, i t can be seen that E u i ( s » f ) = E ( s » f ) 1 S the union of the two parallel l ines L. = {xlx. > 2 , x 0 W l i e . and L 2 = {x|Xj > 2 , x 2 = 4}. It can be veri f ied that the image of in t h e ( f 1 5 f 2 ) plane is given by Gj = { ( f j . f ^ l ^ = ^ ( 4 ^ - 3 ) , 1 < f 1 <2} , and that the image of L 2 is G 2 = { ( f j , f 2 ) | f 2 = 3 ^ / ( 4 ^ - 1 ) , 2/5 < f 1 < 1}. Thus f(E(S,f) ) is not connected. It is then easy to see that S(a) is unbounded for some a e A (see Figure 3), and that for such a, f(S(a)) is not compact. In such a case f (E(a)) , though bounded, is neither closed nor connected. f(E(a)) fa i ls to be closed because ( f 1 5 f 2 ) -»• (1,1) as Xj °°, and (1,1) ^ Gj u G^. (See Figure 4). X2 (2,4) Figure 3 48 Figure 4 We close this chapter with a brief discussion of possible extensions of the connectedness results. First observe that Example 3.4.1 shows that the connectivity may fail i f a cone larger than the Pareto cone.defines preferences. To see this, consider the functions of Example 3.4.1, and 2 the set f(S) reproduced in Figure 5, where the cone P ^ E g shown there 4 9 de f i nes p re fe rences . We see tha t the se t M, o f maximal outcomes w i th respec t to P i s the d isconnected se t c o n s i s t i n g o f the po in ts (1,0) and (0,1). The cor respond ing se t o f a l t e r n a t i v e s M, i s the set'{-1,1}. Figure 5 The sets o f maximal outcomes M, and a l t e r n a t i v e s M, may be d isconnected w i th respec t to a cone sma l l e r than the Pareto cone. As an example cons ide r F igure 6 be low, where the f unc t i ons f j and f^ are quas iconcave , i 2 and the p re fe rence cone P i s a s t r i c t subset o f E g . Observe tha t fo r every x , 1 < x < 2, ( f ^ x ) , f 2 ( x ) ) i s cone dominated by (^(2), f 2 (2)) . Thus we see tha t M = {(0,y)|0 < y < 1} u {(2,1)} and M = [ 0,1] u {2} 5 are d isconnec ted s e t s , r v I a 50 f l X The above examples indicate that an extension of the connectivity results to orders other than those given by EJ? or E p may be di f f icul t , and i t is not clear what subset of quasiconcave functions should be considered. One possibility may be to restrict attention to functions whose generalized upper level sets, {x|f-(x) >aTx+a>, are convex for all a in some neighborhood of the zero vector. Taking a - 0 yields quasiconcavity, and i t has been shown that i f f. is convex, then the generalized upper level sets are convex for all a e E n (see Avriel (1980)). 51 Chapter 4 A p p l i c a t i o n s to Mathemat ical Programming : 4.1 P r e ! i m i n a r i e s In c e r t a i n m u l t i p l e c r i t e r i o n d e c i s i o n problems i t may be p o s s i b l e to combine seve ra l d i f f e r e n t c r i t e r i o n func t i ons i n t o a s i n g l e o b j e c t i v e f u n c t i o n , i n which case i t i s na tu ra l to cons ide r a problem o f the form (P) max (u ( f j ( x ) , . . . , f p ( x ) ) |x €= S} where f ^ , . . . , f are con t i nuous , r e a l va lued c r i t e r i o n func t i ons de f ined on a compact se t o f a l t e r n a t i v e s S, and u i s a r e a l va lued f u n c t i o n , cont inuous on the range o f f = ( f j » . . . » f ) and non-decreas ing in each argument, which orders the se t o f a t t a i n a b l e outcomes. Problem (P) may a l s o occur as an o r d i n a r y mathematical programming problem whose o b j e c t i v e f u n c t i o n happens to be o f the above form. In t h i s chapter our main o b j e c t i v e i s to cons ide r the case where there are two c r i t e r i o n f u n c t i o n s , S i s a compact po lyhedra l s e t , and f j and f^ are l i n e a r f r a c t i o n a l s . P a r t i c u l a r a t t e n t i o n w i l l be pa id to func t i ons u ( f ^ ( x ) , f 2 ( x ) ) o f the form c t j f ^ x ) + a 2 f 2 ( x ) . (1) We s h a l l a l s o cons ide r Chebychev o b j e c t i v e s min [ f 1 ( x ) , . . . , f p ( x ) ] , (2) 52 where f f a re quasiconcave on S . 1 p We develop and t e s t a procedure tha t reduces two c r i t e r i o n problems o f the form (P) to a s imple one parameter l i n e a r program and a f i n i t e se t o f one d imensional subproblems. In the s p e c i a l case where u has the form ( 1 ) , the subproblems are shown to be comple te ly t r i v i a l , and (P) i s so l ved e f f i c i e n t l y i n a f i n i t e number o f s t e p s , even though a j f j + m&y ^ e " e i t h e r quasiconcave nor quasiconvex on S ( e . g . S c h a i b l e (1977) ) . F r a c t i o n a l programs w i th an o b j e c t i v e f unc t i on given by (1) occur when the o b j e c t i v e i s to maximize an expected ra te (Almogy and Lev in ( 1971 ) ) , and c e r t a i n f r a c t i o n a l goal programs may a l s o be reduced to the form (1) - see Kornb lu th (1973) . An a lgo r i t hm f o r the s p e c i a l case o f (1) i n which the o b j e c t i v e f u n c t i o n i s separab le has been proposed by Almogy and Lev in (1971) . However, tha t a lgo r i t hm may be i n v a l i d s i n c e Theorem 3 , Almogy and Lev in (1971) i s i n c o r r e c t . A lgor i thms f o r the s p e c i a l case o f maximiz ing the sum o f a l i n e a r and a l i n e a r f r a c t i o n a l f unc t i on under c e r t a i n concav i t y assumptions have been presented by Teterev (1970) and Kanchan (1981) . I f the concav i t y assumptions are not s a t i s f i e d , a parametr ic method o f R i t t e r (1967) or a branch and bound method o f H i rche and Tan (1977) may be a p p l i e d . Computat ional r e s u l t s have not been repor ted fo r any o f the above methods. In g e n e r a l , f r a c t i o n a l c r i t e r i a are common whenever ra tes or r a t i o s are being c o n s i d e r e d , e . g . Ashton and A tk ins (1979) , Mjelde (1978) , Charnes and Cooper (1978) , Ar isawa and Elmagharby (1972) , 53 Gil more and Gomory (1963). Two cr i ter ion problems of the form (P) where the cr i te r ia are concave have been considered by Geoffrion (1967), and certain discrete b icr i ter ion problems have been studied by Pasternak and Passy (1973). The remainder of this Chapter consists of four sections. In Section 2 the basic tools necessary for our procedure wil l be developed; in Section 3 the algorithm i t s e l f wi l l be described and applied to objec-t ive functions of the form (1); Chebychev problems wi l l be discussed in Section 4. Some computational results for problems with up to 300 variables and 150 constraints, together with a small numerical example, wi l l be presented in the f inal section. 54 4 .2 B a s i c Resu l t s The pr imary mo t i va t i on f o r the procedure to be developed i s prov ided by two s imple lemmas. Lemma 4 .2 .1 (Geo f f r i on (1967)) At l e a s t one opt imal s o l u t i o n to (P) i s Pareto e f f i c i e n t . (That i s , there e x i s t s an ~k~ e E ( S , f ) which i s opt imal f o r ( P ) ) . Proof By compactness o f S , and c o n t i n u i t y o f f and u , (P) has a t l e a s t one opt imal s o l u t i o n x ' . S i m i l a r l y the re e x i s t s a po in t x e S maximiz ing f j ( x ) + . . . + f p ( x ) , sub jec t to the a d d i t i o n a l c o n s t r a i n t s f j ( x ) > ^ ( x ' ) , 1 < i < p. Now x" i s Pareto e f f i c i e n t , f o r the con t ra r y c o n t r a d i c t s the cho ice o f x~. But then x so l ves (P) s i n c e u ( f ( x ) ) > u ( f ( x ' ) ) by cho ice o f x and the f a c t t ha t u i s non-decreas ing i n each f . . • Now assume tha t there are on l y two c r i t e r i a , f j and f 2 , and l e t E denote the se t o f Pareto e f f i c i e n t a l t e r n a t i v e s E ( S , f ) . The f o l l o w i n g are we l l de f ined max {f.(x)|x e S} 1 = 1, 2 , max {fjMJx e S , f2(x) > ? 2), max {f2(x)|x e S , fj(x) >J^}. (5) (4) (3) Moreover, f j ( x ) < f j (6) 55 whenever x e E. For each w i n the i n t e r v a l [ f j , f j ] de f i ne the problem P(w) : max { f 2 ( x ) | x e s , f j ( x ) > w}. Then we have the f o l l o w i n g s imple lemma. Lemma 4 . 2 . 2 I f x i s Pareto e f f i c i e n t then the re e x i s t s a s c a l a r w e [ f j , f j ] such tha t x so l ves P(w). Proof Suppose x e E and l e t w = f j ( x ) . By (6) we have w e [ f j , . Moreover, x so l ves P(w) , f o r o therwise there e x i s t s a y e S such tha t f 2 ( y ) > f 2 ( x ) and f j ( y ) > f ^ x " ) , c o n t r a d i c t i n g the Pareto e f f i c i e n c y o f x . • Lemmas 4 .2 .1 and 4 . 2 . 2 imply Lemma 4 . 2 . 3 A s o l u t i o n o f (P) may be found among the Pareto e f f i c i e n t s o l u t i o n s o f P(w) , f_j < w < f j . The computat ional use fu lness o f Lemma 4 . 2 . 3 depends upon the ease w i th which the parametr ic program P(w) may be s o l v e d . In the case o f l i n e a r f r a c t i o n a l o b j e c t i v e f unc t i ons and po lyhedra l S , r e s u l t s o f Choo (1980) show tha t each s o l u t i o n o f P(w) , f j < w < f j , i s Pareto e f f i c i e n t , and tha t P(w) can be so lved as a parametr ic l i n e a r program. We now rev iew these r e s u l t s . The o b j e c t i v e f unc t i ons f o r the b i c r i t e r i o n f r a c t i o n a l programming problem are g iven by 56 < a x > + b i - i ? V x ; < c . , x > + d . where a., and b^ are vec to rs in E , b.. and c . are s c a l a r s , and < , > denotes the inner p roduc t . Assume tha t the denominators o f f^ and f 2 are s t r i c t l y p o s i t i v e on the s e t o f a l t e r n a t i v e s S = {x e E n | Tx < v , x > 0 } , where T i s an m x n mat r i x and v e E m . Suppose a l s o tha t S i s bounded. I t f o l l ows t ha t f j and f^ are we l l de f i ned by (3) and ( 4 ) . For each w e [jf^, l£ P(w) can be w r i t t e n max (< a 2 , x > + b 2 ) / ( < c 2 , x > + d 2 ) P(w) : s . t . Tx < v , x > 0 , < a ^ x > + b j > w(< Cj , x > + d j ) . P(w) i s a l i n e a r f r a c t i o n a l program and the Charnes-Cooper (1962) t r ans fo rma t i on + _ 1 , y = t x 1 " < c 2 , x > + d 2 can be a p p l i e d to i t , r e s u l t i n g i n the row parametr ic l i n e a r program max < a 2 , y > + b 2 t s . t . Ty < tv Q(w): < c 2 , y > + d 2 t = 1 < a 2 , y >+ bjt > w ( < c r y > + d j t ) t > 0 , y > 0 , having the proper ty tha t i f z = ( t , y ) so l ves Q(w), then x = y / t so l ves P(w) , and the opt imal va lues o f Q(w) and P(w) are e q u a l . 57 Choo then suggests the procedure described below to solve P(w). Parametric Procedure Step (1): Solve (3) and (4) to obtain ? 2 and f (Observe that by Charnes and Cooper (1962),the determination of and fj is equivalent to solving two linear programs). Step (2): Apply row parametrics to the linear program Q(w) , _fj <w < f j , to obtain numbers I l = w0 < w l < ••• < w r = T l and corresponding points (y.. .t^), y i e E n, t. 6 E, solving Q(w.), 0 < i < r, where w. occurs at the ith basis change in the parametric solution of Q(w). Step (3): Let x. = y./t. , 0 < i < r. Choo shows that the above procedure is-well defined (that i s , r is finite and w = f,), and that the following basic structural result r 1 3 holds: Theorem 4.2.1 Let E be the set of Pareto efficient alternatives for the bicriterion linear fractional programming problem, and suppose that Xg,...,xr are obtained by the parametric procedure described above. Then r f(E) = u f[x. . , x J , (7) 1=1 1 - 1 1 where [x^_j,x^] is the line segment joining x._j and x^. Thus f(E) is a compact, piecewise smooth, connected arc in E given by (7). 58 4 .3 The A lgor i thm and i t s A p p l i c a t i o n to Max imiz ing the Sum o f Two F r a c t i o n a l Funct ions 4 Theorem 4 .2 .1 enables us to s o l v e Problem (P) by c o n s i d e r i n g f i n i t e l y many one d imensional subproblems ( R ^ ) , de f i ned f o r 1 < i < r , by (R. j ) : max {u ( f j(x) , f 2 ( x ) ) | x e [ x ^ . x . ] } . Observe tha t the maximum f o r (R^) i s we l l de f i ned by c o n t i n u i t y o f f , u , and the compactness o f [ x ^ _ j , x ^ ] . Suppose x. so l ves ( R ^ ) . 1 < i < r , and l e t x^ be such tha t u ( f ( x k ) ) = max { u ( f ( x \ ) ) | 1 < i < r } . Theorem 4 .3 .1 Problem (P) i s so l ved by x ^ . Proof Th is f o l l o w s d i r e c t l y from Theorem 4 .2 .1 and Lemma 4 . 2 . 3 . • We w i l l now show tha t the l i n e a r f r a c t i o n a l form o f the c r i t e r i o n func t i ons permits the reduc t i on o f the subproblems (R^) to a p a r t i c u l a r l y s imple form. To do t h i s i t w i l l be necessary to i n t roduce some n o t a t i o n . Suppose w. j and w . , toge ther w i th x ._ j and x^ , have been obta ined from the Parametr ic Procedure o f the prev ious s e c t i o n , and tha t w.._j < w^. For j = 1, 2 l e t 59 p] = < c . , x . > + d . . r j = < a j ' X 1 - r X i > » t] o < c j . x 1 - x 1 . 1 > , and define A1 + r 2 P l ) B i • * i -i i q 2 r l c i - t 2 p : - P 2 t j D1 = - ( t jqj + P 2 rj ) Theorem 4.3.2 If w .^ = then any point x.. e [ x i j.x..] solves (fy), and ffx. .^) = f(x.) = f (x . ) . If w .^ < w i , then x i = a i x i - l + ( 1 _ a i ) x i ' solves (R^), where = (w.p] - qj) /(w.tj + rj) , and w.j is the solution to the problem (R..) max {u(w,h..(w)) | w..^ < w < w..} where A.w + B. 60 Proof That some x. e [ x^.x^] solves (R.) follows from the continuity of u and f. It follows from Theorem 4.2.1 and the monotonicity of f1 on line segments that fCx^) = f(x.) = fO^) i f w^j** w i. It remains to verify the forms of the various coefficients for the case w^j <w_ These are obtained by direct calculation. In what follows we define x._j = _x, x^ = x", = w, w^ = w, and drop the index i wherever else it appears. First, i t will be verified that f(x) can be expressed in the form (w, h(w)), where h(w) = (Aw + B)/(Cw + D). By (7), i f w e [ w, w] , there is some a e [0, 1] such that w = f.(x ), h(w) = f 0(x ), where l a c a \ = a* + (l-a)x. We have (8) < a ,xa > + b . J a j To f i n d a s u b s t i t u t e (8) i n t o (9). Thi < a .,ax + (l-a)x > + b s gives <c.,ax + ( l - a ) 7 > + d . = f J ( X a K ( j = U 2 ) J J Solving for a yields, for j = 1, 2 r, - W[ < V * > + c g - [ < a 1 > x > + b . ] < a J f x - x > + f j (7 ) [ < C j , x - x > ] (10) 61 To f i n d f 0 ( x ) i n terms o f f . ( x ) we use (10). Set w = f , ( x ) , h(w) = f 2 ( * )» a n d d e f i n e f o r j = 1» 2 p. = < c r 7 > + d . . q . = < a .,x" > + b. , J J J r . = < a . , x - "x > , J J t . = < c . , x" - X > . J J From (10) and (11) we have W l P l " q l h ( w ) p 2 - q 2 r j + wt j " r 2 + h (w ) t 2 ' This g ives ( r 2 q i - g ^ ) - w ( g 2 f 1 + r 2 P j ) K ] ' w ( t 2 p 1 - p 2 t 1 ) - ( t 2 q j + p ^ ) ' The r e q u i r e d form o f h r e s u l t s by s e t t i n g A • ( q 2 t i + r 2 p l ^ ' B = r 2 q l " q 2 r l ' C = t 2 P 2 - p 2 t j , D = - { t 2 q l + P 2 r J ) . A A I t remains to ob ta in the exp ress ion f o r a. Suppose u so l ves ( R . ) . Then (10) and (11) g i ve ct = (wp : - q 1 ) / ( w t 1 + r x ) . Then (8) y i e l d s the requ i red form o f x . • (11) 62 A b a s i c a lgo r i t hm fo r (P) may now be s t a t e d . I t s v a l i d i t y f o l l ows from Theorems 4 .3 .1 and 4 . 3 . 2 . « B a s i c A lgor i thm Step 1: Apply the Paramet r i c Procedure given i n Sec t i on 4 .2 to ob ta i n f 1 = w 0 < w 1 < . . . < w r = f 1 and po in ts x ^ , 0 < i < r. Step 2 : Let u Q = u ( f j ( x Q ) , f 2 ( x 0 ) - ) . For each i , 1 < i < r , de f i ne u.. by max {u(w,h^(w))|w^_j < w < w^} i-p _^ < . " l - l i f w i - l = w i • where h..(w) i s g iven by Theorem 4 . 3 . 2 . Step 3 : Let u k = max {u.. 11 < i < r } , and l e t x k be the cor respond ing s o l u t i o n o f (R^) g iven by Theorem 4 . 3 . 2 . Then x^ so lves ( P ) . I t w i l l now be shown tha t the subproblems (R. ) are so l ved t r i v i a l l y i n the case where u i s a sum o f two l i n e a r f r a c t i o n a l s . Suppose 1 < i < r and t ha t w._j and w^ have been obta ined by the paramet r i c procedure o f Sec t i on 2 . Assume tha t w.._j < w . , f o r o therw ise Theorem 4 . 3 . 2 i m p l i e s t ha t R. i s so l ved t r i v i a l l y . Suppose as we l l t ha t h.., g iven by Theorem 4 . 3 . 2 , has been determined. For 63 s i m p l i c i t y o f n o t a t i o n w r i t e w.._j = w, w^ = w, and drop the s u b s c r i p t s on a l l q u a n t i t i e s t ha t occur i n ( R . ) . I < The f o l l o w i n g s imple lemma i s r e q u i r e d . Lemma 4 .3 .1 The f u n c t i o n h(w) i s concave, convex , or a f f i n e on [ w,w] acco rd ing as C < 0 , C > 0 , o r C = 0 , r e s p e c t i v e l y . P roo f We have h(w) = (Aw + B) / (Cw + D ) , and h(w) i s s t r i c t l y dec reas ing i n w s i n c e h( [w,w])c f ( E ) . D i f f e r e n t i a t i n g h y i e l d s 2 h'(w) = (AD - CB)/(Cw + D) < 0 , s i n c e h i s a s t r i c t l y dec reas ing f r a c t i o n a l f u n c t i o n . D i f f e r e n t i a t i n g a second t ime g ives h"(w) = ^2C(AD-BC)/(Cw + D ) 2 = -2Ch' (w) . (12 Now h i s a f r a c t i o n a l f u n c t i o n ; as s u c h , i t i s e i t h e r concave or convex on [w,w] . I f h i s convex, then h"(w) > 0 , imp l y i ng v i a (12) and the f a c t t ha t h'(w) < 0 , t ha t h i s convex i f C > 0. S i m i l a r l y h i s concave i f C < 0. I f C = 0 , then h i s a f f i n e . • Wi thout l o s s o f g e n e r a l i t y assume t ha t u i s o f the form u ( f x ( x ) , f 2 ( x ) ) - f x ( x ) + f 2 ( x ) . Then, f o r w < w < w, u(w,h(w)) = w + h(w) = w + Aw + B . Cw + D From Lemma 4 .3 .1 we know tha t h i s e i t h e r concave , convex , or a f f i n e on [w,w] . Thus, by obse rv ing t ha t the l e v e l s e t s o f w + h(w) 2 i n E c o n s i s t o f p a r a l l e l l i n e s w i th s lope - 1 , i t i s seen tha t w, the 64 s o l u t i o n o f (R^) i s e i t h e r w or w i f h i s convex or a f f i n e . I f h i s concave , then i t s d e r i v a t i v e i s d e c r e a s i n g , so tha t • A I w e {w,w} i f the i n t e r v a l [ h ' ( w ) , h'(w)] does not con ta in - 1 . A Otherwise the equat ion h'(w) = -1 can be so lved to ob ta in w. This leads to a quadra t i c equat ion having the roo ts w = (-D + 2 / B C - A D ) / C . By A A c o n c a v i t y o f h e x a c t l y one roo t u l i e s i n the i n t e r v a l [w,w] , and w s o l v e s ( R i ) . 2 F i n a l l y , s i n c e h'(w) = (AD-CB)/(Cw+D) , and s i n c e h'(w) i s dec reas ing by concav i t y o f h , the statement tha t [ h ' ( w ) , h'(w)] con ta ins 2 — 2 -1 i s equ i va len t to (Cw+D) < BC-AD < (Cw+D) . The above observa t ions enable us to s o l v e (R^) very e a s i l y . We A summarize the procedure f o r s o l v i n g (R . ) i n the next theorem. Theorem 4 . 3 . 3 Suppose tha t u(x) = f j ( x ) + fg (x ) and cons ide r ( R . ) . I f C < 0 and (Cw+D)2 < CB-AD < (Cw+D) 2 , then e x a c t l y one o f the numbers (-D + 2 / (BC-AD) /C l i e s i n the i n t e r v a l [w,w] and s o l v e s ( R ^ ) . Otherwise the s o l u t i o n to (R^) i s e i t h e r w or w, depending on which g ives a g rea te r va lue f o r w + (Aw + B)/ (Cw + D). 4 .4 Chebychev Problems When u has the form u ( f 1 ( x ) , f 2 ( x ) ) = min [ f j ( x ) , f 2 ( x ) ] and f j and f2 are l i n e a r f r a c t i o n a l f u n c t i o n s , Theorem 4 .3 .1 s t i l l a p p l i e s A and i t i s p o s s i b l e to so l ve subproblem (R^) w i thout e x p l i c i t computat ion 65 of h^, resulting in a more ef f ic ient form of the basic algorithm of Section 3. Further, connectedness of f(E) (from Theorem 4.2.1) enables one to determine the exact solution of (P). ' Assume without loss of generality that f(S) > 0 , and observe that the level sets of the function(E,T)+ min [e,x] are given by half rectangles with lower vertex on the l ine e=x . Now consider Figure 7 below. Figure 7 66 We see that i f f(E) c { ( f 1 5 f 2 ) | f 2 > fj}, then x maximizing f solves (P). S imi lar ly , i f f(E) c •[(f^,f2) | f 1 > f,,}, then x maximizing f 2 solves (P). If neither of the above cases hold then there are points of f(E) on either side of f^ = f 2 . By connectivity of f(E) i t then follows that the preimage of f^ solves (P), where fj is the intersection of f(E) and the l ine fj = f 2 . In such a case there exists an index i such that f 0 (x . ,) > f . ( x . .) 2V i - l ' V i - l ' and f 2 ( ) <f j (x. . ) . Thus, at optimality, f 2 (x) = f^x ) = w for some x 6 [ x ^ j , x..] . Equivalently, w solves h M = w = A w + B n { " } w Cw + D If C = 0 we have that w = B/(D-A) solves ( ) . If C f 0 a quadratic 1 2 equation resul ts , having the roots w and w below. Summarizing, the three possib i l i t ies are 1 _ (A-D) - / (D-A) 2 - 4BC w - , 2C w2 = (A-D) + / (D-A) 2 - 4BC . (12) 2C w3 = B/(D-A) . Thus we need only apply the parametric procedure of Section 2 until x^_j and x.j sat isfying 67 f 2 ( x i - l } > f l ( x i - l } (.13) f 2 ( x 1 ) < f 1 ( x i ) A. are found. The optimal value w of (P) can then be computed using (12). The optimal solution x is then calculated using Theorem 4.3.2. We now consider more general Chebychev problems of the form (T): max min [ f. ( x ) , . . . , f (x)] x e S 1 p where S is compact and convex, and f j , . . . , f are quasiconcave functions positive on S. Suppose a* is the optimal value for (T). Then one can construct sequence of quasiconcave problems T(a.) such that a. •+ a * 3 J by observing that a. < a* i f and only i f there exists x. e S satisfying f ^ x ) > a 1 < i < p. (14) Observe that the region defined by (14) is convex by quasiconcavity of the f . , and that we may conduct a bisecting search for a*. Connectivity gives additional information concerning a*. Let Sj(x) = fjU), s 2 (x) = min [ f2(x),... ,f (x)] , and s = ( S j . s ^ . Then min [ f j ( x ) . . , f (x)] = min ( s ^ x ) , s 2(x)] , and s 2 is quasiconcave by Lemma 3.4.2. By Theorem 3.4.1, E w (S,s) is connected. Using arguments similar to those that were employed for the case of two l inear f ract ionals , i t can then be inferred that one of the following three possib i l i t ies holds: 68 a * = max ( S j ( x ) | x G s}, a * = max { s 2 ( x ) [ x e S } , a * = S 2 ( x ) = S 2 ( x ) , where x e E (S ,s) c E ( S , f ) . Argu ing i n d u c t i v e l y , i t i s seen tha t f o r q u a s i -w w concave c r i t e r i a f j , ' f , e i t h e r a * maximizes some 'f. over S , or f . ( x ) = f (x) = a * , k ? r , f o r some x i n E . , ( S , f ) . The i n e q u a l i t i e s (14) suggest a procedure f o r maximiz ing the minimum o f p r a t i o s o f the form f ^ (x ) = d . (x ) /e . . ( x ) . In f a c t , (14) i s s a t i s f i e d i f and on l y i f t he re e x i s t s x e S such tha t d ^ x ) - cte . (x ) > 0 1 < i ' < p x e s E q u i v a l e n t l y , the problem T' ( a ) : max z s . t . d ^ x ) - a e ^ x ) > z 1 < i < p x e S has a non-negat ive s o l u t i o n . I f each d.. and e^ are concave and convex, r e s p e c t i v e l y , and S i s g iven by a s e t o f convex i n e q u a l i t i e s , t h e n T ' ( c t ) i s a concave program. For l i n e a r d ^ , e . . , and S , we ob ta i n the method o r i g i n a l l y suggested by Charnes and Cooper (1977) and mod i f ied by Armst rong, Charnes, Cooper and 69 Haksever (1980) f o r l i n e a r f r a c t i o n a l goal programming. Choo (1980) employs an equ i va len t procedure as an i n i t i a l s tep in an i n t e r a c t i v e m u l t i p l e o b j e c t i v e l i n e a r f r a c t i o n a l a l g o r i t h m . '< F i n a l l y , note tha t another equ i va len t f o rmu la t i on o f (.14) i s given by We have a < a* i f and on l y i f there e x i s t s x e S such tha t f ^ (x ) > This i s the fo rmu la t ion we used to so lve the two c r i t e r i o n Chebychev problem. 4 .5 Numerical Example and Computational Resu l t s In t h i s s e c t i o n we prov ide numerical I l l u s t r a t i o n s o f the a l go r i t hm fo r the sum o f two f r a c t i o n a l s and f o r the Chebychev problem. The r e s u l t s o f some computat ional experiments are a l s o p resented . The f o l l o w i n g example i s based on one appear ing in Choo (1980) . Example 4 .5 .1 The c r i t e r i o n f unc t i ons are max f , (x) x G S a 2 < 1 < p . fj(x) - 0.11 + l . l x 1 + x 2 - x 0.1 + x 3 3 0.1 + x + x 2 70 We wish to maximize f ^ x ) + f 2 (x ' ) and min [ f ^ x ) , f 2 ( .x)I sub jec t to the c o n s t r a i n t s 4 4 - l . l x 1 - xc + x < .11 x 1 < 0.9 x1 > 0 , x 2 > 0 , x 3 > 0. F i r s t , jf2 i s determined by s o l v i n g the l i n e a r programs tha t r e s u l t from app l y i ng the Charnes Cooper t r ans fo rma t i on to (3) and ( 4 ) . We ob ta i n ? 2 = 1 .32 , wQ = f l = 0 . 0 , and x Q = ( 0 , 0 , . 1 1 ) . Then the parametr ic procedure i s implemented us ing the PARAR0W op t ion o f MPSX, as shown in the t a b l e below. i x . l w. = i f 2 ( x . ) 0 ( 0 , 0 , . 1 1 ) 0.00 = f l 1.32 1 ( 0 , 0 , . 1 0 ) .10 1.20 2 ( 0 , 1 . 9 0 , 2 ) .10 1.20 3 ( 0 , 2 ,2 ) 1.10 1.143 4 ( 0 , 2 ,0 ) 21.10 = ? 1 0.00 I t i s o f i n t e r e s t to note tha t w^ = w 2 ( imp l y i ng tha t f ( . [ x ^ , x 2 J ) = f ( x but t ha t the segment o f f (E ) l y i n g above the i n t e r v a l [ . 1 , 1.1] i s ob ta ined as the image o f [ x 7 , x , ] , and cannot be obta ined as the image 71 of [ x ^ x3] . To maximize f 2 (x) + f 2 (x) we apply Theorem 4.3.3 to each interval * x i - l ' x i ^ ' a s s n o w n 1 n t n e n e x t table. i C. l Form of h. i Remarks 0 - - 1.32 1 0 1inear 1.30 2 - - 1.30 w l = w 2 = > 1 3 .21 convex 2.243 4 0 1inear 21.10 Thus x^ = (0,2,0) maximizes fj(x) + f 2 (x ) . To solve the Chebychev problem we use the test given by (13) to locate the interval in which the optimal solution l i e s , obtaining the following results. i f j tx.) < f 2 (x . ) ? 0 Yes 1 Yes 2 Yes 3 Yes 4 No 72 Thus the opt imal v a l u e , w, l i e s between w 3 = 1.10 and w^ = 21 .10 . The f unc t i on h4(.w) i s now computed from Theorem 4 . 3 . 2 , y i e l d i n g A 4 = - . 2 4 , B 4 = 5 .064, C 4 = 0 , D 4 = 4 . 2 . Then h 4 (w) i s l i n e a r and i s g iven by h 4(w) = (-.24w + 5 . 0 6 4 ) / 4 . 2 . (12) i s now used to c a l c u l a t e w, g i v i n g w = B 4 / ( D 4 - A 4 ) = 1 .141. To f i n d opt imal s o l u t i o n x , c a l c u l a t e a us ing Theorem 4 . 3 . 2 , y i e l d i n g a = .998. So f i n a l l y , x = . 998x 3 + . 002x 4 = (.0.2, 1 .996) . See F igure 8. F igure 8 73 We now consider some computational questions regarding our algorithm. It is clear that, for reasonably well behaved functions u, the majority of the computational effort is expended in solving the i n i t i a l fractional programs and implementing the parametric procedure. In the absence of heuristics to reduce the search in terva l , i t may be necessary to search the entire interval [W Q , W J^ (such is the case for f j + f^). Thus one is part icular ly interested in the behavior of the parametric LP procedure for solving Q(w). Murty ( 1 9 8 0 ) has recently shown that, in the worst case, the number of vertices that have to be v is i ted in order to solve a parametric objective l inear program can increase exponentially with the number of variables. One would expect similar worst case behavior for the row parametric l inear program Q(w), and i t is of interest to perform some experiments to determine the "average" behavior of Q(w). To this end, 6 0 randomly generated problems with 4 0 variables and 20 constraints were solved, together with 36 problems having 80 variables and 40 constraints. Several larger problems were also solved, the largest having 300 variables and 150 constraints. Following Bitran ( 1 9 7 9 ) we considered equality constrained problems with each entry t . . of the constraint matrix randomly chosen from the uniform distribution on ( 0 , 1 0 ] , with 20% negative entr ies. The n right hand sides v. were defined as v. = ( 2 t . . ) / 2 . To ensure 1 1 i=l 1 J posit ively of the denominators the co-eff ic ients in the denominators of both objective functions were chosen randomly in the interval ( 0 , 1] . The coefficients in the numerator of were chosen randomly in the 74 interval (0, 10] with 20% negative entr ies. The numerator co-ef f ic ients for fj were selected randomly in the interval (0, 10] , thus ensuring that f^x ) > 0 for a l l x e s. Such a choice provided the MPSX PARAROW procedure with the easy i n i t i a l parameter value w = 0. Each problem n also contained the bounding constraint 2 x. < 10n (which was never i=l 1 tight at optimality in any of the problems encountered). The larger problems contained either 100%, 20%,or 10% non-zero entries in the constraint matrix. MPSX was run under the PRIMAL option (I.e. fu l l pricing at each i terat ion) . All CPU times are given in minutes, and are for MPSX running with the aid of VSS 1.5 on the UBC Amdahl IV computer under MTS (VSS 1.5 enables IBM packages such as MPSX to run under MTS). Results for the 20 x 40 and 40 x 80 problems are shown in the tables below. The CPU times are not given for some individual phases because MPSX reports CPU time in hundredths of a minute, and i t is necessary to combine phases to get a meaningful time. 75 20 x 40 60 problems Number o f P i v o t s CPU t ime 100% d e n s i t y V a Min Max a Phase I 23.5 1.8 21 30 • -j Phase II 18.9 5.0 7 30 > .021 • .004 Parametr ic 22.5 7.4 9 46 - — Total 64.9 9.1 46 94 .021 .004 40 x 80 36 problems Number o f P i vo ts CPU t i me 100% d e n s i t y p a Min Max y a Phase I 48.1 3.1 43 55 1 1 Phase II > .036 } .004 42.4 8.5 20 61 J J Parametr ic 67.0 17.4 26 124 .051 .010 Tota l 161.5 19.6 127 229 .087 .011 10 problems o f s i z e 80 x 160 were r u n , 6 w i th 100% non-zero e n t r i e s , and 4 w i th 20% non-zero e n t r i e s . 76 80 x 160 6 problems Number o f P i vo t s CPU t ime 100% d e n s i t y V Min Max u Phase I 100.8 95 107 .08 Phase II 132.5 106 162 .16 Paramet r ic 200.7 148 263 .50 Total 434.0 399 524 .74 8U x 160 4 problems Number o f P i vo ts CPU t ime 20% d e n s i t y Min Max V Phase I 99.5 96 105 .05 Phase II 138.0 121 154 .11 Paramet r ic 166.5 141 218 .20 Tota l 404.0 370 449 .36 A 150 x 300 problem w i th 10% non-zero d e n s i t y requ i red 198,343, and 551 p i vo t s f o r the f i r s t , second, and parametr ic phases , r e s p e c t i v e l y . The cor respond ing CPU t imes were . 2 0 , . 6 1 , and 1.66 minutes . Phase I i t e r a t i o n s were the l e a s t e x p e n s i v e , and parametr ic i t e r a t i o n s the most expens ive . Mean CPU t imes per i t e r a t i o n f o r the 80 x 160 and 150 x 300 problems are shown below. 77 Mean Time per Iteration (xlO ) Size 80 x 160 80 x 160 150 x 300 Density 100% 20% 10% Phase I .8 .50 1.01 Phase II 1.21 .80 1.78 Parametric 2.49 1.20 3.01 78 BIBLIOGRAPHY Almogy, Y . , and Levin, 0.,A Class of Fractional Programming Problems, Operations Research, Vol. 19, pp. 57-67, (1971). Arisawa, S . , and Elmagharly, S . E . , Optimal Time-Cost Tradeoffs in GERT Networks, Management Science, Vol . 18, pp. 589-599, (1972). Armstrong, R., Charnes, A . , Cooper, W., Haksever, C . , Effective Solution of Non-Convex Multi-Objective Ratio Goals Problems, Research Report CCS 390, Center for Cybernetic Studies, University of Texas, Austin, Texas, (1980). Arrow, K., Branakin, E . , and Blackwell, D., Admissible Points of Convex Sets, in Contributions to the Theory of Games, Volume 2, H.W. Kuhn and A.W. Tucker, eds . , Princeton University Press, Princeton, New Jersey, (1953). Avriel , M., Generalized Concavity, to appear in Proceedings of the NATO Advanced Study Institute on Generalized Concavity in Optimization and Economics, University of Br i t ish Columbia, Vancouver, Canada, (1980). Berge, C. , Topological Spaces, MacMillan, New York, (1963). Bitran, G.R., Experiments with Linear Fractional Problems, Naval Research Logistics Quarterly, Vol. 26, pp. 689-694, (1977). Bitran, G.R., and Magnanti, T . L . , The Structure of Admissible Points with Respect to Cone Dominance, Journal of Optimization Theory and Applications, Vol. 29, No. 4, pp. 573-614, (1979). Bowman, V . J . , On the Relationship of the Tchebycheff Norm and the Efficient Frontier of Multiple-Criteria Objectives, in Multiple Criter ia Decision Making, S. Zionts and H. Thir iez , eds. , Lecture Notes in Economics and Mathematical Systems 130, Springer-Verlag, Ber l in , Heidelberg, New York, (1975). Charnes, A . , and Cooper, W.W., Programming with Linear Fractional Functionals, Naval Research Logistics Quarterly, Vol. 9, pp. 181-186, (1962). Charnes, A . , and Cooper, W.W., Goal Programming and Multiobjective Optimi-zations, European Journal of Operations Research, Vol. 1, pp. 39-54, (1977). Charnes, A . , Cooper, C.W., and Rhodes, E . , Measuring the Efficiency of Decision Making Units, European Journal of Operational Research, Vol. 3, pp. 429-444, (1978). Choo, E . , Multiple Criterion Fractional Programming, Faculty of Commerce and Business Administration, University of Br i t ish Columbia, Vancouver, Canada, Ph.D. Thesis, (1980). 79 Craven, B . D . , Vector Valued Optimization, t o appear i n Proceedings o f NATO Advanced Study I n s t i t u t e on Genera l i zed Concav i t y i n Op t im iza t ion and Economics, U n i v e r s i t y o f B r i t i s h Co lumbia , Vancouver , Canada, (1980) . D a n t z i g , C . , Folkman, J . , and S h a p i r o , N . , On the-Continuity of the Minimum Set of a Continuous Function, Journa l o f Mathematical A n a l y s i s and A p p l i c a t i o n s , V o l . 1 7 , pp. 519-548, (1967) . Debreu, G. , Representation of a Preference Ordering by a Numerical Function, Dec i s i on P r o c e s s e s , T h r a l l , Coombs, and Davis e d s . , John W i l e y and Sons , New Yo rk , New York , (1954) . DiGugl iemo, F . , Nonconvex Duality in Multiobjective Optimization, Mathematics o f Operat ions Research , V o l . 2 , pp. 285-291 , (1977) . Evans, J . P . , and G o u l d , F . J . , Stability in Nonlinear Programming, Operat ions Research , V o l . 1 8 , pp. 107-118, (1970) . G e o f f r i o n , A . M . , Solving Bicriterion Mathematical Programs, Operat ions Research , V o l . 1 5 , pp. 3 9 - 5 4 , (1967) . G e o f f r i o n , A . M . , Proper Efficiency and the Theory of Vector Maximization, Journa l o f Mathemat ical A n a l y s i s and A p p l i c a t i o n s , V o l . 2 2 , pp. 618-630 , (1968) . G e o f f r i o n , A . M . , Dyer , J . S . , and F e i n b e r g , A. An Interactive Approach for Multi-Criterion Optimization with an Application to the Operation of an Academic Department, Management S c i e n c e , V o l . 19 , pp. 357-368 , (1972) . G i l m o r e , P . C , and Gomory, R . E . , A Linear Programming Approach to the Cutting Stock Problem, Part II, Operat ions Research , V o l . 1 1 , pp. 863-888, (1963) . H i l d e n b r a n d , W. , and K i rman, A . , Introduction to Equilibrium Analysis, American E l s e v i e r , New York , (1976) . H i r c h e , J . , and Tan, K . H . , Uber eine Klasse nichtkonvexer Optvmierungs probleme, Zeitschrift fur angewandte Mathematik und Mechanik, V o l . 5 7 , pp. 247-253 , (1977) . Hogan, W. , Point to Set Maps in Mathematical Programming, SIAM Review, V o l . 1 5 , pp. 591-603, (1973) . Huard , P . , The Continuities of the Point to Set Maps, Definitions and Equivalences, Mathematical Programming Study 1 0 , pp. 8 - 1 2 , (1979) . Kanchan, P . , Maximizing the Sum of a Linear and a Linear Fractional Function, ( t e n t a t i v e t i t l e ) , t o appear i n Cah iers du Centre d*Etudes de Recherche O p e r a t i o n n e l l e (1981) . 80 Keeney, R . , and R a i f f a , H . , Decisions with Multiple Objectives: Preferences and Value Trade-Offs, John Wi ley and Sons, New York , (1976) . < A K o r n b l u t h , J . S . H . , A Survey of Goal Programming, Omega, V o l . 1 , pp. 193-205, (1973) . Kuhn, H.W. and Tucker , A .W. , Nonlinear Programming, i n Proceedings o f the Second Be rke ley Symposium on Mathematical S t a t i s t i c s and P r o b a b i l i t y , U n i v e r s i t y o f C a l i f o r n i a P r e s s , B e r k e l e y , C a l i f . , (1951) . MacCrimmon, K . R . , An Overview of Multiple Objective Decision Making, i n M u l t i p l e C r i t e r i a Dec is ion Mak ing, J . Cochrane and M. Ze leny , e d s . , U n i v e r s i t y o f South C a r o l i n a P r e s s , Columbus, S . C . , (1973) . Meyer, R. , The Validity of a Family of Optimization Methods, SIAM Journal o f C o n t r o l , V o l . 8 , pp. 4 1 - 5 4 , (1970) . M j e l d e , K . M . , Allocation of Resources According to a Fractional Objective, European Journa l o f Operat iona l Research , V o l . 2 , pp. 116-124, (1978). Mur ty , K . G . , Computational Complexity of Parametric Linear Programming, Mathematical Programming, V o l . 19 , pp. 213-219, (1980). Naccache, P . H . , Connectedness of the Set of Non-Dominated Outcomes in Multicriteria Optimization, Journal o f Op t im iza t ion Theory and A p p l i c a t i o n s , V o l . 2 5 , No. 3 , pp. 459-467, (1978) . Pas te rnak , H . , and P a s s y , U . , Bicriterion Mathematical Programs with Boolean Variables, i n M u l t i p l e C r i t e r i a Dec is ion Mak ing , U n i v e r s i t y o f South C a r o l i n a P r e s s , J . Cochrane and M. Ze leny , e d s . , Columbus, S . C . , (1973) . R i t t e r , K . , A Parametric Method for Solving Certain Nonconcave Maximization Problems, Journal o f Computer and Systems S c i e n c e s , V o l . 1, pp. 44 -54 , (1967) . S c h a i b l e , S . , On the Sum of a Linear and a Linear Fractional Function, Naval Research L o g i s t i c s Q u a r t e r l y , Vo. 24 , pp. 691-693, (1977) . S t a r r , M . , and Ze leny , M . , MCDM-State and Future of the Arts, i n TIMS Stud ies i n Management S c i e n c e , pp. 5 -29 , (1977) . Tan ino , T. and Sawarag i , Y . , Stability of Nondominated Solutions in Multicriteria Decision-Making, Journal o f Op t im iza t ion Theory and A p p l i c a t i o n s , V o l . 3 0 , pp. 229-253, (1980) . T a y l o r , A . , General Theory of Functions and Integration, B l a i s d e l l , New York , (1965) . 81 T e t e r e v , A . G . , On a Generalisation of Linear and Pieaewise Linear Programming ( R u s s . ) , Ekons. i . Mat. M e t . , V o l . 5 , pp. 440-447 (1969) ; E n g l i s h T r a n s l a t i o n i n Matekon, pp. 246-259, (1970) . Yu, P . L . , Cone Convexity, Cone Extreme Points, and Nondominaped Solutions in Decision Problems with Multiobjectives, Journal o f Opt im iza t i on Theory and A p p l i c a t i o n s , V o l . 1 4 , pp. 319-377, (1974) . Yu, P . L . and Ze leny , M . , The Set of All Nondominated Solutions in Linear Cases' and a Multicriteria Simplex Method, Journal o f Mathemat ical A n a l y s i s and A p p l i c a t i o n s , V o l . 4 9 , pp. 430-468, (1975) . Zang, I., Conoavifiability of (? Functions: A Unified Approach, to appear i n Proceedings o f NATO Advanced Study I n s t i t u t e on Genera l i zed Concav i ty i n Op t im iza t i on and Economics, U n i v e r s i t y o f B r i t i s h Columbia, Vancouver, Canada, (1980) .
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Topics in multiple criteria optimization
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Topics in multiple criteria optimization Warburton, Arthur Raymond 1981
pdf
Page Metadata
Item Metadata
Title | Topics in multiple criteria optimization |
Creator |
Warburton, Arthur Raymond |
Date Issued | 1981 |
Description | Several aspects of multiple criteria optimization are investigated. First, sufficient conditions are obtained for the upper semi-continuity of the set of maximal alternatives for a nonscalar parametric optimization problem in which the set of alternatives, the objective functions, and a partial order defined on the set of outcomes may all vary. One of the conditions involves continuity of a function f on a product space and the relationship between various continuity conditions on f that have appeared on the literature are investigated. Second, we study the set of Pareto optimal and weakly Pareto optimal solutions to a vector maximization problem defined by continuous vector valued quasiconcave criterion functions and a closed convex set of decisions, S. If S is compact, it is shown that the set of weakly Pareto optimal decisions is connected, but that the set of Pareto optimal decisions is not necessarily connected. However, the set of Pareto optima is shown to be connected for some important sub-classes of quasiconcave criteria. Under reasonable conditions the compactness assumption on S may be relaxed and connectedness maintained. Connectivity may fail if preferences are given by cones other than the Pareto cone. Finally, bicriterion mathematical programs of the form P: max {u(f₁(x), f₂(x))|xεS} are considered, where S is a bounded polyhedral set, f₁ and f₂ are linear fractional functions, and u is a real valued function, non-decreasing in each argument. It is shown that the solution of P may be essentially reduced to a one parameter linear program. Simple, computationally effective, finite algorithms are obtained for the cases where u is a weighted sum of f₁ and f₂, and where u is the Chebychev function min [f₁(x), f₂(x)]. It is also shown how a simple sequence of quasiconcave problems may be constructed whose solutions converge to the solution of max {min[f₁(x),...,f[sub p](x)]|xεS) if f₁,…f[sub p] are quasiconcave and S is convex. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-03-29 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0095251 |
URI | http://hdl.handle.net/2429/22874 |
Degree |
Doctor of Philosophy - PhD |
Program |
Business Administration |
Affiliation |
Business, Sauder School of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1981_A1 W37.pdf [ 3.56MB ]
- Metadata
- JSON: 831-1.0095251.json
- JSON-LD: 831-1.0095251-ld.json
- RDF/XML (Pretty): 831-1.0095251-rdf.xml
- RDF/JSON: 831-1.0095251-rdf.json
- Turtle: 831-1.0095251-turtle.txt
- N-Triples: 831-1.0095251-rdf-ntriples.txt
- Original Record: 831-1.0095251-source.json
- Full Text
- 831-1.0095251-fulltext.txt
- Citation
- 831-1.0095251.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0095251/manifest