（运筹学与控制论专业论文）集值向量优化问题的共轭对偶.pdf

大连理工大学硕学位论文 摘要 共轭对偶是多目标优化理论中的一类重要问题，其特点是利用共轭函数来建 立原问题的对偶问题，并利用共轭函数的性质来证明各种对偶定理。而共轭函数 概念有着鲜明的经济意义。本文基予偏痔的定义，主要从有限维和无限维两个方 面来研究集值多目标优化的共轭对偶问题。本文取得的结果可概括如下： 王。第一、二章中首先介绍了多雷标优化理论的发震状况，其次介绍? 共辘对儡 的主要进展，最后在前人的研究基础上我们得到启示，进而有了本文的构 思。 2 第三章考虑的是有限维集值向量优化的共轭对偶问题。对集值向量优化问题 提出新的扰动函数：r nx 形曩r pu f 1 l ， ( 搿，) ： ，( z ) + 【 p ，z 。：x ，9 ( z ) 碑u l o 。o e ，o e 7 w z s e ， ( z ，0 ) = ，( 搿) 给出耀应的共轭对偶规划，得到对偶定理。值得提到的是弱对偶定理不需要 任何条件都成立，而本章要求外部稳定的目的是要简化结果。并在稳定性假 设的前提下，使在弱强对偶理论中的结果形式更简单，更一般化，更方便于 应震。 3 第四章考虑的是无限维集值向量优化的共轭对偶问题。对集值向量优化问题 采用掰的扰动丞数参( 2 ，z ) = f ( x z j ，绘出相应的共轭对偶闻题，并褥到对 偶定理。其中我们得到两个很好的引理，即若目标函数是s 一凸的，则扰动 函数也是s 一凸的：若圈标函数是次可加的，则扰动函数关于自变量也是次 可加的。接着在雷标番数满足次可加性的前提下，证明了原问题和对偶闯题 的对偶间隙为0 。最后，我们弱化了强对偶定理得到一个结论即对偶间隙不 为空集的充分必要条件。 4 第五章总结结论。 关键词：共轭对偶；扰动函数；外部稳定；次可微；稳定 大连理工大学硕士学位论文 c o n ju g a t ed u a l i t yi ns e t v a l u e dv e c t o ro p t i m i z a t i o n a b s t r a c t c o n j u g a t ed u a l i t yi sa c l a s so fi m p o r t a n ti s s u e si nv e c t o ro p t i m i z a t i o n i ti s c h a r a c t e r i s t i co fu s i n gt h ec o n j u g a t ef u n c t i o nt oc o n s t r u c tt h ed u a lp r o b l e m ，a n d u s i n gt h ep r o p e r t i e so fc o n j u g a t ef u n c t i o nt op r o v ed u a l i t yt h e o r e m s b a s e do i l t h ed e f i n i t i o no ft h ep a r t i a l l yo r d e r i n g ，w ec o n s i d e rc o n j u g a t ed u a l i t yt h e o r e m so f s e t v a l u e dv e c t o ro p t i m i z a t i o ni nf i n i t ea n di n f i n i t ed i m e n s i o n a ls p a c e s t h em a i n r e s u l t sc a l lb es u m m a r i z e da sf o l l o w s ： 1 i nc h a p t e r1a n d2 ，w ef i r s t l yi n t r o d u c et h ed e v e l o p m e n to ft h ev e c t o ro p t g m i z a t i o nt h e o r y , t h e nt h em a i np r o g r e s si nc o n j u g a t ed u a l i t y , a n db a s e do nt h e r e s e a r c ho fs p e c i a l i s t sa n ds c h o l a r s ，w ed e s i g nt h i sp a p e r 2 i nc h a p t e r3 ，w ec o n s i d e rc o n j u g a t ed u a l i t yt h e o r e mo fs e t v a l u e dv e c t o ro p t g m i z a t i o ni nf i n i t ed i m e n s i o n a ls p a c e s n e wp e r t u r b a t i o nf u n c t i o ni sp r e s e n t e d f o rac l a s so fs e t v a l u e dv e c t o ro p t i m i z a t i o n ，：毋x 毋jr pu ) - ， 纰= 等hk 。k 一，x g o t l z e r w z s e ， 座叩 i ， ， 砂( z ，0 ) = ，( z ) i no r d e rt oo b t a i nc o r r e s p o n d i n gc o n j u g a t ed u a l i t yo p t i m i z a t i o na n dd u a l i t y t h e o r e m s i ts h o u l db em e n t i o n e dt h a ti nt h eg e n e r a lc o n j u g a t ed u a l i t yt h e o r y t h ew e a kd u a l i t ya s s e r t i o ni sf u l f i h e dw i t h o u ta n ya s s u m p t i o n s b u ti no u r w e a kd u a l i t yt h e o r e mi tr e q u i r e st h ee x t e r n a l l ys t a b i l i t yi no r d e rt os i m p l i f y t h er e s u l t w 色s h o wu n d e ras t a b i l i t yc r i t e r i at h a tt h ef o r mo fw e a ka n ds t r o n g d u a l i t yb e c o m e ss i m p l e ，g e n e r a la n dc o n v e n i e n ti na p p l i c a t i o n s 3 i nc h a p t e r4 ，w ec o n s i d e rt h ec o n j u g a t ed u a l i t yp r o b l e mo fs e t - v a l u e dv e c - t o ro p t i m i z a t i o ni ni n f i n i t ed i m e n s i o n a ls p a c e s n e wp e r t u r b a t i o nf u n c t i o n 咖( z ，z ) = f ( x z ) i sp r e s e n t e df o rac l a s so fs e t v a l u e dv e c t o ro p t i m i z a t i o n ， o b t a i n e dc o r r e s p o n d i n gc o n j u g a t ed u a l i t yo p t i m i z a t i o n ，a n dd u a l i t yt h e o r e m s f u r t h e r m o r ew eg e tt w ol e m m a s ，i e ，( 1 ) i fo b j e c t i v ef u n c t i o ni ss c o n v e x ，t h e n p e r t u r b a t i o nf u n c t i o ni sa l s os - c o n v e x ；( 2 ) i fo b j e c t i v ef u n c t i o ni ss u b - a d d i t i o n ， t h e np e r t u r b a t i o nf u n c t i o ni sa l s os u b - a d d i t i o n m o r e o v e ru n d e rs u b - a d d i t i o n i i i 集值向量优化问题的共轭对偶 o fo b j e c t i v ef u n c t i o nh y p o t h e s e s ，w ep r o v i d e st h a tt h ed u a lg a pi sz e r ob e t w e e n t h ep r i m a lp r o b l e ma n dt h ed u a lp r o b l e m f i n a l l y ，t h es u f f i c i e n ta n dn e c e s s a r y c o n d i t i o no fd u a lg a pi sp r o v e d 4 i nc h a p t e r5 w es u m m a r i z et h ep a p e r k e yw o r d s ： c o n j u g a t ed u a l i t y ；p e r t u r b a t i o nf u n c t i o n ；e x t e r n a l l ys t a b l e ；s u b - d i f f e r e n t i a l ；s t a b i l i t y 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的 研究工作及取得研究成果。尽我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也 不包含为获得大连理工大学或其他单位的学位或证书所使用过的材 料。与我一同工作的同志对本研究所做的贡献均已在论文中做了明 确的说明并表示了谢意。 作者签名：霉擀日期：- 二礁删 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文是作者及指导教师完全了解“大连理工大学硕士、 博士学位论文版权使用规定，同意大连理工大学保留并向国家有关 部门或机构送交学位论文的复印件和电子版，允许论文被查阅和借 阅本人授权大连理工大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和 汇编学位论文 作者龇立撵 新虢埤 迎星年l 月l 日 大连理工大学硕士学位论文 1 绪论 l 。l多目标优化及其对偶理论的发展状况 1 1 1 多髓标概述 我们知道，在线性规划和非线性规划中，所研究的问题都只包含一个目标函 数，这类问题常称为单目标优化问题。但在工程技术，生产管理以及国防建设等 部门中，所遇到静闯题往往需要同时考虑多个西标在莱种意义下的最优溜题，我 们习惯称之为多因标规划( 优化) 。一般地，多目标优化问题可描述为 羹中x x ，f ( x 1 y ，x ，y 为拓扑向量空闻。多目标最优化闻题的研究最早可追 溯到1 7 7 2 年，当时f r a n k l i n 提出了多目标矛盾如何协调的问题。c o u r n o t 在1 8 3 6 年 从经济学角度提出了多目标问题的模型。但国际上一般认为多目标最优化 闻题最早是壶法国经济学家v 。p a r e t o 在1 8 9 6 年提出的。他扶政治经济学的焦 度，把许多不好比较的目标归纳成多目标最优化问题。1 9 4 4 年，v o n n e u m a n n 和j m o r g e n s t e r n 又从对策论( 博弈论) 的角度，提出多个决策耆而彼此又相互矛 盾的多目标决策问题。1 9 5 1 年，t 。c 。k o o p m a n s 从生产与分配的活动分砉斥中提出 了多目标最优化问题，并第一次提出了p a r e t o 最优解的概念。同年，h w k u h n 和a w t u c k e r 从数学规划的凫度，给出了向量极值问题的p a r e t o 最优解的概念， 并研究了这种解的充分与必要条件。1 9 5 3 年，a r r o n 等人对凸集提出了有效点的概 念，多目标决策( 多目标规划) 问题逐渐受到人们的关注。1 9 7 0 年，享有“动态 飙划之父”盛誉的b e l l m a n 教授与z a d e h 教授在多唇标决策的基礁上，合作提出了 模糊决策的基础模型。现在，多目标决策问题已成为运筹学和管理科学重要分支 之一。 多西标优化阀题有许多共圊豹特点，最显著熬是：雷标闻的不可公度性和霹 1 集值向量优化问题的共轭对偶 标间的矛盾性。所谓目标间的不可公度性是指各个目标没有统一的度量标准，因 而难以进行比较。目标间的矛盾性是指如果采用某一种方案去改进某一目标值， 可能会使另一目标的值变好或变坏。因此，在多目标优化中，通常不存在能使得 所有目标函数同时得到最优解，即绝对最优解一般不存在，此时需要考虑另一种 解的概念一一有效解( 或非劣解) 。由于有效解集中的有效解的数目比较多，故又 出现问题：如何根据决策者的主观价值判断对有效解进行好坏比较? 这就引入偏 好序。所以我们讨论的多目标问题都是在定义了偏序的基础上进行的。本文所研 究的集值多目标优化是多目标优化的一大部分，是相对于单值多目标而言的，其 中目标函数是集合到集合的映射。这就需要重新定义最值，我们所采用的是集值 映射的最大最小值集合，下文将详细叙述。 1 1 2 对偶理论概述 多目标最优化问题涉及的范围很广泛，但主要研究方向有四个。首先是如何 衡量目标函数的好坏，即关于各种有效解和弱有效解的问题，包括解的性质，存 在性，最优性条件，稳定性等。其中陈光亚在一般实模向量空间中研究了有效点 的几何性质，并且用标量化的方法研究解的存在性。1 9 7 8 年，胡毓达等在一般拓 扑向量空间中引入锥拟凸m i n k o w s k i 泛函，解决了解集和象集的连通性。稳定性方 面有魏权龄，应玖茜发表的“多目标数学规划的稳定性等等。 其次是关于多目标规划的解法。这个问题可分为直接算法和间接算法。直接 算法的研究比较少，其中研究的几种有：单变量多目标规划算法，线性多目标规 划算法以及可行集有限时的优序法等间接算法是把多目标问题转化为单目标问 题。目前我所看到的计算方法有：评价函数法，目标规划法，分层序列法，交互 规划法和隶属函数法，具体方法参见3 5 1 。 第三个研究方向是对偶问题，可分为两大类：l a g r a u g e ：对偶和共轭对偶。其 中学者t a n i n o ，e e r o s i n g e r 和d t l u s 的工作最突出。特别在研究多目标的对称 对偶和自身对偶，林锉云做了大量工作。 第四为不可微多目标规划的研究。而本文研究的问题就属于第三部分。对偶 理论是指：同时讨论一对规划问题之间的重要关系之理论。它在多目标中占有重 要地位，对求解以及最优性条件的揭示等都起着重要作用，而且由于对偶性有其 客观存在的实际背景，因此它在生产实际中也有重要的应用价值。 我们称一对多目标最优化问题关于某种含义的最优解( 如有效解或弱有效解 等) 是对偶的，是指它们满足如下条件： 1 它们中一个是极小化问题，另一个是极大化问题； 2 极小化问题的任一可行解之相应目标函数值总是不小于极大化问题的任一可 行解之相应目标函数值； 2 大连理工大学硕士学位论文 3 它们中若一个问题存在某种含义的最优解，则另一个问题也一定存在该含义 的最优解，而且相应的最优目标函数值相等。 我们称对偶的两个多目标最优化问题中的一个为原问题，另一个为对偶问 题。对偶理论的主要内容是：给定原问题之后，如何建立其相应的对偶问题，使 其满足上述三个条件。其中第一条件在建立对偶问题时自然就做到了，而第二个 和第三个条件的验证是比较困难的。在对偶问题中，第二个条件叙述为弱对偶定 理，而把第三个条件叙述为强对偶定理，或者分述为直接对偶与逆对偶两个定 理。对偶理论实际上就是证明这几个对偶定理。共轭对偶是对偶问题的重要研究 方向，其特点是利用共轭函数构建原问题的对偶问题，并利用共轭函数的性质来 证明各种对偶定理。 1 2共轭对偶 而本文研究的共轭对偶则是在集值多目标优化的范围。共轭对偶在解 决优化问题上展现了其独特的优势。其主要思想为：把原问题m i nf ( x ) 嵌 入到一族优化问题中，即构造扰动问题m i n 西( x ，u ，u ) ，其中u ，移为扰动变量。 当u = 0 ，v = 0 时，f ( x ) = 西( x ，0 ，0 ) ，也就是说原问题等价于m a n 西( x ，0 ，0 ) ， 然后利用扰动函数西( x ，u ，u ) 的共轭函数矽( 丁，a ，b ) 建立原问题的共轭对偶问 题m a x l u a b 【一矿( o ，a ，b ) ) 。 对于集值向量优化问题而言，由于没有经典定义下大小的比较关 系，使得它的共轭对偶问题变得相对复杂。以下介绍共轭对偶的主要进 展。1 9 7 4 年r o c k a f e l l a r 6 首先解决了单目标优化的共轭对偶问题，并给出了一 般框架，即利用其所定义的共轭函数得到原问题的对偶问题，并利用共轭函 数的凸性质来证明各种对偶定理。随后，t a n i n o 和s a w a x a g i 2 0 ，2 1 将共轭对偶问 题推广到有限维空间的多目标优化问题，进一步地p o s t o l i c a 7 对无穷维多目标 规划的对偶问题进行了研究。但以上所考虑的问题都是目标函数为单值的情 况。t a n i n o 1 5 在偏序拓扑向量空间上，基于弱有效解定义了集合的最大值，进而 得到了集值多目标优化的共轭对偶，但其中稳定性准则只在有限维空间成立。接 着s o n g 1 3 讨论了无限维情况下的凸集值多目标优化的共轭对偶，但要求目标函 数是闭有界的，条件要求很强。 e k e l a n d 8 1 9 从所谓的扰动逼近角度考虑了有限维空间中的集值单目标规划的 共轭对偶情况。而b o t 和w a n k a 1 0 ，1 1 采用如下形式的扰动函数给出了集值向量 优化的l a g r a n g e ，f e n c h e l $ 口f e n c h e l - l a g r a n g e 对偶。若扰动函数为 砂( z ，乱) = 篓_ lz o t h ，e x r w z ? s e z ，碑让 i ， 3 集值向量优化问题的共轭对偶 其中l ( z ，0 ) = ， ) ，则这个函数对应于l a g r a n g e 对偶。若扰动函数是 也( z ， ) = 。f ( x ，+ 口lz o t h ，e g r w ? z s e - j y i 夕z 碑。 i o o ， 其中2 ( z ，0 ) = ， ) ，那么这个函数对应于f e n c h e l 对偶。而当扰动函数是 3 ( z ，口，u ) = f ( x + 秽) 。x 亡 e e x r , i g s ( e x ，) 碑u 其中3 ( z ，0 ，0 ) = ， ) ，则这个函数对应于f e n c h e l l a g r a n g e 对偶。利用以上的 扰动函数，t a n i n o v 和s a w a r a g i 2 ，【2 0 在有限维空间中基于p a u r e t o 有效解引入i - f e n c h e l 变换，发展了集值多目标规化的共轭对偶。在用扰动函数讨论共轭对偶的 思想基础上，a l t a n g e r e l ，b o t s q w a n k a 1 研究了下面向量优化问题的共轭对偶 ( y d ) 黜m i n m ) iz g ) 其中，：舻j 舻u _ f o o ) 是广义向量值函数。o 。是想象的点，它的每个分量是+ o 。， g = z xg ( x ) 兄2o ) ，xc 舻，u 形，g ( x ) 册，并得到了强弱对偶定 理，但结论形式相对复杂，不容易判断。这是有限维的情况，对于无限维的问题 我们主要在s o n g 1 3 的基础上讨论的。其研究的原问题为 ( p ) 熙f ( z ) 其中f ：xjy u + ) ，d o m f 0 ，是集值映射，x ，y 是实拓扑向量空间。1 3 1 中 研究了一些稳定性准则，且在闭有界的假设下，得到c o n v e x h k e 集值向量优化的对 偶结论，而在没有闭有界的要求下，只能得到凸集值向量优化的共轭对偶问题。 这篇文章中所要求的条件比较强，一般情况下目标函数也不容易满足闭有界的假 设。 1 3 本文的主要工作 基于以上内容，第二章针对问题( v o ) 通过提出一类新的扰动函数：舻x 舻j 伊u ) ， ( 训) ： m ) + 锄，d 】p x e ，x 夕( z ) 霹钍 l0 0 ，o t t m r w o s e ， ( z ，0 ) = ，( z ) 其中 】p 表示p 维列向量，每个分量为 。进而得到共轭对偶问题及 其相应的对偶定理。在分析过程中考虑约束集使得扰动函数的自变量和扰动变量 4 大连理工大学硕士学位论文 易于分离，这样变形后的共轭对偶与原对偶等价。一般情况下，弱对偶定理不需 要任何条件都成立。本文在弱对偶定理中要求外部稳定目的是要求简化结果。若 再结合外部稳定的假设条件，我们得到了集值问题的对偶定理的很好的结论。相 对于f 1 1 的结论，我们的结果有更一般化的形式，且表达式简单，方便于应用。同时， 所用的条件( 外部稳定) 也不比1 1 中的强。以上我们是针对有限维空间而言的。对 于无限维空间的集值向量优化问题，我们在第三章中详细讨论。 用扰动逼近考虑问题的这一方法给了我们很大的启发，因此我们通过构建新 的扰动函数来研究无限维集值向量优化的共轭对偶，这样就把问题转化为研究目 标函数的某些特征。通过这样的特性就能得到强弱对偶定理，使得集值情况下原 问题和对偶问题没有对偶间隙，既只要能求解对偶问题就能解决原问题。这中间 的难点就是如何构造扰动函数。正由于这样，第三章针对问题m i n f f z l 提出新的 扰动函数砂( z ，名) = f ( z z ) ，其中f 是从x 到矿的集值映射，xy 为实拓扑向量空 间，矿= yu f 士。0 1 ，讨论无限维空间的情况下的对偶问题。其中我们得到两个 很好的引理，即若目标函数是s 一凸的，则扰动函数也是s 一凸的；若目标函数是 次可加的，则扰动函数关于自变量也是次可加的。接着在目标函数满足次可加性 的前提下，证明了原问题和对偶问题的对偶间隙为0 。弱化了文献1 3 1 中的闭有界 条件，同时得到更简捷的结论。最后，我们弱化了强对偶定理得到一个结论即对 偶间隙不为空集的充分必要条件。 值得提到的是，无限维l a g r a n g i a n 对偶被c o r l e y 2 1 1 2 2 1 f 2 3 1 2 4 f 2 5 1 ，d o l e c k i 和m a l i v e r t 2 6 所考虑，w o l f e 和m o n d w 色i r 型对偶被s a c h 和c r a v e nr 3 1 讨论了。盛 宝怀，刘三阳f 3 2 1 借助抽象算子将共轭映射的概念推广到抽象空间，并讨论了集 值映射共轭对偶的全局稳定性。2 0 0 3 年贾继红，罗学波f 3 3 1 研究了集值优化问题的 一共轭对偶。 5 大连理工大学硕士学位论文 2 预备知识 我们首先介绍实值函数，向量值函数的共轭函数和集值映射的共轭映射概 念，其次给出共轭映射的一系列性质，最后给出次微分和扰动函数的概念。 2 1共轭函数与共轭映射概念 定义2 1 1 2 设，( z ) 是舻一冗的实值函数，z + 舻，则称 ，( z ) = s u p x + t z f ( x ) lz 月，) 为厂 ) 的共轭函数。 共轭函数概念有着鲜明的经济意义。例如，欲生产数量为z = 。，z 2 ，z n ) 丁的n 种产品的成本由， ) 给出，这些产品可以分别i ：a x + = ( z i ，z ；，z ：) t 的价格出售。现在的问题是：厂家如何确定n 种产品的数 值z 1 ，z 2 ，z n ，才能使销售这些产品所的到利润最大。因为显然z + t z 一，( z ) 为 利润值，所以利润作为价格z 的函数由厂x + ) 给出。 仿照实值函数的共轭函数的概念，我们给出向量值函数和集值映射的共轭函 数和共轭映射的概念。 定义2 2 【1 2 设，( z ) 是r nj 舻的向量值函数，舻n 为p 佗阶矩阵集合，t 舒xr z ，则称 ，( z ) = s u pu ( t x 一，( z ) iz d o m f ) z r ” 为，( z ) 的共轭函数。其中d d m ，= _ 。舻if ( x ) + 。o ) 。 定义2 3 【3 0 令f ：j pj 印是集值映射，r p n 为p 礼阶矩阵集合，则称 ( i ) 称集值映射 厂口卜蹄) z 坚f 俨八功 j t r p x n 为厂的共轭映射； 7 集值向量优化问题的共轭对偶 _ 二二二_ 二二二_ = 二一一 ( i i ) 称集值映射 广即) 2 鼢t 旦。阶吖( 跏舻 为广的共轭映射，的双共轭映射； 以上为有限维情况下的定义，类似的我们给出无限维抽象空间的共轭映射。 定义2 4 1 5 设x ，y 是实拓扑向量空间，三( 五y ) 是从x 到y 的线性连续算子空 间，f 是x 从p 到的集值映射。集值映射p ：l ( x ，y ) = p ， f ( 刁= s u pu 陬一f p ) 】，t l ( x ，y ) ， z x 称为f 的共轭映射。 2 2 共轭映射的性质 性质2 2 1 1 2 假设，是酽j 殿的集值映射， ( i ) 若令g ( z ) = f ( x + z ，) ， z ，月，贝i j g + ( 即= ，+ ( r ) 一t x ，g = ，”( z + ) ； ( i i ) 若令g ( z ) = f ( x ) + 矿，月p ，贝 i g ( ? ) = ，( t ) 一矿，g = ， ) + y l ； ( i i i ) 若令g ( z ) = f ( a x ) ，口r ，n 0 ，则 g + ( 丁) = ，+ ( 云) y ，g ”= ，”( 凹) ； ( i v ) 若令g ) = o 厂 ) ，a r ，a 0 ，则 甲 g + ( t ) = a ，+ ( 老) ，g ”= 口，( 2 ) ； 2 3 次微分和扰动函数的概念 2 3 1 次微分的概念。 定义2 5 【3 0 令，：舻j 舻是集值映射，u 称为集值映射，在( 互；雪) 的次梯度， 若雪，( 牙) 且 沪阮刚m i l l 吒竖陟p ) 叫 8 大连理工大学硕士学位论文 成立。厂在( z ；y ) 处的所有次梯度的集合用a ，( z ；y ) 来表示，被称为，在( z ；可) 的次微 分。若对任意可，( z ) 有o f ( z ；y ) 0 ，则，称在z 点处是次微分的。 以上是有限维情况下的定义，类似的我们给出无限维抽象空间的次微分的概 念。 定义2 6 1 5 令x o x y o f ( z o ) ，算子t l ( x ，y ) 称为f 在( z o ，珈) 处的次梯 度，若 死。一y o m a xu t z f ) x e x f 在( z o ，跏) 处的所有次梯度的集合称为f 在( 如，珈) 的次微分，记为o f ( z o ，y o ) 。对 任意y o f ( z o ) ，当o f ( z o ，y o ) 仍，称f 在x o 处次可微。 2 3 2 扰动函数的概念 为了研究优化问题的共轭对偶问题，我们引进扰动函数的概念。 定义2 7 f 1 3 令砂( z ，z ) 是集值映射，妒：xxzj yu + 。) ，满足( z ，0 ) = f ( z ) ，对z x ，称( z ，z ) 是f 的扰动函数。 当x = 舻，z = 眇，y = r v 时，显然就得到有限维情况下的扰动函 数定义。通过扰动函数的引入，我们就把目光从原问题转移到研究扰动问 题m i n ( x ，z ) ，以下章节讨论的则是扰动函数的共轭函数。 9 大连理王大学硕士学位论文 3 有限维空间集值向量优化问题的共轭对偶 3 。1引言 本牵的主要结构是第二节介绍本章所用昀基本知识，第三节接导掇共轭对偶 形式，第疆、盂节给出强弱对偶宠理及冀证明过程，第六节我们把结论推广副一 般情况，最詹总结本章凑容。 3 。2基本知识 令e 是黔中的潮凸锥，对毒，舻g 舻，我们有如下的痔关系： 善o 营弘一毒g 毒秽。簪黟一毒秽 0 ， 善鐾g 。 黟簪一莓菇c o 。 同样的方法霹以定义芝殴 ) ，芝耨芝吼错。 定义3 1 【1 5 】设y z ，y 舻。若y y ，且不存在y ，使得y 冬殴 o 矿， 则y 称冀集合y 囊勺最大点。y 中所有最大点的集合称为y 的最大值，用m a xy 表 示e 类似地可以定义y 的最小值。若ygy ，且不存在y 7 y ，使得y o y 7 ， 则称y 为集合y 的最小值点，并且用r a i ny 表示。集合y 的最小点的全体称为y 靛 最小僮。进一步，我们取锥0 楚置鎏受象限霹黼 露一p l ，) t 拶| 筏0 ，i 雀 1 ，托 e 弓l 理3 。2 。【2 j 令k ，砭c 舻，则 ( 1 ) 霹m a 埘x ( y l + 蚝) 霹m a x 。+ 嚣瀚k ， ( 2 1 罐蠕 ( m 书蚝) 避i i t 1 i 。1 m 十暹婚 砼 定义3 3 f 3 0 4 h ：舻霉留是集德映射 1 1 集值向量优化问题的共轭对偶 ( i ) 集值映射h 的最小值集合m i n 九( z ) 称为外部稳定，若 冠no)、。 荆蹦r a i t n 。，h ( 。) + 碎，比彤； ( i i ) 集值映射h 的最大值集合m a x 尼 ) 称为外部稳定，若 、。殴 o 、 蹦m a 舻x ( z ) 一衅，舻 引理3 4 2 令乃：舻j 舻，毋：形j 辟是集值映射，且x 舻，则 刚m a x 。 竖阮 ) + 以z ) it _ 哪m a 斜x 望【r ( 卅酬m a x 。j f 2 ( 训 若艘m a o x 尼( z ) 是外部稳定 则 群m u a x 。，z u x f ，( z ) + 岛( z ) 】2 群m 、a 。x 。，z u x a ( z ) + 群m 、a t x 。j b ( z ) 】 推论3 5 2 令r ：舻j 舻是集值映射，且x 冬舻老；耳m a t x 。j f ( z ) 是外部稳定 则 蹄些m ) 2 鼢婪鼢附 注3 6 当妒：舒_ 舻是一个向量值函数，则妒的共轭映射垆+ 被定义为 妒( 丁) 2 匙m a t x 。j t x - 妒( z ) lz 舻) ，t 彤黼 以下为我们要考虑的问题 ( v o ) 烈l l l j 甜n m ) iz g ) ， 其中g = z xi 夕( z ) 冠o ) ，z 彤， ，( 。) z 矽， u 尺， 9 ( z ) 月， 定义3 7 1 2 如果加( o ) 在。处是次可微的，则称( y d ) 是稳定的，其中叫( o ) = m i n f ( x ) 。 引理3 8 1 2 】向量优化问题( y d ) 稳定的充要条件是 n d n ( v o ) = w ( o ) cw ”( o ) = m a x ( d ) ， 其中叫”( o ) = m a x u 【_ 叫+ ( t ) 】) = m a x ( d ) ，m a x ( d ) 为原问题的对偶问 t 题，w + ( t ) 为， ) 的扰动函数的共轭映射。 1 2 大连理工大学硕士学位论文 定理3 9 1 2 向量优化问题( y 0 ) 稳定的充要条件是：灵t ( v o ) 的每个最优解牙，都 存在共轭对偶问题的最优解矿，使得 ( 牙，0 ) 一+ ( 0 ，y ) ， 即 厂( 牙) 一w + ( 矿) 或者说牙o w ( o ，厂( 牙) ) ，其中，( 牙) = 砂( 牙，o ) ，一妒( 0 ，矿) = - - w + ( y ) 。 定理3 1 0 1 2 对于任意的z r n 和y r n 舰，都有 妒( z ，o ) 一+ ( o ，y ) 一j 珲1 0 ) 3 3 共轭对偶形式 考虑集值多目标优化问题 ( r ) 蹦m i 甜n 地乱) iz 形) 由乱= 0 可得 ( 局) 趴m i 甜n ( x , o ) lz 研一 即( 局) = ( v o ) 。因此问题( y 0 ) 可以转化为( r ) 。 为了得到更好的对偶结果，我们提出一类新的扰动函数西：r nx 形j 舻u 。) ， ( z ，u ) = _ + 3 p ，z o t t 手l e x r w z 8 e 呈z 碎乱i ， ， 妒( z ，0 ) = 厂( z ) 其中 p 表示p 维列向量，每个分量为 。 设通常形式下的共轭映射为集值映射矿：彤n r p mj 舻u _ 。 - + ( 以y ) 2 毗m a 掰x 阮+ y 可一地) 1 z 形，可矽一 为了下面方便分离u 和z ，我们取仇= 佗。因此考虑如下形式的西的共轭映射 矿：舻加xr p 加j 舻u 。) + ( 阢y ) 2 砬m a x 。) u z y u 一( z ，u ) l z r n ，u 兄n ) 1 3 其中 集值向量优化问题的共轭对偶 给出问题( 昂) 共轭对偶问题 ( 风) + ( o ，v ) = 鼢y 掣。m 嗍 哎m a t x 。j v u - 厂( z ) 一 ph x ，夕( z ) 碑札，让碎) 蹄坚肌叫沪m p i ( 班母让，让跗( 3 3 1 ) 由于夕( z ) 碑让的充要条件是u 一9 ( z ) 皿，故令面= t 一夕( z ) ，从而 乎( 0 , v ) 2 刚m a x 。) 坚m w 如) 叫垆胁圳巩。小i 附( 3 3 2 ) 对优化问题( 3 3 2 ) 考虑约束集 l = z xi 由( 3 3 1 ) 得 = 0 ，i f , j 珲) = zi = 矿( 0 ，y ) l 2 娲旦 y 面+ 的( z ) 一m ) 一 】pi 面碑( 3 3 3 ) 2 麟 y 面i 霞皿) + _ 的( z ) 一m ) 一【 】p iz 珊 由于lcx ，且满足闭性，结合( 3 3 1 ) 与上式可得( 0 ，y ) lc 矿( o ，y ) 。且有 ( o ，v ) l 2 黜m a x 科 y 面i 面皿) + 的( z ) 一m ) 一【 协珊( 3 3 4 ) 娲 y 面i 面霹) + 蹦m a x 科 ( z ) 一m ) 一【 】p ) 将( 3 3 4 ) 式中的y r p n 换成是一v r p 舰，由引理( 3 4 ) + ( 0 ，- - v ) l 2 鼢 - y 面i 面皿) + 一的( z ) 一m ) 一f 】p ) )( 3 3 5 ) 一黜， y 冠i 面霹) + 蹦m a x t o 一的( z ) 一m ) 一【 】p ) 再对优化问题( 3 3 3 ) 考虑可行约束集 = _ 【y 殿加iy 面魑0 ，忱衅) 1 4 大连理工奎芏堡主兰堡堕苎一 _ 一 ： v 硭n iy 碎碎) ， ( 3 删 自( 3 3 6 ) 得 r a i n 面砰) ：mv v 以 ( 3 3 7 ) f v 面i 面r ；) = 0 ， l 。 k u “7 尺：t u j ( 3 3 7 ) 可推出 m a x - wl 面r ；) = o ) ，v v l 殁 o ) 根据定义( 3 。3 ) 喇童m w a x ) h 小砰) 是夕卜部稳定的再由引即4 司知 ：筹m a x 悱霹) + 蹄川圹他) _ 【吲巩叫川( 3 3 8 ) = 酬。) 撕l 面霹) + 蹄 叫夕，八叫 夕p 几”b j ( 3 3 8 ) ：m a x 一v g ( x ) 一，( z ) 一【 j p ， r i o ) 。 = ( y ) 因此 蹄y 崩删 = 删m a x 一矿卅弋0 叫如 a2 蹄) v 驯卅弋0 叫粥 5 蹄，鬯，【一硼 = 酶 望，( 蹁m 川+ 【 p l 膨懦舭则 若血n v 夕( z ) + ， ) + 【 j p iz l ，疋引刚 西厄h j ”。 o 乏y 夕( z ) + 【 p 一磷 o ) ， z l 集值向量优化问题的共轭对偶 证明由定理3 1 0 知 矽( z ，o ) 一( o ，v ) l 一兄晕 o ) 由( 3 3 8 ) 矿( o ，- v ) z = 西( y ) 可得一( o ，v ) l = 一( 一y ) ，进而有 m ) 芭忠) 的( z ) + m ) + 】p ) - 碎 0 】 ( 3 删 即 m ) 纽 。) 出l t l i 甜n 蜘( z ) + m ) + 】p ) 因为 鼢m i 甜l l y 夕( z ) + m ) + pz l ) 是外部稳定的，故有 的( z ) + m ) + 小己) 鼢l ：i l i 甜i 1 的( z ) + 他) + 】p iz l ) + 磷 又由( 3 4 1 ) 可得 厂( z ) y g ( z ) + ，( z ) + 】plz l ) 一j 珲 o ) ， 可推导出 。毛v g ( x ) + 【 p j 珲 o ) ，z l ( 3 4 2 ) 再由z l ， - - - - ，( 3 4 2 ) 可写成 o v g ( x ) + 【 】p 一碎1 0 ，z l 结论成立。 口 3 5 强对偶定理 对于强对偶定理，首先假设m a x y 夕( z ) 一 p 一厂( z ) ) 是外部稳定 的。 定理3 1 2 ( 强对偶定理) ( i ) ( v o ) 关于咖稳定，当且仅当对( y d ) 的每个最优解z ，都存在( d o ) 的最优 解y ，使得 0 v g ( z ) 一 】p 一碎= v g ( z ) 一 】p 一砰 若m a x v g ( x ) 一【 】p ) 是外部稳定的，则有 0 m a x v g ( x ) 一 】p ) = m a x v g ( x ) 一【 】p ) 】f ； 大连理工大学硕士学位论文 ( i i ) 如果z l ，v 舻地，且满足( i ) 的条件，则z ，y 分别是( y o ) 和( d ￥。) 的最优 解。 证明( i ) 首先证明必要性。由定理3 9 的必要性知厂( z ) 一矿( o ，y ) l ，其中v 冗n ，通过( 3 3 8 ) + ( o ，一y ) l = ( y ) 可知，( z ) 一( 一y ) ，其中y 冗几。则 有- f ( x ) ( 一y ) 。 矽( 一y ) 2 硝m a x 。 v g ( z ) 一，( z ) 一 】p z l ) 2 黜m a xu l 的( z ) 一 p m ) ) ( 3 5 1 ) v g ( x ) 一 】p 一，( z ) 一j 珲，z l 以上由m a x y 夕( z ) 一 】p 一厂( z ) ) 外部稳定可推出。故一f ( x ) y 9 ( z ) 一 p 一，( z ) 一碎，x l