（应用数学专业论文）半定规划的外梯度法研究.pdf

摘要 与线性规划相比，半定规划是把向量变量由矩阵变量代替，向量的非负性由 矩阵的半正定性代替。因此，半定规划是线性规划的推广。求解半定规划的方法 很多，最成功的方法是利用半定规划的最优性条件得到的内点算法。半定规划的 内点算法正是线性规划内点算法的推广。半定规划是凸规划的一个重要分支，并 且半定规划在组合优化、逼近理论、系统控制理论、机械及电子工程中有着广泛 的应用。因此对半定规划的研究有着重要的理论与实际意义。 本文对半定规划问题进行有效的变换，把求解半定规划问题转化为求解变分 不等式问题，再给出一个改进的求解变分不等式问题的外梯度法，从而得到半定 规划问题的最优解。本文主要工作如下： 首先较为系统的研究了一些重要的最优化问题间的关系，其中包括线性规划， 凸二次规划，线性半定规划，二阶锥规划，多项式最优化等。其次，在满足严格 可行性条件下，将线性半定规划和二次半定规划问题分别转化为变分不等式问题。 最后对已有的变分不等式的一般外梯度法，通过改进校正步步长提出了改进的算 法。给出了改进算法收敛性的证明，并通过数值实验说明该算法是求解半定规划 的一种有效算法。 关键词：半定规划变分不等式投影方程外梯度法 a b s t r a c t c o m p a r e d w i t hl i n e a r p r o g r a m m i n g ，v e c t o r i s r e p l a c e db y m a t r i xa n d n o n n e g a t i v i t yo fv e c t o ri sr e p l a c e db ys e m i d e f i n i t ep r o p e r t yo fm a t r i xi ns e m i d e f i n i t e p r o g r a m m i n g t h u s ，s e m i d e f i n i t ep r o g r a m m i n gi s8 _ r 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 t h e r ea r em a n ym e t h o d sf o rs o l v i n gs e m i d e f i n i t e p r o g r a m m i n g ，i nw h i c ht h e i n t e r i o r - p o i n tm e t h o d sa r et h em o s ts u c c e s s f u l m o s ti n t e r i o r - p o i n tm e t h o d sf o rl i n e a r p r o g r a m m i n gh a v eb e e ng e n e r a l i z e dt ol i n e a rs e m i d e f i n i t ep r o g r a m m i n g s e m i d e f i n i t e p r o g r a m m i n gi sab r a n c ho fc o n v e xo p t i m i z a t i o np r o b l e m i m p o r t a n ta p p l i c a t i o n so f s e m i d e f i n i t ep r o g r a m m i n ge x i s ti nc o m b i n a t o r i a lo p t i m i z a t i o n ，a p p r o x i m a t i o nt h e o r y , s y s t e ma n dc o n t r o lt h e o r y , a n dm e c h a n i c a la n de l e c t r i c a le n g i n e e r i n g i n v e s t i g a t 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 sv e r ys i g n i f i c a t i v eb o t hi nt h e o r ya n di np r a c t i c e i nt h i s p a p e r ，s e m i d e f i n i t ep r o g r a m m i n gi se f f e c t i v e l yt r a n s f o r m e di n t oa v a r i a t i o n a li n e q u a l i t yp r o b l e m a ni m p r o v e de x t r a - g r a d i e n tm e t h o di s p r o p o s e d 血e n s e m i d e f i n i t ep r o g r a m m i n gi ss l o v e d f o rd e t a i l ，w ec o n c l u d et h e ma sf o l l o w s ： t h er e l a t i o n so fs o m ei m p o r t a n to p t i m i z a t i o np r o b l e m sa le s y s t e m a t i c a l l ys t u d i e d i nt h i sp a p e r , s u c ha sl i n e a rp r o g r a m m i n g ，c o n v e x q u a d r a t i cp r o g r a m m i n g ，s e c o n d o r d e r c o n ep r o g r a m m i n g ，s e m i d e f i n i t ep r o g r a m m i n ga n dp o l y n o m i a lo p t i m i z a t i o np r o b l e m s w h e ns e m i d e f i n i t ep r o g r a m m i n gs a t i s f i e st h es l a t e rc o n d i t i o n s ，l i n e a ls e m i d e f i n i t e p r o g r a m m i n ga n dq u a d r a t i cs e m i d e f i n i t ep r o g r a m m i n ga l et r a n s f o r m e di n t ov a r i a t i o n a l i n e q u a l i t yp r o b l e m s i nt h i sp a p e r , an e ws t r a t e g yf o rc o m p u t i n gc o r r e c t i o ns t e ps i z ei s p r o p o s e di ng e n e r a le x t r a g r a d i e n tm e t h o d f u r t h e r , t h ec o n v e r g e n c eo ft h en e w a l g o r i t h mi sp r o v e d n u m e r i c a le x p e r i m e n ts h o w st h a tt h en e wm e t h o di se f f e c t i v ef o r s o l v i n gs e m i d e f i n i t ep r o g r a m m i n g 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 gv a r i a t i o n a li n e q u a l i t y p r o j e c t i o ne q u a t i o n e x t r a g r a d i e n tm e t h o d 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果：也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：丕盔 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位仍然为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 日期坐! ! ：! ：f 一学 名 名 签 签 人 师 本 导 第一章绪论 第一章绪论 本章首先介绍了线性半定规划的标准形式及其对偶理论，其次系统阐述了一 些重要的优化问题问的关系，最后概述了半定规划的主要算法及其研究现状，并 说明了本文的内容安排。 1 1 引言 最优化是应用数学一个十分重要的分支。虽然最优化可以追溯到十分古老的 极值问题，然而直到1 9 4 7 年d a n t z i g i l l 提出求解一般线性规划( l i n e a rp r o g r a m m i n g ， 简记l p ) 问题的单纯形法之后，最优化才成为一门独立的学科。现在解线性规划、 非线性规划、随机规划以及非光滑规划、多目标规划等各种最优化问题的理论和 研究日益趋于成熟完善，实际应用日益广泛。 随着运筹学的产生和发展，在数学规划领域产生了许多新的问题。而已有的 线性规划和非线性规划算法已经不能有效的解决这些问题。于是半定规划 ( s e m i d e f i n i t ep r o g r a m m i n g ，简记s d p ) 问题应运而生。在1 9 6 3 年，r b e l l m a n 和 k f a n 1 2 1 首次提出了一个半定规划问题。线性半定规划是指满足约束“对称矩阵的 仿射组合半正定”的条件下使线性函数极大( 极小) 化的问题。这个约束是非线 性、非光滑、凸的。因此，半定规划是一个非光滑凸优化( c o n v e xp r o g r a m m i n g ) 问题，是特殊的锥优化问题。1 9 8 1 年，c r a v e n 和m o n d 【3 l 把半定规划描述为“带 有矩阵变量的线性规划”，这种描述是对半定规划很恰当的介绍。与线性规划相比， 半定规划是把向量变量由矩阵变量代替，向量的非负性由矩阵的半正定性代替。 因此，线性半定规划是线性规划的一种推广。半定规划与线性规划有着密切的联 系，半定规划的理论与线性规划非常相似。但在开始的二十多年里，半定规划并 没有引起人们的足够重视，主要是由于半定规划的可行集不再是多面体，没有适 用的单纯形法。直到上世纪9 0 年代，n e s t e r o v 和n e m i r o v s k i 4 i 及a l i z a d e h 5 1 分别 把线性规划的内点法推广到半定规划，这才再次激起了人们对半定规划研究的兴 趣。半定规划之所以成为人们研究的热点，主要原因包括：( 1 ) 一些重要的问题可 以看成是半定规划的特例，如线性规划和二次规划。( 2 ) 半定规划在组合优化 6 , 7 1 、 逼近理论、系统控制理论 8 , 9 1 、机械及电子工程【lo j 中有着广泛的应用。因此对半定 规划的研究有着重要的理论与实际意义。( 3 ) 半定规划问题是凸规划，因此其局部 最优解是整体最优解，w b l f e 对偶定理等重要结论对半定规划成立。( 4 ) 线性规划的 内点法被成功的推广到半定规划上 i 1 - 1 3 】，使半定规划的内点法同趋成熟，使它无 2 半定规划的外梯度法研究 论在理论上还是实际中都有行之有效的多项式时间算法。 1 2 1 线性半定规划 1 2 线性半定规划及其对偶理论 为表述方便，首先给出本文用到的记号：冗”为n 维欧式空间。趟为r ”的非 负象限，即群= 讧r ”：x i o ，f - l ，刀 。s ”为n 阶实对称阵集合，即 s ”= 汲i x 犬“”，x = x7 掣为n 阶实对称半正定阵集合，即口= 臼s ”：x r a x o 。由凸锥的定义知，群和 掣都是凸锥。若a 掣，则称a 半正定，记作a - o 。若a s ”，对v d r ” o ， 都有d r a d 0 ，则称a 正定，记作么 _ 0 。 若a 不是对称阵，我们有 一气1x r a x + 三1 ( n = f 血+ 三x t a t x = x r ( 竿) x 讨论a 的半正定性或正定性，等价于讨论对称阵竺妥笙的半正定性，故不失 一般性，在s d p 问题中讨论的都是对称阵。 半定规划的标准形式【6 7 1 为 r a i n c x ( p )s ，a i x = 6 j江1 ，m( 1 - 1 ) x - o 其中6 f ( f = 1 ，聊) 为实数，c 和4 ( 江1 , 2 ，m ) 属于s ”。 或表示f r o b e n i u s 内积，即 - 爿b = t r ( a r b ) = 口口b q 。 ，= l = i 利用l a g r a n g e 法可得半定规划的对偶规划【7 1 为 m a xb r y ( d ) s j y ，4 + s = c ( 1 - 2 ) i = l s 三0 ，y r ” 假设矩阵4 ( 江l ，m ) 是线性无关的。对给定的对偶可行解s ，在该假设下， y 是唯一确定的。故该假设允许用y d 或s d 来代替( y ，s ) d 。注意到 a 。( 江l ，m ) 线性无关等价于v e c ( a f ) ( f - l ，m ) 线性无关，因此这一假设在本质 第章绪论 3 上与l p 中假设约束矩阵是满秩的等价。故此假设不失一般性。 为了表述方便，通过消掉s 和简单的变量代换( y 寸x ，b 寸c ，c 专y o ， 彳，_ 只) ，我们可以把对偶规划写成如下形式： r a i nc t x ( d )s j f ( x ) - o( 1 - 3 ) 其中，f ( x ) = v o + 薯f t = l 故半定规划的对偶形式的目标函数是线性的，约束条件为使得一个线性依赖于 门维向量x 的矩阵f ( x ) 半正定。 半定规划的原问题和对偶问题的可行集分别用p 、d 表示： p ：= xa ，x = 匆( f = l ，研) ，x 三0 ) d ：= s ) l y ，4 + s = c ，s 三o ，y e 尺”) ，- i 类似地，p 木和d 枣分别表示最优集( 即最优解集) ： p ：= x p l c x = 矿) d 术：= ( s ，y ) d 1 6 7 y = d 木 其中p 幸和d 宰分别为( p ) 和( d ) 的最优值。 如果( p ) 是无界的，约定p 掌= 0 0 1 如果( p ) 是不可行的( p = ) ，约定p * = o o 。 对于( d ) 有类似的约定。 如果p 木( 或d 宰) 非空，问题( p ) ( 或( d ) ) 称作可解的，。 引理1 2 1 1 6 7 1 ( i e 交性) 令( x ，( 少，s ) ) p xd 和( x o ，( y o ，s o ) ) p xd 为两对可 行解。记赵= x x o 及a s = s s o ，则从a s = 0 。 证明：由丛和d 的定义，有 丛= ( j ，：) 一咒) 4 ，即丛s p a n a l ，一，a 。) ，= l 类似地，由从和p 的定义，有 a 。x = a f x a j x o = 匆- b , = o ，( f = 1 ，1 ) 即舣s p a n a l 一，a 。) 上 这说明笛在s 。的子空间中，且该子空间是由矩阵a ，( 汪1 ，m ) 张成，舣在 该子空间的正交补中。故战笛= 0 。证毕。 现在令l ：= s p a n a l ，a 册)( 1 - 4 ) 设m s 。满足 4半定规划的外梯度法研究 4 em = 允“= 1 ，m ) 和c m = 0 则原规划和对偶规划还可以表示为 m i n c x s ，x p + m和 x - o m a x m s s 1 s l + c s - o 其中l 是( 1 4 ) 所定义的。 这表明半定规划的对偶规划仍是半定规划。因此，把( 1 - 1 ) 还是( 1 - 2 ) 作为原始 模型在本质上没有区别。 1 2 2 对偶理论 半定规划是线性规划的推广，它有类似线性规划的对偶理论。 弓i 理1 2 2 6 7 1 设a ，b s ”，且a - 0 ，b - 0 ，贝0 彳b 0 。 引理1 2 3 f 6 7 1 设彳，b s ”，且a - 0 ，b - 0 ，则a b = 0 当且仅当a b = 0 。 定理1 2 4 6 7 , 1 4 1 ( 弱对偶定理) 令x ，( y ，s ) 分别为( 1 一1 ) 和( 1 2 ) 的可行解，则 c x b r y 。 ，r d、m 证明：c ox - b 7 y = i y ，a ，+ si x 一少，( 4 x ) = s x ，且x 三o ，s 一 - 0 。 i = 1 i = 1 由引理1 2 2 知，s x 0 ，从而有c x b r y 。 定义对偶间隙叼( x ，y ) = c x b r y = 。对偶间隙的非负性即弱对偶 性。 。 定义1 2 5 6 7 1 如果矿= d 幸，则称问题( p ) 和( d ) 为完全对偶的。 x 是( 1 一1 ) 的严格可行解是指x 是( 1 - 1 ) 的可行解且x - 0 。( y ，s ) 是( 1 - 2 ) 的严格 可行解是指( j ，s ) 是( 1 2 ) 的可行解且s 卜0 。 半定规划的原问题和对偶问题的严格可行集分别用p o 、d o 表示： p o ：= x 1 4 ex = 6 i ( 扛l ，：所) ，x - 0 ) d 。：= ( y ，s ) l 只4 + s = c ，s _ o ，y e r m ) i = l 定理1 2 6 【4 6 7 1 ( 强对偶定理) 如果扩 - - - 0 0 ) ，且( d ) ( 或( p ) ) 是严 格可行的。那么p 枣o ( 或d 宰o ) ，且p 宰= d 母。 推论1 2 7 【6 7 】如果( p ) 和( d ) 都是严格可行的，即尸o 、d o 非空，那么p 幸= d 术且 p 木和d 木都是非空的。 严格可行性条件也称s l a t e r 约束条件或s l a t e r 约束规格，它是保证凸优化问题 第一章绪论5 强对偶成立的一个充分条件。为了在较弱的条件下给出强对偶定理成立的条件， m vr a m a n a , l t u n c e l ，a n dh w o l k o w i c z 在文献【1 5 】中，m vr a m a l l a 在文献 1 6 】 中研究了不要求严格可行性的对偶理论，虽然他们得到的结果有重要的理论意义， 但其形式复杂，因此本文不做讨论。 假设( 1 1 ) 和( 1 2 ) 存在严格可行解，由推论1 2 7 知，最优解集p 幸和d 幸都是非 空的，从而存在可行解x ，y 使得c x = b r y = p + = d + ，7 = = 0 。由引理 1 2 2 知，条件 - 0 等价于x s = 0 。x s = 0 称为互补松弛条件，满足此条件 的最优解称为互补最优解。 从而( p ) 和( d ) 最优性的充分条件是： 彳f x = b i , x 兰0 ，i = 1 ，m y f a f + s = c ，s - 0 ( 1 5 ) 扛l 骼= 0 推论1 2 7 说明如果( p ) 和( d ) 是严格可行的，那么条件( 1 5 ) 也是必要条件。 定理1 2 8 ( 最优性充要条件) 在严格可行性条件下，系统( 1 5 ) 是( p ) 和( d ) 的最优 性的充要条件。 1 3 半定规划与其他重要最优化问题间的关系 本节较为系统的研究了包括线性规划、凸二次规划、二阶锥规划、半定规划、 多项式最优化等重要的最优化问题间的关系。 1 3 1 线性规划 在半定规划问题( 1 1 ) 中，若令 4 = d i a g ( a , ) ( f = l ，m ) ，c = d i a g ( c ) ，x = d i a g ( x ) ， 其中d i a g ( u ) 表示以向量u 为对角元素得到的对角矩阵，则s d p 问题变成了一个标 准的l p 问题： m i n f ( x ) = c 7 x s t a x = b x 0 其中a 是以矿为第i 行的矩阵，j i b = 【b l ，b 。】r 。因此，线性规划是线性半 定规划的特例，线性半定规划包含了线性规划。 6 半定规划的外梯度法研究 1 3 2 凸二次规划 凸二次规划问题的一般形式为 m i n f ( x ) = x t q x + p r x s ，a x b ( 1 - 6 ) 其中，q 三o s j x 彳r x q x + 6 p 7 x 6 ( 1 7 ) 血6 、7 其中，q - o 对于第一个约束条件，由于q 至0 ，必存在正交矩阵u ，使得 q = u 九 u r 其中九为q 的特征值， q = u 其中q = ( 历) 2 ( 历，： u r = u _ 历 历。历 u 7 = 垂r 豆 k ，7 ， 压j l 记q = q z 。 凼此，i 司题( 1 - 7 ) 中第一个约束条件n - - i 以写成6 一x 1q 。q x p 。x 0 ， 该条件等价于 哪，2 出6 纠三。 证明： i ，? 、r 。a xk o 等价于 i ( 函) 卜6 一p r xf q 川。 一。gx ，r? 。互二，f6 - ! 萝；rx 三 一了x 三。， 即瞄6v x 一幺九两卜等价于n 留函圳。证毕。 第一章绪论 7 另外，第二个约束条件可以写成f ( x ) - - f o + 毛e 三o ，其中r = 一d i a g ( b ) ， f = d i a g ( a ，) ，a 。是矩阵a 的第i 列。 定义扩充的变量i = i ，则凸q p 问题c - 一6 ，等价于如下半定规划问题： r a i n 乏t i s j e ( i ) 三0 其中弓= 【1 ，0 ，o t ，j t e ( 2 ) = d i a g g ( s ，x ) ，f ( x ) ) 。这正是半定规划( 1 - 3 ) 的形式。 下面考虑如下带二次约束的凸二次规划问题 m i n f ( x 1 = x 7 q x + p 。x s j x 7h 。x + q ? x + o ，i = 1 9o * o ，m ( 1 - 8 ) 其中q 三0 ，e 三0 若对所有的i ，e = 0 ，则该问题就为凸二次规划问题( 1 6 ) 。带二次约束的凸 q p 问题等价于 m i n6 盯譬h 二- i - 嚣0i 1 ，卅 m 9 ， x 。 x口? x + f ，= ，聊 、 其q bq - 0 ，h 。三0 ( 1 - 7 ) 禾1 ( 1 9 ) 的第一个不等式约束相同，故( 1 - 9 ) 的第一个约束等价于 g 加出嚣x 卢 第二个不等式约束就等价于 砸，= 出一塞，；卜 其中h l = a ：豆i 故带二次约束的凸q p 问题( 1 8 ) 等价于如下半定规划问题： m i n 爸t i s j e ( 舅) 三0 其中i ：陉 ，弓：【1 ，o ，o r ，且e ( 王) ：d i a g g ( 5 ，x ) ，e ( x ) ，巴( x ) 。这正是 半定规戈l j ( 1 3 ) 的形式。 因此，凸二次规划可以转化为线性半定规划，线性半定规划包含了凸二次规 8 半定规划的外梯度法研究 划。 1 3 3 二阶锥规划 定义1 3 1 若k = 匕 ：”圳u 尼”r ”1 ，则称k 为一个n 维的二阶锥。 二阶锥规划问题( s e c o n d o r d e rc o n ep r o g r a m m i n g ) 的标准形式6 2 1 为： 口 r a i n c i t x i 豇圭互t = b ( 1 - 1 0 ) x f k f ，i = 1 , 2 ，g 其中互r 胀1 ，x f r 删1 ，j ，r ”一，b r 删，且k ，是刀，维的二阶锥。 s o c p 问题的对偶规划1 为： m a x b 7 y s j a f y + s j = ti = l 2 ，留 ( 1 - 1 1 ) s l k f i = 1 , 2 ，g 翔叫，耻酣莓船婀删唧晒脱 s j 0 4 - x + q0 6 - x + d ， i ：1 ，2 ，g 1 - 1 2 因为k = ：f ：l j 甜l i 乙，r ，甜r ” i t ： 兰。 所以l 彳_ x + q i i x + 4ol x b r r x 彳，+ + d c , f ) fa v f x x i + + 4 c 三。 故问题( 1 1 2 ) 等价于如下半定规划问题 m i n b7 x s j x b r , r x 彳；+ + d c , ) j ia 玎r x x j + + 吐c , 1 j 三。，z = ，2 ，g 这样，二阶锥规划问题就转化为半定规划问题，二阶锥规划是半定规划的特殊 情况。因此，半定规划是比线性规划，二阶锥规划更为一般的最优化问题。 在二阶锥规划的原问题f 1 1 0 1 和对偶问题( 1 1 1 ) 中，令 第一章绪论 9 c l c 2 ： 一 白 一 x 2 ： x q j l s 2 ： s q ，a = 【4 4 4 】，rk = k xk ： 其中墨，憋，k 是问题( 1 - 1 0 ) 中的二阶锥，x e k 即为x = h 而】r ，其中 一k ，f = 1 ，g 。则( 1 1 0 ) 和( 1 11 ) 分别可写成如下形式 m i n c r x s 2 a x = 6 ，x k 和 m a x b 7 y s l 。a t y + s = c ，s k 凸规划( c o n v e xp r o g r a m m i n g ) 是指目标函数是凸函数，可行域是凸集的优化 问题。凸规划是非常重要的数学优化问题，凸规划之所以得到人们的关注主要原 因有：( 1 ) 凸函数有很好的性质，如一个凸函数没有不为全局极小的局部极小值， 一个非凸函数可以被“凸化的 同时保持全局极小值的最优性；( 2 ) 凸集有很好的 性质，如一个凸集有非空的相对内部，凸集在任何点具有可行方向；( 3 ) w 0 1 f e 对 偶定理等重要结论成立。在实数域上存在三种常见的锥：尺”上非负的实欧几里得 空间群，洛仑兹( 或二阶) 锥，及半正定锥掣。以上三种凸锥都满足内部非空， 自对偶，是对称闭集，具有梯度和h e s s e 阵容易计算的自和谐障碍函数。在这三种 凸锥上分别定义了线性规划、二阶锥规划以及半定规划问题。这些锥的自对偶性 确保了原对偶问题的完全对称性，即原对偶问题可以具有相同的形式。半定规划 是一个非光滑的凸规划问题。而二阶锥规划问题是凸规划问题中另一个重要的分 支。因此，线性规划、二阶锥规划、半定规划都是凸规划。 二阶锥规划在实际问题中有着广泛的应用，如：雷达方针权的设计，捆绑设 计，服务点设置等问题。因此二阶锥规划是人们研究的新的热点。 下面考虑凸二次规划和二阶锥规划的关系。 考虑如下凸二次规划问题 m i n f ( x ) = x 。h x + 2 p 。x ，”、 s j a x 6 l 1 1 ) j 其中h 是正定矩阵。我们可以把h 写成日= h r 2 日啦，并令芦= h 一聊p ，则 问题的目标函数为f ( x ) = l i 啦x + 剖- p r h p ，由于p7 h _ p 是一个常数，故最小 化f ( x ) 就等价于最小化0 日啦工+ 剖，因此问题( 1 1 3 ) 等价于 1 0半定规划的外梯度法研究 令舅：h l x j b = r a i n 6 叫1 日v 2 x + 剖6 a x b ，曰= 【oh v 2 j ， - - 0 彳】 则该问题变成了 m i n 占7 舅 s ，忙+ 水识 盈b 这正是一个s o c p 问题。因此，s o c p 问题包含了凸q p 问题。 1 3 4 特征值优化问题 设对称矩阵钺x ) 是x r 。的仿射函数，即4 ( 力= 4 0 + x z a l + + 砟4 。其中 4 s ”，扛0 ，l ，七? 彳 ) 的最大特征值的最小化问题等价于 r a i n k ( 彳( x ) ) ( 1 1 4 ) j 因为彳( 力对称，所以存在正交阵u ，使得 f k 钺加u l -kr 弓i 入变量，贝u ，一么c x ，= u 一a ，一九血 u r 若f = k ，则玎一彳( x ) 兰0 。故问题r a ，i n ；t m ( a ( x ) ) 为 定义扩充的变量叠= 匀，则特征值优化问题c 一，4 ，转化为如- f s d p 问题： 第一章绪论 m i n 占r 舅 s t e ( i ) 兰0 其中弓= 【l ，o ，o l ，且e ( 舅) = t 一彳( x ) 。这正是半定规划( 1 3 ) 的形式。 设对称矩阵么( x ) 是x r 的仿射函数，即么o ) = 4 + 一4 + + 坼4 。其中 a i s ”，i = 0 , i ，k 。令m ( x ) = 彳( x ) 7 1 a ( x ) ，由于彳( x ) s ”，贝0 ，( x ) 三o ，a ( x ) 的2 - 范数为m ( x ) 的最大特征值的平方根，即恤( x ) 0 ：= 毪( m ( x ) ) 。在实际问题中，尤 其是控制论或系统论中，常要求优化问题哑n 归 ) 1 1 ：，即 m i n m a x 2 ( 彳r ( x ) 么( x ) )( 1 1 5 ) 等价于解 m i n t s j f 2 ，一a ，( 工) 彳( x ) 至o 即问题( 1 1 5 ) 等价于如下半定规划问题： m i n t 姐i ，t 以i _ o 盯k x ) 二。i 三? 特征值优化问题在控制论、结构优化、组合优化、图论 6 3 1 等领域有广泛的应 用。 1 3 5 多项式最优化 多项式最优化( p o l y n o m i a lo p t i m i z a t i o np r o b l e m s ) 问题是指目标函数和约束条件 都是多项式的最优化问题。多项式最优化问题分为无约束和约束多项式最优化问 题。 无约束多项式规划的标准形式为： m i n p ( x ) x e r “ 其中p ( x ) 为多项式。 约束多项式规划的标准形式为： m 斌i n p ( x ) k = & r ”：红( x ) o ，( x ) o 1 2 半定规划的外梯度法研究 显然，线性规划和凸二次规划是多项式优化问题。而在1 3 3 节中说明了二阶 锥规划问题可以转化为半定规划问题。半定规划问题( 1 3 ) 的目标函数是多项式( 线 性函数) ，约束条件是f ( x ) = f o + 一e + + e 兰o 。实对称阵f ( x ) 半正定的充要条 件是f ( x ) 的一切主子式非负，而该条件正是关于x 的多项式。因此，半定规划问 题是多项式最优化问题。多项式优化问题是一类很广泛的问题，它包含了线性规 划，凸二次规划，二阶锥规划，半正定规划问题。而半定规划是一个非光滑的凸 规划问题。我们知道凸规划有很好的性质，如局部最优解就是全局最优解，这就 意味着任何一个能找到局部最优解的算法就能够得到全局最优解。对于凸规划的 问题，已经存在能找到全局最优解的算法。多项式优化是一类特殊的全局优化问 题，很多源于控制理论、信号处理、计算机模拟等领域的问题都可以归结为多项 式优化问题。在实际问题中，除了凸规划问题之外，还有大量的非凸规划问题。 非凸规划问题的难度无论是理论上还是实际上都远远高于凸规划问题。多项式优 化是一个n p 难问题。多项式优化就包含了许多非凸规划问题。 如下问题就是多项式规划问题，但由于它的可行域不是凸集，所以它不是凸 规划。 m i n x i 一2 x 2 s 1 一o ，x 2 0 ( _ - 1 ) 2 + x ；1 ( 一一1 ) 2 + ( x 2 - 1 ) 2 1 综上所述，我们研究清楚了一些优化问题间的关系，它们的关系如下图所示。 图1 - 1 第一章绪论 1 3 1 4 半定规划的算法和研究现状 1 4 1 半定规划的算法综述 由于半定规划是非光滑的凸规划，因此求解半定规划的方法很多，最成功的 方法是利用半定规划的最优性条件得到的内点算法，内点算法是求解中、小规模 半定规划问题非常有效的算法。最初n e s t e r o v 和n e m i r o v s k i t 4 j 及a l i z a d e h t 5 i 分别把 线性规划的内点法推广到半定规划内点算法，随后a l i z a d e h 证明了大多数线性规 划的内点算法都可以推广到半定规划上。内点算法的基本思想是把约束优化问题 转化为无约束优化问题。这种转化常用的方法就是在目标函数中加一个罚项，罚 项在可行域内值非常小，但是接近可行域边界时，罚项变得非常大，使迭代点列 总在可行域内。内点法从下降方式来分主要有：路径跟踪法、势下降法等；从其 处理的规划来分有：原始内点法、对偶调比内点法和原对偶内点法。现在已经有 了内点算法的通用软件包，在许多领域得到广泛应用。内点法之所以备受人们关 注是因为：首先在理论上内点法非常高效，其次在实践中内点法也是高效的，另 外内点法可以有效的利用问题的结构( 譬如稀疏结构和工程技术领域中产生的 t o e p l i t z 结构等) 。但内点算法在求解较大规模问题时，由于内存要求过大、单步 执行时间过长等缺点，不能有效的求解大规模问题。近年来，一些求解大规模半 定规划问题的算法涌现出来，其中包括h e l m b e r g 和r e n d l l l 7 】提出的谱丛算法和 b u r e r f l 8 1 9 】提出的一阶非线性规划方法。 由h e l m b e r g 和r e n d l l l 7 】提出的谱丛算法把半定规划等价为一个特征值优化问 题。而特征值优化问题是一个非光滑的凸规划问题，然后利用非光滑规划的向量 丛算法进行求解。与内点法不同的是向量丛算法利用了次梯度信息，是一阶算法， 类似于最速下降法具有算法开始收敛快的特点。实验证明该方法在精度要求不是 特别高时是求解大规模问题的有效方法。 b u r e r ，m o n t e i r o 和z h a n g 1 8 , 1 9 1 基于矩阵分解把半定规划问题转化为光滑非凸 的约束优化问题来处理，这样转化的优点是把非光滑优化问题转化为光滑优化问 题，进而可利用经典的最优化方法解决。缺点是把凸优化问题转化为非凸优化问 题，尽管目标函数和约束是非凸的，但其全局收敛性可以证明，而且可以得到很 好的数值结果。 1 4 2 研究现状 人们从提出半定规划问题到在理论和实际应用中完善半定规划的算法经历了 几十年的时间。半定规划的提出。最早可以追溯到1 9 6 3 年，r b e l l m a n 和k f a n 1 2 1 1 4半定规划的外梯度法研究 首次提出了一个半定规划问题。在半定规划的内点算法被提出之前，半定规划经 历了相对缓慢的发展时期。众多学者寻求半定规划在理论上有效、实际上切实可 行的算法。理论上取得突破性进展的是n e s t e r o v ，n e m i r o v s k i l 4 l 基于自和谐罚函数 理论得出半定规划问题存在多项式时间的内点算法。在实际计算上a l i z a d e h l 6 】把著 名的k a r m a r k a r 的内点算法推广到半定规划上，取得较好的结果。y i n y uy er 2 0 1 证 明了绝大多数线性规划内点算法几乎可以不变的推广到半定规划。目前内点算法 在理论上非常成熟，是求解中、小半定规划问题常用的算法。 然而实际中问题往往是大规模的，变量和约束个数常达到成千上万个。一般 而言，大部分内点算法都是原始对偶方法。但对于大规模问题，这种方法由于利 用了牛顿法而限制了算法的性能。牛顿法每步迭代需要一个大规模的、稠密的线 性方程组的求解，这需要大的内存以及急剧增加的计算量。即使利用矩阵的稀疏 性，在实际应用中这种算法的局限性还是存在的。如何解决这些局限，许多学者 做了重要研究。如采用c h o l e s k y 分解，低阶分解1 1 9 1 ，预处理的共轭梯度法【2 ，梯 度残量算法1 2 2 1 等等，这些算法在一定程度上可以求解大规模半定规划问题，但是 求解的精度不高，不能解决精度要求高的问题。b e n s o n l 2 3 l 提出的势下降内点法可 以充分利用某些组合优化问题的半定规划松弛模型的特殊结构，从而解决矩阵维 数达上千的大规模问题。m i t u h i r of u k u d a l 2 4 1 提出了拉格朗日对偶预估校正内点法， 数值实验表明该算法在求解一类大规模的半定规划问题时可以得到较高精度的最 优解。随后，出现了把大规模半定规划问题转化为非线性规划的几种有效方法 1 1 7 , 2 5 - 2 7 。这些方法的一个共同特点是基于梯度信息，从而避免了运算量大的线性 搜索和矩阵运算。 9 0 年代中期开始，半定规划的不可行内点法逐渐产生1 2 8 - 3 0 1 。在此之前的内点 算法都是可行内点算法。可行内点算法要求其生成点列在可行域内部，也就是首 先要求给出一个严格可行的初始点。在求解大规模问题时，这一步的工作量是巨 大的。 9 0 年代末，半定规划又被推广到非线性半定规划问题 3 1 - 3 4 1 ，即线性或非线性 目标函数受到非线性矩阵不等式和( 或) 向量不等式约束的优化问题。它主要来 自于最优结构设计，最优鲁棒控制等实际问题。g r a n ad r u m m o n d l 3 3 1 研究了非线性 半定规划的中心路径。b u r e r ，m o n t e i o r , 及z h a n g t l 9 】把半定规划的对偶问题作为光滑 非凸的无约束问题来讨论，实际上这种算法也可以推广到非线性半定规划中。目 前为止，诸多学者对非线性半定规划的理论和算法已经有了一定的研究。 第一章绪论 1 5 1 5 本文内容及安排 本文首先较为系统的研究了一些重要的最优化问题间的关系，其次对半定规 划问题进行有效的变换，把求解半定规划问题转化为求解变分不等式问题，再给 出一个改进的求解变分不等式问题的外梯度法，从而得到半定规划问题的最优解。 具体内容安排如下： 第一章简单介绍了半定规划的研究背景和对偶理论。较为系统的研究了线性 规划，凸二次规划，线性半定规划，二阶锥规划，多项式最优化间的关系，说明 许多实际问题都与半定规划有着密切的联系。并概述了半定规划的主要算法及其 研究现状。 第二章在满足严格可行性条件时，将线性半定规划和二次半定规划问题的最 优性条件等价为变分不等式问题。说明对半定规划问题的求解可以转化为对变分 不等式问题的求解。 第三章在已有的变分不等式的一般外梯度法中，通过改进的校正步步长提出 了改进的算法。给出了新算法收敛性的证明，并通过数值实验说明该算法是求解 半定规划的有效算法。 第二章变分不等式及半定规划问题 1 7 第二章变分不等式及半定规划问题 2 1 引言 变分不等式是由p h a r t m a n ，c t s t a m p a c c h i a 3 6 】和j l l i o n s 等在2 0 世纪6 0 年 代中期提出的类问题，它是由于研究偏微分方程的边界值问题和最优控制问题 而被提出的。互补问题是由r w c o t t l e 几乎在同时期提出的。早期变分不等式是 在无穷维空间内迸行研究。如果在欧式空间的有尖点的闭凸锥中考虑这两类问题， 则互补问题的解与变分不等式问题的解是等价的。 变分不等式问题的数值解法一直备受诸多学者的关注。针对单调变分不等式， g o l d s t e i n l e v i t i n p o l