（应用数学专业论文）半定规划及其应用(1).pdf

摘要 半定规划是线性规划的一种推广近年来其理论和算法取得了很大的进展。并 且在组合优化、系统工程和电子工程等领域得到广泛的应用，已经成为数学规划领 域中一个新的活跃的研究方向 本文首先介绍了半定规划的基本知识，包括半定规划的理论、算法、应用和研 究现状，然后在半定规划的算法和应用方面做了一些工作，具体如下： 1 对图的最大二等分问题提出一种非线性规划算法，并给出该算法的收敛性 证明数值实验表明，该方法与y e 0 6 9 9 近似算法( 现有的求解图的最大二等分问 题的最好的多项式时间近似算法) 得到的解的性能几乎没有差异但我们的方法可 以更有效地求解大规模的图的最大二等分问题 2 给出图的最大二等分问题的整数规划模型的等价模型及其新的半定规划 松弛模型，利用投影梯度算法求解该半定规划松弛模型，然后利用随机扰动算法求 得原问题的次优解数值实验表明该方法可以有效地求解大规模的图的最大二等 分问题最后把投影梯度算法用于求解多用户检测问题，仿真实验表明该方法是求 解多用户检测问题的一个很好的方法 3 给出标准二次优化问题的一个强化半定规划松弛模型，把该模型转化为半 不定的线性规划问题，并提出线性规划的一种新的割平面算法解该问题，理论和数 值实验证明了算法的有效性 关键词：半定规划组台优化非线性规划图的最大二等分问题多用户检测 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 nr e c e n ty e a r s ， t h et h e o r ya n da l g o r i t h mf o rs e m i d e f i n i t ep r o g r a m m i n gh a v ed e v e l o p e dg r e a t l y , a n di t s m o s ti m p o r t a n ta p p l i c a t i o n sa r ef o u n di nc o m b i n a t o r i a lo p t i m i z a t i o n ，s y s t e m e n g i n e e r i n ga n de l e c t r i c a le n g i n e e r i n g s e m i d e f i n i t ep r o g r a m m i n gi s an e wa n d i m p o r t a n tr e s e a r c hf i e l di nm a t h e m a t i c a lp r o g r a m m i n g i nt h ep a p e r , w ef i r s t l ys u m m a r i z et h et h e o r y , a l g o r i t h m ，a p p l i c a t i o na n dr e c e n t r e s e a r c ho fs e m i d e f i n i t ep r o g r a m m i n g ，t h e n ，i n t r o d u c eo u rs o m ew o r ki na l g o r i t h ma n d a p p l i c a t i o n f o rd e t a i l ，w ec o i l c l u d et h e ma sf o l l o w s ： 1 an o n l i n e a rp r o g r a m m i n ga l g o r i t h mw a sp r o p o s e df o r t h em a x b i s e c t i o n p r o b l e m ，a n dt h ec o n v e r g e n tr e s u l tw a sg i v e i l t h ee x p e r i m e n t ss h o wt h a tt h e p e r f o r m a n c eo fo u rm e t h o di ss i m i l a rt ot h ey e 0 6 9 9a l g o r i t h m ，w h i c hi st h eb e s t a p p r o x i m a t ea l g o r i t h mi np o l y n o m i a lt i m e b u to u rm e t h o dcane f f c c t i v e l ys o l v et h e m a x b i s e c t i o np r o b l e mw i t ha l a r g es c a l e 2 a ne q u i v a l e n t i n t e g r a lp r o g r a m m i n gm o d e la n d an e ws e m i d e f i n i t e p r o g r a m m i n gr e l a x a t i o nf o rt h em a x - b i s e c t i o np r o b l e ma r eg i v e i l t h e l l ，w es o l v et h e r e l a x a t i o nw i t hap r o j e c t e dg r a d i e n ta l g o r i t h m c o u p l e dw i t ht h er a n d o m i z e dm e t h o d ，a n a p p r o x i m a t es o l u t i o no ft h em a x b i s e c t i o np r o b l e mi so b t a i n e d t h en u m e r i c a lr e s u l t s s h o wt h a tt h em e t h o dc a l l e f f e c t i v e l ys o l v et h em a x b i s e c t i o np r o b l e m a t1 a s t ，t h e p r o j e c t e dg r a d i e n ta l g o r i t h mi s u s e di nt h ec d m am a x i m u ml i k e l i h o o dm u l t i u s e r d e t e c t i o n t h ee x p e r i m e n ts h o w st h a tt h em e t h o di sag o o dm e t h o df o rt h ec d m a 3 as t r e n g t hr e l a x 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 gf o rs t a n d a r dq u a d r a t i c o p t i m i z a t i o np r o b l e m s i s g i v e n t h er e l a x a t i o ni s t r a n s f o r m e dt oas e m i i n d e f i n i t e p r o g r a m m i n g al i n e a rp r o g r a m m i n gc u t t i n gp l a n ea l g o r i t h mi sp r o p o s e d t h et h e o r y a n de x p e r i m e n tp r o v et h a tt h ea l g o r i t h mi se f f e c t i v e k e y w 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 c o m b i n a t o r i a lo p t i m i z a t i o n n o n l i n e a rp r o g r a m m i n g m a x - b i s e c t i o np r o b l e m m u i t i u s e rd e t e c t i o np r o b l e m 创新性声明 y 5 8 3 4 7 1 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：型筮日期： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可阻允许采用影印、缩印或其他复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本人签名： 导师签名么：l 兰翌旦日期：竺主：! 望 第一章绪论 第一章绪论 本章主要介绍半定规划的基本知识，首先介绍了半定规划及其对偶模 型、对偶理论、主要算法及其应用；接着简述了半定规划的研究现状和意 义；最后列出了本文的内容提要和章节安排 1 1引言 1 9 世纪4 0 年代，随着运筹学的产生和发展，在数学规划的领域内产生了许多 新问题而已存在的线性规划和非线性规划的算法不能有效解决这些问题2 0 世 纪6 0 年代，半定规划产生并发展起来b e l m a n 和f a n 1 在1 9 6 3 年第一次构造了一 个半定规划问题接着苏联的一些学者研究了半定规划( 当时也叫矩阵不等式) 在 控制领域中的应用在7 0 年代的早期，d o n a t h 和h u f f m a n 在文献 2 】、c u l l u m h ， d o n a t h 和w o l f 在文献【3 】中把一些难的图分割问题转化成为一个特征值优化问题 求解在对这些实际问题的解决中半定规划的理论和算法得：至l j , f e 大的发展尤其在 9 0 年代，n e s t e r o v 和n e m i r o v s k i t4 ”、a l i z a d e h l 6 1 把k a r m a r k a r l 7 1 提出的线性规划 的内点算法推广到半定规划，导致了半定规划的飞速发展加上半定规划在控制论 1 6 1 、系统论、组合优化【6 ，8 | ”、特征值优化、滤波器的设计0 n , l l l 和移动通信1 1 2 j 3 , 1 4 等 领域的广泛应用，它成为数学规划领域曰益引入注目的研究方向对半定规划的研 究有重要的理论和实际意义 半定规划分为线性半定规划和非线性规划两类由于对非线性规划的研究剐 刚起步，其理论和算法都很不成熟，再加上其本身的应用目前远远不如线性半定规 划，所以对它的研究还很少本文主要是对线性半定规划做了研究，如果没有特别 注明，本文中的所说的半定规划都指的是线性半定规划 1 2 半定规划及其研究现状 1 2 1 半定规划及其对偶理论 半定规划是线性规划的一种推广，它是在满足约束“对称矩阵的仿射组合半 正定”的条件下使线性函数极大( 极小) 化的问题，这个约束是非线性、非光滑、 半定靓划及其应用 凸的，因而半定规划是一个非光滑凸优化问题 半定规划的标准形式【8 9 1 如下： r a i nc x 弘4 x - h ，i - l , ，m ( 1 1 ) x - o 其中红( f - 1 ，m ) 为实数，“”或似，丑) 表示f r o b e n i u s 内积，即当 a b r ，r 为，l 阶实方阵的全体，o ，引s a b 。蚤，呜岛。护( a t b ) 其中， 矩阵一r 表示矩阵a 的转置对x s “，s “为r l n 实对称矩阵的全体，x 苎0 po ) 表 示x 为半正定( 正定) 矩阵，我们用l s ：p ：+ ) 表示n n 半正定( i e f g ：) 矩阵的全 体c ，4 ( f 一1 ，m ) 为i z x n 的实矩阵不失一般性，可以假设c ，4 s “，否则令 ct ( c + c 。) 2 ，a 一( 彳f + a ：) 2 ，i 一1 ，m 即可 为了方便，我们引进线性算子a ：s “一r ”( 尺“表示m 维实的欧几里德空间) ， 满足 4 。x a 2 x 以x 令6 = ( 6 。，也，) ，则( 1 1 ) 可以写成下述等价形式例 s f a r ；6 ( 1 2 ) x 固 a 的伴随算子，记为a ：r ”一s “，根据伴随算子定义，应满足：对任 x s ”，y 尺“有( a x ，y ) 一( x ，a y ) ，因为 ( 从，y ) ；帆跏堆蓦y l ( m y ) 所以有y2 善y 以事实上，当= 1 时2 叫t a 1 第一章绪论 利用l a g r a n g e 方法可以得到半定规划的对偶模型 m a xb y s t a ) ，+ z ；c ，( 1 3 ) z 兰o ，ye r 4 其中z s “，y r “ 为了说明对偶模型( 1 3 ) 也是半定规划，假设问题( 1 1 ) 有可行解牙在( 1 3 ) 的 目标函数中作代换 ( 6 ，) ，) 一( 盯，y ) = 2 7 ，y ) - ( 豆c z ) 令( a ) 表示a 的零空间，x 、z 所属的仿射子空间分别可用仁+ ( a ) ) 和 仁+ ( a ) 1 来表示则原始一对偶模型还可以表示为 m i n ( c ，x ) “x e ( s ：n 留+ ( a ) ) ) m a x ( x ，c z ) “z e ( s ：n 仁+ ( a ) - ) ) 这表明半定规划的对偶模型仍然是半定规划因此，将( 1 2 ) 还是( 1 3 ) 作为原始模 型在本质上没有区别 半定规划是线性规划的推广，它有线性规划类似的对偶理论”1 为了叙述 方便，先给出两个引理 引理1 1 【9 ”1 设4 ，b e s ”且a - o ，b - 0 ，则彳b20 引理1 2 【9 , 2 9 1 设爿，b s ”且4 三0 ，b - o ，则a b = 0 当且仅当a b ；0 半定规划的弱对偶定理如下： 定理1 3 【9 , 2 9 ( 弱对偶定理) 令盖，y 分别为( 1 2 ) 和( 1 3 ) 的可行解，则 c x b y 证明因为 c 一6 y 兰( a y + z ，x ) 一( a x ，y ) = ( z ，z ) 苫0 则由引理1 1 可知，z x20 ，从而有c x b y 定义列偶间隙，7 = ( z ，彳) 记j 口和d + 分别为原规划( 1 2 ) 和列偶规划( 1 t 3 ) 的最 优值，即： 半定规划及其应用 p + 一i n f c 彳f a r b 肖三o d 。s u p p y 1 a 。y + z cz - o 由定理1 3 知p 2 d 如果玎- ( z ，x ) - 0 ，n x ，z 分别为原始规划( 1 2 ) 和对偶规划( 1 3 ) 的最优解， 但与线性规划不同的是即使x ，z 分别为原始规划( 1 2 ) 和对偶规划( 1 3 ) 的最优解 也并不隐含( z ，x ) 一0 参看文献【6 ，9 设盖。和y 印f 分别为原规划( 1 2 ) 和对偶规划( 1 3 ) 的最优解集合，即： j ，印。一 x l c 。x = p + ，a x = 6 ，z 三o ) y 。= y l b t y = d 1 ，a e y + z c ，z - o 易见，即使p + 或d 有限，x ，或y ，也可能为空集我们引进严格可行解的概念 x 为( 1 2 ) 的严格可行解是指x 为( 1 2 ) 的可行解且x - 0 如果( 1 2 ) 存在严 格可行解则称( 1 2 ) 具有严格可行性( y ，z ) 为( 1 3 ) 的严格可行解是指( 弘z ) 为( 1 3 ) 的可行解且z _ 0 如果( 1 3 ) 存在严格可行解则称( 1 3 ) 具有严格可行性 定理1 4 ( 强对偶定理) 设( 1 ) 半定规划问题( 1 2 ) 存在严格可行解 ( 2 ) 半定规划对偶问题( 1 3 ) 存在严格可行解 则有下面结论： ( 1 ) 如果上面条件至少有一个成立，则p = d ( 2 ) 如果上面两个条件都成立，则p = d ，且x ，和y 均非空 该定理的证明可参看文献 5 ，6 ，9 】为了去掉严格可行性的条件，m v r a m a n a ， l t u n c e l ，a n d h w o l k o w i c 在文献 3 1 】中和m v r a m a n a 在文献【3 2 】中研究了不要 求严格可行性的对偶理论虽然他们得到的结果有重要的理论意义，但其形式很复 杂，还未得到广泛的应用，因此我们不做讨论 假设( 1 2 ) 和( 1 3 ) 都存在严格可行解，则可保证至少存在一对原始一对偶最优 第一章绪论 解，即最优解集合石，和y ，都是非空的，从而就存在可行解z ，y 使得 ( c ，石) - b 7 y p d ，町一( z ，z ) 。0 由引理1 2 有屈0 船to 称为互补松 弛条件，它可看成是线性规划互补松弛条件的推广 综上所述，我们可以给出半定规划的最优性条件1 9 若( 1 2 ) 和0 3 ) 均有严格 可行解，则x 为( 1 2 ) 的最优解当且仅当存在啤，z ) s 4x s “使得 f a x ；b ，x - 0 ja f y + z = c ，z 卜0( 1 6 ) i ( z ，x ) 一o 成立这就是半定规划的k k t 条件 1 2 2 半定规划的算法综述 求解半定规划的方法有很多，最成功方法是利用最优性条件的内点算法，其理 论和算法比较完善，使得内点算法成为求解中、小规模半定规划问题非常有效的算 法现在国际上已经有了内点算法的通用软件包 3 3 , 3 4 l ，在许多领域中得到广泛的应 用当然内点算法在求解较大规模问题时，由于内存要求过大、单步执行时间过长 等缺点，不能有效求解大规模的问题近些年来，新发展起来的利用梯度信息的非 线性规划算法在求解大规模的半定规划问题时取得了很好的效果本节简单介绍 原对偶内点算法，非光滑的凸优化算法谱丛方法以及一种光滑的非线性规划 方法 1内点算法 内点算法最初是由a l i z a d e h l 6 ，n e s t e r o v 和n e m i r o v s k i i 【4 】提出的然后 a l i z a d e h 证明了大多数线性规划的内点算法都可以推广到半定规划上n e s t e r o v 和n e m i r o v s k i i 在文献f 5 中利用自c o n c o r d a n t 罚函数的定义给出了用内点算法求 解锥规划的更完善的理论，证明了半定规划存在多项式时间算法 内点算法从其下降方式来分主要有：路径跟踪算法、势下降算法等：从其处理 的规划来分有：原内点算法，对偶调比内点算法和原对偶内点算法内点算法的基 本思想是由约束的问题转化为无约束的问题这种转化常用的方法就是在目标函 数中加一个罚项，罚项在可行域内值非常小，但是接近可行域的边界的时候，罚项 变得非常大，使迭代点列总在可行域内 半定规划及其应用 下面我们介绍半定规划的原对偶路径跟踪内点算法 假设( 1 2 ) 和( 1 3 ) 均有严格可行解，为了避免在优化过程中离开可行域，在( 1 2 ) 的目标函数中加入罚函数一l o g d e t ( x ) ，其中，0 是罚因子考虑罚闯题 n i n c x 一l o g 5 f a x 一6 ， ( 1 7 ) 盖 - o - 因为对任意d r ，集合 z 三o l a x - b ，( c ，x ) ；d ) 是有界闭集，且目标函数是 严格凸的，所以罚问题( 1 ，7 ) 的最优解存在且唯一( 参看文献 9 ) 易知( 1 7 ) 的最优 解一定在半正定锥的内部 通过引进罚因子y ，上述优化问题可转化为一个无约束优化问题 工( x ，y ) = c 。x 一芦t o g d c t ( x ) + y ( 6 一爿( z ) ) 由于l 暇，y ) 是定义在s ：上的凸函数则其最优性条件为 v x l 。= c 一出一a y 一0 v y ，= b x ( x ) 一0 令z - “x ，可以得到 a x b ，石 - 0 ， a y + z ；c ，z _ 0 ， ( 1 8 ) z xt t t i 其中第一个条件是原始问题( 1 2 ) 的严格可行解的条件：第二个条件是对偶问题严 格可行解的条件；第三个条件当一o 对相应于互补松弛条件z 置= 0 条件( 1 8 ) 不仅是( 1 7 ) 最优解的必要条件，而且是其充分条件 对于固定的，( 1 8 ) 的解暖，z ) 存在唯一，定义为僻，z 。) z 。，z 。分别是原 始、对偶问题( 1 2 ) 、( 1 3 ) 的一个可行解，且其对偶间隙为n 肛当，0 时，由( 1 8 ) 的 鳃伍 z 。) 形成的曲线，称为中心路径，这是条光滑曲线( 参看文献 6 ，9 】) 下面 我们来证明：当卢一0 时，皑 z ，) 存在聚点，且若( x ，z ) 是( x z 。) 的聚点，那 第一章绪论 么x 为原始问题( 1 2 ) 的最优解，z + 为对偶问题( 1 3 ) 的最优解 引理1 5 州令4 b s ：，则a “。) a 。) ( a ，b ) s n a 。即) a p ) 证明令p 是满足爿一朋。p 的正交矩阵，其中a 。为a 的特征矩阵，则 ( a , b ) 宰打( 4 b ) 皇押( p a p 且) it r ( a _ p b p ) a 。i 。( a ) t r ( p 口p ) 一 。( a ) t r ( b ) zk 。) k ，( b ) ( a ，b ) = t r ( a b ) = 护( p a p 。b ) = t r ( a 。p b p ) sk 。；( a ) t r ( p b 尸) ，a 。( a ) t r ( b ) n a h 。似) a h ；p ) 引理1 6 令x ，x ” z e s ”la x = 6 ) 和z ，z zl z = c a 1 y ，y 尺 ，则 ( x 一x ”，z 一z ”) = 0 证明因为a ( x 。一x 。) ；0 ，并且a ( y 。一y 。) 一( z 一z ”) ，故 。一( 盖+ 一x 。，a ( y 一y “) ) 一一( z 一x ”，z 一z ”) 定理1 7 t 9 1 对给定序列 心 ，满足以o 且当k 一+ m 时有心- - - , 0 当u 女一0 时( z z 。) 一定存在聚点，且如果( x ，z ) 为( x 。，z 。) 的聚点，那么彳。为原始 问题( 1 2 ) 的最优解，z x c t 0 1 1 ；3 n ( 1 3 ) 的最优解 证明由引理1 7 知 o = ( z 。一xu , z 。一z ”) = ( x 。，z 。) 一( x 。，z 。) 一( x 。，z 。) + ( x 。，z “) 因为( z ，。，z 。) 一n 。，则 ( x 胪z 。) + ( z 。) = 毗+ ( z 。，z 。) 由引理1 5 知 a 。，( x ，。) 。( z 。) + 。( x ”) a 。( z 。) sn 肛i + ( x 。，z ”) 因为a 。；。( zo ) 0 ，a 。；。( x 。) 0 ，又由引理1 5 知， 盖。 ， z ，。 都是有界集，从而 ( x 舻z 。) 必存在聚点( x + ，z ) ，又由( x 。，z 。) = n 。及当女一+ m 时有地一0 可 得( x ，z ) = 0 定理得证 半定规划及其应用 为了确定瞄z 。) ，需求解下列非线性方程组r 2 9 】 一加悟c 卜 ， e + 呱。( 艋，缈，z ) ；0( 1 1 0 ) 得到搜索方向( 腊，a y ，a z ) 在这里搜索方向是对应求解下列线性系统晴”1 由于一般x ，z 是不可交换的，即船一z x 这样解0 ，1 1 ) 得到的a z 虽然是对 称的，但战一般不是对称的，这与下一步迭代需要x + a 从是对称的矛盾利用 不同的对称技巧可以得到不同的内点算法其中主要有n t 方向m 1 、h k m 方向| 3 6 , 3 7 1 、 a h o 方向等m 1 最近p e n g 等人利用自规则函数提出了求解半定规划的新的搜索方 给定初始可行点( x o ，少，z o ) 满足xo 卜o ，zo - 0 2 计算( 脯，缈，z ) ，如需对称化，可利用上面的对称算子得到对称的矩阵 3 选择a ( 0 ，1 】使得x + 8 醚 - 0 ，z + d z - 0 5 如果i 阻z 一6 刚4 y + z c b 仁，z ) 都足够小时，停止否则返回1 关于内点算法的详细资料请参看文献【9 9 2 非光滑优化算法谱丛算法 第一章绪论 谱丛算法是由h l e m b e r g 和r e n d l 提出的，它把半定规划等价为一个特征值 优化问题而特征值优化问题是一个非光滑的凸规划问题，然后利用非光滑规划的 谱丛算法进行求解与内点算法不同的是：谱丛算法利用了梯度信息，是一阶算法， 可以求解许多大规模半定规划问题但是它没有多项式时间的界 假设半定规划问题存在严格的原始可行解和严格的对偶可行解，一个对称矩 阵是半正定的等价于其最小特征值非负：a 。) ：0 ，亦即a 。( 一x ) 弓0 由于这 个性质，半定规划与基于矩阵仿射集上的特征值优化有着密切的联系若 j = x l a x = b ，五三o ) 是一有界集，则有 引理1 8 9 1 若( 1 2 ) 具有有界可行集，则( 1 2 ) 与( 1 3 ) 无对偶间隙，且存在 y e r ”使得a 。穸- ， 在( 1 3 ) 中，z - o 等价于a 。；( 一z ) s0 ，利用l a g r a n g e 乘子法，将条件z - o 自d 入目标函数，得到无约束非光滑优化问题 3 1 凹k ；( c 一y ) + 6 y ( 1 1 2 ) 引理1 9 川若a 满足歹= 1 ，令。= m a x o ，b 乃，那么( 1 3 ) 等价于( 1 1 2 ) 进 而，如果( 1 2 ) 有可行解，则所有可行解x 满足k t r ( x ) = 心，并且最优值p + 可获得， 满足p + t d + = m i n b y 矩阵x 的最大特征值函数可以表示为k x 何) 。m a 。x ，p x p 当p 是x 的最大 特征值所对应的单位特征向量时，a 。皤) ；p x p 。“令 q - 杪h o ，。1 ) 则q 是集台切：恻l ；1 j 的凸包“将p x p 转化成矩阵内积的形式 ( x ，p p ) ，则 a ( 丑) = m a x ( x ，) ：形q 由凸分析的相关知识易知q 有界，a 僻) 是凸函数，且l i p s c h i t z 连续因 此 皑) 在x 处的次微分a 。皤) ，即满足不等式 1 0半定规划及其应用 以及 矽的全集 4 2 , 4 3 1 ，为 a 。0 9 a ( x ) + ( ，y x ) ，v y e s “ 以m 二鬈：嚣2 ；倦) 。， 一伊泞：f r ) ；1 ，y 兰1 0 ； 、 其中p 的列由x 的最大特征值对应的特征向量空间的标准正交基组成【9 】 令f ( y ) 一肛。k 。( c a y ) + y ，容易知f ( y ) 是凸函数，且有结论 a a 。，( c 一y 。) 一p 兰。卜) 一盹，( c a r y ，) = 九。凹一y ) t e v e i t , - 0 , ) t 阳矿兰o ) 筇( y ) 。营垮；6 一肛。a w ，w e 0 1 。；( c a y ) ( 1 1 4 ) 其中，矩阵p 的列构成c a y 的最大特征值所对应的特征向量空间中的标准正 交基参看文献【9 ，4 0 】 h e l m b e r g 和r e n d l 怫”1 将求解非光滑规划的谱丛方法r ”1 推广并应用到问题 n 1 2 ) 上，得到了谱向量丛方法这里的推广指的是将非光滑规划的谱丛方法中的 凸包络函数即割平面模中的平面变成了曲面，从而伴随着每次迭代要求解一个小 规模的二次半定规划详细内容请参看文献【9 ，4 0 ，4 3 】 谱丛方法只利用一阶导数或广义导数的信息，能否利用二阶导数的信息一直 是人们关心的问题随着凸函数的一l a g r a n g e 理论1 的提出，e o u s t r y 研究了最 大特征值函数的口一l a g r a n g e 函数4 神，并应用到最大特征值的极小问题上得到 了半定规划的二阶谱向量丛方法详细内容请参看文献 4 8 】 3 光滑的非线性规划算法 b u r e t ，m o n t e i o r 和z h a n g 把半定规划的对偶问题作为光滑非凸的无约束问题 来讨论在这种算法中，要求x 的迹是常数实际上这种算法可以推广到非线性的 半定规划上，但是收敛性很难证明，关于这种算法的理论和数值结果可以参看文献 第一章绪论 【4 9 ，5 0 ，5 1 】 考虑下述半定规划及其对偶模型 m a xc x s t d i a g ( x ) - d a x ；b x 兰o 其对偶为 r a i n d z + 6 y 5 s d i a g ( z ) + a y 5 三o 我们下面介绍一下本算法的思想 定义对角线元素非负下三角矩阵l ，这样矩阵的全体记为z ，定义对角线元 素全为正的下三角矩阵的全体为e + 对于任意的对称正定矩阵s ，利用c h o l e s k y 分解，得到s = 叫，l 口+ 而l 可以分解为lt d i a g ( w ) + 三。，这里w 的元素非 负，l 0 是一个严格下三角矩阵则有 d i a g ( z ) + a y c = ( d i a g ( w ) + 三。) ( d i a g ( w ) + k ) 则集合 ( z ，_ ) ，s ) r “x r s ：+ ：s ；d i a g ( z ) + 爿y c ) 可以记为 0 ，y ，工) r “x r 。e + ：d i a g ( z ) + 4 。y c = ( d i a g ( w ) + 厶) ( d i a g ( w ) + 厶，) ) 进行上面的步骤，可以得到下面的等价模型”“1 m i “ d 2 ( ”，y ) + 6 y ( 1 1 5 ) s t w 0 这样，目标函数中的矩阵s 转化为两部分z ( w ，y ) ，并且我们得到的问题是开 集由于原问题的解在边界取得，所以得到的模型不能直接求得最优解，因此得到 的解只是原问题一个非常逼近的近似解，并且z ( w ，y ) 是无限可微的，所以半定规 划问题可以转化为一个非凸无约束优化问题 b u r e r 利用对数罚函数和势下降算法求解( 1 1 5 ) ，算法的关键在于计算梯度尽 1 2半定规划及其应用 管目标函数是非凸的，但其全局收敛性可以证明，且可得到非常好的数值结果 1 2 3 半定规划的应用举例 本节将通过几个实例说明半定规划应用的广泛性，由此说明对半定规划的研 究有着广泛的理论意义和应用价值 例1 二次锥规划 二次锥规划的标准形式如下1 1 5 = tj 1 4 x 。矗忙咖“，m ( 1 4 ) s 0+ 包0 sc ；x + d i ，f 誊1 ，一， 其中，工r “，c g r “，4 r ”，b j r “，c f e r “，d f r ，i 。1 ，m ，”i i 为欧氏范 数，即l l “| l 薯( “) i 二次锥规划在雷达方阵权的设计”、自适应有限脉冲滤波器 的设计 1 0 , 1 1 , 1 8 l 、捆绑设计【1 9 1 等问题上都有广泛的应用 约束h a i x + b i 忙c 扛+ d 。可等价为如下形式 ，( c ；x + d t ) ，a i 。+ b j t - 0 i ( 4 工+ 4 ) c j x + d 。 其中，是单位矩阵 故0 4 ) 可以转化为 m l r l 5 f 这样= 次锥规划就可以转化为半定规划问题有许多闷题，如含有范数的问题 【n 驯、双曲约束问题1 、分数矩阵问题n 5 1 等都可以通过简单的变形转化为二次锥 规划问题，从而转化为半定规划 例2 特征值优化问题 设对称矩阵爿0 ) 是_ x q r 的仿射函数，即爿 ) = ，+ z ： + + t a k 其中 4 s ”，f i o 1 一，k 爿( 上) 的最大特征值的最小化问题即为 $0 小 卜一 趣以 + 和咖 y y砟红 + + “陋 塑二童鲨 1 2 1 1 1 1 1 1 ( 4 ) ) 引进变量t ，该问题可以归结为如下半定规划 r a i n t s ， 盯4 ( z ) 至o 其中t e r ，x e r 。 这一问题在控制论、结构优化、组合优化、图论等领域有着广泛的应用埘 例3 图的最大k 一分割 给定图g 一，e ) 的顶点集矿；a ，h ) 和每对顶点i 和j 间的非负权值 = w j 则图的最大七一分割由下述的整数二次规划给出 m a x 号艺( 1 一u v ，) 2 鲁” 7 “ h | = 七 v 一1 ，1 卜 若令l - 三( d l a g ( w e ) 一) ，x v v r ，则图的最大七一分割的半定规划松弛模型为： m a x ( l ，x ) s 1 d i a g ( x ) a e ( ，x ) ；k 2 z 兰o 其中d i a g ( x ) 表示以z 只”为对角元素，其它元素均是o 的矩阵，逆算子为 d i a g ( x ) 它为解图的最大七一分割提供了一个上界与半定规划联系较紧密的组 合优化还有最大割问题、图的着色、顶点覆盖、0 - i 背包问题等等，它们均可以通 过半定松弛的方法求出一个松弛界【2 1 - 2 5 1 ，而且更强化的松弛模型也很快出现在文 献 2 6 ，2 7 ，2 8 】中 上面，我们给出了三种可转化为半定舰划的问题，丽实际中很多问题又可以转 化为上述三种问题，这说明半定规划的应用是十分广泛的，对半定规划的研究有着 深远的意义，可以为解决这些问题提供一种统一的方法 1 4 半定规划及其应用 1 2 4 半定规划的研究现状 近十几年内，半定规划已成为数学规划领域中一个非常活跃的研究方向半定 规划之所以引起人们如此大的兴趣主要由于下面两个方面的原因：第一，半定规划 有广泛的应用领域，例如在统计学、结构设计、电子工程1 1 0 - 1 4 ( 滤波器的设计和移 动通信等) 、组合优化等领域的应用第二，线性规划的内点算法被成功地推广到半 定规划上 ”- 3 8 蚓，使半定规划的内点算法日趋成熟并且，已被证明内点算法是求 解中小规模问题可靠有效的算法1 9 然而，来自实际的问题往往是大规模的，特别组合优化问题的半定规划松弛模 型w 3 1 一般来说，大部分内点算法都是原对偶方法，对于大规模问题由于这种方 法利用了牛顿法而影响了算法的性能牛顿法的每步迭代需要求解一个大规模的、 稠密的线性方程组，这需要大的内存及急剧增加的计算量。如何解决内点法在求解 大规模问题时的局限，许多人做了许多有实际意义的研究，且取得了一些成果他 们采用了最新的矩阵分解技巧和一些求解矩阵方程的最新算法，力求利用矩阵的 稀疏性，如采用c h o l e s k y 分解，采用低阶分解，采用预处理的共轭梯度法( c o 算 法) ”1 和梯度残量算法( c r 算法) 惭等。这些算法在一定程度上可以求解大规模的 半定规划问题，但是其求解的精度不高，比较适台于求解一些精度要求不高的组合 优化问题，不能满足精度要求高的问题的求解b e n s o n 提出的势下降内点算法可以 充分利用某些组合优化问题的半定规划松弛模型的特殊结构，从而可以求解矩阵 维数达上千的问题m 1 最新由m i t u h i r of u k u d a 等【5 8 1 提出了拉格朗同对偶预估校 正内点算法，大量的数值实验证明该算法在求解一类大规模的半定规划问题时可 以得到较高精度的最优解，比如组合优化问题中的最大割问题，图的二等分问题等 但是规模更大的问题，这些方法仍面临着和原始对偶方法同样的固有困难5 “4 5 近几年。出现了几种利用非线性规划求解大规模半定规划问题的比较有效的 方法1 4 0 , 4 9 , 5 9 , 6 0 1 这些方法的一个共同特点是用基于梯度的信息从而避免了运算量 大的线性搜索和矩阵运算h c l m b c r g 和r c n d l f9 ”1 将一大类半定规划转化非线陛凸 规划，利用非光滑的凸规划向量丛的方法求解得到了谱向量丛方法实验证明该方 法在精度要求不是特别高时是求解大规模问题的一个有效的方法h o m e r 和 p e i n a d o 【叫是利用变换x = 阿，v r “，将最大割问题半定规划松弛转化为一个 第一章绪论 无约束可微非线性规划问题，给出了实验结果非常好的算法晟近，b u r e r 和 m o n t e r i o ”1 利用向量转化石- l f ，工是一个下三角矩阵，对最大割问题半定规划 松弛提出了另一种g u r e r 和m o n t e r i o 算法s a m u e lb u r e r 、r e n a t od c m o n t e i r o 和y i nz h a n g 在文献 4 9 5 1 中将一大类半定规划转化为光滑的非凸的非线性规 划问题，利用非线性规划求解寻找求解大规模半定规划问题的方法是一个非常重 要的研究方向 在半定规划的应用领域中，组合优化问题的求解是半定规划一个非常成功的 应用g o e m a n s ，w i l l i a m s o n “1 对最大割问题利用半定规划松弛模型提出了o 8 7 8 近 似随机扰动算法y i n y uy e t 6 3 1 研究了图的最大二等分问题，提出o 6 9 9 近似随机扰 动算法c v e t k o v i c ，c a n g a l o v i c ，k o v a c e v i c v u j c i c “1 利用半定规划方法研究了旅 行商问题h e l m b e r g 、r e n d l 和w e i s m a n t e l 删研究了二次背包问题，提出了四种半 定规划松弛模型，并比较了它们的关系此外，许多人也将半定规划松弛方法应用 模式识别 6 7 1 ，代数，滤波器的设计和移动通信 1 0 - 1 4 等领域中，得到了良好的效 果开拓半定规划的应用领域、对已有的模型提出更强的半定规划松弛、利用半定 规划松弛模型设计好的近似算法也都是现在非常有意义的研究方向 和线性半定规划相比，非线性半定规划的研究刚刚起步a l e x a n d e rs h a p i r o 在文献 6 9 】中研究了非线性半定规划的一阶和= 阶最优性条件；a n d e r sf o r s g r e n 在文献 7 0 】中研究了非凸半定规划的一阶和二阶最优性条件；l m g r a n a d r u m m o n d 在文献【7 1 中研究了非线性半定规划的中心路径最近，b f a r e s ，d n o l l 和p a p k a r i a n ”1 对一类机器控制设计问题的非线性半定规划模型提出了一种序列 线性半定规划算法，显示出很好的数值结果关秀翠，刁在筠在文献 7 3 】研究了二 次半定规划问题并给出了一种投影收缩算法进一步加深非线性半定规划理论研 究、设计非线性半定规划的有效算法并拓展其应用领域将是今后半定规划非常重 要的研究方向 总之，对半定规划的研究具有重要的理