（运筹学与控制论专业论文）拓展熵规划内点算法的复杂性研究.pdf

摘要 i i i 用内点法解凸规划问题时，通常要求初始点是可行的内点，但要寻找问题的初 始可行解一般而言是比较困难的在某些情况下与求解原问题的复杂性几乎是相同 的 本文受线陛规划的自对偶嵌入模型及锥最优化问题的自对偶嵌入模型的启发， 用锥自对偶嵌入模型求解拓展熵规划问题首先把拓展熵规划问题转化为锥最优化 问题，然后对该锥最优化问题构造一个自对偶嵌入模型，该模型一定存在最优解， 利用该模型可以求解原始不可行或无界的问题这种方法不需要寻找初始可行解， 同时可以证明所构造问题的障碍函数满足自协调性，这保证了用某些内点法解此问 题时，算法是多项式时间算法 本文第一章介绍了内点法的发展，并对拓展熵规划做了简要介绍第二章介绍 了几种内点算法第三章介绍了自协调性的理论和自协调性与凸规划问题的复杂性 的关系第四章介绍了锥最优化理论，引入了锥自对偶嵌入模型第五章讨论了拓 展熵规划问题，并给出对应问题障碍函数自协调性的证明 关键词：内点法，凸规划，锥自对偶嵌入模型，拓展熵规划，自协调性，多项式时 间算法 a b s t r a c t i v i ng e n e r a l ，i tn e e d st of i n dt h ei n i t i a lf e a s i b l ep o i n tw h e nw es o l v et h ec o n v e xp r o - g r m l u u l n gu s i n gi n t e r i o rp o i n tm e t h o d ，y e ti t i sv e r yd i f f i c u l tt of i n dt h ei n i t i a lf e a s i b l e p o i n t s o m e t i m e st h ec o m p l e 。x i t yt of i n dt h ei n i t i a lf e a s i b l ep o i n ti ss a m ea st h a tw es o l v e t h eo r i g i h a lp r o b l e m i nl j g h to ft h es e l f - d u a le m b e d d i n gm o d e lf o rl i n e a rp r o g r a m m i n ga n dc o n i cp r o - g r a m m i n g ，t h i st h e s i sp r o p o s et os o l v et h ee x t e n d e de n t r o p yp r o g r a m m i n gp r o b l e mu s i n g c o n i cs d f - d u me m b e d d i n gu l o d e l w et r a n s f o r mt h ee x t e n d e de n t r o p yp r 0 9 1 r m n m i n gp r o b - l e mi n t oc o n i cp r o g r a m m i n g ，t h e nc o n s t r u c tac o n i cs e l f - d u a le m b e d d i n gm o d e lf o rt h e t r a n s f o r m e dc o n i cp r o g r a m m i n g t h ee m b e d d i n gm o d e li sg u a r a n t e e dt oh a v ea no p t i m a l s o l u t i o n w ec a ns o l v et h ei n f e a s i b l eo ru n b o u n d e dp r o b l e m su s i n gt h ee m b e d d i n gm o d e l t h i sm e t h o dd o e sn o tn e e dt of i n dt h ei n i t i a lf e a s i b l es o l u t i o na n dw ep r o v et h a tt h e b a r r i e rf u n c t i o ni ss e l f _ e o n e o r d a n t ，t h i sg u a r a n t e e st h ea l g o r i t h mi sp o l y n o n f i a la l g o r i t h m w h e nu s es o m ei n t e r i o rp o i n tm e t h o dt os o l v et h i sp r o b l e m i nc h a p t e r1 ，ab r i e fi n t r o d u c t i o ni sg i v e nt ot h ed e v e l o p m e n to fi n t e r i o rp o i n tm e t h o d a n dt h ee x t e n d e de n t r o p yp r o g r a m m i n g i n c h a p t e r2 ，w ei n t r o d u c es o m ei n t e r i o rp o i n t m e t h o d s i nc h a p t e r3 ，w ef o c u so nt h et h e o r yo fs e l f - c o n c o r d a a e y ，a n dt h er e l a t i o n b e t w e e nt h ec o m p l e x i t yo fc o n v e xp r o g r a m m i n ga n ds e l f - c o n c o r d a n c 矿i nc h a p t e r4 ，w e i n t r o d u c et h ec o n i co p t i m i z a t i o na n dc o n i cs e l f - d u a le m b e d d i n gm o d e l i nc h a p t e r5 ， w es t u d yt h ee x t e n d e de n t r o p yp r o g r a m m i n g ，a n dp r o v et h a tt h eb a r r i e rf u n c t i o no ft h e p r o b l e mi ss e i f - c o n c o r d a n t k e y w o r d s ： i n t e r i o rm e t h o d lc o n v e xp r o g r a m m i n g ，c o n i cs e l f - d u a le m b e d d i n gm o d e l ，e x t e n d e d e n t r o p yp r o g r a m m i n g ，s e l f - c o n e o r d a n e y , p o l y n o m i a la l g o r i t h m 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人己发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：盍圣叠导师签名：! 翌益垫 日期：塑! ! 型 第一章前言 l l内点法的发展 内点法是研究者在寻找求解线性规划的多项式时间算法时提出的线性规划 ( l p ) 有如下形式： r a i n ，z s a z = 6 z20 单纯形方法是求解线性规划问题的较好的方法，这种方法利用可行域的几何结构： 沿着可行域的边从一个顶点移动到另一个更优顶点，最后得到最优点 然而二十世纪六、七十年代，随着计算机的快速发展，研究者对算法的复杂性 越来越感兴趣多项式时间算法被认为是有效的算法所谓多项式时间算法就是用 这种方法求解问题时所需要的迭代数以问题大小的多项式为界 1 9 7 2 年，k l e ea n dm i n t y 【1 】给出了一个线性规划的例子，说明了单纯形方法不 是多项式时间算法在这个例子中有n 变量和2 n 个约束条件，当用单纯形方法求 解这个线性规划时需要2 ”一1 步迭代，即迭代数较问题的规模呈指数倍增长那么 对于线性规划是否存在一个多项式时间算法 1 9 7 9 年，k h a c h i a n 2 】首次发表了一篇求解线性规划的多项式时间算法一一椭 球算法的文章，这种椭球算法是基于s h o t 【3 1 和y u d i na n dn e m i r o v s k y 4 l 发展的非线 性规划理论，不应用线性规划的几何结构然而，尽管这种算法是一个多项式时问 算法，但它在实际运算时却很慢，并不是一个有效的算法那么对于线性规划是否 存在一个多项式时间算法，并且在实际运算时也是非常有效的 1 9 8 4 年，k a r m a r k a r 5 】回答了上述问题，他在 5 】中提出了求解线性规划的一 个新的多项式时间算法一一投影方法，这种方法求解大规模线性规划时比单纯形方 法快1 0 0 倍k n ”k w 的工作开辟了一个新的研究领域一内点法的研究领域 自从k a r m a r k a r 提出内点法以后，有关内点法的文章已经发表了三千多篇。一 些教材也已经出版7 】 8 】数值结果确实证实了用某些内点法要比用单纯形法解 线性规划时快得多内点法不仅适合解线性规划问题，而且可以应用于求解非线性 规划二十世纪五、六十年代，f r i s c h 9 1 0 】，h u a r d 1 l 】，d i k i n 1 2 1 分别用对数障 碍函数法，中心法，仿射比例调节法求解非线性规划由于内点法的发展，导致了 1 舶0 6 上海大学硕士学位论文2 这些方法的重现目前，研究者的研究工作大多集中在用内点法解非线性规划，特 别是对凸规划的研究 1 2拓展熵规划简介及研究现状 拓展熵规划( e p ) 具有如下形式： r a i n ，z + ，t ( ) s t a 工= b z 0 这里i ”( 甄) l 墨丘掣， 0 ，c r ”，b r m ，a n ( 假定a 是行 满秩的) 拓展的熵规划是一类凸规划，它在经济、管理等领域有重要的应用，因此对它 的研究有重要理论和现实意义这类问题y e ，p o t r a 1 3 ，h a ne ta 1 1 4 1 进行了主要研 究 e ， 特别当 ( 甄) = x l i n x i 时，称为熵规划，此时有i 一”( 甄) l 五 掣，即岛= 1 【1 i 证明了拓展熵规划的对数障碍函数满足自协调性，因此可用某些内点法使 问题在多项式时间内求解然而这种方法要求初始点是可行的，我们知道寻找初始 点在一般情况下都是比较困难的 【l6 】针对线性规划提出了一种内点法，这种方法不需要初始点是可行的，f 1 7 】证 明了在一定条件下，用此方法解线性规划时算法是多项式时间的然而目前还没 有理论证实此算法使某一类非线性凸规划，包括拓展熵规划在多项式时间内求解 本文主要是把拓展的熵规划问题转化为锥最优化问题，对锥最优化引入自对偶 嵌入模型，证明了问题的障碍函数满足自协调性，这保证了某些内点法可以使问题 在多项式时间内求解 第二章内点法 本章主要介绍内点法的知识，首先介绍内点法中的两个重要概念，然后再介绍 一些内点算法 2 1内点法中重要的概念 本节介绍在内点法中重要的概念；障碍函数和中心路径 2 1 1 障碍函数 在内点法中，一般采用如下障碍函数的概念 定义2 1 1 如果函数f ：c r 满足下面的条件： ( a ) f 是三阶连续可微函数； ( b ) f 是e 上的严格凸函数，即v 2 f 是正定矩阵； ( c ) 当x a g 时( s c 为c 的边界工f ( z ) 一十o 。 那么称f 是凸集e 上的障碍函数 利用障碍函数可以把一个不等式约束的问题( p ) 转化为带有参数的无约束问题( 兄) 。r a r i n 。m ) s t g i ( x ) 0 ，v i 舢r a i n 。m ) + p 地( z ) ) 无约束问题( 巳) 的障碍项p t f ( 吼( z ) ) 使得由( r ) 产生的迭代点在p 的可行域内 部，远离可行域的边界随着p 不断变化可以得到一系列无约束最优化问题我们 期望当p 一0 时，( 兄) 的最优解序列收敛到( p ) 的最优解 2 1 2 中心路径 本小节由凸规划给出中心路径的概念 凸规划f c p ) ： 3 2 0 0 6 上海大学硕士学位论文 4 s t 扛) 0 ，i = 1 ，m z r ” 这里f ( x ) ， ( z ) 是凸函数 为了叙述方便，对于凸规划问题( c p ) ：我们采用【1 5 的形式； s t ( ) 墨0 ，i = 1 ，n y r ” 这里f ( y ) 是凹函数， ( ) 是凸函数 记( c p ) 的可行域为，可行域的内点的集合为声，并且假定一非空有界 ( c p ) 的对偶问题( e d ) ： m i n ，( ) 一观 ( ) = 1 n “x _ f v f i ( y ) = v f ( y ) f = 1 z i 0 ( c p ) 的障碍函数为 砘川= 一半一宝l n ( 吲砒p 。 记 咖川k v 脚卜半+ 霎裂 脚，：= v 2 f 归一掣+ 娄c 珊i + 警， “_ 一ji j 由于h ( y ，p ) 是f o 上的正定矩阵，所以f ( y ，p ) 是f o 上的一个严格凸函数，并且 在可行域f 的边界趋于无穷，所以f ( vp ) 的最优点( t t ) 在f o 上取得，g ( u ) 称为 p 一中心 令g ( g p ) = 0 ，得到关于( 卢) 的k k t 条件： 2 0 0 6 上海大学硕士学位论文 5 五( p ) s0 ， 1 i n 鍪1 q v ( ) = v f o ( ) ， z 0 一，i ( ) 戤= p ， 15 i n 定义2 1 2 中心路径：原始附偶，中心路径是当p 趋于零的过程中( p ) ( z ( p ) ，”( p ) ) 的集合 这里不仅口( p ) 是( c p ) 的可行解，而且( z ( 卢) ，( p ) ) 是( c d ) 的可行解，并且对 偶间隙在( ( p ) ，( p ) ，5 ( 弘) ) 满足 nn ，0 ( 口( p ) ) 一孔( p ) b ( p ) ) 一，0 ( ( “) ) = 一甄( p ) 悖( p ) ) = n i l ( 2 1 ，1 ) i = 12 = 1 因为z ( p ) ，( p ) 是p 的连续函数，并且当p 一0 时，对偶间隙 n ，0 ( ( _ “) ) 一z t ( p ) ( ( p ) ) ，0 ( ( p ) ) = n p 一0 o = 1 所以当肛一0 时，口( p ) ，z ( p ) 将分别收敛于( c p ) ，( c d ) 的最优解 2 2 内点算法 下面以特殊的凸规划一一线性规划为例来介绍几种内点算法 2 2 1 对数障碍函数法 线性规划问题( l p ) 其对偶问题( l d ) s ta z = b z 0 b i y a t y + s = c s 0 2 0 0 6 上海大学硕士学位论文 6 ( l d ) 的对数障碍函数为 f ( 洲) = 一了b t y 一壹i = 1 l n p 。 r ( y ，p ) 的一阶、二阶导数分别为 一阶最优| 陛条件为 9 = 一旦+ a sl e p h ：a s 一2 a t a t y + s = c ， s 0 a z = b z 0 x s = l j e ( 2 2 ，2 ) 记( 2 22 ) 的唯一的一个最优解为( z ( p ) ，”( p ) ，s ( p ) ) ，由( 2 1 1 ) 可知对偶问隙满足 x t ( p ) 5 ( p ) = n p( 2 2 3 ) 因为z ( p ) ，口( p ) 是p 的连续可微函数，所以当p 一0 时，z ( 卢) ，( 卢) 分别收敛于 ( l p ) ，( l d ) 的最优解 记 p + = 工ia x = b ，z o ) 口+ = ( ”) i a t + s = 郇 0 ) 对数障碍函数算法： 步骤0 ：取e 0 ，0 蠢，令g a + 1 ：= ( 1 0 ) g k ，p 女：= p 1 ：转步骤3 ，否则， 终止 步骤3 ：如果1 ip kl f 玑f ，那么转步骤4 ，否则转步骤2 步骤4 ( 内迭代) ：计算步长丘，商= a r g m 。) i n o f ( 讥+ a p k ，p b ) ：姚+ a p k 口+ ) ! ， + 1 ：= y k + 5 p k 2 0 0 6 上海大学硕士学位论文 7 转步骤2 定理2 1 ( 【1 5 】) 如果u 减小，那么原始线性规划( 工p ) 的目标函数值，z 单调减 小，对偶线性规划( l d ) 的目标函数值矿单调增加 r o o sa n dv i a l l l 8 定义( p ) 和严格可行点y 之间的距离： 地，p ) = 哑n 譬e 叶a z = b ) ( 2 删 式( 2 2 4 ) 中s 是一个对角矩阵，满足s e = 毛向量s = c a 7 y ，e = ( 1 ，1 ) t 记式( 2 24 ) 的唯一解为z ( ，p ) 可以得到下面的定理： 定理2 2 ( 1 5 1 ) y = v ( u ) 当且仅当6 ( g ，p ) = 0 ，并且如果6 ( ，p ) = 0 ，那么z ( ，p ) = z ( p ) f ( u ，p ) 在y 点的牛顿方向为 ，( ”，p ) = 一日一1 ，= ( s 一2 7 ) ( ：一a s 一1 e ) 下面定理陈述了距离6 ( ：p ) 和牛顿方向p ( v ，p ) 的日范数之间的关系，这里 h = a s 一2 a t 定理2 3 ( 【1 5 】) 对于给定的p 和y ，有6 ( 弘卢) = jp ( 9 ，p ) i i h = l ls - 1 a t p ( 口：p ) 肌其 中l ip ( ”，u ) f i h = 石7 脚 在不至于混淆的情况下我们把p ( ，p ) 简写为p 定理2 4 ( 1 5 】) 如果6 ( f ，扛) 1 ，那么y + = y + p 是( l d ) 的严格可行解，并且 占( y + ，p ) 茎铲( 可，p ) 下面两个定理说明了目标函数在迭代点y 和中，5 - 路经f ( p ) 处的函数值的关系 定理2 5 ( 1 1 5 ) 如果5 = 6 ( g ，卢) 1 ，那么 f ( v 川- f ( 咖) 川啬 定理2 6 ( f l5 】) 如果5 = 6 ( ，p ) 1 ，那么 b t y - - 嘞( 训等p 而 复杂性分析： 在这里我们取r = ；即6 = 1 1p 怙r = ； 2 0 0 6 上海大学硕士学位论文 8 定理2 7 ( 1 5 1 ) 至多经过 1 1 4 n p o i m 步外迭代后，对数障碍函数算法终止于点y ，满足，一b t y e ，这里z + 为( l d ) 的 最优值 定理2 8 ( 1 5 1 ) 每一步外迭代至多需要 研1 1 0 ( ；q + 萼 步内迭代 定理2 9 ( 【1 5 】) 对数障碍函数算法至多需要 尚( 叭一3 而) + 一1 1 23 0 n 半【( 1 一口) 2 。j 步牛顿迭代找到满足给定精度的最优解 2 2 2 路径跟踪法 这里所介绍的原始一对偶路径跟踪算法，是一种原始一一对偶可行算法，即 所有的迭代点( z ，y k ，s k ) 矿口+ 令( z ，y ，8 k ) 是当前的迭代点，( z k + 1 ，y k 扎3 k + 1 ) = ( x k + a x k ，y k + 蛳，8 k + a s k ) 是下一步p + 1 = ( 1 一日) p ( o 0 ，0 日 l ，初始可行解( x o ，y o ，s o ) p + d + 和相应的p o ，满 足d l ( z o ，y o ，s o ) i ，令p k + 1 ：= ( 1 一目) m ，舭：= p k 扎转步骤3 ，否则，终止 步骤3 ：由( 2 2 5 ) 计算出a x k ，a y k ，钆， z k + 1 ：= z r + z k ，y k + 1 ：= y k + a y k ，s k + 1 ：= 8 女+ a s k z k ：= x k + l ，y k ：= y k + l 8 k ：= 8 k + l 转步骤2 对于路经跟踪算法，如果( z k ，蛳，8 茸) p + 口+ ，那么( $ + 1 ，y k + l ，s k + 1 ) p + d + 并且对于合适的口和r ，如果d 1 ( x k ，y k ，8 k ) ；，转步骤3 ，否则，终止 步骤3 ：由( 2 2 5 ) 计算出a x k ，a y k ，a s k ，转步骤4 步骤4 ：计算步长a ， 舀= a r 9 1 嚷“ + p p k + a a x k ，s + o 船) ：( x k ，批，吼) + a ( a x k ，a y k ，s k ) p 十口+ ) t k + l ：= x k 十q a x t ，y k + l ：= y k + a y k ，s k + l ：= s t + 五s k p + 1 = ( z 玉1 s t + 1 ) n x k ：= x k + l ，y k ：= y k + l ，s k ：= s k + l p k ：= ” + h 转步骤2 在这个算法中搜索方向与路径跟踪算法相同，不同在于在每一步迭代中，卢t 并 不是事先定义好的下降序列，而是需要根据每一步迭代重新计算，即小= ( z 蚕乳) n 势函数算法的复杂性可以由下面定理得到 定理2 1 1 ( 8 1 ) 如果p = v 伍，那么由势函数算法产生的序列z ，y k ，s p + xd + 满足 谚n + 、元( 。k + 1 ，y k + i 8 k + 1 ) s 妒n + v 伍( x t ，y k ，8 k ) 一0 5 关于势函数法的详细内容可以参看【8 】 2 2 4 仿射比例调节法 这种方法利用了投影变换，在一个椭球和仿射子空间的交集上最小化目标函数，对 于线性规划问题( l p ) ： m i n ，z 5 t a z = b z 0 令z t 是当前的迭代点，构造一个以x k 为中心的椭球来代替多胞体，然后在椭球上 最优化目标函数，得到的最优点作为下一步迭代点 令d 是一个正定对角矩阵，x = d w 下面的规划( p d ) 。r a 舻i n ( d c ) 7 u s ta d u = b u0 2 0 0 6 上海大学硕士学位论文 和( l p ) 是等价的 我们选择一个特殊的对角矩阵d = x ，x k e = 我们可以获得下面的规划 问题 。r a 出i n ( 甄c ) 1 “j s t a x k u = b u 0 构造个以e 为中心的球 u 一e | js 卢1 ，这里0 卢 l ，且有 u 一e | | 兰卢1 ) c 扣p o ) ，然后在这个和仿射子空间的交集上最小化目标函数 即 砌r a i n 。陬矿u s ta x k u = b | | u e i 兰卢 返回到原空间，即u = 翼i l z ，得 m i n ，z $ 寸 s a x = b i i 酊1 z e 1 1 卢 容易得到这个问题的解 x p a x h x k c x k + l2 x k 一碡蓠 因为| i j 1 z e | | 卢整个落在x o 中，所以x k + 1 是可行的，且它比x k 更接 近最优解关于卢的选取和收敛性证明可以参看【1 2 】【2 0 】【2 l 】【2 2 】【2 3 】【2 乱但目前为止 仍然不知道这种方法是否是一个多项式时间算法 这里只是对仿射比例调节法的思想做了简要介绍，关于具体算法和详细内容可 参看 1 2 】 1 5 】【1 9 】【2 0 】 2 l 】 2 2 】 2 3 】【2 4 】 第三章自协调性 n e s t e r o v 和n e m i r o v s k y 【2 5 】给出了一个在复杂性证明中重要概念一一自协调 性，自协调性是证明算法复杂性重要条件 3 1自协调性 本节主要阐述自协调性的概念和它的等价条件及性质 定义3 1 1 函数f ：c r 被称为( ) 自协调的，如果f 是一个由定义2 j j 所定义的障碍函数，并且满足下列条件： i v 3 f ( t ) 限，h ，h l l k ( v 2 f ( z ) m ，q ) ( 3 1 1 ) v t f ( z ) ( v 2 f ( z ) ) 一1 v f ( z ) ” 事实上式( 3 1 1 ) 也可以写成 v 3 f 扛) m ，h ，州茎x ( v 2 f ( z ) i h ，州) 因为 v 3 f ( z ) 一h ，一h ，一h i k ( v 2 f ( z ) 一h ，一纠) ；营 一v 3 f ( 茁) 【 ，h ， 】一( v 2 f ( z ) l h ， 】) 【1 9 】介绍了( 3 1 1 ) 和( 3 1 2 ) 的等价条件，由下面两个定理给出 记b ，h ( t ) = f ( x + t h ) ，定理3 1 给出了( 3 1 1 ) 的等价条件 定理3 1 下面四个条件等价： v 3 f ( z ) ，h ，h k ( v 2 f ( z ) ， 】) ；：z i n t c ，h r n 珐( o ) k ( ( o ) g ，z i n t c ，h 础 j 羔：( t ) 茎k ( j 耋 ( ) ，z + t h i n t c ，h r n c 一南) ， 争叭删c ，托舻 1 2 ( 3 12 ) ( 3 1 3 ) ( 3 1 4 ) ( 3 15 ) ( 3 16 ) 2 0 0 6 上海大学硕士学位论文 1 3 誊爱： f 骚 ( 3 1 7 ) ( 3 1 8 ) e ( o ) = v g ( x + ) 【叫，h ( o ) = v 2 f ( z + t h ) h ，叫，碟( o ) = v 3 f ( x + t h ) h ， ，h i 再与( 3 1 7 ) 比较，可知( 3 1 4 ) 与( 3 1 5 ) 是等价的 又因为 ( 一南) 7 = 知一酝， 因此，( 3 1 5 ) 与( 3 1 6 ) 是等价的 - 定理3 2 下面四个条件等价： v 丁f ( z ) ( v 2 f ( 。) ) 一1 v f ( x ) 嵋z i n t c ( o ) 2 茎 ( o ) ，z i n t c ，h 口 h ( t ) 2 ( t ) ，z + t h i n t c ，h 舻 卜赢7 7 外流引驯印“ ( 3 1 9 ) ( 3 1 1 0 ) ( 3 1 1 1 ) ( 3 1 1 2 ) 2 0 0 6 上海大学硕士学位论文 1 4 证明：首先证明式子( 3 11 0 ) 隐含着( 3 1 9 ) v t f 扛) ( v 2 f ( z ) ) 一1 v f ( x ) = v f 扛) ( v 2 f ( 第) ) 一1 v f ( x ) 】 = e ，( v 2 f ( 。) ) 一1 v f ( 。) ( o ) ( v ：唯) ) 却肌) ( o ) = 、厅v 2 f 扛) 【( v 2 f ( z ) ) 一1 v f ( z ) ，( v 2 f ( z ) ) 一1 v f ( x ) 】 = v 石x v t f ( z ) ( v 2 f 扛) ) 一1 v 2 f 0 ) ( v 2 f 扛) ) 一1 v f ( z ) = 厅v t f ( z ) ( v 2 f ( z ) ) 一1 v r f ( 。) 第一个不等式由( 3 1 1 0 ) 得到，所以式子( 3 1 1 0 ) 隐含着( 3 1 9 ) 反过来 ， ( o ) 2 = ( v f ( z ) 嘲) 2 = ( v t f ( z ) ) 2 = f v 7 f ( z ) ( v 2 f ( z ) ) 一1 v 2 f ( z ) ) 2 = ( ( v 2 f ( z ) ) v f ( x ) ， ) ： 曼l i ( v 2 f 扛) ) 一1 v f ) 屺i i 幢 = ( v t f ( 。) ( v 2 f ( z ) ) 一1 v 2 f 扛) ( v 2 f ( z ) ) 一1 v f ( z ) ) ( h t v 2 f ( z ) ) v 2 f ( x ) h ，h 】 = v h ( o ) 第二个不等式由( 3 1 9 ) 得到，所以( 3 1 9 ) 隐含着( 3 11 0 ) 综上可知( 3 19 ) 与( 31 1 0 ) 是等价的 与上述定理证明相似，如果z + t h 取代z ，可知( 3 1 1 1 ) 与( 3 1 1 0 ) 是等价的 最后，因为 ( 一丽1 ) = ( 砭“曲) 。水) 所以( 31 1 1 ) 与( 3 1 1 2 ) 是等价的所以四个条件是等价的 事实上，由式( 3 1 8 ) 中h ( o ) = v f ( x ) h l ，h ( o ) = v 2 f ( z ) 【九，h l 可知，式 ( 3 11 0 ) 即为l v f ( x ) h l l 石( v 2 f ( z ) 函数的自协调性具有如下性质： 2 0 0 6 上海大学硕士学位论文 1 5 性质3 1 1 ( 2 5 】如果f 是凸集q 的( 一l ，) 一自协调障碍函数，g 是凸集岛的 ( 忱，屹) 自协调障碍函数，那么( f + g ) 是o n q 的( m a x k 1 ，k 2 ，n + 地) 一自协 调障碍函数 3 2 自协调性与凸规划 这部分内容阐述了一个重要结论：如果凸规划问题的障碍函数满足自协调性， 那么对数障碍函数算法是求解这个凸规划的一个多项式时间算法 下面我们把h ( y ；p ) = v 2 f ( u ，p ) 简记为h ，这里f ( u ，p ) 为凸规划的障碍函 数，把牛顿方向简记为p ，同时假定f ( y ，肛) 是一个( 一，”) 一自协调障碍函数 定理3 3 ( 【1 5 d 如果y f o ，i l p l l g 0 有 a z + ( 1 一a ) c 即集合包含集合内任意两点的连线 对于凸锥我们有下面的定理 定理4 1 ( 2 r 】) 锥c 是凸锥，当且仅当对任意zec 和yec ，有z + c 定义4 1 2 如果一个锥c 满足i n t c 0 ，那么称这个锥是实心锥 在锥最优化中，一个重要概念是对偶锥概念 定义4 1 3 如果一个集合c + 满足 c + = z + 舻ix t z + 0 ，。c ) 那么称p 是锥c 的对偶锥，如果一个锥的对偶锥是它自己，那么我们称这个锥是 自对偶的 关于对偶锥我们有下面的定理 定理4 2 ( 【2 7 ) 如果c 是一个闭凸锥，那么它的对偶锥c + 也是一个闭凸锥而 且的对偶( c + ) + 等于c 4 1 2 锥最优化及其对偶理论 锥最优化问题( c o p l 是如下的一个规划问题 1 7 2 0 0 6 上海大学硕士学位论文 1 8 这里c 是一个实心凸锥 它的对偶问题( c o d ) ： m o nc x s t a z = b z c m n zb t y s t a 7 y + s = c s c + 这里c + 是c 的对偶锥 【1 9 】介绍了锥最优化的对偶理论一弱对偶和强对偶定理 定理4 3 偈对偶定t 1 ) 如果x 是原始锥最优化问题( c o p ) 的可行解， ( y ，s ) 是 对偶锥最优化( c o d ) 的可行解，那么 当且仅当x t s = 0 时，等号成立 ，s = ，z 一扩称为对偶间隙，显然，如果原始一一对偶对( z ，y ) 满足s t s = ，z b t = 0 ，即满足零对偶间隙，那么z 是原始问题( c o p ) 的最优解，y 是对偶 问题( c o d ) 的最优解反之，不一定成立，即对于锥最优化问题的原始一一对偶 最优解对( z ，) ，不一定满足零对偶间隙 【1 9 】给出一个对偶间隙非零的例子 例：原始问题 r a i na z 3 2 x 4 f 2 15 4 s tz 3 + z 4 = 1 ，z 2 = o ，i 茁4 z 2 i x 5 x 6 2 0 0 6 上海大学硕士学位论文 1 9 y l = 一2 ，y 2 0 是问题的可行解，对于所有可行解有相等的目标函数值一2 ，所以 问题的最优解：d + = 一2 因此对偶问隙为p + 一矿= a + 2 然而在一定条件下，原始问题和对偶问题的最优值是相等的，即对偶间隙为零 这需要严格可行解的概念 定义4 1 4 如果z 是原始问题的可行解，并且z 是锥c 的内点即 a x = b t i n t c 那么z 称为原始问题的严格可行解 相应地 定义4 1 5 如果( y ，s ) 是对偶问题的可行解，并且( y ，s ) 是锥c + 的内点，即 a t y + s = c ，s i n t c + 那么( y ，s ) 称为对偶问题的严格可行解 定理4 4 偿对偶定理，如果对偶问题( c o d ) 有一个严格可行解，那么我们有 r 叫如果对偶问题是无界的，即扩= o 。，那么原始问题是不可行的 r 6 j 如果对偶问题是有界的，那么原始问题是可行的，并且原始问题和对偶问题的 最优值相等，即对偶间隙为零 如果凸锥的障碍函数满足自协调性，那么对数障碍函数法和路径跟踪法都可以 保证锥最优化问题在多项式时间内求解关于锥的自协调性理论可以参看【2 讣 剪 肆 、， 以 0 o 一 2 刊。 一 胆 o 一 0 一 ，。，。 2 0 0 6 上海大学硕士学位论文 4 2自对偶嵌人模型解锥最优化 原始对偶自对偶嵌入模型不需要求问题的初始可行解，且这种模型一定存在最 优解，通过解这种嵌入模型，或者得到原始问题的最优解，或者可以得出原始问题 是不可行的，因此这种方法适合解决原始不可行和无界问题 这种自对偶嵌入方法被拓展用来求解更一般的约束凸规划问题l u o ，s t u r n 和 z h a n g 【2 9 ，d ek l e r k ，r o o s 和t e r l a k y 3 0 ，p o t r a 和s h e n g 3 1 1 用这种方法求解半定规化 问题，实际上l u o ，s t u r n 和z h a n g1 2 9 】这种方法适合解一般的锥最优化问题 下面介绍这种求解锥最优化问题的自对偶嵌入模型 考虑锥最优化问题( c o p ) 和对偶问题( c o d ) ，取任意：c oei n t c ，s o i n t c + ， y o 驴，令 r p = b a x o ，r d = 8 0 一c + a 7 y o ，r 9 = 1 + ”跏一b t y o 考虑下面的嵌入模型( s c o p ) m i n口口 5 t a x b t + r p o = 0 一a t y+ 口+ r d o s = 0 b t y 一一z + r g e k = 0 一焉u 一焉z r g t = 一b z c ，r 0 ，s c + ，k 0 这里口= 1 + ( 2 5 0 ) 7 s o l ，变量为( ，z ，r ，口，s ，女) 容易证明( s c o p ) 是自对偶的，即它的对偶问题是它自已并且( ，z ，r ，口，s ，k ) = ( y o ，t o ，1 ，1 ，8 0 ，1 ) 是约束锥r “x c r + rxc + xr + 的内点，因此( y o ，z o ，1 ，1 ，s o ，1 ) 是( s c o p ) 问题的严格可行解根据自对偶性i( s c o p ) 问题有非空有界的最优 解 2 8 】介绍了锥自对偶嵌入模型的最优解与原始锥最优化问题的最优解之间的关 系： 定理4 5 锥自对偶嵌入模型( s c o p ) 存在最优解，最优解( 矿，矿，r ，眠s + ，k + ) 满 足目+ = 0 ，( z ) 丁s + + r + k + = 0 而且，如果r + 0 ，那么2 5 * t + 是原始锥最优化问 题( c o p ) 的最优解，( 旷r ，s + 厅+ ) 是对偶锥最优化问题( c o d ) 的最优解如果 k + 0 ，那么或者c t 2 5 + 0 ，此时问 题( c o p ) 是不可行的+ 第五章拓展熵规划 本章主要是把拓展的熵规划问题转化为锥最优化问题，在对构造的锥最优化问 题引入自对偶嵌入模型，最后证明了问题的障碍函数满足自协调性，这保证了某些 内点法可以使问题在多项式时间内求解 拓展的熵规划 ( e p ) 等价于 a z = b z 0 同样，l 一”( 奶) j 盔竽，岛 0 ，c r n ，b r m ：a r m 加 定理5 1 拓展熵规划的对数障碍函数f ( z ) l o g ( r 7 ( c t x + 各1 ( 孔) ) ) 一l o g x i 是( 1 + m a x ，n + 1 ) 自协调的 定理的证明要用到下面的两个引理： 引理5 1 1 凸函数f ( x ) c 3 ( ，如) ，如果存在。，崩对任意z 尹，h 舻满足 广i i i v 3 m ) ，h ：圳卢矿v 2 m ) j 等 那么 f ( z ) = ，( z ) 一l o g x l ( 5 1 1 ) l = l 满足自协调性的第一个不等式p i 纠，参数一= l + 1 3 卢并且 n c ( t ，z ) l o g ( t ，( z ) ) 一l o g x i ( j 1 2 ) t = l 也满足自协调性的第一个不等式p u ，参数一= 1 + 1 3 芦 此引理的具体证明过程可以参看 1 5 】 引理5 1 2 如果，( 工) 是凸函数，那么f ( x ) l o g ( ，( z ) ) 满足自挤调性的第二 个不等式p1 圳，且参数= 1 口1 0 一 扛 。日 + z，一 即 s 2 0 0 6 上海大学硕士学位论文 证明：令b ，h ( t ) 一l o g ( ，扛+ t ) ) ，那么有 “归一觜 嘲归一醚型螋斋篇掣幽型 因为，( z ) 0 ，q p ，扛p ) 0( 5 2 7 ) 下面的共轭函数的概念与凸锥c c 的对偶锥密切相关+ 定义5 2 1 如