（应用数学专业论文）半定规划的光滑化方法研究.pdf

摘要 半定规划是线性规划的一种推广。近年来其理论和算法取得了很大的进展， 并且在组合优化、系统工程和电子工程等领域得到了广泛的应用，已经成为数学 规划领域中一个非常活跃的研究方向。 本文首先介绍了半定规划的理论、算法、研究现状和意义，然后引入了求解 半定规划问题的非内点光滑化方法。本文的主要工作包括以下三个方面： 1 利用光滑熵函数对半定规划的最优性条件进行转化，得到与其等价的光滑 方程组，并应用牛顿法求解该方程组，从而构造了求解半定规划问题的一种光滑 化方法。对算法的可行性和收敛性进行了理论分析，并通过数值实验验证了算法 的有效性。 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 g ( s d p ) i 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 t y e a r s ，t h et h e o r ya n da l g o r i t h mf o rs d ph a v ed e v e l o p e dg r e a t l y , a n di t s n u m e r o u s a p p l i c a t i o n sa l 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 me n g i n e e r i n ga n de l e c t r i c a l e n g i n e e r i n g s d pi sav e r yi 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 i s p a p e r , w ef i r s ts u m m a r i z et h et h e o r y , a l g o r i t h m , r e s e a r c h s l a t ea n d s i g n i f i c a n c eo fs d rt h e n ，an o n i n t e r i o rs m o o t h i n gm e t h o di sp r o p o s e df o rs o l v i n gt h e s d p p r o b l e m s t h em a i nw o r ki n c l u d e st h ef o l l o w i n gt h r e ea s p e c t s ： 1 t h ee q u i v a l e n ts m o o t h i n ge q u a t i o n so ft h eo p t i m a lc o n d i t i o na r eo b t a i n e db y e x p l o i t i n gt h es m o o t h i n ge n t r o p yf u n c t i o n a p p l y i n gn e w t o n sm e t h o dt os o l v et h e e q u a t i o n s ，as m o o t h i n gm e t h o df o rt h es o l u t i o no fs d p i sd e r i v e d t h ef e a s i b i l i t ya n d c o n v e r g e n c eo f t h ea l g o r i t h m a r ea n a l y z e dt h e o r e t i c a l l y s o m en u m e r i c a lr e s u l t sa r ea l s o i n c l u d e dw h i c hi n d i c a t et h a tt h ep r o p o s e dm e t h o di se f f i c i e n t 2 b yr e g a r d i n gt h es m o o t h i n gp a r a m e t e ro ft h es m o o t h i n ge n t r o p yf u n c t i o na sa i n d e p e n d e n tv a r i a b l e ，an e wa l g o r i t h mi sp r o p o s e d t h em e t h o di ss h o w n t ob eg l o b a l l y a n d l o c a l l ys u p e r l i n e a r l yc o n v e r g e n t u n d e rs u i t a b l e a s s u m p t i o n s n u m e r i c a l e x p e r i m e n t ss h o wt h a tt h em e t h o d i se f f i c i e n t 3 t h r o u g hi m p r o v i n gt h eu p d a t em e t h o d so fi t e r a t i v ep o i n t sa n dp a r a m e t e r s ，t h e n u m b e ro fs o l v i n gl i n e a re q u a t i o n si sr e d u c e da n dah e wm e t h o df o rs o l v i n gs d p p r o b l e m si sd e r i v e d t h e o r e t i c a la n a l y s i sa n d n u m e r i c a lr e s u l t sa r ei n c l u d e dw h i c hs h o w t h a tt h em e t h o di sv e r yp r o m i s i n ga n dc o m p a r a b l et os e v e r a lc o r r e l a t i v em e t h o d s k e y w o r d ：s e m i d e f i n i t ep r o g r a m m i n g e n t r o p yf u n c t i o n n e w t o n sm e t h o d s m o o t h i n gm e t h o d c o n v e r g e n c e 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：适2 蜇日期：2 q g ：! ：21 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业离 校后结合学位论文研究课题再撰写的文章一律署名为西安电子科技大学。( 保密的 论文在解密后遵守此规定) 导师签名：趟( 丛 第一章绪论 第一章绪论 本章主要介绍了半定规划( s d p ) 的基本知识。首先阐述了半定规划的基本理 论和算法，接着简述了半定规划的研究现状和意义，最后列出了本文的内容提要 和章节安排。 1 1 引言 数学规划讨论决策问题的最佳选择之特性，包括创建数学模型、设计最佳计 算方法、研究这些算法的理论性质及其在设计应用中的实现情况等。上世纪4 0 年 代，随着运筹学产生、发展和壮大，数学规划的领域不断扩大，新问题的出现使 已有的线性规划和非线性规划的算法无能为力，而半定规划的产生为解决这些问 题提供了新的方法和思路。1 9 6 3 年，b e l m a n 和f a n t ”第一次构造了一个半定规划 问题，接着苏联的一些学者相继研究了半定规划( 当时也叫矩阵不等式) 在控制 领域中的应用【2 】。在7 0 年代早期，d o n a t h 和h o f f m a n l 3 1 、c u l l u m ，d o n a t h 和w o l f e 4 把一些比较困难的图分割问题转化成为一个特征值优化问题求解。1 9 7 9 年l o v a s z 例 通过求解半定规划得到图的s h a n n o n 容量的上界，从而解决了长期以来的一个公 开猜想，并引发了c r r o t s h c h e l 、l o v a s z 、s c h r i j v e ： 7 】等人研究求解完美图的最大独 立集等组合优化问题的多项式时间算法的热潮。s h o r e ”提出了组合优化问题的半定 规划松弛模型，标志着半定规划真正成为解决组合优化问题的重要工具之一。在 对这些实际问题的求解过程中半定规划的理论和算法得到了一定的发展，并且其 解的存在性、最优性条件、逆问题、灵敏度分析等方面的研究也取得了一系列的 成果，使得半定规划成为解决数学规划问题的基本工具。1 9 8 8 年，n e s t e r o v 和 n e m i r o v s k i g a 0 l 在理论上证明了k a r m a r k a ：1 1 】提出的线性规划的内点算法可以推广 到半定规划中，使得半定规划得到飞速发展。此外，半定规划在系统控制理论【1 2 1 、 结构优化、特征值优化、组合优化、滤波器设计【1 3 】和移动通信【1 4 】等领域的广泛应 用使它成为数学规划领域日益引人注目的研究方向。 半定规划可分为线性半定规划和非线性半定规划两类。由于非线性半定规划 的应用目前远不如线性半定规划广泛，而且其理论和算法都很不成熟，所以对它 的研究很少。本文主要讨论求解线性半定规划的算法，如无特殊注明，本文中所 涉及的半定规划问题均为线性半定规划问题。 半定规划的光滑化方法研究 1 2 半定规划及其基本算法 1 2 1 半定规划及其对偶理论 半定规划是定义在半正定矩阵锥上的线性规划，它的一些理论相似于线性规 划，线性规划的一些算法也可以类推到半定规划上。但是，它们之间的最大区别 在于：半定规划的对偶理论比较弱；线性规划的单纯形方法不适用于半定规划， 因为半定规划的可行域不再是多面体；一些不能转化为线性规划模型的问题可以 转化为半定规划。 与标准的线性规划相比，半定规划将变量x r ：用半正定矩阵x 甲代替。 半定规划是在满足约束“对称矩阵的仿射组合半正定”条件下使线性函数极大( 极 小) 化的问题，这个约束是非光滑的、凸的，因而半定规划是一个非光滑的凸优 化问题。 半定规划问题的标准形式如下： r a i nc - x ( p ) ： s 1 4 x = 岛( f = l ，砌 ( 1 - 1 ) x 三0 利用l a g r a n g e 方法可得到其对偶规划为： m a x b r y ( d ) ： s j ：1 y , 4 + s = c ( 1 - 2 ) s 乏0 这里的向量b r ”，矩阵c s 及4 ”0 = l ，m ) 为已知的；而x 霹”和 ( y ，s ) r ”s y 分别为原问题和对偶问题的变量。 半定规划是线性规划的推广，因此它有与线性规划相似的对偶理论。我们首 先给出两个引理及对偶间隙的定义。 弓i 理1 2 1 3 a s 设4 ，b s “”且4 三o ，b 三0 ，则4 b 0 。 引理1 2 2 3 ，1 5 1 设a ，b s 4 ”且爿三0 ，b 0 ，则爿b = 0 当且仅当4 b = 0 。 定义1 2 3 设工和( y ，s ) 分别为( p ) 和( d ) 的可行解，则称c x b 7 y 的值 为原规划和对偶规划在( z ，y ，s ) 处的对偶间隙。 为书写方便，可将半定规划原问题及其对偶问题表示为如下形式： m i nc x j j a z = b( 1 3 ) x 卜0 第一章绪论 3 及 m a x b r y j ，a 7 y + s = c ( 1 - 4 ) s 三0 其中，b = ( 岛，b 2 ，吒) 7 ，a ：s 卜r ”为线性算子，定义为 肷= 4 x 以z 厶_ = | 记a 的伴随算子为a 7 ：r ”卜s 1 3 1 ，根据伴随算子的定义，应满足对任意的 x s ，y e r ”有( a r ，y ) = ( z ，a 7 y ) 。事实上 ( a | j ，y ) = ：。咒z ，( 4 r ) = 2 ，( z ：。乃4 ) = ( x ，a 7 y ) 故有( 艄，) ，) = ( j ，y ) 。 下面给出半定规划的对偶定理。 定理1 2 。4 1 3 , 1 5 ( 弱对偶定理) 设z 和( y ，研分别为( p ) 和( d ) 的可行解，则 有 c j b 7 j ，= j s 0 即可行解处的对偶间隙是非负的。 证明：由半定规划原规划及其对偶规划的等价形式( i - 3 ) 和( i - 4 ) 知 c x b o = ( a 7 y + s ，x ) 一( a 石，y ) = ( s ，z ) = x s 故由引理1 2 1 及三0 ，s 艺0 可得，x s 0 ，即c x b 7 y = x s 0 ，证毕。 令p 和d + 分别表示原规划( p ) 及其对偶规划( d ) 的最优解，即 p ：= 够 c j 1 4 x = 6 f o = 1 ，哟，x 兰o = 溜p 7 yj 二。m 4 + s _ c ，s 兰o 由定理1 2 4 可知p d 。设，和d 分别为( p ) 和( d ) 的最优解的集合，即 p 等 z f c z = p + ，4 z = 包( f = l ，研) ，x 兰o d ：= ( 弘s ) f 6 7 y = d + ，三。咒4 + s = c ，s 至o ) 易见，即使p 或d 是有限的，p + 或d + 也可能是空集。 记对偶间隙为，即 4 半定规划的光滑化方法研究 f ：c xb 。y xs( x ，s ) 如果= 0 ，则z 、s 分别为原规划( p ) 与对偶规划( d ) 的最优解；但与线性规 划不同的是，由z 、s 分别为( p ) 和( d ) 的最优解不一定能推出= 0 ( 参见文 献 2 ，3 ，1 5 】) 。下面我们将引入严格可行解的概念。 定义1 2 5 若x ( 或( _ y ，$ ) 为( p ) ( 或( d ) ) 的可行解，且z 0 ( 或s - 0 ) ， 则称x ( 或( y ，s ) ) 为( p ) ( 或( d ) ) 的严格可行解。如果( p ) ( 或( d ) ) 存在 严格可行解，则称( p ) ( 或( d ) ) 具有严格可行性。 定理1 2 6 ( 强对偶定理) 设 ( 1 ) 半定规划的原问题( p ) 存在严格可行解； ( 2 ) 半定规划的对偶问题( d ) 存在严格可行解； 则有下面的结论成立： ( 1 ) 如果上面的条件中至少有一个成立，则p + = d + ； ( 2 ) 如果上面两个条件都成立，则p = d + 且，和d 均非空。 此定理的证明可参见n e s t e r o v 和n e m i r o v s k i 的文献 1 0 】。严格可行性条件也 称为s l a t e r 型约束规范，它是保证凸优化问题强对偶成立的一个充分条件。为了去 掉严格可行性条件，使强对偶定理在较弱的条件下成立，m v r a m a n a 1 6 和l t u n c e l 17 】分别通过不同的途径构造了不要求严格可行性的对偶理论，他们的结果虽 然有重要的理论意义，但形式很复杂，对半定规划的求解并没有太大的用处，还 未得到广泛的应用，因此我们不做讨论。 假设( p ) 和( d ) 都存在严格的可行解，则可保证至少存在一对原始一对偶最 优解，即最优解集合，和d 均非空，从而就存在可行解z 和( j ，s ) 使得 c x = b t y = p + = d + ，= ( x ，s ) = 0 。由引理1 2 2 知船= 0 。我们称船= 0 为 互补松弛条件，它可以看成是线性规划互补松弛条件的推广。 综上所述，我们可以得到半定规划的最优性条件1 3 】： 假设( p ) 和( d ) 均存在严格可行解，则下述各命题等价： ( i ) ( p ) 有最优解： ( i i ) ( d ) 有最优解( y ，s ) ； ( i i i ) 最优性条件 4 x = 岛( f = 1 ，所) ，x 兰0 三。y a + s = c ，s - _ o ( 1 5 ) 爿s = 0 有解( ，y + ，s + ) 。这就是半定规划的k k t 条件。 第一章绪论 1 2 2 半定规划的内点算法 求解半定规划的方法有很多，可以根据其可行解集的结构构造半定规划的多 项式时间算法，如椭圆方法，但椭圆方法的实际运算效果很差1 8 j 。后来将线性规 划的内点法引入半定规划，其理论和算法都比较完善，使得内点算法成为求解中 小规模半定规划问题的非常有效的方法。现已有内点算法的通用软件包1 9 删，在 很多领域中得到了广泛的应用。近些年又发展起来一些新的算法，最常见的有光 滑化的谱丛方法、基于梯度信息的非线性规划方法、割平面法以及光滑化方法。 本节我们着重介绍内点算法。 九十年代初期，n e s t e r o v 和n e m i r o v s k i l l 0 1 、a l i z a d e h 2 1 1 首次将线性规划的内点 法扩展到半定规划；然后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 在文献 1 0 】中利用自协调罚函数的定义给 出了用内点算法求解锥规划的更完善的理论，证明了半定规划存在多项式时间算 法。 内点法从其下降方式来分主要有：路径跟踪算法、势下降算法等；从其处理 的规划来分有：原始内点算法、对偶内点算法和原始对偶内点算法。内点法，顾 名思义就是要求迭代过程要始终保持在可行域内部进行，并且初始点也要在可行 域内部选取。它的基本思想是把约束问题转化为无约束问题。这种转化的常用方 法是在目标函数中加入一个罚项，罚项在可行域内的值非常小，但接近可行域边 界时，罚项变得非常大，从而使迭代点列总在可行域内。 下面介绍半定规划的原始对偶路径跟踪内点算法。 我们在( 1 - 1 ) 的目标函数中加入罚函数一# l o g d e t ( 幻，其中肛 0 是罚因子。 考虑罚问题 m i n c x - # l o g d e t ( x ) j j 4 x = 6 f ( f = 1 ，研)( 1 - 6 ) _ i - 0 不失一般性，不妨假设( 1 - 6 ) 存在严格原始一对偶可行解( z 0 ，y os o ) 。因为上述罚 问题的目标函数是严格凸的，并且对任意的d r ，集合 z 兰o f 4 z = 岛( f = l ，晰) ，c x = d ) 是有界闭集，所以罚问题( 1 - 6 ) 的最优解存 在且唯一【3 】。易知( 1 - 6 ) 的最优解一定存在于半正定锥的内部。 通过引入参数“ 0 ，对最优性条件( 1 - 5 ) 进行扰动，可得 4 x = 龟( f = 1 ，所) ，x - 0 三，只4 + s = c ，s o ( 1 7 ) x s = u i 半定规划的光滑化方法研究 即为( 1 - 6 ) 的k k t 条件。其中第一个条件是原问题( 1 - 1 ) 的严格可行解的条件； 第二个条件是对偶问题( 1 - 2 ) 的严格可行解的条件；第三个条件当“一0 时相应 于互补松弛条件x s = 0 。条件( 1 - 7 ) 不仅是( 1 - 6 ) 的必要条件，而且是其充分条 件。 对于固定的p ，( 1 7 ) 存在唯一的解( ，瓯) 。和瓯分别为原问题( 1 - 1 ) 和对偶问题( 1 - 2 ) 的一个可行解，且其对偶间隙为月p 。当p 0 时，由( 1 - 7 ) 的 解( 4 ，瓯) 构成的曲线称为中心路径口3 1 ，这是一条光滑曲线。下面的我们将证明： 当, u - - ，0 时，( 以，瓯) 存在聚点，且若( f ，s ) 是( x ，瓯) 的聚点，那么f 、分 别为原问题( 1 - 1 ) 和对偶问题( 1 - 2 ) 的最优解。 弓i 理1 2 7 3 1 令彳，b e s ：”，则) ( 彳) k ( 功( 彳，召) ，l a 。( 4 ) a 一( 功。 引理1 2 8 刚令z ，z ”e x s ”“睹= 岛o = 1 ，脚) ) 及s 7 ，s ”i s i s = c 一：。咒4 ，y r ”，贝u ( x - x ”，s 7 一s ”) = o 。 定理1 2 9 脚对给定的序列 地) 满足心 0 ，且当七一+ o o 时有心- - - ，- 0 ，则当 地一。时，( k ，) 必存在聚点。若设( z + ，s ) 为( k ，瓯) 的聚点，那么和 分别为原闯题( 1 - 1 ) 和对偶问题( 1 - 2 ) 的最优解。 证明：由引理1 2 8 知， o = ( z k z 。，瓯一s o ) = ( 爿i ，瓯) 一( 爿0 ，s 。) 一( z 。，瓯) + ( z 。，s 。) 因为( k ，瓯) = 疗地，故( ，s 。) + ( z 。，瓯) = 竹地十( x 。，s 。) 。由引理1 2 7 知 k ( ) k ( 气) + k 。) k ( ) + ( z 。，s 。) 由于k 。) 0 、k ( z 。) o ，根据引理1 2 7 知， & ，、( 瓯j 都是有界集， 从而序列( k ，) 必存在聚点。又由于( k ，& ) = 以以且当| j 一+ o o 时有以一o ， 故( z ，s + ) = o 。证毕。 为确定。和，需要求解下述非线性方程组2 朋1 ： 第一章绪论 4 x 一6 l ( f = 1 ，所) f a x ，y ，s ) = l ：。”4 + s - c x s u l = o( 1 8 ) 利用牛顿法求解方程组 乃( x ，y ，s ) + v 匕( z ，y ，s ) ( a x ，z x y , s ) 7 = 0 ( 1 - 9 ) 得到搜索方向( 彤，a s ) 。在这里对应求解下述线性系纠1 2 , 1 5 ： 4 r = 一( 4 x 一岛) ，( f = l ，埘) ：。锄4 + 丛= 一( 三。乃4 + s c ) ( 1 - 1 0 ) 厶蕊+ x s = 仙i 一烙 与解线性规划的内点法不同的是一般z 、s 是不可交换的，即船；s x 。这样解 ( 1 - 1 0 ) 虽然得到的s 是对称的，但a x 一般是不对称的，这不能满足下一步迭 代x + a x 对称的要求。采用不同的对称技巧可以克服这个困难，得到不同的原 始对偶搜索方向】，其中，软件中常用的有n t - 方向洲、h k m - 方向p 3 2 5 1 、a h o - 方向等。z l 珊g 【2 7 】引进了对称化算予，统一并推广了这三个方向。 利用上述不同的搜索方向就可以得到不同的内点算法，下面我们仅给出内点 算法的一般框架： 步骤0 给定初始可行点( j oy o ) 满足x o 卜0 ，卜o ，令k ：= 0 ； 步骤1 选择“； 步骤2 解方程组 f 幽1 v f a x ，y ，s ) i yl = 一以( z ，y ，回 【监j 得到搜索方向( ，矿，a s ) ，其中 4 x - b a i = 1 ，聊) f a x ，y ，s ) = i 三，只4 + s - c x s u i 步骤3 选择步长嘶( 0 ，1 ，使得z + 嘶卜0 ，s 。+ _ 0 ； 步骤4 - 令( x t m , y k + l , s ) = ( + a 女x 。，y + 嘶矿，s + ) 步骤5 如果( z 州，“) 0 ，使( 1 - 5 ) 变为如下形式( 即中心路径条件( 1 - 7 ) ) a ? x = b i ( j = k ，呻， ：。咒4 + s = c ， x 卜0 ，s - o ，x s = ( 1 7 ) 然后用牛顿法求解此中心路径条件。但是，用牛顿法求解的过程中，( 1 - 7 ) 中的非 负性要求并没有显式地包含在牛顿法所解的方程中，故迭代必须控制在 ? x r ”s = 的范围内，这不可避免地进一步限制了迭代步长。下面所介绍的方 法也是用牛顿法求解的，但在应用牛顿法之前，首先要将最优性条件或中心路径 条件改写为非线性等式系统。改写后的系统不包含任何显式的不等式约束x 三0 、 s 三0 或z 卜o 、s - 0 ，并且用牛顿法求解该系统时可以直接生成对称的搜索方向 而不需要进一步的转换。 2 2 1f i s c h e r - b u r m e i s t e r 函数 定义映射妒：r x r 卜r 为 烈岛6 ) # 口+ 6 一口2 十6 2 ( 2 1 ) 这个映射是由f i s c h e r l 4 5 1 首先提出的，一般称之为f i s c h e r - b u r m e i s t e r 函数。容易验 证它具有下述性质： 妒( 口，6 ) = 0 = 口o , b o ，a b = 0 ( 2 - 2 ) 将上述映射扩展到矩阵域，则可得映射砂：s s 卜s 妒( 盖，s ) # x + s 一( x 2 + s 2 ) ”2 ( 2 3 ) 可以验证映射妒有如下性质： 妒( x ，s ) = o = x 三o ，s 艺o ，j 墨= 0 ( 2 - 4 ) 下面给出上述性质的证明。 定理2 2 1 脚1 令妒是由( 2 3 ) 所定义的f i s c h e r - b u r m e i s t e r 函数，则 妒( 盖，研= o x 艺o ，s 三o ，裕= o 证明：首先假设x 兰o ，s - o ，x s = 0 成立，则有x s + s x = 0 。因此 ( x + s ) 2 = x 2 + 五嚣+ 盟+ s 2 = 2 + s 2 由于x ，s 是对称半正定的，而对称半正定矩阵的方根在对称半正定矩阵空间中是 唯一定义的，故有下面的结论成立 第二章基于f i s c h e r - b u r m e i s t e r 函数的光滑化方法 1 3 x + s ( x 2 + s 2 ) 1 7 2 显然就有妒( 石，回= 0 。 反之，假设对于两个对称矩阵z ，s e s ，妒( x ，回= o 成立，即 x + s = ( x 2 + s 2 ) 7 2 方程的两边同时平方，得 x 2 + s 2 = ( x + s ) 2 和工+ s 跹” 它就等价于 x s + 跗= o 和x + s 秽( 2 5 ) 将对称矩阵石进行谱分解x = d q ，其中q e 醒是正交矩阵， d = d i a g o h ，) ，则( 2 5 ) 式可以改写成 q r d q s + s q r d q = o 和q t d q + s s ? 如果在等式的两边左乘q ，右乘，即得 d q s q r + q s q 7 d = o 和d + q s q 7 铲 令a # 鲫，得 脚+ a d = 0 和d + a f( 2 6 ) 进一步的，对所有的f ，_ ，= 1 ，以，有 ( + ) = o 和d + a 掣” ( 2 7 ) 其中呀( f ，_ ，= l ，n ) 3 懈- a 的元素。特别地，当f = ，时，对所有的f = 1 ，刀有 2 = 0 和d + a 熨” 显然，对所有的待1 ，n 有 0 ，故彳是半正定矩阵。同理，利用s 的谱分解， 也可以得到s 的半正定性。 为了证明x s = 0 ，观察( 2 5 ) 可得 1 x s = r r x s = 妄乃 船+ s x 】- 0 二 由引理1 2 2 就可以得到x s = 0 。证毕。 下一小节将介绍光滑的f i s c h e r - b u r r n e i s t e r 函数。 半定规划的光滑化方法研究 2 2 2 光滑的f i s c h e r - b u r m e i s t e r 函数 首先引入参数p 。令p 0 为任意的非负数，定义：r x r r 为 ( 口，6 ) ；a + b 一a 2 + 6 2 + 2 肛2 称此函数为光滑的f i s c h e r - b u r m e i s t e r 函数h 7 】。对任意的p 0 ，上述函数显然是连 续可微的，并且有如下的性质： 眈( 口，b ) = 0 幸a o ，b 0 ，a b = 肛2 现在我们将光滑的f i s e h e r - b u r m e i s t e r 函数饥进行简单的推广：定义映射 丸：s x s 卜s 为 丸( z ，回譬x + s 一( x 2 + s 2 + 2 z 2 ，) ”2 ( 2 8 ) 则可以证明下述结论： 定理2 2 2 * s l 令p o 为任意的正数且丸由( 2 8 ) 定义，则有 丸( x ，s ) = 0 静x 卜o ，s o ，裕= p 2 1 证明：首先假设j - 0 ，s 卜0 ，x s = p 2 1 成立，则可以推出) i s s + s x = 2 1 2 i 。 因此， ( z + s ) 2 = x 2 + s 2 + 2 p 2 1 则有 x + s = 2 + s 2 + 2 p 2 “ 从而也就可得丸( z ，s ) = 0 。 反之，如果对于两个对称矩阵x ，s s 有丸，s ) = 0 ，即 x + s = ( x 2 + s 2 + 2 p 2 叫7 2 等式两边同时平方得 ( z + s ) 2 = x 2 + s 2 + 2 p 2 i 和x + s s 翟 等价于 x s + s x = 2 p 2 ，和x + s s ：” ( 2 9 ) 设对称矩阵x 的谱分解为= d q ，其中o r 是正交矩阵，且 d = d i a g ( ) 、l ，九) 。与定理2 2 1 的证明类似，记爿# g 堙7 ，则( 2 9 ) 可改写为 d a + a d = 2 1 2 2 门硇d + a s ：” ( 2 一l o ) 第二章基于f i s c h e r - b u r m e i s t e r 函数的光滑化方法 对所有的f ，j = 1 ，珂，用分量的形式写出，有 ( + ) 唧= 2 z 2 6 一d + a 殴” ( 2 - 1 1 ) 其中 。 磊鬣 特别地，当i = j 时，对所有的i = 1 ，玎有 2 气= 2 # 2 和 + a u 0 显然，对任意的i = 1 ，刀都有入 0 。因此对称矩阵x 是正定矩阵。同理对s 进行 谱分解也可得到s 的正定性。 为了证明璎= 弘2 j ，观察( 2 一i i ) ，基于前面的讨论可撂凡+ o ，故对任 意的i _ ，有= 0 。因此a 是一个对角矩阵，进而有d a = a d 。结合( 2 - 1 0 ) 可得 d a = p 2 ，。等式两边左乘矿，右乘q 可得p 2 1 = q r d a q = q 7 d o s = x s 。证毕。 2 2 3 改写中心路径条件 本小节的主要目标是给出半定规划的中心路径条件( 1 - 7 ) 的两种形式。这两 种表达式可通过现有的线性规划及其互补问题的表达式拓展得到。在改写中心路 径条件之前，首先考虑最优性条件( 1 - 5 ) 。 首先定义一个映射西：s r ”s 卜s r “” 4 x 一6 ( f = 1 ，m ) 西( z ，弘s ) 一l 二。y , 4 + s - c 妒( 石，s ) ( 2 1 2 ) 其中函数妒由( 2 - 3 ) 给出。可以看出，最优性条件( 1 - 5 ) 有解当且仅当西( z ，y ，研= 0 。 但是，我们注意到，浃射圣并不是处处可微的。为了克服这种不可微性，我们应 用推广至矩阵域的光滑的f i s c h e r - b u r m e i s t e r 函数来改写中心路径条件( 1 - 7 ) 。 令丸由( 2 8 ) 给出，则可定义映射圣，：s 删r ”x s 椰卜s x r x s 一 彳。x 一盔g = 1 ，m ) 圣，( z ，弘s ) ：= l 三。只4 + s 屯( x ，s ) c( 2 1 3 ) 半定规划的光滑化方法研究 由定理2 2 2 可以得到关于中心路径条件( 1 - 7 ) 的如下结论： 定理2 2 3 4 6 令圣。由( 2 1 3 ) 定义，其中丸由( 2 8 ) 给出且p 0 ，则下述 结论等价： ( i ) ( x ，y ，s ) 满足中心路径条件( 1 - 7 ) ： ( i i ) ( x ，y ，回为非线性系统方程组圣。( x ，y ，s ) = 0 的解。 根据文献【4 6 】的思想，下面我们将参数p 看作独立的变量，令 妒( x ，s ，# 屯( x ，s ) ，即光滑f i s e h e r - b u r m e i s t e r 函数可写为 庐( r ，s ，p ) # x + s 一( x 2 + s 2 + 2 p 2 ，) 1 彪 ( 2 1 4 ) 2 3 1 西的性质 2 3 算法描述及可行性分析 下面介绍毋的连续可微性，首先给出一个引理。 引理2 3 1 1 4 6 设已知矩阵一麟”，b 贮”，则有 0 彳“2 一曰1 胆i i ：l i 彳一圯4 ：- 1 1 4 一b 0 ： 定理2 3 2 1 4 6 1 设已知矩阵z ，s s 和p r + ，如果是由( 2 - 1 4 ) 定义的函 数且z 2 + s 2 + 2 _ f 正2 i 卜o ，则在( z ，最p ) 是连续可微的，且 v 4 , ( x ，s ，p ) ( u ，v ，丁) = u + v 一乓1 【y u + “y 十s 矿+ 飚+ 4 ，盯力 ( 2 1 5 ) 其中e = ( x 2 + s 2 + 2 p 2 d ”2 。 证明：令 ( x ，s ，p ) = 唬( x ，s ，p ) 一也( x ，s ，肛) 其中 破( x ，s ，p ) ：= + s 如( x ，s ，肛) ：= ( x 2 + s 2 + 2 肛2 d m 易知a 是可微的，且有 v 4 , ( x ，s ，p ) ( u ，v ，7 - ) = u + v 下面分析如的可微性。定义e - ( x 2 + s 2 + 2 z 2 ，) i “，假设e 是正定的。令 k i x ：= e x + x e ( 2 1 6 ) 第二章基于f i s c h e r - b u r m e i s t e r 函数的光滑化方法 1 7 表示相应的l y a p u n o v 算子，则e 的正定性保证了l y a p u n o v 方程 k i x 】= h 在对称矩阵集合中对每一个h s ”都有唯一的解( 参见文献 4 8 q h 定理2 2 3 ) 。 因此我们可以记k 的逆为l e - 1 ，即k - 1 日】表示满足e r + 船= 日的唯一元素x 。 进一步定义矩阵 d ：= ( ( 彳+ u ) 2 + ( s + 功2 + 2 ( 肛+ n 2 d ” 则可以通过简单的计算得到d 2 一e 2 = l t d 一司+ ( d e ) 2 。将岛一1 同时作用于等 式两边并移项可得 e - d = 三1 1 【( d e ) 2 一( d 2 一e 2 ) 】 = 历1 ( e d ) 2 一( y u + “y + s 矿+ 矿s + 4 # t i + u 2 + 矿2 + 2 r 2 d 】 又因为岛。1 是线性的，故 ( b 2 【x + u ，s + y ，p + 而一如0 x ，s ，幻一可( b 2 ( x ，s ， ，y ，n = 一v 如( ，s ，( u ，以7 - ) 一( 层一d ) = 一v 如( z ，s ，p ) ( u ，v ，r ) + 坯1 x g + u y + s 矿+ 厢+ 4 p 7 - 刀 + 上1 1 u 2 + y 2 + 2 r 2 刀一乓1 【( e d ) 2 】 ( 2 1 7 ) 由引理2 3 1 知 j l ( e d ) 2 k l e d 睡 s 铂0 e 2 一d 2 i i ； 仉l y u + u 矿+ s 矿+ 塔+ 4 p 7 - i + u 2 + y 2 + 2 ，州： = o ( 1 l l ( t j ，v ，圳2 ) 其中乃 0 是常数，且独立于u ，v 和7 - 。因此 陌陋一功2 玑= o ( 1 l l ( u ，矿，下) 1 1 1 2 ) 又由于 8 乓1 【( u 2 + 矿2 + 2 t 2 1 ) 1 f l ，= o - o 在( x ，s ，p ) 是连续的，由文献【5 0 】 可得v ( z s ，肋在( x ，s ，p ) 也是连续的。因此在( x ，s ，肋点是连续可微的，证毕。 2 3 2 算法描述 昭川洲= 黟7 ) 】 沼 v 。( k ，地l f a 肛w j 、= 一e ( 矿。，以) ( 2 - 2 。) 第二章基于f i s c h e r - b t t n n e i s t e r 函数的光滑化方法 1 9 的解，若眵( z + 幽k , s + a s k , o ) 忆= o ，停止； 否则，若眵( x + z k , s + 丛，以) 犯 舰，则令 i f , # ，鼠譬如，仇= 1 否则，计算仇= 西，这里s 是满足下述条件的自然数 眵( x + 舣k , s + a s k , 以) 肚砒，= o ，1 2 ，j 肛( z + 似k , s + a s k , + 1 地) 肚 陬“ 并置 反；仇地桫= 孑：笛嚣它 ( s 2 ) ( 校正步) 设( z x f f k , 反) = ( 弘，矿，分，趣) 是线性方程组 v e c 矿，觑， 会； = 一e c 旷。，忽，+ 曙一子，忽) c 2 2 ， 的解。令晚为l ，o t ：，吒2 ，。中满足下式的最大的数 ( p + 晚必，分+ 晚丛，反+ 晚反) 肚( 1 一毓) 纸( 2 - 2 2 ) 令形“1 = 矿。+ 晚矿，以+ l ；( 1 一纸) 反，k t - - - k + l ，返回( s 1 ) 。 我们看到在( s 1 ) ( s 2 ) 中要解由不同系数矩阵v o ( w ，弘) 构成的线性方程组， 这比内点法还要耗时，但通过简单的推论表明，对算法进行如下改进后，所有的 收敛性结果仍然成立：若预处理步通过仇 - 0 ( 见文献 4 6 】中引理6 1 ( c ) 的证明) ，故逆磋。存在，并且 第二章基于f i s c h e r - b u r m e i s t e r 函数的光滑化方法 2 l 五k 。岛一j z x x + z x s = 0 ( 2 2 7 ) 利用( 2 2 3 ) 和( 2 2 4 ) ，在方程( 2 2 7 ) 两边与x 作内积得到 o = 硅s 。如一z 脯】从一二a y 一一a , a x = 硅s 。乓“ 艏】战( 2 - 2 8 ) ；0 根据e 一彳卜0 和e s - 0 ，由引理2 3 4 ( i v ) 可得算子硅so 三e r 严格单调。所 以，由( 2 - 2 8 ) 立即得到a r t = 0 。根据( 2 2 7 ) 有a s = 0 。由矩阵4 的线性无关假 设和( 2 - 2 3 ) 式推出= 0 。证毕。 定理2 3 7 m 假设2 3 5 成立时算法2 3 3 是