（应用数学专业论文）半定规划的非内点算法.pdf

摘要 半定规划是数学规划方面一个相对较新的领域，是线性规划的推广，它是在 满足约束“对称矩阵的仿射组合半正定”的条件下使线性函数极大( 极小) 化问 题，这个约束是非线性的、非光滑的、凸的，因而半定规划是一个非光滑凸优化 问题。 本文首先介绍了半定规划的基本理论、主要算法和研究现状，在此基础上对 半定规划问题算法研究做了如下工作： 1 给出了解决半定规划问题的筛选算法。文中首先采用低秩分解技术将半定 规划问题转化为与其等价的非线性规划问题，进而利用非线性规划问题的筛选算法 来求解。文中给出了两种筛选算法，一种是基于方向分解的筛选法分析了它的主 要思想，并给出了具体的算法，最后给出了它的收敛性结论。另一种是与s q p 结合的 筛选法，对其进行了详细的分析，并得到了较好的全局收敛性结论 2 文中又给出了一种光滑化牛顿方法。首先利用推广的f i s c h c r - b u r m e i s t o r 函 数将半定规划问题的k k t 条件转化为一个等价的非光滑方程组，进而利用光滑化 方法将该非光滑方程组光滑化，构造了半定规划问题的光滑化方法。最后，在超线 性收敛的基础上，又对算法作了改进，得到了二次收敛性结论。 关键词：半定规划凸优化筛选法光滑化方法 a b s t r a c t s e m i d e f m i t ep r o g r a m m i n gi s 锄e 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 g , o n em a x i m i z e s ( m i n i m i z e s ) a l i n e a rf u n c t i o ns u b j e c tt ot h ec o n s t r a i n tt h a t a na f f m ec o m b i n a t i o no fs y m m e t r i cm a l 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 hac o n s t r a i n t i sn o f l m e 甜a n dn o n s m o o t h , b u tc o n v e x ，s t ) s e m i d e f m i t ep r o g r a m m i n gi san o n s m o o t h a n dc o n v e xo p t i m i z a t i o np r o b l e m i nt h ep a p e r , t h et h e o r y , a l g o r i t h m ，a n dr e c e n tr e s c a c ho fs e m i d e f m i t ep r o g r a m m i n g a r cs u m m a r i z e d ，s o m ew o r k si na l g o r i h ma r ei n t r o d u c e d i nd e t a i l w ec o n c l u d et h e m a sf o l l o w s ： 1 af i l t e rm e t h o df o rs e m i d e f m i t ep r o g r a m m m gi sp f o p o di nt h i sp a p e r f i r s t l y , a l o w - r a n kd e c o m p o s i t i o nt e c h n i q u ei sa d o p t e dt ot r a n s f o r mt h es t a n d a r ds e m i d e f i n i t e p 玉o 黟越衄i n gi n t oa ne q u i v a l e n tn o 姑i n e 骶p r o g r a m m i n gp r o b l e m t h e nt w ok i n d so f f i l t e ra l g o r i t h m sa r ei n t r o d u c e dt os o l v et h ep r o b l e m 1 1 1 cf i r s ta l g o r i t h mi sb a s e do n a d e c o m p o s i t i o n o fd i r e c t i o n w eg i v et h em a i ni d e ao fi ta n dt h ec o n v e r g e n c e c o n c l u s i o n s t h es e c o n di sac o m b i n a t i o no ff i l t e ra n dt h es q p ad e t a i l e da n a l y s i si s c a r r i e do u ta n db e t t e rg l o b a lc o n v e r g e n c ec o n c l u s i o n sa f co b t a i n e d 2 a ne x t e n s i v ef i s e h e r - b u r m e i s t e rf u n c t i o nm e t h o da r cu s e dt oc o n v e r tt h e o p t i m a l i t yc o n d i t i o u so f s d p i n t oa ne q u i v a l e n tn o n s m o o t hs y s t e mo f e q u a t i o n s t h e nb y s m o o t h i n gt h en o n s m o o t he q u a t i o n s , as m o o t h i n g - t y p em e t h o df o rs e m i d e f m i t e p r o g r a m m i n gi sc o n s t r u c t e c la tl a s t , o nt h eb a s i so ft h es u p e f l i n e a rc o n v e r g e n c e 缸 i m p r o v e da l g o r i t h mi sp r e s e n t e da n dar a p i dq u a d r a t i cc o n v e r g e n c ec o n c l u s i o ni s o b t a i n e d k e y w o r d s ：s e m i d e f i n i t e p r o g r a m m i n g f i l t e rm e t h o d c o n v e x o p t i m i z a t i o n s m o o t h i n g m e t h o d 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特i i i i 以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：绛! j 途 日期 生：z ：矍 ， 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后。发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本人签名：聋墨1 硷 导师签名： 日期垒星出 ， 日期出立：! ：! 第一章绪论 第一章绪论 本章主要介绍了半定规划及其对偶模型、对偶理论，主要算法及其应用；概 述了半定规划的研究现状和意义；最后列出了本文的内容安排 1 1 引言 半定规划( s d p ) 是数学规划方面的一个相对较新的领域。虽然它的起源可以追 溯到几十年以前，但半定规划方面的主要论文都写于2 0 世纪9 0 年代。自1 9 8 1 年 以来，有关半定规划的论文都以“以矩阵为变量的线性规划( l i n e a rp r o g r a m m i n g w i t hm a t r i xv a r i a b l e s ) ”这样的名字来命名，实际上这种命名也是早期引入半定 规划问题的最好方式。 半定规划是线性规划的推广，它是在满足约束“对称矩阵的仿射组合半正定 ”的条件下使线性函数极大( 极小) 化问题，这个约束是非线性的l 咣滑的、凸 的，因而半定规划是一个非光滑凸优化问题。对于半定规划的研究开始于上世纪 的6 0 7 0 年代，它是定义在实数域上的半正定矩阵锥上的规划，当半定规划的目标 函数及其约束都为线性时，称之为半正定线性规划，其他称之为半正定非线性规 划。过去的十几年是半定规划发展的高潮期，研究者在实践当中发现了大量的半 正定规划的例子【i l 这引发了人们的研究热情，许多的线性规划的性质和算法被平移 到了半正定线性规划。最大的成就就是内点算法的成功应用，其中主要的困难是 由于矩阵乘积的不可交换性而导致的迭代过程的牛顿方程不能保证产生对称解， 先后有三种方案，即利用h k m 方向【2 】腑向【3 】和a h o 方向吲，来克服这一困难。 1 9 9 8 年z l m n g t s l 引入对称化算子统一了上述三类搜索方向。同年, n e s t e r o v - t o d d 首先 提出了针对s e l f - s c a l e dc o n e 的内点算法，并且说明了用n e s t e r o v - t o d d 作为搜索方向 的算法多项式时间复杂性。鉴于l i e a l g e b r a 领域，对称锥和e u c l i d e a nj o r d a na l g e b r a 的密切关系，1 9 9 5 年，f a y b u s o v i s h 首先从e u c l i d e a nj o r d a na l g e b r a 角度考察内点算法 1 6 1 ，随后，s t u r m , a l i z a d e h 进一步完善它1 7 l 。2 0 0 2 年, m u r a m a t s u 从e u c l i d e a nj o r d a n a l g e b r a 的角度考察内点算法，而且进一步探讨y z h a n g 所统一的三类搜索方向，及 s e m i l o n g - s t e p sa n dl o n g s t e p s l 勾点算法的多项式时间复杂性田。 近年来，由于半定规划的理论和算法取得了很大的进展，以及它在控制论唧、系 统论、结构优化、组合优化【l o l 、滤波器的设计【川和移动通信等领域【1 2 , 1 3 长j 广泛应 用，使得其成为数学规划领域日益引人关注的研究方向。 2 半定规划问题的非内点算法 1 2 半定规划的基本理论 1 2 1 半定规划的标准形式及其性质“” 半定规划问题的标准形式为 m i n ( c ，x ) s j ( 4 ，z ) = 包，i = 1 2 ，m x - 0 其中c ，4 g y 4 ，x s 为对称矩阵，魂，净1 , 2 ，聊为实数， ( 1 2 1 ) ( c ，x ) # t r ( c x ) 表示c x 的迹。 性质1 , 2 1 半定规划问题是一个凸规划问题，因为其目标函数及约束函数都是 凸函数，其约束集为凸集。 性质1 2 2 一般地说，s d p 的线性矩阵不等式约束是非线性的、非光滑的，但却 是凸的。 性质1 2 3 半定规划的可行集的边界一般不是光滑的，而是分段或分片光滑的。 性质1 2 4 若s d p 的最优解存在，则在可行集的边界上一定存在一个最优解。 1 2 2 半定规划的对偶理论 半定规划原问题的标准形式也可以写成如下形式【1 4 1 ： o ) p + ；警( 乃( c x ) i 什( 4 x ) = 6 f ( f = 1 ，m ) ，x s y ) ( 1 2 2 ) 注意到； p 4 t = i 。n 掣f 。s u 胪p 乃) _ 善咒( 乃( 4 耻匆) = i 。n f 圬s u 胪p 州c 一善圳柳+ 6 r y 交换s u p 和i n f 可以得到( p ) 的拉格朗日对偶： ( d ，s u 胪p 矿y + 堪 n “c 一若m 4 遄) ) m 当且仅当t r ( ( c - 弘4 ) x ) o ，蚜卸时，即当且仅当c 一y , 4 o ，在( d ) 订p-t 的内部最小化问题是下有界的。 在这种情况下，( d ) 的内部最小化问题有最优值0 问题( d ) 可以改写为 第一章绪论 蚱s u ，p b 7 y i c 一善只4 2o ) 的形式 定义s 暑c 一咒4 ，即可得到其拉格朗日对偶问题( d ) 的标准形式如下： d + = s u 。p 6 7 j ，i 只4 + s = c ，s e s t ，y 睨“ ( 1 2 3 ) y l l 当x 和0 ，s ) 分别满足原始和对偶约束条件时，我们分别称之为原始问题和对 偶问题的可行解。 原始和对偶可行集( 即可行解集) 分别记为p 和d ： p # x j t r ( 4 x ) = 龟( f = l ，坍) ，x - o ( 1 2 4 ) 土 d 粤 ( y ，s ) l ：乃4 + s = c ，s 三o y 跄”) ( 1 2 5 ) e d 类似地，+ 和d 吩别表示最优集( 即最优解集) ：p = 协p l n ( c d = p ) ， = ( s ，力d l b r y = d ，值p + 和d + 分别叫做( p ) 和( d ) 的最优值。 我们约定，如果( p ) 是无界的护k 。；如果( p ) 是不可行的, p * - - - c o ( p = 多) 。 对于( d ) 有类似的约定。如果一个问题的最优解尸坳+ 非空，称( p ) ，( d ) 是可 殡的。 半定规划理论的对偶性比线性规划的要弱f 1 4 】。对可行解而言，对偶间隙一般 是非负的，具有零对偶间隙( t r ( c x ) 一b 7 y = t r ( s x ) = 0 ) 的解( x ，y ，s ) 是最理想 的。对l p 而言，若原问题或对偶问题其中一个有最优解，那么这两个问题都有最 优解，而且在最优解处的对偶间隙是零，这是强对偶性质。对s d p 问题，情形就 较为复杂：原问题有最优解而对偶问题可能没有，或者对偶间隙在最优解处可能是 正的等等原问题和对偶问题的最优解要都存在，只有当原问题( p ) 和对偶问题 ( d ) 都有正定可行解，也就是说可行解xy - 0 且s _ 0 ，这称为斯菜特约束规格 1 4 ( s l a t e r c o n s t r a i n t q u a l i f i c a t i o n 或s l a t c rr e g u l a r i t yc o n d i t i o n ) 。 定义1 1 4 1 ( 完全对偶)如果矿= d ，则问题( p ) 和( d ) 称为完全对偶的 定理2 1 1 1 4 1 q ( 弱对偶性) 令x p 和o ，研d ，有t , - ( c x ) 一b 7 ) ，= t r ( s x ) _ o ， 即对偶间隙在可行解处是非负的。 定理2 2 1 1 4 , 1 6 1 ( 强对偶性) 假设扩 一o o ，进一步假设( d ) ( p ) 是严格可 行的，则p # o d $ 0 且矿= d + 。 4 半定规划问题的非内点算法 1 3 1 联系1 ” l - 3 半定规划与线性规划的联系和区别 ( 1 ) 半定规划与线性规划在形式上相似，都是线性函数的极值问题，且都是凸优化问 题。 ( 2 ) 半定规划可视为线性规划问题的推广，即线性规划的向量不等式被线性矩阵不 等式代替。半定规划也可视为一个半无限线性规划，它是指线性函数在对称矩阵的 仿射组合半正定约束下的极小问题。 1 3 2 区别 ( 1 ) 线性规划的可行集的边界一般是多面体而半定规划的可行集的边界一般是非 多面体的。 ( 2 ) 半定规划的对偶理论比线性规划的对偶理论弱【1 钔。 ( 3 ) 线性规划有简单易行且高效的单纯形法；而半定规划尚无直接的、适用的单纯 形法。 1 4 1 内点算法 1 4 主要算法 基于前面介绍的l p 和s d p 之间的联系，l p 的内点算法已被成功地推广到s d p 上来。第一次将l p 推广到s d p 的是n e s t c r o v 和n e m i r o v s k i 1 8 】，a l i z a d e h 在1 9 9 1 年研究了该问题，这也正说明在9 0 年代对s d p 问题的研究兴趣很浓。 内点算法从其下降方式来分主要有：路径跟踪算法、势下降算法等，从其产 生的迭代点列是否满足线性约束可分为：可行与不可行内点算法。内点算法的基本 思想是把约束优化问题转化为无约束优化问题。这种转化常用的方法就是在目标 函数中加一个罚项，罚项在可行域内的值非常小，但是接近可行域的边界时，罚项变 得非常大，从而使迭代点列总在可行域内。 下面给出原始对偶对数罚函数方法： 三 嗽 7 ，( 裕) 一# l o g d e t ( x s ) ：r r ( a x ) = 6 j v f ，m 4 + s = c ) ( 1 4 1 ) 7 j ；1 由文献【l l 】【l7 】可知，该问题的最优解存在且唯一，并且其最优解一定在半正定 锥的内部。利用l a g r a n g e 乘子法可得( 1 4 1 ) 的最优性条件，即k k t 条件【j 刁为： 第一章绪论 r r ( a , x ) = 向o = l ，1 ) ，x 卜0 咒4 + s = c ，s 卜o i t l x s = u l ( 1 4 2 ) 其中第一个条件是原始问题的严格可行解的条件；第二个条件是对偶问题的严 格可行解的条件；第三个是当口一0 对相应互补松弛条件5 x = 0 。上述条件是 ( 1 4 1 ) 最优解的充分必要条件。当肛0 时这些条件可看作是( p ) 和( d ) 的最优条 件的扰动，在假设4 是线性无关的，且( p ) 和( d ) 存在正定可行解条件下，( 1 4 2 ) 存在 唯一解，该解记为( 以，y ，& ) ，且它可被看成是关于肛一条的曲线，称该曲线为 中心路径。以，分别是原始对偶问题和( d ) 的一个可行解，且其对偶间隙为n z 。 对于固定的p ，( 1 4 1 ) 的解，y ，研存在且唯一，下面的定理保证了当p 一0 时， ( | 瓦，y ，& ) 存在聚点，而且该聚点是所求问题的最优解。 弓i 理1 4 1 ”研：令4 ，b 5 p ，则) l 衄( 4 ) 入。( b ) ( 彳，占) ，l 、。( 爿) 】“研。 引理1 4 2 1 9 ：令膏， x e s ”i 肛= 酚和s ，s 。 s i s = c 一y ，y 乳。 ， 则有： ( x 一x ，s 一s - - o 定理i a 3 【1 9 】：对给定序列 段) ，满足以 0 且当k 一+ 时有以一o 。当 以一0 时，眠，) 一定存在聚点，且如果( x o ，) 为氓，瓯) 的聚点，那么z 为 原始问题的最优解，为对偶问题( d ) 的最优解。 为了确定( k ，殴) ，需求解下列非线性方程组【1 6 1 9 l ： w 拂研= 劳c f a x l 利用牛顿法求解：( x ，y ，s ) i 少i _ 一巴( x ，y ，s ) 【笛j 得到搜索方向( 舣，a y , a s ) 。在这里搜索方向是对应求解下列线性系统： 一x = 一( a x - b ) 4 r 少+ s = 一( 彳r y + s c ) ( 1 4 3 ) 蝴+ x a s = u l 一璐 与线性规划内点法不同的是：一般x ，s 是不可交换的，即x s s x 这样解( 1 4 3 ) 得到的s 虽然是对称的，但a x 一般不是对称的，这与下一步迭代需要j + 口舣 是对称的矛盾。采用不同的对称技巧克服这个矛盾，得到不同的原始对偶搜索方向， 其中，软件中常用的有n t 方向、h k m 方向、a h o 方向等，z h a n g 引进对称化算子 统一并推广了这三个方向。 6 半定规划问题的非内点算法 内点法的算法框架： 步1 给定误差容限 0 ，已知严格原始对偶可行点( x o ，y 0 , s o ) 满足 x o 卜o ，s o 卜0 ，令七= 0 步2 解线性化的最优性方程组： f a x l c ( z 弘趵【怎j 2 一以( z 弘回， 得到搜索方向( 凹，沙，a s ) 其中 w 奶沪劳c l o 步3 选择步长，履( o ，l 】使得五+ q 瓦 - o 墨+ 反s 卜0 步4 更新迭代点令 x k “= x l + q t 厶x t y i “= y l + p t 每k s t “= z t + 8 t s t 步5 如果( j ，s ) o l r ( r + 1 ) 2 研) ，由文 献【2 4 】可知它们满足，+ r 厅，并且( 1 4 4 ) 等价于如下规划： m i l lc o ( r r 7 ) s ，a ( 彻7 ) = 6 ( 1 4 5 ) r 驼“7 为了得到( 1 4 5 ) 的局部最优解，b u r e t 和m o n t e i r o 在文献【2 3 】中采用自适应 调节策略来改变，的大小，进而得到s d p 的最优解。 在文献 2 3 1 1 2 4 中，b u r e r 和m o n t e i r 用这种非凸变换石= r r 7 ，r 跄”，把问题 ( 1 2 1 ) 的等价低秩半定规划问题( l r s d p ，) m 两( c ，x ) s f 以，砷= 也，i = 1 ，2 ，一，掰 ( 1 4 6 ) 秩( x ) ， ( 这里，满i f = r ( r + 1 ) 2 小r r r ) 转化为与其等价( 见【2 0 】) 的非线性规划问题 ( n s d p , ) ： 8 半定规划问题的非内点算法 i 响( c r r 7 ) p ( 4 ，r r 7 ) = 以，i = 1 2 ，研 ( 1 4 7 ) 下面讨论非凸光滑优化问题( 1 4 7 ) 的最优性条件，考虑它的l a g r a n g e 函数： ( 足，) = c r r 7 ”( 4 r r 7 一岛) ，l 令s = c 一只4 ，则上式可表示为l ( r ，y ) = s r r 7 + 矿y ，进而它的梯度和二阶 i = l 导数公式具有如下形式： v r ( 4 ( r 掣) 一岛) = 2 4 显 v r l ( r ，y ) = 2 s r v r j l ( r ，y ) e d , d = 2 s ( d d 7 ) ，d e 掰” 定理聊1 ：设f 为( 1 4 7 ) 的局部最有解，并且约束条件在f 处的梯度 2 4 f ：。 线性无关，则存在唯一的，乳”，使得一阶和二阶必要条件： s f = 0 4 r 。d = 0v f = l ，m s o ( d d r ) 0 成立。 定理例：设f 为( 1 4 7 ) 的k t 点，若半正定，n x = r ( f ) 7 ，s ) 分别为s d p 和d s d p 的最优解。 广义拉格朗日算法被认为是一种较好的解决( n s d p , ) 的非线性规划算法。此 算法也是利用罚函数思想。即在不可行点处增加一个罚因子。单纯的罚函数法有时 可导致病态。而广义拉格朗日算法引入拉格朗日乘子只，使每个咒对应一个限制条 件，这样有助于平衡由罚函数产生的病态情形。此外，这些乘子还可以用来检测解 得最优性，并且有助于直接和对偶问题联系起来。 1 5 1s o p 问题在组合优化中的应用 1 5 应用 这部分简单给出s d p 问题在组合优化中一些重要的和成功的应用。 第一章绪论 9 1 t h el o v a s zv - f u n c t i o n i l 4 1 s d p 问题在组合优化应用中最著名的例子就是“t h e l i v a s z 秽f u n c t i o n t h el o v a s z 毋f u n c t i o n 是图g ：( 以e ) 到r + 上的映射，使得 u ( g ) 毋( g ) x t g ) ( 1 5 1 ) 这里( g ) 表示g 的团数，x ( g ) 是需要给图着色的颜色数，并且着色时相邻 点的颜色不能相同，否是g 的完全图，秽( 西是下列s d p 问题的最优值： o ( g ) # t r ( e e 7 柳= e t x e 其中e r 表示所有元素为1 的向量，且满足 矗= 0 ，o ，_ ，) g g ( i ，) t r ( a d = l x 四 关系式( 1 5 1 ) 被称为s a n d w i c h 定理”该定理暗含毋( _ ) 能被看成是u ( g ) 和 x ( g ) 的一个多项式时间逼近，该逼近是与m 有关的，这是一个相对较弱的近似， 最近在逼近性方面的结论又表明：无论u ( g ) 还是x ( g ) 都不能在因子l 叫1 ( 对 垤 0 ) 内进行多项式时间逼近。 2 最大割问题及其扩展1 1 4 l s d p 在组合优化应用中的另一个著名的例子是最大割问题，考虑g = ( 矿，d 这 里每一个边( f ，力有一个给定的权值j ) g o e m a n s 和w i l l a n s o n 2 6 j 毛js d p 对该问题进行了求解，得到了一种随机性的o 8 7 8 近似的算法第一步将最大割问 题看成是一个o ( i 力布尔二次优化问题，也就是带有二次目标函数和布尔变 量的优化问题，对在y 中的每一个顶点，我们引入一个变量 一1 ，1 ) ： l 1 ，若第i 个顶点涂为红色 毛5 1 一l ，若第i 个顶点涂为兰色 于是，对于给定的边( i ，j ) e ，有 il ，若( i ，j ) 是缺陷的 x j _ 5 1 一l ，若( i ，j ) 是非缺陷的 于是最大割的权可由下面式子给出： 卯陉m a x 钆，c # # ( 1 - - x , x j ) = ，鼢厶 s z ， 这里工= - w + d i a g ( w e ) 是对角矩阵。 l o 半定规划问题的非内点算法 这里是具有零对角元素和次对角元素为非负权值的矩阵，e 是所有元素为l 的向量，若所有的权都是0 和l ，则三是拉普拉斯图，由于是一个对角占优阵， 故为一个半正定矩阵 我们将通过以下说明可将问题( 1 5 2 ) 转化为一个s d p 松弛问题。 i ) ，厶= r r ( l h 7 ) ，由迹的性质可得。 i i ) 矩阵为半正定的( 半正定矩阵可分成两矩阵之积) 。 i i i ) 工7 厶= n ( 厶，) 的第三个对角元素为# = i 。 i v ) 矩阵，厶= 丹( 厶，) 的秩为l 。 进而就可得到( 1 5 2 ) 的s d p 松驰： r 1 o l , r _ o e r ：= m a x l a r r ( z x ) l a i o g x ) = e ，j 抄 ( 1 5 ，3 ) g o e m a n s 和w i l l i a m s n 2 6 1 设计出了一种随机扰动方案，用( 1 5 3 ) 的最优解可以 在图中产生出割集，他们的算法产生割的权值至少0 8 7 8 卯r 2 0 8 7 8 0 p t 这结果已被推广到最大k 阶割( m a x - k - c u t ) ，即用k 种颜色代替两种颜色， 该工作由f r i e z e 和j e r r u m 在【2 7 忡完成。具体详细内容参见文献 1 4 】。当边割将所 有顶点分成两个相等的部分时，最大边割问题就变最大二分点问题，f r i c z e t 和 j e r r u m ，给出了最大二分点问题的一种o 6 5 近似算法，该算法被y e 2 8 1 改进到 0 6 9 9 ，另外一种相关的问题是近似图着色问题，目标是给出有k 种颜色的图的一 种合理的着色方法。 3 最大满意性问题( m a x - s a t ) 最大满意性问题被定义为一组布尔分量的集合 c l ，c 2 ，q ) ，每个分量都是从 一组变量 弓，最，只 中分离出来的。或者只是变量，或者一只是变量。 g o e m a n s 和w i l l t a m s o n 在 2 6 1 中用类似于最大割问题的方法证明了最大2 阶满 意性问题，并给出了一种o 8 7 8 近似算法f e i g e 和g o e m a n s 通过添加有效的不等式 ( 所谓的三角不等式) 获得了o 9 3 1 近似算法 k a r l o f f 和z w i c k 2 9 把最大满意性问题扩充到了3 阶并证明了7 8 近似算法。 对于满意性问题，d ek l c = r kc ta i 3 0 研究了一种简单的s d p 松驰形式，并证明 它能用来检测满意性问题中的几种具有多项式形式的可解子类的非满意性。 4 稳定集多面体逼近( a p p r o x i m a t i n gt h es t a b l es e tp o l y t o p e ) 对图g = ( y ，d ，如果子集v c 矿的导出子图没有边，子集矿叫作g 的一个稳 第一章绪论 定集，最大稳定集的基叫做g 的稳定数。一个稳定集矿的关联向量屯被定义为 q ) l = 篇 g 的稳定集多面体s t a b ( g ) 被定义为所有稳定集的关联矩阵的凸包。 s h e r a l i 和a d a m s 在 3 1 d d 第一次提出把一个稳定集多面体看成一个更高维多 面体的映射，l o v a z t 和s e h r i j v e r 在 3 2 1 中给出了相似的思想，用s d p 给出了s t a b ( g ) 的一个描述，这些方法被称作l i f t a n d p r o j e c t 方法，【3 3 】【3 4 】介绍了其它的 l i t t a n d - p r o j e c t 方法。 5 在其它组合优化中的应用 s d p 松驰也可用来解决旅行商问题，二次分配问题、机器运作问题等等 1 5 2s d p 在工程中的应用 目前，s d p 问题应用的最多的领域是系统和控制理论，在这些领域s d p 已成 为一种确定性的工具，参考b o y de ta 1 1 3 5 ，最近b a l a k r i s l m a n 和w a n g 3 6 对s d p 做了更多的研究。 s d p 在其它工程应用包括v l s i 晶体管大小的设计和模式识别( 用椭圆体) 见v a n d e n b e r g h ea n db o y d 3 7 ， 很少关注的一个应用是机械设计，最有名的s d p 问题包括最优的t r u s s 设计( a t r u s si sas t r u c t u r eo fb a r sw h i c hc o n n e c t af i x e d g r o u n d s t r u c t u r e o fn o d e s ) 。 在优化设计中另一个重要的应用是鲁棒性( r o b u s t n e s s ) ，鲁棒优化问题的研究 可以转化为s d p 形式的问题，由b e n - t a le ta l 【3 8 】中给出 1 6 研究现状 上世纪四十年代以来，由于生产和科学研究突飞猛进的发展，特别是电子计 算机日益广泛的应用，使最优化理论和算法迅速发展起来形成- - f q 新的学科。 近二十年来，半定规划已经成为数学规划领域中一个非常活跃的研究方向，原 因如下： 首先，半定规划有有效的算法，求解线性规划的多项式时间算法被成功的推 广到半定规划【4 i 】上来，使半定规划的内点算法在理论上和应用上日趋成熟。并且， 内点算法已被证明是解决中小规模问题可靠有效的算法i l ”。 1 2 半定规划问题的非内点算法 其次，半定规划有广泛的应用领域，s d p 问题在组合优化、逼近理论、系统 控制理论、结构设计、机械及电子工程 4 1 ：2 1 ( 滤波器的设计和移动通信等) 中有 重要的应用。而且自然世界中有许多实际问题都可以通过建立半定规划模型来加 以解决。 在半定规划的内点算法被提出之前，半定规划经过了零散两相对缓慢的发展 阶段，最早可追溯到b e l l m a n 和f a n 4 3 】的工作，他们构造了第一个半定规划问题， 当时称为线性矩阵不等式。后来又有许多学者把许多对称矩阵的最大特征值的最 小化问题转化为半定规划来研究，对此非光滑凸优化问题理论上可用椭球法求解， 虽然椭球法具有多项式收敛性，但实际计算效果很差，因此，未受到重视。正是 在这种背景下，人们寻求理论上有效实际上也切实可行的算法。理论上取得突破 性进展的是n c s t e r o v ，n e m i r o v s k y t l 8 , 4 4 1 基于自和谐罚函数理论得出半定规划问题存 在多项式时间的内点算法；在实际计算上a l i z a d e h 9 1 把著名的k a n n a r k a r 的内点算 法推广到半定规划上，取得较好的效果。y i n y u y c 在 4 5 】中证明绝大多数线性规划 内点算法几乎可不变地推广到半定规划。目前这种算法在理论上非常成熟，并成 为求解中小规模半定规划问题常用的算法。 然而，现实生活中的大量问题往往规模巨大，变量和约束个数经常达到成千 上万个，特别是组合优化问题的半定规划松弛模型是这样的。一般来说，大部分 内点算法都是原始一对偶法。对于大规模问题，这种方法由于利用了牛顿法而限 制了算法性能。牛顿法的每步迭代需要一个大规模的、稠密的线性方程组的求解， 这需要大的内存及急剧增加的计算量。即使充分利用矩阵的稀疏性，在实际应用 中这种算法的局限性也还仍然存在。为了平衡牛顿法的快速收敛性、单步计算量 和存储量大的矛盾，近些年来，b c n s o n 提出的势下降内点算法【1 4 1 可以充分利用某 些组合优化问题的半定规划松弛模型的特殊结构，f u k u d a ，b u r e “9 l 等人基于矩 阵完备化理论提出了更好利用所给问题稀疏性的内点法，从而可以求解矩阵维数 达上千的问题。但是，对于大规模问题，这些方法仍然面i 隘着和原始对偶方法同 样的固有困难。 近几年，出现了几种利用非线性规划求解大规模半定规划问题的比较有效的方 法 2 4 , 2 鄂。这些方法的一个共同点是用基于梯度的信息从而避免了运算量大的线性 搜索和矩阵计算。h e l m b e r g 和r e n d s o l 将一大类半定规划转化为非线性凸规划，利 用非光滑凸规划的向量丛的方法求解得到了普向量丛方法。实验证明该方法在精 度要求不是特别高时是求解一个大规模问题的一个有效的方法。b u r e r 和m o n t e r i o 是利用变换x = 7 ，v 跄”，将最大割问题半定规划松弛转化为一个约束可微非 线性规划问题，给出了实验结果非常好的非线性规划算法。 除了半定规划算法的研究非常活跃之外，有关半定规划应用方面的研究也取 第一章绪论 1 3 得了多方面的进展。g o e m a n s ，w i l l i a m s o n t 2 6 1 对最大割问题利用半定规划松弛模型 提出了0 6 6 9 近似随机扰动算法，h a l p e r i n ，z w i c k 进一步把算法的效率提高到 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 s h 研究了二次背包问题，提出了四种半定规 划松弛模型，并比较了他们的关系。k a r g e r ，m o t w a n i l 5 2 】利用半定规划松弛方法研 究了旅行商问题。一部分人也将半定规划松弛方法应用到鲁棒控制，滤波器的设 计和移动通信等领域中，得到了良好的效果。因此开拓半定规划的应用领域、对 已有的模型提出更强的半定规划松弛以及利用半定规划松弛模型设计近似算法都 具有重要的理论意义和应用价值。 和线性半定规划相比，非线性半定规划的研究刚刚起步。s h a p i r o 研究了非线 性半定规划的一阶和二阶最优性条件，f o r s g r e n 在文献【5 3 】中研究了非凸半定规划 的一阶和二阶最优性条件，d r u m m o n d 研究了非线性半定规划的中心路径，韩乔明 将线性半定规划摄动为二次半定规划进行研究。进一步加深非线性半定规划的理 论研究以及设计半定规划的有效算法将是今后半定规划非常重要的研究方向。 1 7 文章的安捧 本文首先介绍了半定规划的基本理论、主要算法、应用领域和研究现状，然后 借助于非线性规划问题的算法和光滑化方法给出了半定规划问题的有效算法。具 体内容安排如下： 1 第二章首先利用低秩分解技术将半定规划问题转化为与其等价的非线性规 划问题，接着利用非线性规划的筛选算法来解决转化后的半定规划问题。建立了 半定规划问题的筛选算法： 2 第三章首先利用推广的f i s e h e r - b u r m e i s t e r 函数将半定规划问题的k k t 条件 转化为一个等价的非光滑方程组，进而利用光滑化方法将该非光滑方程组光滑化 构造了半定规划问题的光滑化方法。最后讨论了它的超线性收敛性，并在此基础 上，又对算法作了改进，得到了二次收敛性结论 最后是结束语、致谢、参考文献以及本人在硕士学习阶段完成的论文以及参加 的科研项目。 4 半定规划问题的非内点算法 第二章筛选法在半定规划中的应用 本文给出了解决半定规划问题的筛选算法首先采用低秩分解技术将一般的 半定规划问题转化为与其等价的非线性规划问题，进而通过两种筛选算法来求解 该问题一种是基于方向分解的筛选法，分析了它的主要思想，给出了它的收敛性 结论第二种是与s o p 结合的筛选法，对其进行了详细的分析，并给出了较好的全局 收敛性结论 2 1 引言 近几年，s d p 问题在优化领域一直受到人们的广泛关注，对它的研究主要是探 索其在理论上或应用上的有效算法。半定规划的内点法在理论上已非常成熟，并成 为求解中小规模半定规划问题有效的算法，但对于大规模的问题存在内存要求过大 ，运行时间过长等缺点。所以寻找数值结果很好的非内点算法已成为半定规划算 法研究的重点之一。近年来，探索应用上有效的算法受到人们的重视，最近出现的 一些非线性规划算法数值效果很好，我们可将其应用到半定规划上来 非线性规划问题的算法研究已经很多，如线性逼近法和二次规划法，广义拉格 朗日函数等等。最近，f l e t c h e r ： i 1 l e y f f e r l s s 5 6 , 5 7 1 对非线性规划问题提出了一种新的全 局最优化方法。这种方法是为了避免一般惩罚函数或者广义拉格朗日函数那样选 择惩罚参数所带来的困难而给出的，通过定义一个非线性筛子来完成。文献 5 8 】在一 个序列二次规划可信区间算法中，给出了数据实验，数据结果表明方法是非常有效 的。 本文首先通过文献 2 4 ，2 5 c p 采用的低秩分解技术将一般的半定规划问题转化 为与其等价的非线性规划问题，进而结合非线性规划的筛选算法，提出t s d p 的筛 选算法，并证明了该方法的全局收敛性。该算法首先计算一个合适的可信区间半 径，并在其内部迭代，这与沿着分段轨线所进行的后退线性搜索很类似，同时该 方法采用了传统意义上可信区间半径减半或者加倍的技巧及【5 6 】中的可行性修复 算法的思想。 半定规划问题的一般形式为： pp 一 ( s d p ) s j 4 ，x ) = 6 i ，仁l ，2 ，历 ( 2 1 ) i 面 其中c ，4 舻及x ”为对称矩阵，匆，i = 1 , 2 ，肌为实数， 第二章筛选法在半定规划中的运用 1 5 ( c ，x ) # n ( 以) 表示倒的迹下面给出标准半定规划与低秩半定规划之间的一 些相关结论 定理2 1 1 2 4 若x 是s d p 的一个极点，那么r = r a n k ( x ) 满足r ( r + 1 ) 2 m 。 由于问题( 2 1 ) 的最优解是在极点处取得，由上述定理可知：对任何满足 r ( r + 1 ) 2 兰r a 的正数，下列低秩半定规划问题： m i n ( c ，x ) j f 似，x ) = 也，i = l ，2 ，一，m ( 2 2 )