Open Collections

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 )