多目标半定规划的一类评价函数法论文(PDF 48页）.pdf

西安电子科技大学 硕士学位论文 多目标半定规划的一类评价函数法 姓名 郑成忠 申请学位级别 硕士 专业 应用数学 指导教师 刘红卫 20100101 摘要 多目标半定规划是多目标规划和半定规划两方面的有机结合 这是一个较新 的研究方向 由于多目标规划强大的实际应用价值 以及半定规划的迅速发展 多目标半定规划将成为一个新的研究热点 在各类多目标半定规划问题中线性多目标半定规划占有十分重要的地位 目 前求解线性多目标半定规划的方法包含基于一个单目标问题的方法和基于多个单 目标问题的方法 本文基于一个单目标问题的方法 提出了一类评价函数法 引入评价函数 将线性多目标半定规划转化为单目标半定规划 然后利用单目标 规划的内点算法来求解 本文首先设计了基于最短距离的理想点法 在给出了它的模型之后 结合半 定规划的原对偶路径跟踪的思想 给出了最终能得到原多目标半定规划问题一个 有效解的算法 然后又设计了平方和加权算法 该算法模型含有带实际意义的权 值 在求解一个小规模的优化问题后 从前面的理想点法得出的有效解出发 给 出了一个单步迭代算法 就可以得出对应的有效解 大大提高了算法的效率 关键词 多目标半定规划p a r e t o 有效解评价函数理想点 平方和加权 A b s t r a c t M u l t i o b j e c t i v eS e m i d e f i n i t ep r o g r a m m i n g w h i c hi s an e wr e s e a r c hf i e l di n m a t h e m a t i c a lp r o g r a m m i n g i st h eo r g a n i cc o m b i n a t i o no fs e m i d e f i n i t ep r o g r a m m i n g a n dm u l t i o b j e c t i v ep r o g r a m m i n g B e c a u s eo ft h eg r e a tp r a c t i c a la p p l i c a t i o nv a l u ea n d r a p i dd e v e l o p m e n to fs e m i d e f i n i t ep r o g r a m m i n g m u l t i o b j e c t i v e s e m i d e f i n i t e p r o g r a m m i n gw i l lb ear e s e a r c hh o t s p o t T h el i n e a rm u l t i o b j e c t i v es e m i d e f i n i t ep r o g r a m m i n gp l a y sa ni m p o r t a n tp a r ti n t h em u l t i o b j e c t i v es e m i d e f i n i t e p r o g r a m m i n g f i e l d C u r r e n tm e t h o df o rl i n e a r m u l t i o b j e c t i v es e m i d e f i n i t ep r o g r a m m i n gc o n t a i n s t h em e t h o db a s e do ns i n g l e o b j e c t i v ep r o b l e ma n dt h em e t h o db a s e do ns e v e r a ls i n g l eo b j e c t i v ep r o b l e m s I nt h i s p a p e rw ew i l li n t r o d u c eac l a s so fe v a l u a t i o nf u n c t i o nm e t h o d 乇oc h a n g el i n e a r m u l t i o b j e c t i v e s e m i d e f i n i t e p r o g r a m m i n g i n t o s i n g l eo b j e c t i v e s e m i d e f i n i t e p r o g r a m m i n gt h r o u g h t h ei n t r o d u c t i o no ft h ee v a l u a t i o nf u n c t i o n a n dt h e nw o r ko u ti t b ys o m ei n t e r i o rp o i n tm e t h o df o rs i n g l eo b j e c t i v es e m i d e f i n i t ep r o g r a m m i n g F i r s t l yi n t r o d u c e di st h ei d e ap o i n ta l g o r i t h mb a s e d o nt h es h o r t e s td i s t a n c e A f t e r p r e s e n t i n gt h em o d e l w ee s t a b l i s ht h ei d e a lp o i n ta l g o r i t h mw i t ht h ec o m b i n a t i o no f p r i m a ld u a lp a t hf o l l o w i n gm e t h o di ns e m i d e f i n i t ep r o g r a m m i n g a n dw ec a nf i n a l l y g e tae f f i c i e n ts o l u t i o n T h e nw ei n t r o d u c et h ew e i g h t e ds u mo fs q u a r e sa l g o r i t h m t h e m o d e lo fw h i c hh a sw e i g h t e dv a l u e s A f t e rs o l v i n gas m a l ls c a l eo p t i m i z a t i o np r o b l e m w ee s t a b l i s hao n e s t e pa l g o r i t h m w h i c hg e t st h en e we f f i c i e n ts o l u t i o ns t a r t i n gf r o m t h eo r i g i n a le f f i c i e n ts o l u t i o n w h a ti sm o r ei m p o r t a n t t h ee f f i c i e n c yh a sb e e nh i g h l y i m p r o v e d K e y w o r d s M u l t i o b j e c t i v eS e m i d e f i n i t ep r o g r a m m i n gp a r e t oe f f i c i e n ts o l u t i o n e v a l u a t i o nf u n c t i o ni d e a lp o i n t w e i g h t e ds u mo fs q u a r e s 4 8 多目标半定规划的一类评价函数法 尺 s s A B A 0 4 卜0 T r A 彳 B v e c A I 九i 么 丸 么 符号说明 m 维列向量的集合 力维实对称半正定矩阵集合 n 维实对称正定矩阵集合 矩阵A 的F 范数 矩阵A 的1 范数 矩阵彳的o O 范数 A B 0 A s A 对 求矩阵A 的迹 T r A B 矩阵A 的拉直向量 n 维单位矩阵 矩阵彳的最小特征值 矩阵A 的最大特征值 西安电子科技大学 学位论文独创性 或创新性 声明 秉承学校严谨的学风和优良的科学道德 本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果 尽我所知 除了文中特别加以标 注和致谢中所罗列的内容以外 论文中不包含其他人已经发表或撰写过的研究成 果 也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意 申请学位论文与资料若有不实之处 本人承担一切相关责任 本人虢鞋 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定 即 研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学 学校有权保 留送交论文的复印件 允许查阅和借阅论文 学校可以公布论文的全部或部分内 容 可以允许采用影印 缩印或其它复制手段保存论文 同时本人保证 毕业后 结合学位论文研究课题再撰写的文章一律署名单位仍然为西安电子科技大学 保密的论文在解密后遵守此规定 本学位论文属于保密 在一年解密后适用本授权书 日期丝 L 日期坐 f 蛊 L 成一 代一 侈r 寸 釜一 妙一 耻学 名 名 签 签 人 师 本 导 第一章绪论 第一章绪论 在这一部分首先介绍了半定规划和多目标规划的研究现状 意义及其基本理 论与算法 之后对多目标半定规划的研究现状和意义作以阐述 然后给出了多目 标半定规划的模型与基本理论 最后列出了本文的主要工作内容及各章节的安排 1 1 半定规划 1 1 1 研究现状及研究意义 最优化方法主要是研究在约束条件的限制下根据一定的准则从若干可行方案 中选取一个方案 以达到最优目标 达到最优目标的方案称为最优方案 搜索最 优方案的方法称为最优化方法 选取最优方案就是在一定的约束条件下求目标函 数的最大值或最小值的问题 最优化学科是运筹学的一个重要分支 它的基本思 想出现在1 9 世纪初 第二次世界大战后 由于生产发展的需要和电子计算机的应 用 出现了许多数学规划方法 如线性规划 非线性规划 动态规划和随机规划 等 上世纪4 0 年代 随着运筹学产生 发展和壮大 数学规划的领域不断扩大 新问题的出现使已有的线性规划和非线性规划的算法无能为力 而半定规划的产 生为解决这些问题提供了新的方法和思路 它研究含有矩阵函数半正定约束的优 化间题 半定规划是数学规划中一个相对较新的领域 半定规划的起源可以追塑到几 十年以前 1 9 6 3 年 B e l m a n 和F a n t 第一次构造了一个半定规划问题 接着苏联的 一些学者又相继研究了半定规划 当时也叫矩阵不等式 在控制领域中的应用 从 1 9 8 1 年以来 关于半定规划的论文都被以 带有变换矩阵的线性规划 命名 而 真正关于半定规划方面的文章都是在9 0 年代写的 半定规划问题的很多内点算法 在这时期也得到了较深入地研究 E t i e n n ed eK l e r k 于1 9 9 7 年1 2 月发表了他的博士论 文I n t e r i o rp o i n tM e t h o d sf o r S e m i d e f i n i t e 从那时起 半定规划已经成为一个倍受关 注的研究课题 目前在半定规划问题上已经有了一些研究成果 N e s t e r o v 和N e m i r o v s k i 在文 献 4 中首次将线性规划的内点法扩展到半定规划 然后A l i z a d e h 在文献1 4 7 证明了 大多数线性规划的内点算法都可以推广到半定规划上来 N e s t e r o v 和N e m i r o v s k i 在文献1 4 1 中利用自协调罚函数的定义给出了用内点算法求解锥规划的更完善的理 论 证明了半定规划存在多项式时间算法 这些著作从不同的方面入手 通过结 2 多目标半定规划的一类评价函数法 合不同领域的知识提出了各种很有建设性的求解方法 虽然这些只是解决单目标 半定规划问题的 但是对多目标半定规划问题也很有借鉴作用 近几年来 由于 巨大的实际要求 半定规划问题的研究得到了迅速发展 它在控制论 组合优化 逼近理论 特征值优化 系统控制理论 机械及电子工程中等众多方面的重要应 用 使其成为近年来数学规划领域日益受到关注的研究方向 可以说半定规划的 产生为解决一些新问题提供了新的方法和思路 极大的推进了优化学的研究和发 展 半定规划可分为线性半定规划和非线性半定规划两类 随着对线性规划和凸 规划的内点算法的深入研究 线性型半定规划的理论和算法得到了迅速发展和运 用 线性半定规划 线性规划的一种推广 是在满足约束 对称矩阵的仿射组合半 正定 的条件下使线性函数极大 极小 化的问题 文献1 3 1 对线性型半定规划做了 深入的讲解 并且提出了很多比较成熟的算法 目前一些学者又开始了对非线性 型半定规划的研究 并已建立了其一阶和二阶最优性条件 在此基础上也相继出 现了很多较为理想的算法 本文主要讨论求解线性半定规划的算法 如无特殊注 明 本文中所涉及的半定规划问题均为线性半定规划问题 1 1 2 半定规划基本理论 半定规划 S e m i d e f i n i t eP r o g r a m m i n g 是线性规划在半正定矩阵锥上的推广 即在线性规划的标准型中 将线性规划中的向量变量替换成矩阵变量 并且加上 矩阵变量的半正定约束 就得到了半定规划问题 半定规划的标准形式为如下的线性型半定规划 f m i nC X P s J 4 X 包 j 1 2 朋 k o 其中A 4 4 以 r C 4 l 2 m b 岛 6 2 k 丁 R X 墨 4 f 1 2 m 线性无关 R 卅为m 维列向量 墨 代表刀维对称 半 正定 矩阵 X Y t r a c e X7 y t r a c e X 表示求一个矩阵X 的迹 利用L a g r a n g e 方法可得到 P 的对偶规划为 D m a xb r y 豇 只4 s c t l S O 其中 J S R 熨 为形式上的书写方便 将 P D 写成如下形式 第一章绪论 3 肛麓6 IX 0 黟函 其中制叫 4 母厶科 Z 薹y 4 1 2 通常称 1 1 为半定规划 以下简称S D P 的原问题 称 卜2 为S D P 的对偶问题 它们互为对偶 即对偶的对偶是它本身 定义1 1 若X x l A X b X 0 S y S l A T Y S C S 0 则称 X S 分别为 1 1 和 1 2 的可行解 如果再有若X 卜0 S 0 则称X y S 分别 为 1 1 和 1 2 的严格可行解 定义1 2 设X 和 S 分别是问题 1 1 和 1 2 的可行解 如果有X S 0 或 等价地X S 0 则X 和O S 分别是问题 1 1 和 1 2 的最优解 类似的 如果 X S s 则X 和O S 分别是问题 1 1 和 1 2 的s 最优解 S D P 的原问题 P 和对偶问题 D 的对偶间隙为 P 的目标函数值与 D 的目 标函数值之差 即 C X b 7 y 咒4 s X 一 咒乃 4 x s X i li 1 以下记矿 d 奉分别为 P 和 D 的最优值 p D 木分别为 P 和 D 的最优解集 P D 分别为 P 和 D 的可行集 下面给出弱对偶和强对偶定理 定理1 1 令X P 和 Y S D 则有T r C X 一b X y T r S X 0 即对偶间隙 在可行解处是非负的 证 r r c x 一b T Y 乃 Y A s x 一 Y r r A x T r S X X S Ii l 故由X 0 S 0 可得 X S 0 即T r C X 一b V y T r S X 0 得证 定理1 2 强对偶定理 设 1 半定规划的原问题 P 存在严格可行解 2 半定规划的对偶问题 D 存在严格可行解 则有下面的结论成立 1 如果上面的条件中至少有一个成立 则矿 d 毒 2 如果上面两个条件都成立 则矿 d 宰且 和p D 宰均非空 4 多目标半定规划的一类评价函数法 如果在 X S 处对偶间隙为0 即T r X S 0 则X P 和S D 是最优 的 也就是说 当对偶问隙的值为0 时 P 和 D 同时取得最优解 而对偶间隙为0 P 和 D 的最优值当然也相等 由于X 0 S 0 所以条件T r X S 0 等价于X S 0 而 P 和 D 的最 优解当然会是可行解 从而 P 和 D 最优解满足 f 擘劫 A y S C 1 3 l x s 0 其中的条件X S 0 订q 做互补性条件 满足此条件的最优解称为互补最优解 若有 X 0 S 0 贝J J 1 3 是 P 和 D 的最优性充要条件 也称作S D P 的一阶最优性 K K T 条件 1 1 3 半定规划的算法 内点法的含义就是要求迭代过程要始终保持在可行域内部进行 并且初始点 也要在可行域内部选取 求解半定规划的方法有很多 这里主要介绍原对偶路径 跟踪内点算法 我们的算法是为寻求最优解 或者近似最优解 也就是寻求一组满足最优性 K K T 条件 1 3 的可行解 为此引入参数口 对最优性条件 卜3 进行扰动 有 f 竽舶 A Y S C 1 4 船 其中第一个和第二个条件是原问题和对偶问题严格可行解的条件 第三个条件当 专0 时就相当于互补松弛条件X S 0 而对于固定的 卜4 都存在唯一的解 x p S 分别为原问题 P 和对偶问题 D 的一个可行解 且其对偶间隙为 玎 当I t 0 时 由 卜4 的解 x S J L l 构成的曲线称为中心路径 这是一条 光滑曲线 因此在算法中使其沿着中心路径迭代 迭代的每一步都减小参数p 也就是每一步都使得对偶间隙减小 这样迭代下去 在若干步迭代以后得到的可 行解满足或近似满足互补松驰条件X S 0 也即我们可以证明 当p 0 时 X p S J L f 存在聚点 且若 X S 是 X J L l S J L f 的聚点 那么X S 分别为原问 题 P 和对偶问题 D 的最优解 对于系统 卜4 是一个非线性的 求解起来就有些困难 而前两个是线性的 所以通常我们将互补松驰条件约束线性化 在每一次的迭代过程中 求解如下的 一个线性系统 第一章绪论 5 f 爿笋 o 彳 每 A S 0 1 5 lA X S X A S p l 一船 L 得到迭代方向 A X A S 这样就得到新的初始迭代点X7 X A X S S S 逐步 的迭代进行 最终会收敛到最优解或者s 最优解 有关线性化化过程和收敛性部分 可参见文献 引 对于系统 卜5 由于X S 是不可交换的 即X S S X 这样 1 5 的解不能保证是对称的 下一步迭代之后的点就不能保证是对称的 为此可以采 用不同的对称技巧来克服这个困难 得到不同的原始 对偶搜索方向 其中 常 用的有胛方向 H K M 方向 A H O 方向等 本文中用到的都是胛方向 利用上 述不同的搜索方向就可以得到不同的内点算法 算法1 1 S t e p 0 给定初始可行点 X 0y O S o 其中彳o 0 S o 0 令k 0 选取精确 度参数s S t e p l 选择参数 f 彳赵 0 S t e p 2 解方程组 A r A y 丛 0 得到搜索方向 A X A y A S 蝴 Y 心 一爿s S t e p 3 选择步长a 0 1 使得X A X 0 S a 七 S 0 S t e p 4 令 X y k i S 1 X a A X Y a 少 S a 女A S S t e p 5 如果T r X 1 S 1 则原问题可简记为m 啦 石 x 以 x 厶 x r 定义1 4 设x D 如果对任意x D 有Z x Z x j l 2 P 则称x 是多目标规划 卜6 的绝对最优解 如果不存在x D 使乃 x 乃 x l 2 P R 3 k 1 2 p 五 x 0 显 然 圪 是一个多目标凸规划问题 特别地 若4 f l m C l 2 P 都是 对角矩阵 则 圪 等价于一个多目标线性规划问题 借助L a g r a n g e 函数 可求得 圪 的L a g r a n g e 对偶问题也是一个线性型多目标 半定规划问题 眈 j m a xB T y 1 8 眈 伍西 s C 娜 o 其中 U R P U 0 定义1 5 若X X I A X B w X 0 S y S I y S C U S 0 则 称X y S 分别为 1 7 和 1 8 的可行解 如果再有若X 0 S 0 则称X y S 分 别为 1 7 和 1 8 的严格可行解 记 只 和 见 的可行域分别为 F 圪 x S 疗l A X B o o X 0 1 9 F 见 y S R 肿x S I A y S C S 0 1 1 0 这部分给出线性型多目标半定规划模型中的等式约束都为似 B w 的形式 主要是为了方便给出多目标半定规划的对偶模型形式 而在后面的章节中没有必 要给出多目标半定规划的对偶问题 因为我们的算法都是通过间接的方法将多目 标半定规划问题转化为了单目标优化问题 而实际求解的也是单目标优化问题 因此整个过程中没有涉及到多目标半定规划的对偶模型 所以 为方便起见 后 面的章节中我们的多目标半定规划的标准模型都以如下的形式给出 m m C I x q x 2 1 1 1 s 2 A X 6 X 0 7 E S Z I 6 设x 是 圪 的可行解 Z 汪1 2 p 是m J J n G X f 1 2 p 的最 优值 若G x Z i l 2 P 则称x 是 圪 的绝对最优解 定义1 7 设x 和仅s 分别是问题 艺 和 见 的可行解 若X S 0 或等价地 第一章绪论 X S 0 则x 和0 s 分别是 圪 和 见 的 一有效解 这时称 X y s 是 艺 和 见 的甜一有效对 定义1 8 设x 和 y s 分别是问题 乞 和 见 的可行解 若x S s 则X 和 s 分别是 乞 和 见 的s 一 一有效解 这时称 x Y s 是 圪 和 或 的 s U 一有效对 1 4 本文的主要工作及内容安排 多目标半定规划是对多目标规划和半定规划的有机结合和进一步深入 它主 要研究在某种意义下关于对称矩阵的多个数值目标函数的同时优化问题 由于在 已有的理论中关于多目标半定规划的部分还较少 所以本文的工作是从多目标规 划和半定规划相互制约和相互贯穿的关系出发 并在刘红卫老师的悉心指导下完 成的 主要是关于多目标半定规划的一类评价函数法的研究 评价函数可以有很 多 在本文中主要针对一类基于距离的评价函数 提出了两个求解多目标半定规 划的算法 一个是基于最短距离的理想点法 另一个是带有加权意义的理想点法 一平方和加权法 并进行了数值实验及相关收敛性证明 具体内容如下 第一章绪论部分 主要阐述了多目标半定规划的研究现状 研究意义及基础 理论 由于多目标半定规划是多目标规划和半定规划的结合 所以首先介绍了多 目标规划和半定规划的各自的研究现状 及其基本理论和有关算法 之后简要概 述了多目标半定规划理论的理论研究及其基本概念 第二章介绍了多目标半定规划的基于最短距离的理想点法 首先概述了该算 法中的评价函数思想和意义 将多目标问题转化为一个单目标问题 结合原对偶 路径跟踪算法 给出理想点法的模型 然后给出了算法并进行了分析证明 最后 对算法做了数值实验 总结了算法的优缺点 第三章设计了多目标半定规划的平方和加权法 通过平方和加权法和基于最 短距离的理想点法之间的内在联系 在理想点算法的基础上给出了一个相对比较 高效的算法 该算法是从当前已经得到的有效解出发 单步迭代得到我们的其它 权值矩阵的有效解 提高了算法的效率 最后是总结与展望 致谢 参考文献 本人在硕士学习阶段的研究成果 第二章基于最短距离的理想点法 1 3 第二章基于最短距离的理想点法 在本章中把多目标规划的理想点法应用到多目标半定规划中 提出了多目标 半定规划的基于最短距离的理想点法 该算法首先是将多目标问题的有效解的求 解问题转化为一个单目标二次半定规划的问题 再结合半定规划的原对偶路径跟 踪法的思想而提出的 另外还给出了可行性收敛性的分析及相关的数值实验 2 1 理想点法模型介绍 多目标半定规划是多目标规划和半定规划两方面的有机结合 多目标规划是 研究多个目标的同时优化问题 半定规划的模型的标准形式为线性型 因此本文 中研究的都是如下所示的线性型多目标半定规划 jmln Cl x q x 2 2 MSDP 1 1 77 7 1 s j 丘Y b X 0 其中 C f R n n f l 2 P b R 4 R f l 2 m X 掣 A 4 以 r 朋 4 X 4 X 一 4 x 并J t A 扛l 2 m 是线性无关的 另外 M S D P 的可行解集记为 D XlA X 6 X O 2 2 由于这是一个研究多目标的极小化问题 对于该问题直接来求解就比较困难 通 常我们的算法通过某种问接的的方法 而且求解得出的都是它的有效解 但是注 意到 对于 M S D P 中的每一个单目标问题 m i n C X f 1 2 P t 上 这是一个很一般的 S D P 问题 我们已经可以用很多较好的算法求解出它的最优解 集 Z 汪l 2 P 2 3 以及最优解 Z 扛l 2 P 2 4 如果有n Z f 2 j 则显然n Z 就是多目标问题的绝对最优解集 我们不妨称该 1 4 多目标半定规划的 类评价函数法 绝对最优解集中的点为理想点 然而在实际的多目标规划问题求解中很难有这样 的巧合结果 通常都会不存在所谓的理想点 本文中介绍到的 M S D P 的基于最短距离的理想点法就是把多目标优化的理 想点法推广应用到多目标半定规划中 思想就是要寻求一个 M S D P 的比较理想的 有效解 把距离理想点最近的那个点作为 M S D P 的所谓的比较理想的有效解 其 中引入的评价函数为距离函数 这样就将原多目标半定问题转化为求解一个单目标优化问题 该问题还等价于 咖善P 互l e 2 5 2 6 2 7 扣喜圭 e 吖 2 缸 c 珂 2 8 ls j 么x 6 x x 7 0 为形式上的书写方便 现在令 石 片 r c C l C 2 q 7 令 C X C l C 2 c x G 彳 C 2 X c p x 2 9 则 2 8 等价于 卜X T C r C X 7 C X 2 1 0 E 朋吐x Q 1 容易验证这是一个凸二次半定规划问题 它的L a g r a n g e 对偶问题为 第二章基于最短距离的理想点法 1 5 其中A r y y 4 t l m a b r y Z x 7 C r C X y 秽2 s t C X 一厂 r C A r Y S S S7 0 2 1 1 2 1 2 容易得出对偶间隙为 1 X T C T C X 一 r 似 6 r y 一互1x V 凹 c x 一 C X c 似 r 多 C X 一 c X 一 彳r y X 倒一 r C A r y X s X 2 1 3 定理2 1 2 1 0 的最优解一定是 M S D P 的一个有效解 证明 设X 是 2 1 0 的最优解 则X 也是 m l n 工E D 的最优解 假设X 不是 M S D P 的一个有效解 则 j 筏 D s e X l C f X V i 1 2 p 且 又 从而有 且 j f 0 l 2 p s 7 C J o 五 q X 锻 D c x Z i 1 2 P O G 五一彳 q X f f 1 2 P C o X 一 气 X 一 于是有 e X i f 2 0 S 0 要使迭代可行 搜索方向 从 缈 A S 首先必须满足 篮材A 彳y 端她C0 2 1 5 I 篮 彳7 一 c 从 7 P 7 这罩我们每一次迭代都沿着中心路径来寻求迭代方向 我们通过求解如下的非线性 方程组来得到迭代方向 f A A X 0 A S A7 缈一 C A X 7 C 0 2 1 6 4 x 4 0 0 S A S 其中 t r a c e X S o 刀 在算法迭代中参数 以p 1 9 p 0 0 1 的形式更新 现在忽略 2 1 6 第三式中 的二次交叉项 得 f A A X 0 I A S A7 1 妙一 c 麟 7 C 0 2 1 7 I x s A X S l u I 一船 由于x S 是不可交换的 即X S S X 这样 2 1 7 的解不能保证是对称的 下一 步迭代之后的点就不能保证是对称的 为此可以采用不同的对称技巧来克服这个 困难 得到不同的原始 对偶搜索方向 其中 常用的有 丁方向 H K M 方向 A H O 方向等 本文中用到的都是 丁方向 这里N T 尺度矩阵记为 D S 一 S 叉S j S 一 2 1 8 第二章基于最短距离的理想点法 1 7 D 肋一 D 1 z 肋1 V 2 1 9 巩 D 一 A X D q B D 坳 巩 巩 珐 2 2 0 i 1 吼 仇y 1 d V 2 2 2 1 D 1 M D A S J L l X 一S 2 2 3 A 蚁 0 I A S A7 1 A y C 从 7 C 0 2 2 4 D 1 A X D A S p X 一一S 引理2 2 设 F 尺 1 2 聊 线性无关 G r v e e F O v e c F 2 w f 吒 H R 7 M X S S W S 一圭 S 船圭 j S 一 E W 一1o 肜 F I o I 若 一茹础斟 亿捌 f G F H 7 1 E 1 F G7 旯 G F H7 1 H E 1 见一G F H H E 1 G 7 名 A X M a t F H7 日 E 一 F G r A l 一见 2 2 6 1 8 多目标半定规划的一类评价函数法 f 碍l N 砚 N M 固N I ii l G 7 1 v e c A i v e c A 2 v P c 4 H r 1 P c C 1 v e c C 2 l y e c q 雎罐 姚 p 捌 f G F H7 日 E 1F G a y 一G F H7 H E 一G7 A X M a t F H7 1 E 1 F G f A y r 2 2 9 这也就是 2 2 4 的解 其中 F H r E 一F 是正定的 G 又是满秩的 从而 G F H7 1 日 E 一1 F G7 是正定的 f l 了 2 2 9 第一式可唯一解出缈 再由第二第三式唯 S t e p 0 输入严格可行对 彳o S o k O 精确度参数s O p 了鲁 参数p 使得6 c X S O p 三 S t e p l 计算T r X S S t e p 2 若r r X S 0 S 0 若d e t X s o o V 0 口 0 品卜0 证明 由于 d e t X s o d e t X d e t S a 而 d e t X 兀 d e t S 兀九慨 所以 d e t K n 兀凡蛾 又d e t X s 0 1 0 故 V 0 0 R z s o 0 这是显然的 如若不然 则 j f j a 满足 以 0 或者 s o 0 不妨就设丑 K 0 由九 k 的函数连续性及九 K 0 可得 3 a l O a 使得九 以 0 从而d e t X 0 这就与已知矛盾 所以 瓦 0 叉 0 V 0 O 0 得证 引理2 4 假设Q s J 并且假设M R 职 是反对称的 即M M 那么我 们有d e t Q M 0 并且如果九 Q M R f l 2 m 那么有 0 0 又 Q s 2 V t R 一 t M 订M 7 所以类似的也有 V t R V x R x 0 X T Q t M x X T Q x 0 所以Q t M 不会有0 特征值 即 2 0 多目标半定规划的一类评价函数法 V t R d e t Q t M 0 若d e t Q M 0 不成立 即有 d e t Q M 1 0 则由d e t Q t M 的连续介值性知 3 t o 0 1 使得d e t Q t o M 0 这就产生矛盾 所以必有 d e t Q M 0 如果凡 Q M y R j 1 2 聊 贝0Q 黠 一M M 7 V A k 般 Q Q A I 一 0 V t R d e t Q M A I 0 A Q k Q 同样地 V A 0 V t R d e t Q M 一九 0 允 Q 九i n Q 所以0 A i Q A i Q M 九 Q M 1 Q 得证 定理2 2 z x x z X y A S 是由 2 2 9 求解得出的 D x 瓯 喀 最由 2 1 8 一 2 2 0 定义 则有 p O x O s 职仇 钏仇 见1 1 2 证明 瓠 巩 热 2 一 巩 D A 2 气p D X D s D S D x D o D D x D s D s D x D 孑飞 i 1 2 巩B 2 B 巩 D x D s D s D x 仇岛 B 巩 瓠 巩 珐 2 一 仇 O s 2 从而有 一三 巩一珐 2 仇珐 D s D x 丢 以 D s 2 而又显然有 D I O s 2 I I D I 珐 2l I 1 1 D x 珐 1 2 O x 一协 2 l l o x 一珐 2I J 1 1 D x 一协 1 1 2 进而 一扣巩一D s l l 2 I 巩珐 喀哦 0 i i l l 巩一B I l 2 巩一D s 吃一D s D x 仇一2 巩 D s 珐 珐 l 协 D s l l 2 巩 D s 巩 D s 仇 仇 2 巩 D s D s D s 所以 巩一珐1 1 2 一扣仇 珐0 2 一扣巩一珐胁一扣巩 珐n 从而一扣巩 见0 2 巩喀 职巩 扣巩 D s l l 2 所以J D 巩B D s D x 劲巩 坟1 1 2 得证 定理2 3 设x 地s 地 叫耶川 一赤I l D 川 似础 是 由 2 2 4 求解得出的 若6 0 证明 对V O O s O 0 只需证明d e t 以最 0 即可 由于 舣 少 A S 是由 2 2 4 求解得出的 满足 q 矿 一V 贝0 有爿乙 咒 彳 口 x S a S S V a 巩 y a 珐 V 2 伉仇十仅形珐 a 2 仇珐 9 2 a n y 2 昙a2 D x D s D s D x j 1 口2 D J B D s D x 虿1a D x y V D s V D x D s V 现记肘 三a 2 巩珐一珐巩 三1a D W V D s V D x 一珐y Q 口 矿 口 一y z 罢az D x 风 D s D 石 则显然有M7 一M 即M 为反对称矩阵 对Q a 1 a v 2 a p I 竺 昙 D x D s D s D x Z 2 2 多目标半定规划的一类评价函数法 由于0 a 1 所以有 1 一a V 0 而 J J 去 巩B O s O z l l r O s G O x l l 2 i Ii I 户 巩职 皿巩 石I l I 珥1 1 2 6 2 引 即I I 去 巩珐 O s O x 1 1 2 1 其中p D x D s D s D x 劲巩 协1 1 2 是由定理2 2 得到的 所以水九 尹1 B D s D x 故J 竺 1 D x D s D s 巩 是J 下定的 1 1 进而Q a O a V 2 a t t I 竺 委 D x D s D s D x IN 正定N 所以X S Q M 正定 从而由引理2 3f 4x 0 O S 1 0 得证 以T h Z v 2 1 s 1 M D x s l D x D s s D x 肘为反 对称矩阵 如上述证明中定义 弓I 理2 5 j 九m j n 矿 2 t a 1 62 证明 V 2 x 0 s 1 D k M A m i l I y 2 A j n D 胚 M 因为 y 2 r 缈 2 由实对称矩阵的特征值是实数知 丑 矿 2 A D 髂 M R i 1 2 n 由M 的反对称性和p l 的正定性 及引理2 4 得 A m i l l y 2 A j I I D 塔 p k D k 由l 五 D x s p 得 第二章基于最短距离的理想点法 p 凡 又由引理2 2 得 p D x D s D s D x 如巩 D s 1 1 2 故 k J L l J D k p i D k J L f p D k J L l 一1 1G D s 1 1 2 J L l 一刘I 以1 1 2 p 1 6 2 所以有 k i y 2 p 1 6 2 引理2 6 I ID 您1 12 l iD 1 4 证明 显然有 D x 喀 协D x 毒 D x D s 2 一 D x 一坟 2 由引理2 2 中证明我们知道 0 巩一B I l 2 l I D J 见1 1 2 记D D x D s Q r D x D S 则 1 1 2 I I 三 协2 9 2 1 1 2 而1 o 谚8 2 0 90 2 2o B 9 I J 2 去 I J 协2J J 2 刊9 2 1 1 2 l 1 lD 矿1 1 4 I IG 1 1 4 扣现1 1 4 所以I I 1 1 2 五1I I D 1 1 4 得证 o 弓l 理2 7 设 r r x S 刀 6 6 x S 贝l J 6 6 x s F 皂 4 2 1 62 推论2 1 若6 x s J L l 万1 则6 x s 6 x s 也即二次收敛到p 中心 弱一些的条件6 X S I u 手暗含了6 x s J L I 6 X S l a 充分满足收 敛性 证明 若6 x s 肛 三1 从而6 6 x s J L l F 弩 6 2 4 2 1 52 同样的 若6 x s J L l 丢 从酣郇c 赫 需爱 引理2 8 设 T r X S n 6 5 x S 对某0 0 1 若 1 一日 p 则有 6 x s p 孵硐n O2 1 一叩2 有关上面的引理2 7 2 8 的证明可参见文献 3 l 定理2 4 算法2 1 中卉始给定5 x s p 三 1 一日 J L l 若 0 0 1 与 则下一个迭代点 x S 满足6 x s p 1 从而该算法可产 4 n l 2 生一系列迭代点恒满足6 1 2 证明 已知6 x o S O i 1 若p 1 一p 更新后 使得占 x o S O J L l 去 二 二 则下一个满N T 步就能产生一个迭代点 x S 就满足 5 x n G 伍 咒J L l 妒 吾 从而该算法可产生一系列迭代点粤满足6 吾 又由引理2 8 可知 艿 x 跏 2 硼n 0 2 I l 0 咿 x 嘶 所以要满足 6 一s p 万1 第二章 基丁最短距离的理想点法 似一砂删 焉 1 啪2 X S O 川 去2 三 2 3 由 6 x s p x 1 得 丽n 0 2 1 卅舭o m o 焉 1 叫三 故只需丽n 0 2 1 一日 三 三 就可满足 2 3 0 式 化简上式得 n 1 0 2 1 即0 0 喜 得证 4 n l 因此只要算法中初始选取的 s 满足6 x s p 丢 9 万导 迭代时参数J L l 以J L l 1 日 的形式更新 定理2 4 的内容就告诉我们 迭代之后 的点仍然满足6 x s i 1 而由定理2 3 我们早就知道 只要有6 0 S 1 0 这样在算法中就可以一直保证每一步迭代的可行性了 实际上从我们的证明中还可以发现对于a s p p 了b 且满足 6 x s 吾 1 一o u A x 妙 髓 是由 2 2 4 求解得出的 算法2 1 中 得到的序列 x S 是收敛的 这里我们的算法是针对一类二次半定规划问题提出的 关于算法的收敛性理 论分析证明类似于文献 1 1 中的分析 这里就不再给出证明了 在后面的数值实验中 我们会看到很好的数值验证 2 6 多目标半定规划的一类评价函数法 2 4 1 数值实验 2 4 数值实验与小结 在这一部分我们给出有关多目标半定规划的基于最短距离的理想点法算法的 相关实验说明 对于多目标半定规划问题 严 C l C p 州X 2 3 1 s J 么 X 6 f i l 所 X 爵 这里我们要选取的初始点x o S o 要满足 A X b C X f 7 C A7 1 Y S 6 一s p 0 3 3 3 4 3 5 其中的A 称作权值矩阵 可以根据实际问题给出 定义3 1 X X I A X b X 0 0 S y S I c x f 7 t C A 2 y S S 0 则称X y S 分别为 3 4 和 3 5 的可行解 如果再有X O S 0 则称X y S 分 别为 3 4 和 3 5 的严格可行解 定义3 2 设X 和O S 分别是I b J 题 3 4 和 3 5 的可行解 如果有X S O 或等 价地X S O 则X 和 S 分别是问题 3 4 和 3 5 的最优解 且称 X S 为 M S D P 的 基于权值矩阵旯的有效解 类似的 如果X S s 则 X S 称作 M S D P 的基于权 值矩阵A 的g 有效解 3 2 单步迭代算法 正是由于平方和加权法和基于最短距离的理想点法有着密切的联系 模型也 有着很大的相似之处 我们当然可以利用上一章的算法来求解 但是当我们每给 出一组权值 都要将该算法执行一遍同样的算法 这样显得效率很低 既然我们 已经获得了一个有效解 我们就可以从当前的有效解出发 寻找一个效率更高的 第三章平方和加权法 3 1 算法 在下面部分我们给出一个单步迭代算法 由多目标半定规划的模型 3 4 可得出一阶最优性K K T 条件为 f A X b 甜一厂 7 A c A r Y S 3 6 x S o 然而在实际应用中我们求得的都是近似有效解 即s 有效解 X y S 这只需要 满足 丘Y b C X 一 7 A C A7 Y S 3 7 X S s 下面假设 X y S X 0 9 S 卜0 是由上一章的基于最短距离的理想点法求得 的s 有效解 即 X J S 满足 A X b c x 一 7 C A7 Y S X S s 令X X 似 Y Y 缈 S S A S 其中 从 A y A S 迭代方向 对照方程 组 3 7 与 3 8 容易发现 从 a y A S 首先要满足 IA A X 0 1 c x 7 九c c x 一厂 7 A 一 c 一么7 1 少 s 3 9 另外 赵 A y A S 还必须使得X S s 成立 我们还发现 X S X X S S X S X S X S X S 3 一1 0 而且已经有 S 如果再能有 I X 丛 X S 0 赵 A S s 0 成立 那么 X y S 必定会是平方和加权法得到的一个s