MULTICRITERIA LINEAR FRACTIONAL PROGRAMMING by ENG-UNG JCHOO B . S c , Nanyang U n i v e r s i t y , S i n g a p o r e , 1967 Ph.D., The U n i v e r s i t y o f B r i t i s h C olumbia, 1971 M . S c , The U n i v e r s i t y o f B r i t i s h C olumbia, 1976 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY i n THE FACULTY OF GRADUATE STUDIES ( F a c u l t y o f Commerce and B u s i n e s s A d m i n i s t r a t i o n ) We a c c e p t r t h i s t h e s i s as co n f o r m i n g t o the r e q u i r e d s t a n d a r d THE UNIVERSITY OF BRITISH COLUMBIA Oct o b e r , 1980 ^) Eng-Ung Choo, 1981 In presenting th is thes is in p a r t i a l fu l f i lment of the requirements for an advanced degree at the Un ivers i ty of B r i t i s h Columbia, I agree that the L ibrary shal l make it f ree ly ava i l ab le for reference and study. I fur ther agree that permission for extensive copying of th is thes is for scho la r ly purposes may be granted by the Head of my Department or by h is representat ives . It is understood that copying or pub l ica t ion of th is thes is for f inanc ia l gain sha l l not be allowed without my wri t ten permission. Department of The Univers i ty of B r i t i s h Columbia 2075 W e s b r o o k P l a c e V a n c o u v e r , C a n a d a V6T 1W5 D. R. Atkins ABSTRACT The o b j e c t o f t h i s t h e s i s i s t o study the m u l t i -c r i t e r i a l i n e a r f r a c t i o n a l programming problems (MLFP). The c h a r a c t e r i z a t i o n s o f e f f i c i e n c y , weak e f f i c i e n c y and p r o p e r e f f i c i e n c y a r e d e r i v e d . I n t h e b i c r i t e r i a c a s e , the s e t E of a l l e f f i c i e n t s o l u t i o n s o f (MLFP) i s p a t h - c o n n e c t e d by a f i n i t e number o f l i n e segments and the e f f i c i e n t f r o n t i e r F ( E ) can be e v a l u a t e d by u s i n g the row p a r a m e t r i c t e c h n i q u e i n l i n e a r programming. The weakly e f f i c i e n t ( r e s p e c t i v e l y , p r o p e r l y e f f i c i e n t ) s o l u t i o n s can be g e n e r a t e d by s o l v i n g the g e n e r a l i z e d T c h e b y c h e f f norm problems (T3) ( r e s p e c t i v e l y , (T3a)) w i t h d i f f e r e n t parameters 6 and a. The s e t E W o f a l l weakly e f f i c i e n t s o l u t i o n s o f (MLFP) i s compact and p a t h -c onnected by f i n i t e l y many l i n e segments. A d u a l problem i s f o r m u l a t e d which i s a n a t u r a l e x t e n s i o n o f the u s u a l d u a l i n l i n e a r programming, the Wolfe d u a l i n n o n l i n e a r programming and the Isermann d u a l i n m u l t i p l e o b j e c t i v e l i n e a r programming. D u a l i t y r e s u l t s are e s t a b l i s h e d under the assumption t h a t the c r i t e r i a are concave f u n c t i o n s . The m a t r i x o f the d u a l v a r i a b l e s o f (MLFP) can be e v a l u a t e d by s o l v i n g L l i n e a r programs. A h e u r i s t i c arrow s e a r c h a l g o r i t h m i s d eveloped f o r s o l v i n g g e n e r a l m u l t i c r i t e r i a programming problems i n t e r a c t i v e l y . The d e c i s i o n maker merely s e l e c t s h i s most p r e f e r r e d one amongst-the p r e s e n t e d a l t e r n a t i v e s . S o l u t i o n s g e n e r a t e d are e v e n l y d i s t r i b u t e d over the d e s i r e d neighbourhood o f t h e weakly e f f i c i e n t f r o n t i e r . The a l g o r i t h m i s convergent l n the b i c r i t e r i a case, w i t h a p p r o p r i a t e c o n v e x i t y c o n d i t i o n s . When a p p l i e d t o s o l v e (MLFP), the arrow s e a r c h a l g o r i t h m uses o n l y the l i n e a r programming t e c h n i q u e s . i v TABLE OF CONTENTS Page INTRODUCTION 1 CHAPTER 0 PRELIMINARIES 7 CHAPTER 1 EFFICIENCY AND WEAK EFFICIENCY 13 1. C h a r a c t e r i z a t i o n o f E f f i c i e n c y . 14 2. C h a r a c t e r i z a t i o n o f Weak E f f i c i e n c y ' 19 3. Subproblems o f (MLFP) 24 4 . Summary 30 CHAPTER 2 BICRITERIA (MLFP) 32 1. C h a r a c t e r i z a t i o n o f E f f i c i e n c y . 32 2. E v a l u a t i o n o f E f f i c i e n t F r o n t i e r 36 3. A l g o r i t h m f o r E v a l u a t i n g E f f i c i e n t F r o n t i e r . . 43 4. D i s c u s s i o n ., 49 CHAPTER 3 GEOMETRIC PROPERTIES OF E AND E W 51 1. D i s c o n n e c t e d Examples 51 2. Connectedness o f E and E^ 53 3. D i s c u s s i o n 57 CHAPTER 4 PROPER EFFICIENCY 58 1. P r o p e r E f f i c i e n c y 58 2. E x t e n s i o n o f G e n e r a l i z e d T c h e b y c h e f f Norm 60 3. C h a r a c t e r i z a t i o n o f P r o p e r E f f i c i e n c y .. 65 V 4. Isoquants of ||u*-G(x)||J 69 p * 5 - Proper E f f i c i e n c y and Cone Domination ... 7 0 6 . Summary 7 2 CHAPTER 5 DUALITY 7 4 1 . Duality i n M u l t i c r i t e r i a Programming ... 7 4 2 . Quasiconvex Duality 7 6 3 . Dual Formulation 7 7 H. Duality 7 9 5 . Special Cases 8 0 6.. Duality of (MLFP) 8/4 7 - Summary 8 5 CHAPTER 6 HEURISTIC ALGORITHM 87 ' 1 . Arrow Search Algorithm 88 2 . Arrow Search Algorithm for (MLFP) .. 9 ^ 3 . Summary 1 0 0 CHAPTER 7 CONCLUSION '. 1 0 1 I. Conclusion 1 0 1 2 . Conjectures and Further Research ...... 1 0 2 BIBLIOGRAPHY. 1 0 6 APPENDIX ... 1 1 3 ACKNOWLEDGEMENTS I am g r e a t l y i n d e b t e d t o my t h e s i s s u p e r v i s o r P r o f . D.R. A t k i n s f o r h i s v a l u a b l e and generous a s s i s t a n c e d u r i n g the p r e p a r a t i o n o f t h i s t h e s i s . I l i k e t o thank P r o f . S. B r u m e l l e f o r the h e l p f u l d i s c u s s i o n s and i n s t r u c t i v e comments. I w i s h t o thank my w i f e Peggy who p e r s e v e r e d w i t h me and encouraged me t h r o u g h o u t . A l s o s p e c i a l thanks t o my daughter L o r r a i n e f o r h e r p a t i e n c e . The f i n a n c i a l s u p port from the N a t i o n a l Research C o u n c i l o f Canada i s g r a t e f u l l y acknowledged. 1 INTRODUCTION ———_____ ^ This t h e s i s aims to add to the understanding of the p r o p e r t i e s , s o l u t i o n s and s o l u t i o n procedures of a p a r t i c u l a r o p t i m i z a t i o n problem. This problem i s p a r t i c u l a r i n two e s s e n t i a l ways. F i r s t l y , i t i s a m u l t i c r i t e r i a problem, that i s , the ev a l u a t i o n of any f e a s i b l e s o l u t i o n i s based on a vector of c r i t e r i a . The second p a r t i c u l a r f e a -ture about the o p t i m i z a t i o n problem studied here i s that the c r i t e r i a themselves are r a t i o s of a f f i n e f u nctions or 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 , as they are u s u a l l y termed. Without e a r l i e r exposure to the f i e l d , t h i s might appear as a rat h e r strange choice of problem about which to be concerned. As s h a l l be demonstrated below, the motivation behind the concern f o r t h i s problem comes from two sources, one t h e o r e t i c a l and one very p r a c t i c a l . On the t h e o r e t i c a l s i d e , t h i s problem i s j u s t a n a t u r a l extension of research already completed by many authors- i n a wide range of a r t i c l e s i n the p r o f e s s i o n a l j o u r n a l s ' [25,84 ,90]. M u l t i c r i t e r i a l i n e a r programming problems had been e x t e n s i v e l y studied [7,8, 33,35,37,50,72,81,82,87,89] and s i n g l e 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 problems had also a t t r a c t e d considerable research and i n t e r e s t [6,13,18,21,23,30,46,58,66,78,80]. However, there had been very l i t t l e research done on the m u l t i c r i t e r i a l i n e a r f r a c t i o n a l programming problems (MLFP) other than the goal programming approach proposed i n [22,56,59]- I t i s thus 2 n a t u r a l f o r (MLFP) t o be s t u d i e d n e x t . But perhaps of much more d i r e c t r e l e v a n c e and importance i s the p r a c t i c a l m o t i v a t i o n . 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 are w i d e l y used as performance measures i n many management s i t u a t i o n s [22, 46,78]. I n m a n u f a c t u r i n g , p r o d u c t i o n p l a n n i n g and s c h e d u l i n g are judged by p r o d u c t i o n r a t e s , i n v e n t o r y - s a l e s r a t i o s and c a p a c i t y u t i l i z a t i o n r a t i o s [48]. The academic q u a l i t y , f a i l u r e r a t e s and s t u d e n t - t e a c h e r r a t i o s are e s s e n t i a l i n e d u c a t i o n a l p l a n n i n g and a d m i n i s t r a t i o n [41,62,691. . In p a r t i c u l a r , l i q u i d i t y , e a r n i n g per s h a r e , r e t u r n on c a p i t a l employed, e a r n i n g c o v e r , growth r a t e , d i v i d e n d per share and d i v i d e n d c o v e r a r e w i d e l y used i n the a n a l y s i s of f i n a n c i a l e n t e r p r i z e s and u n d e r t a k i n g s [ 3 j l 9 1 . I t was i n the l a t t e r c o n t e x t t h a t the problem f i r s t a r o s e . A study of the use o f m u l t i p l e c r i t e r i a programming methods f o r f i n a n c i a l p l a n -n i n g i n a company had been r e p o r t e d [31. The a u t h o r s a d m i t t e d t h e r a t h e r ad hoc n a t u r e o f t h e method used and suggested t h a t more r e s e a r c h would have t o be done on m u l t i c r i t e r i a l i n e a r f r a c t i o n a l programming. I t t h e r e f o r e seemed r a t h e r i m p o r t a n t t h a t more r e s e a r c h on t h i s problem be done f o r i m p r o v i n g v a r i o u s p r a c t i c a l m o d e l l i n g i n v o l v i n g r a t e s and r a t i o s . The e x t e n s i o n from m u l t i c r i t e r i a l i n e a r t o m u l t i c r i t e r i a l i n e a r f r a c t i o n a l t u r n e d out t o be f a r from a t r i v i a l e x t e n s i o n . In f a c t , almost e v e r y p r o p e r t y o f any v a l u e p o s s e s s e d by the m u l t i c r i t e r i a l i n e a r programming problems seemed t o have d i s a p p e a r e d . I t appeared t h a t a whole new s t a r t needed t o be 3 undertaken i n t h i s area and hence t h i s d i s s e r t a t i o n . Due to the r e a l i z a t i o n that many complex d e c i s i o n making problems i n v o l v e c o n f l i c t i n g m u l t i p l e c r i t e r i a [5,20, 29,34,47,52,55,71,77], m u l t i c r i t e r i a o p t i m i z a t i o n has been the focus of i n c r e a s i n g a t t e n t i o n . I t i s obviously a more r e a l i s t i c approach to modelling the complex s i t u a t i o n s . Also • i t provides a wider range of e f f i c i e n t a l t e r n a t i v e s and promotes a more a c t i v e r o l e f o r the d e c i s i o n makers i n the d e c i s i o n making processes. The fundamental d i f f i c u l t y i s the determination of the d e c i s i o n maker's preference ordering over the set of a l l f e a s i b l e a l t e r n a t i v e s . I t i s assumed that there i s a f u n c t i o n U, known as the d e c i s i o n maker's u t i l i t y f u n c t i o n , whose value d i c t a t e s the preference ordering Except f o r c o n f l i c t s among the c r i t e r i a , the d e c i s i o n maker wishes to maximize every s i n g l e c r i t e r i o n . I f the u t i l i t y f u n c t i o n U i s known e x p l i c i t l y , then the c r i t e r i a f ^ , . . . , f ^ can be u n i f i e d 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 and we end up w i t h the ordinary mathematical programming problem. Many techniques f o r determining U e x p l i c i t l y have been proposed [16,36,45,53,54,65,70]. This approach appeared to have had l i m i t e d acceptance, p a r t l y due perhaps to the f a c t that most d e c i s i o n makers found i t hard to express t h e i r I m p l i c i t l y . f e l t preferences i n mathematical forms. Other techniques do not r e q u i r e the e x p l i c i t knowledge of U. Instead, the d e c i s i o n makers are asked to guide and i n t e r a c t with the s o l u t i o n procedures based on t h e i r i m p l i c i t preference o r d e r i n 4 Here the notion of e f f i c i e n c y played an important r o l e . There were various methods f o r e v a l u a t i n g a l l e f f i c i e n t and extreme e f f i c i e n t s o l u t i o n s f o r m u l t i c r i t e r i a l i n e a r program-ming problems [ 3 3 , 3 5 , 3 7 . 5 0 , 7 2 , 8 1 , 8 7 , 8 9 1 . To obtain a 'best' compromise s o l u t i o n [ 8 8 ] , many i n t e r a c t i v e algorithms had been developed f o r the l i n e a r case [7,8,82,871 and al s o f o r the n o n l i n e a r convex case [31,32,41,67,74,91,931- Also numerous p r a c t i c a l a p p l i c a t i o n s of the m u l t i c r i t e r i a program-ming techniques had been reported [3,26,41,43,61,62,63,69,75, 83,92]. A comprehensive recent review of the m u l t i c r i t e r i a l i n e a r programming method and a p p l i c a t i o n s was given i n [ 2 7 1 . A p p l i c a t i o n s of (MLFP) had been reported i n f i n a n c i a l planning [3] and u n i v e r s i t y planning [ 4 1 , 6 2 , 6 9 1 . This d i s s e r t a t i o n i s concerned w i t h the study of (MLFP). The mathematical p r o p e r t i e s of the 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 are given i n Chapter 0. In Chapter 1, the e f f i c i e n t s o l u t i o n s of (MLFP) are c h a r a c t e r i z e d by the Kuhn-Tucker c o n d i t i o n s and the weakly e f f i c i e n t s o l u t i o n s are c h a r a c t e r i z e d by the gen e r a l i z e d Tchebycheff norm. We studie d the r e l a t i o n s between the s o l u t i o n s of (MLFP) and those of the subproblems obtained from (MLFP) by d e l e t i n g some c r i t e r i a and/or imposing some minimal l e v e l s to c e r t a i n c r i t e r i a . In Chapter 2, a thorough a n a l y s i s of (MLFP) with only two c r i t e r i a i s presented. The set E of a l l e f f i c i e n t s o l u t i o n s i s path-connected by a f i n i t e number of l i n e segments 5 and the e f f i c i e n t f r o n t i e r can be e v a l u a t e d by u s i n g the row p a r a m e t r i c techniques i n l i n e a r programming. Geometric p r o p e r t i e s o f the s o l u t i o n s e t s are i n v e s t i g a t e d i n Chapter 3. The s e t E W o f a l l weakly e f f i c i e n t s o l u t i o n s o f (MLFP) i s compact and p a t h - c o n n e c t e d by f i n i t e l y many l i n e segments. Chapter 4 i s devoted t o the p r o p e r e f f i c i e n c y which i s c h a r a c t e r i z e d by an extended form o f the g e n e r a l i z e d _ T c h e b y c h e f f norm. T h i s p r o v i d e s a p a r a m e t r i z a t i o n scheme t o g e n e r a t e t h e p r o p e r l y e f f i c i e n t s o l u t i o n s of nonconvex m u l t i c r i t e r i a programming problems. P r o p e r e f f i c i e n c y i s e q u i v a l e n t t o t h e e f f i c i e n c y w i t h r e s p e c t t o c e r t a i n s i m p l e convex cones. I n Chapter 5, a s p e c i a l d u a l i t y based on the g e n e r a l i z e d T c h e b y c h e f f norm problem ( T 8 ) and the d u a l i t y f o r q u a s i c o n v e x programming by Luenberger i s d i s c u s s e d . We a l s o i n t r o d u c e d a d u a l f o r m u l a t i o n which i s a n a t u r a l e x t e n s i o n o f the Wolfe d u a l and the Isermann d u a l . The m a t r i x o f d u a l v a r i a b l e s o f (MLFP) can be e v a l u a t e d by s o l v i n g L l i n e a r programs. I n Chapter 6, we i n t r o d u c e d the h e u r i s t i c arrow s e a r c h a l g o r i t h m f o r s o l v i n g g e n e r a l m u l t i c r i t e r i a programming problems. I t i s an i n t e r a c t i v e a l g o r i t h m which r e q u i r e s the d e c i s i o n maker merely t o choose h i s most p r e f e r r e d one amongst the p r e s e n t e d a l t e r n a t i v e s . The a l t e r n a t i v e s g e n e r a t e d by the a l g o r i t h m - a r e e v e n l y d i s t r i b u t e d over the d e s i r e d n e i g h -bourhood o f the weakly e f f i c i e n t f r o n t i e r . The arrow s e a r c h 6 a l g o r i t h m i s convergent i n the b i c r i t e r i a case under some a p p r o p r i a t e c o n v e x i t y c o n d i t i o n s . When a p p l i e d t o s o l v e (MLFP), the a l g o r i t h m uses o n l y the l i n e a r programming t e c h n i q u e s . I n Chapter 7, a. b r i e f summary i s g i v e n . Some u n s o l v e d c o n j e c t u r e s and t o p i c s f o r f u r t h e r r e s e a r c h are d i s c u s s e d . 7 CHAPTER 0 ____________ 9 Throughout t h i s t h e s i s we make extensive use of se v e r a l simple p r o p e r t i e s of 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 . For convenience and p a r t i c u l a r l y because these f u n c t i o n s are not widely used and handled, t h e i r p r o p e r t i e s are c o l l e c t e d t o -gether i n t h i s chapter f o r reference. A l l the proofs can be found i n the appendix. . Let f denote a l i n e a r f r a c t i o n a l f u n c t i o n defined on a subset S of Rn. Then f can be defined e x p l i c i t l y by f ( x j = (c Tx+r)/(d Tx+t) , V x e S where c,d are n-vectors and r , t are r e a l numbers. I t i s assumed that S i s a compact convex set and the denominator T d x+t > 0 f o r every x i n S. I t i s obvious that f has continous p a r t i a l d e r i v a t i v e s of a r b i t r a r y order and i t s gradient vector i s Vf(x) = ( l / ( d T x + t ) ) c - ( ( c T x + r ) / ( d T x + t ) 2 ) d ( 1 ) Being the r a t i o of two a f f i n e forms, f has many d e s i r a b l e p r o p e r t i e s . Theorem 0 . 1 . For any x,y e S, we have (a) f ( x ) < f ( y ) i f and only i f ( y - x ) T V f ( x ) > 0 (b) f ( x ) < f ( y ) i f and only i f ( y - x ) T V f ( x ) > 0 . C o r o l l a r y 0 . 2 . I f Vf(x) = 0 f o r some x i n S, then f.reduces to a constant f u n c t i o n on S. 8 C o r o l l a r y 0.3- f i s p s e u d o l l n e a r ( i . e . pseudoconvex and a pseudoconcave). A l o n g any l i n e segment, f i s monotonic and i s e i t h e r convex or concave. Theorem 0.4. L e t x,y e S and g be the r e s t r i c t i o n o f f on the l i n e segment [x;y] j o i n i n g x and y. Then g i s monotonic and i s e i t h e r convex or concave. The f o l l o w i n g example shows t h a t the b e h a v i o u r o f f v a r i e s from one l i n e segment t o a n o t h e r . Example 0.5. L e t S = {x e R :0 ^ 5 , 0 f 5) and f ( x ) = ( x 1 + 4 x 2 ) / ( x 1 + x 2 + l ) , V x e S. Then D 2 2 f ( x ) = ( 6 x 2 - 2 ) / ( x 1 + x 2 + l ) 2 . Thus f i s concave a l o n g the l i n e segment x 2 = 0 and convex a l o n g the l i n e segment x 2 = 1. I n p a r t i c u l a r , f i s n e i t h e r convex nor concave over S. 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 have n i c e p r o p e r t i e s such as m o n o t o n i c i t y a l o n g l i n e segments,, p s e u d o c o n v e x i t y and p s e u d o c o n c a v i t y . However, t h e sum o f two 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 may be non-monotonic, non-quasiconvex and non-quasiconcave. T h i s i s i l l u s t r a t e d by the next example, 9 Example 0.6. L e t S = {x e R 2:-0.45 < x 1' < 1 and -0.45 < x g ^ 1} and g( x ) = ( - x 1 + x 2 ) / ( x 1 + x 2 + l ) + ( 2 x 1 - 2 x 2 ) / ( x 1 + x 2 + 2 ) , V x e A l o n g the l i n e segment = 0 i n S, the f i r s t p a r t i a l 2 2 d e r i v a t i v e D-^gCx) = - l / ( x . ^ + l ) + 4/(x-L+2) changes s i g n at x = ( 0 , 0 ) . Thus g i s not monotonic a l o n g t h i s l i n e segment. We have g ( ( - l / 3 , 0 ) ) = g ( ( 2 / 3 , 0 ) ) = 0.1 a n d ' g ( 0 . 5 ( - l / 3 , 0 ) .+ 0.5(2/3,0)) = 1/91 < 0.1. Thus g i s not q u a s i c o n c a v e . A l s o we have g ( ( 0 , - l / 3 ) ) = g ( ( 0 , 2 / 3 ) ) = -0.1 and g(0.5(0,-1/3) + 0.5(0,2/3)) = -1/91 > -0.1. Thus g i s not q u a s i c o n v e x . We s h a l l assume t h a t f i s not a c o n s t a n t f u n c t i o n on S. I t f o l l o w s from (1) t h a t V f ( x ) has a f i x e d d i r e c t i o n independent o f x when e i t h e r c = 0, d ^ 0 or c ^ 0 , d = 0 . When c ? 0 and . d j- 0, the d i r e c t i o n o f V f ( x ) v a r i e s w i t h n x. L e t u be a g i v e n non-zero v e c t o r i n R . Then f i s monotonic i n the d i r e c t i o n u a t a l l x i n S. The g r a d i e n t v e c t o r o f f changes i n a s p e c i f i c manner such t h a t e i t h e r ( i ) f i s m o n o t o n i c a l l y i n c r e a s i n g i n d i r e c t i o n u at a l l x i n S, or ( i i ) f i s m o n o t o n i c a l l y d e c r e a s i n g i n the d i r e c t i o n u at. a l l x i n S, or ( i i i ) t h e r e e x i s t s a h a l f - s p a c e H such t h a t f i s m o n o t o n i c a l l y i n c r e a s i n g i n the d i r e c t i o n u at a l l x i n S D H and f i s m o n o t o n i c a l l y d e c r e a s i n g i n the d i r e c t i o n u a t a l l x i n S - H. T h i s i s summarized i n .the next theorem. 10 Theorem 0.7- L e t u e R n and u ^ 0. Then f i s monotonica.lly i n c r e a s i n g i n the d i r e c t i o n u a t a l l x i n S O H and mono-t o n i c a l l y d e c r e a s i n g i n the d i r e c t i o n u at a l l x i n S - H where H = {x e R n : c T u ( d T x + t ) < d T u ( c T x + r ) } . 2 The next example i l l u s t r a t e s Theorem 0.7 i n R . Example 0.8. L e t S = {x e R 2 : x 1 , x 2 e [0;4]} , u T = (1,-2) and f ( x ) = . (5x 1+3x 2-15)/(-x 1-x 2+5). Then H = {x e R 2 : 2 x 1 + x 2 ~ 5 < 0}. We have u T V f ( x ) > 0 , V x e S O'H and u T V f ( y ) < 0. , V y e S - H as shown i n F i g u r e 1. F i g u r e 1 11 D e f i n i t i o n 0.9. A subset Q o f R u i s s a i d t o be a k - d i m e n s i o n a l m a n i f o l d i f Q - x i s a k - d i m e n s i o n a l subspace o f R n f o r any x i n Q where Q - x = {x - x:x e Q}. Let M = {x e R n : c T x + r = d Tx+t = 0}. When c ^ 0 and d / 0, H i s a ( n - 2 ) - d i m e n s i o n a l m a n i f o l d o f R n. O b v i o u s l y , MP\ S = 0. F o r any x i n S, we denote by <M,x> the s m a l l e s t m a n i f o l d i n R n which c o n t a i n s M and x. D e f i n i t i o n 0.10. L e t Q be a subset o f R n. The complementary n J-subspace o f Q i n R , denoted by Q , i s ot~ = {x e R n : x T y = 0 f o r a l l y i n Q}. Theorem 0.11. M s a t i s f i e s the f o l l o w i n g : (a) F o r any x i n S, <M,x> = {x e R n : c T x + r = f ( x ) ( d T x + t ) } (b) F o r any x i n S, <M,x> = ( V f ( x ) } + x. (.c) F o r any x and y i n S such t h a t f ( x ) ^ f ( y ) , we have M = ({Vf(x)}' L+ x) H ( { V f ( y ) } X + y ) . Remark 0.12. When n = 2, c ? 0 and d / 0, M c o n s i s t s o f a . s i n g l e p o i n t and {Vf(x)> + x i s a s t r a i g h t l i n e f o r any - 1 2 ^ x i n S. I n F i g u r e 2, we see t h a t <M,x >,. <M,x >, and <M,xJ> are l i n e s p a s s i n g t h r o u g h the p o i n t x" i n M. Thus the s e t s o f x at d i f f e r e n t v a l u e s o f f form a p e n c i l o f l i n e s i n t e r -s e c t i n g a t M. The g r a d i e n t v e c t o r Vf moves i n the c l o c k w i s e d i r e c t i o n around 1. 12 F i g u r e 2 When n = 3 , c ^ 0 and d / 0, K i s a s t r a i g h t _ x l i n e and { V f ( x ) } + x i s a p l a n e f o r any x i n S. Then 1 2 3 <M,x >, <M,x >, and <M,x > are p l a n e s p a s s i n g t h r o u g h M. The. g r a d i e n t v e c t o r Vf moves i n the c l o c k w i s e o r c o u n t e r -c l o c k w i s e d i r e c t i o n around M. Theorem 0 . 1 3 . Let {x 1 1} be a sequence i n S - {x} such t h a t x n x and x n - x l i m X x = y n+<» | x -x | f "V f <*> - y Tvf(x-) . | x n - x | Then lim. n+°° CHAPTER 1 The m u l t i c r i t e r i a l i n e a r f r a c t i o n a l programming problem (MLFP) can be s t a t e d as f o l l o w s : (MLFP) 'MAX' P ( x ) = ( f x ( x ) , , . . , f L ( x ) ) s u b j e c t t o x e S ='{x e R n:Ax < b} where A i s an (mxn ) - m a t r i x , b i s an m-vector and f ^ , . . . , f ^ a r e 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 d e f i n e d by f ± ( x ) = ( c ^ x + r i ) / ( d ^ x + t 1 ) , V x e s where c^,d^ a r e n - v e c t o r s and , t ^ a re r e a l numbers. Throughout t h i s t h e s i s , i t i s assumed t h a t the denominators o f f ^ , i = 1,...,L, are s t r i c t l y p o s i t i v e at a l l f e a s i b l e p o i n t s i n S and S i s bounded u n l e s s s t a t e d o t h e r w i s e . With r e g a r d t o v e c t o r i n e q u a l i t i e s , we w i l l a p p l y t h e f o l l o w i n g c o n v e n t i o n : f o r any two v e c t o r s y"^ and y 2 i n R L, y 1 £ y 2 i f and o n l y i f ^ y 2 f o r a l l 1 2 1 2 i = 1,...,L; y y i f and o n l y i f y i y and y 1 ¥• y 2 ; y 1 < y 2 i f and o n l y i f y j < y 2 f o r a l l i = 1,...,L. When L = l , ^ and < have same meaning. Without the e x p l i c i t knowledge o f t h e d e c i s i o n maker's u t i l i t y f u n c t i o n U ( F ( x ) ) which u n i f i e s t he L c r i t e r i a f - ^ , . . . , f ^ , (MLFP) becomes the problem o f f i n d i n g 14 t h e s o l u t i o n s w h i c h a r e e f f i c i e n t o r weakly e f f i c i e n t i n the sense o f the f o l l o w i n g d e f i n i t i o n s . 1 2 1 D e f i n i t i o n 1.1. L e t x ,x e S . We say t h a t x i s dominated ( r e s p e c t i v e l y , s t r o n g l y dominated) by x i f and o n l y i f F ( x 1 ) ^ F ( x 2 ) ( r e s p e c t i v e l y , F ( x 1 ) < F ( x 2 ) ). D e f i n i t i o n 1.2. A p o i n t x i n R n i s s a i d t o be an e f f i c i e n t s o l u t i o n o f (MLFP) i f and o n l y i f x z S and t h e r e does not e x i s t y e S s a t i s f y i n g F ( x ) < F ( y ) . We denote the, s e t o f a l l e f f i c i e n t s o l u t i o n s o f (MLFP) by E. The image F(E) o f E under F i s c a l l e d the e f f i c i e n t f r o n t i e r o f (MLFP). D e f i n i t i o n 1.3. A p o i n t x i n R n i s s a i d t o be a weakly e f f i c i e n t s o l u t i o n o f (MLFP) i f and o n l y i f x e S and t h e r e does not e x i s t y e S s a t i s f y i n g F ( x ) < F ( y ) . We denote t h e s e t o f a l l weakly e f f i c i e n t s o l u t i o n s o f (MLFP) by E W . The image F ( E W ) o f E W under F i s c a l l e d t h e weakly e f f i c i e n t f r o n t i e r o f (MLFP). S e c t i o n 1. C h a r a c t e r i z a t i o n o f E f f i c i e n c y L e t P i > - * - j P m . b e t h e row v e c t o r s o f the m a t r i x A. We now d e f i n e the n o t i o n o f a f a c e o f S. D e f i n i t i o n 1.4. A subset T o f S i s s a i d t o be a f a c e o f S « i f and o n l y i f t h e r e e x i s t s J C ( l 3 . . . 5 m } such t h a t T c o n s i s t s o f p o i n t s s a t i s f y i n g p i x = b i 5 V 1 e J ^ p^x < b ± , V i £ J (3) T i s ' c a l l e d the f a c e o f S c o r r e s p o n d i n g t o J . The f o l l o w i n g theorem g i v e s the c h a r a c t e r i z a t i o n o f e f f i c i e n t p o i n t s i n T. I t i s e s s e n t i a l l y t h e Kuhn-Tucker c o n d i t i o n s [ 6 0 ] g e n e r a l i z e d f o r m u l t i p l e o b j e c t i v e s . The p r o o f o f t h e n e c e s s i t y r e q u i r e s o n l y the p s e u d o c o n v e x i t y o f f - p . . . , f j j and t h e p r o o f o f the s u f f i c i e n c y r e q u i r e s o n l y the p s e u d o c o n c a v i t y o f f f , . L e t R n denote the s e t o f a l l X L i O v e c t o r s i n R n w i t h n o n n e g a t i v e components 3 R^ denote th e s e t o f a l l v e c t o r s i n R n w i t h s t r i c t l y p o s i t i v e components. Let VF(x) denote th e ( L x n ) - m a t r i x whose i - t h row i s t h e g r a d i e n t v e c t o r V f j L ( x ) f o r i = 1,...,L . Theorem 1.5« A p o i n t x* i n t h e f a c e T c o r r e s p o n d i n g t o the i n d e x s e t ' { l , . . . , k } i s e f f i c i e n t i f and o n l y i f x* e T and t h e r e e x i s t a e R k and w e R^ such t h a t o + a T A k = w TVF(x*) ( 4 ) where A k i s the ( k x n ) - m a t r i x w i t h row v e c t o r s P^ J...-,Pj c • P r o o f . ( N e c e s s i t y ) Suppose t h e r e e x i s t s x i n R n such t h a t « p i x ^ b i » f o r a 1 1 1 = 1»'-«» k C5) ( x - x * ) T V f 1 ( x * ) > 0 (6) ( x - x * ) T V f i ( x * ) £ 0 , f o r a l l i = 2,...,L (7) Then i t f o l l o w s from t h e p s e u d o c o n v e x i t y o f f - ^ , . . . , ^ and ( 3 ) t h a t t h e r e i s a p o i n t y i n the l i n e segment [x;x*] , s u f f i c i e n t l y c l o s e t o x*, such t h a t y e S and f - ^ x * ) ' < f-^Cy) and f 1 ( x * ) ^ f 1 ( y ) , f o r a l l i = 2,...,L . T h i s c o n t r a d i c t s the h y p o t h e s i s t h a t x* i s an e f f i c i e n t s o l u t i o n o f (MLFP). Hence the f o l l o w i n g system pT(x-x*) ^ 0 , f o r a l l i = l , . . . , k ( x - x * ) T V f 1 ( x * ) £ 0 , f o r a l l i = 2,...,L ( x - x * ) T V f 1 ( x * ) > 0 has no s o l u t i o n f o r x-x* . By the F a r k a s ' lemma, t h e r e e x i s t r e a l numbers a-^ £ 0 , f o r i = l , . . . , k and w-^ > 0 , f o r i = 2,...,L such t h a t k Z a,.p. = V f , ( x * ) + Z w,.Vf. ( x * ) . i = i 1 1 1 1 m 1 1 1 By exchanging the r o l e s o f f-, w i t h f . • , 2 j ^ L , i n the above argument, we can show t h a t t h e r e e x i s t r e a l numbers a ^ ^ 0 , f o r i = l , . . . , k and w j i ^ 0 > 1 ^ j > 1 ^ i $ L such t h a t k Z a..p. = V f . ( x * ) + Z w . . V f , ( x « ) i = i J 1 1 J ' jy j J 1 1 17 L L Let a. = £ a.. , f o r 1 = l , . . . , k and w. = 1 + E w.. , f o r i = 1,...,L . Then a e R k , w e R^ and e q u a t i o n ( 4 ) h o l d s . ( S u f f i c i e n c y ) Suppose x* i s dominated by x e S . We may assume t h a t f x ( x * ) < f x ( x ) and f ^ x * ) ^ f ± ( x ) , f o r i = 2,,..,L I t f o l l o w s from the p s e u d o c o n c a v i t y o f f - ^ , . . . , f ^ t h a t ( x - x * ) T V f 1 ( x * ) > 0 and ( x - x * ) T V f ± ( x * ) £ 0 , f o r i = 2 , . . . Thus w T V F ( x * ) ( x - x * ) > 0 ( 8 ) But e q u a t i o n ( 2 ) i m p l i e s t h a t a T A k ( x - x * ) ^ 0 ( 9 ) From ( 8 ) and ( 9 ) , we see t h a t e q u a t i o n ( 4 ) can not h o l d . T h i s i s a c o n t r a d i c t i o n . Hence x* i s e f f i c i e n t . The f o l l o w i n g example shows t h a t T P i E need not be a convex s e t . Thus e q u a t i o n ( 4 ) i s not a system o f l i n e a r e q u a t i o n s . Example 1 . 6 . L e t f-^(x) = x ^ / x 2 , f 2 ( x ) = x^ , f ^ ( x ) = ( - x 1 - x 3 ) / ( x 2 + l ) and S = {x e R^:0 . 1 < x ^ x ^ x ^ $ 4} L e t T be t h e f a c e o f S c o r r e s p o n d i n g t o J = 0 . Then T i s the i n t e r i o r o f S and e q u a t i o n ( 4 ) becomes 1 x 1 x +x 1 w - , ( — , \- , 0 ) + w 2 ( 0 , 0 , l ) + w.( , — — \ , ) = 0 x 2 x 2 D x 2 + l ( x 2 + l ) x 2 + l .1.8 2 2 Thus w 1 = w^Xp/Cxg+l) j w-^ = w^x 2( x-j^+x^)/x-j^C x 2 + l ) and W 2 = w 3 ^ x 2 + 1 ^ • T n : L S i s e q u i v a l e n t t o x-^ = x 2 x ^ . Thus T O E c o n s i s t s o f p o i n t s s a t i s f y i n g 0.1 < x - j ^ x ^ x ^ < 4 , and x-^ = x 2 x ^ O b v i o u s l y , T H E i s not a l i n e a r l y c o n s t r a i n e d s e t . I n f a c t , (2,1,2) and (2,2,1) are p o i n t s i n T O E but (2,1.5,1.5) = 0.5(2,1,2) + 0.5(2,2,1) i s not i n T O E . Hence T H E i s not a convex s e t . U n l i k e the l i n e a r case the set. E may not be a c l o s e d subset o f S. A l s o some i n t e r i o r p o i n t s o f S can be e f f i c i e n t w i t h o u t n e c e s s a r i l y h a v i n g E = S which i s the case f o r m u l t i p l e o b j e c t i v e l i n e a r programs where the g r a d i e n t v e c t o r s o f t h e o b j e c t i v e f u n c t i o n s a r e independent o f x. T h i s i s shown by the next example. Example 1.7. L e t f - ^ x ) = ( - x 1 + l ) / ( - x 1 - x 2 + 3 ) , f 2 ( x ) = ( - x 2 - l ) / ( x 1 + 2 x 2 + l ) , f 3 ( x ) = x 2 and S ='{x e R 2 : x 1 + x 2 < 2 , x1 £ 0 and x 2 £ 0} . I t f o l l o w s from Remark 0.12 t h a t V f ^ moves i n c l o c k w i s e d i r e c t i o n around (1,2) and V f 2 moves i n c l o c k w i s e d i r e c t i o n around (1,-1) . Then E c o n s i s t s o f the shaded r e g i o n and the heavy l i n e s i n F i g u r e 3- E i s not c l o s e d s i n c e I t does not c o n t a i n p o i n t s i n {x e R :x-^ = 1 , 0 <. x 2 < 1 . I t i s o b v i o u s t h a t E ^ S and E c o n t a i n s 19 ( 0 , 2 ) x. (1,-D F i g u r e 3 i n t e r i o r p o i n t s o f S, S e c t i o n 2. C h a r a c t e r i z a t i o n o f Weak E f f i c i e n c y S i n c e S i s assumed t o be a compact s e t , t h e r e e x i s t z 1 , , z L i n S such t h a t f . ( z 1 ) = max f . ( x ) , i = 1,...,L xeS Let u* = f ^ i 1 ) + e , i — 1, . . . , L ( 1 0 ) ( I D where e i s a s m a l l p o s i t i v e number. The exact magnitude o f e i s not i m p o r t a n t as l o n g as e' i s s m a l l r e l a t i v e t o f ± ( z 1 ) . u* r e p r e s e n t s an i d e a l ( i n f e a s i b l e ) g o a l used t o compare 20 the achievement o f f e a s i b l e p o i n t s i n S. For any v e c t o r 3 > 0 i n R L, Bowman [ l 5 ] d e f i n e d the f o l l o w i n g problem p a r a m e t r i z e d by $: ( T P ) Minflu* - F ( x ) l g s u b j e c t t o x e S where || ||g i s the g e n e r a l i z e d T c h e b y c h e f f norm d e f i n e d by | y | L = Max B |y | , V y e R L ( 1 2 ) We c a l l t h e c u r v e s o f e q u a t i o n s o f the form ||u* - y\\^ = a the i s o q u a n t s o f ||u* - y||g. F i g u r e 4 i l l u s t r a t e s t h a t t h e i s o q u a n t s o f || u* - y||g are L-shaped c u r v e s w i t h ' c o r n e r s ' on the l i n e t h r o u g h u* w i t h d i r e c t i o n ( l / S ^ j i / B ^ ) . Thus the parameter v e c t o r 3 > 0 s p e c i f i e s the d i r e c t i o n o f the l i n e c o n t a i n i n g the ' c o r n e r s ' . The p o i n t x* i s an o p t i m a l s o l u t i o n o f (T3) and F ( x * ) i s on the e f f i c i e n t f r o n t i e r . We observe t h a t F ( x * ) i s a t the ' c o r n e r ' o f ]|U* - y | = ||U* - F ( x * ) f R . F i g u r e k 21 The problem (TB) can be r e w r i t t e n as min z s u b j e c t t o z £ ^ i ^ u * ~ f ^ ( x ) ) . J x e S T h i s i s e q u i v a l e n t t o the f o l l o w i n g program (GB) min max B-z. l N<is<L s u b j e c t t o f ^ ( x ) + z^ £ u* , x e S Remark 1.8. The o b j e c t i v e f u n c t i o n o f (GB) i s known as t h e L / C m e t r i c . The £ p m e t r i c i s ( I ( B , z , ) p ) / p . When p = 1, 1=1 1 L the £ p m e t r i c i s I $*z*> which i s the weighted sum o f i = l 1 1 t h e underachievements z^. Thus (TB) can be r e g a r d e d as a s p e c i f i c form o f t h e g e n e r a l g o a l programming problem [ 2 , 5 6 ] . W ith F as a g e n e r a l c o n t i n u o u s f u n c t i o n , Bowman [15] has shown t h a t e v e r y e f f i c i e n t s o l u t i o n o f (MLFP) i s an o p t i m a l s o l u t i o n o f (TB) f o r some B > 0 and, under the assumption t h a t every dominated s o l u t i o n i s s t r o n g l y dominated, a l l o p t i m a l s o l u t i o n s o f (TB ) , B > 0, are e f f i c i e n t solutions o f (MLFP). The next theorem shows t h a t weak e f f i c i e n c y i s c h a r a c t e r i z e d by the g e n e r a l i z e d T c h e b y c h e f f norm. The p r o o f i s v a l i d f o r a r b i t r a r y f u n c t i o n F. i = 1,. . . L l — 1 j • • • L Theorem 1 . 9 . Let x* be a f e a s i b l e p o i n t i n S. Then x* i s weakly e f f i c i e n t i f x* s o l v e s ( T 3 ) f o r some 3 > 0 . P r o o f : ( S u f f i c i e n c y ) Suppose x* s o l v e s ( T 3 ) f o r some 3 > 0 . I f x* i s s t r i c t l y dominated by x' i n S, t h e n F ( x * ) < F ( x ' ) and thus 3 . ( u * - f . ( x * ) ) > 3 ± ( u * - f . ( x ' ) ) , i = l , . . . , L I t f o l l o w s t h a t . flu* - P ( x * ) | | B > |i u* - F ( x ' ) | | R T h i s c o n t r a d i c t s the h y p o t h e s i s t h a t x* s o l v e s ( T 3 ) . Hence x* i s weakly e f f i c i e n t . ( N e c e s s i t y ) Suppose x* i s weakly e f f i c i e n t . Set 3 ± = l / ( u * - f ± ( x * ) ) , i = 1 , . . . ,L Then 3 > 0 . and f u * - F ( x * ) | | R = 1 . Assume t h a t x* does not s o l v e ( T 3 ) . L e t x" be an o p t i m a l s o l u t i o n o f ( T 3 ) . Then ||u* - F ( x " ) ||R < ||u* - F ( x * ) ||R = 1 . I t f o l l o w s t h a t F ( x * ) < F ( x " ) . Thus x* i s not weakly e f f i c i e n t . T h i s i s a c o n t r a d i c t i o n . Hence x* s o l v e s ( T 3 ) . Based on Theorem 1 . 9 one can generate weakly e f f i c i e n t s o l u t i o n s o f (MLFP) by s o l v i n g (T3) f o r d i f f e r e n t parameter v e c t o r s 3 > 0 . L e t us c a l l t he l i n e t h r o u g h u* w i t h d i r e c t i o n ( 1 / 3 ^ . . . . . . . , 1 / 3 - ^ ) t h e s e a r c h i n g l i n e o f ( T 3 ) . Then the s o l u t i o n o f ( T 3 ) i s o b t a i n e d by s h i f t i n g the L-shaped c u r v e , w i t h t h e ' c o r n e r ' pegged on the s e a r c h -i n g l i n e and w i t h o u t r o t a t i o n , towards F(S') from u* u n t i l the L-shaped curve touches F ( S ) . T h i s i s shown i n F i g u r e 5. Thus the problem (Tg) seeks the f e a s i b l e s o l u t i o n which i s ' n e a r e s t ' , i n the sense o f the g e n e r a l i z e d T c h e b y c h e f f norm, t o t h e i d e a l g o a l u* (not a t t a i n a b l e ) . In F i g u r e 5, when g^ I s i n c r e a s e d from 1 t o 3 w h i l e g 2 i s kept a t 1, the s e a r c h i n g l i n e o f (Tg) moves c o u n t e r - c l o c k w i s e around u* and F ( x | ) moves c l o s e r towards -F(z^) where x | i s an o p t i m a l s o l u t i o n o f (Tg). Thus the parameter v e c t o r g > 0 , I n d i c a t e s t h e r e l a t i v e i m p o r t a n c e o f t h e d e v i a t i o n s o f the o b j e c t i v e v a l u e s from u*. We d e f i n e d u* w i t h e > 0 so - 2 t h a t z i s an o p t i m a l s o l u t i o n o f (Tg) when B 2 i s s u f f i c i e n t l y l a r g e r t h a n g n . (3,1) F i g u r e 5 Due t o the n o n l i n e a r i t y o f (TB ) , i t i s d i f f i c u l t and i m p r a c t i c a l t o o b t a i n the exact parameter v e c t o r 3 > 0 c o r r e s p o n d i n g t o the o p t i m a l s o l u t i o n o f max U ( F ( x ) ) xeS even when U has n i c e f u n c t i o n a l form. I t . f o l l o w s from the above d i s c u s s i o n t h a t an i n t e r a c t i v e a l g o r i t h m can be used t o s o l v e max U ( F ( x ) ) by s o l v i n g a s e r i e s o f problems xeS (TB) w i t h B > 0 a d j u s t e d by the d e c i s i o n maker i n t e r a c t i v e l y t o r e f l e c t h i s t r a d e - o f f s among the d e v i a t i o n s o f the o b j e c t -i v e v a l u e s from u*. U n l i k e the s e t E, t h e s e t E W i s always a c l o s e d s e t . The p r o o f o f t h e next theorem i s v a l i d f o r a r b i t r a r y c o n t i n u o u s f u n c t i o n F. Theorem 1.10. The s e t E^ o f a l l weakly e f f i c i e n t s o l u t i o n s of (MLFP) i s c l o s e d . P r o o f . L e t { x n , n = 1, 2,....} be any sequence o f p o i n t s i n E W . S i n c e S i s compact, we may assume t h a t l i m x n = x* f o r some x* e S. Suppose x* £ E^. There e x i s t s x e S such t h a t F ( x * ) < F ( x ) . I t f o l l o w s from the c o n t i n u i t y o f F t h a t F ( x n ) < F ( x ) f o r s u f f i c i e n t l y l a r g e n. T h i s n W W c o n t r a d i c t s the f a c t t h a t x e E . Hence x* e E and W E i s c l o s e d . S e c t i o n 3- Subproblems o f (MLFP). I n the study o f (MLFP), i t i s n a t u r a l t o i n v e s t i g a t e 25 v a r i o u s subproblems o f (MLFP) o b t a i n e d by d e l e t i n g some of t h e c r i t e r i a or/and i m p o s i n g c e r t a i n m i n i m a l l e v e l s on c e r t a i n c r i t e r i a . F o r c o n v e n i e n c e , we i n t r o d u c e the f o l l o w i n g d e f i n i t i o n s . D e f i n i t i o n 1.11. L e t J be a subset o f {1,...,L} and | J | denote t h e number o f i n d i c e s i n J . We d e f i n e the f u n c t i o n F j from S t o F J J ' by F j ( x ) = j , Vx e S. We d e f i n e (PJ) as f o l l o w s : (PJ) 'MAX' F j ( x ) s u b j e c t t o x E S We denote by E j ( r e s p e c t i v e l y , E j ) t h e set o f a l l e f f i c i e n t ( r e s p e c t i v e l y , weakly e f f i c i e n t ) s o l u t i o n s o f ( P J ) . D e f i n i t i o n 1.12. For 1 ^ k ^ L and a e R, we d e f i n e (P^a) as f o l l o w s : ( P k a ) 'MAX' P j ( x ) s u b j e c t t o x e S and f k ( x ) ^ a where J = {1,....,L} - {k}. L e t E, ( r e s p e c t i v e l y , E^f ) denote t h e s e t o f a l l e f f i c i e n t ( r e s p e c t i v e l y , . w e a k l y e f f i c i e n t ) s o l u t i o n s o f (P^ot) . As the subproblems (PJ) and (P^ct) are s i m p l e r problems w i t h fewer c r i t e r i a , i t w i l l be h e l p f u l t o i n v e s t -i g a t e the r e l a t i o n s h i p between t h e i r s o l u t i o n s and those of (MLFP). We hope t o have some i n t i m a t e r e l a t i o n s between E, E T and E. o r between E W , E! and E^ t h a t would a l l o w ' J k ,a ' J k, a us t o a p p l y m a t h e m a t i c a l i n d u c t i o n on the number of c r i t e r i a 2 6 W L i n d e r i v i n g some g l o b a l p r o p e r t i e s o f E and E . B a s i c a l l y , a we l i k e t o know when a s o l u t i o n o f a subproblem i s an e f f i c i e n t o r a weakly e f f i c i e n t s o l u t i o n o f (MLFP) and v i c e v e r s a . Theorem 1 . 1 3 . F o r any a e R, l ^ k ^ L and J CH { 1 , . . . , L } , w w w w we have E^ C E w and E, C E . J k,a P r o o f . Obvious. • I t f o l l o w i n g from Theorem 1 . 1 3 t h a t E*J U E?J • C E W . However, t h i s r e l a t i o n does not h o l d between E, E T and E, • J k, a The next example shows t h a t i t i s p o s s i b l e t o have ( 1,-D F i g u r e 6 27 Example 1.14. We r e f e r t o Example 1.7 which i s i l l u s t r a t e d i n F i g u r e 6. At t h e p o i n t x* = (1,0.5), V f ^ x * ) = -vf ( x * ) . Thus x* e E j w i t h J = {1,2} and x* E E^ Q y But x* i s dominated by the p o i n t (1,1). Hence E T f) E_ n c E. Some weaker r e l a t i o n e x i s t s between E, E T and E, T h i s i s g i v e n i n t h e next theorem. Theorem 1.15. L e t a e R, 1 ^ k < L and J = { l , . . . , L } - {k} I f x E E , t h e n one o f the f o l l o w i n g m u t u a l l y e x c l u s i v e cases must h o l d : (a) There e x i s t s y e S such t h a t ^ ( y ) > a a n d F j ( x ) =. F j ( y ) . I n t h i s c a s e , x E E J . .(b) ^ ^ ( y ) = a f o r every y e S s a t i s f y i n g F j ( x ) = F j ( y ) . I n t h i s c a s e , x e E. Pr o o f . (a) Suppose x £ E j . Then t h e r e e x i s t s y e S such t h a t F j ( x ) ^ F j ( y ) - By Theorem 0 . 4 , t h e r e e x i s t s z e [ y ; y ] , s u f f i c i e n t l y c l o s e t o y, such t h a t F j ( x ) ^ F j ( z ) a n d f ^ ( z ) > a. T h i s c o n t r a d i c t s the h y p o t h e s i s t h a t x e E^ . ^. Hence x E E J . (b) Suppose x £ E. Then t h e r e e x i s t s y e S such t h a t F ( x ) < F ( y ) . S i n c e f k ( y ) •> f k ( x ) > a a n d * e E k , a ' we can not have F j ( * ) ^ F j ( y ) . Thus F j ( x ) = F j ( y ) a n d f ^ ( y ) > f k ( x ) > «• T h i s i s a c o n t r a d i c t i o n . Hence x e E. There are many u s e f u l r e l a t i o n s between E W , E^ 28 W , x and E, . When the c o n s t r a i n t f. (x) > a i s not b i n d i n g , the weakly e f f i c i e n t s o l u t i o n s o f ( p k a ) are weakly e f f i c i e n t i n (PJ) and every weakly e f f i c i e n t s o l u t i o n x* of (MLFP) i s weakly e f f i c i e n t i n ( P k f k ( x * ) ) . T h i s i s g i v e n i n t h e next theorem. Theorem 1.16. L e t a e R, 1 ^ k $ L and J = {1,...,L} - {k}. (a) I f x e EY and t h e r e e x i s t s y e S such k,a J t h a t f k ( y ) > a and - F j ( x ) = P j ( y ) , t h e n x £ E j . (b) I f x £ E W and f. (x) < max f, ( x ) , t h e n x £ E^ •_ ,- v k X £ S k^ k , f k ( x ) P r o o f . (a) S i m i l a r t o t h e p r o o f o f Theorem 1.15 (a) (b) W -Suppose x i E k ^ ( x ) . Then t h e r e e x i s t s y £ S such t h a t f k ( y ) > f k ^ x ^ a n d < P J ^ " W e m u s t h a v e f k ( y ) = f k ( x ) s i n c e x £ E W . L e t z k e S such t h a t f. ( z k ) = max f, (x) . Then by Theorem 0.4, t h e r e e x i s t s K X£S k z £ [ y ; z k ] , s u f f i c i e n t l y c l o s e t o y, such t h a t F ( x ) < F ( z ) . T h i s c o n t r a d i c t s t h e h y p o t h e s i s t h a t x e E W . Hence r. _ FW x . e E k , f k ( x ) -F o r any k, 1 ^ k ^ L, i t f o l l o w s from Theorem 1.16(a) t h a t E ^ ^ f ^ ' C a ) i m p l i e s E£ n E]J 0 w i t h J = {1,...,L} - {k}. I f x* e E™, then x* £ E™ J ' k, a and 29 <Z f, 1 ( a ) f o r a l l a < f. ( x * ) . I t i s o b v i o u s t h a t k,a k k # • • C f7^(a) f o r a = max f. ( x ) . Thus we have r o u g h l y K , a K xeS K E k a C ^lc"^ f o r l a r g e r a a n d E k a ^ ^ 1 ^ ^ f o r s m a l l e r a. The ex a c t p o i n t o f s e p a r a t i o n i s 6 ^ d e f i n e d by 6 k > l n f { a e R : E k . , a C f k 1 ( a ) K We have E^ C f . " 1 ^ ) , f o r a l l a > 6, and 'E? (£ f ~ 1 ( a ) f o r a l l a < 6 ^ . The next theorem d e s c r i b e s what happens at a = 6\ . k Theorem 1.17. L e t J = ( l , . . . , L } - { k } , 1 < k ^ L. / - w - w (b) There e x i s t s x e E, * such t h a t x z E T . k , 6 k J P r o o f . (a) - W Suppose t h e r e e x i s t s x e E, «• such t h a t K ' ° k f k ( x ) > 6 .• Then i t f o l l o w s from Theorem 1.16 (a) t h a t x e E^ J. L e t a = 0 . 5 ( f , ( x ) + 6, •). Then x e E ^ - and J k k k,a f, (x) > a. Thus E^ - Ct fT1 (a) . By the d e f i n i t i o n o f 6. , k kjCt k J k' we have 6 k > a. T h i s i s . a c o n t r a d i c t i o n . Hence (b) L e t { a n } be a s t r i c t l y i n c r e a s i n g sequence o f r e a l numbers such t h a t l i m a n = 6^. Then t h e r e e x i s t s n-*-°° x n e n - f, ^ ( a n ) , Vn. S i n c e S i s compact, we may assume t h a t l i m x n = x. Suppose x i E^. Then t h e r e n+°° e x i s t s y E EJ such t h a t F_(x) .< . F _ ( y ) . Thus F j ( x n ) < F f o r n s u f f i c i e n t l y l a r g e . S i n c e x n e n - f , _ 1 ( a n ) , we have f k ( y ) < « n < f k ( x n ) . By Theorem 0.4, t h e r e e x i s t s z e [ y ; x n ] such t h a t f k ( ' z ) = a n and F j ( x n ) < F j ( z ) . T h i s c o n t r a d i c t s the h y p o t h e s i s t h a t -n W - W x e E, n . Hence x e E,. k,a J S e c t i o n 4. Summary The Kuhn-Tucker c o n d i t i o n s a re n e c e s s a r y and s u f f i c i e n t f o r the e f f i c i e n t s o l u t i o n s o f (MLFP). U n l i k e the l i n e a r c a s e , the s e t E o f a l l e f f i c i e n t s o l u t i o n s o f (MLFP) i s not n e c e s s a r i l y c l o s e d and may c o n t a i n o n l y a p r o p e r nonconvex subset o f the i n t e r i o r o f S. Weakly e f f i c i e n t s o l u t i o n s can be g e n e r a t e d by s o l v i n g the g e n e r a l i z e d T c h e b y c h e f f norm problem (TB) w i t h d i f f e r e n t parameter v e c t o r s 3 > 0. The problem ( T 3 ) i s a . s p e c i f i c form o f t h e g e n e r a l g o a l programming problem. We a l s o i n v e s t i g a t e d t h e subproblems o f (MLFP) o b t a i n e d by d e l e t i n g some c r i t e r i a or/and i m p o s i n g some m i n i m a l l e v e l s on c e r t a i n c r i t e r i a . There are o n l y some weak r e l a t i o n s between the e f f i c i e n t s o l u t i o n s o f (MLFP) and tho s e o f the subproblems. However, many u s e f u l r e l a t i o n s h o l d between the weakly e f f i c i e n t s o l u t i o n s o f (MLFP) and those o f the 31 subproblems. These r e l a t i o n s a l l o w the a p p l i c a t i o n o f m a t h e m a t i c a l i n d u c t i o n on the number o f c r i t e r i a L i n the p r o o f o f Theorem 3-3 which s t a t e s t h a t the set E W o f a l l weakly e f f i c i e n t s o l u t i o n s o f (MLFP) i s p a t h - c o n n e c t e d . 32 CHAPTER 2 The g e n e r a l b i c r i t e r i a programming problems have a l r e a d y been studied [ 1 , 9 , 2 8 , 3 9 1 . I n t h i s c h a p t e r , we g i v e a t h o r o u g h a n a l y s i s o f the b i c r i t e r i a l i n e a r f r a c t i o n a l programming problems. I t i s shown t h a t t h e s e t o f e f f i c i e n t p o i n t s i s a f i n i t e u n i o n o f l i n e a r l y c o n s t r a i n e d s e t s and the e f f i c i e n t f r o n t i e r i s the image o f a f i n i t e number o f connected l i n e segments o f e f f i c i e n t p o i n t s . A s i m p l e a l g o r i t h m u s i n g o n l y o n e - d i m e n s i o n a l p a r a m e t r i c l i n e a r programming t e c h n i q u e s i s d e v e l o p e d t o e v a l u a t e t h e e f f i c i e n t f r o n t i e r . S e c t i o n 1. C h a r a c t e r i z a t i o n o f E f f i c i e n c y . We w i l l show t h a t t h e c h a r a c t e r i z a t i o n o f e f f i c i e n c y g i v e n by e q u a t i o n (4) i n Theorem 1.5 i s e q u i v a l e n t t o a system o f l i n e a r c o n s t r a i n t s when L = 2. I t f o l l o w s from e q u a t i o n (1) and d^x+t^ > 0 t h a t t he g r a d i e n t v e c t o r V f ^ ( x ) o f f ^ , i = 1 , 2 , a t any p o i n t x i n S has the same T— T— d i r e c t i o n as ( d ^ + t ^ ) ^ - ( c ^ + r ^ d ^ Thus e q u a t i o n (4) can be r e p l a c e d by a l p l + • '•• + a k p k = rp . ip T T W l ^ d l X * + t l ^ C l - W l ^ c x x ' * + r i ) d l + w 2 ( d 2 X * + t 2 ^ C 2 _ W 2 ( c 2 x * + r 2 ^ d 2 (13) E q u a t i o n (13) i s e q u i v a l e n t t o the f o l l o w i n g system a 1 p 1 + ... + a k p k = q 1 c 1 - + q 2 c 2 - h 2 d 2 (14) f 1(x«) = h i / q i , i = 1,2 and q ± > 0, i =1,2. S i n c e e q u a t i o n (14) can be m u l t i p l i e d by any p o s i t i v e r e a l number, f^.(x*) = h^/q^ can be r e p l a c e d by c^x* + r x = h± (15) and d^x* + t-_ = q x . ( l 6 ) By t a k i n g i n n e r p r o d u c t o f x* w i t h b o t h s i d e s o f e q u a t i o n ( 1 4 ) , we get t ) l a l + ' ' ' + b k a k = q i c i x * ~ h _ d ^ x * + Q 2 C 2 X * ~ h 2 d 2 x * (17) Now f 2(x») .= h 2 / q 2 T T i f f h 2 d 2 x * + h 2 t 2 = ' q 2 c 2 x * + q 2 r 2 T T i f f h 2 t 2 - q 2 r 2 = Q 2 C 2 X * - h 2 d 2 x * i f f h 2 t 2 - q 2 r 2 - q 1 ( c ^ x * + r 1 ) = q 2 c 2 . x * - h 2 d 2 x * - h 1 ( d ^ x * + t (because q 1(c^x»+r 1) = h - ^ = h 1 ( d ^ x * + t 1 ) by (15) and (16)) i f f h 2 t 2 - q 2 r 2 - q 1 r 1 + h - L t - L = q 1c^x*-h 1d^'x* + q 2 c 2 x * - h 2 d 2 x i f f h 1 t 1 + h 2 t 2 - q 1 r 1 - q 2 r 2 = b 1a 1+...+b Ra k (by (17)) Therefore,- e q u a t i o n (4) o f Theorem 1.5 i s e q u i v a l e n t t o the f o l l o w i n g system: 'a_P_-+ ••• + a k p k = q 1 c 1 . - h 1 d 1 + q 2 c 2 - h 2 d 2 34 c l x * + r l = h l d^x* + t x = q i h h l + t 2 h 2 " r l q l " r 2 q 2 = b l a l + ••• V k q j _ > 0 , i = 1 , 2 . We have proved the f o l l o w i n g lemma. Lemma 2.1. A p o i n t x* i n T i s e f f i c i e n t i f and o n l y i f .there e x i s t r e a l numbers a^,. .. , a k , h ^ , h 2 ' q i , c * 2 s u c h t n a t a l p l + + ak pk = q l C l ~ h l d l + q 2 C 2 - h 2 d 2 T c^x* + r l = h l d^x* + H - q l + t 2 h 2 " T l Q l - r 2 q 2 = b l a l + + V k p±x* - i = 1,... ,k pTx* < b i > i = k+1,. . . ,m a i ^ 0 , i = 1,.. . ,k and > 0, i = 1, 2 From Lemma 2.1, we see t h a t the c h a r a c t e r i z a t i o n o f e f f i c i e n t p o i n t s i n T i s g i v e n by a system o f l i n e a r e q u a t i o n s and i n e q u a l i t i e s . Thus we have t h e f o l l o w i n g c o r o l l a r y and theorem. C o r o l l a r y 2.2. The s e t o f a l l e f f i c i e n t p o i n t s i n any g i v e n f a c e o f S i s convex. 35 Theorem 2.3- The i n t e r s e c t i o n o f E and T i s a l i n e a r l y c o n s t r a i n e d s e t and E i s a f i n i t e u n i o n of l i n e a r l y c o n s t r a i n e d s e t s . The f o l l o w i n g example i s g i v e n as an i l l u s t r a t i o n o f Theorem 2.3-Example 2.4. 1 MAX' f ^ x ) = x 1 / ( x 1 + x 2 ) J f 2 ( x ) = (-3x1+2x2)/(x1-x2+3) s u b j e c t t o 2 x 1 - 4 x 2 ^ 4 - x 1 - 2 x 2 ^ -2 - x 1 + x 2 < 1 x 1 ^ 6 x 1 ( 0 , l ) (6,7) x^(2,0) F i g u r e 7 36 The f e a s i b l e r e g i o n S i s shaded i n F i g u r e 7. I t f o l l o w s from Remark 0.12 t h a t V f ^ and Vf. 2 move i n the c l o c k w i s e d i r e c t i o n around the p o i n t s (0,0) and (6 ,9) r e s p e c t i v e l y . Thus the e f f i c i e n t s o l u t i o n s i n the f a c e s o f S are { x 1 } , ( x ^ x 2 ] , ( x 2 ; x 3 ) , [ x 3 ^ ) and {x^}. Thus E i s the u n i o n o f f i n i t e l y many l i n e segments and p o i n t s . S e c t i o n 2. E v a l u a t i o n o f E f f i c i e n t F r o n t i e r When L = 2, the most e f f e c t i v e way t o p r e s e n t the e f f i c i e n t s o l u t i o n s i s a g r a p h i c a l p r e s e n t a t i o n o f the e f f i c i e n t f r o n t i e r . T h i s i m m e d i a t e l y d e p i c t s , i n a c o n c i s e and d i r e c t f a s h i o n , the l e v e l s o f each c r i t e r i o n a t every e f f i c i e n t s o l u t i o n and the c o r r e s p o n d i n g t r a d e - o f f between c r i t e r i a . The c h a r a c t e r i z a t i o n o f e f f i c i e n c y by system o f l i n e a r c o n s t r a i n t s i s not too u s e f u l i n e v a l u a t i n g t h e e f f i c i e n t f r o n t i e r s i n c e t h e r e a re u s u a l l y f a r too many f a c e s t o be scanned f o r e f f i c i e n t p o i n t s . I n t h i s s e c t i o n , we d e s c r i b e a p r a c t i c a l method t o generate the e f f i c i e n t f r o n t i e r . T h i s method i s u s u a l l y termed the c o n s t r a i n t method and has been used by Yu [86] , H o c k i n g and Shepard [ 4 4 ] , Adulbhan and Tabucanon [1] and Benson [9 ] . Due t o the s p e c i a l s t r u c t u r e o f (MLFP) w i t h L = 2, the c o n s t r a i n t method can be t r a n s f o r m e d i n t o a s i m p l e a l g o r i t h m u s i n g o n l y o n e - d i m e n s i o n a l p a r a m e t r i c ( p a r a m e t r i c i n one row) l i n e a r programming t e c h n i q u e s . 37 For any a e R, t h e • problems (P-,a) and (P-a) g i v e n by D e f i n i t i o n .1.12 can be w r i t t e n as ( P 1 a ) MAX f 2 ( x ) s u b j e c t t o x e S f-,(x) > a (P-a) MAX f (x) s u b j e c t t o x e S f 2 ( x ) > a i * F o r i = 1,2 , l e t q* = max f . (x) and x be o p t i m a l 1 xeS 1 s o l u t i o n o f ( P ^ q * ) . I t i s o b v i o u s t h a t ( i ) E = {x:x s o l v e s (P-^a) and (P2<5) f o r some a, 6 e R} ( i i ) V x E E, we have f x ( x 2 * ) $ f 1 ( x ) < q* and f 2 ( x l S ) < f 2 ( x ) < q* . _ 2* -Lemma 2 .5- I f ot > f ^ ( x ) and x s o l v e s ( P ^ a ) , t h e n f 1 ( x ) = a and x e E. P r o o f . Assume t h a t f - ^ x ) > a > f- L(x ). I t i s o b v i o u s t h a t f 2 ( x 2 * ) = q* ^ f 2 ( x ) . I f f 2 ( x 2 * ) > f 2 ( x ) , t h e n by Theorem 0.4, t h e r e 1 - 2 * e x i s t s x e [x;x ] such t h a t a < f 1 ( x 1 ) and f 2 ( x ) < f ^ x 1 ) Thus x 1 i s f e a s i b l e t o ( P 1 a ) and f 2 ( x ) < f 2 ( x 1 ) . T h i s I m p l i e s t h a t x does not s o l v e ( P ^ a ) . 38 2 ^ 2 ^ $t I f f j ( x ) = f 2 ( x ) , then x does not s o l v e ( P 2 q 2 ) . Hence, f-^Cx) = a Let x e S. I f f-^Cx) > f-^Cx), then x cannot be an o p t i m a l s o l u t i o n o f (P-^ct) and hence f 2 ( x ) < f 2 ( x ) . I f f 2 ( x ) > f 2 ( x ) , then x cannot be f e a s i b l e t o (P^a) and hence f-^(x) < f - ^ ( x ) . C o n s e q u e n t l y , x e E. The. next lemma f o l l o w s i m m e d i a t e l y from Lemma 2.5. I t i s s i m i l a r t o a r e s u l t i n [ 9 ] • Lemma 2.6. E = {x: x s o l v e s (P^ct) f o r some a e [ f - ^ x 2 * ) ;q*] } . (P-j^ a.) i s c l o s e l y r e l a t e d t o the l i n e a r programming problem (Qct) d e f i n e d by (Qa) MAX c 2 y + r g z s u b j e c t t o Ay 4 zb T d 2 y + t 2 z = 1 T - T °l y + r l Z ^ a ^ d l y + f c l z ^ z > 0 Charnes and Cooper [21] have proved the f o l l o w i n g lemma. 3 9 Lemma 2.7. (1) I f ( y 5 z ) i s a f e a s i b l e s o l u t i o n o f (Qa), then z > 0 (2) I f x s o l v e s ( P 1 a ) J t h e n ( U A d ^ x + t ^ ) x , l / ( d 2 x + t 2 ) ) s o l v e s (Qa) (3) I f ( y , z ) s o l v e s ( Q a ) , t h e n ( l / z ) y s o l v e s (P-^a) ( 4 ) The o p t i m a l v a l u e s o f (P-^a) and (Qa) are e q u a l . Theorem 2.8. E = ' { ( l / z ) y : ( y , z ) s o l v e s (Qa) f o r some a E [ f ^ x 2 * ) ^ * ] } P r o o f . I t f o l l o w s i m m e d i a t e l y from Lemma 2.6 and Lemma 2.7 Theorem 2.9. F o r every a E [ f 1 ( x );q*_), t h e r e e x i s t _ _ Ct ct w E ( a ; q | ) , x and y such t h a t F ( ( x S ; y a ] ) = {F(x) : x s o l v e s ( P ^ ) f o r some a E [ a ; w ] } ( l 8 ) a a — where x and y a r e extreme p o i n t o p t i m a l s o l u t i o n s o f (P-^a) and (Pj^w) r e s p e c t i v e l y and P ( l x 5 ; y 5 ] ) = { F ( x ) : x E [ x S ; y 5 ] } F u r t h e r m o r e , ( x a ; y a ) l i e s i n a o n e - d i m e n s i o n a l f a c e o f S. P r o o f . L e t iw s> be a sequence which s a t i s f i e s a < w s + 1 < / w „ l i m " ^ — ~ " ~ 1 — j - _-S S-+-00 w s < q* V s and l i m w s = a. F o r each s, l e t x s be an extreme p o i n t o p t i m a l s o l u t i o n o f the l i n e a r program (P-^w ) (x may not be an extreme p o i n t o f S ) . Then T s l p ^ : p^x = b p 1 < i ^ m} c o n t a i n s at l e a s t n-1 independent v e c t o r s . L e t fi = {B d {p-^ ,P 2 ,. . • jP m}'• B i s independent and |B| = n - l ) . O b v i o u s l y , fi i s a f i n i t e s e t . Thus t h e r e '10 — T s — e x i s t s B i n ft such t h a t ( s : p . x = b. V i e B} i s * s s k i n f i n i t e . T h e r e f o r e {w } has a subsequence {w } where T s k -p±x = b . V i e B and k = 1,2, S i n c e S i s a s k c l o s e d and bounded s e t , we may assume t h a t {x } i s a s k convergent sequence and l e t x = l i m x k-*°° Then p^x = b. V i £ B and' f ^ x ) = a. F o r every x e S s a t i s f y i n g f - ^ x ) > a, x i s a f e a s i b l e p o i n t i n (P-^ 5 3) and t h u s f 2 ( x ) < f 2 ( x s ) f o r l a r g e s. Hence f 2 ( x ) ^ f 2 ( x ) f o r e v e r y x e S such t h a t f - ^ x ) > a. Suppose t h e r e e x i s t x e S such t h a t f-^fc) = a and f 2 ' ( x ) > f 2 ( x ) . I t f o l l o w s from f 2 ( 5 0 > f 2 ( x ) , f ^ S ) = f - ^ x ) , f 1 ( x s ) = w s > f ] _ ( x ) s and Theorem 0.4 t h a t t h e r e e x i s t s y e (x";x ) such t h a t T-j_(y) > f ^ C x ) and f 2 ( y ) > f 2 ( x ) . But we have j u s t shown t h a t t h i s i s i m p o s s i b l e . Hence x s o l v e s (P-^a). By Lemma 2.6, - s l s 2 x, x , x , ... are e f f i c i e n t s o l u t i o n s o f (MLFP). A l s o they a l l l i e on the o n e - d i m e n s i o n a l l i n e d e f i n e d by T -p i X = b i ' v 1 e B* T t f o l l o w s from C o r o l l a r y 2.2 t h a t - S 2 a - a s 2 - s 2 [x;x ] C E. Let x = x, y = x and w = w . Then [ x a ; y a ] C E i m p l i e s (18) and ( x a ; y a ) l i e s i n the o n e - d i m e n s i o n a l f a c e c o r r e s p o n d i n g t o B. D e f i n i t i o n 2.10. For. every a e [ f ^ ( x ) ; q | ) , l e t D(a) be the se t o f a l l w s a t i s f y i n g t he p r o p e r t i e s s t a t e d i n Theorem 2 . 9 -(Then D(a) ¥• 0 f o r a l l a e [f 1 ( x 2 * ) ;q*)) . We d e f i n e D(q*) =' {q*} . 41 0 2* k Theorem 2.11. L e t a. = f, (x ) and a = sup. w, 1 * w e D ( a K _ 1 ) k = 1,2,... . Then t h e r e e x i s t s N such t h a t a N = . P r o o f . Assume t h a t a k J- q * , k = 0,1,2,... . . k k I t f o l l o w s from Theorem 2.9 t h a t [ x a ; y a ]C E, a k < a k + 1 V k = 0,1,2,... . A l s o ( x a l ; y a l ) and ( x a < ] ; y a J ) l i e i n d i f f e r e n t o n e - d i m e n s i o n a l f a c e s o f S f o r i ? j . T h i s i s i m p o s s i b l e s i n c e S has o n l y f i n i t e number o f on e - d i m e n s i o n a l f a c e s . Hence t h e r e e x i s t s N such t h a t a = q * . C o r o l l a r y 2.12. There e x i s t v° = f ^ x 2 * ) < v 1 ^ v 2 ^ v h = q * and z ^ , z 1 , . . . , z h s a t i s f y i n g z 1 s o l v e s ( P 1 v 1 ) , i = 0,l,...,h (19) P ( [ z 1 ; z i + 1 ] ) = { F ( x ) : x s o l v e s ( P ^ ) f o r some a e [ v 1 ; v 1 + 1 ] }, i = 0,1,...,h-l (20) P r o o f . L e t = f , ( x 2 ) and a k = sup, , w, k = 1,2,.. . 1 w e D ( a k _ ± ) L e t N be the s m a l l e s t i n t e g e r such t h a t a N = q * . The e x i s t e n c e o f N i s guaranteed by Theorem 2.11. L e t h = 2 N - 1, , 0 0 2k-1 2k k 0 a 0 2k-l a k - 1 2k a k v = a , v = v = a , z = x , z = y 3 z = x h h a N - 1 f o r k = 1,2,...,N-1, v = q * and z = y Then v^, v \ . . . , v h and zP ,. . . ,7^ s a t i s f y (19) and (20). Remark 2.13. I t f o l l o w s from C o r o l l a r y 2.12 and Lemma 2.6 t h a t t he e f f i c i e n t f r o n t i e r P(E) i s the image of t h e l i n e 4 2 segments I z ^ j z ' " 1 ! , i = 0 , . . . , h - l , o f e f f i c i e n t p o i n t s . Thus every weakly e f f i c i e n t p o i n t x, which i s not e f f i c i e n t , must s a t i s f y e i t h e r f ^ x ) = q* or f 2 ( x ) = q* . L e t z~^~ be an o p t i m a l s o l u t i o n o f min f ^ ( x ) s u b j e c t t o x e S and f 2 ( x ) > q| • L e t z be an o p t i m a l s o l u t i o n o f min f 2 ( x ) s u b j e c t t o x e S and f ^ ( x ) > q* . Then the weakly e f f i c i e n t f r o n t i e r F ( E W ) i s the image o f the l i n e segments [ z ^ z 1 * 1 ] , i = -1,0,...,h o f weakly e f f i c i e n t p o i n t s . W Theorem 2.14. E and E are c l o s e d and p a t h - c o n n e c t e d by f i n i t e number o f l i n e segments. h _ 1 i i+1 P r o o f . From C o r o l l a r y 2.12, F(E) = \J F ( [ z ;z ] ) . i=0 Thus F(E) i s c l o s e d . Hence E = F - 1 ( F ( E ) ) i s c l o s e d . h-1 i - + 1 We note t h a t | J [z j z 1 ] i s p a t h - c o n n e c t e d . For i=0 every y e E, t h e r e e x i s t x e [ z 1 ^ 1 * " ^ ] f o r some i ( 0 . < i < h-1) such t h a t F ( y ) = F ( x ) . I t f o l l o w s from Theorem 0.4 t h a t [x;y] C E. Thus E i s p a t h - c o n n e c t e d . W The p r o o f f o r E i s s i m i l a r . Connectedness o f e f f i c i e n t s e t i n m u l t i c r i t e r i a programming w i t h l i n e a r or concave o b j e c t i v e f u n c t i o n s has been r e p o r t e d by Yu and Z e l e n y [ 8 7 ] , B i t r a n and Magnanti [11,12] and Naccache [ 6 7 ] . .' '13 S e c t i o n 3- A l g o r i t h m f o r E v a l u a t i n g E f f i c i e n t F r o n t i e r We can now d e s c r i b e an a l g o r i t h m t o g e n e r a t e the e f f i c i e n t f r o n t i e r F ( E ) . The method i n v o l v e s o n l y one-d i m e n s i o n a l p a r a m e t r i c l i n e a r programming t e c h n i q u e s . G i v e n a b i c r i t e r i a l i n e a r f r a c t i o n a l program, we p r o c e e d as f o l l o w s : STEP 1. S o l v e max f ± { x ) subj e c t t o x e S . t o get q{, i = 1,2. T h i s i s e q u i v a l e n t t o s o l v i n g two l i n e a r programs. STEP 2. S o l v e ( P 2 q * ) t o get x 2 * . T h i s i s e q u i v a l e n t t o s o l v i n g a l i n e a r program. STEP 3- ( T h i s s t e p i s j u s t i f i e d by Lemma 2.7.) Apply 2 * row p a r a m e t r i c s on the l i n e a r program (Qa) w i t h a e [f^(x );q*] t o o b t a i n v 1 , . . . , v k and ( y 1 j Z 1 ) , . . . , ( y k , z k ) s a t i s f y i n g ( i ) ( y ^ z 1 ) s o l v e s ( Q v 1 ) , i = l , . . . , k ( i i ) f o r e v e r y v e lv^";v^" +''"], t h e r e e x i s t s (y,z) e [ ( y 1 , z 1 ) ; ( y 1 + 1 , z i + 1 ) ] such t h a t ( y , z ) s o l v e s (Qv), i = 1 , . . . , k - l . STEP 4. Set x 1 = a / z 1 ) y 1 , i = l , . . . , k k " 1 i i + i Then F( E ) = ( J F ( [ x j x 1 ]) 1=1 The forthcomming s i m p l e example i n f i n a n c e i l l u s t r a t e s t h e a l g o r i t h m . Example 2.15. A f i r m has e x i s t i n g cash r e s o u r c e s o f $0.1 and an e q u i t y base o f $0.1. A p r o j e c t , I I ^ 1, i s a v a i l a b l e f o r i n v e s t m e n t i n the f i r s t y e a r and y i e l d s 10% r e t u r n i n ye a r two a t which time a second p r o j e c t , 12 < 2, i s a v a i l a b l e w hich y i e l d s 20$ r e t u r n a f t e r a y e a r . Cash can be r e i n v e s t e d i n t he second y e a r o r p a i d as d i v i d e n d s (DIV 1) t o e x i s t i n g , s h a r e h o l d e r s . A l l cash r e m a i n i n g at t h e end o f the second year i s d i s t r i b u t e d as d i v i d e n d s (DIV 2 ) . New funds can be r a i s e d i n e i t h e r y e a r by the i s s u e o f s h a r e s ( S I and S2) at $1 each up t o a l i m i t o f $2. We w i s h t o "maximize" the d i v i d e n d per share f o r b o t h p e r i o d s . Thus we have ' M A X ' F = ( oTITsT > o . i + s i + S 2 ) w i t h t h e f o l l ™ i n s c o n s t r a i n t s : 11 < 0.1 + S I 0 ^ I I $ 1 12 + DIV1 ^ 1.1(11) + S2 DIV2 = 1.2 (12) 0 <c 12 < 2 0 ^ S2 ^ 2 0 < SI < 2 As i t i s always d e s i r a b l e t o have I I = 0.1 + SI and DIV1 at i t s upper bound, the problem can be s i m p l i f i e d t o ''MAX1 (0.H+1.1S1+S2-I2 1.212 ^ 0.1+S1 ' 0.1+S1+S2 4 5 s u b j e c t t o -1.1S1-S2+I2 ^ 0.11 SI ^ 0 . 9 S2 ^ 2 12 ^ 2 S I > 0, S2 £ 0, 12 > 0 The c o r r e s p o n d i n g (Qa) i s (Qa) max 1.2y 2 s u b j e c t t o - 1 . ly-^+y-p-y^-O. l i t < 0 y-L -0.9t < 0 y 3 - 2t 0 y 2 - 2t < o y± +y-+Q.lt = 1 l . l y 1 - y 2 + y 3 + 0 . i l t ^ a ( y 1 + 0 . 1 t ) a l l y l s y 2 , y 3 , t > o We see t h a t (Qa) i s a l i n e a r program w i t h the l a s t c o n s t r a i n t p a r a m e t r i z e d by a , which s p e c i f i e s the d i v i d e n d per share i n t h e f i r s t y e a r . The row p a r a m e t r i c t e c h n i q u e can be used t o s o l v e (Qa) and o b t a i n t h e s p e c i f i c v a l u e o f a, s t a r t i n g from a = 0 , where the o p t i m a l b a s i s o f (Qa) changes. We used t h e row p a r a m e t r i c f a c i l i t y o f the IBM LP package MPSX and o b t a i n e d the f o l l o w i n g : v 1 = 0, v 2 = 0 . 1 , v 3 = 0.1, v 4 = 1.1, v 5 = 21.1 46 / S l \ where z = 12 . Thus the e f f i c i e n t f r o n t i e r i s the image \S2/ 1 2 2 3 3 4 4 5 of [z ;z ] , tz ; z J ] , [ z J ; z ] and [z ; z J ] under F. The f e a s i b l e r e g i o n i s the r e c t a n g u l a r cube w i t h 2 1 3 4 one c o r n e r s l i c e d o f f a t A z A A as shown i n F i g u r e 8. 1 2 1 2 The e f f i c i e n t s e t E c o n s i s t s o f the pol y g o n s z z A A 1 2 3 5 3 4 4 5 and A z z A and t h e l i n e segments [z ,z ] and [z ; z " j . S2 new share income i n y e a r 2 z 4(0,2-,2). z 3 ( 0 , 2 , 1 . 9 ) ^ 3 ( 0 , 2 , 1 . 8 9 ) 2,1.) .? ?P • 9 ) > j 2 i n v e s t m e n t i n y e a r 2 A ^ O . 9,1,0) A (0.9,1.1,0) SI share income i n y e a r 1 F i g u r e 8 117 The s o l u t i o n z 1 has the maximum l e v e l of the * d i v i d e n d per share i n the second y e a r ( f 2 = 1.32) w i t h z e r o d i v i d e n d per share i n the f i r s t y e a r ( f ^ = 0 ) . The 2 1 s o l u t i o n A has the same performance. At z , t h e r e i s no share i s s u e d w i t h $0.1 and $0.11 i n v e s t e d i n the f i r s t and second p r o j e c t s r e s p e c t i v e l y ( I I = $0.1, 12- = $0.11). 2 At A , t h e r e i s a share income o f $0.9 from the f i r s t y e a r (S I = $0.9) w i t h I I = $1 and 12 = $1.1. A l l p o i n t s i n t 1 2 [z ;A ] have t h e same performance. O b v i o u s l y , t h e s o l u t i o n 2 A r e q u i r e s more c a p i t a l and i n v e s t m e n t s . T h i s suggests t h a t o t h e r c r i t e r i o n such as the net p r o f i t s h o u l d a l s o be i n c l u d e d . As a i n c r e a s e s from 0 t o 0.1, the c o r r e s p o n d -i n g s o l u t i o n s t r a v e r s e a l o n g [ z - ' - j z 2 ] . F o r each z e [ z x ; z 2 ] , t h e r e e x i s t s A e [A^;A X] such t h a t a l l p o i n t s i n [z;A] have t h e same performance F ( z ) . We observe t h a t a l l t h e s e s o l u t i o n s do not r e q u i r e new sh a r e s t o be i s s u e d i n the second year (S2 = $ 0 ) . T h i s i s due t o the f a c t t h a t f^-i s a l l o w e d t o go down t o t h e low v a l u e a i n [ 0 ; 0 . 1 ) . I n m a x i m i z i n g f 2 , S2 i s kept at S2 = 0 whenever i t i s f e a s i b l e . The v a l u e 0.1 i s a c r i t i c a l l e v e l o f f-^ • When a > 0.1, i t i s no l o n g e r p o s s i b l e t o a v o i d i s s u i n g new sha r e s i n the second y e a r . At a = 0.1, t h e s e t o f e f f i c i e n t s o l u t i o n s w i t h f = 0.1 i s the q u a d r i l a t e r a l A 1 z 2 z 3 A ^ Thus t h e r e a re many c o m b i n a t i o n s o f a c t i v i t i e s t h a t r e s u l t i n t h e performance f ^ = 0.1, f 2 = 1.2. SI v a r i e s from $0 at z 2 t o $0.9 a t A 1. S2 v a r i e s from $0 at z 2 t o $1.9 at 48 o 2 1 z . I I v a r i e s from $0.1 at z t o $1 at A . 12 v a r i e s from • 2 3 $0.1 a t z t o $2 a t z . As a i n c r e a s e s from 0.1 t o 1.1, the c o r r e s p o n d i n g s o l u t i o n s t r a v e r s e a l o n g [z ;z ] . There i s no m u l t i p l e s o l u t i o n s f o r a e ( 0 . 1 , 1 . 1 ] . A l l s o l u t i o n s • 3 4 i n [z ,z ] have SI = 0 and 12 = 2. The h i g h e r r e q u i r e -ment o f f ^ ( s p e c i f i e d by h i g h e r v a l u e o f a) f o r c e s the d i v i d e n d p a i d i n the f i r s t y e a r (DIV1) t o i n c r e a s e and t h a t r e s u l t s i n more cash needed t o be r a i s e d f o r the second y e a r by i n c r e a s i n g S2. As a i n c r e a s e s from 1.1 4 5 t o 21.1, t h e c o r r e s p o n d i n g s o l u t i o n s t r a v e r s e a l o n g [z ;z ] . 4 5 A l l s o l u t i o n s i n [z , z ] have maximum number o f shares i s s u e d i n the second y e a r (S2 = 2 ) . As a i n c r e a s e s , the payment of DIV1 c u t s i n t o the i n v e s t m e n t 12 and 12 d e c r e a s e s from A. 4 5 5 $2 a t z t o $o a t . The s o l u t i o n z a t t a i n s the maximum l e v e l o f the d i v i d e n d per share i n the f i r s t y e a r f x = 21.1- . The e f f i c i e n t f r o n t i e r i s shown i n F i g u r e 9. A = (0.1,1.2) and B = (1.1,1.143) are two p o i n t s on the e f f i c i e n t f r o n t i e r and the e f f i c i e n t f r o n t i e r between A and B i s g i v e n by f g = 21/(^ +19.9)-. The m i d p o i n t of A and B, 0.5(A+B) = (0.6,1.1715), i s not i n F ( S ) +'{x e R 2:x < 0}. Thus F(S) +'{x e R 2:x 4 0} i s not a convex s e t . 49 f 2 = d i v i d e n d per share y e a r 2 l i n e a r segment, max. share S2 i s s u e d 0.1 1.1 . f = d i v i d e n d per share year 1 F i g u r e 9 S e c t i o n 4. D i s c u s s i on Even though the b i c r i t e r i a l i n e a r f r a c t i o n a l programming problems a r e n o n l i n e a r and nonconvex, i t i s p o s s i b l e t o d e s c r i b e t h e e f f i c i e n t f r o n t i e r and hence the e f f i c i e n t s e t by a r a t h e r s i m p l e a l g o r i t h m which uses o n l y o n e - d i m e n s i o n a l p a r a m e t r i c l i n e a r programming t e c h n i q u e s . The e f f i c i e n t p o i n t s on each f a c e o f S can be d e s c r i b e d by a system o f l i n e a r c o n s t r a i n t s . Thus the e f f i c i e n t s e t i s a f i n i t e u n i o n o f l i n e a r l y 50 w c o n s t r a i n e d s e t s . I t i s a l s o shown t h a t E and E B are c l o s e d arid p a t h - c o n n e c t e d by f i n i t e l y many l i n e segments. The s i m p l i c i t y and s t r o n g r e s u l t s f o r the b i c r i t e r i a problems are due m a i n l y t o the r e s t r i c t i o n L = 2. I n view o f Example 1.6, Theorem 2.3 i s not v a l i d when L > 2. The a n a l y s i s i n S e c t i o n . 2 i s v a l i d o n l y when L = 2. As (MLFP) i s n o n l i n e a r and nonconvex i n g e n e r a l , more c o m p l i c a t e d a l g o r i t h m s and weaker r e s u l t s , are t o be ex p e c t e d when L > 2. 51 CHAPTER 3 One o f the c r u c i a l c h a r a c t e r i s t i c s o f any c o n s t r a i n e d o p t i m i z a t i o n problem i s the geometric shape of t h e s e t o f s o l u t i o n s . I n n o n l i n e a r programming, c o n v e x i t y i s the most i m p o r t a n t g e o m e t r i c p r o p e r t y which i s t h e b a s i s o f the whole convex programming. As shown in. Example 1.7, the s e t E o f a l l e f f i c i e n t s o l u t i o n s o f (MLFP) i s not n e c e s s a r i l y convex nor c l o s e d . I n f a c t , the same example shows t h a t the s e t E o f a l l weakly e f f i c i e n t s o l u t i o n s o f (MLFP) need not be convex. Another d e s i r a b l e g e o m e t r i c . p r o p e r t y o f a s o l u t i o n s e t i s the connectedness p r o p e r t y . T h i s p r o p e r t y i s e s s e n t i a l f o r many s o l u t i o n t e c h n i q u e s t h a t s e a r c h and e x p l o r e the e f f i c i e n t o r weakly e f f i c i e n t f r o n t i e r s [7,8,41,57,82]. I f E or E^ c o n s i s t s o f s e v e r a l d i s c o n n e c t e d i s o l a t e d components, then the c o r r e s p o n d i n g s o l u t i o n t e c h n i q u e s would have t o be more i n v o l v e d and c o m p l i c a t e d . In t h i s c h a p t e r , we i n v e s t i g a t e t h e connected p r o p e r t y o f E and E W . S e c t i o n 1. D i s c o n n e c t e d Examples For a r b i t r a r y m u l t i c r i t e r i a programming problems, W t h e s e t s E and E are not n e c e s s a r i l y connected. 52 F i g u r e 10 C o n s i d e r t h e problem: 'MAX' ( g l ( x ) , g 2 ( x ) ) s u b j e c t t o x e S 1 2 The unique maxima o f and g 2 o c c u r a t x = 3 and x = 1 1 2 r e s p e c t i v e l y . I t i s easy t o see t h a t x e E and x e.E. The p o i n t x = 2 i s not weakly e f f i c i e n t , b e i n g s t r o n g l y 2 dominated by x . S i n c e every connected subset o f S must be an i n t e r v a l , E and E^ are not connected. Even when t h e o b j e c t i v e f u n c t i o n s a re i n l i n e a r f r a c t i o n a l form, E and E W are not n e c e s s a r i l y connected when S i s unbounded. 53 Example 3-2. Let S = {x e R 2 : x 1 £ 2 , 0 < x g < 4} , •a f 1 ( x ) = x 1 / ( x 1 + x 2 - l ) and _ f 2 ( x ) = x 1 / ( x 1 ~ x 2 + 3 ) . I t f o l l o w s from Remark 0.12 t h a t V f ^ moves i n the c l o c k w i s e d i r e c t i o n around (0,1) and V f 2 moves i n the c o u n t e r - c l o c k w i s e d i r e c t i o n around ( 0 , 3 ) . Thus E = E W = {x e S:x x > 2, x 2 = 0 or 4} , which i s the u n i o n o f two p a r a l l e l l i n e s as shown i n F i g u r e 11. (2,4) x 2 Vf, (0,3) (0,1) Vf, (2,0) F i g u r e 11 x-Thus E =. E W i s not connected. S e c t i o n 2. Connectedness o f E and E W ,W When S i s bounded, E i s p a t h - c o n n e c t e d by a f i n i t e number o f l i n e segments. Theorem 3.3. E W i s p a t h - c o n n e c t e d by a f i n i t e number o f l i n e segments when S i s bounded. P r o o f . I t f o l l o w s from Theorem 2.14 t h a t E W i s p a t h -* connected by a f i n i t e number o f l i n e segments when L = 2. Assume t h a t t h i s i s t r u e when t h e r e a re l e s s t h a n L o b j e c t i v e f u n c t i o n s i n (MLFP). C o n s i d e r (MLFP) w i t h L o b j e c t i v e f u n c t i o n s . L e t x°, x 1 e E W . S i n c e [x°;x] C E W f o r any x e S s a t i s f y i n g F ( x ) > F(x°), we may assume t h a t x°, x 1 e E. I f P (x ° ) = F ( x 1 ) J t h e n [ x ^ x 1 ] C E. Suppose F(x°) / F ( x 1 ) , s a y , f T(x°) < f ^ x 1 ) . Then x° e E? ~ , 0, and u Li L , i ^ i . x ; 1 _ _W V i X £ E L f ( x 1 ) " R e e a 1 1 t n a t 6 L i s d e f i n e d by 6 T = i n f {a e R:E? C f r 1 ( a ) > W where E^ a i s g i v e n i n D e f i n i t i o n 1.12. By Theorem 1.17(b), t h e r e e x i s t s x e E^ fi such t h a t x e E j where J = {1,...,L-1} and t h u s x e E^f , Va < 6 T . L,a 5 — L Case ( i ) : f L( x°) < 6 L < ^ ( x 1 ) W Then x e E L f (x^) " ^ y i n d u c t i o n h y p o t h e s i s , 3 L t h e r e e x i s t a f i n i t e number o f l i n e segments i n E^ „ , r0«, ( C E^ ) L, I ^ v. x ; j o i n i n g x^1 and x. Let y"*" be an o p t i m a l s o l u t i o n o f max f - ^ x ) s u b j e c t t o x e S and f L ( x ) > f L ( x 1 ) . 1 W Then y e E T ^ / l x . By i n d u c t i o n h y p o t h e s i s , t h e r e e x i s t a f i n i t e number o f l i n e segments i n E^ „ , h ( C E W ) L j o i n i n g y 1 and x 1 . Let y be an o p t i m a l s o l u t i o n o f max f-^(x) s u b j e c t t o x e S and ^ L ( X ) > ' 6 L • Then 55 - W y e E T , . By i n d u c t i o n h y p o t h e s i s , t h e r e e x i s t a f i n i t e ' L * number o f l i n e segments i n ^ ( C E W ) j o i n i n g L ' 6 L x and y. L e t J ='{1,L} . Then i t f o l l o w s from the d e f i n i t i o n o f y 1 and y t h a t y 1 e E j and y e E j . Thus by Theorem 2.14 t h e r e i s a f i n i t e number o f l i n e segments i n E^ ( C E W ) j o i n i n g y 1 and y. C o n s e q u e n t l y , t h e r e e x i s t a f i n i t e number o f l i n e segments i n E W j o i n i n g x° and x 1 . Case ( i i ) : f L(x°) < f ^ x 1 ) ^ 5 L x e p / O v and x e „ , 1« . By i n d u c t i o n 5 L 5 L h y p o t h e s i s , t h e r e e x i s t a f i n i t e number o f l i n e segments W z _ W v 0 -i n E T „ / 0 N ( C E ) j o i n i n g x and x. A l s o , t h e r e e x i s t J _ I , i ^ \ x ; a f i n i t e number o f l i n e segments i n E f^ „ , L ( C E W ) J- i } I - j ^ k X ) j o i n i n g x 1 and x. C o n s e q u e n t l y , t h e r e e x i s t a f i n i t e W 0 1 number o f l i n e segments i n E j o i n i n g x and x . Case ( i i i ) : 6 L ^ f L U ° ) < f L ^ x l ) Let y^ be an o p t i m a l s o l u t i o n o f max f ^ ( x ) s u b j e c t t o x e S and ^ L ( x ) £ f^(x°). Then y° e. ^ ( x®)' 3 L By i n d u c t i o n h y p o t h e s i s t h e r e e x i s t a f i n i t e number o f l i n e segments i n E^ „ , 0v ( C E W ) j o i n i n g x° and y°. Let ' L y 1 be an o p t i m a l s o l u t i o n o f max f-^(x) s u b j e c t t o x e S and f L ( x . ) £ f L ( x 1 ) . Then y 1 e EJJ f ( x l ) - B y i n d u c t i o n y L h y p o t h e s i s , t h e r e e x i s t a f i n i t e . n u m b e r o f l i n e segments i n E^ _ , 1, ( C E W ) j o i n i n g x 1 and y 1 . Let J = {1,2}. 5 L 56 Then y w e and e EC. I t f o l l o w s from Theorem 2.14 t h a t t h e r e e x i s t a f i n i t e number o f l i n e segments i n E j ( C E W ) j o i n i n g and y^ ". C o n s e q u e n t l y , t h e r e e x i s t W 0 1 a f i n i t e number o f l i n e segments i n E j o i n i n g x and x . I n d u c t i o n completes the p r o o f . The next theorem suggests t h a t , i n the study o f the connected p r o p e r t y o f E, i t i s e q u i v a l e n t t o c o n s i d e r o n l y t h e e f f i c i e n t f r o n t i e r P ( E ) . Theorem 3-4. E i s connected i f and o n l y F(E) i s connected. P r o o f . ( N e c e s s i t y ) T h i s f o l l o w s from the c o n t i n u i t y o f F. ( S u f f i c i e n c y ) Suppose E = (E O D 1) U (E H D 2) where D± and D 2 are c l o s e d s u b s e t s o f S and D 1 O D 2 O E = Then D1 and D 2 are compact and F(E) = F(E f) D )^ 1 J F(E P ) D2) . 1 2 Suppose t h e r e e x i s t x e E H D-^ , x e E O such t h a t F ( x 1 ) • = F ( x 2 ) . Then [ x ^ x 2 ] C E and [ x ^ x 2 ] = • ( [ x 1 ^ 2 ] O DX) U ( [ x 1 ^ 2 ] P | D 2 ) . T h i s i s i m p o s s i b l e s i n c e [ x ^ x 2 ] i s connected. Hence we have F(E H C\ F(E O D -J = F u r t h e r m o r e , F(E O D ^ = F(E) P \ F(D^) , i = 1,2. Indeed, l e t u e F(E) O F ( D 1 ) . Then u = F ( x ) = F ( x ) f o r some x e E and x e D±. I t f o l l o w s from x e E and F ( x ) = F ( x ) t h a t x e E. Thus u = F ( x ) e F I E O ^ ) . C o n s e q u e n t l y , F(E) = (F (D 1 ) H F ( E ) ) l j (F(D-) P i F ( E ) ) . By the connectedness o f F ( E ) , we must have e i t h e r F(D ) 0 F(E) = 0 or F ( D 2 ) Pi F(E) = 0 . T h i s i m p l i e s t h a t E f \ ^ = 0 or E T l D j = T h e r e f o r e , E i s connected. S e c t i o n 3- D i s c u s s i o n W B o t h E and E may not be connected when the f e a s i b l e r e g i o n S o f (MLFP) i s unbounded. However, W when S i s compact, E i s p a t h - c o n n e c t e d by f i n i t e l y many l i n e segments. When L = 2 , E has the same p a t h -connected p r o p e r t y as s t a t e d i n Theorem 2.14. But f o r L > 2, we f a i l t o prove or d i s p r o v e t h a t E i s connected. I n c h a p t e r s 1 and 3, we have shown t h a t E^ has many W u s e f u l p r o p e r t i e s : E i s compact, p a t h - c o n n e c t e d and has i n t i m a t e r e l a t i o n s w i t h the weakly e f f i c i e n t s o l u t i o n s o f subproblems o f (MLFP). 5 8 CHAPTER 4 « Consider the general vector maximization problem (P) 'MAX" G(x) subject to x e S where G(x) = (g-^(x),. . . ,g^(x)) i s a f u n c t i o n from S to R^. I t i s w e l l known that the e f f i c i e n t f r o n t i e r G(E) can be generated by p a r a m e t r i c a l l y o p t i m i z i n g a weighted sum o,f the L o b j e c t i v e functions g^,...,g^ when G(E) + {u e R L:u i 0} i s convex [ 1 5 , 2 7 , 5 7 ] . But when (P) i s nonconvex, t h i s p a r a m e t r l z a t i o n scheme does not generate the whole e f f i c i e n t f r o n t i e r G(E) of (P). In view of Theorem 1 . 9 , the m u l t i -parametric program (TB) can be used to generate the weakly e f f i c i e n t f r o n t i e r G(E^) of (P) i n the nonconvex case. In t h i s chapter, we develop a par a m e t r i z a t i o n scheme to generate the properly e f f i c i e n t f r o n t i e r of (P) i n the nonconvex case. S e c t i o n 1. Proper E f f i c i e n c y Figure 12 d e p i c t s the c r i t e r i o n space of a b i c r i t e r i a problem. I t i s obvious that G(x) i s on the e f f i c i e n t f r o n t i e r and x e E. But at the point x, i t i s p o s s i b l e to obtain great gain i n the c r i t e r i o n g-^ with a r e l a t i v e l y very small l o s s i n the other c r i t e r i o n gg. Thus x i s not a d e s i r a b l e s o l u t i o n . To el i m i n a t e t h i s 59 type o f anomalous e f f i c i e n t s o l u t i o n , G e o f f r i o n [40] proposed t h e d e f i n i t i o n o f p r o p e r e f f i c i e n c y which was extended f u r t h e r by Borwein [14] , Benson [10] and Henig [ 4 2 ] . . . — — S i F i g u r e 12 D e f i n i t i o n 4.1. ( G e o f f r i o n ) A p o i n t x i s s a i d t o be a p r o p e r l y e f f i c i e n t s o l u t i o n o f (P) i f and o n l y i f x i s an e f f i c i e n t s o l u t i o n o f (P) and t h e r e e x i s t s a s c a l a r M > 0 such t h a t f o r each k and x e S s a t i s f y i n g S k ( x ) > g k ( x ) > w e have g k ( x ) - g k ( x ) < M(gj(x)-gj(x)) f o r some j such t h a t — P g^(x) > g . ( x ) . L e t E denote t h e s e t o f a l l p r o p e r l y p e f f i c i e n t s o l u t i o n s o f (P) and G(E ) denote the p r o p e r l y e f f i c i e n t f r o n t i e r o f ( P ) . I t i s o b v i o u s t h a t the p o i n t x, w i t h image G(x) d e p i c t e d i n F i g u r e 12, i s not p r o p e r l y e f f i c i e n t . The 60 e x i s t e n c e o f M i n D e f i n i t i o n 4.1 r u l e s out the p o s s i b i l i t y s o f h a v i n g an unbounded " m a r g i n a l r a t e o f s u b s t i t u t i o n " . Under a p p r o p r i a t e c o n v e x i t y a s s u m p t i o n s , G e o f f r i o n [40] has p r o v e d t h a t x i s a p r o p e r l y e f f i c i e n t s o l u t i o n o f (P) i f and o n l y i f x maximizes a p o s i t i v e l y w e i g h t e d sum o f g-j_3'-->gL over S. Thus the w e i g h t i n g method can be P used t o g e n e r a t e th e p r o p e r l y e f f i c i e n t f r o n t i e r G(E ) when (P) i s convex. Due t o the n o n c o n v e x i t y i n (MLFP),, we are i n t e r e s t e d i n g e n e r a t i n g the p r o p e r l y e f f i c i e n t p f r o n t i e r G(E ) f o r nonconvex ( P ) . S e c t i o n 2.. E x t e n s i o n o f G e n e r a l i z e d T c h e b y c h e f f Norm We now s e t up. t o d e f i n e an extended form, o f the g e n e r a l i z e d T c h e b y c h e f f norm. F o r any a e R, l e t 1^ ( o r s i m p l y I i f t h e r e i s no c o n f u s i o n about the d i m e n s i o n L) be the ( L x L ) -m a t r i x whose ( i , j ) - e n t r y i s g i v e n by ( I 1 i f i = j a i f i * j and l e t e , ...,e denote the column v e c t o r s o f I . u a a Theorem 4.2. The d e t e r m i n a n t o f the m a t r i x I L i s a d e t ( I ^ ) = ( i - a ) L " 1 ( l + ( L - l ) a ) (21) P r o o f . E v i d e n t l y , i t i s t r u e f o r L = 2. Suppose i t i s t r u e t h a t d e t ( I ^ _ 1 ) = ( l - a ) L ~ 2 ( l + ( L - 2 ) a ) (22) 61 Then d e t ( I L ) a 1-a a-1 0 0 a 1 a a = det ( a a . 1 a a a 1 ( l - a ) d e t ( I ^ ~ 1 ) + ( l - a ) d e t ( 0 a-1 a 1 a a a a 0 a 1 a = ( l - a ) J j ~ ± ( l + ( L - 2 ) a + a) = ( l - a ) L - 1 ( l + ( L - l ) a ) Thus i n d u c t i o n completes the p r o o f , 0 a a = ( l - a ) d e t ( I ^ - 1 ) . + ( l - a ) L " 2 ( a - a 2 ) = (1-a) ( l - a ) L ' 2 ( l + ( L - 2 ) a ) + ( l - a ) L ~ 2 ( a - a 2 ) by (22) ,L-1 Remark 4.3. I t f o l l o w s from (21) t h a t I i s s i n g u l a r o n l y when a = 1 or a = - 1 / ( L - 1 ) . I n t h i s c h a p t e r , a i s always chosen t o be a s m a l l n e g a t i v e number s a t i s f y i n g -1/2L < a < 0 and th u s I i s always n o n s i n g u l a r and d e t ( I ) > 0. 62 Theorem 4 . 4 . Let B be a ( L x L ) - m a t r i x g i v e n by (B) « d e t ( I L _ 1 ) / d e t ( I L ) i f I = j a a 1 J ' - a ( l - a ) L ~ 2 / d e t ( I ^ ) i f I / j Then B = ( I L ) _ 1 . a P r o o f . L e t A = B I L F o r i = j , we have d e t C l ^ - C A ) ^ . = d e t C l ^ - 1 ) - a 2 ( l - a ) L _ 2 ( L - l ) = ( l - a ) L _ 2 ( l + ( L - 2 ) a ) - a 2 (1-a) L ~ 2 (L-'l) = ( l - a ) L ~ 2 ( l + ( L - 2 ) a - ( L - l ) a 2 ) = ( l - a ) L - 2 ( l - a ) ( l + ( L - l ) a ) = d e t ( I L ) F o r i i- j j we have d e t ( I ^ , ) ( A ) i j = a d e t C l ^ " 1 ) - a 2 ( l - a ) L ~ 2 (L - 2) - a (1-a) = a ( l - a ) L _ 2 ( l + ( L - 2 ) a ) - a 2 ( l - a ) L _ 2 ( L - 2 ) - a ( l - a ) L " ~ 2 = 0 Hence B I ^ = I and B = ( I ^ ) " 1 . C o r o l l a r y 4 . 5 . A l l the e n t r i e s o f t h e i n v e r s e m a t r i x of I are p o s i t i v e , a ^ P r o o f . . I t f o l l o w s i m m e d i a t e l y from Theorem 4.2 and Theorem 4 . 4 . L - 2 6 3 Theorem 4.6. Suppose -1/2L < a < a* < 0, a^e 1,} ... + a.e 1. * 1 a' l a ' b l e a + + b L e a a n d a x > - - - J A L a r e n o n n e g a t i v e and not a l l z e r o . I f a < a ' / ( l + 2 I a ' ) s t h e n b > 0 V i = 1,...,L. P r o o f . I t f o l l o w s from a n e .+ 1 a' b ^ 1 + ... + b T e L t h a t l a L a L + a T e . = L a' L b L = 1 1 , a a' .-1. Thus i t s u f f i c e s t o show t h a t I I , > 0. a a' Fo r i = j , we have ( I a l l a ' ) i j d e t ( I a } = d e t C l ^ " 1 ) -. a ( l - a ) L _ 1 a ' ( L - l ) a = ( l - a ) L 2 ( l - a a * - L a + 2 a - L a a ' ) > 0 Fo r i / j , we have ( I - 1 I , ) . . d e t ( I L ) a a' I J . a = ( l - a ) L _ 2 a ' ( l - ( L - 2 ) a ) - a ( l - a ) L " 2 - a ( l - a ) L " 2 a ' ( L - 2 ) = ( l - a ) L _ 2 ( a ' - 2 ( L - 2 ) a a ' - a ) > 0 where t h e l a s t i n e q u a l i t y f o l l o w from a < a ' / ( l + 2 L a ' ) . T h i s completes the p r o o f . We can now d e f i n e the extended form o f the g e n e r a l i z e d T c h e b y c h e f f norm. 64 L • „ _ „ -, . , II ii ct D e f i n i t i o n 4.7- For a e R, 3 e and 6 > 0 , l e t || - „ e P be t h e r e a l - v a l u e d f u n c t i o n on R L ' d e f i n e d by ||y||« = max 3 j (I" 3^)., | (23) Theorem 4.8. I f -1/2L < a < 0 , then || . ||£ i s a norm on R P r o o f . I a i s n o n s i n g u l a r when -1/2L < a < 0 . I t " i s o b v i o u s from (23) t h a t ||y||j!j j> 0 f o r a l l y e R L . Si-rice I " y = 0 i s e q u i v a l e n t t o y = 0 , we have ||y||R = 0 i f " " " " ' " V = u i s pninus ipnt r.n v = n i*ro h a i r o n-ir i| 1 2 L and o n l y i f y = 0. F o r any t e R and y,y ,y e R , we have ||ty||° = max B j ( I ^ C t y ) ) J = max B j t d ^ y ) . ! 1<1<L = |t|-||yi« and y ' V l l g = niax B ± | ( I ^ y ^ y 2 ) . | = max ^ K r V ^ + t r V ) . ! ^ max B 1 | ( I f Y y ) J + max B,| ( I ~ y ), Ki.<L 1 a 1 l ^ i ^ L 1 a 1 = I y 1 ! ^ + | y 2 l l ^ , C o n s e q u e n t l y , || • ||" i s a norm on R 65 Remark 4.9. When a = 0, (12) and (23) are i d e n t i c a l and || . |^ i s i d e n t i c a l t o the g e n e r a l i z e d T c h e b y c h e f f norm || . | d e f i n e d by Bowman [ 1 5 ] . S e c t i o n 3. C h a r a c t e r i z a t i o n o f P r o p e r E f f i c i e n c y C o r r e s p o n d i n g t o the problem (TB), we d e f i n e (TBa) as f o l l o w s (TBa) Min || u* - G(x)|£ s u b j e c t t o x e S. The nex t theorem shows t h a t p a r a m e t e r i z a t i o n on B and' a gen-P e r a t e s t h e s e t E o f a l l p r o p e r l y e f f i c i e n t s o l u t i o n s o f ( P ) . Thus p r o p e r e f f i c i e n c y i s c h a r a c t e r i z e d by the norm || . \\®. Theorem 4.10. L e t x e S. Then x i s a p r o p e r l y e f f i c i e n t s o l u t i o n o f (P) i f and o n l y i f x s o l v e s (TBa) f o r some B > 0 and some a such t h a t -1/2L < a < 0 . P r o o f . ( N e c e s s i t y ) P Let x e E . Then t h e r e e x i s t s a s c a l a r M > 0 such t h a t f o r each k and x e S s a t i s f y i n g S k ( x ) > g^Cx) , we have g k ( x ) - g k ( x ) ^ M ( g j ( x ) - g j ( x ) ) f o r some j such t h a t g j ( x ) > g j ( x ) . L e t a be a n e g a t i v e number s u f f i c i e n t l y c l o s e t o 0 such t h a t M + 1 < ( l - a ) / ( - a L ) (24) . I t f o l l o w s from u* - G(x) > 0 and C o r o l l a r y 4.5 t h a t I _ 1 ( u * - G ( x ) ) > 0. a 66 L e t B, = 1/(1 1 ( u * - G ( x ) ) ) . , i = l , . . . , L . Then ( l / 3 1 ) e ^ t + ... + ( l / 3 L ) e ^ = u* - G(x) ( 2 5 ) and ||u*-G(x)|g = 1. We s h a l l show t h a t x I s an o p t i m a l s o l u t i o n o f (TBa). Suppose x e S such t h a t ||u*-G(x)||g < ||u«-,G(x)|g. L e t e ± = ( I ^ 1 ( u * - G ( x ) ) ) i , i = 1,...,L. Then 0 l e a + ••• + e L e a = u * - QW (26) and max U . = ||u*-G(x)||J < 1. Thus K i « L P 8 1 < 1/B 1 V i = 1,...,L ( 2 7 ) Prom ( 2 5 ) and ( 2 6 ) , we get ( l / 3 1 - 6 1 ) e j + ... + (l/6 L-9 L )eJ; = G(x) - G(x) ( 2 8 ) S i n c e x i s e f f i c i e n t and G(x) ? G ( x ) , g j ( x ) > S j ( x ) f o r some j . E q u a t i o n (28) i s e q u i v a l e n t t o ( i ; 1 ( G ( x ) - G ( x ) ) ) 1 = 1/B. - e i V I = 1,...,L ( 2 9 ) I f G(x) < G ( x ) , t h e n I ~ 1 ( G ( x ) - G ( x ) ) < 0 by C o r o l l a r y 4 . 5 . But t h i s c o n t r a d i c t s ( 2 7 ) and ( 2 9 ) . Hence g R ( x ) > g k ( x ) f o r some k. L e t q = (1/B 1-9' 1) + ... + ( l / B -0 ). From ( 2 8 ) , we have g ±(x-) - g ± ( x ) = aq + ( l - a ) ( l / B 1 - 0 1 ) VI = .1,...,L ( 3 0 ) Without l o s s o f g e n e r a l i t y , we may assume t h a t l/B-^-6^ = max '(1/B.-6.'). Then g, (x) > g, (x) and l/B-,-0, > q/L. Thus g x ( x ) - g x ( x ) a q + ( l - a ) ( l / B 1 - 6 1 ) g^(x) - g,(x) -aq - ( l - a ) d / B , - 6 j . 6 7 a q / ( l - o ) + ( 1 / 0 1 - 6 1 ) - a q / ( l - a ) - (1*/$ - 9 j ) > a q / ( l - a ) + q/L - a q / ( l - a ) = -1 + ( 1 - a ) / (-aL) > M where t h e l a s t i n e q u a l i t y f o l l o w s from ( 2 4 ) . T h i s I s a c o n t r a d i c t i o n . C o n s e q u e n t l y , x i s an o p t i m a l s o l u t i o n o f (TBa) ( S u f f i c i e n c y ) Let x be an o p t i m a l s o l u t i o n o f (TBa) f o r some B > 0 and -1/2L < a < 0. L e t x e S and Q± = ( r 1 ( u * - G ( x ) ) ) 1 , Q± = ( r 1 ( u * - G ( x ) ) ) 1 , i = -1,...,L. Then ( e i-§ 1)e 1 +.... + (9 L-§ L)e^ = G(x) - G(x) (3D Suppose G(x) £ G ( x ) . Then by C o r o l l a r y 4.5, I~ 1 ( G ( x ) - G ( x ) ) > 0 and by (3D, Q± - e\ > 0 V i = 1,... 5L. I t f o l l o w s t h a t |lu*-G(x)||^ = max B-6. < max p . e . = ||u*-G(x)||" T h i s i s 11 "P l,<is<L 1 1 l<i«L 1 1 " a c o n t r a d i c t i o n . Hence x i s an e f f i c i e n t s o l u t i o n o f ( P ) . Suppose g k ( x ) > g k ( x ) . L e t 9 - § = min (6.-§.) (32) J J l ^ i ^ L Then 6. - §. ^ 0 and g.(x) > g . ( x ) . We s h a l l show t h a t J J J J S k ( x ) " S k ( x ) ^ d A - a ) ) (gj(x)-gj(«)). S i n c e g k ( x ) " g k ( x ) ( ® k ~ § k ) + a ( v V + a t g. (x) - g j ( x ) _a(9 k-§. k) - (8j-§j) - at 68 1 ( a - l / a ) (8 .-6 .) - ( l - a ) t = + J J ; -a ~ a (\~®lP ~ ^ j ~ ^ j ) ~ a t where t = E ( 6 . - 0 . ) , i t s u f f i c e s t o show t h a t i * j , k 1 1 ( a - l / a ) ( 6 , - 6 , ) - ( l - a ) t < 0. Indeed -1/(L+1) < a < 0 J J ( l + a ) / ( - a ) > L-2 ( e.-6.)(l+a)/(-a) < (L-2) (6.-6 ) <: t .(by (32)) t) J J J => (1-a) (6^-6^ ) ( l + a ) / ( - a ) - ( l - a ) t < 0 => ( a - l / a ) (6 .-9.) - ( l - a ) t < 0. C o n s e q u e n t l y , x i s p r o p e r l y e f f i c i e n t w i t h M = l / ( - a ) . Remark 4.11. The parameter B r e p r e s e n t s the w e i g h t i n g o f the underachievements of t h e c r i t e r i a comparing t o the i d e a l p o i n t u*. Thus (3 r e f l e c t s t h e r e l a t i v e i mportance o f the c r i t e r i a . The parameter a i s r e l a t e d (M = -1/a) t o the u n i f o r m bound o f t h e m a r g i n a l s u b s t i t u t i o n s between c r i t e r i a as shown i n the p r o o f o f Theorem 4.10. By choos-i n g d i f f e r e n t 3 and a, d i f f e r e n t p r o p e r l y e f f i c i e n t s o l u t i o n s can be o b t a i n e d as o p t i m a l s o l u t i o n s o f (TBa). As B and a have s i m p l e i n t u i t i v e economic i n t e r p r e t a t i o n s , the d e c i s i o n maker can a d j u s t t h e s e parameters i n g u i d i n g t h e s e a r c h f o r the o p t i m a l s o l u t i o n o f max U ( F ( x ) ) . Hence an x e S i n t e r a c t i v e a l g o r i t h m i s i m m e d i a t e l y a v a i l a b l e u s i n g t h e p a r a m e t r i c problems (TBa). 69 S e c t i o n H. I s o q u a n t s o f ||u*-G(x)| a * I t i s i n t e r e s t i n g t o compare the i s o q u a n t s o f t h e a g g r e g a t e d o b j e c t i v e s ||u*-G(x)| f t , ||u.*-G(x)Jg and a 1 g 1 ( x ) + + a L g L ( x ) as d e p i c t e d i n F i g u r e 13. As noted are two extreme cases o f the g e n e r a l g o a l programming problem u s i n g the £ p m e t r i c when p = 0 0 and p = 1 [2] . The l i n e a r w e i g h t e d sum problems have th e i n h e r e n t i n s t a b i l i t y o f jumping between a d j a c e n t extreme p o i n t s o l u t i o n s [31 and do not probe i n t o nonconvex d i p s . The g e n e r a l i z e d T c h e b y c h e f f norm problems (TB) overcome the i n s t a b i l i t y but may g e n e r a t e i n e f f i c i e n t s o l u t i o n s . The i s o q u a n t s o f ||u*-G(x)jg are between those o f t h e two extreme cases as shown i n F i g u r e 13. Thus ||u*-G(x)|| R i n Remark 1 . 8 , u * - G ( x ) f R and a 1 g 1 ( x ) + .'. . ..+a Lg L(x) a,g (x)+a 0g„(x) = c o n s t a n t ||u*-G(x)|^= c o n s t a n t " ||u*-G(x) |" = c o n s t a n t g 1 F i g u r e 70 i s a b e t t e r way t o combine t h e c r i t e r i a g-,,...,gT • .J. Li We know from Theorem 4.10 t h a t t h e o p t i m a l s o l u t i o n s o f (TBa) are p r o p e r l y e f f i c i e n t . F u r t h e r m o r e , as the i n v e r s e m a t r i x o f I can be o b t a i n e d e x p l i c i t l y , the problem (TBa) can be s o l v e d e x p l i c i t l y . Thus i n the abscence o f c o n v e x i t y , ||u*-G(x)||g i s an a t t r a c t i v e way t o combine the c r i t e r i a g-j_,-..,g^ f o r s o l v i n g the problem ( P ) . S e c t i o n 5. P r o p e r E f f i c i e n c y and Cbne Domination F o r each a e R , l e t C a = {a ne 1+....+a Te L : * l a L a a £ 0, i = 1,...,L} . I t i s o b v i o u s t h a t C i s a convex cone g e n e r a t e d by e 1,...,e^ and thus has s i m p l e g e o m e t r i c s t r u c t u r e . The cone d o m i n a t i o n w i t h r e s p e c t to C a has been d e f i n e d by Yu [ 8 6 ] . 1 2 1 D e f i n i t i o n 4.12. F o r any x and x i n S, x i s s a i d t o be 2 ct 2 dominated by x w i t h r e s p e c t t o C i f and o n l y i f G(x ) 1 a - --G(x ) i s i n the cone C . I f x e S and x i s not dominated w i t h r e s p e c t t o C01 by any x e S such t h a t G(x) i- G(x) , t h e n x i s s a i d t o be e f f i c i e n t w i t h r e s p e c t t o C . We w i l l show t h a t p r o p e r e f f i c i e n c y i s e q u i v a l e n t 71 t o e f f i c i e n c y w i t h r e s p e c t t o C a. T h i s r e s u l t i s s i m i l a r « t o t h e c h a r a c t e r i z a t i o n g i v e n by Henig [ 4 2 ] . Theorem 4.13. L e t x e S. Then x i s an o p t i m a l s o l u t i o n o f (T3a) f o r some 3 > 0 and -1/2L < a < 0 i f and o n l y i f x i s an e f f i c i e n t s o l u t i o n o f (P) w i t h r e s p e c t t o C a f o r some -1/2L < a < 0. P r o o f . ( N e c e s s i t y ) L e t x be an o p t i m a l s o l u t i o n o f (T3a) f o r some 3 > 0 and -1/2L < a < 0. L e t a e R such t h a t a < a/(l+2La) < 0. Suppose t h e r e e x i s t s x c S such t h a t G(x) f G(x) and G(x)-G(x) e C a. Then t h e r e e x i s t n o n n e g a t i v e a ^ j . . . } a ^ , not a l l z e r o e s , such t h a t G (x)-G(x) = a 1 e J + . . . . + a L e ^ . (33) L e t u*-G(x) = 6 ne-+ +9 Te- and u*-G(x) = 1 L e i + l a L a l a + t T e t . Then L a G(x)-G(x) = (ei-'§1)e^+.... + ( e L - t L ) e ^ (34) I t f o l l o w s from (33), ( 3 4 ) , a < a/(l+2La) < 0 and Theorem 4.6 t h a t ^ - t ^ > 0> v 1 = 1,...,L. Thus 3 i 6 i > 3 1 ^ 1 , V i = 1,...,L and hence ||u*-G(x)|g > 3 ||u*-G(x)||p which i s a c o n t r a d i c t i o n . T h e r e f o r e x i s e f f i c i e n t w i t h r e s p e c t t o C a, ( S u f f i c i e n c y ) L e t x be an e f f i c i e n t s o l u t i o n o f (P) w i t h 72 r e s p e c t t o C a f o r some a, -1/2L < a < 0. Let 3 i = l / ( I ~ x ( u * - G ( x ) ) ) ± , I = 1,...,L. Then ||u*-G(x)||g = 1. Suppose x does not s o l v e (TBa) , then t h e r e e x i s t s £ e S and ||u*-G(ic)||g < 1. L e t u*-G(£) = 9 1e 1+ + 0 L e a • T h e n G ( 2 ) ^ G ( x ) , B± < 1/Bi , i = 1,...,L and G(5c)-G(x) = ( l / 3 1 - 6 ] L ) e J + . . . L ct . + ( l / 3 L - 6 L ) e a i s i n the cone C . T h i s i s a c o n t r a d i c t i o n . Hence x i s an o p t i m a l s o l u t i o n o f (TBa). C o r o l l a r y 4.14. L e t x e S. Then x i s a p r o p e r l y e f f i c i e n t s o l u t i o n o f (P) i f and o n l y i f x i s an e f f i c i e n t s o l u t i o n o f (P) w i t h r e s p e c t t o C a f o r some a, -1/2L < a < 0. P r o o f . F o l l o w s i m m e d i a t e l y from Theorem 4.10 and Theorem 4.13. S e c t i o n 6. Summary Pr o p e r e f f i c i e n c y i s c h a r a c t e r i z e d by an extended form o f the g e n e r a l i z e d T c h e b y c h e f f norm. T h i s p r o v i d e s a p a r a m e t r i z a t i o n scheme t o generate t h e p r o p e r l y e f f i c i e n t s o l u t i o n s o f nonconvex v e c t o r m a x i m i z a t i o n problem (P) by s o l v i n g (TBa) w i t h v a r y i n g parameters B and a. The i s o q u a n t s o f ||u*-G(x) I* l i e between tho s e o f || u*-G(x) ||g and a-^g-^(x) + . . .+a^g^(x) which a re the extreme cases o f &p m e t r i c w i t h p = °° and p = 1. I n g e n e r a l g o a l programming 73 w i t h t h e ly m e t r i c , i t i s not s a t i s f a c t o r y t o use • p = °° and p = 1. T h i s s u g g e s t s t h a t ||u*-G(x)IJg i s a b e t t e r way o f u n i f y i n g the c r i t e r i a g - ^ j - . - j g ^ and (TBa) i s a b e t t e r g o a l programming f o r m u l a t i o n whose s o l u t i o n s are always p r o p e r l y e f f i c i e n t . I t i s shown t h a t p r o p e r e f f i c i e n c y i s e q u i v a l e n t t o the e f f i c i e n c y w i t h r e s p e c t t o c e r t a i n cones w i t h s i m p l e g e o m e t r i c s t r u c t u r e . 74 CHAPTER 5 Given a m a t h e m a t i c a l programming problem, t h e r e i s a n o t h e r m a t h e m a t i c a l programming problem c l o s e l y a s s o c i a t e d w i t h i t . The p a i r i s known as the p r i m a l and the d u a l problems. I n l i n e a r and convex programming, t h e p r i m a l and the d u a l problems have e q u a l o p t i m a l v a l u e s . Hence i t i s p o s s i b l e t o s o l v e the p r i m a l problem i n d i r e c t l y by s o l v i n g the d u a l problem to o b t a i n the o p t i m a l v a l u e . A l s o the weak d u a l i t y r e l a t i o n s t a t e s t h a t any d u a l f e a s i b l e v a l u e i s g r e a t e r than o r e q u a l t o any p r i m a l f e a s i b l e v a l u e . Thus any d u a l f e a s i b l e v a l u e can be used as an upper bound of t h e o p t i m a l v a l u e o f t h e p r i m a l problem. F u r t h e r m o r e , th e d u a l v a r i a b l e s have the u s e f u l i n t e r p r e t a t i o n as the m a r g i n a l v a l u e s o f r e s o u r c e s i n t h e p r i m a l problem. T h i s a l l o w s m e a n i n g f u l s e n s i t i v i t y a n a l y s i s of the s t a b i l i t y o f o p t i m a l s o l u t i o n s i n r e a l economic and o r g a n i z a t i o n a l problems w i t h r e s p e c t t o v a r i o u s k i n d s o f p e r t u r b a t i o n s . D u a l i t y has p l a y e d an i m p o r t a n t r o l e i n m a t h e m a t i c a l programming. Many a u t h o r s [11,17,49,57,77] have s t u d i e d the d u a l i t y i n m u l t i c r i t e r i a l i n e a r and convex programming. I n t h i s c h a p t e r , we st u d y t h e d u a l i t y i n m u l t i c r i t e r i a programming and the d u a l v a r i a b l e s o f (MLFP). S e c t i o n 1. D u a l i t y i n M u l t i c r i t e r i a Programming There are t h r e e b a s i c approaches towards d u a l i t y 7 5 i n m u l t i c r i t e r i a programming. The f i r s t approach i s the » o r d i n a r y d u a l i t y based on the n o n l i n e a r program max U(G(x)) xeS a s s o c i a t e d w i t h t h e v e c t o r m a x i m i z a t i o n problem (P) 'MAX' G(x) s u b j e c t t o x e S = {x £ R n:Ax 4 b} .• The f u n c t i o n U u n i f i e s the c r i t e r i a g 1 , . . . J g L i n t o one o b j e c t i v e f u n c t i o n . T h i s approach i s o f course p e r f e c t p r o v i d e d the u t i l i t y f u n c t i o n U o f the DM i s known e x p l i c i t l y and has a p p r o p r i a t e c o n v e x i t y p r o p e r t y f o r u s e f u l d u a l i t y r e s u l t s . The s i m p l e s t form f o r U i n the f i r s t approach I s the l i n e a r w e i g h t e d sum a-j_6]_ + ... + a L g ^ which i s used t o s t u d y t h e d u a l i t y i n m u l t i p l e o b j e c t i v e l i n e a r programming [ 5 7 J and m u l t i p l e o b j e c t i v e convex programming [ 1 1 ] . S i n c e (MLFP) i s nonconvex as i l l u s t r a t e d i n Example 2 . 1 5 , t h e l i n e a r w e i g h t e d sum method can not be used. I n v i e w . o f the c h a r a c t e r i z a t i o n o f weak e f f i c i e n c y i n Chapter 1 , i t i s n a t u r a l t o use the g e n e r a l i z e d T c h e b y c h e f f norm || u* - F ( x ) || ^ as U. Even though t h e problem (Tg) : min || u* - F ( x ) || xeS * i s a n o n l i n e a r program w i t h o u t the r e g u l a r i t y p r o p e r t i e s such as d i f f e r e n t i a b i l i t y and c o n v e x i t y , the f u n c t i o n ||u* - F(x)||g. i s q u a s i c o n v e x and thus one may t r y t o use the d u a l i t y r e s u l t s d eveloped by Luenberger [ 6 4 ] , T h i s i s d e s c r i b e d i n S e c t i o n 2 . The second approach i s t o c o n s i d e r the d u a l v a r i a b l e s o f (P) as m a t r i c e s which have t h e i n t e r -p r e t a t i o n t h a t the j t h row i s the v e c t o r o f o r d i n a r y d u a l v a r i a b l e s a s s o c i a t e d w i t h the c o n s t r a i n t s w i t h r e s p e c t , t o 76 t h e j u u c r i t e r i o n f u n c t i o n g. . T h i s approach has been used i n t h e l i n e a r case by K o r n b l u t h [571 , Isermann [491 and the convex case by B r u m e l l e [171 - We w i l l use t h i s approach t o d e v e l o p the d u a l i t y t h e o r y f o r (MLFP). The t h i r d approach i s based upon the r e l a t i o n s h i p between any e f f i c i e n t s o l u t i o n x o f (P) and the c o n s t r a i n e d problem ( M 1 ( x ) ) d e f i n e d by (M 1(3c)) max f - ^ x ) s u b j e c t t o x e S; f ^ ( x ) > f ^ ( x ) , i = 2,...,L . The o r d i n a r y d u a l v a r i a b l e s o f (M-^x)) d e s c r i b e the t r a d e - o f f s between t h e c r i t e r i o n 1 and the c r i t e r i o n i f o r each i = 2,...,L at the e f f i c i e n t s o l u t i o n x. We s h a l l a p p l y t h i s o b s e r v a t i o n w i t h the second approach i n the sequ S e c t i o n 2. Quasiconvex D u a l i t y L e t x* be any weakly e f f i c i e n t s o l u t i o n o f (MLFP) I t f o l l o w s from Theorem 1.9 t h a t t h e r e e x i s t s 3 e R L such t h a t 3 > 0 and x* s o l v e s t h e problem (TB). (TB) min ||u* - F ( x ) ||R s u b j e c t t o x e S The o b j e c t i v e f u n c t i o n o f (TB) i s || u* - F ( x ) I = max 3 ( u * - f ( x ) ) The f u n c t i o n B ^ ( u * - f ^ ( x ) ) i s pseudoconvex s i n c e f ^ i s pseudoconcave f o r i = 1,....,L. Thus ||u* - F ( x ) | R i s 77 q u a s i c o n v e x b e i n g the maximum o f a f i n i t e number of q u a s i -convex f u n c t i o n s . Hence (T3) i s a q u a s i c o n v e x programming problem w i t h a c o n t i n u o u s q u a s i c o n v e x o b j e c t i v e f u n c t i o n . Under the assumption t h a t t h e r e e x i s t s x e S s a t i s f y i n g Ax < b, i t i s shown by Luenberger [64] t h a t t h e r e e x i s t s X° e R m, X° > 0 such t h a t x* i s a l s o an o p t i m a l s o l u t i o n o f t h e f o l l o w i n g problem (DA 0) min || u* - F ( x ) ||g s u b j e c t t o (A°) T(Ax-b) <, 0 F u r t h e r m o r e , we have || u* - F ( x * ) | L = max { o p t i m a l v a l u e o f (DX):X > 0} p As s t a t e d by L u e n b e r g e r , the d u a l v a r i a b l e X° i s determined by x* o n l y t o w i t h i n a p o s i t i v e s c a l a r and we may not have 0 T (X ) (,Ax*-b) = 0. Thus t h e s t a n d a r d s e n s i t i v i t y a n a l y s i s i n t e r p r e t a t i o n o f X° i s v a l i d o n l y i n a weaker form. S e c t i o n 3. Dual F o r m u l a t i o n The e f f i c i e n t s o l u t i o n s o f (MLFP) are c h a r a c t e r i z e d by the Kuhn-Tucker c o n d i t i o n s g i v e n i n Theorem 1.5. The f o l l o w i n g theorem s t a t e s the Kuhn-Tucker c o n d i t i o n s i n a d i f f e r e n t form w h i c h i s s u i t a b l e f o r the d u a l f o r m u l a t i o n . Theorem 5.1. Suppose g^ i s pseudoconvex f o r each i =1,..,L. Le t x* be an e f f i c i e n t s o l u t i o n o f ( P ) . Then t h e r e e x i s t w e R L and Q e R L x m such t h a t w > 0, Q > 0, Q(Ax*-b) = 0 78 T and w (VG(x*)-QA) = 0 P r o o f . ' Without l o s t o f g e n e r a l i t y , we may assume t h a t P^x* = b f o r i = 1,...,k and P^x* < b f o r i = k+1,.. F o r each j = 1,...,L , i t f o l l o w s from the p r o o f o f Theorem 1.5 t h a t t h e r e e x i s t a.. > 0 f o r i = l , . . . . k and w.. > f o r 1 < i ^ j 4 L such t h a t I a j i P i = V S , ( x * ) + E w,,Vg,(x*) 1=1 j iv & i L e t w. = 1 + E w.. f o r i = 1,...,L . Then w > 0 Let Q be the (Lxm)-matrix g i v e n by (35) Q = a l l / w l a 1 2 / w l a l k / w l 0. . . 0 a L l / w L a L 2 / w L a L k / w L 0. Then Q £ 0 and Q(Ax*-b) = 0 . I t f o l l o w s from (35) t h a t T w (VG(x*)-QA) = 0. T h i s completes the pr o o f , Remark 5.2. The c o e f f i c i e n t a., i n (35) can be r e g a r d e d t h T as the d u a l v a r i a b l e o f the i c o n s t r a i n t P.x < b. i n I i the f o l l o w i n g problem max g.(x) J s u b j e c t t o Ax 4 b , G(x) > G(x*) Thus Q s h o u l d be the "Dual v a r i a b l e s " o f " M a x i m i z i n g " G(x) 79 With r e s p e c t t o the m u l t i c r i t e r i a programming problem (P) as the p r i m a l problem, we d e f i n e i t s d u a l program as f o l l o w s : (D) 'MIN' G(y) - QAy + Qb s u b j e c t t o w T(VG(y)-QA) = 0 , w > 0 , Q > 0 where Ax < b d e f i n e s t h e f e a s i b l e r e g i o n o f ( P ) , Q e R L x m , w e and y e R n. T h i s d u a l f o r m u l a t i o n (D) i s a b l e n d o f t h e Wolfe d u a l [85] and the Kuhn-Tucker c o n d i t i o n s . , The c o n s t r a i n t s o f (D) r e p r e s e n t the Kuhn-Tucker c o n d i t i o n s as shown i n Theorem 5.1. The o b j e c t i v e f u n c t i o n o f (D) has the same form as t h a t o f the Wolfe d u a l . The m a t r i x Q has the i n t e r p r e t a t i o n t h a t i t s j row i s the v e c t o r o f d u a l v a r i a b l e s a s s o c i a t e d t o t h e c o n s t r a i n t s Ax 1 b w i t h r e s p e c t t o the j c r i t e r i o n f u n c t i o n g.. 3 S e c t i o n H. D u a l i t y I n t h i s s e c t i o n , we e s t a b l i s h some d u a l i t y r e l a t i o n s between (P) and (D) under the assumption t h a t g^ i s concave f o r i = 1,...,L . F i r s t , we have the weak d u a l i t y . Theorem 5-3- There e x i s t no p r i m a l f e a s i b l e x and d u a l f e a s i b l e (Q,w,y) such t h a t G(x) 2L G(y) - AQy + Qb P r o o f . S i n c e g^ i s concave, we have T g 1 ( x ) < g ± ( y ) + V g ± ( y ) (x-y) , i = 1,...,L (36) (37) 80 w TG(x) $ w TG(y) + w T V G ( y ) ( x - y ) -o = w TG(y) + w TQAx - w TQAy « w TG(y) - wTQb + w TQAy where the f i r s t i n e q u a l i t y f o l l o w s from w > 0 , the e q u a l i t y T f o l l o w s from w (VG(y)-QA) = 0 and t h e l a s t i n e q u a l i t y f o l l o w s from Q >. 0 and Ax < b. Hence we can not have ( 3 6 ) . Theorem 5 . 4 . I f x i s p r i m a l f e a s i b l e and (Q,w,y) i s d u a l f e a s i b l e such t h a t G(x) = G(y) - QAy + Qb, then x and ( Q j W j y ) a r e e f f i c i e n t s o l u t i o n s o f (P) and (D) r e s p e c t i v e l y . P r o o f . I f x i s not e f f i c i e n t , t h e n t h e r e e x i s t s x e S such t h a t G(x) < G ( x ) . But the n G(x) £ G(y) - QAy + Qb which c o n t r a d i c t s Theorem 5 - 3 . Hence x i s an e f f i c i e n t s o l u t i o n o f ( P ) . S i m i l a r l y , we can show t h a t (§,w,y) i s an e f f i c i e n t s o l u t i o n o f (D). S e c t i o n 5 . S p e c i a l Cases We s h a l l show t h a t (D) i s a n a t u r a l e x t e n s i o n o f t h e u s u a l d u a l i n l i n e a r programming, the Wolfe d u a l i n n o n l i n e a r programming and i s e s s e n t i a l l y e q u i v a l e n t t o the Isermann d u a l [491 i n m u l t i p l e o b j e c t i v e l i n e a r programming. (1) When L = 1, t h e c o n s t r a i n t w T(VG(y)-QA) = 0 becomes VG(y) = QA and (D) can be w r i t t e n as min G(y) - Q(Ay-b) s u b j e c t t o VG(y) = QA , Q 1 0 81 which i s e x a c t l y the Wolfe d u a l o f ( P ) . * T (2) When L = 1 and G(x) = c x, then the c o n s t r a i n t w T(VG(y)-QA) = 0. becomes c T = QA and G(y) - QAy = (c T - Q A ) y = 0 f o r a l l y e R n. Thus (D) i s the u s u a l l i n e a r d u a l o f ( P ) . (3) Suppose L > 1 and G(x) = Mx where M i s an ( L x n ) - m a t r i x . Then (P) becomes the f o l l o w i n g m u l t i p l e o b j e c t i v e l i n e a r program: (PL) 'MAX' Mx s u b j e c t t o Ax < b We have o b v i o u s l y VG(y) = M f o r a l l y e R n and (D) can be w r i t t e n a s : (DL) 'MIN' (M-QA)y + Qb s u b j e c t t o w T(M-QA) = 0 , w > 0 , Q > 0 . The d u a l o f (PL) d e f i n e d by Isermann [49] i s as f o l l o w s : ( D l ) 'MIN' Qb s u b j e c t t o w T(M-QA) = 0 , w > 0 , Q ^ 0. We w i l l show t h a t (DL) and ( D l ) are e s s e n t i a l l y e q u i v a l e n t . Isermann [49] has proved t h e next theorem. We p r o v i d e a d i f f e r e n t p r o o f h e r e . Theorem 5-5. L e t x be an e f f i c i e n t s o l u t i o n o f ( P L ) . Then t h e r e e x i s t s Q e R L x m such t h a t Q ^ 0, M = QA and QUx-b) = 0. P r o o f . L e t N be the ( ( n L + L ) x ( m L ) ) - m a t r i x g i v e n as f o l l o w s : N = T A 0 0 A T 0 0 0 0 0 0 0 0 T A x 0 0 0 0 0 0 A 0 0 0 0 T B 0 0 B" T where B = b-Ax. L e t 6 e R n L + L be the v e c t o r g i v e n by rp rp rji 0 *~ (c^,.**,c,0,«««,0) Then the system Nq = 9, q > 0. (38) i s e q u i v a l e n t t o rn rn m m m A Q = M , B Q = 0 and Q 2 0 . I t f o l l o w s from t h e theorem on p o s i t i v e s o l u t i o n s o f l i n e a r e q u a l i t i e s by Gale L38] t h a t t h e system (38) has no s o l u t i o n i f and o n l y i f t h e r e e x i s t z 1 e R n , i = 0,....,L, such t h a t fT -rp , (39) z > 0 , z T N 1 0 and z T 6 > 0 where z T = ((z 1) T,...,(z L) T,(z°) T). The system (39) can be r e w r i t t e n as 83 A z 1 < z? 0, i = 1,...,L and E c f z 1 > 0 (40) 1 1=1 ^ where I s the i - t h row v e c t o r o f M, i = 1,...,L. Then A z 1 < z°3 = z°_(b-Ax) 4 0 , 1 = 1,...,L. S i n c e S = {x e R n:Ax < b} i s bounded, i t f o l l o w s from A z 1 < 0 t h a t z 1 = 0 f o r i = 1,... ,L. Thus we have L T i E c,z = 0 and t h e r e i s no s o l u t i o n f o r t h e system ( 4 0 ) . i = l 1 Hence t h e system (38) has a s o l u t i o n . C o n s e q u e n t l y , t h e r e e x i s t s Q 2 0 such t h a t M = §A and §(Ax-b) = 0. C o r o l l a r y 5 . 6 . L e t x be an e f f i c i e n t s o l u t i o n o f ( P L ) , then t h e r e e x i s t s Q which i s an e f f i c i e n t s o l u t i o n o f (DL) and ( D I ) . P r o o f . By Theorem 5 -5 , t h e r e e x i s t s Q" £ R L x m such t h a t Q k 0 , M = QA and Q(Ax-b) = 0. O b v i o u s l y , Mx = ^b. Suppose Q i s not e f f i c i e n t . Then t h e r e e x i s t s Q w h i c h i s f e a s i b l e i n (DI) and Qb > Qb. Then. Mx > Qb = (M-QA)0+Qb. T h i s c o n t r a d i c t s Theorem 5 -3 . Hence Q i s an e f f i c i e n t s o l u t i o n o f ( D I ) . L e t w e R^ such t h a t w > 0. Then (§,w,x) i s f e a s i b l e i n (DL) and Mx = Mx-QAx+Qb s i n c e Q(Ax-b) = 0. I t f o l l o w s from Theorem 5-4 t h a t (Q,w,x) i s an e f f i c i e n t s o l u t i o n o f (DL). Remark 5-7- I n s t u d y i n g the e f f i c i e n t s o l u t i o n s o f ( P ) , 84 the d u a l programs (DL) and (DI) y i e l d the same d u a l v a r i a b l e m a t r i x Q. Hence we may r e g a r d (DL) as e s s e n t i a l l y e q u i v a l e n t t o t h e Isermann d u a l ( D I ) . S e c t i o n 6. D u a l i t y o f (MLFP). The d u a l program o f (MLFP) can be w r i t t e n as (DLFP) 'MIN 1 F(y)-QAy+Qb s u b j e c t t o w T(VF(y)-QA) = 0 w > 0 , Q > 0. S i n c e F may not be concave, we do not have the d u a l i t y r e l a t i o n between (MLFP) and (DLFP) d e s c r i b e d i n Theorem 5-3 and Theorem 5-4. The next theorem f o l l o w s i m m e d i a t e l y from Theorem 1.5 and Theorem 5 . 1 . Theorem 5 - 8 . I f x i s an e f f i c i e n t s o l u t i o n o f (MLFP), then t h e r e e x i s t s w > 0, Q ^ 0 such t h a t (Q,w 3x) i s f e a s i b l e i n (DLFP) w i t h t h e same o b j e c t i v e v a l u e ' F ( x ) . From Remark 5 . 2 , t h e c o e f f i c i e n t a., i n ( 3 5 ) t h T i s t h e d u a l v a r i a b l e o f the i c o n s t r a i n t P^x < b^ i n the f o l l o w i n g program; (M.(x)) max f . ( x ) j J s u b j e c t t o Ax < b f ± ( x ) £ f ± ( x ) , i / j . 85 Charnes and Cooper [21] have shown t h a t t h e program ( M j ( x ) ) i s e q u i v a l e n t t o the f o l l o w i n g l i n e a r program: — T ( Q j ( x ) ) max c^y+ r j Z T s u b j e c t t o d^y+ t j Z = 1 c ^ y + r 1 z >- f i ( x ) ( d ^ y + t 1 z ) , i * j Ay < zb , z ^ 0. T -K o r n b l u t h and S a l k i n [ 5 8 ] have shown t h a t a.. = X./(d.x+t.) where i s t h e o r d i n a r y d u a l v a r i a b l e c o r r e s p o n d i n g t o T -the c o n s t r a i n t P.y ^ zb. i n the l i n e a r program ( Q . ( x ) ) . Hence i t i s r e l a t i v e l y easy t o o b t a i n the m a t r i x o f d u a l v a r i a b l e s Q c o r r e s p o n d i n g t o any g i v e n e f f i c i e n t s o l u t i o n x o f (MLFP). T h i s c e r t a i n l y more th a n compensates f o r the l a c k o f d u a l i t y r e l a t i o n s between (MLFP) and (DLFP) which i s t o be e x p e c t e d due t o t h e n o n c o n v e x i t y i n (MLFP). • S e c t i o n 7. Summary A s p e c i a l d u a l i t y based on the g e n e r a l i z e d T c h e b y c h e f f norm problem (T3) and the d u a l i t y f o r q u a s i -convex programming by Luenberger was d i s c u s s e d . We a l s o i n t r o d u c e d a d u a l f o r m u l a t i o n which i s a n a t u r a l e x t e n s i o n o f the u s u a l d u a l i n l i n e a r programming, the Wolfe d u a l i n n o n l i n e a r programming and t h e Isermann d u a l i n m u l t i p l e o b j e c t i v e l i n e a r programming. D u a l i t y r e s u l t s are e s t a b l i s h e d under t h e assumption t h a t the c r i t e r i a are concave f u n c t i o n s . I t i s : shown t h a t the m a t r i x o f d u a l v a r i a b l e s f o r (MLFP) can be o b t a i n e d by s o l v i n g some L l i n e a r programs. 8 7 CHAPTER 6 In s o l v i n g (MLFP), we assume t h a t t h e r e i s a f u n c t i o n U, known as the d e c i s i o n maker's (DM) u t i l i t y f u n c t i o n , whose v a l u e U ( F ( x ) ) d i c t a t e s the p r e f e r e n c e o f F ( x ) . Except f o r c o n f l i c t s among the c r i t e r i a , t h e DM always wishes t o maximize each c r i t e r i o n . Thus i t i s s u f f i c i e n t t o c o n s i d e r o n l y t h e s e t E o f a l l e f f i c i e n t s o l u t i o n s . Without knowing U e x p l i c i t l y , (MLFP) becomes the problem o f g e n e r a t i n g the e f f i c i e n t s e t E and the e f f i c i e n t f r o n t i e r F ( E ) . I f F(E) can be p r e s e n t e d i n an e f f e c t i v e manner, th e n the DM can choose th e o p t i m a l s o l u t i o n from F(E) guided by h i s i m p l i c i t l y f e l t u t i l i t y f u n c t i o n U. T h i s i s t r u e f o r the b i c r i t e r i a (MLFP) where the e f f i c i e n t f r o n t i e r s can be p r e s e n t e d v e r y e f f e c t i v e l y p as p i e c e w i s e smooth cur v e s i n R . But when L > 2, t h e r e i s no e f f e c t i v e ways t o d e s c r i b e F(E) due t o the non-l i n e a r i t y o f (MLFP) and t h e c o m p l e x i t i e s o f h i g h e r d i m e n s i o n L. I f U i s known e x p l i c i t l y , t h e n (MLFP) becomes an o r d i n a r y s i n g l e o b j e c t i v e programming problem. Many t e c h n i q u e s f o r d e t e r m i n i n g U e x p l i c i t l y have been proposed [ 1 6 , 3 6 , 4 5 , 5 3 , 5 4 , 6 5 , 7 0 ] . U n f o r t u n a t e l y , t h e s e t e c h n i q u e s have the g r e a t d i s a d v a n t a g e o f p l a c i n g a r e l a t i v e l y l a r g e demand on the DM f o r i n f o r m a t i o n r e q u i r e m e n t s . A l s o , the DM has t o a r t i c u l a t e h i s p r e f e r e n c e s i n advance of the a n a l y s i s o f the problem. As i l l u s t r a t e d by Example 2 . 1 5 , 8 8 the image s e t F(S) may not be convex. Even i f U has n i c e p r o p e r t i e s such as m o n o t o n i c i t y and c o n c a v i t y , the problem o f m a x i m i z i n g U over the s e t F(S) i s not a convex program and t h u s i t i s not s o l v a b l e i n any r e l i a b l e f a s h i o n . On the o t h e r hand, even though t h e DM i s unable t o p r e c i s e l y a r t i c u l a t e h i s u t i l i t y f u n c t i o n U, i t i s r e a s o n a b l e t o assume t h a t he can r e l i a b l y choose the most p r e f e r r e d one from a f i n i t e , n o r m a l l y s h o r t , l i s t o f a l t e r n a t i v e s o l u t i o n s . An i n t e r a c t i v e a l g o r i t h m f o r s o l v i n g (MLFP) i s t o p r e s e n t t o t h e DM, i n a s e r i e s o f m e e t i n g s , a c h o i c e o f e f f i c i e n t a l t e r n a t i v e s which are i n some sense r e p r e s e n t a t i v e s o f F ( E ) . Over t h i s s e r i e s o f m e e t i n g s , the DM i s t o e x p l o r e h i s p r e f e r e n c e s among t h e p r e s e n t e d a l t e r n a t i v e s and choose a most p r e f e r r e d one. T h i s a l l o w s t h e DM t o e x p l o r e t h e e f f i c i e n t f r o n t i e r i n t e r a c t i v e l y . The main d i f f i c u l t y o f such an i n t e r a c t i v e a l g o r i t h m i s how t o generate a . s h o r t r e p r e s e n t a t i v e l i s t o f e f f i c i e n t p o i n t s t o be p r e s e n t e d t o t h e DM i n the i n t e r a c t i v e phase o f the a l g o r i t h m . D i f f e r e n t approaches have been proposed [7,8,31,32,41,67, 74,82,87,91,93]. We attempt t o use m i n i m a l amount o f non-l i n e a r programming t e c h n i q u e s i n s o l v i n g (MLFP). An i n t e r a c t i v e a l g o r i t h m i s proposed which uses m o s t l y l i n e a r programming t e c h n i q u e s . S e c t i o n 1. - Arrow S e a r c h A l g o r i t h m I n t h i s s e c t i o n , we d e s c r i b e a h e u r i s t i c i n t e r a c t i v e 89 a l g o r i t h m f o r s o l v i n g t h e m u l t i c r i t e r i a programming problem ( P ). (P) 'MAX' G(x) s u b j e c t t o x e S Weak e f f i c i e n c y i s used because i t i s more wo r k a b l e . Assume t h a t t h e i d e a l g o a l u*, d e f i n e d by e q u a t i o n ( 1 1 ) , has been o b t a i n e d . The purpose o f PHASE I i s t o o b t a i n a ' c e n t r a l ' p o i n t u° on the weakly e f f i c i e n t f r o n t i e r G ( E W ) . I n view o f Theorem 1.8, t h i s amounts t o s o l v i n g (TB) f o r some a p p r o p r i a t e c h o i c e o f B > 0. A simple-minded c h o i c e i s B = ( 1 , . . . , 1 ) . The p o i n t u° i s used as a s t a r t i n g p o i n t o f t h e a l g o r i t h m . I t i s o f c o u r s e , b e n e f i c i a l t o have u° c l o s e t o the o p t i m a l s o l u t i o n o f max U ( y ) . Suppose yeG(S) B > 0 has been chosen. PHASE I . S o l v e the problem (TB). (TB) min ||u*-G(x)|| p subj e c t t o x e S Let u° = G(x°) where x° s o l v e s (TB). Gi v e n a p o s i t i v e i n t e g e r m and a p o s i t i v e r e a l number D, we d e f i n e g k = kD/m , f o r k = 0,...,m and uk = u* - (g k+|u*-u°|)(u*-u°)/|u*-u°| , f o r k = 0,...,m. PHASE I I . F o r each c r i t e r i o n i = 1,...,L , we s o l v e ( M 1 u k ) max g ± ( x ) k s u b j e c t t o G(x) 2 u , x e S. 90 f o r each k = 0 s u c c e s s i v e l y u n t i l the maximand s t o p s i k i n c r e a s i n g . For each i and k, the o p t i m a l s o l u t i o n x o f (Mj,u^) i s weakly e f f i c i e n t . L e t u l k = G ( x l k ) . PHASE I I i , ends w i t h the s e t { u l k } C_ G ( E W ) . F i g u r e 14 i l l u s t r a t e s t h e geometry o f PHASE I I . The parameters m and 6 are used t o c o n t r o l t h e spread o f { u l k } over the f r o n t i e r G ( E W ) . Thus the r e p r e s e n t a t i v e n a t u r e o f { u l k } can be ensured. u 2m us lm -* S-F i g u r e 14 We can now d e s c r i b e the a l g o r i t h m , t o be c a l l e d the arrow s e a r c h a l g o r i t h m I n view of F i g u r e 14. Step 0. Determine u* and B > 0. Choose a p o s i t i v e r e a l number D and p o s i t i v e i n t e g e r s m and 0. 91 Step 1. Do PHASE I t o get u°. Go t o Step 2. Step 2. Do PHASE I I t o o b t a i n { u l k } , i = 1,...,L and k = 0,...,m. Go t o Step 4. Step 3. Do PHASE I I t o o b t a i n ' { u l k } , i = 1,...,L and k = l,...,m. Go t o Step 4. Step 4. P r e s e n t { u l k } t o the DM. L e t u p be the one most p r e f e r r e d by the DM. Set u° = u p . I f u p = u ^ m f o r some I , the n go t o Step 3-O t h e r w i s e , go t o Step 5. Step 5' I f i s a c c e p t a b l e as t h e " b e s t " p o i n t , t h e n STOP. O t h e r w i s e , s e t D = D/8 and go t o Step 3. Remark 6.1. The p o i n t s u l m , . . . , u L m are the o u t e r p o i n t s o f { u i k } . When u P = u i m f o r some i , t h i s i m p l i e s t h a t the o p t i m a l s o l u t i o n o f max U(y) may not l i e i n [um<u*]={u£RL yeG(S) :u m<u<u*}. In t h i s c a s e , D i s kept unchanged w h i l e the a l g o r i t h m goes back t o PHASE I I as g i v e n i n Step 4. T h i s makes sure t h a t no n a r r o w i n g o f the s e a r c h i n g p r o c e s s o c c u r s u n l e s s the o p t i m a l s o l u t i o n i s i n the s e t [u m<u*]. The parameter D i s the "depth" o f the s e a r c h i n g arrows i n t o the s G(S) as shown i n F i g u r e 14. Remark 6.2. The parameter m deter m i n e s the number o f g r i d p o i n t s u°,...,u m. I t f o l l o w s from Remark 6.1 t h a t m does not have t o be a b i g i n t e g e r . The s i z e o f m s h o u l d be i n v e r s e l y r e l a t e d t o the c o m p u t a t i o n a l r e q u i r e m e n t s f o r s o l v i n g the problems (M^u ). Remark 6 . 3 . S i n c e t h e p o i n t u° s e r v e s o n l y as a s t a r t i n g p o i n t o f t h e a l g o r i t h m , t h e r e I s no a b s o l u t e n e c e s s i t y f o r x° t o be an o p t i m a l s o l u t i o n o f (TB). Thus i n PHASE I , i t i s p r a c t i c a l j u s t t o s o l v e (TB) f o r an e - o p t i m a l s o l u t i o n x°. That i s , || u*-F(x°) ||^ i s w i t h i n e d i s t a n c e away from the o p t i m a l v a l u e o f (TB). T h i s eases the c o m p u t a t i o n a l r e q u i r e m e n t i n PHASE I . Remark 6 .4 . I n Step 4, the s e t { u l k } i s p r e s e n t e d t o the DM. An e f f e c t i v e way t o d i s p l a y the s e t { u l k } i s t o use the v a l u e p a t h s d i s p l a y d e v e l o p e d by S c h i l l i n g [79] • T h i s d i s p l a y mechanism i s i l l u s t r a t e d i n F i g u r e 15 w i t h L = 5• F i g u r e 15 The next theorem a l g o r i t h m i s convergent i n r e g u l a r i t y c o n d i t i o n s . shows t h a t b i c r i t e r i a t he arrow s e a r c h case under some m i l d 93 Theorem 6.5. Suppose G ( E W ) + {u e R L:u £ 0} i s convex and t h e u t i l i t y f u n c t i o n U i s concave. When L = 2, the arrow s e a r c h a l g o r i t h m converges t o an o p t i m a l s o l u t i o n o f max U(y) . yeG(S) P r o o f . L e t B denote t h e s e t o f o p t i m a l s o l u t i o n s o f max U(y) I t s u f f i c e s t o show t h a t [ u m <u*] Pi B ? 0 yeG(S) whenever the o u t e r p o i n t s u x m and u 2 m a r e not p r e f e r r e d i n the i n t e r a c t i v e phase. L e t { u 1 1 , u 2 1 , . . . , u l m , u 2 m } be o b t a i n e d from PHASE I I and 6 = max { U ( u l k ) : i = l , 2 ; l < k < m } . Suppose u l m and u 2 m are not p r e f e r r e d . Then U ( u l m ) < 6 and U(u ) < 6. Without l o s t o f g e n e r a l i t y , we may assume t h a t U ( u l x ) = 6. Assume t h a t [ u ^ u * ] Pi B = 0. Let y* e B Pi G ( E W ) . Then y* £ [u m<u*] i m p l i e s t h a t y* < u™ o r y* < u™ . L e t us assume t h a t y* < u™. Then t h e r e e x i s t s z e [ y * ; u x x ] such t h a t z-L = u™. I t f o l l o w s from p the c o n c a v i t y o f U t h a t Afi = {y e R :U(y) > 6} i s convex. E v i d e n t l y , [ y * , u l x ] C Afi and U(z) ^ <5. Now, [ y * , u x l ] d G ( E W ) + {u e R 2:u < 0} s i n c e y* e G ( E W ) , u 1 1 e G ( E W ) and G ( E W ) + {u e R 2:u < 0} i s convex. Thus z e G ( E W ) + {u e R 2:u <r 0} and z < u 2 m . But t h i s i m p l i e s t h a t U ( u 2 m ) > U(z) > 6. T h i s c o n t r a d i c t s the h y p o t h e s i s t h a t u 2 m was not p r e f e r r e d . Hence [um<_u*] C\ B f 0. 9 4 S e c t i o n 2. Arrow Sea r c h A l g o r i t h m f o r (MLFP) For s o l v i n g (MLFP), PHASE I and PHASE I I o f the arrow s e a r c h a l g o r i t h m have a p a r t i c u l a r l y s i m p l e and easy t o implement s t r u c t u r e . The problems ( M ± u k ) i n PHASE I I are e q u i v a l e n t t o l i n e a r programs and e - o p t i m a l s o l u t i o n o f (TB) can be o b t a i n e d by s o l v i n g a f i n i t e sequence o f l i n e a r programs. G i v e n B > 0, l e t 6 = ||u*-F(x)||R f o r some x e S. F o r any w e [ 0 , 6 ] , we d e f i n e the l i n e a r programming problem (QBw) by (QBw) min z s u b j e c t t o z ^ (u^-w/B^^) (d^x+t 1)-(cTx+r i) , V i x e S , z > 0. Let h R be t h e r e a l - v a l u e d f u n c t i o n on [0;6] d e f i n e d by h R(w) = o p t i m a l v a l u e o f (QBw). I t i s ob v i o u s t h a t h R i s n o n n e g a t i v e and n o n i n c r e a s i n g o v e r [0;<S] . Theorem 6.6. The o p t i m a l v a l u e o f (TB) i s g i v e n by i n f {w:w e [0;6] and h R(w) = 0} P r o o f . L e t x° be an o p t i m a l s o l u t i o n o f (TB) and v = ||u*-F(x°) I . Then, by the d e f i n i t i o n o f || . || , v > B 1(u*-f.(x 0)) , i = 1,...,L . Thus 0 > (u*-v /e i)(d^x°+t i.)-(c^x°+r 1)' , i = 1,...,L and h B ( v ) = 0 (41) 95 L e t w e [0; 6] such t h a t h 0(w) = 0. Then t h e r e P # e x i s t s x e S such t h a t 0 > ( u | - w / 6 1 ) ( d i X + t 1 ) - ( c ^ x + r 1 ) , i = 1,...,L (42) (42) can be r e w r i t t e n as w £ | u * - F ( x ) | ^ . Thus w £ v. Hence w v whenever h Q(w) = 0 (43) P I t f o l l o w s from ( 4 l ) and (43) t h a t v = i n f {w:w e [0,6] and h D(w) = 0}. P I t f o l l o w s from Theorem 6.6 t h a t we can approximate v by an u n i v a r i a t e s e a r c h o f h Q ( . ) over [ 0 : 6 ] . The P f o l l o w i n g b i n a r y s e a r c h p r o c e d u r e i s s u f f i c i e n t t o s o l v e f o r v w i t h e r r o r bounded by e > 0. I t r e q u i r e s o n l y the s o l u t i o n s o f a f i n i t e sequence o f l i n e a r programs (Qgw). B i n a r y S e a r c h P r o c e d u r e f o r e - o p t i m a l s o l u t i o n o f ( T g ) : Step 0. Set [L,H] = [0,6] Step 1. Set w = (L+H)/2 S o l v e (Qgw) t o get h D ( w ) . Go t o Step 2. P Step 2. I f h D(w) > 0, s e t L = w and go t o Step 1. P O t h e r w i s e , go t o Step 3. Step 3- I f H-L > e , s e t H = w and go t o Step 1. O t h e r w i s e , s e t v 1 = w and STOP. The v a l u e v 1 w i l l be w i t h i n e d i s t a n c e away from the a c t u a l o p t i m a l v a l u e v o f ( T g ) . Thus the o p t i m a l s o l u t i o n x o f (Qgv 1) o b t a i n e d i n Step 1 i s an e - o p t i m a l 96 s o l u t i o n o f (TB). i * I n PHASE I I , (M ±u ) has 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 u n c t i o n w i t h l i n e a r c o n s t r a i n t s . Charnes and Cooper [21] shown t h a t (M^u k) i s e q u i v a l e n t t o t h e f o l l o w i n g l i n e a r program: T , max c^y+r^z s u b j e c t t o Ay £ zb T k T c^y+ r j Z U j ( d ^ y + t j z ) , j = ±,...,L z > 0. Thus PHASE I I amounts t o s o l v i n g L l i n e a r programs to o b t a i n t h e s e t ' { u l k } . Remark 6.7> Weakly, e f f i c i e n t s o l u t i o n s can be o b t a i n e d by s o l v i n g the f o l l o w i n g problem (M 1u) max f 1 ( x ) s u b j e c t t o x e S and F ( x ) >_ u. where u e R L i s some p r e s p e c i f i e d f e a s i b l e g o a l . (M-]_u) i s s i m i l a r t o the problem ( M 1 u k ) . Thus f o r (MLFP), ( M ^ ) can be t r a n s f o r m e d i n t o a l i n e a r program. PHASE I may be r e p l a c e d by s o l v i n g the problem (M^u) t o o b t a i n a weakly e f f i c i e n t s o l u t i o n x^. Then u^ = F ( x ^ ) can ser v e as the s t a r t i n g p o i n t o f t h e arrow s e a r c h a l g o r i t h m . The main d i f f i c u l t y o f t h i s v e r s i o n l i e s i n the c h o i c e o f a f e a s i b l e g o a l u so t h a t u^ i s a good s t a r t i n g p o i n t . But t h e r e i s a g r e a t advantage o f s a v i n g the computations r e q u i r e d i n t he b i n a r y s e a r c h p r o c e d u r e f o r e - o p t i m a l s o l u t i o n o f (TB). 97 Example 6 . 8 . We i l l u s t r a t e t h e a p p l i c a t i o n o f the arrow s e a r c h a l g o r i t h m t o s o l v e the f o l l o w i n g b i c r i t e r i a problem: 'MAX' f - ^ x ) = x 1 / ( x 1 + x 2 + l ) , f 2 ( x ) = x 2 / ( x 1 + l ) s u b j e c t t o x 1 + x 2 < 1 , > 0 , x 2 > 0 The e f f i c i e n t f r o n t i e r o f t h i s problem i s the h y p e r b o l a ( f 1 + l ) ( f 2 + l ) = 2 i n t h e n o n n e g a t i v e quadrant. L e t u* = ( 0 . 6 , 1 . 2 ) and B = ' ( 1 / 0 . 6 , 1 / 1 . 2 ) . The PHASE I problem i s t h e n min z s u b j e c t t o z > ( 0 . 6 - 0 . 6 w ) ( x ^ + x 2 + l ) - x ^ z £ ( 1 . 2 - 1 . 2 w ) ( x 1 + l ) - x 2 1 * 1 + x 2 , x 1 > 0 , x 2 > 0 , z 0. We t a k e 6 = ||u*-F( ( 0 . 5 , 0 . 5 ) ) | | R = 0 . 7 2 . The b i n a r y s e a r c h p r o c e d u r e s e a r c h e d t h r o u g h the f o l l o w i n g i n t e r v a l s : [ 0 , 0 . 7 2 ] , [ 0 . 3 6 , 0 . 7 2 ] , [ 0 . 5 4 , 0 . 7 2 ] , [ 0 . 6 3 , 0 . 7 2 ] , [ 0 . 6 3 , 0 . 6 7 1 . PHASE I i s ended w i t h v 1 = 0 . 6 7 and x° = ( 0 . 3 9 , 0 . 5 6 ) . Thus u° = P(x°) = ( 0 . 2 , 0 . 4 ) i s t h e s t a r t i n g p o i n t g o i n g i n t o PHASE I I . We choose m = 2 , D = 0 . 4 4 7 2 and 6 = 2 . ' Then u 1 = ( 0 . 1 , 0 . 2 ) and u 2 = ( 0 , 0 ) . From PHASE I I , we o b t a i n t h e f o l l o w i n g p o i n t s as shown i n F i g u r e 16. u 1 0 = ( 0 . 2 1 4 3 , 0 . 4 ) , u 1 1 = ( 0 . 3 3 3 3 , 0 . 2 ) , u 1 2 = ( 0 . 5 , 0 ) u 2 0 = ( 0 . 2 , 0 . 4 2 8 6 ) , u 2 1 = ( 0 . 1 , 0 . 6 6 6 7 ) , u 2 2 = ( 0 , 1 ) 98 ( 0 . 6 , 1 . 2 ) (0 ,1) F i g u r e 16 We n o t i c e t h a t the p o i n t s u°, u 1 0 and u 2 0 are c l o s e t o each o t h e r s i n c e u° i s c l o s e t o the e f f i c i e n t f r o n t i e r . These p o i n t s a re p r e s e n t e d t o the d e c i s i o n maker who (we s.uppose) chooses u° = ( 0 . 1 , 0 . 6 6 6 7 ) as the most p r e f e r r e d p o i n t . PHAES I I w i l l be r e p e a t e d but t h i s t i me w i t h D = 0 .2236. 99 The depth o f s e a r c h D has been s h o r t e n e d t o n a r r o w - i n t o the o p t i m a l s o l u t i o n . We get u 1 = (0 .2353 ,0 .5851) and u 2 = ( - 0 . 0 5 3 , 0 . 5 0 3 6 ) . From PHASE I I , we o b t a i n e d the f o l l o w i n g p o i n t s as shown i n F i g u r e 17. F i g u r e 17 1 0 0 u° = ( 0 . 1 , 0 . 6 6 6 7 ) , u 1 1 = ( 0 .1309 ,0 .5851), u 1 2 = (0 .1651 ,0 .5036) u 2 1 = (0 .2353 ,0.91) , u 2 2 = (0 ,1) We n o t i c e t h a t from t h e second i t e r a t i o n onwards, the most P p r e f e r r e d p o i n t u at the end o f the p r e v i o u s i t e r a t i o n w i l l be i n the l i s t { u l k } and D = |u m-u°|. S e c t i o n 3. Summary The arrow s e a r c h a l g o r i t h m has been i n t r o d u c e d f o r s o l v i n g g e n e r a l m u l t i c r i t e r i a programming problems. I t i s a h e u r i s t i c i n t e r a c t i v e a l g o r i t h m . The d e c i s i o n maker merely s e l e c t s h i s most p r e f e r r e d s o l u t i o n amongst the p r e s e n t e d a l t e r n a t i v e s . P o i n t s g e n e r a t e d a re e v e n l y d i s t r i b u t e d over t h e d e s i r e d neighbourhood o f the weakly e f f i c i e n t f r o n t i e r . There i s no g e n e r a l c onvergent p r o p e r t y . However, t h e a l g o r i t h m i s convergent i n t h e b i c r i t e r i a case w i t h a p p r o p r i a t e c o n v e x i t y c o n d i t i o n s . When a p p l i e d f o r s o l v i n g (MLFP), t h e a l g o r i t h m makes use o f o n l y the l i n e a r programming t e c h n i q u e s . 101 CHAPTER 7 • » S e c t i o n 1 . C o n c l u s i o n We have s t u d i e d the v a r i o u s a s p e c t s o f the m u l t i -c r i t e r i a l i n e a r f r a c t i o n a l programming problem (MLFP). The c h a r a c t e r i z a t i o n s o f e f f i c i e n t , weakly e f f i c i e n t and p r o p e r l y e f f i c i e n t s o l u t i o n s are d e r i v e d . The Kuhn-Tucker c o n d i t i o n s are n e c e s s a r y and s u f f i c i e n t f o r the e f f i c i e n t s o l u t i o n s o f (MLFP). The weakly ( r e s p e c t i v e l y , p r o p e r l y ) e f f i c i e n t s o l u t i o n s are c h a r a c t e r i z e d by the g e n e r a l i z e d T c h e b y c h e f f norm || • fl^ ( r e s p e c t i v e l y , the extended form o f the g e n e r a l i z e d T c h e b y c h e f f norm II * II g )• l n t n e b i c r i t e r i a c a s e , t h e s e t E o f a l l . e f f i c i e n t s o l u t i o n s o f (MLFP) i s p a t h - , connected by a f i n i t e number o f l i n e segments and the e f f i c i e n t f r o n t i e r F ( E) can be e v a l u a t e d by u s i n g the row p a r a m e t r i c technique i n l i n e a r programming. The weakly ( r e s p e c t i v e l y , p r o p e r l y ) e f f i c i e n t s o l u t i o n s can be g e n e r a t e d by s o l v i n g the g e n e r a l i z e d T c h e b y c h e f f norm problems (TB) ( r e s p e c t i v e l y , the extended g e n e r a l i z e d T c h e b y c h e f f norm problems (TBa)) w i t h d i f f e r e n t p a r a m e t e r s . The s e t E o f a l l weakly e f f i c i e n t s o l u t i o n s o f (MLFP) i s compact and p a t h - c o n n e c t e d by f i n i t e l y many l i n e segments. A d u a l problem i s f o r m u l a t e d which i s a b l e n d o f the Wolfe f o r m u l a t i o n and the Kuhn-Tucker c o n d i t i o n s . T h i s d u a l i s e q u i v a l e n t t o the Wolfe d u a l i n n o n l i n e a r programming and the Isermann d u a l i n m u l t i p l e o b j e c t i v e l i n e a r programming. 102 D u a l i t y r e l a t i o n s are e s t a b l i s h e d under the assumption t h a t the c r i t e r i a a re concave f u n c t i o n s . The m a t r i x o f t h e d u a l v a r i a b l e s o f (MLFP) can be e v a l u a t e d e a s i l y by s o l v i n g L l i n e a r programs. A s p e c i a l d u a l i t y based on the g e n e r a l i z e d T c h e b y c h e f f norm problem (T$) and the d u a l i t y f o r q u a s i c o n v e x . programming by Luenberger was a l s o d i s c u s s e d . A h e u r i s t i c arrow s e a r c h a l g o r i t h m i s d e v e l o p e d f o r s o l v i n g g e n e r a l m u l t i c r i t e r i a programming problems i n t e r -a c t i v e l y . The d e c i s i o n maker merely s e l e c t s h i s most p r e f e r r e d one amongst the p r e s e n t e d a l t e r n a t i v e s . . The s o l u t i o n s g e n e r a t e d a r e 'evenly' d i s t r i b u t e d over t h e d e s i r e d neighbourhood of t h e weakly e f f i c i e n t f r o n t i e r . The a l g o r i t h m i s convergent i n t h e b i c r i t e r i a case w i t h a p p r o p r i a t e c o n v e x i t y c o n d i t i o n s . When a p p l i e d t o s o l v e (MLFP), th e arrow s e a r c h a l g o r i t h m uses o n l y t h e l i n e a r programming t e c h n i q u e s . S e c t i o n 2. C o n j e c t u r e s and F u r t h e r R esearch I n i n v e s t i g a t i n g t h e g l o b a l p r o p e r t i e s o f the s o l u t i o n s e t s o f (MLFP), the v e r y f i r s t t h i n g t o be c o n f i r m e d s h o u l d have been the connected p r o p e r t y o f the s e t E o f a l l the e f f i c i e n t s o l u t i o n s . However, we were unable t o prove or d i s p r o v e t h a t E i s connected. By u s i n g the s i m p l e geometry i n Remark 0.12, one can show t h a t E i s connected when n = 2 . Together w i t h Theorem 2.14, we see t h a t i f t h e r e i s any example w i t h d i s c o n n e c t e d E, i t must have n > 2 and L > 2 . 103 I n m u l t i c r i t e r i a l i n e a r programming, Isermann [511 proved t h a t t h e r e i s no d i f f e r e n c e between the e f f i c i e n c y and t h e p r o p e r e f f i c i e n c y . We c o n j e c t u r e t h a t the same r e s u l t i s v a l i d f o r (MLFP). I f an e f f i c i e n t s o l u t i o n x i s not p r o p e r l y e f f i c i e n t , t h e n t h e r e i s a sequence { x n : n = l , 2 , . . . } C S such t h a t l i m x n = x , f k U n ) >' f k U ) a n d f o r every j such n-»-oo t h a t f (it) > f j ( x n ) , we have l i m f k ( x n ) ~ f k ( x ) ( 4 4 ) ,. — , —n, — = OO ' F o r t h e f i x e d x, s i n c e g i ( x ) = f 1 ( x ) - ^ f 1 ( x ) , f o r i = j , k , ar e 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 , we may assume t h a t f k ( * ) = f . ( x ) = .0. Then ( 4 4 ) becomes J l l m ^ k ' > k > ^ ^ n + t . 1 > " n ^ - ( c J x n + r j ) ( d T x n + t k ) s ffi+V l i m ck x R + rk d k x + t k -c.x - r j S i n c e = f j ( x ) . = 0 , c' kx + r k = cTx+r^ = 0. Thus c Tx n+r c T(x n-x) c V l i m ck x + rk l i m V x x ) l i m ck y _ „ n-H. _ c T x n _ r j " ^ T ^ n , - ) " n - _ c T y n " ( 4 5 ) n x^_x n Where y = : ; — , V n . We may assume t h a t y i s convergent i n - 1 |x -x| and l e t y = l i m y 1 1 . ( 4 5 ) i m p l i e s t h a t .cTy = 0. I f c^y > 0, then y TVf k(x) = y T ( c . k - f k ( x ) d k ) / ( d k x + t k ) > 0 . T h i s , i m p l i e s 104 t h a t x i s dominated by x+ey f o r some s m a l l e > 0.. T h i s r p _ » c o n t r a d i c t s x e E. Thus c^y = 0 . When S C R 2 , we have y n = ( c o s 0 n , s i n 0 n ) • , l i m 6 n = 9" and y = ( c o s 9 , s i n 9 ) . I t f o l l o w s from (45) n->oo and t h e L ' H o s p i t a l R u l e t h a t l i m c k i c o ^ n + c k 2 s i n 0 n Ti-*-°° n n -Cj-^cos© - C j 2 s l n 6 = l i m - c k i B l n 9 n / + c k 2 c o s 0 n ( 4 6 ) n*°° c , n s i n 0 n - c , 0 c o s 9 n J l J2 The numerators and t h e denominators i n (46) must v a n i s h at 9 T- T-s i n c e c u y = c.y = 0. That i s , c k l c o s 0 + c k 2 s i n 9 = 0 - c ^ s i n ^ + c k 2 c o s 9 = 0 -c.,cos9 - c . ? s i n 9 = 0 c . , s i n 9 - c j 2 c o s 9 = 0 t h a t c k l = C k 2 = c .., J l J 2 j k are c o n s t a n t f u n c t i o n s . T h i s i s i m p o s s i b l e . Hence x must be p r o p e r l y e f f i c i e n t . Thus the c o n j e c t u r e i s t r u e i n the case o f two v a r i a b l e s . The arrow s e a r c h a l g o r i t h m i s convergent i n the b i c r i t e r i a case under some a p p r o p r i a t e c o n v e x i t y c o n d i t i o n s . Remark 6.1 and Remark 6.2 seem t o suggest t h a t the parameter D can be used a p p r o p r i a t e l y t o ensure t h a t the a l g o r i t h m i s moving towards the o p t i m a l s o l u t i o n i n ' t h e s o l u t i o n p r o c e s s . Thus one e x p e c t s t h e a l g o r i t h m t o have good performance 10'j even though the convergence o f the a l g o r i t h m • h a s not been e s t a b l i s h e d . T h i s can be done e m p i r i c a l l y by a p p l y i n g the arrow s e a r c h a l g o r i t h m t o s o l v e t h o s e p r a c t i c a l problems i n [3,41,62,69] where o t h e r s o l u t i o n methods have been used. F u r t h e r r e s e a r c h i n t h i s d i r e c t i o n would be u s e f u l f o r i m p r o v i n g the s o l u t i o n t e c h n i q u e s o f (MLFP). 106 BIBLIOGRAPHY [1] Adulbhan, P. and Tabucanon, M. T. B i c r i t ' e r l o n L i n e a r Programmingj Computers and O p e r a t i o n s R e s e a r c h , V o l . 4, 1977, P P . 147 - 1 5 3 . [2] A s h t o n , D. J . and A t k i n s , D. R. C r i t e r i a S t r u c t u r e s f o r Goal Programming, i n v i t e d paper t o TIMS/ORSA j o i n t c o n f e r e n c e , New Yor k , May, 1978. [31 A s h t o n , D. J . and A t k i n s , D. R. M u l t i c r i t e r i a Programming f o r F i n a n c i a l P l a n n i n g , J o u r n a l o f O p e r a t i o n a l Research S o c i e t y , V o l . 3 0 ( 3 ) , 1979, pp. 259 - 2 7 0 . [4] A p o s t o l , T. M. M a t h e m a t i c a l A n a l y s i s , Addison-Wesley, 1963. [5] Baum, S. and C a r l s o n , R. C. M u l t i - g o a l O p t i m i z a t i o n In M a n a g e r i a l S c i e n c e , OMEGA, V o l . 2 ( 5 ) , 1974, pp. 607-623. [6] B a z a r a a , M. S. and S h e t t y , C. M. N o n l i n e a r Programming, Theory and A l g o r i t h m s , John W i l e y & Sons, New York, 1979-[7] Benayoun, R. and Tergny, J . M a t h e m a t i c a l Programming w i t h M u l t i - o b j e c t i v e F u n c t i o n s : A S o l u t i o n by P.O.P., METRA, V o l . 9 ( 2 ) , 1970, pp. 279-299-[8] Benayoun, R., M o n t g o l f i e r , J . , Tergny, J . and L a r i t c h e v , 0. L i n e a r Programming w i t h M u l t i p l e O b j e c t i v e F u n c t i o n s : Step Method (STEM), M a t h e m a t i c a l Programming, V o l . 1 ( 3 ) , -1971, P P . 366-375. [9] Benson, H. P. V e c t o r M a x i m i z a t i o n w i t h Two O b j e c t i v e F u n c t i o n s , J o u r n a l o f O p t i m i z a t i o n Theory and A p p l i c a t i o n s , V o l . 28, 1979, P P . 253-257. [10] Benson, H. P. An Improved D e f i n i t i o n o f P r o p e r E f f i c i e n c y f o r V e c t o r M a z i m i z a t i o n w i t h Respect t o Cones, t o appear i n J o u r n a l o f O p t i m i z a t i o n Theory and A p p l i c a t i o n s . [11] B i t r a n , G.-.R. and M a g n a n t i , T. L. O p t i m i z a t i o n w i t h R e f e r e n c e s D e f i n e d by Cones, paper p r e s e n t e d a t the NATO Advanced Study I n s t i t u t e i n G e n e r a l i z e d O p t i m i z a t i o n and Economics, Vancouver, B r i t i s h C olumbia, 1980. [12] B i t r a n , G. R. and M a g n a n t i , T. L. The S t r u c t u r e o f Admissable P o i n t s w i t h Respect t o Cone Dominance, J o u r n a l o f O p t i m i z a t i o n Theory and A p p l i c a t i o n s , V o l . 29 ,1979, pp. 573-614. [13] B i t r a n , G. R. and Novaes, A. G. L i n e a r Programming w i t h a F r a c t i o n a l O b j e c t i v e F u n c t i o n , O p e r a t i o n s R e s e a r c h , V o l . 21, 1973, P P . 22-29. 107 [14] B o r w e i n , J . P r o p e r E f f i c i e n t P o i n t s f o r M a x i m i z a t i o n s w i t h Respect t o Cones, SIAM J o u r n a l p f C o n t r o l and O p t i m i z a t i o n , V o l . 15, 1977, pp. 57-63-[15] Bowman ' J r . , V. J . On the R e l a t i o n s h i p o f the T c h e b y c h e f f Norm and the E f f i c i e n t F r o n t i e r o f M u l t i p l e - C r i t e r i a O b j e c t i v e s , i n T h i r i e z , H. and Z i o n t s , S., eds. M u l t i p l e C r i t e r i a D e c i s i o n Making, S p r i n g e r - V e r l a y , 1976, pp. 76-85. [16] B r i s k i n , L. E. A Method o f U n i f y i n g M u l t i p l e O b j e c t i v e F u n c t i o n s , Management S c i e n c e , V o l . 12 (10) , 1966, pp. B406-B416. [17] B r u m e l l e , S. D u a l i t y f o r M u l t i p l e O b j e c t i v e Convex Programs, U n i v e r s i t y o f B r i t i s h C olumbia, Working paper No. 6 6 8 , J u l y 1979. [18] Chadha, S. S. A Dual F r a c t i o n a l Program, ZAMM, V o l . 51, 1971, pp. 560-61. [19] Chambers, D. Programming the A l l o c a t i o n o f Funds S u b j e c t t o R e s t r i c t i o n s on Reported R e s u l t s , O p e r a t i o n a l Research Q u a r t e r l y , V o l . 10, 1967, pp. 407-431. [20] Charnes, A. and Cooper, W. W. Management Models and I n d u s t r i a l A p p l i c a t i o n s o f L i n e a r Programming, W i l e y , New Y o r k , 1961. [21] Charnes, A. and Cooper, W. W. Programming w i t h L i n e a r F r a c t i o n a l F u n c t i o n a l s , N a v a l Research L o g i s t i c s Q u a r t e r l y , V o l . 19, 1962, pp. 181-186. [22] Charnes, A. and Cooper, W. W. Goal Programming and M u l t i p l e O b j e c t i v e O p t i m i z a t i o n s , European J o u r n a l o f O p e r a t i o n a l R e s e a r c h , V o l . 1, 1977, pp. 39 - 5 4 . [ 2 3 ] Charnes, A., Granot,.D. and Gra n o t , F. A Note on E x p l i c i t S o l u t i o n i n L i n e a r F r a c t i o n a l Programming, N a v a l Research L o g i s t i c s Q u a r t e r l y , V o l . 23 ( l ) , 1976, pp. 161-167. [24] Choo, E. U. and A t k i n s , D. R. An I n t e r a c t i v e A l g o r i t h m f o r M u l t i c r i t e r i a Programming, Computer and O p e r a t i o n s R e s e a r c h , V o l . 7, 1980, pp. 81-87• [25] Cochrane, J . L. and Z e l e n y , M., eds. M u l t i p l e C r i t e r i a D e c i s i o n Making, 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 , Columbia, S. C., 1973. [ 2 6 ] Cohon, J . L. " A p p l i c a t i o n s o f M u l t i p l e O b j e c t i v e s t o Water Resources Problems, i n Z e l e n y , M., ed. M u l t i p l e C r i t e r i a D e c i s i o n Making: Kyoto 1975, S p r i n g e r - V e r l a y , 1975, pp. 252-267. 108 [27] Cohon, J . L. M u l t i o b j e c t i v e Programming and P l a n n i n g , Academic P r e s s , New Yor k , 1978. t [28] Cohon, J . L., Church, R.'L. and Sheer, D. P. G e n e r a t i n g M u l t i o b j e c t i v e T r a d e - O f f s : An A l g o r i t h m f o r B i c r i t e r i o n P r oblems, Water Resources R e s e a r c h , V o l . 15 ( 5 ) , 1979 3 pp. 1001-1010. [291 C y e r t , R. M. and March, J . G. A B e h a v i o r a l Theory o f t h e F i r m , P r e n t i c e - H a l l , New J e r s e y , 1963. [30] D i n k e l b a c h , W. On N o n l i n e a r F r a c t i o n a l Programming, Management S c i e n c e , V o l . 13 ( 7 ) , ' 1 9 6 7 , PP- 492-498. [ 3 H Dyer, J . S. I n t e r a c t i v e Goal Programming, Management S c i e n c e , V o l . 19 ( 1 ) , 1972, pp. 62 - 7 0 . • [32] Dyer, J . S. A T i m e - s h a r i n g Computer Program f o r the S o l u t i o n o f th e M u l t i p l e C r i t e r i a Problems, Management S c i e n c e , V o l . 19 (12 ) , 1973, pp. 1379-1383. [33] E c k e r , J . G., Hegner, N. S. and Kouada, I . A. G e n e r a t i n g A l l Maximal E f f i c i e n t Faces f o r M u l t i p l e O b j e c t i v e L i n e a r Programs, D i s c u s s i o n Paper 7617, CORE, U n i v e r s i t e C a t h o l i q u e de L o u v a i n , H e v e r l e e , B e l g i u m , 1976. [ 3 4 ] E i l o n , S. Goals and C o n s t r a i n t s i n D e c i s i o n - M a k i n g , O p e r a t i o n a l R e s e a r c h Q u a r t e r l y , V o l . 23 ( 1 ) , 1972, pp. 3-15. [35] E v a n s , J . P. and Steuer,- R. E. A R e v i s e d Simplex Method f o r L i n e a r M u l t i p l e O b j e c t i v e Programs, M a t h e m a t i c a l Programming, V o l . 5 ( 1 ) , 1973, pp. 54-72. [36] F i s h b u r n , P. C. and Keeney, R. L. Seven Independence Concepts and Continuous M u l t i a t t r i b u t e U t i l i t y F u n c t i o n s , J o u r n a l o f M a t h e m a t i c a l P s y c h o l o g y , V o l . 11 , 1974, pp. 294-327. [37] G a l , T. A G e n e r a l Method f o r D e t e r m i n i n g the Set of A l l E f f i c i e n t S o l u t i o n s t o a L i n e a r Vectormaximum Problem, European J o u r n a l o f O p e r a t i o n a l R e s e a r c h , V o l . 1 , 1977, pp. 307-322. [38] G a l e , D. The Theory o f L i n e a r Economic Models, M c G r a w - H i l l , New York, i 9 6 0 . [39] G e o f f r i o n , A. M. S o l v i n g B i c r i t e r i o n M a t h e m a t i c a l Programs, O p e r a t i o n s R e s e a r c h , V o l . 15, 1967, pp. 39-54. [-40] G e o f f r i o n , A. M. Pr o p e r E f f i c i e n c y and the Theory o f , V e c t o r M a x i m i z a t i o n , J o u r n a l o f M a t h e m a t i c a l A n a l y s i s and A p p l i c a t i o n s , V o l . 22, 1968, pp. 618-630. 109 [ 4 1 ] G e o f f r i o n , A. M., Dyer, J . S. and F e l n b e r g , A. An I n t e r a c t i v e Approach f o r M u l t i c r l t e r l o n O p t i m i z a t i o n , w i t h an A p p l i c a t i o n t o the O p e r a t i o n *of an Academic Department, Management S c i e n c e , V o l . 19 ( 4 ) , 1 9 7 2 , P P . 3 5 7 - 3 6 8 . [ 4 2 ] H e n i g , M. I . P r o p e r E f f i c i e n c y w i t h Respect t o Cones, J o u r n a l o f O p t i m i z a t i o n Theory and A p p l i c a t i o n s , f o r t h c o m i n g . [ 4 3 ] Haimes, Y. Y. and H a l l , W. A. M u l t i o b j e c t i v e s i n Water Resources Systems A n a l y s i s : The S u r r o g a t e Worth T r a d e - o f f Method, Water Resources R e s e a r c h , V o l . 10 ( 4 ) , 1 9 7 4 , pp. 6 1 5 - 6 2 4 . [ 4 4 ] H o c k i n g , R. R. and Shepard, R. L. P a r a m e t r i c S o l u t i o n o f a C l a s s o f Nonconvex Programs, O p e r a t i o n s Research,. .Vol. 1 9 , 1971, PP- 1742 - 1 7 4 7 . [ 4 5 ] Huber, G. P. Methods f o r Q u a n t i f y i n g S u b j e c t i v e P r o b a b i l i t i e s and M u l t i a t t r i b u t e U t i l i t i e s , D e c i s i o n S c i e n c e s , V o l . 5, 1 9 7 4 , pp. 4 3 0 - 4 5 8 . [ 4 6 ] I b a r a k i , T. S o l v i n g M a t h e m a t i c a l Programming Problems w i t h F r a c t i o n a l O b j e c t i v e F u n c t i o n s , paper p r e s e n t e d a t NATO Advanced Study I n s t i t u t e , Vancouver, B r i t i s h C o lumbia, August, 1 9 8 0 . [47] I j i r i , Y. Management Goals and A c c o u n t i n g f o r C o n t r o l , N o r t h - H o l l a n d , Amsterdam, 1965. [ 4 8 ] I n t r i l i g a t o r , M. D. M a t h e m a t i c a l O p t i m i z a t i o n and Economic Theory, P r e n t i c e - H a l l , New J e r s e y , 1 9 7 1 . [491 Isermann, H. On Some R e l a t i o n s Between a Dual P a i r o f M u l t i p l e O b j e c t i v e L i n e a r Programs, Z e i t s c h r i f t f u r O p e r a t i o n s R e s e a r c h , V o l . 2 2 , 1 9 7 8 , pp. 3 3 - 4 1 . [50] Isermann, H. The Enumeration o f the Set o f A l l E f f i c i e n t S o l u t i o n s f o r a L i n e a r M u l t i p l e O b j e c t i v e Program, O p e r a t i o n a l R esearch Q u a r t e r l y , V o l 28 ( 3 ) , 1 9 7 7 , pp. 7.11-725. [ 5 1 ] Isermann, H. Pro p e r E f f i c i e n c y and the L i n e a r V e c t o r Maximum Problem, O p e r a t i o n s R e s e a r c h , V o l . 2 2 , 1 9 7 4 , pp. 1 8 9-191. [ 5 2 ] Johnson, E. S t u d i e s i n M u l t i o b j e c t i v e D e c i s i o n Models, S t u d e n t l i t t e r a t u r , Lund, 1 9 6 8 . [531 K e e l i n , T. W. A P r o t o c o l and Procedure f o r A s s e s s i n g M u l t i - a t t r i b u t e P r e f e r e n c e F u n c t i o n s , Ph.D. D i s s e r t a t i o n , Department o f En g i n e e r i n g - E c o n o m i c Systems, S t a n f o r d U n i v e r s i t y , 1 9 7 6 . no [54] Keeney, R. L. and R a i f f a , H. D e c i s i o n s w i t h M u l t i p l e o b j e c t i v e s : P r e f e r e n c e s and V a l u e T r a d e - o f f s , W i l e y , New Yo r k , 1976. •1551 K l a h r , C. N. M u l t i p l e O b j e c t i v e s i n M a t h e m a t i c a l Programming, O p e r a t i o n s R e s e a r c h , V o l . 6, 1958, pp. 849-855-[56] K o r n b l u t h , J.. S. H. A Survey o f Goal Programming, OMEGA, V o l . 1 (2 ) , 1973, PP. 193-205. [573 K o r n b l u t h , J . S. H. D u a l i t y , I n d i f f e r e n c e and S e n s i t i v i t y A n a l y s i s i n M u l t i p l e O b j e c t i v e L i n e a r Programming, O p e r a t i o n a l R esearch Q u a r t e r l y , V o l . 2 5 ( ( 4 ) , 1974, pp. 599-614. 158] K o r n b l u t h , J . S. H. and S a l k i n , G. R. A Note on the Economic I n t e r p r e t a t i o n o f the Dual V a r i a b l e s i n L i n e a r F r a c t i o n a l Programming, ZAMM, V o l . 52, 1972, pp. 175-178. [591 K o r n b l u t h , J . S. H. and S t e u e r , R. E. Goal Programming w i t h L i n e a r F r a c t i o n a l C r i t e r i a , Working Paper No. BA54, C o l l e g e o f B u s i n e s s and Economics, U n i v e r s i t y o f Kentucky, L e x i n g t o n , K e n t u c k y , F e b r u a r y , 1980. [60] Kuhn, H. W. and T u c k e r , A. W. N o n l i n e a r Programming, i n Neyman, J . , ed. P r o c e e d i n g o f the Second B e r k e l e y Symposium on M a t h e m a t i c a l 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 , 1951, PP• 481-492. [61] Lawrence, K. D. and Lawrence, S. M. A M u l t i p l e O b j e c t i v e L i n e a r Programming Model f o r C o r p o r a t e F i n a n c i a l Management, An I n v i t e d Paper P r e s e n t e d at ORSA/TIMS J o i n t N a t i o n a l C o n f e r e n c e , A t l a n t a , 1977. [62] Lee, S. M. and C l a y t o n , E. R. A Goal Programming Model f o r Academic Resource A l l o c a t i o n , Management S c i e n c e , V o l . 18 ( 8 ) , 1972, pp. B395-B408. [63] L i n , W. T. A Survey o f Goal Programming A p p l i c a t i o n s , A Paper P r e s e n t e d a t ORSA/TIMS J o i n t N a t i o n a l M e e t i n g , Los A n g e l e s , 1978. [64] L u e n b erger, D. G. Quasi-Convex Programming, SIAM J o u r n a l o f A p p l i e d M a t h e m a t i c s , V o l . 16 ( 5 ) , 1968, pp. 109,0-1095. [651 MacCrimmon, K. R. and S i u , J . K. Making T r a d e - o f f s , D e c i s i o n S c i e n c e s , V o l . 5 ( 4 ) , 1974, pp. 680-704. [66] Mond, B. and Craven, B. D. A Note on M a t h e m a t i c a l Programming w i t h F r a c t i o n a l O b j e c t i v e F u n c t i o n s , N a v a l Research L o g i s t i c s Q u a r t e r l y , V o l . 20, 1973, pp. 577 -581. [67] M o r r i s , P. A. and Oren, S. S. M u l t i - O b j e c t i v e D e c i s i o n Making by S e q u e n t i a l Resource A l l o c a t i o n , Xerox A n a l y s i s R e search Group T e c h h l c a l ' R e p o r t , " 1 9 7 8 . I l l [68] Naccache, P. H. Connectedness o f the Set o f Nondominated Outcomes i n M u l t i c r i t e r i a O p t i m i z a t i o n , J o u r n a l o f O p t i m i z a t i o n Theory and A p p l i c a t i o n s * , V o l . 25, 1978, pp. 459-467. [69] O k e l l o , R. M., Kaufman, S. and Z i o n t s , S. A M u l t i p l e O b j e c t i v e D e c i s i o n P r o c e d u r e f o r U n i v e r s i t y A d m i s s i o n P l a n n i n g , A Paper P r e s e n t e d a t ORSA/TIMS J o i n t N a t i o n a l C o n f e r e n c e , San F r a n c i s c o , 1977-[ 7 0 ] Oppenheimer, K. R. A Proxy Approach t o M u l t i - a t t r i b u t e D e c i s i o n Making, Management S c i e n c e , V o l . 24 ( 6 ) , 1978, pp. 675-6b9. [71] O s t e r y o u n g , J . S. M u l t i p l e Goals i n the C a p i t a l B u d g e t i n g D e c i s i o n , i n Cochrane, J., L. and Z e l e n y , M. , eds. M u l t i p l e C r i t e r i a D e c i s i o n Making, 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 , C olumbia, S. C , 1973, pp. 447-457-[72] P h i l i p , J . A l g o r i t h m s f o r the V e c t o r M a x i m i z a t i o n Problem, M a t h e m a t i c a l Programming, V o l . 2, 1972, pp. 207-229. [ 7 3 1 P o n s t e i n , J . Seven K i n d s o f C o n v e x i t y , SIAM Review, V o l . 9 ( 1 ) , 1967, PP. 115-119-[ 7 4 ] P r i c e , W. L., An I n t e r a c t i v e O b j e c t i v e F u n c t i o n G e n e r a t o r f o r Goal Programming, i n T h i r i e z , H. and Z i o n t s , S., eds. M u l t i p l e C r i t e r i a D e c i s i o n Making, S p r i n g e r - V e r l a g , 1976, pp. 1 4 7 . [75] P r i c e , W. L. and P i s d o r , W. G. The A p p l i c a t i o n o f Goal Programming t o Manpower P l a n n i n g , INFOR, V o l . 10 ( 3 ) , 1972, pp. 221-231. [76] R'ddder, W. A G e n e r a l i z e d S a d d l e p o i n t Theory, I t ' s A p p l i c a t i o n t o D u a l i t y Theory f o r L i n e a r V e c t o r Optimum Problems, European J o u r n a l o f O p e r a t i o n a l R e s e a r c h , V o l . 1, 1977, PP. 55-59. [ 7 7 ] Roy, B. Problems and Methods w i t h M u l t i p l e O b j e c t i v e F u n c t i o n s , M a t h e m a t i c a l Programming, V o l . 1 , 1971, pp. 239-266. [78] S c h a i b l e S. F r a c t i o n a l Programming: A p p l i c a t i o n s and A l g o r i t h m s , t o appear i n European J o u r n a l o f O p e r a t i o n a l R e s e a r c h . [ 7 9 1 S c h i l l i n g , D. M u l t i o b j e c t i v e and Temporal C o n s i d e r a t i o n s i n P u b l i c F a c i l i t y L o c a t i o n , Ph.D. T h e s i s , 1976, Department of Geography and E n v i r o n m e n t a l E n g i n e e r i n g , John Hopkins U n i v e r s i t y , B a l t i m o r e , M a r y l a n d . [ 8 0 ] Sharma, J . C. and Swarup, K. On D u a l i t y i n L i n e a r F r a c t i o n a l F u n c t i o n a l s Programming, Z e i t s c h r i f t f u r O p e r a t i o n s R e s e a r c h , V o l . 16, 1972, pp. 91-100. 112 [81] S t e u e r , R. E. L i n e a r M u l t i p l e O b j e c t i v e Programming w i t h I n t e r v a l C r i t e r i o n W e i g h t s , Management S c i e n c e , V o l . 23, 1976, pp. 305-317. [ 8 2 ] S t e u e r , R. E. 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 Programming P r o c e d u r e , TIMS S t u d i e s i n Management S c i e n c e s , V o l . 16, 1977, PP. 225-239. [83] S t e u e r , R. E. and S c h u l e r , A. T. 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 Programming Approach t o Problem i n F o r e s t Management, O p e r a t i o n s R e s e a r c h , V o l . 26, 1978, pp. 254-269. [84] T h i r i e z , H. and Z i o n t s , S., eds. M u l t i p l e C r i t e r i a D e c i s i o n Making, S p r i n g e r - V e r l a g , 1976. [85] W o l f e , P. A D u a l i t y Theorem f o r N o n -Linear Programming, Q u a r t e r l y o f A p p l i e d M a t h e m a t i c s , V o l . 19, 1961, pp. 239-244. [86] Yu, P. L. Cone C o n v e x i t y , Cone Extreme P o i n t s , and Nondominated S o l u t i o n s i n D e c i s i o n Problems w i t h M u l t i o b j e c t i v e s , J o u r n a l o f O p t i m i z a t i o n Theory and A p p l i c a t i o n s , V o l . 14, 1974, pp. 319-377. [ 8 7 1 Yu, P. L. and Z e l e n y , M. The Set o f A l l Nondominated S o l u t i o n s i n L i n e a r Cases and a M u l t i c r i t e r i a Simplex Method, J o u r n a l o f M a t h e m a t i c a l A n a l y s i s and A p p l i c a t i o n , V o l . 49, 1975, PP. 4 3 0 - 4 6 8 . [88] Z e l e n y , M. Compromise Programming, i n Cochrane, J . L. and Zele n y M., eds. M u l t i p l e C r i t e r i a D e c i s i o n Making, 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 , Columbia, S. C , 1973, pp. 262-301. [89] Z e l e n y , M. L i n e a r M u l t i o b j e c t i v e Programming, S p r i n g e r -V e r l a g , B e r l i n , H e i d e l b e r g , New York, 1974. [90] Z e l e n y , M., ed. M u l t i p l e C r i t e r i a D e c i s i o n Making: Kyoto 1975, S p r i n g e r - V e r l a g , B e r l i n , H e i d e l b e r g , New Yor k , 1976. [91] Z i o n t s , S. M u l t i p l e C r i t e r i a D e c i s i o n Making f o r D i s c r e t e A l t e r n a t i v e s w i t h O r d i n a l C r i t e r i a , Working Paper, S c h o o l o f Management, S t a t e U n i v e r s i t y o f New York a t B u f f a l o , 1976. [921 Z i o n t s , S. and Deshphande, D. A Time S h a r i n g Computer Programming A p p l i c a t i o n o f a M u l t i p l e C r i t e r i a D e c i s i o n Method t o Energy P l a n n i n g - A P r o g r e s s R e p o r t , Working Paper, . S c h o o l o f Management, S t a t e U n i v e r s i t y o f New York at B u f f a l o , 1977. [93] Z i o n t s , S. and W a l l e n i u s , J . An I n t e r a c t i v e Programming-Method f o r S o l v i n g t h e M u l t i p l e C r i t e r i a P r oblem, Management S c i e n c e , V o l . 22 ( 6 ) , 1976, pp. 652-663. 11.3 APPENDIX Theorem 0.1. For any x j i n S, we have (a) f ( x ) < f ( y ) i f and o n l y i f ( y - x ) T V f ( x ) ^ 0 (b) f ( x ) < f ( y ) i f and o n l y i f ( y - x ) T V f ( x ) > 0 P r o o f . (a) ( y - x ) T V f ( x ) > 0 i f f ( y - x ) T ( c - f ( x ) d ) £ 0 (by (1) and d Tx+t > 0) i f f ( y - x ) T c £ f ( x ) ( y - x ) T d i f f c T y + r - c T x - r >, f (x) ( d T y + t - d T y - t ) i f f c T y + r >, f ( x ) ( d T y + t ) ( c T x + r = f ( x ) ( d T x + t ) ) i f f f ( y ) ^ f ( x ) (b) S i m i l a r t o the p r o o f o f ( a ) . C o r o l l a r y 0.2. I f V f ( x ) = 0 f o r some x e S, then f reduces t o a c o n s t a n t f u n c t i o n on S. P r o o f . F o r ev e r y y e S, we have ( y - x ) T V f ( x ) = 0 . I t f o l l o w s from Theorem 0.1 t h a t f ( y ) = f ( x ) . C o r o l l a r y 0.3- f i s p s e u d o l i n e a r . P r o o f . By Theorem 0 . 1 ( a ) , we have f ( x ) ^ f ( y ) whenever T (y-x ) V f ( x ) 0. Thus f i s pseudoconvex. By Theorem 0 . 1 ( b ) , we have f ( x ) ^ f ( y ) whenever ( y - x ) T V f ( x ) 4.0. Thus f i s pseudoconcave. 1 1 4 Theorem 0.4. L e t x,y e S "and g be the r e s t r i c t i o n o f f on t h e l i n e segment [x;y] j o i n i n g x and y. Then g i s monotonic and I s e i t h e r convex o r concave. P r o o f . . We may r e g a r d g as a f u n c t i o n d e f i n e d on t 0 ; l ] as f o l l o w s Then g(X) = f ( ( l - X ) x + X y ) g(X) = (aX+b)/(pX+q) f o r X e [0;1] T T T T T T where a = c y-c x, b = c x+r, p = d y-d x and q = d x+t 2 The d e r i v a t i v e s o f g a r e : g'(X) = (aq-bp)/(pX+q) and g"(X) = 2 c ( b p - a q ) / ( p X + q ) 3 . . We n o t i c e t h a t the s i g n s o f g'(X) and g"(X) are independent o f X. Thus g i s m o n o t o n i c a l l y n o n - i n c r e a s i n g ( r e s p e c t i v e l y , n o n - d e c r e a s i n g ) i f aq-bp < 0 ( r e s p e c t i v e l y , aq-bp > 0 ) . A l s o , g i s convex ( r e s p e c t i v e l y , concave) i f c(bp-aq) > 0 ( r e s p e c t i v e l y , c(bp-aq) < 0 ) . Theorem 0.7- L e t u e R n and u / 0. Then f i s m o n o t o n i c a l l y i n c r e a s i n g i n ' t h e d i r e c t i o n u at a l l x i n S O H and m o n o t o n i c a l l y d e c r e a s i n g i n the d i r e c t i o n u at a l l x i n S - H where H = {x e R n : c T u ( d T x + t ) £ d T u ( c T x + r ) } . P r o o f . I t f o l l o w s from (1) and d Tx+t > 0 t h a t V f ( x ) has • T T the same d i r e c t i o n as (d x + t ) c - ( c x + r ) d . Hence V f ( x ) T u > 0 i f f ( d T x + t ) c T u £ ( c T x + r ) d T u i f f x e H . 115 Theorem-0.11. M s a t i s f i e s the f o l l o w i n g : « (a) F o r any x i n S, <M,x> = {x.e R n : c T x + r = f ( x ) ( d T x + t ) > l b ) F o r any x i n S, <M,x> = {Vf(x)> + x. (c) F o r any x and y i n S such t h a t f ( x ) / f ( y ) , we have M = ( { V f ( x ) } X + x) O ({Vf(y)}" 1" + y ) . P r o o f . (a) x e <M,x> i f f x e tx;y] f o r some y e M i f f x = (1-X)x+ y where c y+r i f f c T x + r = ( l - X ) ( c T x + r ) and i f f c T x + r = f ( x ) ( d T x + r ) (b) x e <M,x> i f f c T x + r = f ( x ) ( d T x + t ) = 0 and d Ty+t 3 T__ , , _ /-, y \ / -i T" i f f U - x ) T [ ( d T x + t ) c - ( c T x + r ) d ] = 0 i f f ( x - x ) T V f ( x ) = 0 i f f x = (x-x)+x and x-x e'-fVfCx)}" 1" i f f x e {Vf(x)}" 1" + x (c) ( { V f ( x ) } X + x) O ( { V f ( y ) } X + y) = <M,x> C\ <M,y> = {x e R n : c T x + r = f ( x ) ( d T x + r ) } 0 {x e R n : c T x + r = f ( y ) ( d T x + r ) } = {x e R n : c T x + r = f ( x ) ( d T x + r ) = f ( y ) ( d T x + r ) } = {x e R n : c T x + r = d Tx+r = 0} s i n c e f ( x ) f f ( y ) 1.16 Theorem 0 . 1 3 . . L e t {x 1 1} be a sequence i n S - {x} such t h a t 8 x n •*• x and n -, . x - x n - > - o o I x -x I Then l l m f ( x n ) - f ( x ) = -T -i n —, n - » - o o | x -x | P r o o f . By compactness o f S, t h e r e e x i s t s an open s e t Q such t h a t S C Q and d Tx+t > 0 , V x e Q. Thus a l l the p a r t i a l d e r i v a t i v e s o f f e x i s t and are c o n t i n o u s over Q. I t f o l l o w s from Theorem 6 - 1 8 i n A p o s t o l [4 ] t h a t f o r every e > 0 , t h e r e e x i s t s 6 > 0 such t h a t 0 < |x-x| < 6 i m p l i e s | f ( x ) - f ( x ) - ( x - x ) T V f ( x ) | < |x-x|e / 2 or e q u i v a l e n t l y , ( v_~ ^U-rV - > I < e / 2 f ( x ) - f ( x ) ( x - x ) ^ V f ( x ) |x-x| |x-x| n -I t f o l l o w s from l i m x ~ x = y t h a t I n — i x -x | ( x N - X ) T V f ( x J - T ^ - s l i m — ' —'- = y V f ( x ) n - » - o o |x -x| Thus t h e r e e x i s t s N such t h a t x n - x -x - x < e / 2 , V n > N, and ( i i ) |x -x| < 6 T V n > N. T h e r e f o r e , f o r each n > N, we have 117 |x -x| f ( x n ) - f ( x ) ( x n - x ) T V f ( x ) n -x -x l.x"-x| < e . T h i s completes t h e p r o o f . ( x n - x ~ ) T V f ( x ) x -x I y T v f ( x )
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Multicriteria linear fractional programming
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Multicriteria linear fractional programming Choo, Eng-Ung 1981
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Multicriteria linear fractional programming |
Creator |
Choo, Eng-Ung |
Publisher | University of British Columbia |
Date Issued | 1981 |
Description | The object of this thesis is to study the multi-criteria linear fractional programming problems (MLFP). The characterizations of efficiency, weak efficiency and proper efficiency are derived. In the bicriteria case, the set E of all efficient solutions of (MLFP) is path-connected by a finite number of line segments and the efficient frontier F(E) can be evaluated by using the row parametric technique in linear programming. The weakly efficient (respectively, properly efficient) solutions can be generated by solving the generalized Tchebycheff norm problems (Tβ) (respectively, (βα)) with different parameters β and α. The set E[sup=W] of all weakly efficient solutions of (MLFP) is compact and path-connected by finitely many line segments. A dual problem is formulated which is a natural extension of the usual dual in linear programming, the Wolfe dual in nonlinear programming and the Isermann dual in multiple objective linear programming. Duality results are established under the assumption that the criteria are concave functions. The matrix of the dual variables of (MLFP) can be evaluated by solving L linear programs. A heuristic arrow search algorithm is developed for solving general multicriteria programming problems interactively. The decision maker merely selects his most preferred one amongst-the presented alternatives. Solutions generated are evenly distributed over the desired neighbourhood of the weakly efficient frontier. The algorithm is convergent in the bicriteria case, with appropriate convexity conditions. When applied to solve (MLFP), the arrow search algorithm uses only the linear programming techniques. |
Subject |
Linear programming |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-03-26 |
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.0095487 |
URI | http://hdl.handle.net/2429/22727 |
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 C49.pdf [ 5.33MB ]
- Metadata
- JSON: 831-1.0095487.json
- JSON-LD: 831-1.0095487-ld.json
- RDF/XML (Pretty): 831-1.0095487-rdf.xml
- RDF/JSON: 831-1.0095487-rdf.json
- Turtle: 831-1.0095487-turtle.txt
- N-Triples: 831-1.0095487-rdf-ntriples.txt
- Original Record: 831-1.0095487-source.json
- Full Text
- 831-1.0095487-fulltext.txt
- Citation
- 831-1.0095487.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}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>

https://iiif.library.ubc.ca/presentation/dsp.831.1-0095487/manifest