（运筹学与控制论专业论文）求解非凸半定规划问题的一种非线性lagrange方法.pdf

大连理工大学硕士学位论文 摘要 经典的l a g r a n g e 函数( 即关于乘子向量与约束映射均是线性的函数) 在凸规划对偶理 论的研究中起重要的作用，尤其线性规划与二次规划的对偶理论要通过经典的l a g r a n g e 函数来表达但对于非凸规划而言，基于经典l a r a n g 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 函数的修正形式，它关于乘子向量或约束函数是非线性 函数，基于非线性l a g r a n g 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 方法的成熟和非凸半定规划在实 际问题中的广泛应用，我们尝试把这种方法推广到求解非凸半定规划中我们构造了基 于一种非线性函数的对偶算法来解决非凸半定规划问题，并证明了其局部收敛性，即由 非线性l a g r a n g e 算法产生的序列局部收敛到原问题的k k t 解，并建立了参数解的误差 估计式本文取得的主要结果可概括如下； 1 本文第二章归纳和总结了非凸半定规划的最优性条件，这些条件是下一章构造的 对偶算法的理论分析所必备的这章首先介绍了抽象约束优化问题的最优性条件，之后把 它用到非凸半定规划中去 2 ，本文第三章给出了非凸半定规划的一个非线性l a g r a n g e 算法，并证明了它的收敛 性即证明了在适当条件下，罚参数存在个阀值，当罚参数小于这一阀值时，由非线性 l a g r a n g e 算法产生的序列局部收敛到原问题的k a r u s h - k u h n - t h c k e r ( k k t ) 解，并建立 了参数解的误差估计式 关键词；非凸半定规划；最优性条件；非线性l a g r a n g e 算法；收敛定理； 求解非凸半定规划问题的一种非线性l a g r a n g e 方法 an o n l i n e a rl a g r a n g em e t h o df o rs o l v i n gn o n c o n v e x s e m i d e f i n i t ep r o g r a m m i n gp r o b l e m s a b s t r a c t c l a s s i c a ll a g r a n g i a n si nw h i c ht h em u l t i p l i e rv e c t o r sa n dt h ec o n s t r a i n tm a p p i n g sa r e i n v l o v e di nl i n e a rw a y s ，p l a ya ni m p o r t a n tr o l ei ns t u d i e so nt h ed u a l i t yt h e o r i e so fc o d , - v e xp r o g r a m m i n g s ，e s p e c i a l l yt h a to fl i n e a rp r o g r a m m i n g sa n dq u a d r a t i cp r o g r a m m i n g s w h i c hs h o u l db ee x p r e s st h r o u g hc l a s s i c a ll a g r a n g i a n s b u ti nn o n c o n v e xp r o g r a m m i n g s ， t h ep r i m a lp r o b l e m sa n dt h ed u a l i t yp r o b l e m sw h i c ha r eb a s e do nc l a s s i c a ll a g r a n g i a n s h a v ed u a l i t yg a p s s om a n ys h o l a r sa r eb e c o m em o r ea n dm o r ei n t e r e s t e di ns t l l d y i n g o nt h ev a r i e so fc l a s s i c a ll a r a n g i a n s n o n l i n e a rl a g r a n g i a n sa r ev a r i a n t so ft h ec l a s s i c a l l a g r a n g i a n i nw h i c ht h em u l t i p l i e rv e c t o r so rc o n s t r a i n tf u n c t i o n sa r ei n v o l v e di nn o n l i n - e a rw a y s n o n l i n e a rl a g r a n g em e t h o d sa r ed u a lm e t h o d sb a s e do nn o n l i n e a rl a g r a n g i a n s f o rs o l v i n go p t i m i z a t i o np r o b l e m s a sd u a lm e t h o d su s u a l l yr e q u i r en or e s t r i c t i o n so nt h e f e a s i b i l i t yo fp r i m a lv a r i a b l e s ，n o n l i n e a rl a g r a n g em e t h o d sa r ep l a 舜n gi m p o r t a n tr o l e s i ns o l v i n gc o n s t r a i n e do p t i m i z a t i o np r o b l e m s t h i sd e s s e r a t i o na t t e m p t st oe x t e n dt h i s m e t h o dt os o l v i n gn c s d pf o rt h ep r o f i c i e n c yo fn o n l i n e a rl a g r a n g e i a na l o g r i t h ms o l v - i n gn o n l i n e a rp r o g r a m m i n ga n de x t e n s i v eu t i l i z a t i o no fn c s d pi np r a c t i c a lp r o b l e m s w ec o n s t r u c tad u a la l o g r i t h mb a s i n go nan o n l i n e a rl a g r a n g i a nf o rs o l v i n gn c s d pa n d t h e np r o v ei t sl o c a lc o n v e r g e n c e 黜i st os a y t h es e q u e n c ep r o d u c t e db yt h ea l o g r i t h m c o n v e r g et ok k tp o i n t so fp r i m a lp r o b l e m a n da tl a s tw ee s t a b l i s ht h ee r r o re s t i m a t e f o r m u l a t h em a i nr e s u l t s ，o b t a i n e di nt h i sd i s s e r a t i o n ，m a yb es u m m e r i z e da sf o l l o w s ： 1 c h a p t e r 2i sd e v o t e dt os u m m a r i z i n gt h eo p t i m a lc o n d i t i o n so fn c s d pw h i c ha r e i n d i s p e n s a b l et ot h en e x tc h a p t e r t h i sc h a p t e ra tf i r s ti n t r o d u c e st h eo p t i m a lc o n d i t i o n s o fa b s t r a c tc o n s t r a i n to p t i m i z a t i o n a n dt h e nu t i l i z e st h o s ec o n d i t i o n st ot h en c s d p 2 c h a p t e r 3i sd e v o t e dt ob r i n g i n gf o r w a r da n o n l i n e a rl a g r a n g ea l g o r i t h mf o rn c s d p p r o g r a m m i n ga n dp r o v i n gi t sc o n v e r g e n c e n a m e l y , u n d e rs o m em i l da s s u m p t i o n s ，i ti sp r o v e d t h a tt h e r ee x i s t sat h r e s h o l do ft h ep e n a l t yp a r a m e t e rs u c ht h a tt h e s es e q u e n c e sg e n e r - a t e db yt h en o n l i n e a ra l g o r i t h ml o c a l l yc o n v e r g et ot h ek k t p o i n to fn c s d pw h e nt h e p e n a l t yp a r a m e t e ri sl e s st h a nt h et h r e s h o l d m o r e o v e r ，w ee s t a b l i s ht h ee r r o rb o u n do f t h es o l u t i o n sw i t ht h ep e n a l t yp a r a m e t e r k e yw o r d s ： n o n c o n v e xs d p ；t h eo p t i m a lc o n d i t i o n s ；n o n l i n e a rl a g r a n g i a na l g o - r i t h m ；c o n v e r g e n c et h e o r e m n 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工作 及取得研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学或 其他单位的学位或证书所使用过的材料与我一同工作的同志对本研究所做 的贡献均已在论文中做了明确的说明并表示了谢意 作者签名：毛k 乏b l l ：z 坦2 ：2 ：j 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 越定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 饭，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 艾。 作者签名。主丝。盎、 导师签名钽 缉年4 月l 日 大连理工大学硕士学位论文 1 绪论 本章介绍了半定规划( s e m i d e f i n i t ep r o g r a m m i n g ) 的研究现状和现实意义，综述了解 决非线性优化问题的非线性拉格朗日方法的发展历史和最新成果，列出了本文的研究成 果，并在最后给出了本论文中常用符号代表的含义 1 1半定规划的研究现状和现实意义 半定规划( s d p ) 是约束为半正定锥的一类特殊的对称锥优化问题此问题的一般形 式为： 谢出，? ) ，( 1 1 1 ) s u b j e c tt oc ( x 110 、7 其中c ：p s m 是从舻到m m 维实对称矩阵空间s ”的个映射 a 5 0 表 示a 是负半定矩阵 最近十几年，半定规划已经成为一个相当活跃和热门的研究领域，吸引了一大批科学 研究工作者，其中包括凸规划线性代数数值优化、组合优化、控制论、特征值优化以及统 计方向的许多专家究其原因，是因为人们发现半定规划在这些领域有着极其广泛和重要 的应用特别是近些年来，随着半定规划问题内点算法的不断发展以及优化理论的不断完 善，许多原来很难解决甚至不能解决的问题都可以转化为求解半定规划模型，然后通过对 半定规j 秘模型的求解，进而可以得到比较满意的结果见v a n d e n b e r g h e ，b o y d ( 1 9 9 6 ) “， h e n r y , r o m e s h ，l i e v e n ( 2 0 0 0 ) 闼，k l e r k ( 2 0 0 2 ) 3 l 等等另外，通过将非凸二次规划转化为 半定规划，进而求解半定规划得到非凸二次规划的近似解提供了求解非凸二次规划的另 一种途径，见n e s t e r o v ，w o l b 奶船，y e ( 2 0 0 0 ) t a l 半定规划的产生最早要追溯到二十世纪四、五十年代，几乎与l p 的产生一样早在 五、六十年代，由于g b d a n t z i g 的高效单纯形法的发现，l p 得以迅猛发展但是，自 b e l l m a n 和f a n 在1 9 6 3 年发表关于s d p 的文章剐开始，二十多年里s d p 却一直被人 们忽视，主要是由于s d p 的可行集不再是多面体，并且没有适用的单纯形法直到八， 九十年代，f l e t c h e r 【b 】f l 激发了s d p 的研究兴趣，出现了许多s d p 的理论上高效的算 1 求解非凸半定规划问题的一种非线性l a g r a n g e 方法 法，尤其是内点法问世以后，对s d p 领域的研究才逐渐火爆起来，s d p 进入了个飞速 发展的崭新阶段国际上涌现出一批半定规划专家，如n e s t e r o v ，n e m i r o v s k y , a l i z a d e h ， r o d d ，b o y d ，f l e t c h e r 等等 近些年来国内外对于半定规划的研究主要集中在线性半定规划( 1 i n e a rs e m i d e f i n i t e p r o g r a m m i n g ) 的研究，线性半定规划具有如下形式， n m m n i z e ( c ，x ) s u b j e c tt o ( a i ，x ) = 6 i ，l = 1 ，m x 兰0 其中( a ，b ) = t r ( a t b ) 线性半定规划是线性规划的推广，它是通过将线性规划中的向量变量用矩阵变量取 代，向量的非负性由矩阵的非负半定取代得到的其约束是非线性的，非光滑的，但却 是凸的，因而半定规划是凸规划由于线性半定规划矩阵锥是凸锥且其边界是非线性的， 因丽线性半定规划是非线性凸规划同时，线性半定规划与线性规划有许多类似的性质， 例如t 1 ) 对偶理论s 半定规划的对偶理论在形式上与线性规划很相似，但是但是由于线性半定 规划是非线性规划，所以要用稍强一点的条件来保证强对偶理论的成立 2 ) 内点方法t 许多求解线性规划的内点算法都可以推广到线性半定规划，并且在实践中 都非常有效虽然线性规划中内点算法是否比单纯型法优越还存在争议，但在线性半定 规划中内点算法的优越性则是人们公认的，这是由于可行域的非线性则是人们公认的。这 是由于可行域的非线性使得单纯型法不再适用 1 9 8 4 年，k a r m a r k a r 提出了l p 的内点法唑该算法及其随后产生的算法具有比较 好的多项式复杂性，在实践中却非常有效k a r m a r k a r 的文章在当时引起了强烈的轰动 内点法随后被用于处理凸二次规划问题和某些线性互补问题1 9 8 4 年到1 9 9 7 年期间，l p 的内点法逐渐发展成熟，达到近乎完善的程度 1 9 8 8 年，n e s t e r o v y j 和n e i n i r o v s k y i u 】取得了一个重大突破他们基于对具有自协 调性质的障碍函数的研究，证实了内点法原则上可以运用到一切凸优化问题为了实用， 障碍函数的一阶和二阶导数必须易于计算n e s t e r o v 和n e m i r o v s k y 证实了每个凸集 都存在个自协调障碍函数，但一般地说，它们的自协调障碍函数不易计算幸运的是半 定规划问题是一类重要的凸优化问题，它们有易于计算的自协调障碍函数，所以内点法 适用关于一般凸优化问题的内点法的比较完整的一篇参考文献是d e nh e r t o g 于1 9 9 3 年发表的。线性、二次及凸规划的内点法” 1 1 】 1 9 9 2 年，n e s t e r o v ，n e m i r o v s k y , a l i z a d e h 1 翻与k a m a t h ，k a r m a r k a r 1 3 1 1 4 独立的 把l p 的内点法推广到半定规划，使内点法成为求解半定规划问题的主要算法 2 大连理工大学硕士学位论文 内点法之所以备受人们的关注是因为t 首先，内点法在实践中非常高效；第二，内点 法从理论上来说也是高效的；第三，具有利用问题结构的能力我们知道，解s d p 的主 要计算量在于每一步迭代需要解的最小二乘问题上，利用内点法可以有效地利用问题的 结构，譬如稀疏结构和工程技术领域中产生的t o e p l i t z 结构等9 0 年代中期开始，不可 行内点法逐渐兴起 1 5 1 1 0 l l “1 在此之前的文章大都研究可行的内点法，即要求原始问题 和对偶问题都是严格可行的，并且事先知道个严格可行点与不可行内点法相对应，我 们称这类方法为可行内点法近年来，随着内点法求解凸规划一般理论的提出，内点法无 论从理论上还是实践上都成为求解线性半定规划的最好算法，因而目前对求解线性半定 规划算法的研究成为国际上数学规划领域的一个研究热点 上个世纪末本世纪初，s d p 又被推广到非线性半定规划( n l s d p ) 问题1 1 硎【瑚，即线 性或非线性目标函数受到( 非线性) 矩阵不等式和( 或) 向量不等式约束的优化问题。它主 要来自最优结构设计瞄u 1 、最优鲁棒控制瞄l l ，鲁棒反馈控制设计【z 勰等领域，尤其是线 性半定规划不能给出满意模型的优化问题n l s d p 才刚刚起步，它的发展还很不成熟 因此，研究求解非线性半定规划的算法无疑是有重要意义的综观人们对非线性半定规 划的研究，我们发现这方面的工作相当有限，见b e n - t a l ，j a r r e ，k o e v a r a ，n e m i r o v s k i i ， z o w e ( 2 0 0 0 ) 2 3 1 ，j a r r e ( 2 0 0 0 ) 2 4 1 ，b o n n a n s ，c o m i n e t t i ，s h a p i r o ( 1 9 9 9 ) 1 2 5 1 ，s h a p i r o ( 1 9 9 7 ) 2 6 1 ， f o r s g r e n ( 2 0 0 0 ) t 引】s h a p i r o ( 1 9 9 7 ) 2 q 通过锥的性质给出了非线性半定规划一阶和二阶 最优性条件，f o r s g r e n ( 2 0 0 0 ) c 2 7 采用非线性规划的最优性条件分析的技巧也讨论了非线 性半定规划的最优性条件m o s h e y e v ，z i b u l e v s k y ( 2 0 0 0 ) 1 2 8 】提出了一类惩罚障碍乘子方 法用于求解约柬为线性矩阵不等式的非线性半定规划问题；b u r e t ，m o n t e i r o ，z h a n g ( 2 0 0 2 ) 瞄韧【5 u 】考虑将一类特殊的半定规划转化为非线性规划进行求解；b e n - t a l ，j a r r e ，k o e v a r a ， n e m i r o v s k i i ，z o w e ( 2 0 0 0 ) 2 3 ，j a r r e ( 2 0 0 0 ) 2 4 1 ，p d n g e r t z ( 1 9 9 7 ) 3 1 1 采用障碍方法求解非线 性半定规划然而，障碍方法要求迭代初始点是严格可行的内点，这一要求在实际中往往 很难满足目前它是个热门的领域，很有发展前途许多专家和学者正致力于n l s d p 的研究，尤其是对于大规模n l s d p 的研究本文中讨论的非凸半定规划( n c s d p ) 问题 就属于非线性半定规划问题 1 2非线性优化问题的非线性拉格朗日方法的发展历史和最新成果 9 7 】 考虑非线性规划问题 i n i n i l 2 1 i z e f o ( z ) s u b j e at o五( z ) 芝0 ， = 1 ，m ， ( 1 2 1 ) p ) = o ，j = ，z 其中是z r ， ：舻一r 1 ，i = 1 ，m ；b ：r n r 1 ，j = ，z 是实值函数问题 3 求解非凸半定规划问题的一种非线性l a 孕a n g e 方法 ( 1 2 1 ) 的经典( 线性) l a g r a n g e 函数定义为 它在描述问题( 1 2 1 ) 的最优条件及设计算法中起着重要的作用对于凸规划，利用 经典l a g r a n g e 函数可以建立鞍点理论，也可以发展基于对于某一矿求解r a i nl ( x ，u 。) 的对偶算法对于非凸非线性规划，l ( z ，u 8 ) 通常是非凸的，即使u 。当在矿的附近，茹 在矿的邻域内也是这样，其中( 矿，矿) 是问题的k u h n - t a c k e r 点，因而在数值计算上遇 到困难 无论在线性规划中还是在非线性规划中，惩罚函数法和对数函数法对算法的研究中 均起着重要的作用众所周知，内点法跟对数障碍函数密切相关，见y e ( 1 9 9 8 ) 1 3 2 1 对于 凸规划，障碍函数法在内点算法的设计中同样重要，见n e s t e r o v & n e m i r o v s k i i ( 1 9 9 4 ) 3 3 】。 国内外学者对障碍函数法都做了大量的工作，提出了众多的算法 惩罚函数法函数法旨在将约束优化问题转化为序列无约束优化问题，该方法的研究 可以追溯到c o u r a a t ( 1 9 4 3 ) 3 4 1 ，f r i s h ( 1 9 5 5 ) ；j 训，c a r r o u ( 1 9 6 1 ) 3 6 等的工作关于研究惩罚函 数法和障碍函数法的工作可以参阅f i a c c o & m c c o r m i c k ( 1 9 6 8 ) 1 3 7 ，m c c o r m i c k ( 1 9 7 1 ) 3 8 1 3 9 等中工作然而，早期的障碍函数法或惩罚函数法要求惩罚参数趋于无穷大或零，这在数 值计算中面临着诸多困难 为了克服匕述方法的不足，t t e s t e n s ( 1 9 6 9 ) 4 0 1 与p o w e u ( 1 9 6 9 ) 4 1 1 各自独立提出了近 似增广l a g r a n g e 函数 f ( z ，入) = ，0 ( z ) + a r ( z ) + 2 1 1 h ( z ) i | 2 ( c o ) 和 f p ( x ，a ，0 ) = ，o p ) + 芝一= h j ) + 巳】2 j 兰1 来求解具有等式约束的非线性优化问题最初的乘子法是基于二次增广l a g r a n g e 函数建 立的这一方法的优点在于早期罚函数的病态问题以及收敛速度慢等弱点 h a a r h o f f & b u y s ( 1 9 7 0 ) 1 4 2 1 进一步研究了求解一般非线性优化问题的二次乘子法关 于应用增广l a g r a n g e 函数研究乘子迭代的一些有意义的早期工作可参见m i e l e 等人的 工作 4 3 4 4 1 1 4 5 1 p o w e l l ( 1 9 6 9 ) 4 1 1 对等式约束的最优化问题，利用他娴熟的矩阵分析技巧 证明了经典增广l a g r a n g e 函数的收敛性 p o l y a k & t r e t y a k o v ( 1 9 7 3 ) 4 6 1 证明了在适当条件下，存在惩罚函数的f 珂值，当惩罚 参数小于( 或大于) 该阀值时，由该方法产生的解序列以几何收敛率收敛到原始最优 4 pb吩 。脚 一 z 五 m ：l p 矗 = ：， p l 大连理工大学硕士学位论文 解，并给出了与罚参数相关的解的误差上界r o c k a f e u a r 4 。7 1 1 4 8 3 把h e s t e n e s ，p o w e l l 和 h a d o r f f & b u y s 的思想有进一步推广到应用于不等式约束优化问题，得到了一般问题的经 典增广l a g r a n g e 函数，并对凸规划建立了建立了增广l a g r a n g e 函数的理论 b e r t s e k a s ( 1 9 7 5 ) 在文【蝴中讨论了二次乘子法的收敛速率，并在文中p u j 指出，所建 立的二次乘子法优于标准的二次惩罚函数法r u p p 5 1 l 提出了乘子法的收敛条件，该条 件不必考虑初始乘子的选择b e r t s e k a s 【b 2 l 针对凸问题提出了惩罚函数法产生一个最优 l a g r a n g e 乘子的充要条件关于经典增广l a g r a n g e 法的详细工作可参阅b e r t s e k a s 5 3 6 2 】 及b e r t s l 6 3 ，6 4 d i p i l l o & g r i p p o ( 1 9 7 9 ) 6 5 引入了一类求解具有不等式约束的优化问题的增广l 舢 g r a n g e 函数 f ，p ，c ) = a ( x ) + i z r h ( x ) + c l l h ( 茹) lj 2 + i i m ( x ) 霹1 1 2 ( c 0 ) 其中吃是经典l a g r a n g e 函数关于z 的梯度，并给出了矩阵m ( z ) 的几个选择，并在文 1 6 6 1 中，通过引入松弛变量及对矩阵m ( z 1 的特殊选择将其应用于求解具有不等式约束 的优化问题，c a x o t e n u t o & r 且i c o n i ( 1 9 8 7 ) 6 7 1 将该方法应用于求解极小化具有双线性约束 的二次函数，并在很弱的条件下得到了相似的结果 g l a d ( 1 9 7 9 ) 6 8 研究了对增广l a g r a n g e 函数 。 啦舶圳卅嘶) + 和孤卅去妄( 叫。，叫卅叫) 2 _ 五1 册( c 。) 中的l a g r a n g e 乘子的不同的更新方法的收敛性质 b o g g s & t o l l e ( 1 9 8 0 ) o 切引入了一类新的乘子法，发展了的对偶理论，构造了一类新 的惩罚函数并建立了精确罚函数和乘子法的联系这一类乘子法与d ip i l l o ( 1 9 7 9 ) 提出 的相关关于惩罚函数，精确罚函数和乘子法的早期进展可以参阅【，u ，上】 由于非线性l a g r a n g e 函数可用于构造求解非线性优化问题的对偶算法，而对偶算法 对原始变量的可行性没有限制，因此吸引了许多学者对这一课题进行研究随着人们对 修正l a g r a n g e 方法的深入研究，该方法的优越性逐渐显示出来了，尤其是函数的形式也 由复杂趋于简单 对于凸规划，p o l y a k & t e b o u l l e ( 1 9 9 7 ) t m l 讨论了一类具有如下形式的l a g r a n g e 函数 g ( 舭，p ) = ，o ( z ) 一# - 1 妒( 以( z ) ) ， ( 1 - 2 3 ) = l 其中p 0 是罚参数，妒是二次连续可微函数他们建立了非线性重新尺度化( n o n l i n e a r r e a c a l i n g ( n r ) ) 算法在适当的假设条件下，证明了由( n r ) 算法产生的对偶解序列全 5 求解非凸半定规划问题的一种非线性l a g r a n g e 方法 局收敛到最优乘子，而相应的原始解序列在e r g o d i c 意义下收敛到近似原始最优解此 外，a u s l e n d e r ，c o m i n e t t i & h a d d o u ( 1 9 9 7 ) ，叫以及b e n - t a l & z i b u l e v s k y ( 1 9 9 7 ) 问研究了一 类l a g r a n g e 函数并获得了有意义的收敛结果t a a g & z h a n g ( 1 9 9 5 ) ，剐证明了凸规划极大 熵方法的收敛性基于l o g - s i g m o i d 函数【。p o l y a k ( 2 0 0 2 ) j 发展了非线性重新尺度 化算法，并建立了收敛速度特别地，在标准二阶最优性条件下，( n r ) 算法具有q - 线性 收敛速度 进一步地，对于具有不等式约束的凸规划问题，p o l y a k & g r i v a ( 2 0 0 4 ) r 形】提出了原 始对偶非线性重新尺度化( p d n r ) 算法，证明了( p d n r ) 算法具有局收敛性并估计了 原始解序列对偶解序列的误差界。特别地，在标准二阶最优性条件下，误差界收敛到 0 g r i v a & p o l y a k ( 2 0 0 5 ) l ，纠发展了具有动态尺度化参数更新的原始对偶重新尺度化算法 基于函数类1 2 6 ，证明了该算法的全局收敛性并且在标准的二阶最优性条件及h e s s e 阵 v 2 五( z ) ，i = 0 ，m 满足l i p s c h i t z 条件下，具有1 5 q - 超线性收敛速率 对于非凸规划m m a g a s a r i a n ( 1 9 7 5 ) 8 0 】引入了一类非线性l a g r a n g e 函数来求解具有 不等式约束优化的优化问题，导致了无约束鞍点问题；c h a r a l a m b o u s ( 1 9 7 7 ) l 5 1 】给出了极 小p - 函数 b e r t s e k a s ( 1 9 8 2 ) a 狮提出了幂l a g r a a g e 函数 f ( x ，u ，七) = ，0 ( z ) 一七一1 1 - e 嘶( z 】； ( 1 2 4 ) i = 1 p o l y a k 【8 2 】给出了两个修正障碍函数，即修正的m 8 h 函数 f o c z ) 一k 叫凳1u i l n ( k f ( x ) + 1 ) ，击i n t f l k ， f ( x ，牡，k ) = l + o o o t h e r w i s e 和修正c a r r o l l 的函数 fy o ( x ) 一k 一1 銎1 地 1 一( 七， p ) + 1 ) 一1 】，z i n t f l k ， c ( 。，i ，k ) = l + 。 o t h e r w i s e 其中是k 0 是惩罚参数，= x l k f d x ) + 1 0 ，t = 1 ，m ； l i ( 1 9 9 5 ) 1 8 3 1 构造p - 幂l a g r a a g e 函数 l p ( x ，u ) = 【，o ( z ) 】，一 “历( z ) 】p - 6 ) ( 1 2 5 ) 6 大连理工大学硕士学位论文 和部分p - 幂l a g r a n g e 函数 ( 1 2 6 ) 其中p 0 是罚参数， ( o ) = ( z ) 一也及五( z ) 0 = 1 ，f n ) 假定采取正值且b t 0 ， = 1 ，m ；l i ( 1 9 9 5 ) 证明了，当p 足够大时，所构造的等价问题的扰动函数在b 附近是局 部凸的且当应用原始对偶方法能够保证对偶间隙为零后来，x u ( 1 9 9 7 ) 瞄4 1 对部分p 幂 l a g r a n g e 函数得到相似的结果，进一步地，p 幂l a g r a 且g e 函数可用于保证整数规划问题 成功的对偶研究，见l i & s t m ( 2 0 0 0 ) 8 5 ，8 6 1 与l i & w h i t e ( 2 0 0 0 ) 8 7 。l i & z h a n g 8 8 分析了 p 幂l a g r a n g e 算法的收敛性 针对具有不等式和等式约束优化的问题，g o l d f a r b 等( 1 9 9 9 ) s 9 3 提出了个修正的 障碍一增广l a g r a n g e 函数 f p ，弘七) = ，0 ) 一k - 1 地1 n ( 南 ) + 1 ) 一b ) + ；碍 ) ，z 伽t q = j ，= i，= l 其中q k = ： ( z ) 一k - l , i = 1 ，p ) p o l y a k ( 2 0 0 1 ) i 8 6 1 构造了l o g - s i g m o i d 函数 f ，u ，七) = ，0 ( 。) 一七一1 u t 【2 1 n 2 2 1 n ( 1 + e 一 ( z ) 】 岳= 1 贺素香等( 2 0 0 4 ) 9 1 ) 】给出了一个势函数 f ，t ，后，= 矗 ) + 悻i 銎1 t ：三一 ( z ”一击一1 ) 三 e 。，i n 伽t 。s 。, 其中t 0 是惩罚参数，s = l1 一，t p ) o ，i = 1 ，m 此外，在通常的二阶充分性条件下，j e a n - p i e r r ed u s s a u l t ( 2 0 0 4 ) 9 1 分析了形如的非 线性l a g r a n g e 函数类的渐近性并获得了超线性收敛性结果那些抽象的罚函数包含了由 p o l y a k 引入的所谓的修正障碍函数及c o m i n e t t i & d u s s a u l t 9 2 1 等学者提出的指数惩罚函 数 对于无约束极小极大问题 r a i nm a x 兀( z ) z 1 t m 7 、，醪 一 p p厉r l m： 一 p 南 = u k c h a r a l a x n a b o u s ( 1 9 7 9 ) 1 9 3 提出了p - 阶函数，该函数具有一些好的性质，基于该匾数的算 法具有很好的收敛性但是，p - 阶函数的表达式比较复杂，不利于计算；p o l y a k ( 1 9 8 8 ) 9 4 建立了一个形式简单的光滑函数 e p ( 础) = p 一1 u t e p ， = 1 其中是p 0 是罚参数并证明了基于该函数的算法有很好的收敛性；张立卫和唐焕文 ( 1 9 9 7 ) 【】提出了具有参数的极大熵算法，l i & f a n g ( 1 9 9 7 ) 9 1 i 】研究了求解极大极小优化 问题的熵函数方法 最近，p o l y a k 提出了n r 法来求解离散的极大极小问题，利用函数将原始的极大极 小问题转化为个等价问题，该变换用一个正的尺度化参数或由正的尺度化参数向量来 衡量对于等价问题，经典的l a g r a n g e 函数是n r 算法的主要工具所提出的非线性 l a g r a n g e 函数如下l 仇 三( z ，“，p ) = p 丸妒一1 p ) ) ， ( 1 2 7 ) i 穹1 其中a s k = a 【m l 銎】= 1 ) 它避免了病态，与此同时也改善了收敛速率特 别地，在标准的二阶标准收敛条件下，当尺度参数固定且足够小时，n r 具有q - 线性收 敛速率 值得注意的是，最近，张立卫，任咏红 驯j 构造并研究了一种基于f r i s c h e r - b u r m e i s t e r n c p 函数的新的非线性l a g r a n g e 函数：并证明了基于此函数的l a g r a n g e 方法无论从 理论分析还是从数值计算方面在求解某些非线性优化问题时都优于已有的l a g r a n g e 方 法尤其对应于在最优解处非起作用的约束的乘子是二阶收敛的，这是以往的非线性 l a 口a n g e 方法的研究中未出现的结果 1 3 研究背景和取得的主要结果 最近，非凸半定规划出现在许多应用领域中，如最优结构设计、最优鲁棒控制、鲁 棒反馈控制设计等等，因此研究非凸半定规划的算法有着重要的现实意义近些年来国 内外对于半定规划的研究主要集中在对线性半定规划的研究已取得的成果主要集中在 利用内点算法来求解线性半定规划方面而对于非线性半定规划的成果比较少众所周 知，大部分用于求解线性规划的算法都可推广到求解线性半定规划中和一般的凸规划中 去，鉴于非线性l a 铲a n g e 算法在求解非线性规划问题的成功，我们希望把这种方法推广 到解决n c s d p 中去，尽管有一定的挑战性，但有很大的理论意义 8 大连理工大学硕士学位论文 本文第二章归纳和总结了非凸半定规划的最优性条件，这些条件是本文下一章构造 对偶算法所必备的这章首先介绍了抽象约束优化问题的最优性条件，然后把用到了非 凸半定规划中去 本文第三章提出了求解非凸半定规划( n c s d p ) 的个非线性l a g r a n g 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 算法产生的序列局部收敛到原问题 的k k t 解 1 4 符号及说明 下面我们给出本论文中常用符号代表的含义 1 p ：n 维实数空间 r r n “n ：m n 阶实数矩阵的集合 s m ，印，s 备，s 竺分别表示m 阶对称矩阵集合，半正定矩阵集合，正定矩阵及负半定 矩阵集合 2 对于a ，b s m ，a10 ，a - 40 ，a 三0 ，a - 0 分另表示半负定矩阵，负定矩阵，半正 定矩阵，正定矩阵 a _ b 表示a b 卜0 3 对于矩阵m ，m 表示m 的笫巧个元素 4 v e c ( ) ：矩阵的拉直运算 对于b = ( b 1 ，b 2 ，b 。) r “。”，v e c ( b ) = ( b f ，目多，b 三) t r ”。1 5 对于数量值函数，：p 酞， v ( x ) 表示，关于z 的梯度 以( x ) = ( v ，( z ) ) t 表示，关于2 的导数 瑶，( z ) = 五( v ，( z ) ) = v 2 ，( z ) 表示，关于$ 的二阶导数 6 对于向量值函数g ：i p r 一，j 。g ( x ) 表示9 关于z 的j a c c o b i 矩阵 7 对于对称矩阵值函数c ：p s ”，d c ( x ) 表示从妒到s ”的线性映射，定义如 下 j l ， 【d c ( x ) l y = 佻g ( z ) 坳舯 i = l