（应用数学专业论文）半定规划及其在组合优化中的应用.pdf

摘要 阵定规划是线性规划的推广，许多凸规划问题都可以转化为半定规划半定 规划为研究这一系列凸规划问题并构造算法提供了统一的数学框架，而且半定规 划在控制理论、信号处理、特征值优化和组合优化等领域已获得成功的应用，因 此半定规划在近几年备受关注，矿一 首先，本文提出一种求解半定规划的占一次微分向量丛方法该方法根据次微分 理论与半定规划的强对偶定理，通过求解对偶问题得到原始问题的最优值数值实 验与理论分析均表明该算法适用于求解大规模问题，且具有良好的收敛性；其次， 研究了电路二等分问题本文先通过增加非线性约束得到原始问题的等价模型，进 而对等价模型利用提升技术，提出了一个强化的半定松弛模型；最后，将结果推 广到更具一般性的图的分割问题在利用l a g r a n g e 乘子理论得出原始问题的等价 形式之后，将近似算法与改进的坐标上升( 下降) 算法结合，求得原问题的次优 解 关键词：半定规s 次微分向量丛方；松弛二等分坐标上升算；，。 a b s t r a c t i ti s s i g n i f i c a n t l yi m p o r t a n t t od i s c u s ss e m i d e f l n i t e p r o g r a m m i n g i t s m o s t i m p o r t a n ta p p l i c a t i o n sa l ef o u n dw i t h i nm a n yf e l d s ；o n t h eo t h e r h a n d ，s e v e r a lc l a s s i c a l o p t i m i z a t i o np r o b l e m s c a nb ef o r m u l a t e da ss t a n d a r ds e m i d e f i n i t e p r o g r a m m i n g t h e r e f o r es e m i d e f i n i t ep r o g r a m m i n gp r o v i d e sau n i tf o r mt os t u d yt h e s ep r o b l e m sa n d c o n s t r u c ta l g o r i t h m s f i r s t l y , b a s e do nt h e s s u b d i f f e r e n t i a lt h e o r ya n ds t r o n gd u a l i t yo fs e m i d e f i n i t e p r o g r a m m i n g ，w ep r o p o s eo n e m e t h o dt os o l v es e m i d e f i n i t e p r o g r a m m i n g i nt h i s m e t h o d ，w eg e tt h eo p t i m a lv a l u eo fs e m i d e f i n i t ep r o g r a m m i n gb yf i n d i n gt h eo p t i m a l d e s c e n td i r e c t i o no fi t sd u a lp r o b l e m b o t ht h e o r e t i c a lp r o o fa n dn u m e r i c a le x p e r i m e n t s i n d i c a t et h a tt h i s a l g o r i t h m i s c o n v e r g e n t a n de f f e c t i v ef o r s o l v i n gl a r g e s c a l e s e m i d e f i n i t e p r o g r a m m i n g i n t h e f o l l o w i n gs e c t i o n ，w e w o r ko v e rt h eb i s e c t i o n p r o b l e m s b ya d d i n gn o n l i n e a rc o n s t r a i n t st o c i r c u i tb i s e c t i o n ，w eo f f e re q u i v a l e n t f o r m st o r e a d e r s e x e c u t i n gt h el i f t i n g m e t h o dt ot h e e q u i v a l e n tp r o g r a m m i n g ，w e p r e s e n t as t r e n g t h e n e ds e m i d e f i n i t er e l a x a t i o n a sp r e d i c t e d b yt h e o r ya n dc o n f i r m e db y n u m e r i c a le x p e r i m e n t st h et i g h ts e m i d e f i n i t er e l a x a t i o ng i v e sab e t t e rl o w e rb o u n do f c i r c u i tb i s e c t i o nt h a nt h eo n et h a tt h ep r e v i o u ss e m i d e f i n i t er e l a x a t i o ng i v e s t h e na s u b o p t i m a ls o l u t i o no f t h eg r a p hm a x i m u m e q u a l c u tp r o b l e mi sp r e s e n t e de m p l o y i n g t h er a n d o m i z e da l g o r i t h ma n dt h ei m p r o v e dc o o r d i n a t ea s c e n t ( d e s c e n 0a l g o r i t h mo n t h e o p t i m a l s o l u t i o no fs e m i d e f i n i t er e l a x a t i o n i t s i m p l e m e n t a t i o n s h o w st h a tt h e i m p r o v e d c o o r d i n a t ea s c e n t ( d e s c e n t ) a l g o r i t h mi sp r a c t i c a l 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 g s - s u b d i f f e r e n t i a lb u n d l er e l a x a t i o n b i s e c t i o na s c e n ta l g o r i t h m 第章绪论 第一章绪论 本章主要介绍半定规划的基本知识，首先介绍了半定规划的性质、 研究现状、研究意义以及半定规划的对偶理论；接着简述了半定规划的 应用背景；最后列出了本文的内容提要和章节安排 1 1 1 半定规划的形式 半定规划的标准形式如下 1 1 半定规划 l r a i n ( c 抑 5 上( 4 ，西= 6 ii = k , o r( 1 - 1 ) 1 x - 0 其中包( f = 1 ，m ) 为实数，当a 、b 均为n n 阶实矩阵时，( 爿，b ) = t r ( b 7 爿) = 冬 ；：1 a 口表示矩阵a 与b 的f r o b e n i u s 内积，对于n n 阶实对称矩阵x ， x 三o p0 ) 表示彳为半正定( 正定) 矩阵，c ，a 。( ，= 1 ，m ) 为疗 阶实矩阵不失 一般性，可以假设c ，a ，( f = l ，m ) 也是实对称矩阵，否则令c = ( c + c 7 ) 2 a ，= ( 爿，+ a r ) 1 2 即可 用r ”来代表m 维实向量空间，引入变量y r “，并记6 = ( 6 。，6 ：，b 。) 7 r ” 利用k t 条件可得半定规划( 1 1 ) 的对偶规划为 ( 1 2 ) 令s ”表示n n 实对称矩阵空间，进而口( s ：+ ) 表示s “中的半正定( 正定) 矩 c f f z+ 4 9 酗础 m 姐 西安电子科技大学硕士论文：半定规划及其在组合优化中的应用 阵集合同时定义算子爿：月z = 【 ， ， r ，其伴随算子 47 ：a7 y 2 ：= ，y ，a ，p = ( 1 ，1 ，1 ) 7 是全1 向量 有了以上的定义，半定规划及其对偶问题还可以表示成如下常见的形式： m i n ( c ，x )m a x b l ) s t a z = b ( p )s t 月7 y + z = c ( d p ) x 三0 y r ”z - o 假设原始问题( p ) 有可行解牙在( d p ) 的目标函数中，作代换 ( 6 ，y ) = ( 月牙，_ y ) = ( 牙，a7 y ) = ( 牙，c z ) 令n ( 爿) 代表4 的零空间，进而z 、z 所属的仿射空间分别用忙+ ( ) 和 c + n ( ) 1 来表示则原始对偶问题还可以表示为 min(cxstx kn 谚+ n ( a ) ) ( s ? n z +( ) j 。m 上a x ( z x 。, c 忱- z n ) c + n ( a ) - ) )s 上z l s ：n c +( ) 1 j 这表明，半定规划的对偶问题仍然是半定规划，关于原始问题的性质同样也适用 于对偶形式，二者在本质上是统一的 半定规划( 简称s d p ) 是线性规划( l p ) 的推广，它要求在满足约束“对称矩 阵的仿射组合半正定”的条件下使线性函数极小化不难看出，半定规划与线性 规划最本质的区别在于半定规划中用半正定矩阵锥取代线性规划中的非负象限 ，、1 半正定矩阵集合k = 江：z 霹 是闭凸锥，维数是n o + 1 ) ，且其边界是非线性 z 厂 一 的，例如当n = 2 时，x 可以表示成x = l 乏：，l ，其中，z ，_ ，z 满足不等式x 0 ， l 。，j y 0 ，x y z2 示意图参见图1 1 当z 在k 的边界时，z 奇异，当x 在k 的内部 时，z _ 0 因而，半定规划属于非线性凸规划范畴”5 1 。 半定规划与线性规划比较，具有以下相似与不同之处： 1 ) 对偶理论：半定规划的对偶理论在形式上与线性规划很类似，但是由于半 定规划是基于半定矩阵约束的线性函数极小化，而半定锥不是多面集合， 所以需要稍强一些的假设来保证强对偶定理成立，目前使用最多的是 s l a t c r 型约束规格“。7 1 ，例如原始问题与对偶形式均存在严格可行解，即存 在可行解x 和( 只z ) 满足z 卜0 ，z - 0 第一章绪论 2 ) 内点方法：许多求解线性规划的内点算法都可以推广到半定规划，并且在 实践中非常有效，这一重大发现主要归功于n e s t e r o v 、n e m i r o v s k i ”1 和 a l i z a d e h 0 1 ，前者深入分析了内点算法求解凸规划的机理：后者证明了许多 求解线性规划的内点算法都可以推广到半定规划虽然在线性规划中内点 法是否比单纯形法优越仍然是一个有争议的问题，但是在半定规划中内点 法的优越性是人们公认的，这是因为可行域的非线性使得单纯形法不适 用 z 图1 1 半正定矩阵锥k 示意 1 1 2 能表示为半定规划的几个实例 半定规划具有简单的表达形式和良好的分析性质，许多常见的优化问题如线 性规划、二次规划、特征值优化等等，都可以转化为半定规划的形式因此，半定 规划为研究不同形式的规划之间的共性并求解之提供了统一的方法，同时，相关 理论的发展又推动着半定规划的发展下面给出几个实例，它们都可以转化为半定 规划的形式，其中图g = ( 矿，e ) ，v 表示顶点集 l ，2 ，n ) ，e 代表图中相互连接的 边集，用e 。表示从顶点f 到顶点，的边w = 1 ) 表示相应的赋权矩阵( 若v ，v ，间 无边连接，记k = 0 ) 例1 1 特征值优化问题 设对称矩阵爿( x ) 是x r 的仿射函数，即彳( x ) = a o + x j a 。+ + x k a 女其中 ! 堕室皇三型垫盔堂堡主堕塞! 兰塞塑型墨苎垄塑鱼垡些塑壁旦 a i s 爿( x ) 最大特征值的最小化问题可以归结为如下半定规划 j m m 【s t t i 一4 ( x 垃。 其中t r ，x r k 这一问题在控制论、结构优化、组合优化、图论等领域有着广泛 的应用“” 与之有关的许多有趣问题都可以通过半定规划来求解，例如极小化彳( x ) 的前r 个最大特征值之和的问题可以转化为关于t r 、x r 、x s p 的半定规划问题 卜髫叫功卸 该问题的维数为：n = 2 p ，m = 1 + k + p ( p + 1 ) 2 这一结果也可推广到包括特征值 的绝对值、特征值的加权和等问题。1 如果我们要极小化矩阵a ( x ) = 4 + 工。a ，+ + 以4 r ”的范数，此问题可 f m i n t 卜t ，a 口( x 卜 其中x r ，t r ，这一问题的维数：n = p + q ，m = k + 1 给定图g = ( 矿，e ) 的顶点集v = 1 ，月 和每对顶点i 和_ ，间的非负权值 ，f ，= 则图的最大后一分割由下述的整数二次规划给出 m a x 群1 w o 。) 【 若令= l ( o i a g ( w e ) 一矽) ，x = w r ，则图的最大j i - 分割的半定规划松弛模型为： 第一章绪论 f m a x ( 厶x ) r 棼净 其中d i a g ( x ) 表示以x r “为对角元素，其它元素均是0 的矩阵，逆算子为d i a g ( x ) 它为解图的最大k 一分割提供了个上界与半定规划联系较紧密的组合优化还有 最大割问题、图的着色、顶点覆盖、o - 1 背包问题等等，它们均可以通过半定松弛 的方法求出一个松弛界限”“1 8 1 ，而且更强化的松弛模型也很快出现在相关文献中 ”1 关于半定松弛，作者在半定规划的应用背景中作了简要介绍 1 1 3 半定规划的研究现状与意义 历史上，人们曾经研究过比半定规划更一般的数学规划问题，如凸规划和锥 规划，而对半定规划的深入研究则是伴随一系列实际问题展开的关于半定规划解 的存在性、最优性条件、逆问题、灵敏度分析等理论问题也取得一定的成果”“ 随着n e s t e r o v 、n e m i r o v s k i 利用内点算法求解凸规划的一般理论的提出，如何将线 性规划的内点法推广到半定规划是数学规划领域备受重视的课题，这一方面的研 究已经取得了很大进展”6 ”1 近年来，随着半定规划在工程技术和组合优化中的广 泛应用，特别是由于一些n p h a r d 问题可以通过松弛成半定规划模型来研究，使得 半定规划受到了更为广泛的关注目前，半定规划的算法设计及其应用已经成为应 用数学中一个重要的研究方向 在求解方法上，主要是将线性规划的内点算法推广到半定规划，首先是势函数 减少方法o ，后来有路径跟踪方法和投影方法等其中一些算法已被证明具有包括 多项式时间复杂性在内的线性规划内点算法的许多重要性质针对路径跟踪方法， 与线性规划不同，通过对摄动互补松弛条件采用不同的对称技巧，可以得到半定规 划许多不同的原始一对偶搜索方向，使用最多的方向有n t 方向、h k m 方向、a h o 方向等o 。矧在算法中使用不同的方向可得到不同的收敛性质，各种方向的对比参 见文献o ”求解半定规划投影算法的实质是求解与最优性条件等价的单调变分不 等式。“州，而求解半定规划的原始- 对偶内点算法实质是用牛顿型方法求解最优性 条件组成的非线性方程组事实证明内点算法确实是解决半定规划的一个非常有 效的方法，有关半定规划内点算法的理论结果也日益完善关于内点算法的详细、 系统的结果，在a l i z a d e h 、h e l m b e r g 等人的个人主页上”“”均能查到，也可参阅文 献 4 3 4 8 】 在此期间，其他的算法也被提出，例如d i k i n 的仿射算法，但是它可能不收敛 6 西安电子科技大学硕士论文：半定规划及其在组合优化中的应用 于最优解，m u r a m a t s u 和v a n d e r b e i m l 曾经给出一个反例说明 近几年来，半定规划的研究重点已经转向如何求解大规模问题就目前论文出 现的数字表明，内点算法对解决n = 9 0 0 以上的问题已经出现困难近期m k o j i m a ， k n a k a t a 。1 5 ”以及s t e v e nj b e n s o n ，y i n y uy e 和x i o n g z h a n g 利用大规模问题的结构 以及稀疏性，将内点算法进行改进，对于最大割问题的半定松弛，将所能计算的 规模提高到n = 3 0 0 0 对于解决大规模问题，h e l m b e r g 和r e n d l “提出的半定规划 谱丛算法以及本文作者和刘三阳o ”提出的一次微分算法在实际应用中取得了很好 的数值结果，而且从理论上证明了算法的收敛性他们利用强对偶定理，通过解决 对偶问题从而求得原始问题的最优值利用谱丛算法能够解决n = 3 0 0 0 的半定松弛 问题，当然，它仍然是基于稀疏矩阵的尽管它没有给出原始问题最优解，但是对 于半定松弛问题，仍是一个很实用的算法 在求解半定规划的谱丛算法出现之后，针对具体情况，c h e l m b e r g 嘲“1 运用割 平面法求解半定规划，取得了一些新的成果，但是总体来讲，仍然有许多困难没 有解决 对半定规划的研究具有重要的意义，首先，半定规划有着广泛的应用；其次， 由于许多凸规划问题( 例如线性规划和凸二次约束下的二次规划问题) 都可以转 化为半定规划，所以半定规划提供了一个统一的方法用来研究这一系列凸规划问 题并构造求解这些问题的算法“对半定规划的研究不仅在现在，而且在将来的一 段时间里都是一个引人注目的方向，我们可以在这一领域内得到精妙的理论结果、 有效的算法以及广泛的应用唧 对半定规划的详细介绍，请参阅v a n d e n b e r g h e 和b o y d 以及m j t o d d 等人的综述性文章“6 。”1 1 2 1 对偶性定理 1 2 半定规划的对偶理论 给定一个半定规划，自然会想到如下问题： 1 ) 半定规划问题的可行域是否非空? 2 ) 假设1 ) 是肯定的，目标函数是否有界? 3 ) 假设2 ) 是肯定的，最优解是否可以达到? 4 ) 假设3 ) 是肯定的，如何求得最优解? 要想回答这些问题，首先必须了解半定规划的对偶性在给出半定规划对偶理 论之前，先给出两个引理： 苎= 皇丝笙 ： 引理1 1 设4 和曰是两个月阶实对称矩阵，若一卸，b - 0 ，则( 一，占) o 引理1 2 。1 设彳和曰是两个h 阶实对称矩阵，若彳三o ，b 兰0 ，则( 彳，b ) ：0 当且仅当 a b = 0 与线性规划的对偶理论相似，首先介绍半定规划的弱对偶定理 定理1 3 令x ，y 分别为( 尸) 和( d 尸) 的可行解，则( c ，x ) 2 b r y 证明因为( c ，z ) 一善岛咒2 ( c ，z ) 一苫m 、a z ，z ) y ，= ( c 一著mm 4 ，x ) = ( z ，x ) 则由引理1 1 可知，( z ，x ) 0 ，从而有( c ，x ) b r y 定义对偶间隙t 1 为n = t r ( z x ) ，若t 1 = 0 ，则对应- j 彳亍角翠- z ，x 是最优解，反 之不真，v a n d e n b e r g h e 和b o y d m l 曾经给出反例证明下面介绍强对偶定理，它保证 了在一定条件下若对偶间隙为0 ，则z ，x 是最优解记p + 5 1 1 1 d + 分别为原规划( 户) 和对偶规划( d 尸) 的最优值，即： p + = i n f ( c ，z ) ：( 4 ，z ) = 包( f = 1 ，历) ，娩o ) = s u 一i by ：喜dy 。爿，+ z = c ，z - o + = s u p y 。爿，+= c ， j 由定理1 3 知p + d + 设x 和y 叫分别为原规划( p ) 和对偶规划( d p ) 的最优解 集，即： x 。，= 似：( c ，x ) = p - ，( 4 ，x ) = b 。( f = 1 ，m ) ，x - o = y ：b r y = d * , 喜驰一c 您0 ) 注意到，即使p + 或d + 是有限的，或也可能为空集删 定理1 4 。1 如果下列条件之一满足，贝q ：f f p + = d - 1 ) 半定规划原问题( 1 - 1 ) 存在严格可行解，即存在x 满足 x 卜0 ，( m iz ) = b i , i = 1 ，m 2 ) 半定规划对偶问题( 1 2 ) 存在严格可行解，即存在z _ 0 ，满足 e y f a f + z = c 西安电子科技大学硕士论文：半定规划及其在组合优化中的应用 如果以上两个条件都满足，则最优解集合x o p , 弄1 y o p 非空 定理1 4 是一般对偶理论在凸分析中的应用，因此所要求的条件并不特 别w o l k o w i c 哪! 和r a m a n a 呻1 分别通过不同的途径构造了不利用严格可行性的对偶 理论他们的结果虽然有着重要的理论意义，但由于其形式复杂，对半定规划的求 解并没有太大的用处，因此我们不做讨论 1 2 2 最优性条件与对偶准则 假设( p ) 和( d p ) 都存在严格的可行解，则可保证至少存在一对原始对偶最优解 且最优解集合叫和y 非空，即存在可行解x ，y 使( c ，x ) = b r y = 矿= d + ，从而 t 1 = ( x ，z ) = 0 由引理1 2 知x z = 0 ，它称为互补松弛条件，可以看成是线性规划 互补松弛条件的推广 利用上述结论，不难推知若( p ) 与( d p ) 有严格可行解，则为( p ) 的最优解当且 仅当存在( x ，z ) s f 墨使得 ( a i , x ) = b i i = 1 ，i n 卅 y 。a f + z = c( 1 - 3 ) 扭l z y = 0 ( 1 3 ) 称为半定规划的最优性条件与线性规划类似，半定规划可能以多种多样 的形式出现虽然可以经过一系列的变换使其成为标准形式，却没有直接利用对偶 性方便因此我们给出求对偶半定规划的一般准则如表1 1 所示： 表1 1 求对偶规划的准则 m i nm a x 矩阵， 三0 矩阵， 兰 变量 矩阵，1 0 约束 矩阵， 三 矩阵，无约束矩阵， = 矩阵， 三 矩阵， _ o 约束 矩阵，! 变量 矩阵， r 在x r 4 点是局部k 一李普希兹连续的，则 1 ) 可( z ) 是非空的、凸的紧集且可( 工) cb ( 0 ，k ) 2 ) 。( 工，d ) = m a x 磐7 d ：善可( x ) ，v d r ” 3 ) 可( ) ：r 4 _ p ( r ”) 是上半连续的 其中b ( 0 ，k ) = 仁：u x o 忙x ，p 俾“) 表示由r ”的所有子集组成的集合 第二章占一次微分向量丛方法 将上述概念推广，有占一方向导数、占一次梯度以及占一次微分的概念 定义z 3 设，：r ”j r 是凸函数，厂在x 相应于d 的占方向导数定义为 烈列) = 垛丝生掣 定义2 4 设占0 ，则凸函数f ：r ”_ 矗在x r ”的占一次微分可以定义为集合 a ，( z ) = 话r “：，( y ) ，( x ) + 舌7 ( y x ) 一占，_ y r ”1 每个元素告a 。f ( x ) 叫做，在x 点的一个占一次梯度 定理2 2 ”1 如果：r “寸r 是凸函数，则具有下列性质： 1 ) 若s 占2 ，则a ，( x ) ca 。：厂( x ) 2 ) l ( z ，d ) = m a x 倍7 d ：善0 f f ( x ) ，d r ” 3 ) 0 。，( x ) = 话r “：九( x ，d ) 毒7 d ，d r “l ， 4 ) 0 。厂( x ) 是非空、凸的紧集并且对所有亏a 。厂( 工) 满足：k ，其中k 为一常 数 5 ) a 。厂( ) ：r “_ p ( r “) 上半连续 上述概念以及定理是凸分析的基础知识，也是我们要讨论的非光滑凸优化的 理论基础接下来，介绍求解非光滑凸规划的思想方法 2 2 解非光滑凸规划的向量丛方法 2 2 1 非光滑优化 考虑非光滑无约束凸规划 “m i n f x ( x r ) 。( 2 - 1 ) 它属于非线性规划，在数学规划中占有重要的地位在过去的十几年里，对非 线性规划的研究取得了突出的成果，很多迭代算法被提出并得到了广泛的应用最 基本的迭代算法是 算法2 1 m 1 1 4 西安电子科技大学硕士论文：半定规划及其在组合优化中的应用 步0 ：( 初始化) 找到一个初始可行点五g ，令k ：= 1 步1 ：( 寻找下降方向) 找到一可行下降方向d 。r ”，使得 f ( x i + t d i ) 0 步2 ：( 终止) 若x 。满足终止条件，则终止，否则 步3 ：( 线性搜索) 寻找最优步长t 。 0 使得 t a r g m i n 沙( 工t + t d t ) ，t 0 步4 ：( 替换) 4 x ：= x 女+ f i d ，k ：= k + 1 ，转步1 - 其中a r g m a x ( a r g m i n ) 表示使目标函数达到最大( 小) 值的元素关于如何求 解光滑的非线性优化，许多常用的算法，例如共轭梯度法、拟牛顿方法等等，在 寻求下降方向( 步1 ) 的过程中均运用了目标函数的导数的有关性质，首先求出函 数在当前迭代点的导数，继而取与之相反的方向即为函数的局部最优下降方向”o ”1 但是，对于非光滑优化，目标函数的非光滑性增加了寻求下降方向的难度，并且 有许多辅助工作需要完成首先，也是最困难的一个问题，目标函数在当前迭代点 的任意一个导数的相反方向并不一定是它的下降方向其次，终止条件并不是都能 十分明确地表示，即使可以，数值结果也并不理想 下面讨论非光滑函数达到局部最优值的必要性条件，对于凸函数来讲，这些 条件也是充分的并且能够达到全局最优值z 是无约束优化问题( 2 - 1 ) 的最优解的 必要性条件是 定理2 4 ”7 ”如果，：r ”_ r 在x r ”点是局部李普希兹连续的，并且x 是局部 最优解，则 1 ) 0 o f ( x ) 2 ) 对所有d r ”有，o ( x ，d ) 0 与此相应，若x 是无约束优化问题( 2 1 ) 的占一最优解，有： 定理2 5 m7 ”设厂：r ”o r 是凸函数，则下列条件等价 1 ) 0 a ，厂( z ) 2 ) x 是厂的占- 最优解，即厂( x ) 墨厂( y ) + 占，v y r “ 第二章占次微分向量丛方法 2 2 2 向量丛方法 对于非光滑无约束凸规划( 2 1 ) ，假设f ( x ) m 由2 1 的有关知识不难知道， 对于给定一点孔r ”，若矗不是最优解，即0 仨o f ( ) ，则在 的某一邻域内存 在z r ”，使得f ( x ) f ( x 。) 由于h 处的次微分彭( 以) = 毒i f ( x ) f ( x 。) + 考7 ( x x k ) ，v x r ”) ，( z r 时非光滑凸函数的次微分的示意图见图2 1 ) ，则对 图2 1 非光滑函数次微分示意图 于任意毒f f ( x 。) ，有毒7 ( x x 。) 0 问题( 2 一1 ) 等价于寻求下降方向d ”1 ，使得 f ( x 。+ d ) 一f ( x 。) 最小，亦即 m i n f ( x 女+ d ) 一f ( x i ) s t d r ” 根据方向导数与次微分的关系，有厂 。，d ) = m a x 偕7 d 陪o f ( x 。) 7 , 7 0 1 为寻 求下降方向，引入优化问题 厂”= m i n f ( ，d ) s t d r ” i i d l l - 1 ( 2 2 ) 由以不是最优解可知，+ 0 使 f ( x + t d ) ，( x ) ，v t ( 0 ，r ) 成立 f 1 3 _ l ：述定理可知，求得( 2 3 ) 的最优解毒+ ，d = 一孝+ 即为( 2 1 ) 的下降方向在非 光滑优化中，满足厂( _ ，d ) 0 的d 并不具有稳定的下降性质，而l f lf ( h ，d ) 关于h 是不连续的通常来讲，基于上述下降方向的最小化算法并不具有很好的收敛性， 因为数值计算结果表明，这样的下降方向并不是充分的而正( _ ，d ) 关于耳是连 续的，从而保证了下降方向的数值有效性在寻求下降方向时，用a 。f ( x 。) 代替 可( 屯) ，( 2 - 3 ) 转化为 m i n 号柳 s t 孝a 。f ( x i ) 与定理2 6 相对应，有 定理2 7 m 1 若d 是，( 石) 的占- 下降方向即f 。( x ，d ) - o m i n b 7 y j t z = a7 y c ( d p ) z - o 其中，x s “，y r ”若：| f = z ia x = 抚x - o 是一有界集，则有 引理2 8 “”若( p ) 具有有界可行集z ，则( p ) 与( d p ) 满足强对偶定理，且存 在歹r ”使得 月7 歹= i( 2 6 z 由引理2 8 知若( p ) 有界可行，则( p ) 的最优值可以通过求解( d p ) 得到： 1 8 西安电子科技大学硕士论文：半定规划及其在组合优化中的应用 m a x - d + = m i nb r y ，并且最优解z 满足 = d + 一x = b x 三o 在( d p ) 中，z - o 等价于旯一( 一z ) 0 ，利用l a g r a a g e 乘子法，将条件z 至d 加入目标函数，得到无约束优化问题 卿胁a m “( c a 7 ) ，) + b 7 y ( 2 - 7 ) 其中z 。= m a x o ，b 7 夕) 引理2 8 的条件并不特别，在实际应用中绝大部分问题都满 足并且相应的地 0 ，本文讨论z 。 0 时的情况( z 。= 0 时( 2 - 7 ) 是无约束线性规 划，最优值趋向于负无穷) ，它对半定规划的应用有着重要意义 引理2 9 ”1 若a 满足( 2 6 ) ，那么( d p ) 等价于( 2 7 ) ，进而，如果( p ) 可行，则所 有可行解x 满足t r ( x ) = t d 并且最优值p + 存在，p + = d 4 = r a i n b 7 y 根据引理2 8 ，( p ) 的最优值等于( 2 7 ) 的最优值下面讨论( 2 7 ) 2 3 3 半定规划的占一次微分向量丛方法 令厂( y ) = 。丑。( c 一7 y ) + 6 7 y ，不难得知，( y ) 是凸函数，且有结果 c 0 2 m x ( c 一飞) = 眨。i 护( 矿) 铂， = 五一( c 一4 铆) = f p 即7 f i r ( v ) = 矿兰o 以及矽( y 。) ：# 括：6 一心月，w 0 2 ( c ar y 。) j 有界嗽，其中，矩阵p 的列表示 c a7 y 。的最大特征值所对应的特征向量空间中的标准正交基 设辅助点y ：，i = 1 , 2 ，1 定义 g ( y ) = a 。( c a y ) 口i = 旯。( c j 47 y k ) 一旯。( c a7 y ：) 一r l ( y 。一_ y ：) ，叩：a g ( y ：) 可以证明，堙( _ y ：) = 叩卜= 一4 ，形c 9 1 。( c 一爿7 y ：) ) ，又因为g ( y ) 是凸函数， 第二章占一次微分向量丛方法 1 9 所以口：0 定义集合 g ( 以) ：b k ：q 玎；，玩a g d ，i “，i q ，e 1 。蚝：l ，嘶- o i ， 则有： 定理2 1 0 g ( s t ) 依上述定义，则集合b + o g ( s t ) 是凸集、有界，且 b + o g ( 吼) a r u o + + f ( y t ) - 证明由定义不难知道g ( e 。) 是凸集、有界，所以b + z 。g ( 8 。) 是凸集、有界 设叩g ( 6 。) ，对v y r ”有下面不等式成立： 2 m , x ( c a7 y ) = ：。峨a 。( c a y ) ：；。“。 a 。( c a7 y ：) + ( y y ：) 7 叩。i = ，= l “。p 一( c 一“7 y 。) + ( y y 。) 7 叩i 一 旯一( c 一47 y 。) 一k ( c 一7 y ：) 一 ( 儿一y ：) 7 磙】) = 。i u ， m i x ( c 一47 y 。) + ( y - y 。) 7 ，7 ：一口。i = ：；。“，五。( c 一7 ，。) + ( y y 。) 7 0 ，u ，仇- t i ：。“，o t ： 2 a 。“( c a7 y t ) + ( y y i ) 7 1 7 ：一占i 所以 i t o 旯。( c 一爿7 y ) + b r y 。 旯。( c 一4r y k ) + ( y - y , ) 7 叩；一占。 + 6 7 ( y - y , ) + 6 y 。 = 。旯一( c - 爿7 y i ) + 6 7 y t + ( _ y y k ) 7 ( 6 + g o 叩) - g o 占i ， 由以上证明知6 + 鳓叩a 。“f ( y i ) ，命题得证 根据( 2 - 4 ) 与( 2 7 ) ，求解 m i n + i i。f l 。哪m “。i u i 吒i 毛( 2 8 ) ；l u f 。1 “0 ，i = 1 , 2 ， 西安电子科技大学硕士论文：半定规划及其在组合优化中的应用 令”= ( “。，“：，“，) ，m = ( 叩：，玩，琅) 7 ( ，7 ：，旌，7 ：) ，n = ( 叩：，棋) 7 b ， 口= ( 口：，口：) 7 ，e = ( j ，j ，j ) 7 ，则( 2 8 ) 可以等价地写为 r a i n 号届 7 m u + i t o n 7 甜+ 土6 7 b s j 擘 以 ( q p ) 。 e 。”= 1 一一 u 0 因此，求解二次规划( q _ p ) t ，就能得出下降方向d 。= 一亏= 一6 一胁：；，吩优然 后利用一维搜索方法求出t 。，使得 f ( y k + 噍) = 1 册厂( y i + t d t ) f 次微分向量丛算法如下： 算法2 2 步1 。胁= m a x 0 ，b 7 - ，e x i t f l a g ：= 0 ，k ：= 1 ，任取辅助点y ：r m , i = 1 , 2 ， 令k = y ：，y ：) ，y i ：= a r g m i n f ( y k ) ，f o = f ( y i ) ， 2 步2 ：若e x i t f l a g 1 ，d + = ，( 儿) ，终止：否则，计算口