（运筹学与控制论专业论文）利用扩张的互补问题求解线性规划的光滑型算法.pdf

摘要 通过利用线性规划问题的最优性条件，我们构造一个扩充的系统，然后利用 光滑型算法来求解扩充的系统，进而考察原线性规划问题的可解性。本文讨论的 算法有以下四个特点。( 1 ) 这个算法在不需要任何正则性假设的条件下是全局收 敛的；( 2 ) 算法中只需要求解一个线性方程组并在每一次迭代中进行一次线性搜 索；( 3 ) 如果所要求解的线性规划问题有解( 因此该问题就有一个严格互补解) ， 那么本算法将会产生该线性规划问题的一个严格互补解；( 4 ) 如果所要求解的线 性规划问题不可行，那么本算法将会正确的检测出该线性规划问题不可行。 关键词：线性规划；光滑规划；严格互补解：全局收敛 a b s t r a c t w ep r e s e n tas m o o t h i n g - t y p ea l g o r i t h mf o rs o l v i n gt h el i n e a rp r o g r a m ) b y m a k i n gu s eo fa l la u g m e n t e ds y s t e mo fi t so p t i m a l i t yc o n d i t i o n s t h ea l g o r i t h mh a s f o l l o w i n gp r o p e r t i e s ：( 1 ) t h ea l g o r i t h mi ss h o w nt ob eg l o b a l l yc o n v e r g e n tw i t h o u t r e q u i r i n ga n yr e g u l a r i t ya s s u m p t i o n ；( 2 ) ro n l yn e e d st os o l v eo n es y s t e mo fl i n e a r e q u a t i o n sa n dt op e r f o r mo n el i n es e a r c ha te a c hi t c r a t i o n ；( 3 ) i ft h el ph a sas o l u t i o n ( a n dh e n c ei th a sas t r i c t l yc o m p l e m e n t a r ys o l u t i o n ) ，t h e nt h ea l g o r i t h mw i l lg e n e r a t e as t r i c t l yc o m p l e m e n t a r ys o l u t i o no ft h el p ；( 4 ) i ft h e 凹i si n f e a s i b l e ，t h e nt h e a l g o r i t h mw i l lc o r r e c t l yd e t e c ti n f e a s i b i l i t yo ft h el p t ot h eb e s to fo u rk n o w l e d g e ， t h i si st h ef i r s ts m o o t h i n g t y p ea l g o r i t h mf o rs o l v i n gt h el ph a v i n gt h ea b o v ed e s i r e d c o n v e r g e n c ef e a t u r e s k e yw o r d s ：l i n e a rp r o g r a m ，s m o o t h i n ga l g o r i t h m ，s t r i c t l yc o m p l e m e n t a r y s o l u t i o n , g l o b a lc o n v e r g e n c e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘茎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名： 专，摒 签字日期： c ，可年月。日 学位论文版权使用授权书 本学位论文作者完全了解苤盗盘鲎有关保留、使用学位论文的规定。 特授权墨盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 、 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 签字日期： 矽刃年 导师签名：岛鸟 签字日期：础降1 月f d 日嘶枷 玩 阳 第一章线性规划 1 1 线性规划基本理论 第一章线性规划 线性规划问题( 1 i n e a r p r o g r a m m i n g , 简记为i j p 闯题) 是运筹学中研究较早、 发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理 的一种数学方法。线性规划所研究的是：在一定条件下，合理安排人力物力等资 源，使经济效果达到最好。早在本世纪3 0 年代末，就有人从运输问题开始研究 应用线性规划的方法。自1 9 4 7 年丹泽( g b d a n t z i n g ) 提出求解线性规划问题的 一般方法一单纯形法之后，标志着最优化学科的建立，在实际应用中日益广泛 与深入。特别是随着电子计算机的发展和计算速度的不断提高，线性规划适用的 领域更加广泛，从工程技术的优化设计到工业、农业、商业、交通运输规划及管 理诸问题的研究中，它已成为必不可少的重要手段之一。 1 1 1 线性规划问题 线性规划问题，就是在一组线性的等式或不等式的约束之下，求解一个线性 函数的最大值或最小值。 线性规划问题( l p ) 的标准形式( s t a n d a r df o r m ) 为： m i n ，( z ) = c 1 工 s t a x = b ， x 0 对于一个l p 问题，下面三种情况必占其一： ( i ) 该l p 问题无解或不可行； ( i i )该l p 问题无界； ( i i i )该l p 问题有最优解。 满足约束条件a x = 易和x 0 的x 称为可行解，全体可行解的集合称为可行 域，记为d 。 定义1 1 1 若，d ，对于一切工d 恒有，( f ) 厂( 工) ，则称，为i j p 的整 第一章线性规划 体最优解。 1 1 2 线性规划问题的一些重要结论 由于这些定理比较普遍，证明过程在许多介绍线性规划知识的基础教程中都 可以找到，所以这里只给出定理内容，证明从略。 定义1 1 2 设约束方程组系数矩阵a 的秩为m ，且ms 1 ，则a 中必存在m 阶 非奇异的予阵b 。为方便起见，不妨设 b = ( p l ，p 2 ，) ， 称b 为l p 的一个基矩阵。向量岛，p ：，p 。称为基向量，其余的列向量称为非基 向量。与基向量对应的变量称为基变量，其余变量称为非基变量。令所有的非基 变量为零，得到的解x = ( 三 = ( b ：6 ) ，称为相应于丑的基本解c b 硒t c s 。u d 。n ，。 基本解满足约束方程组，但不一定满足非负条件，所以不一定是可行解。若基本 解夏0 ，即它也是可行解，则称i 为基本可行解( b a s i cf e a s i b l es o l u t i o n ) 。 定理1 1 2 设x 是标准型线性规划( i j p ) 的可行解。工为( i j p ) 的基可行解 的充分必要条件是z 的正分量对应的系数列向量线性无关。 定理1 1 3 设x 是标准型线性规划( l p ) 的可行解。z 为( l p ) 的基可行解 的充分必要条件是工为可行域d 的极点。 i 定理1 1 4 若d 矽，则d 有极点。 定理1 1 5 若线性规划l p 存在可行解，则它一定存在基可行解。 定理1 1 6 若线性规划i j p 存在最优解，则必存在基可行解是最优解。 由上述几个定理可知，若线性规划问题( l p ) 有最优解，只需要从基可行 解中找最优解，而基可行解的个数不会超过簟个。但是，对于很大的n 和m ，要 算出全部基可行解，并从中选出一个使目标函数取极小值的解，计算量是很大的。 因此需要一种计算方法，按一定的规律只挑选- - d , 部分基可行解，并且收敛到极 小点。在1 9 4 7 年由g b d a n t z i g 提出的单纯形法( s i m p l e xm e t h o d ) 就是这样的 一种方法。 第章线性规划 1 2 单纯形方法简介 对于标准型的线性规划问题，有定理1 1 6 知，如果它有最优解，则必可在 某一基本可行解处达到，因而只须在基本可行解中寻找最优解。单纯形方法是先 找到一个基可行解，即找到可行域韵一个极点，判断这个极点是不是最优解。如 果是，问题就解决了。如果不是，设法找到一个相邻的极点，使新极点处的目标 函数值不大于前一个极点处的目标函数值。这样做下去，经过有限次迭代步骤就 可以找到l p 的极小点或者判断线性规划问题没有最优解。因此，这里主要有两 个问题：一是寻找初始解，二是如何判别和迭代。 1 2 1 单纯形方法的基本思想 考虑标准形式的线性规划 m i n 厂( z ) = c t x s t a x = b ， x 0 ( 1 1 ) ( 1 2 ) ( 1 3 ) 首先我们假定r a n k ( a ) = m o ，假定b = ( 喁9o i - 9 ) 。 记向量 嘭= j 5 f q = ( 瓦，) r ，j = l ，n ； g = b 1 务= ( 云，瓦) 7 。； 以及 甭= 曰一1 则( 1 4 ) 式可以写成 而+ x j f f j = 6 或+ 砜= 矿 ( 1 5 ) j = m + l 显然，如果所取的基不同，则对应的方程表达式也不同。因此我们把( 1 5 ) 第一章线性规划 式所表示的m 个方程称为对应于基b 的典则方程组，简称典式。若i 0 ，则典式 c 5 ，就对应着基本可行解舅= ( 吾) 。当万 。时，该解为非奇异的基本可行解。 对( 1 2 ) 式进行了变化以后，目标函数也要作为相应的变换，将它用非基 变量来表示。 ，( 功= c t 工 = c s t x s + c s t x n - - c s t 西一畏x 0 + c ? x n = c 囊一( c b t 丙一c t v t 、) x n = 7 i 一口芬- c j ) x ， ( 1 6 ) 我们用f o 表示基本可行解i 所对应的目标函数值，则f o - - c r i = r 万，也就是 ( 1 6 ) 式中的常数项。 。 由于瓦，嘎，瓦是单位向量，故当j = l ，m 时， c t b c z - - j c j2 q 因而如果引入下面的记号 p ，一 f2 c ；a 0 一c ，_ ，2 l ，万； 或者用向量表示 = c b b 。1 a c = ( 友，) 兰( 缸，磊) = ( o ，c r i b - 1 一c ) 则( 1 6 ) 式可记为 f ( x ) - c ：b px 因而，经过变换后的问题可叙述如下： r a i n ，( 工) = f o f r 工 ( 1 7 ) s j + b n x n = 玩 ( 1 8 ) z 20 该问题对应的基本可行解i = ( 吾 ，万。 4 第一章线性规划 1 2 2 单纯形法的计算步骤 根据上面所得表达式的系数情况我们给出下面三个定理，这三个定理给出了 单纯形法的迭代步骤。证明从略。 定理1 2 1 如果( 1 7 ) 式中的f o ，则i 是原问题的最优解。 定理1 2 2 如果( 1 7 ) 式中的向量f 有分量幺0 ，而向量兹o ，则原问 题无解。 定理1 - 2 3 如果( 1 7 ) 式中有友o ，且嚷至少有一个正分量，则能找到 基本可行解名，使，岩 o t 。 “庶 l j s t e p6 以代替，得到新的基，回到s t e pl 。 1 3 本文内容安排 论文的组织如下：在第二章中，介绍了线性互补问题及其一些算法；第三 章我们给出了最优性条件的扩大系统，然后讨论一些相关的特性；第四章，我们 介绍求解这一扩大系统的光滑型算法，同时在没有任何假设的前提下给出算法全 局收敛性的证明；第五章是数值试验部分，表明算法的实际应用与理论论证相一 致：最后是结论部分。 在整篇论文中我们用到的表示法如下：“：”表示“定义为”。缈：= 1 ，2 ， n + 1 ) 吼“表示n 维实向量空间，吼：( 相应的，吼：+ ) 表示吼“中的非负( 相应的， 第一章线性规划 正) 向量。大写表示转置。对任意的两个向量x 吼7 和y 吼我们将( ，y r ) t 简 写为( 工，y ) ，其中z ，r 为两个任意的正整数。对于所有的i = l ，2 ，f ，而o 我们则 记为x 0 。对于任意的指标集合k ( 矽x e 缈) 和任意的向量x e 9 t ，x x 表示 从工中去掉f 萑k 的分量玉后所得到的向量。两个任意的正整数z 和厂，0 1 。，表示i x r 维的零矩阵。在没有歧义的情况下我们也用0 来表示这样的零矩阵。对于任意的 l l ，u t 吼，v e c u f ：f 1 ，z ) ) 表示z 一维向量，其中第f 个分量是“f ； d i a g u ，：i 6 l ，表示一个i x r 维的对角矩阵，其中第f f 个对角元素为u ，。 第二章线性互补问题 2 1 线性互补问题 第二章线性互补问题 本章我们介绍线性互补问题( 1 i n e a rc o m p l e m e n t a r i t yp r o b l e m ，简称l c p ) 及 其主要的算法。 线性互补问题是互补问题中最常见、应用最广泛的一类互补问题。早在1 9 3 9 年k a r u s h 研究带不等式约束的连续变量非线性规划的最优性条件时就提出了互 补的概念，然而直到1 9 6 3 年h o w s o n 把一个双矩阵对策的n a s h 平衡点问题转化 为一个线性互补问题，互补问题才引起人们的注意，互补问题的研究才显得重要。 1 9 6 4 年c o t t l e 提出了非线性互补问题。1 9 6 8 年c o t l e 和d a n t z i g 把线性规划问 题、二次规划和双矩阵对策问题统一表述为线性互补问题，这项突破性的工作激 发了互补问题研究的高潮。经过近四十年的研究，互补问题的理论与算法己趋于 成熟，而其在工程、经济和运筹学中的广泛应用使其成为数学规划领域中一门内 容非常丰富的学科。 2 1 1 线性互补问题的一般形式 线性互补问题( l c p ( q m ) ) 的一般形式为：求解向量z = ( 工，y ) e9 c h ， 使得， m x y + q = o ，x 0 ，y 0 ，工r y = 0 ， ( 2 1 ) 其中m 吼“”，q e 贸“。 这类问题有广泛的背景。例如，l j p 问题可以转化为线性互补问题求解。求 解l p 问题 m i n ，( 工) = c t x s t a x = b ， x 0 就可以归结为求解l c p 问题。因为我们知道j c 是该问题最优解的一个充分必要 第二章线性互补问题 条件是k u h n t u c k e r 条件。可以将原l p 问题及其对偶问题转化为： c 五s ，。， o l = i o a r 会 二 + ? ，s = 。， 显然这就是一个l c p 问题。本篇论文的主要内容是依靠这一事实展开的。 2 1 2 线性互补问题的推广形式 ( 1 ) 混合线性互补问题( 札c p ) ，其一般形式是：求x e 吼”，y e 孵，s e 吼“且满 足 似，) ，s ) 2 巳 ( 2 2 ) x 0 ，s 0 ，r s = 0 ( 2 ) 水平线性互补问题( h l l t ) ，其一般形式是：给定n e 欢舢，留吼“， m 欢棚，求石”，s ”且满足 一 m x + n s + q = o ,( 2 3 ) x 0 ，s 0 ，一s = 0 若n = ，时，( 2 3 ) 式即为标准的线性互补问题；若为非奇异矩阵，则( 2 3 ) 式等价于线性互补问题l c p ( 一n m ，一n - 1 q ) 。 ( 3 ) 垂直线互补问题( v l c p ) ，即给定m 吼，g 吼”且 m = 【m 1 ，m ”】r ，日= 【9 1 ，q 4 r ，m 吼吗期，q 吼 ，i = l ，2 ，j l ，砚- m ， 求石9 1 c “满足 m x + q o ，x o ，玉( h ( 肘x + q ) j ) = o ，i = l ，2 ，1 ( 2 4 ) ( 4 ) 线性矩阵互补问题( s d l c p ) ，s 脚，s ? ，$ 分别表示全体玎，l 阶实对称矩 阵、实对称半正定矩阵以及实对称正定矩阵的集合：t r ( x ) 表示矩阵x 的迹，对 x ，y es 定义内积x 木y = t r ( x r y ) ，则线性矩阵互补问题的一般形式是 求x ，l ，s 棚，使其满足下面关系式 y = l ( x ) + q ，x “，y ! x ，| ，x 宰y = 0 ( 2 5 ) 其中q s d o i ) l ：s 舳一s 棚为线性算子，o 为零矩阵。 8 第二章线性互补问题 c 5 ，l o r e n t z 锥上的线性互补问题，记k = t 工= p ) i l 比8 z ，“吼，z 吼，称k 为 l o r e n t z 锥。l o r e n t z 锥上的线性互补问题的一般形式是 求五y 孵且满足 y = m x + q ，x , y ek ，y = o ， ( 2 6 ) 其中m 吼脚，口孵，k 为l o r e n t z 锥。 2 1 3 线性互补问题的分类 根据线性互补问题一般形式中矩阵肘的类型作为分类标准，性互补问题可分为 如下几类： ( 1 ) 若矩阵m 满足，尬0 ，协吼“，则称m 为半正定矩阵，而相应的互 补问题称为单调互补问题。 ( 2 ) 若对任一非零向量工坩，存在某个豇( 1 天a n ) 满足五( 蚴。 o ，则称m 为p 矩阵，而相应的互补问题称为p 矩阵线性互补问题。 ( 3 ) 若对任一非零向量石时，存在某个七( 1s 七n ) 满足x k ( m x ) 兰o ，且 x k + ( 。o ，则称m 为昂矩阵，而相应的互补问题成为昂矩阵线性互 补问题。 显然，昂矩阵互补问题是p 矩阵互补问题和单调线性互补问题的推广。 2 2 线性互补问题的常见算法 目前关于互补问题的研究可以分为两类，一类主要讨论互补问题解的存在 性、唯一稳定性以及灵敏度分析等：另一类集中研究求解互补问题的有效算法以 及相应的理论分析。本节分门别类地介绍了求解互补问题的各种算法。 2 2 1 旋转类算法 最早用来求解线性互补问题的算法是旋转类算法。该类算法是受求解线性规 划的单纯形方法的启发发展而来的，如l e m e k e 法和c o t t l e 法。前者是对原变量、 第二章线性互补问题 互补变量一起进行旋转，而后者是只对原变量进行旋转的。l c m e k e 算法是旋转 类算法中最为成功，应用最广泛的一类算法。该算法对于中小型问题十分有效， 目前在工程和经济领域中仍被广泛地应用。然而，由于单纯形方法的计算复杂性 随着变量个数的增多按指数型增加，因此l e m e k e - 算法似乎仅适合于中小规模问 题，而且只是针对线性互补问题构造的。 2 2 2 内点算法 1 9 7 9 年k h a c h i y a n 证明了求解线性互补问题的椭球算法具有多项式复杂性， 但是该算法的实际计算性能远非预期的那么好。1 9 8 4 年k a r m a r k a r 提出的投影尺 度方法是一个可执行并具有多项式复杂性的内点法。此后，内点法获得了迅速发 展。其中m e g i d d o 构造了原一对偶内点法。由于均等的看待原变量和对偶变量， 出现了一些无论是在理论上还是实际计算性能上都非常好的算法，且原一对偶算 法被扩展到了线性互补问题、二次规划、凸规划、不可微规划、半定线性规划以 及半定互补问题等。 求解线性互补问题的内点法可以看作是求解线性规划的原一对偶- 内点法的 一个自然推广。最早是1 9 9 1 年由k o j i m a , m i z a n o 和y o s h i s e 给出的势减算法，该 算法的基本思路是求解摄动方程组： 墨一胍一目= o ， 工 0 ，工 0 ，s = 膨， 0 ) ( 2 7 ) 若线性互补问题为e o 型的，则对任意方程组存在唯一解( x ( ) ，s ( ) ) 。随着 一o ，( 工( ) ，s ( ) ) 构成了一条趋向最优解集的同伦曲线，这就是所谓的中心路 径。按照沿着中心路径的不同策略，内点算法可以分为路径跟踪算法和势减算法 两大类。路径跟踪算法采用围绕中心路径的邻域避免靠近边界。而势减算法则采 用势函数来避免靠近边界。内点法中，一般在进行一个和几个n e w t o n 步以后对 参数进行调整旷= ( 1 一秒) 。若矽依赖于，l ，则称该算法为小步长算法，否则，称 为大步长算法。对于线性互补问题，大步长路径跟踪算法的计算复杂性为 o ( n l n n ) ，而小步长路径跟踪算法计算复杂性为d ( ，li n n l e ) 。然而，实际计 算效果却是大步长路径跟踪算法大大地好于小步长路径跟踪算法，这样就形成了 l o 第二章线性互补问题 理论分析和实际计算性能之间一个矛盾。p e n g t e r l a k y r o o s 、j a s e n 以及d ek l e k e 等在这方面作了很突出的工作。他们从理论和算法两个方面改进了大步长路径跟 踪算法。通过定义自正则邻近度量函数，他们把大步长路径跟踪算法的计算复杂 性减少到了o ( n 州胆9 1 0 9 ( n 捃) ) ，( 留1 ) 。 若在( 2 7 ) 中，= m x + 口始终成立，则称该算法是可行内点算法，否则为不 可行内点算法。不可行内点算法更容易选取初始点，甚至可以将任意的正点作为 初始点。不可内行点法的另一个优点是可以用来求解没有严格可行内点的问题。 k o j i m a ，m e g i d d o 和m i z u n o 给出了不可行内点算法的全局收敛性。而y z h a n g 首先 给出了不可行大步长路径跟踪算法的多项式复杂性d ( n 2 l n n l e l 。显然，不可行 内点算法的计算复杂性比不上可行内点算法。 在实际应用的原一对偶内点算法中，不可行预估一校正算法是比较有效的。 多数内点算法的应用软件都是基于m e h r o t r a 预估一校正算法基础上设计的。预估 一校正算法在每一步迭代做一次矩阵分解，分别做一个预估步和一个校正步。其 中预估步是为了减少对偶间隙并同时减小不可行性，而校正步使得点列更接近中 心路径，远离边界。 2 2 3 光滑算法 用一个依赖于光滑参数 0 的光滑函数屯去逼近非光滑的n c p 函数中，之 后再用牛顿型方法解光滑化的方程组，这种方法被称作光滑化法( s m o o t h i n g m e t h o d ) 。应该说这是人们非常喜欢的一类方法。 光滑逼近函数可取： 彩。口，6 ，： a 2 1 万( 口一6 + 筹) 旷l a - b l 譬， 。2 8 ， lr a i n ( 盘，参) o t h e r w i s e 还可以取 啦( 口，易) = 丢( 口+ 6 一i ：j i 而) ( 2 9 ) 上面两个函数分别称为一致光滑函数( u n i f o r ms m o o t h i n gf u n c t i o n ) 和 c h k s ( c h e n - h a r k e r k a n z o w s a m a l e ) 光滑函数。此外，还可以针对不同的问题 第二章线性互补问题 使用如下的光滑算数函数 丸( 口 扫) = _ l n e x p ( 一a l t ) + e x p ( - b l l t ) 】 ，。? 。一 九( 口，易) = a 2 + 易2 + - a - b 对光滑化算法的研究吸引了很多学者的注意。尽管已经得到了很不错的数值 结果，但并没有给出收敛性证明。为此，b u r k e 和x u 借助于内点算法中“路径跟踪” 的思想。通过引入中心路径邻域的概念弥补了不足，在对互补问题的某种假设下 建立了算法的全局线性收敛结果。和内点算法比较起来，光滑化算法有两个主要 的不同点：一是初始点不必是内点；二是迭代点列没有严格正的限制。 2 3线性互补问题的光滑算法 2 3 1 线性规划问题互补形式的转化 考虑线性规划问题( l p ) 的原形式： f f l p ) r a i nc t x s t a x = b x 0 和对偶形式： ( d l p ) m a xb r y s t a r y + s - - c ，s 0 ， 其中a 吼，c 6 卯和6 吼? l 是给定的数据，同时我们假设矩阵a 是行满秩的。 根据已知结论，求解( p l p ) 和( d l p ) 问题等价于求解下面的原对偶最优性条 件： c 唧p 孔一料阱煳 而上式为一个混合的线性互补问题。在这篇论文中我们致力于运用光滑型算法解 决线性规划问题( p l p ) 和( d l p ) 的最优性条件( o p c ) 。 2 3 2 光滑型算法的应用 光滑型算法的主要思想是将需要求解的问题重构成为一个带参数的光滑方 1 2 第二章线性互补问题 程组，然后在每一次迭代中运用n e w t o n 型方法近似地求解光滑方程，同时使光 滑参数减少到零，这样就得到了原问题的解。这类算法可以从任意点开始搜索， 而且也不需要中间迭代点是正的。因此这种方法在使用过程中要比内点算法更灵 活。在光滑算法中，光滑函数起到了一个重要的作用。 光滑函数的性质： 对于任意的，a ，b ，c ) e 吼+ + 9 【9 吼，我们有 妒( ，a ，6 ) = c a - c 1 2 0 b - c 1 2 0 ，( 口一c 2 ) ( 6 一c ，2 ) = 特别的当c = 0 时，有 妒( ，a ，扫) = 0 营a 0 ，b 0 ，a b = t 现在针对不同的优化问题已经提出了很多种光滑型算法 1 7 ，9 ，1 6 ，1 8 ，2 2 2 4 。 有些光滑型算法为了保证收敛性必须要求该算法生成的迭代点序列是有界的。为 了保证这一点，需要有很多的前提假设，比如昂+ r 假设和一致p 假设。其他的 一些假设条件可以从【1 1 ，条件1 2 】，【3 ，假设1 1 】，【l ，假设a 】，【2 4 ，引理4 】 以及 1 4 ，假设3 1 】中找到。已知，在【1 2 】中证明由以上给出的所有条件可推出以 下假设。 假设2 1 所求问题的解集是非空有界的。 假设2 1 被用于一些正则的光滑型算法 2 1 ，1 5 ，1 7 。对于单调的互补问题， ，在文 1 9 ，2 0 中证明了假设2 1 等价于 假设2 2 所求问题有一个严格可行解。 假设2 2 被广泛的用于内点算法中，同时也被用在一些光滑型算法中【2 ，4 ， 1 0 】。但是，除了假设2 2 ，b u r k e 和x u 2 还需要额外假设起始光滑参数足够大； e n g e l k e 和k a n z o w 1 0 额外假设起始光滑参数足够小。因此，假设条件2 1 ( 或 假设条件2 2 ) 要弱于大多数光滑算法为了保证算法的收敛性而需要的假设前提。 应该指出c h e n 和y e 8 通过使用扩大的光滑方程来求解昂矩阵线性互补问题 ( l c p ) 提出了一种大r 光滑算法。他们使用的假设是所求l c p 问题有解。但 是在他们全局收敛的证明中还需要一个附加的假设条件【8 ，定理3 3 】。 这篇论文中我们考虑使用光滑型算法在使用扩大的最优化系统( o p c ) 条件 下来解决线性规划问题( l p ) 。我们设计了一种光滑型算法来解决这个扩大的系 统，这个算法有如下的特性： 第二章线性互补问题 可以从任意的点开始进行搜索而且不需要中间迭代点为正。因此这种方法在使 用过程中要比内点算法更灵活。 算法需要求解一个线性方程组同时在每一个迭代点处进行一次线性搜索，从概 念性上看这比许多现有的光滑算法要更简单。 算法在不需要任何正则性假设的前提下是全局收敛的。 如果l p 问题有解，那么算法将得到该l p 的一个严格互补解；如果所求的l p 问题不可行，那么算法将正确的检测出l p 的不可行性。 根据我们的了解，这是第一种求解线性规划问题的光滑型算法具有以上收敛 特性。在文献 2 3 ，2 1 ，1 6 ，2 6 ，1 3 中介绍的光滑型算法思想以及y e - t o d d m i z u n o 在 齐次自对偶线性规划问题 2 5 】中的工作给了我们很多启发。 1 4 第三章扩大系统及其一些特性 第三章扩大系统及其一些特性 3 1 构造线性互补问题的扩大系统 任意给定( j ，i ) 欢：+ 和萝吼”，我们构造最优性条件( o p c ) 的一个扩大的 混合线性互补问题如下： 0 m l s r 0 + o 剃 o 嘲 o ( i ) t ；+ 1 ( x ，t , s ，神o ，c y ，d 吼“咒，j + 钎= 0 ， 其中；0 ：= 扫一眠珞荨c a t 萝一；，；c t 曼+ l - b t 歹表示的是原线性规划、对 偶问题的不可行性，以及线性规划在点( 夕，置；) 处的原对偶间距。在本篇论文中 舅# p 以及；p ，其中p 代表的是所有元素为一的n 维向量。 为了简便，我们采取如下的表示法： 口# ( s ，砷，“；( 工，f ) ，w ；( ) ，五死，z 声( 0 ，s ，瓦0 ) 吼”吼“吼咒 肘； ，以及g ；( o ，0 , 0 ，甩+ 1 ) 吼”吼“吼吼 31() 我们用f 表示( a m l c p ) 的可行集，即f ：= ( w d ) 吼栩+ 柑吼”1i z = m w + q ) 。 从( a m i c p ) 的构造上看，易得( a m l ( ) 有一个严格可行解。比如，如 果我们令 y 高歹，x ：= 殳= p ， f = 1 ，伊= l ，s ；i = 已，以及r = 1 ， ( 3 2 ) 那么( w 口) # ( y ，x ，t ，只s ，种是( a m l c p ) 的一个严格可行解。另外，可以看出m 是个斜对称矩阵，这就表示对于任意的w ：- - ( y ，五f ，e ) e 吼”吼“吼吼， 1 5 _ 1 o 而 c o l a c _ i o _ o o 而 c o _ j a 吖彳 第三章扩大系统及其一些特性 “t u = 兰 t 兰 = 三 t 肘 三 + 三 t 口= 三 t g = c 行+ ，秒 c 3 4 ， 3 2o p c 和a c p 的关系 下面的定理描述了最优性条件( o p c ) 与扩大系统( a m l c p ) 之间的相互 关系，这是通过求解扩大系统进而求解线性问题的基础。 定理3 1 设( 矿，矿) 是( a m i 艘) 的一个严格互补解。那么： ( i ) ( o p c ) 有解当且仅当广 0 。特别的，如果， o ，那么( y 广，f 广，5 广) 是( o p c ) 的一个严格互补解。另外，x l r 是原线性规划问题i j p 的一个最优 解同时( y f ，s ，) 是线性规划l p 的对偶问题的一个最优解。 ( i i ) 如果( o p c ) 可行，那么，( = - c t ，+ 矿y ) 0 。特别的，如果， 0 ，那 么c t f 与一b t y 至少有一个严格的小于零。另外，如果c t x 0 ，那么( d l p ) 是不可行的；如果- b t y 0 ，那么( p l p ) 是不可行的；如果c t ， 0 。根据假设( o p c ) 有解，我们可以记为( i 瓦习，从( o p c ) 和( a m l c p ) 中我们不难看出( 歹，夏，f ，0 ，i ，0 ) 是( a m l c p ) 的解，其中f = 1 0 。那么必要 性可得。 “乍 ：如果， 0 ，那么f = 0 。因此，根据( a m l c p ) 和假设条件有： 从= 订，a t y + s 。= c 广，f ) 飞= o ，以及h 。+ 矿 o 这表明( y i ，；e ，s 广) 是( o p c ) 的一个严格互补解。 ( 赶) 因为( o p c ) 是不可行的，那我们可以得到c t f o 或者- b t y 0 或者 c t ， 0 与- b t y 0 同时成立。这里我们只考虑c t ， o 的情况，其他的情形 相似可证。当c t f 0 的前提下，在每一次迭代中运用n e w t o n 型算法来解决方程组( 4 2 ) ，使 得h ( i x ，m 们- - 0 。算法描述如下： 算法4 1 ( 光滑型算法) s t e p0 取两个常量最仃( o ，1 ) 。选定初始点( w o ，矿) 吼”肘2 吼胂1 那么( w o ，矿) ，。选定7 ( o 5 ，1 ) , i x o 吼+ + 使得三7 + 2 以万 1 1 ( 4 4 ) s t e p4 令m = i t + a ，矿+ 1 = + 五，口川= 矿+ 五矿以及七# 七+ 1 。返回 到s t e p1 。 4 2 光滑型算法的特性 稍后我们将会看到算法4 1 有我们所需要的收敛特性。即，如果l p 有解， 那么算法4 1 将生成l p 的一个严格互补解；如果l p 不可行，那么算法4 1 正确 的检测出i j p 的不可行性。根据我们所了解的现有的光滑型算法中还没有以上这 些收敛特性。 命题4 1 雅克比矩阵h ( i t ，w d ) 对于所有的 ( i t ，m ：= ( i t ，y ，u ，口，口) ：= 钮，) ，工，l 幺j ，d 吼吼”贸“吼吼吼4 吼 是非奇异的，其中 0 。 证明：因为 0 ，易得函数日是可微的，其雅克比矩阵可由下式计算得出 其中： 日。叫= 簪 0 m 删* 0 m 叶1 ) 一mi o 珑磁 ，。：=三三：，d：；vpc薏c，“，q，：r9-)， 叫l 娑o u ( 俐) o f 川阳| ，咖凳( 脚) id u 1 9 第四章光滑型算法及其收敛性 娑o u ) ；咖甓o u 壮d 1 ， i 瓤划叫嚣似, u l , v t ) ：i ed 对于任意的，w ，u ) 9 【+ + 吼肿斛2 叼+ 1 ，如果想证明h ，m d ) 是非退化的，只 需要证明 一m，。 i 珑磁j 是非奇异的。令 ( d w , d o ) ：= ( d r ，d u ，d o , d r ) ：= ( d y ，d x , d r , d s , d s ，d r ) e 爨”吼”暖飒受”吸以及 - 珑m 龇 。i p 叫9 - o ( 4 5 ) 那么我们只需要证明d w = o 以及d v = 0 。 根据珑和磁的定义形式，( 4 5 ) 式可转化为 一黼+ ，o d v = o ( 4 6 ) 娑，删) a u + - 要- - ( a , u , v ) d u ：o ( 4 7 ) o uu “ 从( 3 3 ) 式我们可得 - d w r m d w = 0 ( 4 8 ) 利用( 4 8 ) 式和，o 的定义，由4 6 式可得 d u r d v = d w r i o d v = d w r m d w = 0 ( 4 9 ) 结合( 3 4 ) 式和( 4 9 ) 式，我们有 d o = 0 ( 4 1 0 ) 对于任意的f f ，因为 薏( 腓班( o ，2 煅嚣( 脚眯( 0 2 ) ， 根据( 4 7 ) 和( 4 9 ) 式我们可以得到 瓤删，r c m o ， 以及d v = 0 。这样结合( 4 7 ) 式可以得到d u = 0 。因为( 4 6 ) 式的第二个方程 第四章光滑型算法及其收敛性 司以写成如下形式： - a 7 方+ c d f 一白d 秒一凼= o ， 由于d u = 0 ，d r = 0 以及( 4 1 0 ) 式成立那么我们可以得到匆= o ，又因为a 是 一个满秩的矩阵那么表明a y = 0 。 因此d w = o 同时d v = o 。证明完毕。 注释4 1 假设数列 ( 矿，产，扩) ) ，是由算法4 1 得到的，其中 ，产，矿) ；( j u k , y k , u k , 矿，移) ；( ，y k , ，矿，矿，s k , ) 吼吼”贸“吼吼吼“晚 ( i ) 由( 4 3 ) 的第一个方程有 七+ 1 = t + 五舭= ( 1 一五) + 五矽( ，矿，耖) o ( 4 1 1 ) 这表明对于所有的k o 有 o 。根据命题4 1 ，日。，矿，矿) 在矿 o 时 是非退化的，那么我们可以得到对于所有的k o 方程( 4 3 ) 是有解的。另 一方面，令轳= ( ，矿，矿) 以及r ( 功# 日( + c l ，h ) 一日( 鲈) 一础( 轳) a h 。 那么根据( 4 3 ) ， 忡( 三+ 础。) i i - - i r ( 口) + 日( 轳) + a r h ( 艺) ，1 2 1 1 - 0 时日( ) 是连续可微的。对于所有的k 0 我们有 l i r 2 ( 叻0 = o ( 功。那么根据( 4 1 2 ) 得线形搜索( 4 4 ) 是完各的，也就是说 算法4 1 是完备的。 ( i i ) 从( 4 4 ) 式中我们不难看出数列钏日( k 矿，矿) i i ) 是单调递减的，这也表明 数列 夕( ，扩) ) 也是单调递减的。 ( i i i ) 令q ； ( ，w , v ) e 吼+ 吼”+ 一+ 2 粤州：( ，w ”) f ，筇( ，w p ) ) 。那么 o ，w o ，扩) q 。实际上，根据如下两方面我们可以得到，对于所有的k 0 ， ，扩) q 。首先，根据( a m l c p ) 可行域的线性性质和n e w t o n 方程 ( 4 3 ) ，对于所有的k o ，我们可以得到( ，矿) f ；其次，因为如果 对于某些指标，o 有艺：= ( 7 ，抄) q ，那么根据( i i ) 有 2 1 第四章光滑型算法及其收敛性 m 一酗( 乏h 1 ) = ( 1 一a ) + 五矽( 分) 一羁8 ( 乏1 ) 芦( ( 掣) - p c 2 , “1 ) ) ， 由此可以得出“1 筇( 掣+ 1 ) 。 ( i v ) 结合( 4 1 1 ) 以及上面的结论( i i i ) ，我们可以得到 h 1 = ( 1 一五) 。+ 五即( ，矿，矿) ( 1 一五) 。+ 五= l ， 这说明数列 ) 是单调递减的。 4 3 光滑型算法的全局收敛性 卜