（应用数学专业论文）半定规划信赖域算法的研究.pdf

摘要 半定规戈i j ( s d p ) 是线性规划的一种推广，它是在满足约束“对称矩阵的仿射 组合半正定”的条件下使线性目标函数极大( 极小) 化的问题这个约束是非线性、 非光滑、凸的，因而半定规划是一个非光滑凸优化问题最近几十年来，由于半 定规划的理论和算法的研究取得了很大的进展，并且半定规划在控制论、电子工 程、组合优化等领域得到了广泛的应用，因此它已发展成为数学规划领域中一个 非常活跃的研究方向 本文首先就半定规划的产生与发展做了一个比较详细的概述，介绍了半定规 划最初的产生过程以及最近几十年来学术界关于半定规划算法研究的发展情 况接着又给出了半定规划的基本概念、半定规划的对偶理论、半定规划的主要 算法介绍以及半定规划的实际应用背景等 本文的主要部分给出了求解半定规划的信赖域算法首先利用互补松弛条件 求出了原半定规划与其对偶问题的最优性条件，即k k t - 条件通过最优性条件， 就把求解半定规划问题转化成了一个求解非线性不可微方程组的解问题接着， 利用推广的f i s c h e r - b u r m e i s t e r 光滑函数，将不可微的方程组转化成一个非线性 可微的方程组然后又把这个非线性可微的方程组转化成了一个无约束的优化问 题最后利用最小二乘原理，定义了一个效益函数，因此求解原来的半定规划问 题就转化为了求解无约束最小优化问题 最后，本文利用信赖域算法求出了上述无约束最小优化问题的近似解，即为 原半定规划问题的最优解，并分析了该算法的有效性、适定性，还给出了算法的 收敛性证明，表明该算法是切实可行的 关键词：半定规划，原始对偶问题，信赖域算法，收敛性 a b s t r a c t s e m i d e f i n i t ep r o g r a m m i n gi sa l le x t e n s i o no fl i n e a rp r o g r a m m i n g i ns e m i d e f i n i t e p r o g r a m m i n go n em a x i m i z e s ( m i n i m i z e s ) al i n e a ro b j e c t i v ef u n c t i o ns u b j e c tt ot h e c o n s t r a i n tt h a ta na f f i n ec o m b i n a t i o no fs y m m e t r i cm a t r i c e si sp o s i t i v es e m i d e f i n i t e s u c ht h ec o n s t r a i n ti sn o n l i n e a ra n dn o n s m o o o t h ，b u tc o n v e x ，s os e m i d e f i n i t ep r o g r a m m i n gh a sb e e no n eo ft h em o s ta c t i v er e s e a r c ha r e a si nm a t h e m a t i c a lp r o g r a m m i n g b e c a u s ei t st h e o r ya n da l g o r i t h m sh a v e b e e nd e v e l o p e dg r e a t l ya n di t sn u m e r o u sa p p l i c a t i o n sh a v eb e e nf o u n di nc o n t r o lt h e o r y , e l e c t r i c a le n g i n e e r i n ga n dc o m b i n a t o r i a l o p t i m i z a t i o n t h i sa r t i c l ef r s t l ys u m m a r i z e st h ep r o d u c ta n dd e v e l o p m e n to fs e m i d e f i n i t e p r o g r a m m i n gi np a r t i c u l a r l y i ti n t r o d u c e st h ei n i t i a lp r o d u c tp r o c e s so fs e m i d e f i n i t e p r o g r a m m i n ga n dt h ea l g o r i t h mr e s e a r c hd 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 i na c a d e m i ai nr e c e n td e c a d e s t h e nt h i sp a p e rg i v e st h eb a s i cc o n c e p t i o n t h ep r i m a l - d u a lp r o b l e m ，t h em a i na l g o r i t h m so fs e m i d e f i n i t ep r o g r a m m i n g f i n a l l y , i ti n t r o d u c e s t h ep r a c t i c a la p p l i c a t i o n so fs e m i d e f i n i t ep r o g r a m m i n g t h ec o r eo ft h i s p a p e rg i v e st h e t r u s t r e g i o na l g o r i t h m f o rs e m i d e f i n i t e p r o g r a m m i n g f i r s t l y , w eo b t a i nt h eo p t i m a lc o n d i t i o n so fs e m i d e f i n i t ep r o g r a m m i n g a n di t sd u a lp r o b l e mb ym e a n so fc o m p l e m e n t a lr e l a xc o n d i t i o n s t h a ti sk k t c o n d i t i o n s s ow et r a n s f o r mt h es o l u t i o n so fs e m d e f i n i t ep r o g r a m m i n gi n t ot h e s o l u t i o n so fn o n l i n e a rd i f f e r e n t i a b l ee q u a t i o n s t h e nw ea l s ot r a n s f c i r n lt h en o n l i n e a r d i f f e r e n t i a le q u a t i o n si n t oan o n l i n e a rd i f f e r e n t i a b l ee q u a t i o n sb yu s i n ge x t e n s i v e f i s c h e r b u r m e i s t e r ss m o o t hf u n c t i o n s t h e nt h en o n l i n e a rd i f f e r e n t i a b l ee q u a t i o n si s c o n v e r t e dt oau n c o n s t r a i n e do p t i m a lp r o b l e m f i n a l l y , w ed e f i n ea ne f f e c t i v ef u n c t i o n b ym e a n so fl e a s t s q u a r ep r i n c i p l e s o t h es o l u t i o n so ft h eo r i g i n a ls e m d e f i n i t e p r o g r a m m i n gi st r a n s f o r m e di n t ot h eu n c o n s t r a i n e do p t i m a lm i n i m a xp r o b l e m f i n a l l y ，t h i st h e s i sw o r k so u tt h ea p p r o x i m a t es o l u t i o n so ft h eu n c o n s t r a i n e d o p t i m a lm i n i m a xp r o b l e mb ym e a n so ft r u s tr e g i o na l g o r i t h m ，t h a ti st h er e s u l t so f o r i g i n a ls e m d e f i n i t ep r o g r a m m i n g i ta l s oa n a l y s e s t h ee f f i c i e n c ya n dq u a l i t a t i v e r e l e v a n c eo ft h ea l g o r i t h m a tl a s t ，t h eg l o b a lc o n v e r g e n c ea n a l y s i so ft h et r u s tr e g i o n a l g o r i t h mi sp r o v e d t h ee x p e r i m e n ti n d i c a t e st h a tt h i sm e t h o di se f f e c t i v e k e yw o r d s ：s e m i d e f i n i t ep r o g r a m m i n g ；p r i m a l - d u a lp r o b l e m ；t r u s tr e g i o na l g o r i t h m ； c o n v e r g e n c e i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其他教育机构的 学位或证书而使用过的材料与我一同工作的同志对本文研究所做的任何贡献均 已在论文中作了明确的说明并深表谢意 签名： 关于论文使用授权的说明 嗍边夕 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保 留、送交论文的复印件，允许论文被查n 矛i ：i 借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保持论文 ( 保密的论文在解密后应遵守此规定) 签名：贮导师等名：卜菇叁扭期：越 武汉理丁大学硕十学位论文 第1 章绪论 1 1 半定规划的产生与发展 数学规划是研究决策问题的最佳工具之一，它包括创建数学模型、设计最佳 的计算方法、研究这些算法的理论性质及其在实际应用中的实现情况等自从上 世纪四十年代以来，数学规划就成为运筹学中十分活跃的一个分支，尤其是随着 电子计算机的普及，使得我们所设计的各种算法得以实现，更是促进了数学规划 的迅猛发展现在数学规划已经广泛应用于工程设计、控制理论、生命科学、信 息科学、交通通讯、经济计划以及国防建设等诸多重要领域，它已发展成为包括 线性规划、非线性规划、随机规划、双层规划、非光滑规划等许多分支的数学学 科 半定规翅j ( s d p ) 的产生可以追溯到二十世纪四、五十年代，几乎与线性规划 ( l p ) 是同时产生的半定规划是线性规划的一种推广，它是在满足约束“对称矩 阵的仿射组合半正定”的条件下使线性目标函数极大( 极小) 化的问题，这个约束 是非线性、非光滑、凸的所以，半定规划是一个非光滑的凸优化问题半定规 划的研究起源于上世纪六、七十年代，b e l m a n 和f a n 1 在1 9 6 3 年首次构造了一 个半定规划问题，接着前苏联的一些学者研究了半定规划( 当时也叫矩阵不等式) 在控制领域中的应用【引早在七十年代初期，c u l l u m ，d o n a t h 和w 6 l f e 在文献 3 中把一些有关对称矩阵特征值的优化问题转化为半定规划问题求解1 9 7 9 年 l o v a s z 4 1 通过求解半定规划得到图的s h a n n o n 容量的上界，从而解决了长期以来 的一个公开猜想，并导致了g r o t s h c h e l 、l o v a s z 、s c h r i j v e r 剐等人研究求解完美 图的最大独立集等组合优化问题的多项式时间算法的热潮s h o r 在文献 7 】中提 出了组合优化问题的半定规划松弛模型，这标志着半定规划真正成为解决组合优 化问题的重要工具之一在对这些实际问题的解决过程中，半定规划的理论和算 法得到了快速的发展尤其是在九十年代，n e s t e r o v 和n e m i r o v s k i i s , 9 1 基于自和谐 障碍函数的概念提出了解一般凸优化问题的多项式时间内点算法的理论体系和 算法的一般框架接着y i n y uy e i i o j 把k a r m a r k a r 提出的著名的解线性规划的势 下降内点算法成功的移植到了半定规划上来，最终导致了半定规划算法研究的飞 速发展1 9 9 5 年g o e m a n s 和w i l l i a m s o n t 眩】提出了用半定规划松弛方法来得到组 合优化问题中最大割问题的近似解的随机扰动方法，这种方法提供了半定规划解 决组合优化中许多n p 难问题的有效途径近年来，由于半定规划的理论和算法 武汉理工大学硕士学位论文 取得了很大进展，以及它在控制论【1 3 】、系统论、结构优化、组合优化1 4 , 1 5 】、滤波 器的设计和移动通信等领域【1 7 】的广泛应用，使得其成为数学规划领域日益引 人关注的研究方向 自从k a r m a r k a r 内点算法被成功移植到半定规划上以来，就使内点法成为求 解半定规划问题的主要算法【1 8 , 1 9 , 2 0 , 2 1 】此外，求解半定规划的方法还有势下降算 法【2 2 1 ，非线性规划方法【2 3 1 和割平面法【2 4 , 2 5 1 等内点法之所以备受人们关注有以 下几方面原因：第一，从理论上来说，内点法是非常高效的；第二，内点法在实 践中也是非常高效的【2 6 】；第三，内点法具有利用问题自身结构的能力我们知道， 解半定规划的主要计算量在于每一步迭代需要解的是一个最d , - 乘问题，而利用 内点法可以有效地利用问题的结构，譬如稀疏结构和工程技术领域中产生的 t o e p l i t z 结构等 九十年代中期开始，不可行内点法就逐渐兴起【2 7 , 2 8 , 2 9 】在此之前的文章一般 都是研究可行的内点法，即要求原始问题和对偶问题都是严格可行的，并且事先 知道存在一个严格可行点这与不可行内点法相对应，因此我们称这类方法为可 行内点法 上个世纪末本世纪初，半定规划( s d p ) 又被推广到非线性半定规划( n l s d p ) 问题【3 0 , 3 1 1 ，即线性或非线性目标函数受到( 非线性) 矩阵不等式和向量不等式约束 的优化问题它主要来自于最优结构设计【3 列、最优鲁棒控制【3 3 】、鲁棒反馈控制 设计【3 4 】、控制论 3 5 , 3 6 1 等领域，尤其是那些用如下线性矩阵不等式( 简称l m i ) 形式 m i nc t x s 2 m ( x ) 苎0 ( 其中m ( x ) = m 。+ t m ，m o ，m l ，一，坂为己知的玎刀实对称矩阵) 不能给 i = 1 出满意模型的优化问题已经出现的算法有：s q p 类型方法、可用于非线性非凸 优化问题的内点法、增广或改进的l a g r a n g e 技术、分枝切割方法等由于非线 性半定规划的研究才刚刚起步，它的发展还很不成熟，目前它是一个热门的研究 领域，有很大的发展空间因此国内外许多专家和学者正致力于这类规划问题的 研究，尤其是对于大规模非线性半定规划的研究 1 2 半定规划的研究现状及意义 半定规划的研究是在解决实际问题的过程中逐步发展起来 堑j 1 3 8 , 3 9 1 二十世纪 四十年代，随着运筹学的产生、发展和不断壮大、使得数学规划的研究领域不断 扩大，新问题的出现使线性规划无能为力，而半定规划在解决这些问题中的有效 武汉理t 大学硕十学1 1 i ) = 论文 运用使得半定规划的理论与算法获得了飞速的发展1 4 ，并且在半定规划解的存在 性、最优性条件、逆问题、灵敏度分析等方匝的研究也取得了一系列成果1 4 1 | ，这 就使得半定规划成为解决数学规划问题的基本工具 近二十年来，半定规划已经成为数学规划领域中一个非常活跃的研究方向， 受到了学术界很多专家和学者的重视，其主要原因如下： 首先，半定规划有有效的算法，求解线性规划的多项式时间算法被成功的推 广到半定规划【4 2 】上来，使半定规划的内点算法在理论上和应用上日趋成熟并且， 内点算法已被证明是解决中小规模问题可靠的有效算法i 4 引 其次，半定规划有着广泛的应用领域，半定规划问题在组合优化、逼近理论、 系统控制理论、结构设计、机械及电子工程】中都有重要应用而且现实生活中 许多实际问题都可以通过建立半定规划模型来加以解决可见，半定规划有着非 常广泛的应用自仃景 在半定规划的内点算法被提出以前，半定规划经过了零散而相对缓慢的发展 阶段，最早是b e l m a n 和f a n 1 j 所做的工作，1 9 6 3 年他们首次构造了一个半定规 划问题，当时称其为线性矩阵不等式后来又有许多学者把对称矩阵的最大特征 值的最小化问题转化为半定规划来研究，对此非光滑凸优化问题理论上可用椭球 法求解，虽然椭球法具有多项式收敛性，但实际计算效果很差，因此这种算法未 受到重视正是在这种背景下，人们在寻求理论上有效而实际上也切实可行的算 法取得了一定的成果n e s t e r o v 和n e m i r o v s k i l 8 , 9 1 基于自和谐惩罚函数理论得出半 定规划问题存在多项式时间的内点算法在理论上取得了突破性的进展，并取得了 较好的预期效果而在实际计算上，a l i z a d e h 2 1j 把著名的k a r m a r k a r 内点算法推 广到半定规划上，取得了比较好的效果y i n y uy e 在 4 5 】中证明了绝大多数线性 规划内点算法几乎可不变地推广到半定规划上目前这种算法在理论上非常成 熟，已经成为求解中小规模半定规划问题常用的算法 然而，来自实际中的问题往往都是大规模的，特别是组合优化问题的半定规 划松弛模型对于大规模问题，由于内点算法的每步迭代需要求解一个大规模的 稠密的线性方程组，这使得计算量急剧增加如何解决内点法在求解大规模问题 时的局限性，成为许多专家和学者当时面临的一大难题经过学者们的不懈努力， 终于取得了一些成果他们采用了最新的矩阵分解技巧和一些求解矩阵方程组的 最新算法，力求利用矩阵的稀疏性，如采用c h o l e s k y 4 0 1 分解、采用低阶分解、采 用预处理的共轭梯度法( c g 算法) 【4 6 】和梯度残量算法( c r 算法) h7 j 等，这些算法在 一定程度上可以求解大规模的半定规划问题，但是其求解的精度不高，不能满足 精度要求高的问题的求解b e n s o n l 3 9 1 提出的势下降内点算法可以充分利用某些组 合优化问题的半定规划松弛模型的特殊结构，从而可以求解矩阵维数达上千的问 武汉理：l ：大学硕+ 学位论文 题【l l 】最新由m i t u h i r of u k u d a 等【2 1 】提出的拉格朗日对偶一预估校正内点算法， 大量的数值实验表明该算法在求解大规模的半定规划问题时可以得到较高的精 度的最优解，但是规模更大的问题，这些方法仍面临着和原始对偶方法同样的固 有的困难 最近几年以来，专家和学者们研究了几种利用非线性规划求解大规模半定规 划问题的比较有效的方法【2 4 , 2 6 这些方法的一个共同点是用基于梯度的信息，从 而避免了运算量大的线性搜索和矩阵计算h e l m b e r g 和r e n d l l 5 1 将一大类半定规 划转化为非线性凸规划，利用非光滑凸规划的向量丛的方法求解得到了谱向量丛 方法实验证明该方法在精度要求不是很高时是求解一个大规模问题的一个有效 的方法b u r e r 和m o n t e r i o 2 8 】是利用矩阵变换x = w7 ，v r “”，将最大割问题 半定规划松弛模型转化为一个约束可微非线性规划问题，给出了实验结果非常好 的非线性规划算法 除了半定规划算法的研究非常活跃之外，有关半定规划应用方面的研究也取 得了多方面的成果g o e m a n s ，w i l l i a m s o n 1 2 】对最大割问题利用半定规划松弛模型 提出了o 6 6 9 近似随机扰动算法，h a l p e r i n ，z w i c k l 2 7 】进一步把算法的效率提高到 了0 7 0 2 h e m l b e r g ，r e n d l 和w e i s m a n t e l w j 研究了二次背包问题，提出了四种半 定规划松弛模型，并比较了他们之间的关系k a r g e r , m o n t w a n i 2 2 1 利用半定规划 松弛方法研究了旅行商问题一部分人也将半定规划松弛方法应用到鲁棒控制， 滤波器的设计和移动通信等领域中，并得到了较好的效果因此开拓半定规划的 应用领域，对已有的模型提出更强的半定规划松弛条件，利用半定规划松弛模型 设计近似算法都具有重要的理论意义和应用价值 与线性半定规划相比，非线性半定规划的研究才刚刚起步，还很不成 熟s h a p i r o t 3 0 】研究了非线性半定规划的一阶和二阶最优性条件，f o r s g r e n 在文献 4 9 中研究了非凸半定规划的一阶和二阶最优性条件，d r u m m o n d 5 2 1 研究了非线 性半定规划的中心路径，韩乔明【5 3 】将线性半定规划摄动为二次半定规划进行了研 究因此，进一步加深非线性半定规划的理论研究以及设计半定规划的有效算法 将是今后半定规划非常重要的研究方向 我们对半定规划的研究具有非常重要的意义首先，半定规划有着非常广泛 的应用领域，尤其是在组合优化中的应用，如最大割问题、顶点覆盖问题、图的 着色问题和旅行商问题等，都可以通过求解半定规划松弛问题获得原问题的上 ( 下) 界：其次，许多凸规划问题( 例如线性规划和凸二次约束下的二次规划问题) 都可以转化为半定规划松弛模型，所以半定规划提供了一个统一的方法，通过对 半定规划问题的研究，我们可以来研究上述一系列凸规划问题，并构造相应的算 法以及最后如何求解这些问题的最优解等 4 武汉理工大学硕士学位论文 因此，对半定规划的研究具有非常重要的理论意义和应用价值正如 o v e r t o n 4 1 1 所述：“对半定规划的研究不仅是现在，而且在将来的一段时间里都是 一个引人注目的方向，我们可以在这一领域内得到精妙的理论结果和有效的算法 以及广泛的应用” 1 3 本文的主要工作和内容安排 半定规划在实际生活中的许多方面都有着重要的应用因此，研究半定规划 的算法是件非常有意义的事情本文的主要工作是关于半定规划信赖域算法的研 究，其内容安排如下： 第一章就半定规划的产生与发展做了一个比较详细的概述，介绍了半定规划 最初的产生过程以及最近几十年来学术界关于半定规划算法研究的发展情况等 第二章中给出了半定规划的基本概念、半定规划的对偶理论、半定规划的主 要算法介绍以及半定规划的实际应用背景等 第三章中着重给出了求解半定规划的信赖域算法，首先通过半定规划的最优 性条件，将半定规划和其对偶问题转化为一个无约束的优化问题，然后利用信赖 域法来求解这个无约束的优化问题，最后给出了信赖域算法的收敛性证明 第四章是对本文内容的一个简单总结，并提出了本文所存在的问题和不足之 处，为我们以后的学习研究过程提供了一个发展方向 最后是参考文献、致谢以及本人在硕士学习阶段完成的论文目录等 武汉理f t 大学硕士学位论文 第2 章基本理论 2 1 半定规划的基本概念 2 1 1 半定规划 半定规划( s d p ) 问题的标准形式【1 3 】为： r a i nc x ( s d p ) s 2 4 x = 6 f ，i = 1 ，2 ，m ( 2 1 ) - 0 其中x r 为给定的门阶实对称矩阵，b = ( b i ，b 2 ，b o ) 7 r ”为给定的m 维向 量；“”或( 彳，b ) 表示f r o b e n i u s 内积，即对任意矩阵彳，b 为刀，2 阶实方阵时， 有彳b = ( 么，b ) = 色= 护( 彳7 b ) 三o ( - o ) 表示x 是半正定( 正定) 矩阵， 用尺? 表示刀，2 阶半正定矩阵集合，而用r ：”表示正定矩阵集合，a r 表示矩阵a 的转置c ，4 ( i = 1 ，m ) 为，z 门阶实矩阵，利用对称矩阵和反对称阵的性质， 可以假设c ，4 为对称的实矩阵，如果矩阵c ，a i 为不对称的实矩阵时，则我们可 以把牮小学户k 一圳阿 式： 为了简便起见，我们可以把半定规划的标准形式写成如下的等价的简便形 其中，a ：r “”一尺”表示线性算子，定义为： 6 ( 2 2 ) “劫。 以从胁一 m “x m 甜 武汉理j 【= 大学硕十学位论文 a x = 4 x a 2 x a m x 6 = ( 6 l ，如，瓦) 7 定义2 1 1 对于半定规划( 2 1 ) ，如果对某一x 满足其约束条件，则称x 为半 定规划( 2 1 ) 的一个可行解，由所有可行解组成的集合称为可行集 通过对半定规划标准形式的研究，我们可以得到如下的有关半定规划的几条 简单性质1 8 1 ： 性质2 1 1半定规划( s d p ) 问题是一个凸规划问题 因为其目标函数及约束函数都是凸函数，其约束集为凸集 性质2 1 2 半定规戈t j ( s d p ) 的线性矩阵不等式约束是非光滑的、非线性的， 但它却是凸的 性质2 1 3 若半定规翔j ( s d p ) 的最优解存在，则在可行集的边界上一定存在 一个最优解 性质2 1 4 半定规划( s d p ) 的可行集的边界一般不是光滑的，而是分段光滑 或分片光滑的 为了求出对偶问题，我们利用l a g r a n g e 方法可以得到半定规划( s d p ) 问题的 对偶规划( s d d ) 形式【1 3 】： f 一? r y ( s d d ) 忸只4 + z = c ( 2 3 ) l z i = l 兰。 其中z 群x n ，y r ” 在得出半定规划的对偶规划形式后，我们要说明它也是半定规划问题而为 了说明对偶舭i j ( 2 3 ) 也是半定规划，我们假设原半定规划( 2 2 ) 有可行解戈在目 标函数中，作代换 ( 6 ，y ) = ( 以y ) = ( 又，彳r 夕) = ( j ，c z ) 然后令s ( 么) 表示彳的零空间，则x ，z 所属的仿射子空间分别可用 又+ s ( 彳) ) 和 c + s ( 么) 上 来表示因此，原半定规划和其对偶规划还可以表示为： fm i n ( c ，x ) ( s d p ) 1 s ，x ( 足n j + s ( 彳) ) ) 7 武汉理工大学硕士学1 1 i ) = 论文 im i n ( 又，c z ) 0 0 k ( r n ! nn i a s z a - t ) ) 1 f l 尺。“” c + s ( i 其中，r “”表示n 门实对称半正定矩阵的全体从以上两式可以看出，半 定规划的对偶规划仍然是半定规划所以，式( 2 2 ) 和( 2 3 ) 均可作为半定规划问题 的原始模型，它们在本质上是没有区别的 从半定规划的标准形式可以看出，半定规划与线性规划的主要区别在于半定 规划用半正定矩阵锥取代线性规划中的非负象限半正定矩阵约束是非线性的， 因此线性规划的许多性质和算法( 如单纯形法) 对半定规划不再适用，因此半定规 划的算法研究在很多方面都不同于线性规划，正是因为如此，近年来专家学者们 都在致力于半定规划的研究因此，半定规划受到了越来越多的人的重视，与此 同时，半定规划的研究也比线性规划的研究要更为复杂，而非线性半定规划的研 究就更加复杂了 2 1 2 对偶理论 半定规划是线性规划的一种推广，因此半定规划与线性规划有着极其相似的 对偶理论f 1 5 , 1 8 1 ，下面介绍半定规划的对偶理论及其在求解半定规划算法中所起的 作用在这之前我们先引入两个引理： 弓i 理2 1 1 1 1 3 i n ：a ，b r ”。”且么三o ，b 三0 ，则a b 0 引理2 1 2 1 1 5 i设彳，b r 且彳兰o ，b 三0 ，则a b = 0 当且仅当a b = 0 因为半定规划是线性规划的推广，与研究线性规划一样，我们先介绍一下半 定规划的弱对偶定理 定理2 1 3 1 3 1 5 1 ( 弱对偶定理) 令x 与( y ，z ) 分别为半定规划原问题( 2 1 ) 和 其对偶问题( 2 3 ) 的可行解，则c x b r y 我们可以定义对偶间隙为r = ( z ，x ) ，记p 和d 分别为半定规划原问题( 2 1 ) 和其对偶问题( 2 3 ) 的最优值，即有： p = m i n c xa , x = 6 f ，i = 1 ，2 ，m x 三0 d ：m a xb t y m 4 + z ：c ，z 三0 1 由定理2 1 3 可知，p d 武汉理工大学硕士学位论文 如果对偶间隙7 7 = ( z ，x ) = 0 ，则x ，z 分别为半定规划原问题( 2 1 ) 和其对偶 问题( 2 3 ) 的最优解，反过来，即使x ，z 分别为半定规划原问题( 2 1 ) 和其对偶问题 ( 2 3 ) 的最优解，也并不一定隐含( z ，彳) = 0 我们假设，和分别为半定规划原问题( 2 1 ) 和其对偶问题( 2 3 ) 的最优解 集合，则可以得到： ，= xc x = p ，4 x = 匆，f = l ，2 ，聊x 三0 r 朋 1 = y 妒y = d + ，m 4 + z = c ，z 三0 l 1 = 1 j 从以上集合可以看出，即使最优值p 或d + 是有限的，然而解集合k y o p ， 也可能为空集因此我们要引进严格可行解的概念1 2 引 x 为原半定规戈t j ( 2 1 ) 严格可行解是指x 为( 2 1 ) 的可行解且x o 如果( 2 1 ) 存在严格可行解，则称( 2 2 ) 具有严格可行性 ( j ，z ) 为原半定规划对偶问题( 2 3 ) 严格可行解是指( y ，z ) 为( 2 3 ) 的可行解且 z - 0 如果( 2 3 ) 存在严格可行解，则称( 2 3 ) 具有严格可行性 有了严格可行解概念后，我们可以得到半定规划的强对偶定理，此定理在推 导半定规划的k k t - 条件中有着非常重要的作用 定理2 1 4 【1 5 , 1 8 】( 强对偶定理) 设 ( 1 ) 半定规划原问题( 2 1 ) 存在严格可行解； ( 2 ) 半定规划对偶问题( 2 3 ) 存在严格可行解 则有下面结论： ( i ) 如果定理中条件至少有一个成立，则p 。= d ( i i ) 如果定理中两个条件都成立，则p = d ，且，和，均为非空集 该定理的证明可以参见n e s t e r o v 和n e m i r o v s k y 的文献 8 ，9 】定理2 1 4 是一 般对偶理论在凸分析中的应用，其严格可行性条件也称s l a t c r 型约束规格，它是 保证凸优化问题强对偶定理成立的一个充分条件为了在比较弱的条件下给出强 对偶成立的条件，m v r a m a n a ，l t u n c e l ，a n dh w o l k i c 在文献 5 0 中研究了不要求 严格可行的对偶理论虽然他们得到的结果具有重要意义，但是其形式很复杂， 还没能得到广泛的应用，因此在这里我们就不讨论它 假设半定规划原问题( 2 1 ) 和其对偶问题( 2 3 ) 都存在严格可行解，则可保证至 少存在一对原始一对偶最优解，即可知最优解集合k 。和都是非空集，从而 就存在可行解x ，y 使得( c ，x ) = b r y = p = d ，r l = ( z ，x ) = 0 由引理2 1 2 有 9 武汉理工大学硕士学位论文 应= 0 x z = 0 称为互补松弛条件，它可看成是线性规划互补松弛条件的推广 通过以上的分析，我们可以给出半定规划的最优性条件【1 5 】，假设半定规划原 问题( 2 2 ) 和其对偶问题( 2 3 ) 都存在严格可行解，则x 为( 2 2 ) 的最优解当且仅当存 在( x ，z ) r “”r “”使得 f 掣= b ，x 三o a 7y + z = c ，z 三0( 2 4 ) l( z ，x ) = 0 成立这就是半定规划的的k k t - 条件，而且该条件是充分必要条件把( 2 4 ) 写 成等价的形式如下： 只4 + z = c j = l 4 f x ；b ii = l ，2 ，m( 2 5 ) 义z = 0 x z o 与线性规划类似，半定规划可能以各种各样的形式出现虽然可以经过一系 列的变换使其转化成标准形式，但却没有直接利用对偶性方便因此我们可以给 出求对偶半定规划的一般准则【6 l 】如下表所示： 表2 1求对偶规划的准则 m i nm a x 矩阵， 0 矩阵，三 变约 矩阵，_ 0 ( 2 6 ) 因为对任意d r ，集合 x _ _ 0a x = 6 ，( c ，x ) = d ) 是有界闭集，且目标函数是严 格凸的，而( 2 6 ) 中的约束矩阵x 0 ，所以罚问题( 2 6 ) f 1 0 最优解存在且唯一【1 9 】因 此易知( 2 6 ) 的最优解一定在半正定锥的内部 我们通过引进罚因子y ，把上述罚问题( 2 6 ) 可转化为一个无约束的优化问 题： 三( x ，y ) = c x 一l o g d e t ( x ) + y 7 ( 6 4 x ) 然后再利用l a g r a n g e 乘子法可得( 2 6 ) 的最优性条件为： fa x = b ，x - 0 a r y + z = c ，z - 0 ( 2 7 ) l z x = t i l 其中，表示单位矩阵，前两个条件分别是原问题和对偶问题严格可行解的条件； 当一0 时，第三个条件相当于是互补松弛条件条件( 2 7 ) 是罚问题( 2 6 ) 最优解 的充分必要条件 对于一固定的，( 2 7 ) 存在唯一解( 以，z u ) 以，z l , 分别是( 2 2 ) 和( 2 3 ) 的一 个可行解，且其对偶间隙为刀当啼。时，由( 2 7 ) 的解( 以，乙) 构成的曲线称 为中心路径，这是一条光滑曲线15 1 我们又知道，当- - + o 时，( x u ，乙) 存在聚 点，且若( ，z ) 是( ，乙) 的聚点，那么x 是半定规划原问题( 2 2 ) 的最优解， z 是其对偶问题( 2 3 ) 的最优解 武汉理一i ：大学硕十学位论文 九。( 么) 丸i 。( 召) ( 彳，b ) 疗a 。( 彳) 九缸( b ) 引理2 2 2 【1 5 】设x7 ，x 。为原半定规划( 2 2 ) 的解，z ，z ”为其对偶问题( 2 3 ) 的 x ，x ” x r ：”l 从= 6 ) z ，z 。 z l z = c - a 7 y ，y r ” ( x 一”，z 7 - z ”) = 0 定理2 2 3 对给定的序列 以) ，满足以 o 且当k _ + 时有心j 0 当 地一。时，( x u , ，z 脚) 一定存在聚点，且如果( x ，z ) 为( ，气) 的聚点，那么x 为原始问题( 2 2 ) 的最优解，z 为对偶问题( 2 3 ) 的最优解 为了确定( 厶，乙) ，需求解下列非线性方程组1 蟹戊班 磊c 卜 亿8 ， 乞+ v g ( a x ，每，z ) 7 = 0 ( 2 9 ) 得到搜索方向( 似，a y ，a z ) 在这里搜索方向是由下列线性系统1 3 1 得到的 a z k , f = 一( 制一6 ) a r a y + a z - - ( a7 y + z - c ) ( 2 1 0 ) 岘+ x a z = , u l 一避 与线性规划不同的是一般x ，z 是不可交换的，即x z z x 这样解( 2 1 0 ) 得到的 z 虽然是对称的，但从一般不是对称的，这与下一步迭代需要x4 - 口赵是对 称的相矛盾利用不同的对称技巧可以到到不同的内点算法其中主要有n t 方 向【2 1 1 、h k m 方向【2 2 】、a h o 方向【2 3 】、k m 方向等，这些方法得到的从是对称 的z h a n g 5 2 】通过引进下述对称化算子统一了这些方向 h p ( m ) = 寺ip m p 一+ ( p m p 1 1 l ( 2 11 ) 武汉理丁大学硕十学位论文 兵中p 是非奇异矩阵 则纪+ x z = ，一勉等价于日p ( 勉+ 杞+ 越彳) = m 当p ：x 一，为k m 方向；当p = z 一2 ，为h k m 方向；当p7 尸= w ，为n t 方向； 其中，形- x ；x l f 厨； x ；，当尸= ，a h o 7 与- 向 利用上述不同的搜索方向就可以得到不同的内点算法，下面我们给出内点算 法的一般框架： 内点算法一般步骤： 步0 ：给定初始可行点( x 。，y o , z 。) 满足x 。 - o ，z 。 - o ； 步l ：选择： 步2 ：计算( 以，a y ，z ) ，如需对称化，可利用上面的对称化算子得到对称矩阵； 步3 ：选择口( o ，1 】使得x + 础 - o ，z + a a z - 0 ； 步4 ：令( x ，y ，z ) = ( x + a a x ，y + a a y ，z + a a z ) ； 步5 ：女口果a x - b ，0 a 7 y + z cl f ，( x ，z ) 都足够小时，停止否则返回步1 为了对内点算法有一个更加清楚的认识，下面我们简单介绍h k m 方向捌 、的可行内点算法 考虑中心路径的邻域： 。噼卜，：kc 砷竿，l i f 臼华冽) 显然，中心路径有界： ( 1 - 0 ) 华丑( z 品x z 卜臼) 竿 选择初始点( x 。，z 。) 和口，满足：x 。o ，z 。三o ，( x 。，z 。) n ( o ) 令：f ，1 一睾 丝型，贝| j 有下面定理成立： 门 ，z 定理2 2 4 2 2 1 设( 战，缈，z ) 是h k m 方向，令x - x o + 似，z ：= z o + z ， 则可得 ( i ) x - o ，z o ，( x ，z ) n ( o ) 武汉理工大学硕士学位论文 ，x , z 一= ( ，一砉p z 。) 选择适当的( x 。，z 。) 非常困难，通常转化为求解如下的与原规划等价的辅助 半定规划满足辅助半定规划初始点条件的点( x 0z 。) 较容易得到1 m i n 9 8 s ，彳x r b + 1 9 万：0 一彳7 y + r c 1 9 e z = 0 b r y - ( c ，x ) + , g a - p = o ( 2 1 2 ) 万7 y + ( e ，x ) - r a - a + 1 3 = o x 三0 ，f 0 ，1 9 0 ，z 芝0 ，p 0 ，仃0 其中 = - a i + b ，e = c - i ，a = ( c ，) + l ，= n + 2 ，显然y o = o ，x 。= z 。= ， r o = 矿= p o = 仃o = 1 是在中心路径上的可行点 设( x