（运筹学与控制论专业论文）多目标规划的若干理论和方法.pdf

大连理工大学博士学位论文 摘要 本文主要研究多目标规划的理论和方法，包括多目标规划的罚函数法和非光滑多目标 分式规划的最优性条件以及对偶性。本文取得的主要结果可以概括如下： 1 、研究了多目标规划的指数罚函数法。本文提出了多目标规划的指数罚函数法，详尽 地证明了该方法的收敛陛。将多目标规划的指数罚函数法应用到有限m i n m a x 多目标规划 问题上，建立了求解该类不可微多目标规划问题的指数罚函数法，所得到的结果与施保昌和 胡新生【7 4 ，1 2 8 给出的求解有限m i n m a x 多目标规划问题的极大熵方法是一致的 2 、给出了一种构造多目标规划罚函数的统一框架。对一般不等式约束多目标规划问 题，利用熵光滑化方法，导出多目标规划的指数罚函数法。在此基础上，将个由闭正常严 格凸函数产生的可分离变量的向量函数加到向量值l a g r a n g e 函数上，建立求解具有不等式 约束的多目标规划问题的向量拉格朗日光滑化方法。最后，利用所建立的多目标规划问题的 向量拉格朗日光滑化方法，给出一种构造具有不等式约束的多目标规划问题的罚函数的统 一框架。 3 、研究了三种类型的非光滑多目标分式规划问题的最优性条件和对偶性。 ( 1 ) 对具有不等式约束的非光滑多目标分式规划问题，利用c l a r k e 次微分首次引入：广义 ( 只口，p ，d ) 一凸和广义( 只o ，p ，d ) 一v - 凸的概念。在广义( f i 口，p ，d ) - 凸和广义( e a ，p ，d ) 一弘 凸的条件下建立起该非光滑多目标分式规划的p a r e t o 有效解的最优性条件。在此基础上， 建立了三种对偶模型：m o n d - w e i r 型对偶模型、半参数对偶模型、参数对偶模型。利用已 得到的最优性条件，对每一种对偶模型针对p a x e t o 有效解建立了弱对偶定理、强对偶定理 和逆对偶定理。 ( 2 ) 研究了一类带有抽象约束的非光滑多目标分式规划问题，其中所包含的函数是局部 l i p s c k i t z 的和c l a r k e 次可微的。首先，在g 一( e 力凸的条件下，证明了择一定理。然后， 证明了该多目标分式规划问题在g e o f f r i o n 意义下的真有效解的充分条件和必要条件。这部 分内容改进了c h e n 8 4 1 中的结果。 ( 3 ) 讨论了一类具有不可微凸不等式约束、线性等式约束和抽象约束的不可微多目标分 式规划问题。首先利用 次微分给出了该不可微多目标分式规划问题 弱有效解的必要条 件和充分条件。在此基础上，构造出了一种参数对偶模型，并证明了相应的 对偶定理。 多目标规划的若干理论和方法 4 、研究了具有f 一凸目标函数和f 一凸约束函数的多目标规划问题的最优性条件。 通过对目标函数的修改构造一个与之等价的多目标规划问题。然后，对构造的多目标规划问 题引入f 一拉格朗日函数和新型的鞍点。最后，给出了新型的鞍点与原多目标规划问题有 效解之间的关系。 关键词：光滑化方法；多目标规划；罚函数法；多目标分式规划，最优性条件；对偶性 p a r e t o 有效解；g e o f f r i o n 真有效解；广义( f 口，p ，d ) 一凸；广义( f j n ，p ，d ) 一v 一凸 i i 大连理工大学博士学位论文 a b s t r a c t t h i sd i s s e r t a t i o ns t u d i e sm a i n l yt h e o r ya n dm e t h o d so fm u l t i o b j e c t i v ep r o g r a m m i n g ， i n c l u d i n gp e n a l t yf u n c t i o nm e t h o d ，o p t i m a l i t yc o n d i t i o n sa n dd u a l i t yo fn o n s m o o t h m u l t i o b j e c t i v ef r a c t i o n a lp r o g r a m m i n gp r o b l e m s ，t h em a i nr e s u l t so b t a i n e di nt h i sd i s s e r t a t i o n m a yb es u m m a r i z e da sf o l l o w s ： 1 t h ee x p o n e n t i a lp e n a l t yf l m c t i o nm e t h o do fm u l t i o b j e c t i v ep r o g r a m m i n gp r o b l e m s i ss t u d i e d f o l l o w i n gt h ec l a s s i c a le x p o n e n t i a lp e n a l t yf u n c t i o nm e t h o do fm a t h e m a t i c a lp r o - g r a m m i n g ，t h ee x p o n e n t i a lp e n a l t yf u n c t i o nm e t h o d o fm u l t i o b j e c t i v ep r o g r a m m i n gp r o b l e m s i sc o n s t r u c t e da n dc o n v e r g e n c eo ft h ee x p o n e n t i a lp e n a l t yh m c t i o nm e t h o do fm u l t i o b j e c t i v e p r o g r a m m i n gp r o b l e m si sp r o v e d w h e nt h ee x p o n e n t i a lp e n a l t yf u n c t i o nm e t h o do fm u l - t i o b j e c t i v ep r o g r a m m i n gp r o b l e m si su t i l i z e df o rt h em u l t i o b j e c t i v ep r o g r a m m i n gp r o b l e m e q t m l i e n tt ot h e f i n i t en f i n m a xm u l t i o b j e c t i v ep r o g r a m m i n gp r o b l e m ，t h ee x p o n e n t i a lp e n a l t y f u n c t i o nm e t h o df o rt h i sc l a s so fn o n d i f f e r e n t i a b l em u l t i o b j e c t i v ep r o g r a m m i n gp r o b l e mi s e s t a b i s h e d ，w h i c hi sc o n s i s t e n tt om a x i m u me n t r o p ym e t h o d 【7 4 ，1 2 8 】f o rt h ef i n i t em i n m a x m u l t i o b j e e t i v ep r o g r a m m i n gp r o b l e m ， 2 au n i f i e df r a m e w o r kf o rc o n s t r u c t i n gp e n a l t yf u n c t i o n so fm u l t i o b j e c t i v ep r o g r a m - r u i n gp r o b l e m si so f f e r e d f i r s t ，f o rm u l t i o b j e c t i v ep r o g r a m m i n gp r o b l e m sw i t hi n e q u a h t y c o n s t r a i n t s ，t h ee x p o n e n t i a lp e n a l t yf u n c t i o nm e t h o do fm u l t i o b j e e t i v ep r o g r a m m i n gp r o b - l e m si sd e r i v e db yt h ee n t r o p ys m o o t hm e t h o d f u r t h e r m o r e ，w h e na d d i n ga v e c t o rs e p a r a t e f u n c t i o np r o d u c e db yt h ec l o u s e ，n o r m a l ，s t r i c tc o n v e xf u n c t i o n ，t ot h ev e c t o rl a g r a n g i a n f u n c t i o n ，w ed e v e l o pt h ev e c t o rl a g r a n g i a ns m o o t ha p p r o a c hf o rm u l i o b j e c t i v ep r o g r a m - m i n gp r o b l e m sw i t hi n e q u a l i t yc o n s t r a i n t s a tl a s t ，u s i n gt h ev e c t o rl a g r a n g i a ns m o o t h a p p r o a c hf o rm u l t i o b j e c t i v ep r o g r a m m i n gp r o b l e m sw i t hi n e q u a l i t yc o n s t r a i n t s ，w eo f f e ra u n i f i e df r a m e w o r kf o rc o n s t r u c t i n gp e n a l t yf u n c t i o n so fm u l t i o b j e c t i v ep r o g r a m m i n gp r o b - l e m s 3 o p t i m a l i t yc o n d i t i o n sa n dd u a l i t yf o rt h r e ek i n d so fn o n s m o o t hm u l t i o b j e c t i v ef r a e - t i o n a lp r o g r a m m i n gp r o b l e m sa r ec o n s i d e r e d ( 1 ) f o rn o n s m o o t hm u t i o b j e e t i v ef r a c t i o n a lp r o g r a m m i n gp r o b l e m sw i t hi n e q u a l i t yc o n - s t r a i n t s ，w ei n t r o u c e dg e n e r a l i z e d ( f 0 ，p ，d ) - c o n v e xa n dg e n e r a h z e d ( f ，a ，p ，d ) 一v - c o n v e x i i i 多目标规划的若干理论和方法 c o n c e p t sb yc l a r k es u b d i f f e r e n t i a l u n d e rg e n e r a l i z e d ( f ) 口，p ，d ) 一c o n v e xa n dg e n e r a l i z e d ( f ，。，p ，d ) 一v c o n v e xc o n d i t i o n s ，o p t i m a l i t yc o n d i t i o n so fp a l e t oe f f i c i e n ts o l u t i o n sa r ee s t a b l i s h e df o rn o n s m o o t hm u l t i o b j e c t i v ef r a c t i o n a lp r o g r a m m i n gp r o b l e m s b - h r t h e r m o r e ，t h e m o n d w j i rt y p ed n a h t ym o d e l as e m i p a l a m e t r i cd u a l i t ym o d e la n dap a r a m e t r i cd u a l i t y m o d e la r ec o n s t r u c t e d f o re v e r yd u a l i 妙m o d e l ，a p p r o p r i a t ed u a l i t yt h e o r e m sa r ep r o v e d ( 2 ) ac l a s so fm u l t i o b j e c t i v ef r a c t i o n a lp r o g r a m m i n gp r o b l e m sa r es t u d i e d ，w h e r et h e i n v o l v e df u n c t i o n sa l el o c a ll i p s c h i t za n dc l a r k es u b d i f f e r e n t i a b i e f i r s t ，u n d e rg 一( f ，p ) c o n v e x i t y , t h ea l t e r n a t i v et h e o r e mi sp r o v e d m o r e o v e r ，s u f f i c i e n tc o n d i t i o na n dn e c e s s a r y c o n d i t i o nf o rap r o p e r l ye f f i c i e n ts o l u t i o ni nt h es e n s eo fg e o f f r i o na l ep r o v e d ( 3 ) n e c e s s a l ya n ds u f f i c i e n tc o n d i t i o n sa r ed e r i v e df o r 一w e a ke f f i d e n ts o l u t i o n so fn o n - d i f f e r e n t i a b l em u l t i o b j e c t i v ef r a c t i o n a lp r o g r a m m i n gp r o b l e m sw i t hn o n d i f f e r e n t i a b l eo b j c a - t i v ef u n c t i o n ss u n o c tt on o n d i f f e r e n t i a b l ec o n v e xi n e q u a l i t yc o n s t r a i n t s ，l i n e a re q u a l i t yc o n - s t r a i n t sa n da b s t r a c tc o n s t r a i n t sb y 一s u b d i f f e r e n t i a l b a s e do nt h e s e ，o n ep a r a m e t r i cd u a f i t y m o d e li sc o n s t r u c t e da n da p p r o p r i a t es - d u a l i t yt h e o r e m sa l ep r o v e d 4 o p t i m a l i t yc o n d i t i o n sf o rm u l t i o b j e c t i v ep r o g r a m m i n gp r o b l e m sh a v i n gf - c o n v e x o b j e c t i v ea n dc o n s t r a i n tf u n c t i o n sa r ei n v e s t i g a t e d a ne q u i v a l e n tm u l t i o b j e c t i v ep r o g r a m - m i n gp r o b l e mi sc o n s t r u c t e db yam o d i f i c a t i o no ft h eo b j e c t i v ef u n c t i o n f u r t h e r m o r e ，8 f l a g r a n g ef u n c t i o ni si n t r o d u c e df o rac o n s t r u c t e dm u l t i o b j e c t i v ep r o g r a m m i n gp r o b l e m ， a n dan e w t y p eo fs a d d l ep o i n ti si n t r o d u c e d a tl a s t ，t h er e l a t i o n sb e t w e e nt h en e wt y p eo f s a d d l ep o i n ta n dp r i m a lm u l t i o b j e c t i v ep r o g r a m m i n gp r o b l e ma r eg i v e n k e yw o r d s ：s m o o t hm e t h o d s ，m u l t i o b j e c t i v ep r o g r a m m i n g ，p e n a l t yf u n c t i o nm e t h o d s ， m u l t i o b j e c t i v ef r a c t i o n a lp r o g r a m m i n g ，o p t i m a l i t yc o n d i t i o n s ，d u a l i t y , p a r e t oe f f i c i e n ts o l u - t i o n ，g e o f f r i o np r o p e re f f i c i e n ts o l u t i o n ，g e n e r a l i z e d ( f ，日，p ，d ) 一c o n v e x ，g e n e r a l i z e d p ，d ) v - c o n v e x i v 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究工作 及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学 或其他单位的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名 多目标规划的若干理论和方法 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使 用规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和 电子版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇 编学位论文 保密口，在年解密后适用本授权书 本学位论文属于 不保密口 c 请在以上方框内打”) 作者签名：童】芝蛆 指导教师签名：堡璺函 1 0 2 大连理工大学博士学位论文 1 绪论 本章主要阐述多目标规划的发展概况，并介绍研究本文所需的预备 知识。在最后一部分介绍本文的工作以及获得的主要结果。 1 1 引言 人们在政治、经济和日常生活中常常需要作出决策。要作出好的决策，首先需要 给出判别决策好坏的标准。当只用一个目标作为判断决策好坏的标准时，人们应设法 选择使这一目标在某种意义下达到“最优”的决策。这类决策问题就是传统的单目标 规划问题。但在现实世界中，衡量一个决策优劣的指标往往不止一个，一般需要多个 指标来衡量，而这些指标之间又常常是相互矛盾的。如何协调这些矛盾，兼顾各个指 标，选出最满意的方案，是人们在现实生活中经常遇到的难题，多目标规划因此应运 产生。多目标规划问题出现在许多领域中，例如，在水资源分配这个范围内，多种用途 的水库的经营，可以要求灌溉和为附近居民点提供电力，同时还要保持水库本身和下 游的最低水位，以适应环境和娱乐的要求。而这些目标实际上可能是互相冲突的，要 同时满足它们往往是矛盾的。所以，多目标规戈问题，总是以牺牲一部分目标的利益 来换取另一些目标的利益的改善，正如v o nn e u m a n 和m o r g e n s t e r n 1 ，2 1 指出的：“这 种多目标的情形，肯定是无最优值的问题，而是几个相互冲突的最优问题特有的和扰 人的混合这一类问题不能用传统数学方法来处理”这就是多目标规划 问题的基本性质之一。 多目标规划的理论要涉及多门现代数学学科，如凸分析、非光滑分析和随机分析 等。它的求解方法，则常借助于线性规划、非线性规划、随机规划以及数值计算的手 段和技巧。目前，多目标规划无论在理论研究、求解方法，还是应用方面都取得了重 要的进展，使它成为一门庞大的学科。多目标规划包括广泛和丰富的内容。多目标规 划问题也称为：多目标优化问题或向量优化问题或向量极值问题，它与只含有一个数 值目标函数的单目标规划问题不同。在一般情况下并不存在最优解。因此，多目标规 划理论的研究包括以下几个方面：( 1 ) 解的定义。由于多目标规划的目标不只一个， 如何定界多目标最优化解的概念成为一个首要问题。( 2 ) 对于各类解的最优性条件的 多目标规划的若干理论和方法 研究，是多目标规划中一个重要和基本的课题。所谓解的最优性条件，就是在某种意 义下所考虑的解要满足的必要和充分条件。它不仅可以用来判断一个可行解是否为所 考虑意义下的最优解( 因此被广泛地用于设计求解的算法) ，还可以通过它来讨论稳 定性理论等。( 3 ) 解的连通性。多目标规划的解通常不唯一，而是一个集合，所以讨论 解集的连通性，成为一个重要的研究方向。( 4 ) 对偶性。对偶理论的内容非常丰富， 是多目标规划这门学科的重要组成部分，它在多目标规划的理论研究和应用研究中 都扮演着十分重要的角色。但到目前为此，对偶理论的整个内容还不成熟，正处在充 实和发展阶段，有许多课题尚待人们进行研究。( 5 ) 稳定性。稳定性是多目标规划理 论中一个重要的研究领域。由于多目标规划具有不同于单目标规划的某些特殊性，使 得这方面的研究呈现复杂多样的特点。众所周知，非线性规戈的扰动主要是指扰动解 的连续性、可微性等性质。而在多目标规划中，解的概念要依赖于控制结构的选择， 因而，其扰动除了涉及可行集和目标函数外，还要考虑控制结构的扰动。此外，又由 于多目标规划解的多样性( 如有效解，弱有效解，真有效解，较多有效解等) 以及稳 定性的多样性( 如上、下半连续，次可微，l i p s c h i t z 连续等) ，使这方面的研究成为一 个多姿多彩的领域。( 6 ) 求解方法。多目标规划的求解方法，则常借助于线性规划、 非线性规划、随机规划以及数值计算的手段和技巧。 本文只对多目标规划的一些方面进行研究，主要研究多目标规戈d 的的最优性条 件和对偶性，以及多目标规划的求解方法。 1 2 多目标规划的发展概况 多目标规划的思想萌芽于1 7 7 6 年经济学中关于效用理论的研究。1 8 9 6 年，经济 学家p a x e t o 3 首先在经济平衡的研究中提出了多目标规划问题，并给出了后来称之为 p a r e t o 最优解的朴素思想。1 9 4 7 年，v o nn e u m a n 和m o r g e n s t e r n 4 j 在对策论的著作中 提到了多目标规划f 习题，引起了人们对多目标规划的重视。1 9 5 1 年，k o o p m a n s 5 】在 生产与分配的活动分析中提出了多目标最优化问题，并第一次提出了p a r e t o 最优解 的概念。同年，k u h n 和t u c k e r 6 1 从数学规划的角度，给出了向量极值问题的p a r e t o 最优解的概念，并研究了这种解存在的充分条件和必要条件。1 9 5 4 年d e b r e u 7 有关 评价均衡的讨论，以及1 9 5 8 年h a r w i c z 8 1 对拓扑向量空间中的多目标最优化问题的 研究，都为这门学科的建立奠定了坚实的基础。1 9 6 8 年，j o h n s e n 9 出版了关于多目 标决策模型的第一部专著。从此，不少学者先后转入这一研究领域，并取得了许多成 果。直到2 0 世纪7 0 年代到8 0 年代，经过众多学者的努力，终于建立起多目标规划的 2 大连理工大学博士学位论文 基本理论，使之成为应用数学的一个新的学科分支。下面介绍本文涉及到的多目标规 划有关方面的发展概况。 1 2 1 解的最优性条件 在k u l m 和t u c k e r 6 的开拓性工作之后，国内外许多学者致力于多目标规划最 优性条件的研究，取得了许多重要的成果。1 9 7 6 年，对于有限维多目标规划问题的 p a r e t o 有效解，l m l l 0 1 首先给出了它的f r i t zj o h n 必要条件和k u h n - t u c k e r 必要条件。 此后，在1 9 7 7 年，b o r w e i n 1 1 1 利用切锥给出了一个最优性条件。在l i n 工作的基础 上，林锉云f 1 2 ，1 3 ，1 5 j 从1 9 8 2 年开始，利用特定的向量函数和次线性泛函等工具，给 出了在广义拟凸和广义伪凸下的若干充要条件和充分条件。应玫茜 1 6 】利用伪凸性， 建立了解的若干充要条件和判别准则。在1 9 8 9 年，c o m b i n i 和m a r t e i n 1 7 给出了关于 凸锥的有效解的f r i t z - j o h n 型条件，考虑的空间是实的线性空间。同年，刘三阳【6 6 利 用d i n i 导数，建立了非光滑多目标规划的f r i t z - j o h n 型条件。在1 9 9 0 年，胡毓达和孙 尔江 1 8 】在对目标函数和约束函数上加上适当凸性的条件下，得到了几个f r i t z - j h o n 型充分条件。在f j 型条件中，为了保证关于目标函数的梯度的系数不为零以使之确 实具备最优性条件的功能，应对目标函数附加一定的约束规格。l i n 1 0 给出了k - t 约 束规格下多目标规划的最优性k u h n - t u c k e r 条件。s i g h n 2 0 利用收敛向量集的概念， 给出了多目标可微规划一种非k - t 约束规格的k u h n - t u c k e r 条件。w a n g 和d o n g 2 1 】 用s i g h n 的方法，给出了非光滑多目标规划的一种约束规格。m a e d a 2 2 利用线性锥 和切锥给出了可微多目标规划k t 必要条件成立的约束规格。l i 2 3 】通过引进有限个 凸集并的核的概念，给出了非光滑多目标强k t 条件成立的约束规格。胡毓达【2 4 - 2 6 】 在讨论较多有效解类时也得到了几个最优性条件。关于无限维空间的情况，对最优性 条件的研究成果则较少。对b a n a h 空间多目标规划问题锥有效解的最优性条件，陈 广亚【2 7 曾得到若干结果。对于拓扑向量空间的情况，李泽民【2 9 】借助j e y a c u m a r 2 8 的次拟凸概念，讨论了f r i t z - j o h n 型必要条件，并给出了一个鞍点条件。之后，胡毓达 3 0 】引进广义约束规格，进一步得到了拓扑向量空间中锥弱有效解的k u l m - t t l c k e r 最 优性必要条件，同时还在锥凸的假设下证明了锥有效解和锥弱有效解的几个充分条 件。b r a n d o ，r o j a s m m e d a r 和s i l v a 3 1 1 给出了b a n a c h 空间中非凸非光滑向量最优化 问题的最优性条件。 1 2 2 对偶性 3 多目标规划的若干理论和方法 在1 9 5 1 年，g a l e ，k u h n 和t u c k e r 3 2 】第一次给出了关于向量最优化的对偶性的有 关结果。他们建立了线性多目标规划的对偶定理。后来，k o r n b l u t h 3 3 ，r o d d e r 3 4 和 i s e r m a n n 3 5 3 6 进一步发展了线性多目标规划的对偶定理。 i s e r m a n n 3 7 首先给出了g a l e ，k u h n 和t u c k e r ，i s e r m a n n 和k o m b l u t h 的对偶概念 之间的关系。在【3 8 中，i v a u o v 和n e h s e 研究了线性多目标最优化中一些对偶概念之 间的关系，即g a l e ，k u t m 和t u c k e r 3 2 ，i s e r m a n n 3 5 3 6 ，r o d d e r 3 4 】和f i a l a 4 0 所提出 的对偶概念之间的关系。最近c a l p e r i u 和j i m e n e z 4 1 1 用另一种方法研究了线性多目标 最优化的对偶问题，该方法是以g a l p e r i n 4 2 1 的平衡集方法为基础的。 关于非线性向量最优化问题，其对偶理论是很丰富的。目前讨论较多的有l a g r a n g e 对偶模型、m o n d w e i r 对偶模型、共轭对偶模型等等。在l a g r a n g e 对偶理论方面， 1 9 7 9 年，t a n i n o 4 3 等人根据单目标规划情形w o l f e 对偶模型的框架，通过引入所谓 的向量l a g r a n g e 函数提出了多目标规划的l a g r a n g e 对偶模型，并证明了当原问题是 凸规划问题时，原问题和l a g r a n g e 对偶模型的有效解是对偶的。此后，林锉云【4 4 4 6 进一步推广了上述结果，证明了条件减弱为广义凸性条件( 如伪凸、拟凸、i n v e x 凸等 等) 时，原问题和对偶问题的有效解的对偶性仍然成立。1 9 9 3 午李仲飞和汪寿阳 4 7 则讨论了有限维空间中基于尖闭凸锥内部( 即锥弱有效解) 的l a g r a n g e 对偶问题。 1 9 8 1 年，m o n d 和w e i r 4 8 给出了多目标规划问题的另一种对偶模型，这种模型一出 来，就引起了广大学者的极大兴趣，他们对l a g r a n g e 对偶模型进行了修改，简化了 目标函数，增加了约束条件，并证明了有效解之间的对偶性。我们把这种对偶模型称 为m o n d - w e i r 对偶模型。在多目标规划的共轭对偶理论方面，在1 9 7 9 年，t a n i n o 和 s a w a r a g i 4 3 用共轭映射的概念研究了向量最优化问题的对偶。实际上，他们通过对向 量映射和集值映射引入新的概念一共轭映射和次梯度，把由r o c k a s e l l a r 7 5 1 所得到的 单耳标规划的对偶理论扩展到多目标规划。此后，许多学者对集值最优化问题( 集值 最优化问题是向量最优化问题的推广) 引入了不同的共轭对偶理论。1 9 8 0 年t a n i n o 和s a w a r a g i 5 0 给出了有限维空间中基于正锥( 即p a r e t o 有效解) 的共轭对偶结果，其 特点是：利用共轭函数及性质来建立对偶问题，并证明了对偶定理。1 9 8 1 年和1 9 8 2 年k a w a s a k i 5 1 5 2 1 讨论了有限维空间中基于正锥内部( 即p a r e t o 弱有效解) 的共轭对 偶问题，1 9 8 8 年汪寿阳f 5 3 1 则建立了b a n a c h 空间中基于尖闭凸锥( 即锥有效解) 的 共轭对偶理论。最近，h u a n g 和y a n g 5 4 】以及s i n g h ，b h a t i a ，和r u e d a 5 5 通过增广拉 格朗日函数建立了其对偶模型，并证明了对偶定理；o s u n a - g o m e z ，r u f i a n - l i z a n a 和 r u i z - c a n a l e s 5 6 讨论了具有广义次似凸函数的不可微多目标规划问题的l a g r a n g e 对 4 大连理工大学博士学位论文 偶；s a n t a ，l a l i t h a ，s e e m a k h u r a n a 5 7 】建立了多目标规划的二阶对称对偶模型，并在 ，卜二阶凸和叩一伪二阶凸的条件下，证明了弱对偶定理、强对偶定理和逆对偶定理； g e r t 和r a d u 5 8 用f e n c h e l - r o c k e r f e l l a r 对偶理论导出了约束条件为线性不等式约束、 目标函数为凸函数的平方与凹函数之商的多目标规划的对偶问题；t a r m i n e n 5 9 给出 了凸多目标规划偏爱解的对偶理论。 1 2 3 多目标最优化方法 在求解多目标规划问题的方法方面，按h u a n g 和m a s u d 6 0 于1 9 7 9 年提出的由决 策者的偏爱信息的表达方式来划分的原则，可分成以下三类：事先评价法，事中评价 法和事后评价法。 事先评价法要求决策者在求解多目标规划问题之前，一次性提供全部偏爱信息， 它主要有评价函数法和目标规划法。评价函数就是决策者事先给出关于多个目标的评 价函数，从而将多目标最优化问题转化为单目标规划问题。最典型的评价函数法有线 性加权法、极大极小法和理想点法，参见 6 1 】。目标规划法【6 2 则是由决策者事先给 出每个目标函数的目标函数值组成目标向量，然后将多目标规划问题，转化为对向量 目标函数与目标向量之间在某种意义下的距离的极小化问题。 事中评价法即交互规划算法，其特点是：在求解过程中决策人通过与分析人( 或 计算机) 之间的对话逐步给出其偏好信息，直至决策人在某步迭代时对分析人提供的 某个解满意为止。自1 9 7 1 年b e n a y o u n 6 3 】等提出第一个交互规划算法以来，关于这类 算法的研究已得到了快速的发展。 事后评价法的特点是，寻求多目标问题的所有( 或大多数) 的有效解，然后把这 些解送给决策人，由他从其中选择一个最合意的解。事后评价法是其它两种方法的基 础。它的主要方法有二变权线性加权法 6 4 】， 约束法 6 5 】，多目标线性规划法f 9 9 】，同 伦法【6 7 ，广义同伦法【6 8 ，与边界垂直相交法 6 9 。特别值得一提的是我国学者在多 目标算法方面做了许多工作，取得了不少引人注目的成果。主要有：施保昌、于寅【7 0 的“一类不可微多目标决策问题的可行方向法”；张乐友、刘三阳【7 1 的“多目标规划 的光滑同伦方法”；孟红云、刘三阳 1 2 0 的“求解多目标优化问题的多智能体遗传算 法”还有旆保昌、陈铤【7 2 】的“多目标的一类基于精确罚函数的交互式方法”以及刘 庆怀、林正华f 7 3 】的“求解多目标最小弱有效解的同伦内点法”等研究工作。 1 3 预备知识 5 多目标规划的若干理论和方法 1 3 1 连续函数的基本概念及性质 本节介绍连续函数的一些性质及方向导数、次微分等概念，这是研究不可微优化 问题的基本工具。 定义1 3 1 设p 是实赋范空间 ( a ) ) 墨。是”中的点列，如果 l i mi l 。一矿0 = 0 那么称 甄) 墨。收敛于矿，即当i 一。时，珑一矿，矿称为 戤, 】忙o o o 的极限点； ( b ) 戤) 墨。是v 中的点列，如果存在子集k c n = 1 ，2 ，) ，使得对每个子列 甄 t e k ， ；+ 曼耳慨一矿0 = o 那么称矿为 研) 罂。的聚点，记为当i p o 时，鼢5 矿，或l i m k 2 ：t = 矿。 定理1 3 1 假设xc 舻是闭有界集，那么x 是紧集。 推论1 3 1 假设 甄) o = 0 0 是瓣”中的有界点列，如果 峨) t o 卸。仅有一个聚点矿，那么它 收敛于矿。 定理1 3 2 假设 规) ：吕是瓣中的点列，且茁o 。1 2 ：2 ( 即点列是单调递减的) 。 如果 戤) 罂。有聚点矿，那么当i o 。时，缸一矿，即矿是极限点。 证明：见文献【1 2 1 】中的命题5 1 1 6 。 推论1 3 2 假设 。t ) 函是蹰中单调下降的点列，如果存在b 瓣，使得对所有的 i n ，甄b ，那么 冠) 罂。收敛于矿驼。 定义1 3 2 设是实赋范空闻 ( a ) 函数，：j _ 驼在点x 处是上半连续的( u p p e rs e m i c o n t i n u o u s ) ，如果对v d 0 ， 存在p 0 ，使得 ，( 一) 一f ( x ) 0 ，使得 ，( z 7 ) 一，( 。) - - 5 ,v x e b ( 。，p )( 1 3 2 ) 6 大连理工大学博士学位论文 定理1 3 3 设v 是实赋范空间 ( a ) 函数f ：v 一蛇在矿上半连续，当且仅当点列 翰) 函c ，当i o 。时，观一矿 l i m f ( x _ ) 墨f ( x + ) ； ( b ) 函数，：i ，一虢在矿下半连续，当且仅当点列 瓤) 罂oc 扩，当i o 。时，甄一矿 ! 立旦，( 观) f ( x + ) 。 定义1 3 3 设b 是实b a n a c h 空间，f ：b 一妒， ( a ) 。，h 召， f ( x ；h ) 垒l 。h n 迎掣 ( 1 3 r 3 ) 这里t 0 。若极限存在，称，( 。；h ) 为，( ) 在。处沿方向 的方向导数 ( b ) 若对v h 8 ，方向导数，( 而h ) 存在，则称，( ) 在z 处方向可微； ( c ) 矿，h b ，。( z ；h ) 垒匾州。f ( x t + t h ) - - f 一( x ) ( 1 删 若上式极限存在，则称为，( ) 在矿处沿方向h 的c l a r k e 方向导数或称为广义方向导 数。 当f ：b 一瓣是局部l i p s c h i t z 连续的，它的c l a r k e 方向导数存在，但是方向导数不 一定存在。若f ：b 一瞬的方向导数与c l a r k e 方向导数都存在，则f o ( z ；h ) ，( 为h ) 。 又若v x , h b ，f o = ，( h ) ，则称，( ) 是c l a r k e 正则的，简称为正则的。 定义1 3 4 嚣是实b a n a c h 空问，假设f ：廖一瓣，比，h 舀，c l a r k e 方向导数，。( z ；h ) 存在，定义，( ) 在。召的c l a r k e 次微分o 。f ( x ) c 召如下 a 。，( z ) 垒 舀i ，。( z ；h ) 任，危) ，v h 8 )( 1 3 5 ) 下面我们给出极大值函数 妒( z ) 垒啦x 尸( 。) ( 1 3 6 ) j c q 的一些性质。其中f j ：舻一驼，j = 1 ，2 ，g ，q 竺 l ，2 ，订。对v 。舻，定义 白( 。) 竺 j qi ，( 。) = 1 】c ( 茁) ( 1 3 7 ) 定理1 3 4 函数妒( ) 如( 1 3 6 ) 式定义，这里，：舻一跪，j q ，是局部l i p s c h i t z 连 续的，且v 。，h 渺，方向导数( ；哟存在。那么 ( a ) 妒( ) 是局部l i p s c h i t z 连续的； 7 多目标规划的若干理论和方法 ( b ) 护妒( 。) cc o o 。户( z ) ，j 矗( z ) ) 这里日( z )