 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,,, mmxxxx R, 1m, so as to maximize  12,,nfxfxfx,fx subject to xX, where the feasible domain X is nonempty, 2, ,1,nJnR is the index set, , is a given continuous function for all . 2n:ifXniJSince the objective functions  may conflict 1niif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 xX is called a Pareto-optimal solution if and on ly if there does not exist a point yX such that iifyfx for all niJ and kkfyfx for some . The set of Pareto-optimal solutions of nkJX is denoted by f,XPO and is called a Pareto-optimal set. Its image ,,fPOPFXf Xf is called a Pareto-front set. b) A point xX is called a strictly Pareto-optimal solution if and only if there does not exist a point yX such that iifyfx for all and niJxy. The set of strictly Pareto-optimal solutions of X 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 X be compact. It is well-known that and ,POXf,X fPF are nonempty, ,,f POXSPOXf and ,PF X f fX . 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 , 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X if and only if there exists a continuous function such that for all :rX Yrx xxY. The function is called a retraction. rb) The set is a deformation retract of YXX if and only if there exist a retraction and a homotopy :rX Y:0;1HXX such that 0Hx, x and  ,1Hxrx for all xX. c) The set is contractible (contractible to a point) if and only if there exists a point such that YaY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xY such that xhx. Remark 1. Let X d Y btwo topological spaces. A homotopy between two continuous functions an e ,:fgX Y is defined to be a continuous function :0;1HXY such that ,0Hxfx and  ,1Hxgx for all xX. Note that we can con-sider the homotopy H as a continuously deformation of f to g .  Remark 2. From a more formal viewpoint, a retrac-tion is a function such that r:X Yrrxrx for all xX, since this equation says exactly that r 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 actibrally th.  ility, but the converse does not hold in general. Con-tractibility of sets is preserved under retraction. This means that if set X is contractible and Y is a retract of X, then set Y contractible too. L us consid a multifunction :Y is Yet 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 xY such that xx.  mark 4. A peRe roperty is calld a topological property if and only if an arbitrary topological space X has this property, then Y has this property too, wre Y is homeomorphic theo X. Compactness, contractibility and the fixed point prorties (the fixed point property and the Kakutani fixed point property) are topological prop-erties.  Of crse, thpeoue topological properties of the Pareto- opd the Kakutani fixed potimal set relate to the topological properties of the Pareto-front set, respectively. Remark 5. The fixed point anint properties of sets are preserved under retraction . This means that the following statements are true: if set X has the fixed point property and Y is a retract of X, then set Y has the fixed point pperty too; if set roX has the Kutani fixed point property and Y is a retract of akX, then set Y has the Kakutani fixed point property too Remark 6.e Ka.  Thkutani fixed point property is very clet be compact. It can be shown thosely related to the fixed point property. If nSR 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. LnSRce anyt  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,gph Srem it follows that there is an approxyS |yx. From nd Cellina’s Theoximate continuous selection h of  [17,18]. That is, for each kN there exists acontius function :khS S  nuosuch that1,,gph for kdxh kxall xS. rop-From the assxed point perty, it follows that each function kh has a fixed point kump has the fition thatS xS. As a result we get a sequence 1kkxS such Copyright © 2011 SciRes. AM Z. D. SLAVOV ET AL. 558 that 1,,xxgph, i.e. thkkdke point ,kkxx approaches the set gph. The set S is cimplying that there a convergensubsequence 11kmk kxx such that 0lim mkkompact, exists t mkxxS . We also see that  1,,mk mkxdxgph mk. But  is cusco, then gph mk00,xxis closed. Taking the limgit as k we have and obtain  ,k mkx ph lim mkx 0 . This means that xS is a fixed point for , see also . Finally, we t S has the Kakutanf ixed point property.  We usmR and nR as generic finite-dimensaves. Itionfind thae i ionl ctor spacen addi, we also introduce the follow-ing notations: for every two vectors ,nxyR, 12,, nxxx,x 12,,,nyyy y mieans ixy for all niJ, 12,,, 12,, ,nnxxxx yyyeans iy mixy for iJ1,all order),  2 2,, ,,,nnn (wea1kly componentwisexxxyxyy means iiyxy for all rder), andniJ (strictly com1,ponentwise o 2 12,, ,,,nnxxxx yyyy means iixy for all niJ and kkxyorder)n Result for some nJ (comentwise . 3. aik 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 :XXby xyX|fyfx for all xX; define a function :sXR by sx j1njfx for all xX. Choose xX and consider an optimization problem wile objth a singective function as follows: maximize sy subject to yx. By letting x vary over all of X 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. X is a nonempty, compact and con-vex set. Assumption 2. Arg max,1sx for all xX. Assumption 3 If 0ii.is a metric in , d mRxX , then 0kx0,lim dyk for 0li ,dx xm 0kkand all 00yx. Assumption 4. f is to obtain a set ie. ur aimof conditions which guaran-point prs bijectivOtee the compactness, contractibility and fixed operties of the Pareto sets. Remark 8. Let Cl X be the set of all nonempty compact subsets of X. A sequence of sets A 1kkX is said to Wn converge to Cl ijsmaACl X if and only if for each xX, lim ,dxA . ,kdxAko Assumption 3. These definitions and ptions allow us t the main theorem of this pTheorem 1.See alsassumto presenaper. 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 Thsommas. In oe the preorem 1, we will prove me leLemma 1. If xX, ,xPO Xf is equivalent to xx. Proof. Let ,xPO Xf e that and assumxx. Fromxx the conditions and xx, there exists it follows that \yxx such that fyfx. As a result we get that sysx, but ,xPO Xf implies sysx and fy by assumption fx. Sincef is bijective, we deduce xy; which contradicts the condition \yxxus, we obta i n  . Thxx. Conversely, let xx and assume that ,xPO Xf. From the assump,xPX fOtion , it follows that there exists yX\ x such that fyfx. Thus we deduce thatyxand xy, which contradicts the condition  xx. Therefore, we obtain ,xPO Xf. The lemma is proven. Lemma 2. If xX, then Arg max,sx ,POXf. Copyright © 2011 SciRes. AM Z. D. SLAVOV ET AL.559 x and as-sumProof. Let us choose Arg max,yse that ,yPO Xf,. From the assumption yPO Xf it follows that there exists \zX y such that  fzfy derive zx and . As a result weszfore, sy. This leads to a conwe obtain ,tradic-tion; thereyPO Xf. The lemma is sing proven. Now, uAr ,g max,sxPOXf (Lemma 2) and Arg max,1sxn to constru (Assumption 3), wct a function e are in a positio,r:XPO Xf such that rxArg max,sx for all xX, see also Defi-nition 1 and Lemma 1. ying LemmaRemark 9. Appls 1 and 2 it follows that: if ,xPO Xf, then xrx; if ,xX\POXfthen , xrx. This me ans that ,POXf.  rXLemma 3.  is continuous on X. Proof. at if First, we will prove th1kkxX such that andnces yXare a pair of seque1kk lim kk0xxX and kkyx fr allo, then kNf 1ythere exists a convergent subsequence okk whose to 0limit belongsx. ion The assumptkkyx for all kimplies N kkfyfx for all kN. From ondition kyX it the cexists a convergent q1kbsequence11follows that therkksue su kkqych thatlim kk 0yX. e exists nvergent subsequence ksuch thatkkqpand 0lim kpxTherefore, thkper11kkxa cok. Thus, we find that kkfqfp for a the limit as k we obtain  00ll kN. Takingfyfx. This implie s 00yx. This means that  is upper seuous mi-continon X . Secon prd, we willove that if 1kkxX is a se-qutoence convergent 0xX and 00yx, th there enexists a sequethat nce 1kyX suckh kkyx for all kN and limkAs usual, the distanceen theX0kyy. e betw point0yand the set kxX is denoted by 0,syx|x.inkkd xfdi Clearly, kx is nonempty and compact; therefore, if 0kyx, then there exists kˆyx such that ddo cases as0,yy. Thkˆere are tw follows: if 0kyx, the0n kd and let 0kyy; if 0kyx, thennd let kˆyy kd0 a. Thua sequence s, we get 1kkdR and a sequence 1kkyX such that kkyx f kNor all and 0,ky. Asslim kkkddyumption 03 and xx imply that the sequence gent and 1kkd is conver-lim 0kkd. Finally, we obta0yin limk ky. s meansThi that  is los onwer semi-continuou X . In summary,  is continuous on X. eo -, n-The lemen. ma is provh, aLemma 4 [21, Trem 9.14 – The Maximum Theorem]. Let nSRmR, :hSR a cotinuous functionnd :DS be counction. Th, a mpenth 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 5X. Proof. As was mentioned before, the multifunction  is com and continuous pact-valuedon X. Applying Lemma 6 for SX and D, we deduce that r is an uppe semi-continuous mltirufon onuncti X. isObviously, an upper semi-continuous multifunction continuous when viewed as a function. Th shows that isr is continuous on X. 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 nSR into itself, th be an. en h has a fixed pointLemma 7 [21, Theorem 9.26 - Kakutani’s Fixed Point Theorem]. Let SR a nonempty, compact and convex set and the multifunction :SnSusco, then be c ha fixed point. s aLemma 8. ,POXf is homeomorphic to ,PF X f. Proof. It is well-known tha compact. In fact, the at every continuous image of pset act set is comX is compact and th is continuous one function r X. Hence, the set Copyright © 2011 SciRes. AM Z. D. SLAVOV ET AL. 560 ,X frmpact. Recalling that POX tion :nis cothe func-fXR is strcontinuous, we deduce that the re-iction :, ,hPOXf PFXf of f 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, 1hvers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 Proof of Theorem PO. As a result we fin1. Apply emX f therX ,X f and ArrxPOg maxs, xfor all xX. This means that ,OXf Pis a retract of X. We know that X is nonempty, compact and convex (Assumption 1), i.e. it is contractile, has the fixed point and the Kakutanerties, see Lem bxed point propallows us to deducei fiand 7. Thisk mas 6 remart tha,X fd thenvex inractibility x. se thnctions which POpact and contractib fixed point anni fixed point prop [6is comKakutage emark 11. thevedoconcavity assumple, has theerties. sets ge, compactness aain is comp are that the prootions on the objective VolAccording 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 arenact and Thef t ueship 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- nd cdi fuot coneral, it is not difficult to ontconved no 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. Inrify 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 domtwo important facts Concare 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 relation5. References  J. Cohon, “Multi-Objective Programming and Planning,” Academic Press, Cambridge, 1978.  Y. Collette and P. Siarry, “Multi-Objective Optim J. Jahn, “VectoExtensions,” Spr D. Luc, “Theory of Vector Optimization,” Springer, Ber-lin, 1989.  B. Peleg, “Topological Properties of the Efficient Point Set,” Proceedings of the AmerVol. 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.  Z. Slavov, “The Fixed Point Property in Convex Multi- Objective Optimization Problem,” Acta Universitatis Apu-lensis, Vol. 15, 2008, pp. 405-414.  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.  S. Boyd and L. Vandenberghe, “Cmbridge University Press, Cambridge, 2004.  Z. Slavov, “Compactness of the Pareto Sets in Multi- Objective OMathematics and Education in Mathematics, Vol. 35, 2006, pp. 298-301.  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  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  Z. Slavov, “Contractibility of Pareto Solutions Sets in ave Vector Maximization,” Mathematics and Edu-cation in Mathematics, Vol. 36, 2007, pp. 299-304.  Z. Slavov, “On the Engineering Multi-Objective Maxi-mization and Properties of the Pareto-Optimal Set,” In-ternational e-Journal of Engineering Mathematicsory and Application, Vol. 7, 2009, pp. 32-46.  A. Hatcher, “Algebraic Topology,” Cambridge Univer-Copyright © 2011 SciRes. AM Z. D. SLAVOV ET AL. Copyright © 2011 SciRes. AM 561nlin-erie Oematical Economics: Lin-ourse in Optimization Theory,” Publica-sity Press, Cambridge, 2002.  J. Borwein and A. Lewis, “Convex Analysis and Noear Optimization: Theory and Examples,” Springer, Ber-lin, 2000.  A. Cellina, “Fixed Point of Noncontinuous Mapping,” Atti della Accademia Nazionale dei Lincei Sttava Cambridge University Press, London, 1996.  A. Wilansky, “Topology for Analysis,” DoverRendiconti, Vol. 49, 1970, pp. 30-33.  J. Franklin, “Methods of Mathear and Nonlinear Programming, Fixed Point Theorems,” Springer, Berlin, 1980.  A. Mukherjea and K. Pothoven, “Real and Functional Analysis,” Plenum Press, New York, 1978.  R. Sundaran, “A First Ctions, New York, 1998.