（基础数学专业论文）原始对偶内点法的几点研究.pdf

摘要 原始对偶内点法是优化算法中的一个热点课题，长期以来一直受到广泛的 关注并取得了很大的进展。内点法不但具有多项式复杂性，而且在实践中也是 很有效的。不可行内点法起始于分量都为正的个任意点，随着最优性的达到 可行性也随之达到。许多著名的软件都是使用不可行内点法，因而很有必要给 予继续关注。 本文第一章主要研究求解线性规划问题的f u l l - n e w t o n 步不可行内点算法， 该算法使用的是f u l l - n e w t o n 步，它的多项式复杂度跟现有的不可行内点法的复 杂度保持一致。每次迭代由一个可行步( 用于改善可行性) 和几个中心步( 用于拉 回到中心路径) 构成。这个算法由r o o s2 0 0 6 年最先提出，为了保持整个文章的 可读性，在1 2 节我们简单介绍r o o s 提出的f u l l - n e w t o n 步不可行内点法。我们 提出在f u l l - n e w t o n 步不可行内点算法中引入k e r n e l 函数，将经典的n e w t o n 方向 延伸到一个更普遍的情况。 第二章中，我们使用n e s t e r o v - t o d d 方向将第一章中解线性规划的原始对 偶内点法延伸到半定规划。众所周知，线性规划的原始对偶可行的内点法通 过使用n e s t e r o v - t o d d 方向很容易延伸到半定规划。本文考虑的是不可行问题， 在r o o s 的线性规划问题基础上，我们利用对数障碍函数的一些特性，成功地将 算法延伸到半定规划。 最后我们涉足非线性规划的内点法在第三章我们在u l b r i c h 的工作的基础 上，结合内点方法提出一个3 维的f i l t e r 算法该算法与原有算法相比，充分利用 t f i l t e r 框架的宽容性，使得所要考虑的迭代点的范围和搜索准则放得更宽。 关键词f u l l - n e w t o n 步，f u l ln e s t e r o v - t o d d 步，多项式复杂性，不可行内点 算法，原始对偶内点法 a b s t r a c t p r i m a l d u a li n t e r i o r - p o i n tm e t h o d sa r eo n eo fh o ti s s u e si no p t i m i z a t i o n e x t e n s i v ea t t e n t i o nh a sb e e np a i da n dg r e a tp r o g r e s sh a sb e e nm a d ef o ral o n g t i m e i n t e r i o r p o i n tm e t h o d sn o to n l yh a v ep o l y n o m i a lc o m p l e x i t y , b u ta r ea l s o h i g h l ye f f i c i e n ti np r a c t i c e i 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 d ss t a r tw i t ha na r b i - t r a r yp o s i t i v ep o i n ta n df e a s i b i l i t yc a nb er e a c h e da so p t i m i z a t i o ni sa p p r o a c h e d m o s to ft h ee x i s t i n gs o f t w a r ep a c k a g e su s ei 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 d s ，t h u s i ti sw o r t hb e i n gp a i dm u c ha t t e n t i o n t h e t o p i co ft h i sp a p e ri so nf u l l - n e w t o ni 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 m s t h ea l g o r i t h ma l w a y st a k e sf u l l n e w t o ns t e p sa n di t sr e s u l to fp o l y n o m i a lc o m - p l e x i t yc o i n c i d e sw i t ht h eb e s tk n o w nr e s u l tf o ri 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 m s e a c hi t e r a t i o nc o n s i s t so faf e a s i b i l i t ys t e p ( u s e df o ri m p r o v i n gt h ef e a - s i b i l i t y ) a n ds e v e r a lc e n t e r i n gs t e p s ( u s e df o rt a k i n gi t e r a t e sb a c kt ot h ec e n t r a l p a t h ) t h ea l g o r i t h mw a so r i g i n a l l yp r e s e n t e db yc r o o si n2 0 0 6 i no r d e rt o m a k et h ew h o l ep a p e rr e a d a b l e ，w ei n t r o d u c et h eo r i g i n a lf u l l - n e w t o ni n f e a s i b l e i n t e r i o r - p o i n ta l g o r i t h mi ns e c t i o n1 2 i nd e t a i l s o u rk e yw o r kf o rt h i sc h a p t e r i st h a tw ei n t r o d u c eak e r n e lf u n c t i o ni nt h ef u l l - n e w t o ni n f e a s i b l ei n t e r i o r - p o i n t a l g o r i t h m ，a n dw eg i v es o m et h e o r e t i c a la n a l y s i sf o rt h en e wa l g o r i t h m i nc h a p t e r2 ，w em a i n l yf o c u so nt h ef u l l - n e w t o ni n f e a s i b l ei n t e r i o r - p o i n t a l g o r i t h mi nt h ec a s eo fs e m i d e f i n i t ep r o g r a m m i n g w eu s en e s t e r o v - t o d dd i - r e c t i o n st oe x t e n dt h ef u l l - n e w t o ni 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 rl i n e a r p r o g r a m m i n gt os e m i d e f i n i t ep r o g r a m m i n g i ti sw e l lk n o w n t h a tf e a s i b l ep 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 m sf o rl i n e a rp r o g r a m m i n gc a nb ee x t e n d e de a s i l yt o s e m i d e f i n i t ep r o g r a m m i n gb yu s i n gn e s t e r o v - t o d dd i r e c t i o n s h e r ew ed e a lw i t h i 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 d s b a s e do i lr o o s w o r k ，w et a k ea d v a n t a g eo f 8 0 m ep r o p e r t i e so ft h el o g a r i t h m i cb a r r i e rf u n c t i o na n ds u c c e e di ne x t e n d i n gt h e a l g o r i t h mt os e m i d e f i n i t ep r o g r a m m i n g f i n a l l y , w ef o c u so ni n t e r i o rp o i n tm e t h o d sf o rn o n l i n e a rp r o g r a m m i n g i n c h a p t e r3 ，b a s e do i lt h ea l g o r i t h mo fu l b r i c h ，w ed e v e l o pa3 df i l t e ra l g o r i t h m b yc o m b i n i n gi n t e r i o r p o i n tm e t h o d s c o m p a r i n gw i t ht h eo r i g i n a la l g o r i t h m ， 一l l t h en e wa l g o r i t h mi n h e r i t st h ep r o p e r t i e so ff i l t e r - t y p em e t h o d s k e yw o r d s f u l l - n e w t o ns t e p ，f u l ln e s t e r o v - t o d ds t e p ，p o l y n o m i a lc o m - p l e x i t y , i 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 d ，p r i m a l - d u a li n t e r i o r p o i n tm e t h o d 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已经发表 或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了谢意。 研究生签名： 日期： 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版；有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅；有 权将学位论文的内容编入有关数据库进行检索；有权将学位论文的标题和摘要 汇编出版。保密的学位论文在解密后适用本规定。 研究生签名： 日期： 第一章解线性规划问题的f u l l n e w t o n 步不可行内点算法 第一章解线性规划问题的f u l l - n e w t o n 步不可行内点 1 1引言 算法 解线性规划问题的内点法是1 9 8 4 年由k a r m a r k a r 9 最先提出来的它不但具 有多项式复杂性，而且在实际中也有很高的效率内点法分为可行内点法和不 可行内点法可行内点法要求开始于一个严格可行的内点并且在迭代过程中一 直保持可行性寻找一个严格可行的开始点的一个比较优秀的方法是通过引入 人工变量并使用自对偶嵌入模型这个技巧最初由y e 等 2 2 1 提出来的许多著名 的商业软件包，例如，m o s e k 与s e d u m i 也是基于使用自对偶模型 不可行内点算法开始于分量为正的一个任意点，随着最优性的达到可行性 也同时达到第一个不可行内点法是l 主l l u s t i g 1 2 和t a n a b e 2 1 提出的全局收 敛性是m k o j i m a 等【1o 】给出的m i z u n o 1 3 i j i x y - 个原始对偶不可行内点算法 并且证明了算法的全局收敛性目前的原始对偶不可行内点法的性能高度依赖 初始点的选取，这就使这些算法与使用自对偶嵌入技巧的那些方法相比缺少了 一些稳健性 通常我们考虑下面标准形式的线性规划问题 ( p ) 及其对偶问题 ( d ) m i n c t x ：a x = b ，z o ) ， m 觚 矿y ：a t y4 - s = c ，s o 一 这里a 妒舶，6 ，y r m 及c ，z ，s p 不失一般性，假i 发r a n k ( a ) = m 对于不可行内点法，大家最熟悉的迭代界是 。( 山g 型盟坐掣监型型 见( m i z u n o 1 3 】) ，这里护，y o ，8 0 表示初始迭代点，而6 一a z o 与c a ? y o s o 分 别为初始的原始残差与对偶残差向量，e 是算法终止时的对偶间隙以及残差向 量范数的一个上界要得到这个结果，需要假设存在一个最优解( z + ，y + ，s 4 ) 满 足l i ( z + ；s 4 ) l l o o ( ，以及初始迭代满足( z o ，y o ，s o ) = ( ( e ，0 ，e ) ，其中( 是预先给定 的常数 直n 2 0 0 3 年，所有原始对偶不可行内点法中使用的搜索方向都是从下面的 线性系统得出来的 a z = b a x r 一十 = c a 丁y 一(1-12a a y a say812 ) 1 += c 一 1 一 (一) s a z + x a s5 弘e x 8 ， 也就是说产生所谓的原始对偶n e w t o n 搜索方向z ，a y ，a s 最近s a l a h i 等f 1 9 1 使用所谓的自正则度量函数为不可行内点法定义一个新的搜索方向 他们只是对上面系统的第三个方程作了修改，算法没有能对迭代界( 1 1 1 ) 进行 改进 在介绍本文的思想之前我们对不可行内点法作一些点评在可行的内点法 中，迭代的可行性是事先给定的，而最终目的是得到满足最优性的迭代点有一 个很出名的内点算法试图迭代一步就达到最优，这就是仿射尺度法但是熟悉 内点法的人都知道这个算法不是一个多项式时间算法最近二十年的研究表明， 为了得到一个多项式时间算法，不应该太贪婪而应该采用一个搜索方向，朝最 优性的方向慢慢移动只有这样才能充分利用n e w t o n 法的有效性，这就是内点 法的驱动力 在不可行内点法中，迭代都是不可行的，除了需要达到最优性还需要朝可 行性方向努力这可以通过选取m ( 1 1 2 ) 定义的搜索方向反映出来因为，当 从z 移n z + ：= z + a x ，新的迭代点矿满足原始可行性约束，而可能不满足非 负约束事实上，通常矿会有负分量，而为了保持迭代为正，被迫采用形式 为矿：= z + q z 的阻尼步，这里o z 0 有解，则对所有的肛 0 都有解，并且这个解是唯一 的有解的充要条件是( 尸) 和( d ) 满足内点条件( i p c ) ：( p ) 有个可行解z o 同 一3 1 2 问题和算法 时( d ) 有一个可行解( y ，s ) 满足5 0 如果i p c 满足，则用( z ( 弘) ，秒( p ) ，s ( p ) ) 表 示系统( 1 2 3 ) 的解，称之为( p ) 和( d ) 的少中心所有胪中心组成的集合称 为( p ) 和( d ) 的中心路径随着卢趋向于0 ，z ( p ) ，秒( p ) 和s ( 肛) 收敛于( 尸) 和( d ) 的 最优解当然系统( 1 2 3 ) 仍然难以求解，但是通过n e w t o n 方法，很容易找到近似 解 接下来描述当p 固定时求解( 1 2 3 ) 的n e w t o n 方法给定任何原始可行 解z 0 和对偶可行解可及8 0 ，需要得到满足下面方程组的偏离量a x ， a y 和a s ： a ( z + z ) = b ， a r ( y + a y ) + s + a s = c ， ( z + z ) ( s 十a s ) = 肛e 忽略第三个方程中的二次项a x a s ，可以得到未知数为z ，a y ，a s 的线性方程 组： a a x = b a x a r 可+ a s = c a t y s ，( 1 - 2 4 ) s a x + x a s = “e z s 因为a 满秩，向量z ，s 都是正的，可以证明系统( 1 2 - 4 ) 的系数矩阵是非奇异的 因而这个系统唯一定义了搜索方向z ，a y ，a s 这些搜索方向用于现有的原 始对偶( 包括可行和不可行) 内点法，并命名为n e 吼o n 方向如果z 是原始可行 j l ( y ，s ) 是对偶可行，则6 一a x = o 且c a t y s = 0 ，这时上面的系统简化为 a a x = 0 铆十a s = 0 ，( 1 - 2 5 ) s a x + x a s 。p e z s ， 这就为可行的原始对偶内点法定义了常用的搜索方向 新的迭代由下面的公式给出， z + ：= o 十z ， y + ：= y + a y s + ：= s + a s 4 第一章解线性规划问题的f u l l n e w t o n 步不可行内点算法 注意到z 属于a m 零空间，而s 属于a m 行空间这说明z 与s 是正交的，即， ( a x ) 丁a s = 0 接下来我们给出一个很重要的性质，即一个f u l l - n e w t o n 步之后的对偶间隙 与p 中心处的对偶间隙的值一致，为n p 引理1 2 1( 1 7 ，l e m m ai i 4 6 ) 一个原始对4 $ i n e w t o n 步之后，可以得 到( z + ) t s + = n p 假定预先给定了一个原始可行的z o 和对偶可行的( 矿，s o ) ，其中护，8 0 0 ，对某 个肛= 矿，它们各自靠近z ( p ) 和( 可( p ) ，s ( 肛) ) ，我们可以在0 ( 而1 0 9 ( n e ) ) 次迭代 内为图1 1 中的算法找到一个e 解 原始对偶可行的内点法 i n p u t ： 精度参数 0 ： 障碍更新参数0 ，0 o 且满 j 匕t 8 = n p 并且令6 ：= 6 ( z ，s ；p ) ，p + ：= ( 1 一目) p 则 怖；2 卸叫n 南 引理1 2 3 ( 1 7 ，l e m m ai i 4 9 ) 如鄹：= 6 ( z ，s ；p ) 1 ，则原始对 偶n e w t o n 步是可行的，即矿与s + 是非负的此外，如果6 0 ，y o 和8 0 0 ，对某个正数p o ，满足z 0 8 0 = p o e 对于满足0 1 的任意，考虑如下定义 的扰动问题r ， ( r ) m i n ( c 一( c a t 可。一s o ) ) r z ：a x = b 一( 6 一a x o ) ，z o ) ， 以及对偶问题( 仇) ： ( d p )m a x ( ( b 一( 6 一a x o ) ? y ) ：a t y + 8 = c 一( c a r y o s o ) ， s o ) 注意到，如果= 1 ，则z = x 0 是( r ) 的一个严格可行解，( y o ，8 0 ) 是( 仇) 的一个严 格可行解因而断定，如果= 1 ，则( 只) 和( d ，) 满足内点条件( i p c ) 引理1 2 5 ( 1 s ，l e m m a3 1 】) 原来的问题( p ) 与( d ) 可行的充分必要条件是 对满足o 0 而在第一次迭代开始时，这是成立的 现在描述一下算法中的一次迭代过程假定对某个p ( 0 ，弘o 】，能够 得到z ，y ，s 满足= 肛“o 时的可行条件( 1 2 7 ) 和( 1 2 8 ) ，并且满足z t s = 几p ， 6 ( z ，5 ；p ) 7 - 严格地说，可以这样描述算法中的一次迭代：将p 减少到( 1 一目) p ， 其中口( 0 ，1 ) ，然后用矿取代弘，矿= i t + 取代，通过( 1 2 7 ) ，( 1 2 8 ) 求解得到 新的迭代矿，y + ，s + ，同时满足，8 = n 矿，j ( 矿，s + ；矿) 7 ，其中矿= ( 1 一口) 更准确地说，我们的首要目标是让迭代点( z ，y ，s ) 对2 + = 矿是可行 的，并且靠近胪中心( z ( p ，矿) ，可( p ，矿) ，s ( 肛，矿) ) 如果能够使新的迭代满 足j ( z ，s ；p + ) 1 以，则通过在( r + ) ，( 玩+ ) 的p + 一中心处执行一个n e w t o n 步， 可以很容易地让迭代点对问题( r + ) ，( d p + ) 来说是可行的，并且6 ( z ，s ；矿) 7 将初始的原始残差和对偶残差用r 2 和r ：表示，即， 7 2 = b 一4 z o ， 0 = c a r y o 一8 0 则问题( r ) ，( d ) a o 可行条件可表示为 a x = b 一7 2 ，z 0 ， a r y + s = c 一7 ：，s 0 问题( b + ) ，( d + ) 的可行条件可表示为 a x = 6 一+ r o ，z 0 ， a r 可+ 8 = c 一j + 0 ，8 0 为了使迭代相对( r + ) ，( d p + ) 是可行的，需要满足如下条件的搜索方 向，z ，a f y ，a f s ： a ( z + a ，z ) = b + r 2 ，z 0 ， a r ( 可十a ，y ) + ( s + a f s ) = c i + 0 ， s 0 因为z 对( r ) 是可行的，( y ，s ) 对( d p ) 是可行的，可以推出，z ，可，a i s 应该满足 a a ，z = ( b a x ) 一+ r 2 = r ：一+ 7 2 = p r 2 ， 7 ， 1 2 问题和算法 a 丁a ，y + a i s = ( c a t y s ) 一+ r ：= 7 ：一z ，+ r ：= 口r ： 因而用下面的系统来定义搜索方a f x ，a f y ，a f s ： 新的迭代为 a a s x = o u r o ， a t a f y + a f s = o u r o ， s a l x + x a y s = p e z 8 ， x f = z + a j x ， y y = y + a i y s i = s + a i s 可以推断一个可行步之后，迭代将满足= 矿时的( 1 2 7 ) 和( 1 2 8 ) 分析中最难 的部分能够得到保证，即一个可行步之后迭代满足5 ( z s ，s l ；矿) 1 、，侄 可行步之后，为了使迭代另外满足z 丁8 = n 肛及5 ( x ，s ；矿) 丁，这就需要执 行中心步通过使用推论1 2 4 ，能够轻松地得到中心步所要求的次数因为，假 设6 ( 矿，s + ；矿) 1 、2 ，经过k 步之后，将会有迭代( z ，y ，s ) 相对( 所) ，( d v + ) 仍 旧是可行的，并且 所以k 应该满足 s ；矿) ( 砺1 ) 扩 ( 焉1 ) 2 r ， 、z k 1 0 9 2 ( 1 。9 2 去) 图1 2 给出了算法更为正式的描述 一8 一 ( 1 - 2 1 0 ) 第一章解线性规划问题的f u l l - n e w t o n 步不可行内点算法 原始对偶不可行的内点法 i n p u t ： 精度参数 o ； 障碍更新参数臼，0 0 ；y ：= y o ；s ：= 8 0 0 ；x o s o2p o e ；肛：= 肛o ； w h i l em a x z r s ，i i b 一4 z i l ，i i c a t y s l l d o - b e g i n 可行步： ( z ，y ，s ) ：= ( z ，y ，s ) + ( a f x ，a y ，a s s ) ； p 一更新： ，上：= ( 1 一口) p ； 中心步： w h i l e6 ( z ，s ；p ) td o ( z ，y ，s ) ：= ( z ，y ，s ) + ( z ，a y ，s ) ； e n dw h i l e e n d e n d 图1 2 注意每次迭代之后残差和对偶间隙都减少( 1 一p ) 倍如果残差的范数和对 偶间隙都小于精度参数e ，则算法终止下面给出k e r n e l 函数的定义 定义1 2 6 二次可微函数砂( ) ：( 0 ，。) _ 【0 ，o o ) 称为k e r n e l 函数，如果有 砂( 1 ) = 0 ，妒7 ( 1 ) = 0 ，砂0 ) 0 ，觇 0 定义 ：= 竽，：= 学，( 1 - 2 - 1 1 ) 其中 由( 1 2 6 ) 定义 k e r n e l 函数最初由p e n g 1 6 】引进，近几年得到迸一步研究，参看a m i n i 【1 】j b a i 2 】，s a l a h i 【2 0 等。 1 2 问题和算法 定义搜索方向，z ，秒和，s 的系统，能够按照尺度化的搜索方向d f 和d f 表 示如下： a d ! = o u r o ， a t 掣+ ：o u r s - i t 。， “ 。 d ! + d ；= 口一u ， 其中 a = a v x ，v = d i a g ( ) ，x = d i a g ( x ) 注意系统中的第三个方程的右边是下面对数障碍函数的负梯度方向： 皿( t ，) ：= 矽( 让) ， i = 1 瓯瓦 钆2 ， vp 而它的k e r n e l 函数是 妒 ) = 去( 2 1 ) 一l o g t 本文中的可行步是标准n e w t o n 方向的一个小的修改，由下面的系统定义来确定： 五= o u r o ， a t 竽+ ：o l , v s - l r o ，( 1 - 2 - 1 2 ) + d ；= 一v 西k e r ( 口) ， 这里圣k e r ( u ) 的k e r n e l 函数是 k e r ( 蚍= 三( t 2 - 1 ) + 等 ，l k k e r n e l i n 数的定义可以看出，渤0 ，e k e r ( 艺) 确实是一个k e r n e l 函数因 为矽k e r ( t ) = t t 一，n n ( 1 2 1 2 ) 的第三个方程能写成 d ! + d ；= 口一p 一 ( 1 - 2 1 3 ) 定义 仃( z ，s ；p ) ：= 矿( u ) ：= l v c k e r ( 口) l i = - p - v i i ( 1 2 1 4 ) 注意到盯( 口) = o 当且仅当口= e ，于是口( ) 也是一个合适的度量下面的结果说明 渤( 0 ，1 】，度量盯( u ) 总是小于度量6 ( 可) 特别要说明的是尽管我们使用了一个 新的k e r n e l n 数来定义可行步，但是并不抛弃对数障碍函数 第一章解线性规划问题的f u l l n e w t o n 步不可行内点算法 弓i 理1 2 7 对任何t 0 ，可以证明 l t p t l l t t - z l ，p ( 0 ，1 】 证明因为 ( t - t - 1 ) 2 一( t - t - p ) 。：坠尘峰必， 对0 1 ，上面的式子总是非负于是引理得以证明口 引理1 2 8 对任意的 0 ，可以证明 l t 一半一t 字l i t 一1 一t l ，p 【0 ，1 ) 证明 因为 舻+ 吉) 一( t 1 - p - t - 西1 ) = ( t 3 p - 可1 ) ( 一t i + p + 1 ) ， 无论对0 1 ，上面的式子都是非负的于是引理得证口 引理1 2 9 如果1 1 2 = 亿，则字| i n ，p 【o ，1 ) 证明因为对任意的，y r ，都有i l e l l i = 何，由h 6 l d e r 不等式可以证明引理 口 下面的引理关注可行的f u l l - n e w t o n 步的行为 引理1 2 1 0 令( z ，s ) 为正的原始对偶迭代，p o 满勋r s = 叩此外令6 ( ) = 6 ( z ，s ；p ) 和心：= 钉孚佣则有 砸) 2 ( 1 - o ) 州+ 岛 证明 科= 扣厕一半一涌1 1 2 = 扣佣( 口一半一口孚) + ( 厕警一丽与 孚) 1 1 2 = t 1 - 0 一孚一钐警i | 2 + 掣藩一三即一导一口节) 毛警 ( 1 - 0 ) 跏) 2 + 岛， 这里的证明我们用到了引理1 2 8 ，同时因为f 1 2 = n ，我们用了两次引理1 2 9 n 1 3 技巧性引理 引理1 2 1 1( 1 4 ，l e m r n aa 1 ) 对i = 1 ，仇，令五：r + 一r 为凸函数则 对于任意非零向量石r 2 ，下面的不等式 壹i = l 讹，麦喜卅驴，)。j ；1i j 成立 1 3 技巧性引理 这一节我们利用对数障碍函数，给出一些理论结果通过这一节，能够知道 产生的迭代点列有一个上界限制 给定( 尸) 的一个严格的原始可行解z 和( d ) 的一个严格的对偶可行解( y ，s ) 以 及“ 0 ，令 吣s ；小卸( 小= i 地) ，一、警，帅) 一扣- 1 - l 吲2 ) = 1 v i 大家都知道砂( ) 是原始对偶对数障碍函数的k e r n e l 函数，而原始对偶对数障碍函 数与圣( z s ；弘) 相差一个常数 引理1 3 1可以证明， 垂( z s ；p ) = 圣( z s ( p ) ；p ) 十圣( z ( p ) s ；p ) 证明引理中的等式等价于 壹i = l ( 等一1 - l o gx 丢s - - - j - i ) = 喜( 学一崦学) + 喜( 掣一1 - l o g x i _ _ _ s s 因为 1 0 9 等刮。g 羽x i 丽8 i 叫。g 鑫仙g 南礼g 掣仙g 警， 引理成立的充要条t 牛- 是 x t 8 一佗p = ( z t s ( p ) 一亿p ) + ( 8 t x ( u ) 一九p ) 利用z ( p ) s ( p ) 这一项，这时有z ( p ) t s ( u ) = 佗p ，上式可以写为( z z ( p ) ) 丁( 5 一 s ( 肛) ) = 0 ，这个式子成立的前提是向量z z ( p ) 与向量s s ( p ) 正交因为z 一 第一章解线性规划问题的f u l l n e w t o n 步不可行内点算法 z ( p ) 属于a 的零空间，s s ( p ) 属于a m 行空间，z z ( p ) 与8 一s ( p ) 正交性是成立 的于是引理得以证明 口 定义 p ( a ) ：= 6 + 、1 + 6 2 ( 1 - 3 - 1 5 ) 定理1 3 2 令6 ( u ) 是( 1 2 6 ) 定义的量，p ( 6 ) 是( 1 3 - 1 5 ) ) 定义的量则皿( 锄) s 砂( p ( 6 ( 口) ) ) 证明如果v = e ，则6 ( ) = 皿( u ) = o 以及p ( o ) = 1 ，矽( 1 ) = 0 这时引理是很 明显的我们考虑a ( v ) 0 ，皿( u ) o 这种非平凡的情形对丁 0 ，考虑问题 n。 t l z r = 峄 0 ，都有，( 下) 0 从 而可以推出皿( ) 关于k 是单调减少的所以当七= 1 时雪( u ) 取最大，于是得到了 定理中的结果 口 推论1 3 3 令7 - o 且5 ( v ) 丁则有皿( 可) 7 - ，其中7 - ：= 妒( 7 - ) ) 证明 因为j d ( 5 ) 关于s 单调增加，对所有的s o 有p ( s ) 1 ，另外，如果t 1 ， 则妒( t ) 单调增加，所以函数妒( j d ( 6 ) ) 关于6 ( 6 o ) 单调增加这样从定理1 3 2 就得 到了结论 口 引理1 3 4 令6 ( u ) 7 以及丁7 为推论1 - 3 3 中所定义于是有 妒( 厮( 厮) ， i = 1 ，n 证明 由引理1 3 1 可知，皿( z s ；p ) = 皿( z s ( p ) ；芦) + ( z ( p ) s ；肛) 因 为皿( z s ；p ) 总是非负的，于是( z s ( p ) ；p ) 和皿( z ( p ) s ；p ) 都是非负的 由推 论1 3 3 可知皿( z s ；p ) 7 - 7 进而有皿( z s ( p ) ；p ) 丁7 及皿 ( p ) s ；弘) 丁7 由第 一个不等式推出 皿( z s ( 肛) ；p ) = 砂( i = 1 ) 丁7 第一章解线性规划问题的f u l l - n e w t o n 步不可行内点算法 因为对每一个t 0 ，妒( t ) 0 ，于是 ) 下7 ，i = 1 ，n 因为z ( p ) s ( p ) = p e ，我们可以得出 兢s i ( p )z i s i ( p ) x i x i 8 i兢s i l p jj pz t ( p ) s i ( p ) x i ( p ) pz t ( p ) s i 【p )( p ) 这时可以得到引理的第一个不等式第二个不等式可以用同样的方法得到 口 下面我们要使用砂( ) ( 其中o t 1 ) 的反函数，将其表示为x ( s ) 于是x ： 0 ，o o ) 一( 0 ，1 】，并且有下面的关系成立： x ( s ) = t铮8 = 妒( t ) ，8 0 ，0 0 ，可以证明x ( 砂( t ) ) t 1 + 、2 砂( ) 证明假定e ( t ) = 8 0 因为砂( t ) 是凸函数，在t = 1 处达到极小值，其值 为矽( 1 ) = 0 ，以及因为当z 趋向于零和当芒趋向于无穷时矽( ) 都趋向于无穷，所以 确切存在两个数a 和b 满足矽( n ) = 矽( 6 ) = s ( 其中o a 1 6 ) 因为o 1 ，所以凸= x ( s ) = x ( 砂( ) ) ，证明了引理中不等式的左半部分对 于b ，可以将s 表示为 s = 去( 6 2 1 ) 一l o gb 去( 6 2 1 ) ， 这就说明6 1 + 侮，于是证明了右边的不等式 口 推论1 3 6 如果6 ( u ) 7 ，则 m 、南 1 + 何川丁畦 赢 1 + 历 证明直接由引理1 3 4 和引理1 3 5 可以得到 口 定理1 3 7 如果6 ( u ) 7 ，则 1 + 何z ( 肛) x ( t 7 ) 以 1 + 厨s ( u ) x ( 下7 ) 4 - z ，1 5 0 仿照m a n s o u r i 等 1 4 】的引理4 1 ，相反部分也能得以证明于是引理得 证口 令 则可以得到 丽 一石， ：= 了v a r x ， d f x ： _ v a r l s ， z ，= z + ，z = z + 争= 詈( u + 如) ， s ，= s + a l s = s + 警= ；( 勘+ 也) 为了简化表示，用滚示万( z ，s ；p ) 现在假设万丁 ( 1 - 4 - 1 7 ) ( 1 - 4 - 1 8 ) 第一章解线性规划问题的f u l l n e w t o n 步不可行内点算法 引理1 4 2 p ( 6 ) 由( 1 - 3 1 5 ) 定义如果 i i d ! l l 丽1 ，i i d l l 丽1 ，( 1 - 缸1 9 ) 则迭代点严格可行 证明 从( 1 4 - 1 7 ) 司以看出，z ，是严格司行的当且仅当v + 0 如 果| i i | o 肯定是成立的因为2 5 = i i v v - 1 l f ，钞的分量能够 达到的最小值f 将满足t 1 与1 t t = 2 6 最后一个方程表明t 2 + 2 6 t 一1 = 0 ， r p t = 一6 + 们丽= 1 p ( a ) 这就证明t ( 1 一缸1 9 ) 中的第一个不等式第二个 可以由同样的方式得到 口 从引理1 4 2 的证明可以看出向量u 的元素满足 1 赢忱p ( 6 ) ， i = 1 棚 ( 1 - 4 - 2 0 ) 接下来令 u ( ) ：= 寺枷d f l i z - 4 - l i d y l l = ( 1 - 4 - 2 1 ) 于是, - id a 知道l i d ，l | 2 u ( u ) ，l i d 酬2 u ( ) ，以及有 ( ) r i l d 纠去( | l 1 1 2 - 4 - i i , t ；1 1 2 ) = 2 u ( ) 2 ，( 1 - 4 - 2 2 ) j i i i d ! l ll l d , s l | 2 w ( v ) 2 ，1 i n ( 1 - 4 - 2 3 ) 引理1 4 3可以证明 4 跏，) 2 岛+ 辔+ ( 1 叫当 证明由于 肛学= 坚1 - 巡0 ， 根据定义( 1 2 6 ) ，可以得到 竹 4 6 ( v ，) 2 = i