（应用数学专业论文）半定规划的内点算法.pdf

摘要 半定规划是线性规划的推广。由于半定规划在许多领域有着广泛的应用，近 年来其理论和算法取得了很大的进展。半定规划的内点算法由于在理论上具有多 项式复杂度以及在实际运算中的良好效率而得到了广泛的研究，成为当前解决中、 小规模半定规划问题的主要的算法。 本文前部分介绍了半定规划的基础知识、基本理论、主要算法，对半定规划 的研究现状作了简单的说明。本文后部分是对两种半定规划的内点算法所作的研 究，主要研究成果如下： 1 提出了一个改进的核函数，并基于此函数建立了半定规划的原对偶内点算 法，给出了相应的长步长和短步长算法的复杂度。 2 采用不同的可行步，建立了半定规划的相应的全牛顿步的原对偶不可行内 点算法，并给出了算法的复杂度。 关键词：半定规划核函数原对偶可行与不可行内点法 多项式复杂度 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 ne x t e n s i o no fl i n e a rp r o g r a m m i n g ( l o ) i n r 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 m sf o rs d p h a v ed e v e l o p e dg r e a t l y ，a n di t sm 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 d i nm a n yf e l d s i n t e r i o r - p o i n tm e t h o d s ( i p m s ) f o rs d p h a v e b e e ns t u d i e di n t e r s i v e l y , d u et ot h e i rp o l y n o m i a lc o m p l e x i t y a n dp r a c t i c a l e 伍c i e n c y i p m sh a v eb e c o m et h em o s ti m p o r t a n tm e t h o dt os o l v es m a l lo rm e d i u m s c a l es d pp r o b l e m s i nt h i sp a p e r , w ef i r s t l yi n t r o d u c et h et h e o r y , a l g o r i t h ma n dr e c e n tr e s e a r c ho f s 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 rw o r ki ni p m sf o rs d ew ec o n c l u d e t h e ma sf o l l o w s ： 1 w ep r e s e n tap r i m a l d u a li n t e r i o r - p o i n ta l g o r i t h mf o rs d pb a s e do na ni m p r o v e d k e m e lf u n c t i o na n dd e r i v et h ec o m p l e x i t ya n a l y s i s w eo b t a i n e dt h ei t e r a t i o nb o u n d sf o r l a r g e a n ds m a l l - u p d a t em e t h o d s 2 w ep r e s e n tan e wp r i m a l d u a li n f e a s i b l ei n t e r i o r - p o i n ta l g o r i t h mf o rs d p w i t h f u l l n e w t o ns t e p sb yu s i n gad i f f e r e n tf e s a s i b l es t e p sa n dd e r i v e t h ec o m p l e x i t y a n a l y s i s 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 k e m e lf u n c t i o n p r i m a l - d u a l f e a s i b l ea n di n f e a s i b l ei n t e r i o r - p o i n tm e t h o dp o l y n o m i a lc o m p l e x i t y 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位仍然为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 日期纽f 旦：ll 日期坐! ! ：! ：j 蝉学 名 名 签 签 人 师 本 导 第一章绪论 第一章绪论 本章主要介绍了半定规划的产生和发展的基本状况，阐述了半定规划的基本 概念、基本理论及其主要算法。最后列出了本文的章节安排。 1 1 引言 1 1 1 半定规划的产生与发展 数学规划主要是研究在一定限制条件下，选取某种方案，以达到最优目标的 - - f l 学科，包括创建数学模型、设计最佳计算方法、研究这些算法的理论性质以 及在实际问题中的应用等。数学规划自产生以来就一直是运筹学中比较活跃的分 支，而现代计算机的普及，更是促进了数学规划的迅猛发展。现在数学规划已经 在工程设计、系统与控制理论、经济计划以及国防建设等许多领域内得到了广泛 的应用。 随着运筹学的产生和不断发展，许多新的问题逐渐在数学规划领域中提出， 而已有的线性规划和非线性规划的相关理论难以解决这些新问题。对这些新问题 的不断研究导致了数学规划的一个新的领域一一半定规划的产生和发展。半定规 划，作为线性规划的一种推广，是一类求解受约束于仿射集和半正定矩阵的交集 的凸规划问题。 1 9 6 3 年，b e l m a n 和f a n l l 5 】第一次构造了一个半定规划问题。接着半定规划在 一些具体领域当中得到了应用。而在五、六十年代线性规划的高效的单纯形法的 提出极大的促进了线性规划的发展。半定规划无法使用单纯形法，当时也没有发 现比较高效的算法，其发展受到了一定的影响。而在随后的研究中，研究人员提 出了半定规划有比较好的应用，如：d o n a t h 和h u f f m a n 1 6 j 、c u l l u m ，d o n a t h 和 w o l f e 1 7 】等发现可以把一些难的图分割问题转化成为一个特征值优化的问题来求 解。1 9 7 9 年l o v a s z l l 8 l 发现可以将图的s h a n n o n 容量的上界的问题转化成为求解半 定规划的问题。研究半定规划的高效的算法是非常有必要的。直到内点算法的提 出，这一问题才得到了较好的解决。 1 9 8 4 年，k a r m a r k a r i z 7 1 提出了线性规划的内点算法。该算法起源于之前的椭圆 算法，他们都具有理论的多项式复杂度。而与椭圆算法不同的是：内点算法在实 践中也非常的高效。k a r m a r k a r 的文章在当时引起了轰动，受到了广泛的关注。内 点算法也得到了广泛而深入的研究。1 9 8 4 年到1 9 9 7 年期间，线性规划的内点算法 2 半定规划的内点算法 发展到了非常完善的程度。 1 9 8 8 年，n e s t e r o v 和n e m i r o v s k y 3 0 , 3 2 基于对具有自协调性质的障碍函数的研 究发现：内点法原则上可以运用到一切凸优化问题。半定规划也属于凸优化问题， 因此也能够使用内点算法。1 9 9 2 年，n e s t e r o v 、n e m i r o v s k y l 3 1 3 2 1 、a l i z a d e h 【2 2 2 3 】 与k a m a t h 、k a r m a r k a r 独立的把线性规划的内点算法推广到了半定规划中。半定 规划的内点算法同样保留了线性规划的内点算法的在理论上具有多项式复杂度、 在实际计算中也有很好的效率的这一特点。半定规划的内点算法的诞生，使得半 定规划也具有了相对高效的算法，极大的促进了半定规划的发展，使得半定规划 进入了一个飞速发展的崭新阶段。同时内点算法也成为求解中、小规模半定规划 问题的最主要的算法。国际上也涌现了一批半定规划专家，如n e s t e r o v 、 n e m i r o v s k y 、a 1 i z a d e h 、t o d d 3 4 , 5 4 】、b o y d l 2 4 1 、f l e t c h e r 等等。 1 9 9 5 年以前提出的内点算法大多需要严格可行的原一对偶初始点，也被称为可 行内点算法。然而大多数问题都事先并不知道严格可行的初始点，并且往往很难 得到这样的点。同时可行内点算法要求迭代过程中始终保持可行性。于是并不要 求初始点严格可行的不可行内点算法引起了人们的兴趣。9 0 年代中期开始，不可 行内点算法逐渐开始兴起并得到了广泛的研究。最早提出不可行内点算法的是 k o j i m a ，s h i n d o h 和h a r a 【4 3 。，近十几年来的研究证实：原始一对偶内点法，尤其是 不可行内点法是解半定规划的相当有效的算法，并且这些算法存在多项式复杂度 结果【4 4 , 4 5 , 4 6 1 。 半定规划分为线性半定规划和非线性半定规划。当目标函数为线性函数，可 行域为线性约束时，称之为线性半定规划，其余的都称为非线性半定规划。本文 研究的是线性半定规划。 半定规划在组合优化问题【2 2 2 3 】、近似理论、系统和控制理论【2 4 1 、特征值优化【17 1 、 滤波器的设计和移动通信【2 6 1 等机械和电子工程3 3 1 等方面有着广泛的应用，日益 受到人们的关注。总之，不管从理论分析还是从实际应用的角度来说对半定规划 的研究都有着重要的意义。 1 1 2 本文用到的符号及术语： 只”，r ”+ ，r ”+ + 分别代表r 维空间，非负r 维空间，正刀维空间。 r “”代表所有m r 阶矩阵所形成的矩阵空间。 s ”，s ”+ ，s ”+ + 分别代表刀甩对称矩阵，半正定矩阵，正定矩阵锥。 ，代表刀以单位矩阵。 表示矩阵的f r o b e n i u s 范数。 对任意对称矩阵彳，b ，引入偏序符号“三9 9 9 其中彳 b 表示彳一b 为半正定矩 阵，彳 _ b 表示彳一b 为正定矩阵。 第一章绪论 ! 对任意9 s ”+ + ，9 z 表示矩阵9 的平方根，即若q 2 = p ，则即= q 若a 为一个向量，则丑表示该向量的第f 个分量，即九= ( ，如，九) r 。对角 元素分别为九的对角矩阵可表示为妣g ( ，如，九) 或者咖( a ) 对于任意的彳b r “”，我们定义它们的迹内积为： 彳b = ( 彳，b ) = 乃( 彳r b ) = ，j = l 对任意矩阵y s ”+ + ，用九( 矿) 表示矩阵的特征值所形成的玎维向量，其中y 的 特征值按单调不增的顺序排列，即a ( y ) 如( y ) 九( 矿) 对任意矩阵m ，仃，( 矿) 仃2 ( y ) 仃。( 矿) 表示矩阵m 的奇异值，易知，若m 为 对称矩阵，则有q ( y ) = l 凡( 矿) i ，f _ 1 ，刀 i 2 半定规划的基本理论 1 2 i 半定规划的基本模型 半定规划是线性规划的推广，是一类求解受约束于仿射集和半正定矩阵的交 集的凸规划问题。其约束条件是非线性、非光滑的，因而是一个非光滑的凸优化 问题。 半定规划( s d p ) 的标准形式2 9 ，3 6 1 为 m j n c x = t r ( c x ) = ( c ，x ) ( 尸) s j 4 x = r r ( 4 x ) = 6 f ，f = 1 ，m ( 卜1 ) x q 利用l a g r a n g e 方法可以得到半定规划问题的对偶问题的标准形式为 m a xb r y ( d ) j j 只4 + s = c ( 1 2 ) i = 1 s - 0 y r ” 其中，向量6 = ( 6 l ，5 2 ，k ) 。r ”，矩阵c s ”以及4 s ”( 扛1 ，m ) 为已知对 称矩阵；而x 祥和( y ，s ) r ”x 霹分别为原问题和对偶问题的变量矩阵。x 三0 即表示x 为半正定矩阵。 引入线性算子a ：s ”一r ”满足 a x = ( 4 x ，4 x ，以x ) 则a 的伴随算子a r ：r ”一s ”满足 4 半定规划的内点算法 a 7 y = 只4 根据伴随算子的定义，线性算子a 和a r 应当满足：对任意x s ”，y r ”， 有( 瞄，y - - ( x ，a r y ) 成立实际上 ( 蛳) - ( ) = 善删= 乃悻= l ”4 ) = ( x , a r y ) 则半定规划的原问题和对偶问题可表示为 r a i n c x = v r ( c x ) = ( c ，x ) ( 尸) s t a x = 6( 卜3 ) x - 0 ( d ) m a xb r y s 1 a 1y + s = c s 0 ，y r ” ( 1 - 4 ) 定义1 1若x 与( y ，s ) 分别满足原始问题( 尸) 和对偶问题( d ) 的约束条件，则 x 与( y ，s ) 分别称为原始问题( p ) 和对偶问题( d ) 的可行解。 原一对偶可行集( 即可行解的集合) 可分别用p 和d 表示： + p ：= i x t r ( a , x ) = 6 j ( f = 1 ，m ) ，x 三o d ：= s ) l y ，4 + s = c ，s 三o ，y r m 1 = 1 记p 和d 分别为原始问题( 尸) 和对偶问题( d ) 的最优值，则易得： p ：= i 妒 乃( c x ) i 乃( 4 x ) = 包( 汪1 ，m ) ，x 掣) d ：= s u p 6r y l 只4 + s = c ，s 掣，y r m | ) y pi = l 类似地，尸和d 分别表示最优集( 即最优解集) ，则： 尸：= x p l t r ( c x ) = p 事 d ：= ( s ，y ) d 1 6 r y = 扩) 记，= ( x ，y ，s ) p xd x s = o 表示对偶间隙为零的最优解集。 我们约定：如果原始问题( 尸) 是无界的，记作p = - - - o o ，如果原始问题( 尸) 是不 可行的，记作p = 0 0 ( p = ) ；同理，若对偶问题( d ) 是无界的，记作d = o o ，若 对偶问题( d ) 是不可行的，记为d = - - o o ( d = 妒) 原始问题( 尸) 是可解的，若p + 驴同理，对偶问题( d ) 是可解的，若d 在后面的所有内容中我们均用到如下假设1 - 2 ( 两条假设) ： 假设1 2 i 3 6 1 矩阵4 ( i = 1 ，m ) 是线性无关的。 第一章绪论 在假设下，对一个已知对偶可行的问题来说，s ，y 是相互唯一确定的。即 假设允许我们在后面用y d 或s d 来代替( y ，s ) d 。这一假设本质上与线性 规划中假设约束矩阵是满秩的是等价的。 1 2 2 半定规划的对偶理论 半定规划作为线性规划的推广，与线性规划一样具有对偶理论，但是由于其 本身的特点，其对偶理论比线性规划的对偶理论弱。为了叙述的方便，我们首先 直接给出两个引理以及对偶间隙的定义。 弓i 理1 3 t 4 0 】设a ，b s ”且a - 0 ，b - 0 ，则彳b 0 引理1 4 【4 0 】设么，b s ”且a _ 0 ，b - 0 ，则彳b ：o 当且仅当a b = 0 定义1 5 f 3 6 1 ( 对偶间隙) 设x p 和( j ，s ) d ，值t r ( c x ) 一b t y 称为原始问题 ( 尸) 和对偶问题( d ) 在( x ，y ，s ) 处的对偶间隙。 定理1 6 【3 6 ，4 川( 弱对偶定理) 设( x ，y ，s ) 为原始问题( p ) 和对偶f 口- j n ( d ) 的可 行解，可得 t r ( c e ) 一b7 y 0 事实上 。 。 ，肘、 m t r ( c x ) - b 7 y = t r li 只4 + sl xi z y , m a , x = t r ( s x ) o 旧 。_ 定义1 7 若p = d ，则称原始问题( 尸) 和对偶问题( d ) 为完全对偶的。 由弱对偶性，若对x p 和( y ，s ) d 有对偶间隙t k c x ) 一b7 y = t r ( s x ) = 0 ，则 x p 和( j ，s ) d 即是( p ) 和( d ) 的最优解。但是在最优解( x ，y ，s ) 处未必有 t r ( c x ) 一b t y = 0 。由此引入严格可行解的概念 定义1 8 若x 为( p ) 的可行解，且x 10 ，则称x 为( 尸) 的严格可行解若( 尸) 具有严格可行解，则称( p ) 严格可行；若s 为( d ) 的可行解，且s _ o ，则称s 为( d ) 的严格可行解若( d ) 具有严格可行解，则称( d ) 严格可行 定理1 9 【2 3 ，3 2 1 ( 强对偶定理) 设d - o o ) ，且已知( d ) ( 或( p ) ) 是严格可行的，则p ( 或d 妒) 且p = d 根据定理1 9 ，我们可以得到一个有用的推论，此推论形成了强对偶性的一个 充分条件。 推论1 1 0 3 6 1 设原始问题( p ) 和对偶问题( 研严格可行，则 p = d 且p 咖，d 西 在后面的内容中，我们也用到了如下的假设： 假设1 2 【3 6 1 存在x p 和s d ，满足x - 0 和s - 0 。 假设是关于严格可行性的假设。在假设的基础上，我们直接得到( p ) 、( d ) 严格可行。再根据推论1 1 0 可得到结论p = d 。故这一假设也被称作是强可行 6 半定规划的内点算法 性，s l a t e r 约束条件或者s l a t e r 规范条件或者内点假设。该假设与凸优化中s l a t e r 规范的通常定义具有一致性啪1 。 假设原始问题( 尸) 和对偶问题( d ) 严格可行，从而存在x p 和( y ，s ) d 满 足： t r ( c x ) = b r y = p = d ，t r ( c x ) 一b7 y = t r ( s x ) = x s = 0 根据引理1 4 可得：x s = 0 我们称x s = 0 为互补松弛条件，它可以看成是线 性规划互补松弛条件的推广。 综上我们可以得到原始问题( 尸) 和对偶问题( d ) 的最优性条件： 假设( p ) 和( d ) 严格可行，则下列各命题等价： ( 1 ) ( 尸) 具有最优解f ( 2 ) ( d ) 具有最优解( j ，s ) ( 3 ) 最优性条件 t r ( a , x ) = 包，x o ，i = 1 ，m 只4 + s = c ，s o ，= 1 船= 0 有解( x + ，j ，s ) 。系统( 1 5 ) 就是半定规划的k k t 条件。 1 3 半定规划的算法 ( 1 - 5 ) 半定规划的算法主要分为内点算法和非内点算法。内点算法由于其多项式复 杂度以及在实践中良好的效率而成为现今半定规划的主要的算法。随着研究的不 断深入，近年来陆续又发展起来一些新的算法，最常见的有光滑化的谱从方法、 基于梯度信息的非线性规划方法、割平面法以及光滑化方法等。下面我们首先介 绍一下内点算法的一般框架，后面对其他的非内点算法也作出简要的说明。 1 3 1 内点算法 t 线性规划的内点算法或多或少都起源于k h a c h i y a n 在1 9 7 9 年提出的椭圆方 法。虽然椭圆方法在理论上具有多项式复杂度，但是将椭圆方法应用到实际问题 的计算中的运算效果却非常差【3 7 1 。1 9 8 4 年k a r m a r k a r 2 7 1 取得了突破性的进展，提 出了线性规划的内点算法，这种算法不但在理论中具有多项式复杂度，而且在实 际计算中也具有非常良好的效率。内点算法也迅速成为线性规划的比较活跃的研 第一章绪论 7 究方向。1 9 8 8 年n e s t e r o v 、n e m i r o v s k i 3 0 3 2 1 取得了较大成果，他们基于对具有自 协调性质的障碍函数的研究，证实了内点法原则上可以运用到一切凸优化问题。 n e s t e r o v 和n e m i r o v s k i 证实了每一个凸集都存在一个自协调障碍函数，虽然通常 它们的自协调函数难以计算。而半定规划作为一种凸优化问题，其自协调函数易 于计算，所以内点法适用。于是线性规划的内点算法被平移到了半定规划中。经 过多年的发展，现在半定规划的内点算法的理论和算法已经相当的完善，使得内 点算法成为求解中、小规模半定规划问题非常有效的算法。现在已有内点算法的 通用软件包。 内点算法的基本思想是将约束优化问题转化为无约束优化问题。这种转化常 用的方法就是在目标函数中加一个惩罚项，惩罚项在可行域的内部的值非常小， 而在接近可行域的边界的时候，惩罚项将变得非常大，从而使迭代点列始终保持 在可行域内。内点算法从其下降方式来分主要有：路径跟踪算法、势下降算法等， 从其产生的迭代点列是否满足线性约束可分为：可行与不可行内点算法，从其处 理的规划可分为：原内点算法、对偶调比内点算法和原对偶内点算法。 下面采用对数函数为惩罚项建立原一对偶可行内点算法： 考虑最优化问题 n f m r r ( x s ) - pl o gd e t ( x s ) s j z r ( a i x ) = 6 ，x - o ，f _ 1 ，2 ，m ( 1 - 6 ) ! 乃4 + s = c ，s - 0 i = 1 根据文献【3 6 】可知，该的最优解存在且唯一，并且其最优解一定在半正定锥的内部。 利用l a g r a n g e 乘子法可得的最优性条件1 ，即k k t 条件为： 乃( 4 x ) = 6 f ，x - 0 ，江l ，2 ，m 三l 只4 + s = c ，s - 0 ( 1 - 7 ) f = l x s = u 其中( 1 7 ) 第一个条件是原始问题( p ) 的严格可行解的条件；第二个条件是对偶问题 ( d ) 的严格可行解的条件；第三个条件当0 时相应于原始问题( 尸) 和对偶问题 ( d ) 的最优性条件( 1 - 5 ) 的互补松弛条件x s = 0 。( 1 7 ) 条件不仅是( 1 6 ) 最优解的必 要条件而且是其充分条件。当0 时这些条件可以看作是对原始问题( p ) 和对偶 问题( d ) 的最优性条件( 1 - 5 ) 的扰动。 对于固定的卢，系统( 1 - 7 ) 的解( 彳，y ，s ) 存在且唯一，定义为( x p ，y ，s 。) 。x 。和 ( y 驴s 。) 分别为原始问题( 1 - 1 ) 和对偶问题( 1 - 2 ) 的一个可行解，且其对偶间隙为力。 对“ 0 ，设r 为系统( 1 7 ) 的解构成的曲线或路径，即 i = ( ，y 。，s 。) l ( x 。，y p ，s 。) 解系统( 1 7 ) ，对j l l 0 半定规划的内点算法 我们称r 为中心路径。这是一条光滑曲线。下面的定理给出了如下结论：当专0 时，( 扎，y u ，瓯) 存在聚点，且若( x ，y ，s ) 是( 以，y u ，乱) 的聚点，那么 彳，( y ，s ) ，( x + ，y ，s ) 分别为原始f 1 n ( 1 1 ) 和对偶问题( 1 2 ) 和原对偶f j 题i ( 1 6 ) 的 最优解。为此，我们首先直接给出两个引理，具体证明详见相关参考文献。 引理1 1 1 令a ，b 蹬，则 k ( 彳) k ( b ) t r ( a b ) = ( a ，b ) 刀k ( 么) k ( b ) 引理1 1 2 1 6 1 令x ，x w e x s ”i 乃( 4 x ) = 6 l ，f = l ，m ， 舯、 s 7 ，s s s ”i s = c - y a ，y e r ” ，则 t = l j ( x 一x ”，s 一s ) = 0 引理1 1 2 表明的是迭代方向的正交性。 定理1 1 3 【1 6 j 对给定序列 地) ，满足以 0 ，且当k 专佃时有心- - - y0 。当 心专0 时，( k ，瓯。) 二定存在聚点，且如果( x ，s ) 为( k ，) 的聚点，那么x 为原始问题( 1 - 1 ) 的最优解，s + 为对偶问题( 1 2 ) 的最优解。 证明：根据引理1 1 2 可知 o = ( k x 。，一s 。) = ( k ，瓯) 一( ，s 。) 一( x 0 瓯) + ( x 。，s 。) 由于( ，s p t ) = 毗， 则 ( k ，s 。) + ( x 。 ) = 胛p k + ( x 。，s 。) 根据引理1 1 1 可知 k ( k ) k 试( s 。) + k 缸( x 。) 九戤( ) ，z p k + ( x 。，s 。) 由于k ( s o ) o ，k 。( x 。) 0 ，而根据引理1 1 1 ， ，都是有界集，从而序列 ( k ，瓯) 必定存在聚点。又由于( k ，) = n i l 。，当k - - - + o o 时有以j o ，故 ( x ，s ) = 0 。证毕。 由于我们始终保持x - 0 ，s 0 ，即沿着可行域内部进行迭代。 原始对偶路径跟踪内点算法的基本思想是：令专0 ，迭代点将沿中心路径逼 近问题的最优解。对此类算法的分析关键在于三个方面：一是移动方向的选取； 二是步长的选取：三是要保证每一步迭代点均位于中心路径的某个邻域内。 首先分析移动的方向。考虑对如下非线性方程组1 ，竽山1 e ( x ，y ，s ) = ia 。y + s cl = 0 l x s j l l ，j 利用牛顿法求解，即设( 从，a y ，a s ) 为迭代点的移动方向，则由 第一章绪论 9 + 晖( 从，缈，a s ) 7 = o 得到如下的线性系统【2 3 】： 4 从= 岛一4 x ，f = l ，m 觚4 + 丛= c s 一只4 ( 卜8 ) j 掌ii = 1 蚁s + x 醛= 嘻i 一) ( s 若迭代点始终保持可行，则岛- 4 x = 0 ，f = 1 ，m ，c - s - y , 4 = o ，此时， ，；l 移动方向的选取就由如下系统确定： 4 似= 0 ，f = 1 ，m ， a y , 4 + 丛= o ， ( 1 9 ) i = 1 砖+ x z l s s = “s 一一x 在一般情况下，x ，s 是不可交换的，即x s s x 这样虽然解( 卜8 ) 或( 卜9 ) 得到的心虽然是对称的，但是赵不一定是对称的，这与下一步迭代需要x + a 从 必须是对称的矛盾。利用不同的对称技巧可以得到不同的迭代方向。其中主要有 n t 方向、h k m 方向、a h o 方向、k m 方向等。这些方向得到的似是对称的，z h a n g i 3 8 】 通过引入对称化算子： h a m ) = 专脚1 + ( p m p 一) 7 ) 统一了这些方向。则a x s + x 心= ，一船等价于h ，( x s + a j ( s + x a s ) = l a i 则如何更好的选取变换矩阵p 就成为半定规划研究中一个重要的课题。p 的选法 目前已知的有二十多种，但是从算法的性能，比如解的精确性，迭代次数即多项 式复杂性以及收敛速度等方面考虑，公认最好、最具有代表性的主要有三种选取 l 办法，分别是：取p = ，即得前面的a h o 方向【4 1 】；取p = 彳2 ，即得k m 方 l 1 i ， i 1 、一了 1 向【4 2 】；取尸：驴，即得h k m 方向【9 】；取p7 p ：w ，其中形= x jix t s x 7l 。x j ， l 即得n t 方向( 3 9 1 2 0 0 2 年左右p e n g 提出了自正则函数的概念并建立了基于自正则函数的求解线 性规划的原对偶内点算法【5 , 7 , 1 1 , 1 4 】，在算法中迭代方向与核函数妒( f ) 有关。y q b a i 等对此类方法进行了深入研究并此算法推广到了半定规划当中【2 ，3 ，4 , 1 0 , 1 2 , 1 3 1 。在本文 的第二章中主要是在文献 4 的基础上提出一个修正的核函数，此核函数并不是自 正则的函数，我们利用该核函数构建了算法的搜索方向，相应的建立基于此核函 数的原一对偶内点算法，并最终得到算法的复杂度结果。 其次考虑步长的选择。通常在取定方向的基础上，在所取方向上通过适当的 l o 半定规划的内点算法 线搜索策略来确定我们的步长。对方向和步长的确定都需要满足可行性要求，即 在可行域内部迭代。 下面给出内点算法的一般框架： 步骤0 给定误差限s 0 ，给定初始可行点( x 0r y o , s o ) 满足x o 卜0 ，s o 卜0 ， 令k = 0 ； 步骤1 选择“； 步骤2 解方程组 f ，a x l v f ( x ，y ，s ) l a yi = 一c ( x ，y ，s ) i a sj ，a x - 61 得到搜索方向( 从，a y k , a s ) ，其中吒( x ，y ，s ) = la r y + s ci ； i 船一j l l ，j 步骤