（运筹学与控制论专业论文）关于lcp大m数方法的若干拓展结果.pdf

摘要 瑚6 7 2 9 0 用大刚数方法利用内点算法求解线性互补规划问题( l c p ) ， k o j i m a 等人曾经对大刃数的调整提出过一种有效的规范。, e 4 r n i , , l 论的互补问题是可解的m o n o t o n e l c p s 。本文把k o j i m a 等人的那种 规范推广到可解的只( k ) 一l c p s 上。 对于一般的并不预先知晓可解与否的m o n o t o n e - - l c p s 或只( k ) 一 l c p s ，前述规范在调整大射数方面并不起作用。本文进一步提出一 种识别过程，用来调整大射数，不论讨论的问题可行与否。 a b s t r a c t w h e na p p l y i n gi n t e r i o rp o i n tm e t h o d st ot h es o l v i n go fs o l v a b l el c p s b a s e do nb i g 一9 1 4a p p r o a c h ，k o j i m ae ta lp r o p o s e dac r i t e r i o nf o rm a k i n g e f f e c t i v ea d j u s t m e n t so ft h eb i g - 北t h ep r o b l e m st h e yd i s c u s s e da r eo f m o n o t o n e - - l c p s i nt h i sp a p e rw ee x t e n dt h e i rr e s u l tt o 只( k ) _ l c p s f o rm o n o t o n eo r 只( k ) 一l c p si ng e n e r a l ，i e w ed on o tk n o ww h e t h e r t h e ya r es o l v a b l eb e f o r e h a n d ，t h ea f o r e m e n t i o n e dc r i t e r i aa r ei n v a l i d i n t h i sw o r k ，w ep r e s e n ti na d d i t i o na “d i s c e r n i n g p r o c e d u r et h a ti su s e d t o a d j u s tt h eb i g 一朋e f f e c t i v e l y , n om a t t e rw h e t h e rt h ep r o b l e mc o n c e r n e di s s o l v a b l eo rn o t 复垦大学颈士学位论文 引言 对于求解线性互补规划问题( l c p s ) ，传统的转轴算法( 如l e m k e 算法) 在 理论上并不是多项式时间算法，在实际操作上，也不适于处理大规模问题。自从 k a r m a r k a r 于1 9 8 4 年发表了有关线性规划的内点算法以来，由于内点算法在处理 大规模以及超大规模问题上的优势，引起了内点算法在求解线性规划、凸二次规 划和线性互补规划方面的蓬勃发展( 【2 】，【5 】) 。 内点算法的一个重要问题在于初始点的选取。最初的内点算法都要求以一个 严格的可行点作为初始点。所谓的“严格可行点”，对线性规划、二次规划和线 性互补规划而言，就是那些满足所有约束条件，特别是严格满足所有不等式约束 的点。这类算法被统称成为可行内点算法。可行内点算法的初始点和以后的所有 迭代点都保持在问题的可行域内部。但是，如何找到一个严格可行点却不是一件 容易的事。从八十年代末期，兴起了另一种内点算法的构造思路：不可行内点算 法。初始点不必是可行内点，只要求是一个正的启动点就可以了。算法在运行过 程中，会同时寻求可行性和最优性的双重目标。不可行内点算法的好处在于它不 必假设问题可解或有可行内点，从本质上克服了可行内点算法无法解决的难题。 据我们所知，不可行内点算法主要包括两类：一类为自对偶方法；另一类为 大数法。其中，y i n y uy e ，t o d d 和m i z u n o 7 提出的自对偶方法，通过构造齐次 自对偶的线性规划模型来求解线性规划型线性互补问题( l p l c p s ) 。其后，y i n y u y e 将该算法加以推广，用来探讨约束为半正定矩阵的线性互补规划。如果问题 可行，算法生成一个可行解或最优解( 朱必同时) ：如果不可行，则给出一个不 可行标志。 不可行算法的另个解决途径是大数法。这种算法把原始问题嵌入到一个扩 展问题中，通过引入人工变量，把原始问题的维数进行扩充：同时，对线性互补 规划引入一个充分大的参数大州，从而找到符合要求的初始点。在利用大数方法 解决线性互补规划时。必须解决两个问题。首先理论上说，大见数应该耿为一 个足够大的正数，否则人工问题不能导出原始问题的解。然而在计算机上实现时， 塞皇苎兰丝兰兰生堑苎 个足够大的正数，否则人工问题不能导出原始问题的解。然而在计算机上实现时， 取数过大有经常导致数值困难或计算失败。另外，由于约束矩阵维数的增加，新 增的行和列很可能把原问题矩阵的好性质给破坏掉。为了克服上述困难，k o j i m a ， m i z u n o 和y o s h i s e 1 在求解m o n o t o n e l c p s 时，曾经对大m 数的调整提出了一 种有效的规范。对于可行的m o n o t o n e l c p s ，通过这一规范鉴别大纵数是否足 够大，从而实现大埘数的有效调整。 本学位论文把k o j i m a 等人的调整规范由求解m o n o t o n e - l c p s 推广到求解 只( k ) 一l c p s 上，扩大讨论对象的范围。同时，由于对于一般的并不预先知晓可 解与否的m o n o t o n e - - l c p s 或只( k ) l c p s ，前述规范在调整大州数方面并不起 作用，所以本文进一步提出一种识别过程，用来调整大瓤数，不论讨论的问题 可解与否。具体来说，就是当扩展问题c 的解是一个不确定解时，也就是人 工变量不等于零，执行这一识别过程可以获得以下三种结果之一： 1 ) 得到三c 的一个确定解： 2 ) 得到原问题l c p 不可解； 3 ) 得知朋还不够大。 本文的组织结构安排如下：在第一章中，我们介绍与本论文有关的基本概念 和基本性质；第二章主要分析m o n o t o n e l c p s 的大朋数扩展问题的性质，同时 回顾k o j i m a 等人的调整规范并提出了一种新的识别过程；在第二章的基础之上， 第三章我们把k o j i m a 等人的大m 方法调整规范以及我们的识别过程推广到 只“) 一l c p s 上。 复曼大学硕士学位论文 第一章基本概念和基本理论 首先，我们给出所要研究的线性互补规划的标准形式： f w = m z + q ( 1 1 ) l c p ： w 0 ，z 0 lw 7 z ：0 其中，w + z ，g r ”，m r 。为使讨论方便，不妨假设m 和q 的元素都是整数。 当m 是半正定矩阵时，我们称问题( 1 1 ) 为m o n o t o n e - - - l c p s ；当m 是只k ) 阵 时，称问题( 1 1 ) 为只k ) l c p s 。在分析求解线性互补规划问题的算法过程中， 通常需要定义l c p 的输入规模上： = 胁：( 1 + ) 1 + 阮：( 1 + 眦h ) + 阮：( n + 1 ) 其中为系数矩阵吖中所有子式绝对值的最大值。 下面我们介绍半正定矩阵( p s d ) 以及m o n o t o n e - - l c p s 的相关定义及性质。 ( i ) n 阶方阵m 被称为半正定矩阵，如果对于任意一个向量“r “，满足： u r m u = “，( m u 。j o ( i i ) 半正定矩阵的主子式也是半正定矩阵。 ( i i i ) 如果m 和m 2 都是半正定矩阵( 其中m 和m ：可以有不同维数) ，那么矩 m = ( 羔，m a ：卜半正定腓 ( i v ) n 阶方阵m 是半正定矩阵，如果对于某个fr f - 1 ，2 ，n j 矩阵元数m 。= o ， 则m 口= 一m ，对任意成立。 ( v ) 约束为半正定矩阵的线性互补规划可行性等价于可解性。 只k ) 阵最早由k o j i m a 等首先提出，只k ) 阵线性互补规划问题是一类很广 复旦五学砑士笋岔蘑卫 的优化问题，它包含了线性规划问题、凸二次规划问题及单调线性互补问题，目 前已经有许多内点算法可以求解只k ) 阵线性互补规划问题。下面，介绍只仁) 阵 以及只忙) l c p s 的定义及相关性质。 ( i ) n 阶方阵m 被称为只缸) 阵，如果存在一个数k o ，对于任意一个向量“r ” 满足： ( 1 2 ) r l + 4 r j “，r 胁 + 蚝( m u ) j - 0 ， 其中，“和r 缸 分别代表“和m u 的第f 个元素，且 ，+ = i l u 。r 胁 - - 0 ，i = 1 2 ，n ) ，一= i u ，r 胁 - 0 l e ， 显然，半正定属于只仁) 阵。 ( i i ) 只0 ) 阵的主子式也是只0 ) 阵。 ( i i i ) m 为只k ) 阵的充分必要条件是m 是s u f f i c i e n t 阵。 ( i v ) n 阶方阵肘是只k ) 阵，如果对于某个ir f = 1 ，2 ，n j 矩阵元数m 。= o ，则 当m 口 0 ( 或 0 和一个足够大 的正数白，是它们满足w = m z + z o e + q 0 ：然后选取充分大的正数大m ，满足 w o = - e r z + m o , 则( w ，( 主) 便构成为问题c z ，的一个初始内点。由于 m 。n o t 。n e l c r 的可行性与可解性等价，上c 厶是可解的。假定( 蠹 和( 丢) 构 复垦大学硕士学位论文 成c 匕的一个解：当毛= o 时，称它为确定解，不然，则称之为不确定解。显 然，确定解导出原问题的一个解r 茹，三j ；然则，不确定解对于原问题的可解与否 一般不能提供确切的判断；除非是当m “足够”大时，我们可以证明原问题不可 解，这里m “足够”大时是指m 已经达到2 0 ( ) 以上。这是因为对于可解的 m o n o t o n e l c p s ，至少存在一个解满足p 7 x r a a 砖r z i ( w j z ) 为三c l p 的主基本解 根据上述定义，显然刑皓存在) 茎刑”。实际上，m 的确切值只有在求解 原始问题之后才能知道，而m “提供的是一个取值范围。 命题z s 对于问题c z ，如果( w w 0 ，( z z o 是它的一个互补解，那么我们可l 有以下结论： 1 ) 如果l c p 是可解的，则当m 埘”，则l c p 无解。 碱t ，用反证法矾瓤删一有m ( 主 为上哦蚓懈 并且i o = o ，则( 茹，z ) 构成为l c p 的解。由于砜= 一e 7 ；+ m 0 ，n - i n 朋e 7 i 。 根据m 的定义可得m m + ，这与初始条件矛盾。 当m ) 鲥时，如果z o 0 ，假设m 在互补解( 谛，j ) 上达到。令 ，吼2 呻i + m l三o = o 复e 大学硕士学位论文 则 ( 主 构成为上c 匕的一个确定解。取 ( 转删。 由于习是半正定矩阵，所以可得 三， ， ( 2 2 ) z f 。+ w o z o o 。 f = i 因为2 0 o ，所以w 0 ：w o 一饥 o ，则 1 4 1 02 0 。这时( 盏 ，( 主 构成为c p 。f f ：j 一个确定解。取 渤a o ，可得到w o ：w 0 一 0 ，则 w 0 2 0 o 。 同时 所以 w i z ，= 一面 i x z ，一乏) = w i z f + 话，乏一w 。i z f w f 磊 0 妻w ，z ，+ w 0 z 。 0 。 f _ l 这与书是半正定矩阵瓤 口 通过上述命题可以看出，对于可解的l c p 问题，只有当m ) m + 时，问题( 2 1 ) 才能导出l c p 的解。然而，在计算机上实现时，取数过大经常会导致数值困难或 计算失败。所以有必要设计鉴别大刑是否足够大的检验标准。 2 2k o j i m a 的调整规范 对于利用大m 方法求解可解的m o n o t o n e - l c p s 时，k o j i m a 等人在 1 】中对大 刑的调整提出了一种有效的规范，这一规范是建立在如下定理的基础之上 定理z s 如果。c r 是可解的，假设( 五 ，( 主 是c 的一个严格可行 副习，、，l 复壁大学硬士学位论文 解，z 为满足以下条件的数 i ) 0 z o w o + w ( 硝廿 ( 硝乏 一 矧 w 。钿+ 塞。，：， k l = ( w o 一茹o x z o 一毛) + ( w t 一面，x z ，一乏) 刚习，i，、 m ， i i ， ， ，l 复旦大学磺士学位论文 = w o z o + w ，z ，+ 吼毛+ 话，； 一茹。z o w o 毛一茹，z ，一w 五 w 嘲+ ”而 芦l 0 这与( 羔习是半正定矩阵矛盾a 口 在设计利用大朋方法求解可解的m o n o t o n e l c p s 时，比较理想的方法是在 算法启动时掰比较小，在迭代过程中通过鉴别标准判断埘是否太小而需要更新。 为此，k o j i m a 等人设计了一种对大m 进行调整的算法。 算法2 1 取常数嘲a 。满足o k w o z o + w i z r ，取弼= 1 9 1 ，z “1 = v w k + l , w k + l , z k + l , z o k + 1 ) = w k , 缸 t 矽嘞“- ) t _ t + 1 ： n ( b ) 如果z z o w o z o 十w ，z ，利用内点算法迭代产生下一点 ( w “1 ，“，z “1 ，“t ) 口 当( b ) 成立时，因为内点算法的收敛性保证了人工变量在迭代过程中趋 近于0 ，所以不必调整刑和z 。在实际操作中，参数御五可以灵活的选取，比 如f = o5 和丑= 2 。 复垦大学硕士学位诧文 2 3 关于m o n o t o n e - - l c p s 的大数方法的一种识别过程 对于任意一个m o n o t o n e - - - l c p ，由于开始不知道其是否可解，所以仅仅利用 k o j i m a 等人提出的调整规范可能在实际操作中会遇到问题。即使我们知道当 9 1 , 1 2 0 ( ) 且z o o 时，原问题不可解，但由于2 0 ( ) 很难确定，所以我们仍然需 要设计一个鉴别不可解m o n o t o n e - - l c p s 的识别过程。 定舭e 对于三吼的任意互补解 五) ，( 主) c 其帆圳，我们可以通 过对下表： 眩。，= 瞄矧+ 黔删 进行不超过n 次的转轴操作获得一个基本可行解。假设转轴以后t 一 1 4 的表形式 如下： ( 2 5 ) ( 翥 = 厨( 疏蚓 当基本解 蠹) ， 主) 不能直接导出l c p 的解时，我们可得以下结论： i ) 如果虿2 0 ，那么l c p 无解； i i ) 如果牙2 0 不成立，那么纵刑”，其中射“的上界为2 0 ( 。 觋。用反证法。不妨假设将( 甜( 主卜入哦的初始表中，对应的形 式如下式： 鼢矧愉朋( 0 ) 因为( 主 ，( 主 不能窟接导出l c r 的解，所以毛。如果l c p 是可解的，假 复黾大学酸士学位论文 l w o = 一p 。z + 9 t , l 【 z 。= o 由于牙2 - 0 ，即使扩大州时，磊仍然保持不为零，所以不妨假设纵已经足够大 这时 。，( a ( 主o k , i 为三暖的一倒懈令 ( 嚣) = ( z 一( 主 ，( 暑 = ( 主 一 主 则 ( 州羔矧 而w 。：w 0 一磊。 o ，g o ：z 。一嚣 o ，所以w 0 z 。 o 同时 乃= ( - 一冠k ，一茸) = w ，z l + 氟毒一厩z f w f 乏o 由此叫珊驴瞄( 羔；) 是半正定矩阵藕 i i ) 如果虿2 o 不成立，那么必然存在虿， o ，七= l s 七胛+ 1 。 s t e p 3 ：如果对角元而且0 ，以蜕0 做枢轴元进行主转轴。否则检查集合 s = 矧以= o ，而盯o ，l k 0 , i = l , 2 - - , n ) 。因为m 为只。，阵，根据 定义可知： ( 3 3 ) u t 胁+ 4 k 蜥( 胁) 2 0 i l + 下面通过对( 3 2 ) 式和( 3 3 ) 式的比较进行判断。因为： “，i i - e m l r 魁炉删观s m ； “ ( 二，； ( 。二。 ，= r z “，- + “。+ ，k ，= = 一i i u n + l ，= , + 1 所以我们只需要讨论j = l 和，= h + 1 的不同情况 1 ) 当【( 轧1 ) + “。+ l - l o ，一“l “。+ l o 时， “i ( 4 h ) l o ，【( 缸) i + “。+ i - l u i “。+ i = l ( 知) 1 ( 3 2 ) 式等于( 3 3 ) 式。 2 ) 当i i 缸) l + “。+ l k i o ，一“i “。+ l o 时，“i ( 缸) l - u l m u l ， ( 3 2 ) 式大于或等于( 3 3 ) 式。 综合上述不同情况可知( 3 1 3 ) 式一定大于或等于0 ，根据定义可知露是只忙) 阵。同理采取逐步加变的办法，可知匕： 也是只似) 阵。 口 由上述性质可知，问题( 3 i ) 仍然是只伍) 一l c p s 。同时，对问题( 3 1 ) 我们可以方便的选取初始内点：选取z 0 和足够大一个的正向量z o r “，满足 w = 拖+ z o + g 0 ；然后选取充分大的正数大m ，满足w o = 一l z + m e o 。这时 ( 墨 ，( ；) 构成为问题c s ，的一个初始内点。由于只) 一l c p s 的可行性 与可解性等价，所以上c 巳是可解的。假定利用内点算法得到c 的一个解 当z o = 0 时，称它为确定解，不然，则称之为不确定解。显然， 确定解导出原问题的一个鳃r 西，：) ；然则，不确定解对于原问题的可解与否一般 不能提供确切的判断；除非是当埘“足够”大时，可以证明原问题不可解，这里 m “足够”大时是指埘已经达到2 d f ) 以上。 定义3 2 对于一个可解的只k ) 一l c p ，m 定义为满足一下条件的数 m = m i n m a x ( z j ，z 2 ，】( z ) 为c p 的互补解。 定义3 3 对于任意一个只) 一l c p ，m “定义为满足以下条件的数： m ”m 瓯k ( z l ，z 2 ，z 。l ( w ，z ) 为工c 尸的主基本解) 根据上述定义，显然m r 若存在) 朋”。 命题s 。对于问题c s ，如果( w w 0 ，( ；) 是它的一个互补解，我们可有以 、， z 扩 ，l 珀个 、 茹矿 ，。l 塞皇茎兰堡主1 0 里笪l 一 下结论： 1 ) 如果原始问题( l c p ) 是可解的，则当m 刑“，则原始问题( l c p ) 无解。 证明：，下面用反证法证明。当射c 刑时，假设有( 墨) ，( ；o l 为三c 的 互补解，并且；o ；0 ，则( 茹，三) 构成为l c p 的解。由于= 一三+ 触o ，因此 m - m a x z ， 。根据瓢的定义，可以得到m m ，这与初始条件矛盾。所以， 当m ) m + 时，z o 0 。 当m ) m 时，如果z o o ，假设州在互补解( 访，1 ) 上达到。令 f 访o = 一三+ ，h # 1j o ：0 则( 孙构成为三暖的一个确定解。取 ( 0 ， = ( 墨 一( 1 ：! ： ，( z z 0 7 = ( ； 一；o ) 则 阱( 蔓o j z 。 由于( 蔓， 是只仁，阵，所以 堋小r b w ，z i + 州z + w i z i o 因为z 0 ；o ，取指标集，= ii z i o ，i = 1 ，2 ，n ，对于v f ，w ，o = o ，可得到 w 。= w i 0 访。 0 ，则。z f 。 0 ，f ，。而对于堙， z 。o ：z o j o ：0 ，w i 0 z i 0 ：0 ，i g ，。因此 塞皇苎兰堑兰竺垒丝墨二一 同时 由此可知 w 。oz ，o 。这时 主 ， 则 ( 计匕 ( 主 构成为工哦的一个确定解。取 。 因为z o o ，取指标集j v = f k o ，i = 1 ，2 ，n ，x 于- t v i e n ，w o = 0 ，可得到 所以 w f o = w f o 一嘭o o oz ，o 矿，l c p 无解。 口 通过命题( 3 4 ) 可以看出，对于可解的l c p 问题，只有当m ) m 。时，才能 导出l c p 的解。同时，由于在计算机上实现时，取数过大经常会导致数值困难或 计算失败，所以有必要设计鉴别大瓢是否足够大的检验标准。 3 2k o j i m a 调整规范的推广 这一节中，我们将k o j i m a 等人在 1 】中对大埘的调整的规范推广到求解只似) l c p s 上。 定理s s 如果l c p 是可解的，假设( 二) ，( z z 0 是c 厶的一个严格可行 解，z 为满足以下条件的数： i ) 0 掰一z 。 用反证法证明。如果存在l c p 的一个互补解( 霄，；) 不满足上述条件 令 则 ；) 构舭哦的一个确黼取 因为话，o z ，所以 计算可得 阱阱( 别 阱( 州； 厂n 一 、 ( 1 + 4 刮z t o w ，o + z l w f1 t = 1 f = l z i - l - z 2 0q - + z n o ) 彤 窆z ，。吼。 f = l ( ，w1 7 ( 多 + 。r ( 。z ，+ w z , + 。z 。，+ ，w ，z ， = 0 + o 刁o + 孵五+ 以她z i o 一茹，毛一w ，毛一话，o z ，o 一羁o z ，o + 4 叫z w 而+ 弼z + w o 毛o + 厩。薯o 、l e l + t e l t d ，i d 0 、 一协，z f 一w i 三 i 一话，o 乙。一w ，o 蟊o 瓣 0 一z = 一0 = _ z 0 ，l 塞皇茎兰堡兰堂生羔三l 一 这与f 蔓 口 根据上述定理，我们可以设计一个求解可解的只似) 一l c p s 的大m 算法。 算法3 6 取常数卿a ，满足0 芷 ( 1 + 4 r ) r w 。z 。+ 妻w j z j ，取 f - l m k = 2 m k ，z = h k w k + l , w k + lj z k + l , z o k + 1 ) = w k 缸一 矽，z 。“1 ) k ? = k + 1 ( b ) 如果x k ( z l 。女4 - z 2 0 k + + z 。j ( 1 + 4 k v w 。z 。+ 囊w ，毛j ，利用 ，= l 内点算法迭代产生下一点( w ，w 川，z 川，z 。川) 3 3 关于只k ) 一l c p s 的大数方法的一种识别过程 口 对于任意一个，由于开始不知道其是否可解，所以我们仍然需要设计一个鉴 别不可行l c p s 的识别过程。 定理。z 对于哦的任意互补解( 二 ，( ； c 其中z 。，我们可以通 2 2 一w 巧 。商 、 乙 w 。商 + 产 w 。耐 r ，+w 垃 鼠 毛 矛 阵 d v l - 0 ，即使扩大m 时，；o o ，所以不妨假设m 已经足够大，这时w o o ， ( 品) ，构成为l 哦的一佃懈令 ( = ( 墨) 一 蠹) ，( 多) = ( ；) 一( 委) 复皇苎兰堕兰竺丝堑苎一 ( = ( ( 多 对于指标集= i z 2 i o o ，i = 1 ，2 ，n ，有 w j 。w i 0 一氓。 0 ，毛。= z i 0 一嚣。 o ，f n 可得w ，o 毛o 0 ，f n 对于堙，有z f o = z f o 一嚣o = o ，可得oz i o = o ，i 仨n 。 因此可得 同时 可得 w j oz f o o f = l ：( w ，一葡x z ，一乏) = w t z j 七磊i t 一磊t z i w 暑ls q 黔，+ 善w i 。z t 。+ 4 i t 【互w j z j + 虬z ，w i r z i r j 枷 f = lj = ll e lf e ，上j 这与f 羔肛州阵矛盾o i i ) 如果虿2 o 不成立，那么必然存在牙， o ，七= 1 七2 盯。 + 鲥k s t e p 3 ：如果对角元而，o ，以吼0 做枢轴元进行主转轴。否则检查集合 s = 阳吼= o ，而目o ，1 2 n ，如果s 中，任选，s ，以和而一做枢轴元进 行双转轴，转至s t e p 5 如果s = 中，进入s t e p 4 ： s 刚：取m 一杀嶂脚一卜果对于某爪r 匍= 毒n ， 以f 作为枢轴列指标。令 k i s ：= is 一& t 【吼? = 吼一而口0 供中1 5 s ”+ 1 ) 这时，如果刁= o ，直接进入下一步；否则，以嘞和甬j f 做枢轴元进行双转轴。 s t e p 5 ：如果存在非基变量不为零，转至s t e p 2 ：否则这时可得如下图表 2 6 、，j w 扩 ，l 把则否 nh川u矿 nhuu一 塞皇苎兰堡兰兰堡墼苎 互正工二日 + + 朋。 如果此时人工变量z o = o ，那么( w ，z ) 构成为原始问题的解。算法终止；否则 检查虿2 ：当牙2 o 时，l c p 无解，算法终止：如果牙2 0 不成立，此时州 不够大，取射川= 2 m 。，t # k + 1 ，转至s t e p l 。 几hunhu 复垦大学硬士学位论文 参考文献 【l 】m k o j i m a ，s m i z u n oa n da y o s h i s e ，“al i t t l et h e o r e mo f t h eb i g 纵i ni n t e r i o r p o i n ta l g o r i t h m s ”，m a t h e m a t i c a lp r o g r a m m i n g ，5 9 ( 1 9 9 3 ) 3 6 1 3 7 5 【2 】2 r d c m o n t e i r oa n di a d l c r , “i n t e r i o rp a t h - f 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 g ”，m a t h e m a t i c a lp r o g r a m m i n g ，4 4 ( 1 9 8 9 ) 2 7 4 1 【3 】3m k o j i m a ，s m i z u n oa n da y o s h i s e ，“ap o l y n o m i a l t i m ea l g o r i t h mf o rf lc l a s s o f l i n e a rc o m p l e m e t a r i t y p r o b l e m s ，”m a t h e m a t i c a l p r o g r a m m i n g ，4 4 ( 】9 8 9 ) 1 - 2 6 【4 】4 k m a n s t r e i c h e r ，“ac o m b i n e dp h a s e i - p h a s e i i