 Applied Mathematics, 2011, 2, 556-561 doi:10.4236/am.2011.25073 Published Online May 2011 (http://www.SciRP.org/journal/am) Copyright © 2011 SciRes. AM Compactness, Contractibility and Fixed Point Properties of the Pareto Sets in Multi-Objective Programming Zdravko Dimitrov Slavov1, Christina Slavova Evans2 1Varna Free University, Varna, Bulgaria 2The George Washington University, Washington DC, USA E-mail: slavovibz@yahoo.com, evans.christina.s@gmail.com Received March 6, 2011; revised March 18, 2011; accepted March 22, 2011 Abstract This paper presents the Pareto solutions in continuous multi-objective mathematical programming. We dis- cuss the role of some assumptions on the objective functions and feasible domain, the relationship between them, and compactness, contractibility and fixed point properties of the Pareto sets. The authors have tried to remove the concavity assumptions on the objective functions which are usually used in multi-objective maximization problems. The results are based on constructing a retraction from the feasible domain onto the Pareto-optimal set. Keywords: Multi-Objective Programming, Pareto-Optimal, Pareto-Front, Compact, Contractible, Fixed Point, Retraction 1. Introduction During the last four decades, the topological properties of the Pareto solutions in multi-objective optimization problems have attracted much attention from researchers, see [1-8] for more details. The aim of this paper is to present some new facts on compactness, contractibility and fixed point properties of the Pareto-optimal and the Pareto-front sets, shortly Pareto sets, in a multi-obj ective maximization problem. The authors have tried to remove the concavity assumptions of the objective functions which are usually used in this optimization problem. The standard form of the multi-objective maximiza- tion problem is to find a variable 12 ,,, m m xxx R, 1m, so as to maximize 12 ,, n xfxfx,fx subject to X, where the feasible domain is nonempty, 2, , 1, n n R is the index set, , is a given continuous function for all . 2n : i fX n iJ Since the objective functions may conflict 1 n ii f with each other, it is usually difficult to obtain a global maximum for all objective functions at the same time. Therefore, the target of the maximization problem is to achieve a set of solutions that are Pareto-optimal. His- torically, the first reference to address such situations of conflicting objectives is usually attributed to Vilfredo Pareto (1848-1923). Definition 1. a) A point X is called a Pareto-optimal solution if and on ly if there does not exist a point X such that i i yfx for all n iJ and kk yfx for some . The set of Pareto-optimal solutions of n kJ is denoted by f,XPO and is called a Pareto-optimal set. Its image ,, POPFXf Xf is called a Pareto-front set. b) A point X is called a strictly Pareto-optimal solution if and only if there does not exist a point X such that ii yfx for all and n iJ y . The set of strictly Pareto-optimal solutions of is denoted by ,X fSPO and is called a strictly Pareto-optimal set. The strictly Pareto-optimal solutions are the multi- objective analogue of unique optimal solutions in scalar optimization. In this paper, let the feasible domain be compact. It is well-known that and ,POXf ,X fPF are nonempty, ,,f POX SPOXf and ,PF X f X [4]. One of the most important problems in multi-criteria maximization is the investigation of the topological  Z. D. SLAVOV ET AL.557 properties of the Pareto-optimal and Pareto-front sets. Information about these properties of the Pareto sets is very important for computational algorithms generating Pareto solutions [8,9]. Consideration of topological properties of Pareto solutions sets is started by [5], see also [4,6,9,10]. We focus our attention on the compactness, contracti- bility and fixed point properties of the Pareto sets. Com- pactness of these sets is studied in [4,6,11]. Contracti- bility of Pareto sets is considered in [12-14]. Fixed point properties of Pareto-optimal and Pareto-front sets have been addressed in [7,15]. This paper is organized as follows: In Section 2, we describe some definitions and notions from topology and optimization theory. In Section 3, we study compactness, contractibility and fixed point properties of the Pareto-optimal and Pareto-front sets. 2. Definitions and Notions Recall some topological definitions. Definition 2. a) The set is a retract of YX if and only if there exists a continuous function such that for all :rX Y rx x Y . The function is called a retraction. r b) The set is a deformation retract of YX if and only if there exist a retraction and a homotopy :rX Y :0;1 XX such that 0 x, x and ,1 xrx for all X . c) The set is contractible (contractible to a point) if and only if there exists a point such that Y aY a is a deformation retract of . Y Definition 3. The topological space is sa id to have the fixed point property if and only if every continuous function from this set into itself has a fixed point, i.e. there is a point Y :hY Y Y such that hx. Remark 1. Let d Y btwo topological spaces. A homotopy between two continuous functions an e ,: gX Y is defined to be a continuous function :0;1 XY such that ,0 xfx and ,1 xgx for all X. Note that we can con- sider the homotopy as a continuously deformation of to [16]. Remark 2. From a more formal viewpoint, a retrac- tion is a function such that r:X Y rrxrx for all X, since this equation says exactly that is the identity on its image. Retractions are the topologi- cal analogs of projection operators in other parts of mathematics. Clearly, every deformation retract is a re- Remark 3. It is known that convexity implies contr- tract, but in genee converse does not hold ac tib rally th[16]. ility, but the converse does not hold in general. Con- tractibility of sets is preserved under retraction. This means that if set is contractible and Y is a retract of , then set Y contractible too. L us consid a multifunction :Y is Y et er empty, co. Let it be upper semi-continuous with a nonmpact and convex image, shortly we say that is cusco. Definition 4. The topological space Y is said to h ave the Kakutani fixed point property if and only if every cusco :YY has a fixed point, i.e. there is a point Y such that x . mark 4. A peRe roperty is calld a topological property if and only if an arbitrary topological space has this property, then Y has this property too, wre Y is homeomorphic the o . Compactness, contractibility and the fixed point prorties (the fixed point property and the Kakutani fixed point property) are topological prop- erties. Of crse, th pe oue topological properties of the Pareto- op d the Kakutani fixed po timal set relate to the topological properties of the Pareto-front set, respectively. Remark 5. The fixed point an int properties of sets are preserved under retraction [16]. This means that the following statements are true: if set has the fixed point property and Y is a retract of , then set Y has the fixed point pperty too; if set ro has the Kutani fixed point property and Y is a retract of ak , then set Y has the Kakutani fixed point property too Remark 6.e Ka . Thkutani fixed point property is very cl et be compact. It can be shown th osely related to the fixed point property. If n SR has the Kakutani fixed point property, then sin continuous functio n from S into itself can be viewed as a cusco it follows that seS will also have the fixed point property. Remark 7. Ln SR ce any t the Kaat set S havingkutani fixed point property is equivalent to S having the fixed point property. Re- mark 6 has shown that if S has the Kakutani fixed point property, then S hashe fixed point property. Now, let :SS t be cusco, S have the fixed point property a , ph S rem it follows that there is an appro xyS |yx . From nd Cellina’s Theoximate continuous selection h of [17,18]. That is, for each kN there exists acontius function : k hS S nuo such that 1 ,,gph for k dxh k xall S . rop-From the assxed point p erty, it follows that each function k h has a fixed point k ump has the fition thatS S . As a result we get a sequenc e 1 kk S such Copyright © 2011 SciRes. AM  Z. D. SLAVOV ET AL. 558 that 1 ,,xxgph , i.e. th kk dke point , kk x approaches the set gph . The set S is c implying that there a convergensubsequence 1 1k mk k xx such that 0 lim mk k ompact, exists t mk xS . We also see that 1 ,, mk mk x dxgph mk . But is cusco, then gph mk 00 ,xx is closed. Taking the lim g it as k we have and obtain , k mk x ph lim m kx 0 . This means that S is a fixed point for , see also [19]. Finally, we t S has the Kakutanf ixed point property. We usm R and n R as generic finite-dimensa ves. Ition find tha e i ionl ctor spacen addi, we also introduce the follow- ing notations: for every two vectors ,n yR, 12 ,, n xxx,x 12 ,,, n yy y mi eans i y for all n iJ, 12 ,,, 12 ,, , nn xxx yyy eans i y m i y for iJ 1 , all order), 2 2 ,, ,,, nn n (wea 1 kly componentwise xxyxyy means ii y y for all rder), and n iJ (strictly com 1 , ponentwise o 2 12 ,, ,,, nn xxx yyyy means ii y for all n iJ and kk y order) n Result for some n J (comentwise . 3. ai k transfer our pon M s usual, the key idea is toAmulti-objective optimization problem to mono-objective optimization problem by defining a unique objective function. We begin with the following definition: define a mul- tifunction : X by yX|fyfx for all X; define a function : XR by x j 1 n j x f or all X. Choose X and consider an optimization problem wile objth a singective function as follows: maximize y subject to x . By letting vary over all of we can identify different Pareto-optimal solutions. This optimization technique will allow us to find the whole Pareto-optimal set. In this paper, we will discuss the role of the following assumptions: Assumption 1. is a nonempty, compact and con- vex set. Assumption 2. Arg max,1sx for all X . Assumption 3 If 0 ii .is a metric in , d m R X , then 0 k x 0, lim dy k for 0 li ,dx xm 0 k k and all 00 x . Assumption 4. is to obtain a set ie. ur aimof conditions which guaran- point pr s bijectiv O tee the compactness, contractibility and fixed operties of the Pareto sets. Remark 8. Let Cl X be the set of all nonempty compact subsets of . A sequence of sets A 1 kk X is said to Wn converge to Cl ijsma Cl X if and only if for each X , lim ,dxA . , kdxA k o Assumption 3. These definitions and ptions allow us t the main theorem of this p Theorem 1. See alsassumto presen aper. If Assumptions 1, 2, 3 and 4 hold, then: a) ,,POXfSPOXf. b) ,POXf and ,PFXf are compact. c) ,POXf and ,PFXf are contractible. d) ,POXf and ,PFXf have the fixed point properties. rder to givoof of Th sommas. In oe the preorem 1, we will prove me le Lemma 1. If X , , PO Xf is equivalent to x . Proof. Let , PO Xf e that and assum x . From x the conditions and x , there exists it follows that \ xx such that yfx. As a result we get that ysx, but , PO Xf implies ysx and y by assumption fx. Since is bijective, we deduce y ; which contradicts the condition \ xx us, we obta i n . Th x . Conversely, let x and assume that , PO Xf. From the assump , PX fOtion , it follows that the re exists X\ x such that yfx. Thus we deduce that x and y , which contradicts the condition x . Therefore, we obtain , PO Xf. The lemma is proven. Lemma 2. If X , then Arg max,sx ,POXf. Copyright © 2011 SciRes. AM  Z. D. SLAVOV ET AL.559 x and as- sum Proof. Let us choose Arg max,ys e that , PO Xf , . From the assumption PO Xf it follows that there exists \zX y such that zfy derive zx and . As a result we z fore, sy. This leads to a con we obtain , tradic- tion; there PO Xf. The lemma is sing proven. Now, u Ar , g max, xPOXf (Lemma 2) and Arg max,1sx n to constru (Assumption 3), wct a function e are in a positio ,r:XPO Xf such that rxArg max , x for all X, see also Defi- nition 1 and Lemma 1. ying Lemma Remark 9. Appls 1 and 2 it follows that: if , PO Xf, then rx; if , X\POXf then , rx. This me ans that ,POXf. rX Lemma 3. is continuous on . Proof. at if First, we will prove th 1 kk X such that and nces yX are a pair of seque 1 kk lim k k0 xX and kk x fr allo, then kN f 1 y there exists a convergent subsequence okk whose to 0 limit belongs . ion The assumpt kk x for all kimplies N kk yfx for all kN. From ondition k yX it the c exists a convergent q 1k bsequence 11 follows that ther kk su e su kk qy ch thatlim k k 0 yX . e exists nvergent subsequence k such that kk qp and 0 lim k px Therefore, th k p er 11kk x a co k . Thus, we find that kk qfp for a the limit as k we obtain 00 ll kN. Taking yfx. This implie s 00 x. This means that is upper seuous mi-continon [20]. Secon prd, we willove that if 1 kk X is a se- qutoence convergent 0 X and 00 x , th there en exists a sequethat nce 1k yX suc kh kk x for all kN and lim k As usual, the distanceen theX 0k yy. e betw point0 y and the set k X is denoted by 0,syx|x.in kk d x fdi Clearly, k is nonempty and compact; therefore, if 0k x, t hen there exists k ˆ x such that dd o cases as 0 , yy . Th kˆ ere are tw follows: if 0 k x , the0n k d and let 0k yy ; if 0k x , thennd let kˆ yy k d0 a . Thua sequence s, we get 1 kk d R and a sequence 1 kk yX such that kk x f kN or all and 0,k y. Ass lim k k k ddyumption 0 3 and x imply that the sequence gent and 1 kk d is conver- lim 0 k kd . Finally, we obta0 yin lim k k y . s meansThi that is los onwer semi-continuou [20]. In summary, is continuous on . eo - , n- The lemen. ma is prov h , a Lemma 4 [21, Trem 9.14 – The Maximum Theo rem]. Let n SRm R, :hSR a co tinuous functionnd :DS be co unction. Th, a mp enth act-valued ane function d continuous multif :Rh* defined by is continuous on , and the multifunction D*:S ine defd by D*x D|h ,x h* is compact-valu- ed and upper semi-co ntinuous on . . r is continuous on Lemma 5 . Proof. As was mentioned before, the multifunction is com and continuous pact-valuedon . Applying Lemma 6 for SX and D , we deduce that is an uppe semi-continuous mltirufon onuncti . isObviously, an upper semi-continuous multifunction continuous when viewed as a function. Th shows that is is continuous on . The lemma is proven. Lemma 6 [2 1, Theorem 9.31 – Schauder’s Fixed Point Theorem]. Let :hS S be a continuous function from anonempty, compactd convex set n SR into itself, th be an. en h has a fixed point Lemma 7 [21, Theorem 9.26 - Kakutani’s Fixed Point Theorem]. Let SR a nonempty, compact and convex set and the multifunction :S n S usco, then be c ha fixed point. s a Lemma 8. ,POXf is homeomorphic to ,PF X f. Proof. It is well-known th a compact. In fact, the at every continuous image of pset act set is com is compact and th is continuous one function r . Hence, the set Copyright © 2011 SciRes. AM  Z. D. SLAVOV ET AL. 560 ,X frmpact. Recalling that POX tion :n is cothe func- XR is str continuous, we deduce that the re- iction :, ,hPOXf PFXf of is con- tinuous too. We know that the function h is bijective. Consider the ine function ,POXf of h. As we proved abov ,OXf is compact; therefore, 1 h vers 1:,hPFXf e, the set P is continuous tod that function h is homeomorphism. The lemma is proven. ing Lma 1 we get that ,,PO XfS. From Lemma 5 it follows that there exists a continu- ous function :,rXPOXf such that o [22] Proof of Theorem PO . As a result we fin 1. Apply em X f the rX ,X f and ArrxPO g maxs, x for all X. This means that ,OXf Pis a retract of . We know that is nonempty, compact and convex (Assumption 1), i.e. it is contractile, has the fixed point and the Kakutanerties, see Lem b xed point prop allows us to deduce i fi and 7. Thisk mas 6 remart tha ,X f d the nvex in ractibility x. se th nctions which PO pact and contractib fixed point an ni fixed point prop [6 is com Kakuta ge emark 11. the ve do concavity assump le, has the erties. sets ge , compactness a ain is comp are that the proo tions on the objective Vol According to Lemma 8 we obtain that the Pareto-front set ,PFXf is compact and contractible, has the fixed point and the Kakutani fi xed point pr op e rties too. The theorem is proven. Remark 10. It is important to note that the Pareto-optimal and Pareto-front are n act and The f t ue ship between the first two. iza- tion,” Springer, Berlin, 2003. r Optimization: Theory, Applications, and inger, Berlin, 2004. ican Mathematical Society, onvex Optimization,” ptimization with Quasi-Concave Functions,” : The- n d c di fu ot co neral, it is not difficult to ont conve d no [9] neral. RAs we have shown in Lemma 6, if an ar- bitrary set is nonempty, compact and convex, then it has Ca fixed point property. In rify that the Pareto-optimal and Pareto-front sets are nonconvex, but they are compact and contractible. Thus among noonvex setsnc not have direct relationship with the fixed point prop- erty. There are examples of compact and contractible sets which do not have the fixed point property. It is not known what types on nonconvex sets have this property. 4. Conclusions We have shown the compactness, contractibility and fixed point properties of the Pareto-optimal and Pareto- front sets in multi-objective mathematical programming when the feasible dom two important facts Conc are usually used in this optimization problem, and that the Pareto-optimal and Pareto-front sets are not compact and convex in general. The authors see three directions for future r esearch re- lated to this article: one would look for general condi- tions on the objective functions without the assumption of their concavity; one would analyze specific types of concave or quasi-concave objective functions; and one would study the relation 5. References [1] J. Cohon, “Multi-Objective Programming and Planning,” Academic Press, Cambridge, 1978. [2] Y. Collette and P. Siarry, “Multi-Objective Optim [3] J. Jahn, “Vecto Extensions,” Spr [4] D. Luc, “Theory of Vector Optimization,” Springer, Ber- lin, 1989. [5] B. Peleg, “Topological Properties of the Efficient Point Set,” Proceedings of the Amer Vol. 35, No. 2, 1972, pp. 531-536. doi:10.1090/S0002-9939-1972-0303916-2 ] Z. Slavov and C. Evans, “On the Structure of the Effi- cient Set,” Mathematics and Education in Mathematics, . 33, 2004, pp. 247-250. [7] Z. Slavov, “The Fixed Point Property in Convex Multi- Objective Optimization Problem,” Acta Universitatis Apu- lensis, Vol. 15, 2008, pp. 405-414. [8] R. Steuer, “Multiple Criteria Optimization: Theory, Com- putation and Application,” John Wiley and Sons, Hobo- ken, 1986. M. Ehrgott, “Multi-Criteria Optimization,” Springer, Berlin, 2005. [10] S. Boyd and L. Vandenberghe, “C mbridge University Press, Cambridge, 2004. [11] Z. Slavov, “Compactness of the Pareto Sets in Multi- Objective O Mathematics and Education in Mathematics, Vol. 35, 2006, pp. 298-301. [12] J. Benoist, “Contractibility of the Efficient Set in Strictly Quasi-Concave Vector Maximization,” Journal of Opti- mization Theory and Applications, Vol. 110, No. 2, 2001, pp. 325-336. doi:10.1023/A:1017527329601 [13] N. Huy and N. Yen, “Contractibility of the Solution Sets in Strictly Quasi-Concave Vector Maximization on Non- compact Domains,” Journal of Optimization Theory and Applications, Vol. 124, No. 3, 2005, pp. 615-635. doi:10.1007/s10957-004-1177-9 [14] Z. Slavov, “Contractibility of Pareto Solutions Sets in ave Vector Maximization,” Mathematics and Edu- cation in Mathematics, Vol. 36, 2007, pp. 299-304. [15] Z. Slavov, “On the Engineering Multi-Objective Maxi- mization and Properties of the Pareto-Optimal Set,” In- ternational e-Journal of Engineering Mathematics ory and Application, Vol. 7, 2009, pp. 32-46. [16] A. Hatcher, “Algebraic Topology,” Cambridge Univer- Copyright © 2011 SciRes. AM  Z. D. SLAVOV ET AL. Copyright © 2011 SciRes. AM 561 nlin- erie O ematical Economics: Lin- ourse in Optimization Theory,” Publica- sity Press, Cambridge, 2002. [17] J. Borwein and A. Lewis, “Convex Analysis and No ear Optimization: Theory and Examples,” Springer, Ber- lin, 2000. [18] A. Cellina, “Fixed Point of Noncontinuous Mapping,” Atti della Accademia Nazionale dei Lincei Sttava Cambridge University Press, London, 1996. [22] A. Wilansky, “Topology for Analysis,” Dover Rendiconti, Vol. 49, 1970, pp. 30-33. [19] J. Franklin, “Methods of Math ear and Nonlinear Programming, Fixed Point Theorems,” Springer, Berlin, 1980. [20] A. Mukherjea and K. Pothoven, “Real and Functional Analysis,” Plenum Press, New York, 1978. [21] R. Sundaran, “A First C tions, New York, 1998.
|
