（计算数学专业论文）内点法中线性方程组三种解法的误差分析.pdf

在用内点法求解线性规划问题的过程中，我们经常遇到一个对称的秩一p 修改的系统( ，+ u u 7 ) z = r 我们研究三种算法，即q r 算法：先对u 进 行q r 分解，再求解该系统；e q r 算法：除了对u 进行e q r 分解，其它 与q r 算法相同；s m w 算法：使用s h e r m a n m o r r i s o n w o o d b u r y 公式求 解该系统我们的理论分析表明如果f f f f 较大，那么q r 算法比e q r 算法 和流行的方法：s m w 算法更有效该系统和不可行内点法的数值试验也和 理论分析一致 关键词：秩一p ，内点法，q r ，s h e r m 粕姚r i s o 阽w 而a 瓦；r y 嬲2 枷巴、t 锈嘶 a b s t r a c t f o rs o l v i n gl i n e a rs y s t e m sf r o mi n t e r i o rp o i n ta l g o r i t h mf o rl i n e a rp r o g r a m m i n g ，o n eo f t e ne n c o u n t e r sas y m m e t r i cr a n k - pm o d i f i c a t i o ns y s t e m ： ( ，+ u u 丁) z = r w es t u d yt h r e ea l g o r i t h m sf o ri t ，n a m e l ya l g o r i t h mq r ： w h i c hd o e sq rd e c o m p o s i t i o nf o ru t h e ns o l v e st h es y s t e m ；a l g o r i t h m e q r ：s a m ea sq re x c e p te c o n o m i c a lq r ( e q r ) d e c o m p o s i t i o ni sd o n e ；a 1 一 g o i t h ms m w ：w h i c hu s e ss h e r m a n m o r r i s o n w o o d b u r yf o r m u l ao u rt h e o r e t i c a la n a l y s e ss h o wt h a ti f5 9 l li sl a r g e ，a l g o r i t h mq ri sm o r ee f f i c i e n t t h a na l g o r i t h me q ra n dt h ep o p u l a rw a y ：a l g o r i t h ms m wn u m e r i c a le x p e r i m e n t sf o rt h es y s t e m s ，a n df 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 ma g r e e w i t ho n ra n a l y s i s k e y w o r d s ：r a n k p ，i n t e r i o r p o i n ta l g o r i t h m ，q a ，s h e r m a n m o r r i s o n w o o d b u r y 1引言 1 1线性规划和原一对偶内点法 线性规划( l i n e a rp r o g r a m m i n g ) 是通过数量的分析来解决实际的问 题，例如计划，路线安排，日程安排，任务分派等问题现在它已被广泛应 用到经济和军事等方面d a n t z i g 在1 9 4 7 年发现了单纯形法我们知道如 果一个线性规划问题有最优解，那么基本可行解集中必有最优解单纯形法 的思想是先找到一个基本可行解，如果它不是最优解，那么再找一个比它更 优的解，直到找到最优解或者判定无界尽管单纯形法平均迭代次数不超过 n 2 ，但1 9 7 2 年k l e e 和m i n t yf 2 1 证明了单纯形法迭代复杂性为指数阶使 用单纯形法来求解大型的，极端退化的问题效果非常差 1 9 8 4 年k a r m a r k a rf 3 1 提出了求解线性规划问题的一个具有多项式复杂 性的算法：内点法他在 3 中指出内点法比单纯形法快4 0 倍实际上，在 二十世纪五六十年代内点法已经得到了发展f 1 】内点法是一种迭代算法，它 从一个初始可行内点出发，产生一系列满足约束条件的点，最后收敛到最优 点实际上，内点法的效果要好于单纯形法尤其是对大型稀疏问题在本篇 文章中，我们关注大型稀疏问题 内点法主要有三种：仿射均衡尺度法( t h ea f l i n es c a l i n ga l g o r i t h m ) ，降势 法f t h ep o t e n t i a lr e d u c t i o na l g o r i t h m ) ，t h ep a t h f o l l o w i n ga l g o r i t h m t h e p a t h f o l l o w i n g 算法被认为是最有效的内点法( 参见【4 和【7 ) m o n t e i r o 和 a d l e r 【4 】证明了原一对偶法迭代的复杂性为d ( v 历l o g ( c o e ) ) 内点法需要一个严格可行的初始内点( 满足所有约束条件的点) ，然而得 到这样一个可行内点需要解一个大型的系统不可行内点法只需要内点( 只 满足不等式约束的点) 作为初始点，因而它比内点法更有效，( 8 j 1 2 ， 1 3 j 和 1 5 ) 线性规划问题的标准形式如下： m i n i m i z e， s u b j e c tt oa x = b ，z20 表达式c t x 称为目标函数，向量z 称为决策变量 它的对偶问题是 n l a x l m l z e s u b j e c tt o 如果( z 。，+ ，s 8 ) 满足著名的k a r u s h k u h n t u c k e r ( k k t ) 条件 a x + = b ， z20 ， a t y ”+ 8 + = c s + 20 ， ( + ) t 8 + = 0 ， 北儿川， 其中x = d i a g ( x ) ，s = d i a g ( s ) ，肛= x t 8 ，r b = b a x ，n = c a t y s ， 再计算出，d 8 a d 2 a t d y = a ( z 一盯p s 一1 e + d 2 r 。) + n ， ( 1 ) d s = r 。一a f 屯 如= 一。+ s 一1 0 7 # e x d s l 2 一 = 十咖卿 方程组( 1 ) 等价于系数矩阵为d a r 的最小二乘问题的正则方程在内点法 中，由于当前点一( z ，s ) 是可行内点，故n = r 。= 0 无论在内点法还 是在不可行内点法中，解方程组( 1 ) 都是最主要的计算工作f 1 7 1 指出， 尽管正则方程法求解最小二乘问题的数值稳定性差( 与q r 和s v d 方法相 比) ，但是由于其速度快，仍然经常被使用【1 0 和 1 4 用预条件共轭梯度 法来解上面的方程由于构造好的预条件矩阵非常困难和当接近最优解时系 数矩阵条件数非常大，预条件共轭梯度法的使用非常有限，只对一些特殊的 线性规划问题有效由于计算精度的问题，标准的稀疏c h o l e s k y 分解可能会 遇到问题最近w r i g h t 【2 2 】提出改进的c h o l e s k y ( m o d c h 0 1 ) 分解来解称正 定方程组( 1 ) 他证明了虽然计算解d 9 可能与真实解妇有较大误差，但是 a 丁 与a 7 咖非常接近这样出和d s 可以被精确的计算方程组的右边 仅依赖。及8 ，与y 无关，这样迭代可以进行下去 如果a 有稠密的列，a d 2 a 了1 可能是稠密的，我们无法应用稠密c h o l e s k y 分解来解方程组( 1 ) 一个通用的方法是( 参见 6j 和 8 】) ：把a 分成两部分 a = f a 。，a 。) ( 通过一些排列) ，其中az 是稀疏的，4 。是稠密的，a 2 只有 极少的列，对应地把d 分成两部分，作分解a 。d 2 。n t ，= l 。口，那么 a d 2 a 丁= a 1 d 1 2 a t l 十a 2 d 。2 a t 。= l 1 ( ，+ u u t ) l 其中u = l f l a 2 d 2 当接近最优解时，孔s - 3 0 ，所以d 1 和d 2 的条件 数可能非常大，的条件数也可能非常大a l 可能不是行满秩矩阵，即 4 1 d a l 可能是正半定矩阵，我们使用m o d c h o l 1 9 来分解a i d a 1 正则 方程组可以分如下三步来解：两步解三角方程组和解一个具有如下形式的方 程组： ( ，+ u u 。) x = r ( 2 ) 1 2 求解( ，+ u u t ) z = r 的三种算法 设a t t “，a 2 r “p 及p 1 ) ，另一方面是由于我们采用有限精度来计算c h o l e s k y 分 解( 如果我们用c h o l e s k y 分解来解a z = r ) 【2 3 给出对( ，+ b b t ) z = z 结 构误差分析我们感兴趣的不是这一步的误差分析，而是最后的误差分析， 这里我们用经典误差分析 引理l 设x 为方阵且ll x l l 1 ，那么一x 可逆，( ，一x ) “= 墨o x 4 证明请参见 1 9 ，p a g e3 3 现在，如果 l a “e l | p ，a = f + u 旷和m = ，+ u r u ，则 l u m “ l = ! m 一1 u t l l = l l c ，r a 。l = i a 1 u f 旦竺；岳i 产， ( 1 2 ) j i a ij = j t i l = 1 + j j 训2 ，( 1 3 ) j j a “j j = l ，( 1 4 ) l l u r u = ij 1 f t a - i u u m 一1 州= i i u u t a - 1 j j = 而i i u i t 2 ，( 1 5 ) m 1 u t a x t l = f i u t z l l ( 1 6 ) 不等式( 1 2 ) ，( z a ) ，( 1 4 ) ，( 1 5 ) 和( 1 6 ) 可以用奇异值分解来证明 定理2 设z 和圣分而1 为( ，+ 矿u t ) z = r ，( ，+ ( u + u ) ( u + u ) t ) 牙= r + a r 的解，其中a u ，2 x r 满足 e x 幽i i u l l ，帮) 击 那么成立误差估计 忙一钏 i l u t ( z 一圳 忙 证明我们定义 e ( 、一( m ) + i l u l l s 。+ 屯) ， 1 时，参见表1 ，2 s y s t e mo m i nk ( m ) z s zt z s l0 1 + j l u l l 2p e l| j u l1 + j l u l l 2 s 2o l 十l i 训2p e m o1 s 3 桫| | l p e l l l u l i1 + 渺1 1 2 s 4 j j 训 l p e 。 ol 我们来比较e q r 算法和q r 算法对斧，e q r 算法和q r 算法同 样精确，但是对世高产，在表1 中s l 和s 3 的情况下q r 算法比e q r 算 法精确 尽管对系统s 2 ，s m w 算法比q r 算法准确，但对系统s 1 和s 3 ，s m w 算法的误差达到c “胆所以当”卅f 较大时，q r 算法比s m w 算法更有 1 8 悭= 业 _ | u 1h 一圣) l c u l l x 1c u l 蚓 s y s t e mq re q r s m wq re q rs m w s 1 o ( i i u h 2 )o ( 1 l u l l 2 ) o ( 1 l u l l 3 )o ( 1 l u l l 2 )o ( 1 l u l l 3 )o ( 1 l u i l 3 ) s 2 o ( 1 t ur f 2 )o ( i f 1 1 2 )o ( 1 l ur 1 )o ( rr ur 2 )o ( 1 1 0 7r 2 )o ( r i u l l ) s 3 o ( 1 l u l l 2 )o ( 1 l ub 1 2 )o ( 1 l u l l 2 )o ( 1 l u i i )o ( u o ( 1 l u l l 3 ) s 4 o ( 1 )o ( 1 ) o ( 1 ) o ( 1 l u l l )o ( 1 l u l l ) o ( 1 l u l l ) 效在内点法中，o ( 1 l u l l 2 ) 阶的误差是可以被接受的，但是o ( 1 l u l l 3 ) 是不 能接受的从表2 ，我们推荐使用q r 算法 5 数值试验 我们的误差分析式中包括 i uj ，k ( m ) ，s 。，如，因此我们这样构造数值例 子：设p 为6 6 的正交阵，q 为3 3 的正交阵，为6 3 对角阵，我 们指定其对角元素( 参见表3 从系统矿1 到u 1 2 ) ，令u = p e q 我们令z 分别等于p e l ，p e 。，p e l + p e 。定义e 为我们估计的误差 界限 我们用m a t l a b 的任意精度算术运算( v p a ) 来计算p 和q 类似地 我们计算o = p e l ，p e 。，p e l + p e 。，u = p e q 和r = ( i + u u t ) z ，这样z 是( ，+ u u 丁) z = r 的“精确”解所有的试验都是在p c 机上进行的，软 件为m a t l a b5 3 1 1 1 ，机器精度u 1 1 l o _ 1 6 表3 给出( + u u t ) z = r 的扰动性分析的结果( 参见定理3 ) 我们令 e = t 0x1 0 。4 ，l i a u i i = f l l u l l ，i v , d l = ( 1 l f l l 设。和。分别为u 的 最大和最小奇异值从表中看出，我们的误差分析非常有效 表4 ，5 给出用q a ，e q r 和s m w 算法来计算( ，+ u 沪。) z = r 的误差 分析即不等式( 3 1 ) ，( 3 2 ) ，( 3 8 ) ，( 3 9 ) ，( 4 3 ) 和( 4 4 ) 盯。盯。z 的取值请参 见表3 令c = 1 0 对系统u 1 到u 6 ，q r ，e q r 和s m w 算法的结果都非常 好，我们不关注这几种情况 对系统u 8 ( 参见表4 ) ，我们的估计远大于实际的误差我们仅对q r 算 1 9 表3 ：f - f u u t ) z = r 的扰动性 s y s t e m o - r n z仉n l n ze 1 i u l ( z ) | _ f 儿三= 纠 f 旧f f 忙f f u 11o e 一6 p e l 1 9 e 一1 44 4 e 一1 42 5 e 1 538 e 一1 4 u 2 10 e 一6 p e 6 30 e 一1 6 2 4 e 一1 43 3 e 1 71 7 e 一1 4 u 31 o e 一6p e 】+ p e 6 18 e 一1 5 3 7 e 一1 44 1 e 1 73 1 e 一1 4 u 4 p e l 1 0 e 一1 44 o e 一1 444 e 1 63 o e 一1 4 u 51 p e 6 5 0 e 1 5 2 0 e 1 45 o 正1 1 5i 5 e 一1 4 u 611 p e l + p e 6 7 9 e 一1 53 3 e 一1 43 5 e 1 525 e 一1 4 u 71 0 e 6 p e l 7 1 e 一32 o e 一2 3 4 e 一3 1 4 e 一2 u 81 ，0 e 6 p e 6 3 1 e 一1 07 1 e 一956 e 一91o e 一8 u 91 o e 61 p e l + p e 6 56 e 一31 4 e 一22 4 e 一31 0 e 一2 u 1 01 o e 61 o e 6p e l97 e 一32 0 e 一2 2 6 e 一9 3 0 e 一8 u 1 11 0 e 61 o e 6 p e 6 49 e 一1 5 2 0 e 一1 448 e 一91 o e 一8 u 1 21 o e 61 o e 6 p e l + p e 6 6 0 e 一41 4 e 一2 3 9 e 一9 2 4 e 一8 法进行分析： 掣c u ( k ( 吖) + i i u l l s 。) | | 山| | 当s 。= 0 或如f f 矿m 也就是系统u 8 的情况，一( 肘) 占主导地位k ( m ) 来自解p p 的方程组，这是个经典误差分析结果在我们的例子中，如果经 典误差分析远大于实际误差，我们的误差估计也就远大于实际误差e q r 和s m w 算法的分析与q r 算法类似 表4 表明q r 和e q r 算法比s m w 更有效对系统u 8 ，s m w 算法比 q r 算法准确，但是q r 算法的误差也是可以接受的对系统u 7 l = 1 ， 然而，j i x s m w ”= 4 5 ，这意味着z j w 毫无用处系统u 9 也是同样的情况 从表4 我们知道对系统u 7 ，u 9 ，u 1 0 和u 1 2 ，x q r 和x e q r 同样精确， 对系统u 1 0 和u 1 2x q n 和x s m w 同样精确，然而，从表5 我们可以看出 q a 算法计算出的u t 童要比e q r 和s m w 计算的准确 2 0 q re q r s m w s y s t e m 此= 纠 e 止= 到 e 止= 业 e l o 目l 恼| |l l u 72 1 e 一0 417 e 一0 31 5 e 一0 42 8 e 。0 345 e + 0 11 6 e + 0 3 u 83 8 e l l5 6 e 一0 438 e 1 156 e 0 42 o e 一1 77 9 e 一1 0 u 91 6 e 0 41 3 e 0 3 9 8 e 0 5 2 1 e 0 31 9 e + 0 11 1 e + 0 3 u 1 05 o e 一0 41 1 e 0 35 、1 e 一0 42 2 e 0 312 e 一0 42 2 e 一0 3 u 1 16 7 e 一1 61 1 e 一1 51 2 e 一1 62 2 e ，1 53o e 1 8 1 1 e 一1 5 u 1 236 e 一0 479 e 一0 42 9 e 一0 41 6 e 0 37 5 e 0 516 e 一0 3 “ 4 - j o o q 】气 e ( 2 r s mw s y s t e m l i ( ，1 仕一圣) | e i l 矿7 ( z 一刳l | e | | 矿( z 一劫j | e l l 蚓l 江| | z u 748 e 0 57 9 e 0 47 7 e + 0 l1 1 e + 0 32 9 e + 0 222 e + 0 3 u 8 1 1 e l l7 9 e 0 43 9 e l l 79 e - 0 4 2 0 f 、- 1 li 1 e 一0 9 u 91 5 e 一0 579 e 。0 49 6 e 0 17 9 e + 0 21 7 e + 0 21 6 e + 0 3 u 1 04 3 e 一1 01 1 e 0 97 1 e + 0 11 1 e + 0 37 1 e + 0 12 2 e + 0 3 u 1 l 19 e 一1 0 11 e 。0 91 1 e 一1 0 2 2 e 0 95 1 e 一1 l l1 e 0 9 u 1 236 e l o11 e 。0 913 e + 0 17 9 e + 0 27 4 e + 0 11 6 e + 0 3 2 1 6 不可行内点法的应用 在这一节，我们用不可行内点法来解线性规划问题在每一步迭代中， 我们分别使用上面的三种算法，最后对结果进行比较 我们先给出不可行内点法，这个算法选自 1 6 - 为了叙述方便，我们做 了一些改动 不可行内点法 对给定的a ，b ，c 和初始点( y o ，z o 0 ，s o o ) ，令( y ，z ，s ) = ( y o ，x o ，3 0 ) 1 若| | z r c 一丁圳 e o 或l l z 丁s l i e 0 则停止，已找到最优解 2 令n = b a x ，= c a r y s ，p = 8 t z n ； 3 调用算法s u b l 来计算参数7 0 ，1 和q 0 ，1 ； ( 1 0a t , d x ) 0 叫；， 5 调用算法s u b 2 来计算步长o 6 计算新解 7 转到l ”( z 、i如1 矿qi d y j 算法s u b l 1 设”= l 及7 = 0 ，解方程组( 4 5 ) 求如，内及d s 2 计算a = m i n q 。，盘。，血l ) ，其中 o 。= m i n - x j ( d x ) j ：如果( 如) j o ) ， q 。= m i n 一s j ( d s ) j ：如果( d s ) j o ， 。是一个较大正的参数 2 2 3 计算7 = 0 5 【( z + a d z ) 丁( s + q d s ) n 肛) 及q = 1 7 算法s u b 2 1 计算q = f a c t o r $ m i n 。，q 。，( 2 l ) ，其中 。= m i n 一码 d x ) j ：如果( d z ) j 0 ) ， o 。= m i n - s j ( d s ) j ：如果( d s ) j o ， a l 是一个较大正的参数，f a c t o r ( 0 ，1 ) 2 如果d 。7 d s 0 ，令= m i n a ，一( z 了1 $ d s 十s 了1 d x ) d x d s 我们令o = l e 一7 ，a l = l o o o o 及f a c t o r = o 9 9 9 5 这里，我们没有给出不 可行内点法的收敛性证明 我们构造a ，茁，8 + ，y + ，b 及c 的方法来在 2 2 】对a = ( a 1 ，a 2 ) ， a r ”一，a 2 r “p ，令m = 6 ，n = 1 0 ，p = 3 及4 的元素为( f l o 5 ) 1 0 6 ( f 。- 0 ”，其中f i 及6 为 0 ，l 】间的随机数定义指标集s 并且sc f l ，2 n 原始解上4 ，对偶解y + 及最优对偶松弛变量s + 构造方法如下： +l 0 i fi s q 一11 0 3 驴。i fi s y = ( 1 ，1 ，1 ) t ， 萨 。1 0 4 4 - 2 麓； 其中3 及矗为【0 ，l 】之间的随机变量最后计算b = a x + 及c = a 丁y + s 在这一节，我们使用m o d c h o l 2 2 来代替标准的c h o l e s k y 分解 为了观察不可行内点法的收敛性，我们定义 m 三揣r r c = 揣，帷警并， 分别表示主不可行性，对偶不可行性，对偶间隙我们知道当m a x ( r r b ，r r c ，r 肛) _ 0 ，则z 叶x s o i u t i o n 及s - - + s s o l u t i o n 因此我们用m a x ( r r b ，r r c ，r p ) 来衡 量收敛性在表6 ，7 ，8 和9 ，i 表示迭代的次数 表6 ：q r ，e q r 和s m w 算法在不可行内点法中的应用，其中指标集s 1 ，2 ，8 ) q re q rs m w r r br r cr “r r dr r cr “r r 0r r cr “ 13 19 5 e 一0 l1 _ 13 19 5 e 0 11 13 195 e 一0 11 l 22 0 6 1 e 一0 l 4 0 e ，0 l2 o6l e 0 l40 e - o l2 06i e 0 l 4 0 e o l 31 339 e 0 11 6 8 0 11339 e o l1 _ 6 e 0 11 339 e 0 l1 6 e 0 1 447 e 0 1 i 4 e 0 1 4 5 e - 0 24 7 e 0 l 1 4 e 0 i4 5 e 0 2 4 7 e 0 l 1 4 e 0 l45 e 0 2 577 e 0 22 3 b 0 26 6 b 0 37 7 8 0 22 3 8 0 26 6 d 0 37 7 e 0 22 3 e 0 266 e - 0 3 64 o e 0 31 2 e 0 33 3 e 0 44 o e 0 31 2 8 0 33 3 e - 0 44 0 e 一0 3 1 2 e 0 33 3 e 一0 4 76 4 e 0 62 0 e 0 66 2 e 0 7 12 e 0 4 2 0 e ，0 66 2 e - 0 752 e 一0 52 0 e 一0 66 2 e - 0 7 832 e 一0 99 8 e 1 03 1 8 1 05 1 e ，0 21 3 e 0 73 3 e 0 87 9 e 0 29 8 e 1 01 1 e 0 8 9 4 2 e o l 1 3 e 0 73 3 e 0 85 7 8 0 1 97 e 。1 0 3 6 e 0 9 在表中6 ，指标集s = 1 ，2 ，8 对q r 算法，8 次迭代后得到了很好 的结果：m a x ( r r b ，t t c ，r p ) = 32 e - 9 对e q r 算法，m i n m a x ( r r b ，t t c ，r p ) = 1 2 e 一4 及s m w 7 算法为5 2 e 一5 对s = 1 ，2 ，8 q r 算法好于e q r 算法和s m w 算法在表7 中，指标集s = 9 ，i 0 ，这三种算法都有很好的 收敛性 在表8 中，指标集s = 2 ，l o 我们发现一个有趣的结果三种算 法有相同的结果实际上，通过计算我们知道在整个计算过程中1 i u i l l e 3 从表2 ，我们知道解方程组( 2 ) 的误差都很小 在表9 中，指标集s = 1 ，3 ，5 ，7 ，9 1 0 次迭代后q r 算法得到了很好的 结果，更多的迭代次数使结果变的更坏e q r 算法和s m w 算法与q r 算法 有类似的情况，但是q r 算法的结果最好：m i n m a x ( r r b ，r r c ，r 肛) ) = 3 4 e 8 7 结论 当j j uj j 较小时，解方程组( ，+ u u 丁) z = r ，这三种算法的都非常有效 我们推荐选择s m w 算法，因为它速度最快当i l u | | 较大时，q a 算法是 表7 ：q r ，e q r 和s m w 算法在不可行内点法中的应用，其中指标集s = 9 ，1 0 q re q rs m w r r b r ! c r nr r dr r cr “r r br r cr “ 19 6 e o l9 8 e 0 l9 6 e 0 19 6 e o l9 8 e 0 196 e 0 19 6 e 0 l98 e 一0 19 6 e 一0 l 293 e 0 195 l o l6 4 e 0 19 3 e 一0 l9 5 e 0 16 4 e 一0 l9 3 e 一0 l9 5 e 0 l64 e 0 l 384 e 。0 l8 5 e 0 12 6 e 一0 l84 e o l85 e o l26 e 一0 18 4 e 0 l85 e o l2 6 e 一0 1 46 8 e 0 16 9 e ，0 11 1 e 0 168 e o l6 9 e 一0 l1 1 e 0 l6 8 e 0 16 9 e 0 11 1 e 0 1 531 e 一0 132 e 一0 12 o e 0 23 1 e 0 13 2 e 0 l2 1 e 0 23 1 e 0 l 3 2 8 0 12 0 8 0 2 61 0 e 0 11 1 e 0 l4 6 e - 0 31 1 b - 0 l1 1 e 一0 l5 1 e - 0 39 8 e 一0 298 e 0 24 3 e 0 3 73 9 e 0 339 e 0 33 5 e 0 41 1 e 0 15 7 e 一0 33 8 e - 0 46 6 e 0 22 5 e 0 32 8 e 0 4 83 4 e 0 835 e 0 831 e 0 54 8 e 0 7 5 4 e - 0 85 o e 0 52 9 e 0 5 1 1 e 一0 6 2 3 e 一0 5 9 4 3 e 1 04 4 e 1 03 9 e - 0 78 1 8 0 99 1 e l o8 5 e - 0 73 1 b 0 71 2 e 0 82 6 e 0 7 1 05 9 e 1 33 8 e 1 33 4 e 1 086 e 一1 21 0 e 1 294 e 1 0l8 e 1 07 4 8 1 21 6 b l o 最好的选择在原一对偶内点算法中，当z ，s 接近最优解时，i f c 厂| | 可能非 常大，所以这时q r 算法是最有效的 2 5 表 2 8 ：q r ，e q r 和s m w 算法在不可行内点法中的应用，其中指标集s = 1 0 ， q re q rs m w lr r br r cr “ 17 7 e o l8 5 e o l1 0 26 o e 0 166 e 0 14 1 e 一0 1 3 4 5 e 一0 1 4 9 e - 0 l1 9 e 一0 l 44 2 e 0 146 e 0 11 5 e 一0 1 54 1 e 一0 14 5 e 0 19 国e 一0 2 63 9 e 一0 14 2 e 一0 l6 3 e 0 2 73 8 e 0 14 2 e 0 1 4 3 e 0 2 83 7 e 0 1 4 1 e o l 2 9 e 0 2 93 6 e 0 14 o e 0 12 3 e 一0 2 l o1 6 e 0 11 8 e 一0 11 8 e 0 2 1 17 5 e 0 28 2 e 一0 23 2 e 0 3 1 26 4 b 0 37 o e 一0 32 8 b ，0 4 1 31 ，4 e 一0 415 e 0 45 1 e 0 6 1 48 4 e 一0 89 2 e 一0 83 2 e 一0 9 1 54 6 e 一1 l5 1 e 一1 11 8 e 一1 2 2 6 表9 ：q r ，e q r 和s m w 算法在不可行内点法中的应用，其中指标集s i ，3 ，5 ，7 ，9 q re q r s m w r r br r cr “r r b r r c r “r r b r r c r “ l94 e l98 e 。li 09 4 e 一19 8 e ll09 4 e l9 8 e ll0 288 e 1 92 e 。1 5 2 e l88 e 19 2 e l52 e 18 8 e 19 2 e 15 2 e 1 377 e - l 8 0 b i l9 b l 77 壬l8 0 e li 9 b 17 7 e + l8 0 e il 9 e - l 45 6 e 15 8 e 17 0 e - 25 6 e l58 e 17o e 256 e 15 8 e 17 0 e 2 52 9 e 一13 0 e 122 e - 22 9 b 13 o e 12 2 e 22 9 e 13 0 e 12 2 8 2 67 5 e 27 8 e 24 5 e 一31 3 e 17 8 e 23 8 e 31 1 e 一17 倡e 24 7 b ，3 712 e 2l _ 2 e 28 5 e 一42 1 e 21 2 e - 28 8 e 41 7 e 21 2 e 一28 3 e 4 8 9 1 e 一595 e 5 54 e 5 2 1 e 39 9 e 55 8 e 55 6 e 21 0 e 46 0 e 5 91 2 e 51 2 e 56 5 e 一6l5 e 一41 3 e - 57 1 e 61 0 8 21 8 d 59 4 e 。6 i 03 4 e - 82 3 e _ 81 4 b 823 8 25 3 8 7 2 6 e 76 1 e 33 7 8 71 7 8 7 2 7 参考文献 1 avf i a c c oa n dgpm c o r m i c kn o n l i n e a rp r o g r a m m i n g ：s e q u e n t i a lu n e o n s t r a i n e dm i n i m i z a t i o nt e c h n i q u e s j o h nw i l e y ，n e wy o r k ，1 9 6 8 2 vk l e ea n dg ，j m i n t y h o wg o o di st h es i m p l e xa l g o r i t h m s ? ，i ni n e q u a l i t i e s h i , 0s h i s h a ( e d ) ，a c a d e m i cp r e s s ，n e wy o r k ，n y ，1 5 9 1 7 5 ，1 9 7 2 【3 n k a r m a r k a ran e wp o l y n o m i a l t i m ea l g o r i t h mf o rl i n e a rp r o g r a m m i n g c o r n b i n a t o r i c a 4 ，3 7 3 3 9 5 ，1 9 8 4 【4 】r dcm o n t e i r oa n di a d l e r i n t e r i o rp a t hf o l l o w i n gp r i m a l - d u a la l g o - r i t h m s p a r ti ：l i n e a rp r o g r a m m i n gm a t h e m a t i c a lp r o g r a m m i n g ，v o l4 4 ，p p 2 7 4 1 1 9 8 9 57 g ，h g o l u ba n dc f v a nl o a nm a t r i xc o m p u t a t i o n s ，2 n de d ，t h ej o h n s h o p k i n su n i v e r s i t yp r e s s ，b a l t i m o r e ，m d ，1 9 8 9 6 li cc h o i ，cl m o n m aa n dd fs h a n n o ，f u r t h e rd e v e l o p m e n to fap r i m a l d u a li n t e r i o rp o i n tm e t h o do r s aj o u r n a lo nc o m p u t i n g v 0 1 2 ，n o 4 ，p p 3 0 4 3 1 1 ，1 9 9 0 7 】k am c s h a n e ，c lm o n m a ，a n dd s h a n n o a ni m p l e m e n t a t i o no f ap r i m a l d u a li n t e r i o rp o i n tm e t h o df o rl i n e a rp r o g r a m m i n g o r s aj o u r n a lo nc o r n p u t i n g1 ，7 0 8 3 1 9 9 1 8 】ijl u s t i g ，r e m a r s t e na n dd f s h a n n o c o m p u t a t i o n a le x p e r i e n c ew i t h ap 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 df o rl i n e a rp r o g r a m m i n g l i n e a ra l g e b r a a n di t sa p p l i c a t i o n s 1 5 2 ：1 9 1 - 2 2 2 ，1 9 9 1 ( 9 r j v a n d e r b e i s p l i t t i n gd e n s ec o l u m n si ns p a r s el i n e a rs y s t e m s l i n e a r a l g e b r aa n di t sa p p l i c a t i o n s1 5 2 ：1 0 7 一1 1 7 ，1 9 9 1 1 0 j sm e h r o t r a ，i m p l e m e n t a t i o n so fa f f i n es c a l i n gm e t h o d s ：a p p r o x i m a t es o l u t i o n so fs y s t e m so fl i n e a re q u a t i o n so fs y s t e m so fl i n e a re q u a t i o n su s i n g p r e c o n d i t i o n e dc o n j u g a t eg r a d i e n tm e t h o d s o r s aj o u r n a lo nc o m p u t i n g ， v 0 1 4 ，p p1 0 3 一t 1 8 ，1 9 9 2 1 l jt h em a t h w o r k s m a t l a b 月咖f e n c eg u i d e t h em a t h w o r k si n c ，n a t i c k ， m a ，1 9 9 2 1 2 】m k o j i m a ，n m e g i d d oa n ds m i z u n o ap r i m m d u a li n f e a s i b l ei n t e r i o rp o i n t a l g o r i t h mf o rl i n e a rp r o g r a m m i n gm a t h e m a t i c a lp r w r a m m i n g 6 1 ：2 6 3 2 8 0 ， 】9 9 3 2 8 c t 3 l yz h a n go nt i l ec o n v e r g e n c eo fac l a s so fi n f e a s i b l ei n t e r i o r l p o i n tm e t h o d s f b rt h eh o r i z o n l ，a lc o