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

大连理工大学博士学位论文 摘要 本文旨在研究求解非凸半定规划的一类非线性l a g r a n g e 方法的收敛速度其中的非 线性l a g r 锄g e 函数是基于l 6 w n e r 算子构造的并且关于约束是非线性的 在简要介绍了半定规划的相关背景知识和非线性l a g r a n g e 方法的发展历史之后，第 二章给出了预备知识和研究的主要内容预备知识包括非线性半定规划的最优性理论 和l 6 w n e r 算子的微分公式本文的主体工作在第三章到第五章取得的结果可概述如下： 1 第三章建立了非凸半定规划的非线。眭l a g r a n g e 方法的理论框架首先，给 出l s w n e r 算子要满足的三个条件并假设问题满足约束非退化条件、严格互补 条件和二阶充分性条件其次，讨论了所提出的非线性l a g r a n g e 函数的微分性质最 后，研究了子问题精确求解时算法的收敛速度收敛速度定理表明：当罚参数t 小 于某一阂值时，基于该类函数的算法生成的原始一对偶点列是局部收敛的，并且原 始一对偶解的误差界与罚参数t 成正比 与非线性规划的非线。| 生l a g r a n g e 方法的收敛速度分析相比，我们需要处理非凸半 定规划的二阶充分性条件中的s i g m a 项与s t i n g l t l 】的工作相比，本文所研究的问题 增加了等式约束本文重新建立的非凸半定规划的非线性l a g r a n g e 方法的收敛定理 更加完善，与p o l y a k t 2 】求解非线性规划的非线。l 生l a g r a n g e 方法的经典收敛定理完全 对应另外，我们给出的l s w n e r 算子满足的条件比s t i n g l 的条件要弱 2 基于第三章的假设条件，第四章建立了算法子问题非精确求解时的收敛速度定理 定理表明：在算法子问题非精确求解的情况下，当罚参数t 小于某个阈值时，基于该 类函数的算法生成的原始一对偶点列是局部收敛的，并且原始一对偶解的误差界与罚 参数t 成正比 3 第五章例举了五个非线性l a g r a n g e 函数，验证它们中的l f w n e r 算子满足第三章提出 的三个条件，因此证明了由这些非线性l a g r a n g e 函数构成的算法是局部收敛的，且 原始_ 对偶解的误差界与罚参数t 成正比 关键词：非凸半定规划；非线性l a g r a n g e 函数；l 6 w n e r 算子；收敛速度 大连理工大学博士学位论文 ac l a s so fn o n l i n e a rl a g r a n g em e t h o d sf 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 g a b s t r a c t t h i sd i s s e r t a t i o nf o c u s e so ns t u d y i n gt h ec o n v e r g e n c er a t eo fac l a s so fn o n l i n e a rl a g r a n g e m e t h o d sf o rs o l v i n gn o n c o n v e xs e m i d e f i n i t ep r o g r a m m i n g t h el a g r a n g i a n sa l eg e n e r a t e db y l r w n e ro p e r a t o r sa n dt h ec o n s t r a i n tf u n c t i o n si nt h el a g r a n g i a n sa r ei n v o l v e di nn o n l i n e a r w a y s a f t e rab r i e fi n t r o d u c t i o no ft h eb a c k g r o u n da b o u ts e m i d e f i n i t ep r o g r a m m i n ga n dt h ed e - v e l o p m e n to ft h en o n l i n e a rl a g r a n g em e t h o d s ，c h a p t e r2p r e s e n t st h ep r e l i m i n a r i e sa n dd e - s c r i b e st 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 t h ep r e l i m i n a r i e si n c l u d et h et h e o r yo f o p t i m a l i t yc o n d i t i o n sa n dt h ed i f f e r e n t i a lf o r m u l a so fl _ r w n e ro p e r a t o r s t h em a i nr e s u l t s ， m a i n l yi nc h a p t e r3 ，c h a p t e r4 a n dc h a p t e r5 ，a r es u m m a r i z e da sf o l l o w s ： 1 c h a p t e r3e s t a b l i s h e sat h e o r yf r a m e w o r ko ft h ec l a s so fn o n l i n e a rl a g r a n g em e t h o d s f o r s o l v i n gn o n c o n v e xs 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 ，w ep r o v i d eas e r i e so fc o n d i t i o n s t h a tt h ei 西w n e ro p e r a t o r ss h o u l ds a t i s f ya n da s s u m et h a to u rp r o b l e ms a t i s f i e sc o n s t r a i n t n o n d e g e n e r a c yc o n d i t i o n ，t h es t r i c tc o m p l e m e n t a r i t yc o n d i t i o na n d t h es e c o n do r d e rs u f - f i c i e n tc o n d i t i o n s e c o n d ，t h ed i f f e r e n t i a lp r o p e r t i e so ft h en o n l i n e a rl a g r a n g i a n s a led i s - c u s s e d f i n a l l yw ea n a l y z et h er a t eo fc o n v e r g e n c eo ft h en o n l i n e a rl a g r a n g ea l g o r i t h m s w i t hs u b p r o b l e m se x a c t l ys o l v e d t h ec o n v e r g e n c ea n a l y s i ss h o w st h a tt h ea l g o r i t h m s a l el o c a l l yc o n v e r g e n tw h e nt h ep e n a l t yp a r a m e t e ri sl e s st h a nat h r e s h o l da n dt h ee r r o r b o u n do ft h ep r i m a l d u a ls o l u t i o n si sp r o p o r t i o n a lt ot h ep e n a l t yp a r a m e t e r c o m p a r e dt ot h ec o n v e r g e n c ea n a l y s i so ft h en o n l i n e a rl a g r a n g i a nm e t h o df o rn o n - l i n e a rp r o g r a m m i n g ，w eh a v et oo v e r c o m et h ed i f f i c u l t yc a u s e db yt h es i g m at e r mi nt h e s e c o n do r d e rs u f f i c i e n tc o n d i t i o no fn o n c o n v e xs e m i d e f i n i t ep r o g r a m m i n g s o m ec o m - m e n t so u g h tt ob em a d ea b o u tt h ed i f f e r e n c eb e t w e e nt h i sd i s s e r t a t i o na n ds t i n g l s i f i r s t 。as e to fe q u a l i t yc o n s t r a i n t sa r ei n c l u d e di nt h ec o n s t r a i n to ft h ep r o b l e mc o n s i d e r e d s e c o n d ，t h ec o n v e r g e n c et h e o r e mg i v e ni nt h i sd i s s e r t a t i o ni se l e g a n tc o m p a r e dt o t h a to fs t i n g l ，w h i c hc o m p l e t e l yc o r r e s p o n d st ot h ec o n v e r g e n c et h e o r e m ( e g t h e o r e m 求解非凸半定规划的一类非线性l a g r a n g e 方法 4 1i np o l y a k t 2 】) i nt h en o n l i n e a rp r o g r a m m i n gc a s e a d d i t i o n a l l y , t h ec o n d i t i o n sf o rt h e l 6 w n e ro p e r a t o r si nt h i sd i s s e r t a t i o na r ew e a k e rt h a nt h eo n e si ns t i n g l sw o r k 2 b a s e do nt h ea s s u m p t i o n si nc h a p t e r3 ，c h a p t e r4 p r e s e n t st h ec o n v e r g e n c ea n a l y s i so f t h en o n l i n e a rl a g r a n g ea l g o r i t h mw i t hs u b p r o b l e m si n e x a c t l ys o l v e d t h i sc o n v e r g e n c e t h e o r e ma l s os h o w st h ea l g o r i t h m sa r el o c a l l yc o n v e r g e n tw h e nt h ep e n a l t yp a r a m e t e ri s l e s st h a nat h r e s h o l da n dt h ee r r o rb o u n do fp r i m a l d u a ls o l u t i o n si sp r o p o r t i o n a lt ot h e p e n a l t yp a r a m e t e r 3 c h a p t e r5e n u m e r a t e sf i v es p e c i f i cn o n l i n e a rl a g r a n g i a n s w ep r o v et h a tt h el 6 w n e ro p - e r a t o r si nt h e s el a g r a n g i a n ss a t i s f yt h ec o n d i t i o n sm e n t i o n e di nc h a p t e r3 ，w h i c hm e a n s t h a tt h ea l g o r i t h m sc o n s t r u c t e db yt h e s el a g r a n g i a n sa r el o c a l l yc o n v e r g e n ta n dt h ee r r o r b o u n do ft h ep r i m a l - d u a ls o l u t i o n si sp r o p o r t i o n a lt ot h ep e n a l t yp a r a m e t e r k e y w o r d s ：n o n c o n v e xs e m i d e f i n i t ep r o g r a m m i n g ；n o n l i n e a rl a g r a n g i a n ；l 6 w n e r ； o p e r a t o r ；r a t eo fc o n v e r g e n c e 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方 外，本论文不包含其他个人或集体己经发表的研究成果，也不包含其他已 申请学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的 贡献均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：蒸鞫雄茎必堕堕二塑韭递睦幽墅型2 彰三： 作者签名：二童_ 至生一 日期：型雩年l 月二理日 大连理工大学博士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间论文工 作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有权保留论文并向国 家有关部门或机构送交论文的复印件和电子版，可以将本学位论文的全部或部分内容 编入有关数据库进行检索，可以采用影印、缩印、或扫描等复制手段保存和汇编本学 位论文。 学位敝船茎强塑鲨坠塑些竺二塾垦堕丝鲤塑鱼垄 互 作者签名：盗壁旦 一一p 导师签名： 8 3 日期：珥年月生日 日期：珥年_ 鱼月鱼日 大连理工大学博士学位论文 1绪论 本章给出了半定规划的背景知识介绍了非线性l a g r a n g e 方法的发展历史和用非线 性l a g r a n g e 方法解决半定规划的研究情况 1 1 半定规划 半定规划( s e m i d e f i n i t ep r o g r a m m i n g ) ，简称s d e 是对称锥规划的一种特殊形式 早在1 9 6 3 年，b e l l a n 和f a n 首次提出了半定规划的框架他们从一个松弛的线性规划 模型出发。并用矩阵变量替换了向量变量【3 1 半定规划并没有像线性规划那样迅速吸引人 们的注意力，直到大量b m i 形式的控制问题被归结为半定规划问题随之而来的，关于半 定规划的有效算法在理论上得到实现从此以后，人们才开始大量关注这个问题关于半 定规划的介绍可以参看v a n d e r b e r g h e ，w o l k o w i c z 和s a i g a l ( 2 0 0 0 ) t 4 】合作的关于半定规划的 手册，t o d d ( 2 0 0 1 ) 3 】的工作及w o l k o w i c z ( 2 0 0 1 ) t 5 】整理的在线的文献下面我们就详细介 绍有关半定规划的知识 1 1 1 半定规划的形式 起初，人们研究的是线性半定规划主要形式如下： m i n ( a 0 ，x ) ， s t ( a ，x ) = 玩，i = 1 ，m ， x s 竺 其中，a o 酽，这里s p 勘p 的对称矩阵组成的空间，跹是负半定矩阵组成的空间， ( a ，b ) = t r ( a r b ) 随后，人们发现在实际领域中有很多问题可以归结为其它形式的半定规划例如非 线性半定规划( n l s d p ) ，其主要形式如下： u n s t ( x ) g ( x ) 跹， z r n 其中函数f ：r 竹_ r 而映射g ：p _ 妒 再后来，由于实际问题的需要，人们在上面两种半定规划形式的基础上稍作改动得 求解非凸半定规划的一类非线性l a g r a n g e 方法 到了许多新的半定规划问题例如在约束上增加等式约束或不等式约束等本文所研究 的是带有等式约束和负半定锥约束的非线性半定规划问题 1 1 2 半定规划的相关理论 s h a p i r o ( 1 9 9 7 ) 6 - 9 1 在非线性半定规划的理论研究方面做出了重要的贡献在【8 1 ( 或中 文译本【1 0 1 ) 中第5 3 节详细介绍了负半定锥的几何性质，矩阵凸性，非线性半定规划的对偶 性质，一阶最优性条件，二阶最优性条件以及稳定性与灵敏度分析 另外，f o r s g r e n ( 2 0 0 0 ) 1 1 】也研究了非凸半定规划的最优性条件他研究了一个特殊形 式的非凸半定规划即。 r a i n f ( x ) s t c ( x ) 三0 其中，( z ) 关于z 是线性的c ( z ) 是对称矩阵且关于z 是非线性的作者用局部半 定l a g r a n g e 函数这一概念来得到一阶和二阶最优性条件 矩阵值函数在半定规划算法中有非常重要的应用s u n ，s u n ( 2 0 0 2 ) 1 2 】研究了矩阵值 函数的广义微分性质他们主要研究了b 导数和矩阵值函数的半光滑性证明了矩阵绝 对值函数和在半正定矩阵锥上的投影函数是强半光滑的 s u n ( 2 0 0 6 ) 1 3 1 证明了对于一个非线性半定规划问题的局部最优解，下列几个条件等 价： 强二阶充分性条件和约束非退化条件； k k t 系统的c l a r k e 广义j a c o b i a n 矩阵的非奇异性； k k t 点的强正则性 1 1 3 求解半定规划的算法 起初人们对半定规划的研究主要是针对线性半定规划问题学者们入手的角度不尽 相同首先，线性半定规划是凸优化问题，因此可以通过与凸分析相关的理论来解决这 表明半定规划问题给凸分析理论提供了一个非常“广阔”的应用空间其次，线性半定规 划也可以视为线性规划的一种扩展比如，它可以看做是一个非多面体凸锥上的线性优 化问题于是人们就尝试着把有效的解决线性规划的方法用来求解线性半定规划问题 因为内点法在解决线性规划问题时非常有效，所以很多学者开始研究是否能用内点法求 2 大连理工大学博士学位论文 解线性半定规划问题a l i z a d e h ( 1 9 9 5 ) 1 1 4 】指出大部分已知的线性规划的内点法可以完全 推广到线性半定规划上相关解决线性规划的内点法参看y e ( 1 9 9 7 ) 1 1 5 】 z h a o ，s u n ，t o h ( 2 0 0 9 ) 1 6 】研究了求解线性半定规划的n e w t o n c g 增广l a g r a n g e 方法 这一方法取得了非常好的数值结果 目前，人们对求解非线性半定规划算法的研究还不是很多，因此在这方面还有许多 课题有待研究。这也是本文选题的一个主要原因 1 1 4 半定规划的应用 近些年来半定规划成为备受关注的问题之一，其主要原因是它在实际问题中有着非 常广泛的应用1 4 ，1 刀 最早出现约束是半正定矩阵的问题多是一些控制问题例如，l y a p u n o v ( 1 9 8 0 ) 在 描述一个线性微分方程解的稳定性的时候，遇到了一个约束恰好是线性矩阵不等式 的问题因此最早的l m i ( 1 i n e a rm a t r i xi n e q u a l i t y ) 就是 l y a p u n o vl m r 它在控制理论中 的重要性在二十世纪六七十年代已经被公认随着求解线性半定规划的内点法的发 展，人们开始大量地把线性半定规划用于求解控制问题例如，b o y d ，e lg h a o u i ，f e r o n 和b a l a k r i s h n a n ( 1 9 9 4 ) t 1 踟 此外半定规划经常用来解决组合优化问题例如，g o e m a n s 和w i l l i a m s o n ( 1 9 9 5 ) 1 1 9 1 发 现半定松弛可以为组合优化中的最大切割问题提供一个尽可能好的近似f e i g e ( 2 0 0 1 ) 【2 0 】，a n j o s ( 2 0 0 5 ) f 2 1 1 研究了最大割问题的半定松弛算法： 更多具体的应用见1 1 7 ，2 m 9 1 在v a n d e r b e r g h e ，w o l k o w i c z 和s a i g a l ( 2 0 0 0 ) 1 4 合作的半定 规划手册中p a r t 专门介绍了半定规划如何应用在组合优化，非凸二次规划，系统控制理 论，结构设计，矩问题，随机实验设计和特征值问题中 1 2 非线性l a g r a n g e 方法发展历史及现状 本节回顾了非线性规划的非线性l a g r a g e i 函数方法的历史，介绍了半定规划问题的非 线性l a g r a n g e 方法的研究情况 1 2 1 非线性l a g r a n g e 方法发展历史 求解非线性规划问题( n l p ) 的方法很多，例如【3 1 枷】等等非线性l a g r a n g e 方法也是求 解非线性规划问题的有效方法之一 3 求解非凸半定规划的一类非线性l a g r a n g e 方法 下面介绍非线性规划问题的形式： n u n s t 其中z r n ，( z ) ：辩hr ，i = 1 ，f 和9 j ( x ) ：r n r ，j = l ，仇是实值函数 非线性规划问题的l a g r a n g e i 函数定义为 其中( a ，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 函数可以建立鞍点理论，也可以建立求 解r a i n l ( x ，”，矿) 的对偶算法而对于非凸线性规划，假设( z ，”，矿) 是问题的k k t 点， 即使当( a 七，矿) 在( 入+ ，矿) 的附近，z 在z + 的小邻域内，l ( x ，a 七，p 七) 通常也是非凸的为了克 ) 艮l a g r a n g e 函数的这一缺点，学者们提出了其它形式的l a g r a n g e 函数 h e s t e n e s ( 1 9 6 9 ) 【4 1 】和p o w e l l ( 1 9 6 9 ) m 】分别提出了增广l a g r a n g e 函l 数 f ( z ，a ) = ，( z ) + a 丁 ( z ) + 差| | 九( z ) 1 1 2 ( ? o ) 和 l p ( x ，a ，秒) = ，( z ) + ( z ) + o j 2 j = l 来求解具有等式约束的非线性优化问题p o w e l l 在1 9 6 9 年的文章【4 2 】对具有等式约束的 优化问题，利用矩阵分析的技巧证明了经典的增广l a g r a n g e i 函数法的收敛性定理随后， p o l y a k 和t r e t y a k o v ( 1 9 7 3 ) | 4 3 1 证明了在适当条件下，存在罚参数的一个阈值，当惩罚参数 小于或者大于这个阈值的时候，该方法产生的解系列以几何收敛率收敛到原始最优解。 并且给出了与罚参有关的解的误差界的上界r o c k a f e l l a r ( 1 9 7 0 ，1 9 7 1 ) m 4 5 1 把h e s t e n e s ， p o w e l l 和h a a r h o f f , b u y s 的思想进一步推广到具有不等式约束的优化问题上，得到了一般 约束优化问题的经典增广l a g r a n g e i 垂l 数，并且为凸规划建立了增j l a g r a n g e 方法理论有 4 l m i i = 2 = 0 是惩罚参数，妒是二次连续可微函数他们建立了非线性重新尺度化( n o n l i n e a r r e s c a l i n g ) 算法p o l y a k ( 1 9 9 2 ) 删给出了两个修正的障碍函数，即修正的f r i s h 函数 聊删： “习叫- 1 善灿 烈甸“) ，蚝m i + o o ， 。譬i n t f 2 t ， 和修正的c a r r o l l 函数 舶归一和邱饰) + 1 ) - 1 ) z i n t s 2 t z 聋i n tq t ， 其中后 0 是惩罚参数，f h = 【z i l + 吼( z ) 0 ，i = 1 ，m ) 他在2 0 0 1 年又【2 】构造 - l o g s i g m o i d i 函数 m f ( z ，肛，亡) = ，( z ) 一t 一1 # i ( 2 1 n 2 2 1 n ( 1 + e 一七 z ) ) i - - - - 1 来求解具有不等式约束的优化问题我所提出的非线性l a g r a n g e 函数的形式对 应p o l y a k 提出的( 1 2 ) 的形式 关于求解非线性规划问题的l a g r a n g e 方法的研究很多，可以参看b e r t s e k a s ( 1 9 7 5 ，1 9 7 6 ) t 6 1 , 6 2 ，张立卫和唐焕文( 1 9 9 5 ，1 9 9 7 ) 豳，删，李端和孙小玲等( 2 0 0 0 , 2 0 0 6 ，2 0 0 7 ， 2 0 0 8 ) 【6 5 棚1 ，还有其它重要的工作，在此不一一列举，参看【2 ，5 2 ，7 0 - 8 1 1 1 2 2 非线性l a g r a n g e 方法的研究现状 随着半定规划的日益兴起，大家开始尝试各种方法来求解它于是有人开始 考虑用非线性l a g r a n g e 方法求解半定规划b e n - t a l s t l z i b u l e v s k i 于1 9 9 7 年在s i a mj 二5 求解非凸半定规划的一类非线性l a g r a n g e 方法 o p t i m i z a t i o n 上发表了一篇关于求解凸规划的障碍乘子罚函数方法的文章【7 引在此基础 上，z i b u l e v s k i 在他的博士论文1 8 2 】中首先使用了非线性l a g r a n g e 方法来解决线性半定规 划问题他提出一个惩罚障碍函数的推广形式并且给出了相应的求解半定规划的非线 性l a g r a n g e 算法【8 2 】解决了如下形式的半定规划： 瓣 ，( z ) ：a ( z ) 三o ) ， n 其中，：r n r 是凸函数，a ( x ) = + x i a i ，这里a ，i = 1 ，n 是对称矩阵这种 i = 1 仇 方法的主要思想是用妒( 九 ) ) 来惩罚矩阵a ( z ) 的负特征值九 ) 的部分这里妒是一 = 1 个标量罚函数这个罚函数还可以被写成t r 妒( a ( z ) ) z i b u l e v s k i 提出妒可以取以下四种函 数： 1 对数障碍函数( 1 0 9 a r i t h m i cb a r r i e rf u n c t i o n ) 8 3 1 妒( 芒) = 一l o g ( t ) ， 2 修正障碍函数( m o d i f i e db a r r i e rf u n c t i o n ) 1 6 0 妒( 亡) = 一l o g ( t + 1 ) ，- 1 t ， 3 指数罚函数( e x p o n e n t i a lp e n a l t yf u n c t i o n ) t 8 4 1 v ( t ) = e 一1 ， 4 混合二次- 对数罚 函数( m i x e dq u a d r a t i c l o g a r i t h m i c ) 8 5 ，8 6 当一1 7 - 1 时， 阱c 亡，= 3 t 2 + b t + c + ，：至 纵归 警妒魄。皆h 砖2 是 6 大连理工大学博士学位论文 z i b u l e v s k i 所提出的非线性l a g r a n g e i 垂i 数形式为 f ( x ，v , p ) = f ( x ) + t r q o p ( v a ( x ) v ) ， 其中u = v 2 ，u 为l a g r a n g e 乘子 s u n ，z h a n g 和w u ( 2 0 0 6 ) s t 在严格互补条件成立时研究了求解非线性半定规划的增 广l a g r a n g e 方法而s u n ，s u n 和z h a n g ( 2 0 0 7 ) t 8 8 】在严格互补条件不成立的情况下，解决非凸 半定规划问题的增广l a g r a n g e i 函数算法收敛速度问题 s t i n g l 在博士论文【1 】中指出，z i b u l e v s k y 和m o s h e y e v s 9 - 9 0 1 的工作中收敛定理证明仅限 于凸规划，并且在计算上依赖于约束矩阵的特征值分解，这大大增加了计算的复杂度针 对这两点，s t i n g l 在【l 】中进行了修正因为用经典的非线性l a g r a n g e 函数方法解决非凸非 线性规划问题已经存在一套完备的理论框架在【1 】中，这一方法被进行了推广，用来解决 约束是非线性的半定规划问题k 0 6 v a r a 和s t i n g l 先后于2 0 0 3 和2 0 0 7 年给出了两种有效 软件p e n n o n 和p e m b m i 来处理不同类型的半定规划问题【9 l 9 2 ，都取得了良好的计算结 果 随后，针对与s t i n g l 9 h 所选择的修正障碍函数，n 0 1 1 1 9 3 1 在研究求解非凸半定规划的非 线性l a g r a n g e 方法的文章中提出 w e d g e 收敛的定义，给出了不同的收敛定理证明 7 大连理工大学博士学位论文 2预备知识及本文主要工作 本章所给出的非线性半定规划的理论知识和l i s w n e r 算子的微分公式是后续工作的 基础 2 1 预备知识 本章的预备知识均可参考b o n n a n s ，s h a p i r o ( 2 0 0 0 ) 9 4 1 和中文译本【埘 考虑下述形式的最优化问题 m l n z q s t f ( x ) ( 2 1 ) c ( x ) 10 ， 其中q 是欧氏空间r n 的一非空凸闭子集，：舭_ r ，g ：r n s p 是从r n 到p p 对称 矩阵空间酽的映射记号a 冬o ( a 三o ) 意味着对称阵a 是负半定的( 正半定的) 并且假 设，0 ) 与g ( z ) 是连续的 2 1 1 最大特征值函数的方向导数 因为双和跹的性质相类似，所以讨论有关跹的性质锥跹是闭凸的，且可以表示成 如下的形式： s p - = _ y s p ：入z ( y ) o ， 其中a 枷。( y ) 记矩阵y 的最大特征值，于是可以用函数入m 凹：s p _ r 的微分结构计算s p 的二阶切集先给出最大特征值函数的方向导数 最大特征值函数的一阶方向导数 考虑矩阵a 妒矩阵的最大特征值可表示为 a m a x ( a ) 2 m a ：x 1 x t a x e = 【e l ，e 8 】是1 s 矩阵，它的y d e l ，e s 构成了对应于4 的最大特征值的特 征向量空间的一组直交基，即a e = q e ，矿e = 厶，s 是a 的最大特征值的重数则 a 二“( a ，h ) = a m a x ( e r h e ) 9 一 ( 2 2 ) 求解非凸半定规划的一类非线性l a g r a n g e 方法 最大特征值函数的二阶方向导数 令k 是8xs 矩阵e r h e 的最大特征值的重数，f 是一sxk 矩阵，它的列 ， 构 成了对应最大特征值的e r h e 的特征向量空间的一组直交基则 入煞( a ；日，w ) = 入m 缸( ，e 丁 一2 h ( a a m 戕( a ) ) 日】e f ) ( 2 3 ) 2 1 2s o p 约束集合的切锥与二阶切集 要研究半定规划的最优性条件，一定要会刻画s d p 约束集合的切锥和二阶切集 切锥 设a 是一负半定矩阵满足入一( a ) = 0 ，即a 是集合跹的边界上的点，因此，矩阵e 的 列生成a 的零空间由公式( 2 2 ) ，跹在点a 处的切锥可以写成下述形式 啦( 4 ) = 日酽：e r h e5o ) ( 2 4 ) 锥k 的最大线性子空间被称为其线性空间，记为l i n ( k ) 切锥的线性空间表示为： l i n ( t s = ( a ) ) = o 满足wnb ( a ，e ) 是闭的还有，集 合w r 构成了线性空间s p 的一光滑流形 一1 0 大连理工大学博士学位论文 命题2 1 ：集合w r 是一光滑流形，m 在点a 眦处的切空间可以写成如下的形式 孤c 俨卜酽： 一o ，1 z j ， 其中e l ，一r 是矩阵a 的零空间的一组基 下面的横截性的概念借自微分几何 定义2 2 ：称一光滑( 连续可微) 映射g ：渺一妒与光滑流形m 横截地相交于点z 舻， 记为g 面z m ，若或者g ( z ) 隹w r 或者 ( g ) ) + d g p ) 渺= 酽 若对所有的z 舻，均有g 而z m ，则称g 与w r 横截地相交，记为g 而m 命题2 3 ：令g ( z ) w ，f i p r a n k g ( x ) = r ，用e 1 ，e p r 记矩阵g ( z ) 的零空间的一组基 则g 讳w 的充分必要条件是下述的礼- 维向量是线性无关的： ，e i = l le o g ( x ) o x l o g ( x ) o x n三) ，1 t j p r 我们称半定规划问题( p ) 的可行点z 是非退化的，如果g 币z 眦，其中r ：= r a n k g ( x ) 也就是说，半定规划问题可行点的非退化性等价于它满足横截性条件 2 1 4 矩阵凸性 在空间妒中关于锥跹的偏序被成为l 6 w n e r 偏序，即对a ，b s p ，a 芝b 当且仅 当a b 是正半定矩阵称映射g ( z ) ( 在凸集q 上) 是矩阵凸的，若它i 关于- l 6 w n e r 偏序是凸 的这意味着，对任何t 【0 ，1 】及任意z 1 ，x 2 舯( 任意的z 1 ，x 2 q ) ，不等式 t g ( x 1 ) + ( 1 1 ) g ( z 2 ) 三g ( t x l + ( 1 一亡) z 2 ) 成立s d p 问题( p ) 称为是凸的若厂( z ) 是凸的，集合q 是凸的，映射g ( z ) 是矩阵凸的 求解非凸半定规划的一类非线性l a g r a n g e 方法 命题2 4 ：对于映射g ：r 竹_ s p ，下述结论成立： ( i ) g ) 是矩阵凸的当且仅当对任何z r p ，实值函数矽( z ) ：= z t g ( z ) z 是凸的 ( i i ) 如果g ( z ) 的每一_ 元素( z ) ，i ，j = 1 ，p 是二次连续可微函数，则g ( z ) 是矩阵凸的 充分必要条件是对任何( 魂，匆) 酞饨及z r n ，佗钆矩阵p 磊乃v 2 9 i j ( z ) 是正 t ，j = l 半定矩阵 ( i i i ) 若g ) 是二次连续可微的，且仰印块矩阵日( z ) ：= 【v 2 ( z ) 】呈歹：1 对任何z 均 是正半定的，则g ( z ) 是矩阵凸的 ( i v ) 若g ( z ) 是矩阵凸的，则它的最大特征值函数( z ) ：= k 凹( g ( z ) ) 是凸的 2 1 5 对偶理论 问题( 2 1 ) 的l a g r a n g e 函数可以写为下述形式 l ( x ，q ) ：= ( x ) + ( q ，g ( z ) ) ，( z ，q ) 酞? s p 因此，( 2 1 ) 的( l a g r a n g e ) 对偶问题为 ( d )m a x i n fl ( x ，q ) ) 。屹u c w 。 回顾，( 牙，豆) 被称为l a g r a n g e n l 数l ( x ，q ) 在集合q 辞上的鞍点，若 ( 2 5 ) 牙a r g n 1 i n q l ( x ，q ) ， q a r g m a x q s 王三( 孟，q ) ( 2 6 ) ( 2 6 ) 的第二条件意味着g ( 牙) 跹，豆辞，互补条件( 孬，g ( 牙) ) = o 成立于是得到条 件( 2 6 ) 等价于 牙a r g m i n x q l ( x ，孬) ， ( 豆，g ( 孟) ) = 0 ，g ( 孟) 50 ， 豆三0 ( 2 7 ) 由( l a g r a n g e ) 对偶的一般理论有下述结论 命题2 5 ：( 【9 4 ，p r o p o s i t i o n5 7 7 】) 令( p ) 与( d ) 分别是原始问a ( 2 1 ) 与对偶问题( 2 5 ) 1 2 大连理工大学博士学位论文 贝j j v a l ( d ) g v a l ( p ) 进一步，v a l ( p ) = v a l ( d ) 且牙与豆分别是( p ) 与( d ) 的最优解的充分必要条 件是( 牙，豆) 为l ( z ，q ) 在q 辞上的鞍点，即当且仅当条件( 2 7 ) 成立 从共轭对偶性的观点来讨论原始与对偶问题与原始问题( 2 1 ) 相联系的( 标准) 参数 化问题是 罂碧，( z ) s t g ( z ) + y 冬o ， 它依赖于参数矩阵y 妒将这一问题记为( p y ) ，用u ( y ) 记它的最优值，臣p v ( y ) ：= v a l ( p y ) 问题( p o ) 与原始问题( p ) 重合j i v a l ( p ) = u ( o ) 函数口( ) 的共轭由下式给出 卅，= 警p l 筹n 因此，对偶问题( 2 5 ) n 以表示为在约束q 三0 2 下极大化一v + ( q ) 这一问题，进一步， v a l ( p ) = u ( o ) 且v a l ( d ) = 口( o ) 由共轭对偶性的一般性理论，下述结果成立 命题2 6 ：( 9 4 ，p r o p o s i t i o n5 8 0 1 ) 下述性质成立 ( i ) 若v a l ( d ) 是有限的，则5 ( d ) = o v ( o ) ( 豇) 若u ( y ) 在y = o 处是次可微的，则原始问题与对偶问题间没有对偶间隙，g , s ( d ) = 踟( o ) ( i i i ) 若v a l ( p ) = v a l ( d ) 是有限的，则( 可能空的) 集合s ( d ) 对偶问题的最优解集，与锄( 0 ) 重 厶 口 现在考虑约束规范 0 i n t g ( q ) 一跹) ， 这意味着对0 s p 的邻域中的所有的y ，v ( y ) 十o o 成立由共轭对偶性理论，还有下述 结果 定理2 1 ：( 9 4 ，t h e o r e m5 8 1 ) 设原始问题( p ) 是凸的若问题( p ) 的s l a t e r 条件成立，则原始 与对偶问题间没有对偶间隙，进一步，若它们的公共的最优值是有限的，则对偶问题的最