求解p 2c0线性互补问题的一个非精确非内点连续化算法.pdf

摘要 非内点连续化算法自上世纪九十年代中期引起国际优化界广泛关注以来，得 到了快速发展并且取得了很好的研究成果，已经可以用于求解各种优化问题。在 非内点连续化算法中，求解牛顿方程是其核心步骤，也是工作量最大最集中的部 分。在以往的研究中都是采用精确求解方程的办法，这就造成了很大的计算量， 特别是对一些规模比较大的实际问题，形成了实际应用中的诸多困难。而与此同 时，利用非精确牛顿法求解方程的研究有了很大进展。这种方法不要求精确地求 解，它在每一次迭代求解牛顿方程时都在牛顿方程右端加上一个扰动项，从而达 到提高计算效率的目的。 本文提出了一个求解只线性互补问题的非精确非内点连续化算法，该算法将 非精确牛顿法引入到非内点连续化算法中，利用非精确牛顿法求解迭代方向。而 后证明了该算法是适定的，并且在合适的假设下保持了非内点连续化算法良好的 收敛性质，即具有全局线性收敛性和局部二次收敛性。该算法在理论上比非内点 连续化算法更有效率，实际上也具有更好的数值实验结果，这点在求解大型稀疏 矩阵线性互补问题上尤其明显。 关键词：非精确牛顿法；非内点连续化算法；全局线性收敛性；局部二次收敛 性 a b s t r a c t i nt h em i d d l eo ft h e9 0 so ft w e n t i t hc e n t u r y , n o n - i n t e r i o rc o n t i n u a t i o na l g o r i t h m r e c e i v e de x t e n s i v ea t t e n t i o no fi n t e r n a t i o n a l o p t i m i z a t i o nf i e l d f r o mt h e no n ， n o n - i n t e r i o rc o n t i n u a t i o na l g o r i t h md e v e l o p e ds of a s tt h a tc o u l dr e s o l v em a n yk i n d s o fo p t i m i z a t i o np r o b l e m s i nt h en o n i n t e r i o rc o n t i n u a t i o na l g o r i t h m ，s o l v i n gn e w t o n e q u a t i o ni si t sc r i t i c a ls t e pa n da l s ob r i n g sah e a v yw o r k l o a d i nt h ee x i s t i n gp a p e r s ， t h e ya l l s o l v et h ee q u a t i o ne x a c t l y , s oal a r g ec o m p u t a t i o nw o r k l o a di s p r o d u c e d ， e s p e c i a l l yf o rt h ep r o b l e m sw i t hl a r g es p a r s em a t r i x e s a tt h es a m et i m e ，u s i n gi n e x a c t n e w t o nm e t h o dt os o l v et h ee q u a t i o nh a sb e e nd e v e l o p e dq u i c k l y t h i sm e t h o dd o e s n o ts o l v ee q u a t i o n se x a c t l y i ne a c hi t e r a t i o n ，i ta d d sap e r t u r b a t i o nt ot h er i g h ts i d eo f n e w t o ne q u a t i o nt or e d u c et h ec o m p u t a t i o nw o r k l o a d i nt h i sp a p e r ，w ep r o p o s ean e wi n e x a c tn o n - i n t e r i o rc o n t i n u a t i o na l g o r i t h mf o rt h e e 0 l 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 t h i sn e wa l g o r i t h mc o m b i n e si n e x a c tn e w t o n m e t h o da n dn o n - i n t e r i o rc o n t i n u a t i o na l g o r i t h m ，u s i n gi n e x a c tn e w t o nm e t h o dt o s o l v et h ee q u a t i o n a n dt h e n ，w ev e r i f yt h a tt h i sn e w a l g o r i t h mi sw e l ld e f i n e da n di t h a sg l o b a ll i n e a r c o n v e r g e n c e a n dl o c a l q u a d r a t i cc o n v e r g e n c e w i t h p r o p e r a s s u m p t i o n s t h e o r e t i c a l l yt h i sn e wa l g o r i t h mi sm o r ee f f i c i e n tt h a nn o n - i n t e r i o r c o n t i n u a t i o na l g o r i t h m ，a n dh a sab e t t e rr e s u l ti nt h en u m e r i c a lt e s t s ，e s p e c i a l l yf o r l 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 sw i t hl a r g es p a r s em a t r i x e s k e yw o r d s ：i n e x a c tn e w t o nm e t h o d ；n o n - i n t e r i o rc o n t i n u a t i o na l g o r i t h m ； g l o b a ll i n e a rc o n v e r g e n c e ；l o c a lq u a d r a t i cc o n v e r g e n c e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫注叁堂：或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者躲馅译签字嗍研年月易日 学位论文版权使用授权书 本学位论文作者完全了解基鲞盘堂有关保留、使用学位论文的规定。 特授权岙鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位敝作者签名怕辞 签字日期：w 啊孑年占月易日 导师签名： 签字日期：溉6 月3 日 第一章绪论 第一章绪论 1 1 互补问题及其算法的发展历史 互补问题首先是由美国的c o t t l e 于1 9 6 4 年在他的博士学位论文“n o n l i n e a r p r o g r a m sw i t hp o s i t i v e l yb o u n d e dj a c o b i a n s ”中提出的。而后，c o t t l e l9 6 4 年的文 献 1 】和d a n t z i g 与c o t t l e 合作的1 9 6 7 年的文献 2 】中都曾指出：线性规划与二次 规划是线性互补问题的特例。在c o t t l e 与d a n t z i g 合作的1 9 6 8 年的文献【3 】中更 指出：双矩阵对策问题也是线性互补问题的一个特例。除此之外，线性互补问题 还包括了最优停止和市场均衡问题等。非线性互补问题、混合互补问题和隐互补 问题包括了更多的数学问题，如一般非线性规划的k k t 条件是混合互补问题的 一个特例。互补问题被提出以后，很快在工程技术中得到了重要的应用，在力学、 交通、经济、金融、控制等许多领域都可以利用互补问题的模型解决很多实际问 题。 由于互补问题应用广泛，许多学者都参与到这项研究中来。到八十年代中后 期，经过2 0 余年的努力，在算法研究方面取得了丰硕成果【4 】：( i ) 对线性互补问题， 有直接方法( 如l e m k e 法，c o t t l e d e n t z i g 法) 和迭代法( 女i m a n g s a r i a n 法) ；( i i ) 对非线 性互补问题，有不动点法，同伦法，投影法，n e w t o n 法等，其算法的特征是， 在迭代中需要求解线性互补子问题或者二次子规划。l e m k e 算法是这一时期最著 名的方法之一。 随着八十年代科技与经济的发展，互补问题变得越来越重要。这就刺激了对 其算法的进一步研究，出现了八十年代后期的研究高潮。在这将近十年的时间里， 学者们提出了许多有效算法，并且完善与丰富了算法的收敛性理论。这些算法主 要包括光滑方程法，非光滑方程法，可微无约束优化法，g l p 投影法，内点法和 非内点连续化算法等。其中非内点连续化算法是由c h e n h a r k e r 5 于1 9 9 3 年提出 的，并以其众多优势吸引了学者们的注意，取得了迅速的发展。纵观当前互补问 题的研究现状，不难发现非内点连续化算法仍是求解互补问题的十分有效的算法 之一，并且经过多年的发展已经取得了很好的结果 6 】- 【1 7 】，即在适当的假设下 该算法具有全局线性收敛性和局部超线性( 局部二次) 收敛性。另外，由于该算 法不但具有路径跟踪算法的主要特征，而且能取任何初始点及充分选取步长，在 实际计算中也有令人满意的效果。 在利用非内点连续化算法求解互补问题时，利用牛顿法求解非线性方程是计 第一章绪论 算量最大最集中的步骤，特别是在互补问题矩阵是大规模稀疏矩阵时更为明显。 牛顿法求解非线性方程是精确求解，必然会产生很大的计算量，那么能否利用非 精确牛顿法来求解非线性方程呢? 与此同时，非精确牛顿法也得到了极大的发展， 取得了很好的研究成果【1 8 】【2 5 】，即选取适当的强制参数时该算法是局部超线性 ( 局部二次) 收敛的。为了进一步提高非内点连续化算法的计算效率，降低计算 量，本文将非精确牛顿法引入到非内点连续化算法中，利用非精确牛顿法求解迭 代方向，提出了一种新的非精确非内点连续化算法，并证明了新算法的适定性， 全局线性收敛性和局部二次收敛性。在随后的数值实验中，新算法也表现出了令 人满意的计算效果。 1 2 线性互补问题 线性互补问题是最简单的一类互补问题，但同时也是研究最深入、应用最广 泛的，是运筹学中的一类基本问题。 首先给出几类矩阵的定义。 定义1 1 ：矩阵m r 被称为半正定矩阵，如果x r m x 0 ，v x r “；m 被称 为正定矩阵，如果x t m x 0 ，v x 尺“，石0 定义1 2 ：矩阵m r “”被称为昂矩阵，如果对v x r “，z 0 ，存在一个分量 x k o ，使得x k ( m x ) 0 显然，半正定矩阵必是咒矩阵。 定义1 3 ：矩阵m r 称为只矩阵，如果存在一个常数f 0 使得对v x r 8 有 ( 1 + f ) 五“级) ，+ 薯( 矗岔) ，0 ， f e ，+ ( 上)f e ，- ( j ) 其中 ( 工) ；( fj 西( 尬) ， o ，i = 1 ，1 ) ，( 而= l ， ，刀) ( 工) _ 下面给出线性互补问题的定义。 定义1 4 ：给定矩阵m r “，向量q r “，求( x ，s ) r 2 ”使满足： 2 第一章绪论 ( x ，s ) 2o ，s = m x + q ，x t s = 0 ， 称为线性互补问题，记作l c p ( m ，g ) 当m 为不同的矩阵时，l c p ( m ，g ) 有不同的类型。若m 为半正定矩阵，则 l c p ( m ，g ) 称为单调l c p ；若m 是昂矩阵，旦l l jl c p ( m ，g ) 称为p o l c p ；若m 为只矩 阵， i 1 1 l c p ( m ，g ) 称为p , l c p 。本文主要讨论了一种新的求解p o t c e 的算法。 第二章预备知识 2 1 简介n c p 函数 第二章预备知识 定义2 1 ：函数沙：r 2 专r 1 被称为“n c p 函数”，如果对v ( a ，6 ) t r 2 ，都有 g t ( a ，6 ) = 0 c ，a 0 ，b 0 ，a b = 0 n c p 函数有很多种形式，下面给出几个常用的n c p 函数以及它们各自的性 质。 ( 1 ) m i n 函数： 。= m i n a ，6 ) 容易验证，r a i n 函数是一个朋铲函数。m i n 函数的不足是在直线a b = 0 上 的点均不可微，这使得映射m i n ( x ，f ( 功) 不可微。m i n 函数还有另外一种表达式： 缈k 。( 口，6 ) ：委( 口+ b 一- b ) 2 ) ， ( 2 1 ) 这种形式在算法设计中非常有用。 ( 2 ) f i s c h e r - b u r m e i s t e r 函数。 知( 口，6 ) - 口2 + 6 2 一( 口+ 6 ) ，v ( a ，6 ) t 苣r 2 定理2 1 ：函数是一个凸朋碧函数，且在任意点( 口，6 ) t 0 可微，y 2 船在 平面上任意点连续可微。 ( 3 ) y ge v t u s h e n k o 和v a p u r t o v 提出了如下的c p 函数： ，伊e p ( a ，6 ) ：= 一口6 + 寺( ( 口+ 6 ) 一) 2 ，v ( 口，6 ) ， 其中符号( f ) 一：昙( h - t ) 0 是待定的步长，方向d 称为光滑牛顿方向。 对于c p 函数( 口，b ) ，利用式( 2 1 ) ，bc h e n ，p t h a r k e r ，ck a n z o w 和s 弘锰( ，口，6 ) ：a + b - x ( a ：_ - b ) 2 + 4 一2 ，( 口，6 ) t r 2 ， o 由光滑函数收膦( ，a ，b ) 可得到互补问题n c p ( f ) 的光滑逼近方程： i 彤删船( ，五，互( 力) l 西( ，工) ：= i ； l = o ， 0 【- 虼嬲( ，毛，c ( x ) ) j 6 第二章预备知识 2 3 非精确牛顿算法 令f ：r “_ 足“是一个连续可微的非线性映射，求解大型稀疏非线性方程 f ( x ) = 0 ( 2 4 ) 在工程以及科学计算中经常遇到。 在所有的求解非线性方程( 2 4 ) 的方法中，牛顿法是最基本最受欢迎也是最重 要的一种 3 3 1 。局部二次收敛性是其很多优势中最吸引人的一个。但是，牛顿法 的计算量也是非常大的，尤其在问题的规模非常大的情况下更为明显，这是因为 在每个迭代步中，都要求解牛顿方程 f ( x ) + ，( 矿) c t = 0 ，( 2 5 ) 其中x 是当前迭代点，7 扛。) 是f ( x ) 在x 点的雅可比矩阵。牛顿方程的解d 被称作牛顿步。得到牛顿步后，下一个迭代点由工“1 = x + d 给出。 为了提高牛顿法的计算效率，d e m b o ，e i s e n s t a t 和s t e i h a u g 提出了非精确牛顿 法 3 4 1 ，它是牛顿法的一个推广，以下给出它的一个简要描述。 算法2 1 非精确牛顿算法 3 5 】 s t e p l ：给定x o r “ s t e p 2 ：令k = 0 ，l ，2 直到迭代序n x ) 收敛为止 s t e p 2 1 ：选取某个矿【o ，1 ) s t e p 2 2 ：非精确地求解牛顿方程( 2 5 ) ，并使矛满足 l i f ( x k ) + f 7 ( ) 孑。0 彳8 f 。) 1 1 ( 2 6 ) s t e p 2 3 ：令x “1 ：x k + 矛 在算法2 1 中，矿称作第k 步的强制参数，矛称作非精确牛顿步，式( 2 6 ) 称作非精确牛顿条件。 在非精确牛顿法的每个迭代步中，首先应该选择一个实数矿，然后通过近似 地求解牛顿方程得到牛顿步矛因为f ( x ) + f ( ) 矛既是牛顿方程的剩余也是 f ( x ) 在x 点的局部线性型，所以非精确牛顿条件( 2 6 ) 既反映了局部线性型范数 7 第二章预备知识 的减少也反映了求解牛顿方程的精确度。因此在求解牛顿方程时，强制参数扮演 了控制精确程度的角色。特别地，如果对所有的k 都令矿= o ，那么非精确牛顿法 将退化成牛顿法。 非精确牛顿法被广泛应用于很多领域，并且被公认为是求解非线性方程( 2 4 ) 的最有效的工具之一。 非精确牛顿算法和牛顿算法一样，是局部收敛的。 定理2 4 ( d e m b oe ta 1 3 4 ，t h e o r e m2 3 】) ：设f ：r 4 一r ”连续可微，x + r ”满 足f ( x ) = 0 并且f ( z + ) 是非奇异的。给出0 ，7 n m x f 1 如果非精确牛顿法的强 制参数 矿) 对所有的k 满足矿 f 0 使得对v x o m ( x ) ， m ( x ) _ x ：忙一x + l i o ，函数是连续可微的，则令( ) 表示巴( ) 在点国r 2 ” 。、一m i 佃净b i 国m t ( 妫j ， 。5 ) 妒删；搬 1 _ 丽x i - - $ i 儿i ， 肛净抛 + 丽萧x i - - s 雨i 以z ) ， 其中d i a g u ，：f i ) 表示第f 个对角元素为“，的对角矩阵。 综上所述，由式( 3 4 ) 可知i 求解光滑方程巴沏) = o 并且逐步减小光滑参数 至o 等价于求解叫m ，g ) 1 0 第三章非精确非内点连续化算法及其收敛性分析 s t e p 0 ：取万，厂，盯( 0 ，1 ) ，f 【0 ，1 ) ，x o r “为任意向量，令实数脶 0 ，令 s 。= 尬o + q , c o o ：= ( x 0 ，s o ) ，乇- 风, g + ol 厶选取实数使它满足2 i 且0 气( 扩) l i 矾令k 0 s t e p l ：若f o ( r o ) = 0 ，则停止；否则转到s t e p 2 。 s t e p 2 ：若气( ) = o ，那么缈m - - ( 0 t ，哦= 1 ，转s t e p 4 ；否则通过方程 气( c o ) a c o = 一气( c o ) + 解出a r o 一( 缸，a y ) r 2 n , 方程( 3 6 ) 中r k r 2 n , r k 的前聆个分量为0 ，且 恢( ) i i s t e p 3 ：令晚是1 ，万，万2 ，中满足不等式 ( 3 6 ) ( 3 7 ) i i f , ( c o + 0 。a o j ) l l - o ( 3 ) t k ) 单调递减且对讹k ，t k 0 由算法3 1 初始点的选取，易得风 0 利 用数学归纳法，不妨设某个l k ，“ o ， 肌= ( 1 一而d 而鸥) 仍胁 由f ，仃，岛，r , e ( o ，1 ) 知肼+ l o 因此，对v 后k ，吆( c a ) 非奇异，即s t e p 2 是适定的。 再证明s t e p 3 的适定性。给定某个k k ，对v 口( 0 ，1 ) ，令 y ( 口) ：= 厶( c a + t z a c a ) 一( c a ) 一口吆( c a ) a c a 。 由s t e p 2 有 ，( 口) = 气( 矿+ a a c a ) 一( 矿) 一口( 一& ( ) + 准) 第三章非精确非内点连续化算法及其收敛性分析 = 气( 国+ a a o j ) + ( 口一1 ) f u k ( c o ) 一a r , 0 气( 国+ 必彩) 0 = i l ( 1 一口) 气( 国。) l l + l l y ( 口) 0 + 0 口吃0 _ _ ( 1 - o t + a t ) i l l 4 + 愀口) i i 以下估算咿 ) 1 1 由于当段 o 时，气( 矿) 连续可微，所以对v 口( o ，l 】，有 ： 帜口) 8 = d ( 口) ( 3 1 2 ) 因此，j 历( 0 ，1 ) ，满足对v 口( 0 ，a - ) ，有 0 气( + a a c o ) l i ( 1 一口+ 们) 砒 至此完成了s t e p 3 适定性的证明。 最后证明s t e p 4 的适定性。分后k 。和尼k ：两种情况讨论。 当j j k l 时， 当后k 2 时， 吆( + 1 ) 忙0 乞( 矿+ 1 ) 一吃( 矿“) 0 q 石而南丽鸱段 雨1 靠t ) ( 1 - t ) 赡钒 + ( 1 + “ 【1 一仃( 1 一t ) o k f l ，u , = 跪 f 血( t o k “) i i 0 称为该邻域的宽度。 那么，给定( 0 ，风】，光滑路径邻域片为 n ( f l , ( 0 ，风) ) # 国n ( f l , p ) ：( o ，觞) ) ( 3 1 3 ) 本文始终在以下的假设下进行研究。 假设3 1 ：由式( 3 1 3 ) 定义的光滑路径邻域片是有界的。 这个假设在研究非内点连续化算法时是一个基本的假设，因为大多数保证算 法全局收敛性的假设都是充分条件，例如忍+ r 假设，一致p 假设等。 由引理3 2 的( 3 ) 可知，假设3 1 可以保证算法3 1 产生的迭代序列是有界 的。在下面的收敛性分析中，要经常用到这个事实。 引理3 3 ：设m 是圪矩阵，并且假设3 1 成立，那么算法3 1 产生无穷迭代序 列 ( 以，矿) ) 。战j j 1 i m 。一以= o 证明：由假设3 1 和引理3 2 的( 3 ) 可知， ( 以，c o ) ) t e k 有界。设( 肛，国) 是 ( 段，) ) 。战的任一聚点，则存在一个无限指标集k 满足 l i m 腻，t 一( 段，矿) = ( 肛，国+ ) 由引理3 2 ( 2 ) 知，段 o 可以推出肛o 下面证明肚= o 反设肛 0 由于& ( ) 是连续可微的，有 l i m 懈，。一( 矿) = 气( + ) ，l i m 腻，。一吆( 矿) = 吆( 国) 第三章非精确非内点连续化算法及其收敛性分析 如果存在一个无限子集k 。= 毛，奄，砖们 ck 满足 吆( 矿) = o 那么由算法3 i 的s t e p 2 知， 最= 1 对v i k ”，有 纸+ = 反( 1 一再赤盯) 心 令i 专o o ，有 吣肛郅一可靠盯) 肛 得到矛盾。因此，不失一般性地可以假设，对v k k7 ，有 & ( c o ) o 令 反：= ， 由算法3 1 的s t e p 3 知， i i 气( 缈。+ 反) 0 1 一盯( 1 一f ) 哽】觚 又有 0 气( 国+ 反缈) 1 1 ：1 1 y ( 反) + 气( 国) + 反( 一( 国) + ) 0 ：i i y ( 瓦口) + ( 1 一反) & ( 国) + 反吃) 4 = 1 1 - ，( 反) 0 + ( 1 一反) l 厶( 国) 0 + 反i i 0 0 y ( 反) 0 + ( 1 一反) 局+ 反f 局哝 因此有 【l o - 0 一f ) 反】触耖( 磊) 0 + ( 1 一反) 局+ 嗄f 局逸， o 忙( 反) 0 + ( 1 一f ) 反( 仃一1 ) 触 不等式两边同时除以反，并对k - - 4 , o o 取极限。由式( 3 1 2 ) 知( 1 _ f ) ( 盯一1 ) 触0 ， 1 6 第三章非精确非内点连续化算法及其收敛性分析 得到矛盾。 证毕。 以下的定理讨论了算法3 1 的全局收敛性。 定理3 1 ：设m 是r 矩阵。算法3 1 产生的序列记作 ( 从，) ) 。k ，如果假设 3 1 成, - 5 - ，那么迭代序列 ( 以，) ) 。战是有界的，并且该序列的每一个聚点( 肛，国+ ) 都满足从= 0 ，彩三 证明：由引理3 3 知肛= 0 由引理3 2 的( 3 ) 以及兄( ) 的连续性知0 3 + 是 l c p ( m ，g ) 的一个解。 3 3 全局线性收敛性和局部二次收敛性分析 首先我们给出三个假设，分别为假设3 2 、假设3 3 和假设3 4 ，以及它们z 间的关系，并在这三个假设下研究算法3 1 的全局线性收敛性和局部二次收敛性。 假设3 2 ：令 段) 。e k 和 矿 。配是由算法3 1 产生的序列，其中k z 是由式 ( 3 1 1 ) 定义的。那么，存在c o 使得对讹k ：都有i i 彩忙c 段 假设3 3 ：令 魄，) ) 。战是由算法3 1 产生的序列，那么对所有的露k ：，都 存在一个常量仑 o 使得i i 【吆( 矿) 】一1 1 - 0 ，对所有的k ，k k ，都满足 i j 忙c l 段， 因为对弘 o ，毛( ) 都是非奇异的，所以 m a x i l 【最( ) 州：k 1 州2 一k o - 1 n 是一个正的有限数。因此，利用与命题3 1 相似的证明方法， 个标量c 2 0 ，对所有的k l ，2 ，- 1 n ，满足 ( 3 1 4 ) 可以得到，存在一 第三章非精确非内点连续化算法及其收敛性分析 i a o ) 忙c 2 段 ( 3 1 5 ) 综合式( 3 1 4 ) ；f 1 1 ( 3 1 5 ) ，得到假设3 2 成立。 证毕。 设m 是半正定矩阵并且假设3 2 成立，那么由命题3 1 和命题3 2 可以得到 若假设3 3 和假设3 4 中有一个成立，则假设3 2 成立。因此假设3 2 严格弱于假 设3 3 和假设3 4 。特别需要指出，假设3 2 并不意味着l c p ( m ，q ) 的解的唯一性。 下面讨论算法3 1 的全局线性收敛性。 对弘r ，c ；( 以，6 ) r 2 ，令v 。矽( ，c ) ：- - v ( 。，( ，a ，6 ) 表示对变量口，b 的梯 度。设 ) 。战，是算法3 1 产生的序列，其中k ：由式( 3 1 1 ) 定义。引入记号 斫：= ( ( 缸) ，( a s ) ，v ie i ，v ke k 2 引理3 5 ：矽是由式( 3 1 ) 给出的函数。 ( 以，) ) 。e k 和 ) 。e k ，是由算法3 1 产生的序列，其中k ：由式( 3 11 ) 定义。那么对每个i i ，k e k 2 ，v 口【0 ，1 ) ，下式均 成立 ，群+ 口斫h 魄翮一四群矽魄翮t 斫l 丢0 斫1 1 2 证明：令蜈( 版，群) 表示矽的关于变量磷( v 后k z ) 的雅可比矩阵。那么经过 直接计算可得 舭翮= 丽 - ：1 二l 讹吗 因此对v f i ，k k 2 ，都有 0 略( 以，群) i | ，l 以 并且对v i i ，k k 2 ， i ( 以，群+ 口斫) 一妒( 熊，群) 一a v 露( 以，科) t 斫i 一= 卜f ( v 露矽( 段，群+ 彩斫) 一v 群矽( 熊，群) ) t 斫出i 甜叭面) t 略( 从，群+ 口驴a m k ) a o k d r d t l 鲋f t 胍( 以，群+ 口护斫) k r t l l 斫1 1 2 1 9 第三章非精确非内点连续化算法及其收敛性分析 崭f t 。- 熊! - d r d t 。1 1 2 匀斫1 1 2 证毕。 定理3 2 ：设m 是昂矩阵。 ( 以，) 九e k 和 ) 。函：是由算法3 1 产生的序 列，其中k ：由式( 3 11 ) 定义。如果假设3 1 和假设3 2 均成立，那么存在常量0 ( 0 ，1 ) 并对v k k 有 版+ 。讯 证明：k 。，k 2 是由式( 3 11 ) 定义的。对v 尼k ，要么k k 。要么七k ：n n n 下分两种情况讨论。 当七k 。时，有最= 1 由算法3 1 的s t e p 4 ，有 以+ 。= 仇a 庞= 己以， 其中 c l ：= 1 一而丽1 盯 ( 3 1 6 ) 1 l + ( 1 + f ) ( 1 一f ) 。 当k k 2 时，设a r o 是由算法3 1 中式( 3 6 ) 产生的，对v 口( 0 ，l 】，令 y k ( 口) 车气( c o 。+ a a r o ) 一吆( t o ) 一口吆( t o ) a r o ( 3 1 7 ) 那么 0 吃( 矿+ 必矿) i 气( 矿) + 口( 一吃( 矿) + 咯) i i + | p ( 口) i i ( 1 一口) 0 气( 国) 0 + 口0 气8 + 0 t 。( 口) 0 ( 1 - a ) f l # t + 口f 局+ i i y ( 口) 0 = ( 1 一口+ 鲥) 局+ l l y ( 口) 1 i ( 3 i s ) 因此 ( 口) | i = i i 气( + 础矿) 一气( 矿) 一口吆( 矿) a r o 。0 = 0 由地( c o + a a r o ) 一西胁( c o ) 一砷幺( 彩。) a r o 0 第三章非精确非内点连续化算法及其收敛性分析 令 = 丽a 2 、厨n 巧丽4 丢二1 1 斫 1 2 = 期砑0 2 鱼盈 2 拓掣c | ? z ( 3 1 9 ) ( 3 2 0 ) 那么由式( 3 1 9 ) 知，对v 口( 0 ，西) ，有 胪( a ) _ ( 1 - o ) ( 1 - t ) f l c q t k ( 3 2 1 ) 因此，由式( 3 1 8 ) 和( 3 2 1 ) 知，对v 口( o ，舀) ，有 0 & ( 国+ u a c o ) 0 一( 1 一仃( 1 一f ) 口) 局 _ ( 1 - ( 1 - t ) a ) f l l “, + 0 y ( 口) i i 一( 1 一盯( 1 一f ) 口) 局峨 = ( 盯一1 ) ( 1 一t ) a 1 3 1 t k + l l y ( 口) 0 0 即 i i ( 国+ 必缈) 0 ( 1 一盯( 1 一f ) 口) 局 ( 3 2 2 ) 设m 是满足万”舀的最大的非负数，其中舀由式( 3 2 0 ) 给出，那么f h 幺的定义知 鼠万”， 2 1 第三章非精确非内点连续化算法及其收敛性分析 令 院：= 万” 那么有 l i 气( 国“1 ) 0 ( 1 一仃( 1 一f ) 皖) 陬 ( 1 - o ( 1 - t ) t , ) f l t k 因此， 心州= 仇a a = ( 1 一i 赢暇) 版己儿， 其中 c 2 1 。雨而t ) ( 1 矾 一 1 1 + ( 1 +一f ) 综合以上两种情况，有 段+ l 觐， ( 3 2 3 ) 其中 ：= m a x ( c l ，己) 事实上，e 与七独立。一方面，五与尼独立；另一方面，西与尼独立，所以鼠 与尼独立，则磊与尼独立。因此，式( 3 2 3 ) 对讹k 均成立。 下面讨论算法的局部二次收敛性。 引理3 6 ：设m 是b 矩阵，且假设3 1 成立。那么对足够大的k k ，有 胪( 口) i l 0 ，满足 0 ( + 1 ) l i 粥+ 2 厩微 那么，对足够大的k e k 2 , 当刁赫时，下式均成立 一 一 c 睡+ 2 、 n q r l l t ks , a r t a = p 玎c l p k 不失一般性地，对每个足够大的后k ：，令r h 车广，那么，由仇在s t e p 4 中的 选取方法可知，对足够大的k k ：，有 可以推出 n k + 1 广矿2 珊葡赢雠 歹；2 仉砖南段咧舢 那么，对所有足够大的k k ：，有 当k k 。时，有 从+ 。= r t 厥= d ( 露) 2 4 由式( 3 9 ) 知 第三章非精确非内点连续化算法及其收敛性分析 气( c o “1 ) = o ，皖= 1 反= 五以， 其中莓由式( 3 1 6 ) 给出。f hr h 的选取方法知， 仇厥0 ( 国“1 ) 0 0 ( 国“1 ) 一气( 国“1 ) 9 = 忙鹏( 国“1 ) 一胁( c o “1 ) 0 2 , f i n ( 1 7 2 玩评) 彳 m i n i e i 2 矽- s “| ) 因此，对足够大的k k ，有 版+ l = r h 反 1 2 石( 1 7 2 玩评) 露 m i n i e l 2 伊一s d ( 以2 ) 综合以上两种情况，可得对足够大的k k ，有段+ ，= d ( 露) 证毕。 第四章数值计算结果及分析 第四章数值计算结果及分析 本文选取了十个典型的线性互补问题进行数值计算，首先给出十个算例中具 体的矩阵m 和向量g 。 算例l ：问题规模为n ，矩阵m = 算例2 ：问题规模为4 ，矩阵m = 算例3 ：问题规模为3 ，矩阵m = 算例4 ：问题规模为3 ，矩阵m = 算例5 ：问题规模为3 ，矩阵m = 算例6 ：问题规模为5 ，矩阵m = 向量q = 1j 1 三i ，向且g i o 叫习 扣g = ； 叫习 ，向量q = 算例7 ：间题规模为1 2 8 ，矩阵矽= l o ，三 ，其中。表示6 4 6 4 维的零菇阵， 一、l，j r趣巧4 3 o ；o rll ，一 一、 = 一、，一 ，j；，j 1 l ，) 2 0 2 4 2 乏 0 o 4 2 2 o ，f。l 、， 1 2 3 一、， l o o 2 3 1 0 一 1 o o l 2 3 o 0 o 1 l 1 ，f。l、，j。、，j。l 2 o 一 1，i f o 。o o 哪 t _ _ ， q o 。 缈o o 0 0一 o 0 0 o )d)l 1 第四章数值计算结果及分析 肚 3 - l 封，g = g o g o ，g o 为6 4 6 4 维随机矩阵，向量g = 算例8 ：问题规模为2 。，矩阵m = 三 算例9 ：问题规模为4 ，矩阵m = l 言言3 r ，3 10 0 鼢 净郎日 罢竺卜g = 42j i 2j 算例1 0 ：问题规模为5 ，矩阵m = a a ，a 为5 x 3 维随机矩阵，向量9 为随机向 量。 使用m a t l a b 编程计算以上十个算例，选取参数万为0 1 ，y 为0 5 ，仃为0 5 ， t 为o 1 ，终止条件为s 1 o e 一6 统一选取初始点风= o 0 1 ，x o 为全一向量。分别将 c p u 时间，函数调用次数以及迭代次数，列示于下表3 1 中。 表3 1 c p u 时间( 单位为秒)函数调用次数迭代次数 算例1 2 2 3 2 8 0 0 e + o ol 4 53 算例2 1 4 0 0 0 0 0 e 0 014 8 4 算例3 9 3 0 0 0 0 0 e 0 0 27 77 算例4 4 7 0 0 0 0 0 e 0 0 25 04 算例5 4 7 0 0 0 0 0 e 一0 0 23 93 算例6 3 10 0 0 0 0 e 0 0 2 3 93 算例7 3 4 4 0 0 0 0 e 一0 017 3 8 算例8 1 0 9 0 1 6 0 e + 0 0 24 6 4 算例9 3 4 4 0 0 0 0 e 0 015 55 算例1 0 3 10 0 0 0 0 e 0 0 26 l5 上表所列计算结果显示本文提出的非精确非内点连续化算法对各种类型的 2 7 第四章数值计算结果及分析 问题都具有较好的计算效果。 令算例l 和算例3 的初始点而为