（应用数学专业论文）非线性互补问题的非精确算法研究.pdf

摘要 摘要 互补问题自1 9 6 3 年首次提出后受到广大研究者的重视，成为数学规划研究中 较为活跃的分支，求解互补问题的算法的研究领域也取得了丰硕的成果本文研究 非线性互补问题的非精确解的算法；针对求解其线性子问题的精确解的困难，提出 求其非精确解的方法，从而减少计算量一方面，基于光滑n e w t o n 法的思想和半光 滑的理论，利用f i s c h e r b u r m e i s t e r 互补函数的光滑形式，将非线性互补问题转化 为光滑非线性方程组求解，从而得到非线性互补问题的光滑非精确n e w t o n 法，数据 结果表明算法的有效性另一方面，基于信赖域方法有较好的可靠性，在解决大型 非线性互补问题时更有效，利用f i s c h e r b u r m e i s t e r 函数的光滑逼近函数将非线性 互补问题转化为无约束优化问题求解：文中将信赖域方法和非单调w o l f e 线搜索相 结合，提出一种非单调非精确信赖域算法，在线性系统的子问题的求解中采用共轭 梯度法得试探步的非精确解：在试探步不被接受时，采用非单调w o lf e 线搜索得到 下一个迭代点，使得算法不需要重新求解信赖域的子问题在一般情况下，证明了 算法产生的点列包含在一个水平集中，在此水平集是紧集的条件下，算法产生的点 列至少有一个聚点是非线性互补问题的解：在算法求得的解是b d 一奇异解的条件 下，证明了算法产生的点列收敛到惟一点，且有全局和局部超线性收敛速度 关键词：非线性互补问题非精确解n e w t o n 法信赖域法收敛性 a b s t r a c t a b s t r a c t c o m p l e m e m t a r i t yp r o b l e mw a s f i r s tp r o p o s e di n19 6 3 s i n c et h e ni th a sb e e nt h e h o t s p o ti nt h er e s e a r c ho fm a t h e m a t i c a lp r o g r a m m i n gf i e l d a l s om a n ya l g o r i t h m sh a v e b e e np r o p o s e d t h et h e s i sm a i n l yd e a l s 、析t ht h es t u d i e so fi n e x a c ta l g o r i t h m sf o r n o n 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 s w ep r o p o s ea ni n e x a c ts o l u t i o n ，i no r d e rt os o l v e t h ed i f f i c u l to ft h ee x a c ts o l u t i o nf o ri t ss u b p r o b l e m o nt h eo n eh a n d ，t h et h e s i sb a s e s o nt h ei d e ao fq i ss m o o t h i n gn e w t o nm e t h o da n dt h et h e o r yo fs e i m s m o o t h ，w i t ht h e s m o o t ht y p eo ft h ef i s h e r - b u r m e i s t e rf u n c t i o n ，n c pi sc o n v e r t e di n t oas m o o t h i n g n o n l i n e a re q u a t i o n sa n ds m o o t h i n gi n e x a c tn e w t o nm e t h o di su s e dt os o l v et h e e q u a t i o n s ，n u m e r i c a lr e s u l t si n d i c a t et h a tt h ea l g o r i t h mi se f f e c t i v e t h eo t h e rh a n d ，t h e t r u s tr e g i o nm e t h o dh a ss t r o n gc o n v e r g e n c ea n dr e l i a b i l i t y , w i t ht h es m o o t ha p p r o a c h f u n c t i o no ft h ef i s h e r - b u r m e i s t e rf u n c t i o n n c pi sc o n v e r t e di n t oa nu n c o n s t r a i n e d o p t i m i z a t i o np r o b l e m ，w ep r o p o s ean o n m o n o t o n i ci n e x a c tt r u s tr e g i o na l g o r i t h mf o r u n c o n s t r a i n e do p t i m i z a t i o n w ee m p l o yb o t ht h en o n m o n o t o n i cw o l f el i n es e a r c h t e c h n i q u ea n dt r u s tr e g i o nm e t h o d ，t h ei n e x a c ts o l u t i o no fs u b p r o b l e mg e n e r a t et r a i ls t e p a te v e r yi t e r a t i o n ，n o n m o n o t o n i cw o l f el i n es e a r c hi su s e dt os o l v et h en e x ti t e r a t i o n w h e ni ti sn o ta c c e p t e d u n d e rg e n e r a l i z e dc o n d i t i o n s ，t h el e v e ls e ti n c l u d e sas e q u e n c e b ya l g o r i t h m ，a n da tl e a s t ，n c p ss o l u t i o ni si t sa na c c u m u l a t i o np o i n t ，t h eg l o b a la n d s u p e r l i n e a rc o n v e r g a n c eo ft h ea l g o r i t h ma r ep r o v e d k e y w o r d ：n o n l i n e a r m e t h o d c o m p l e m e n t a r i t yp r o b l e m i n e x a c ts o l u t i o nn e w t o n t r u s tr e g i o nm e t h o d c o n v e r g e n c e 西安电子科技大学 学位论文独创性( 创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特另t l d h 以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：羡 7 ( 秒 1 7 1j 胡： 枷j o 6 、7 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文和使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复印手段保存论文。同时本人保 证，毕业后结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大 学。( 保密的论文在解密后遵循此规定) 本人签名： 导师签名： r 孰 弘| o 、6 。- 1 同期 如p 第一章绪论 第一章绪论 本章简要回顾互补问题的发展过程和求解非线性互补问题的常见算法，并简 单介绍作者在该硕士论文中的主要工作 1 1 互补问题的引入 互补问题 1 1 就是寻找向量x r ”，使其满足以下关系： x 0 ，f ( x ) 0 ，x 7f ( x ) = 0 ( 1 1 ) 其中f ：r ”专r “是连续可微的 若f ( x ) = m x + q ，其中m r “，q r ”，则称其为线性互补问题，记为 l c p ( m ，q ) ：否则，称其为非线性互补问题，记为n c p ( f ) 互补问题的一个自然推广就是变分不等式问题【l ，2 l ，即寻找向量x q ，使其满 足以下关系： ( j ，一x ) 丁f ( x ) 0 ，v y q ( 1 2 ) 其中q r ”为一个非空闭凸集 互补问题和变分不等式问题是相伴而生的，已经出现在大量的书籍 1 , 2 , 1 1 - 1 4 1 和 文献 3 - i 0 1 当中l e m k e 和h o w s o n1 1 9 于1 9 6 3 年首先提出互补问题，用来计算 b i m a t r i xg a m e 中的n a s h 均衡点问题，其中是将其转化为一个线性互补问题，并且 发展了一种求解此类线性互补问题的简单而有效的方法次年，c o t t l e 在他的博士 论文【1 3 1 中提出求解它的数学规划算法，当时并不是用“互补问题 这一名称，该名 称是后来才出现的，由c o t t l e ，h a b e t l e r 和l e m k e 【1 4 1 共同完成，主要用来解决线性互 补问题1 9 6 8 年，c o t t l e 和d a n t z i gi n , 1 2 】给出了线性与二次规划问题及在线性互补问 题表述下的统一形式，从而促进了对互补问题的研究对于线性互补问题的研究， 贡献最大的应为l e m k e 和h o w s o n1 1 9 1 的独创性算法非线性互补问题( n c p ) 是 1 9 6 4 年c o t t l e 提出的，后来h a r t m a n 和s t a m p a c c h i a 将非线性互补问题( n c p ) 与变 分不等式问题( v i p ) 联系在一起非线性互补问题的早期研究主要是对于解的存在 性，对于算法的研究与应用却相对较少对于非线性互补问题的研究，l e m k e 和 h o w s o n 【1 9 1 的独创性算法引导了整个不动点算法体系的发展到2 0 世纪8 0 年代中 2 非线性互补问题的非精确算法研究 后期，互补问题在算法研究方面也取得了丰硕的成果：对于线性互补问题，主要的 算法有直接法( 如l e m k e 法，c o t t l e d e n t z i g 法) 和迭代法( 如m a n g s a r i a n 法) 等对 于非线性互补问题的研究，主要的算法有不动点法，内点法，同伦法，投影 法，n e w t o n 法 1 , 2 1 等，其算法的特征是：在迭代中需要求解线性互补子问题或者二次 子规划l e m k e 算法( 1 9 6 4 年) 是这个时期最著名的方法之一，主要有综述文献l 1 0 1 及 部分优秀专著 1 , 2 , 1 1 , 1 2 , 1 81 互补问题是一类重要的最优化问题，目前在许多领域都有着广泛的应用，如工 程物理，经济和交通平衡等领域：同时，它也出现在约束优化的最优性条件中因此， 对互补问题的研究具有重要的意义，目前已产生了很多求解的方法，也得到了很好 的全局和局部收敛性 1 2 非线性互补问题的几种常见算法 1 2 1 光滑方程法 用她w 幻胛法求解m a n g a s a r i a n 于1 9 7 6 年首先提出这种方程组2 9 1 f ，q , ( x l ，巧( x ) ) 1 g ( x ) = i i i = 0 ( 1 3 ) l 矽( 矗，f a x ) ) j 缈( 口，6 ) = 口( 1 口一6 i ) 一护( 口) 一秒( 6 ) ( 1 4 ) 鼻( z ) 是f ( x ) 的第i 个分量，江1 ，2 ，n o ( t ) ：r 专r 是一个严格递增的函数，满足 o ( o ) = 0 ，称妒( 口，b ) 为n c p 函数或势函数，随后，m a n g a s a r i a n 证明了两个重要结 定理1 1 1 2 9 1 假设汐( 口，6 ) 由( 1 4 ) 定义，则伊( 口，b ) = 0 a 0 ，b o ，a b = 0 ，进而 x r ”为n c p ( f ) 的解的充要条件为g ( x ) = 0 定理1 2 1 2 9 假设x r ”为n c p ( f ) 的解，f ( x ) 在x 连续可微，若下面条件成 ( a ) x + 是非退化的，即x + f ( x ) 0 ： ( b ) f ( x ) 在x + 的j a c o b i a n 矩阵v f ( x ) 非奇异： 第一章绪论 3 ( c ) o ( t ) 连续可微、严格递增，且当f 0 时，0 ( ，) 十0 ( o ) 0 ，则g ( x ) 在x 的 j a c o b i a n 矩阵v g ( x ) 非奇异的 显然，满足定理1 2 的函数秒( f ) 有很多，因此可以派生出许多光滑方程，并能 用n e w t o n 法求解同时，在满足定理1 2 条件的解x 附近，算法超线性收敛为了保 证大范围收敛性，w a g o n 建立了一个同伦算法1 4 2 1 ，即取目( f ) = t 3t 。s u b r a m a n i a n 提出 了一个带阻尼因子的g a u s s n e w t o n 法【4 0 1 ，即取秒( ，) = f i t i ，迭代格式为 x ”鲫= x + a t p ，p = ( 彳( x ) + 名( x ) ，) v y ( x ) ( 1 5 ) 其中口 0 为步长，由非精确a r m i j o索求得，且沙( x ) = 专l l a ( x ) 1 1 2 ，旯( x ) = 缈( x ) ， a ( x ) = v g ( x ) r v g ( x ) ，1 表示适当维数的单位矩阵随后，凡括和l u c i d i 用非单 调搜索技术改进( 1 4 ) ，得到更好的结果x i u 和s u b r a m a n i a n 【4 l 】证明了：在f ( x ) 连 续可微时，( 1 4 ) 是大范围收敛的：在定理1 2 的条件下，其点列局部超线性收敛基 于i 凹函数( 1 3 ) ，k a n z o w 2 s 1 考虑如下光滑方程组( 要求f 至少是只一函数) h ( x ，少) = y f ( x ) 缈( 而，m ) 妒( 吒，虬) = 0( 1 6 ) 给出了j a c o b i a n 矩阵v h ( x ，y ) 中n c p ( f ) 的非解点处逆矩阵存在的几个充分条件， 算法的大范围收敛性与水平集 三( ，广) = 眠y ) r 2 “ii i h ( x , y ) h h ( ，) i i ) ( 1 7 ) 的有界性有密切的联系随后，t s e n g 【4 5 1 则把( 1 6 ) 变成 日p ( x ，y ) = ( y - f ( x ) ) p 矽( 而，乃) 矽( 毛，) = 0 。p 0 ( 1 8 ) 进一 n p 0 的增长情况利用光滑函数的彪6 加相容性，c h e n ，q i 和s u n 【2 0 1 提出了光滑n e w t o n 法，也称为j a c o b i a n 光滑化方法，在每步迭代时求解 混合n e w t o n 方程，并建立了全局收敛性与局部超线性或二阶收敛性，缺点是收敛 性依赖于混合n e w t o n 方程系统的可解性，对一般非线性互补问题并不适用后来， k a n z o w 和p i e p e r 【2 6 j 通过引入梯度步， a x 七= 一v 沙( 矿) 4 非线性互补问题的非精确算法研究 提出了适用于一般非线性互补问题的j a c o b i a n 光滑化方法虽然种类方法有一定 的优越性，但也有缺点，即使一个线性互补问题，转化后的方程组往往是非线性的， 并且非线性程度比较高，这就使得理论和算法复杂化，而非光滑法恰恰弥补了这个 不足 1 2 2 非光滑方程法 非光滑方程法就是把非线性互补问题转化为一个与之等价的非光滑方程组， 然后利用广义n e w t o n 法求解 首先给出非光滑的几个概念： 定义5 f 称函数h ：r ”一r ”在点x r ”是曰一可微的，如果存在一个度为1 的 正的齐次函数b h ：r ”专r “”( 即对v v r ”， 0 ，有b h ( x ) t v = ，b h ( x ) 1 ，) ，使得 ”l l m v - - , o 塑产一o 1 忑一5 u y 此时，称b h ( x ) 为日在点x 的b 一导数：如果日在集合sgr ”的每一点均是召一可 微的，则称日在s 上口一可微 定义6 【i 】设h ：r ”岭r ”为局部l i p s c h i t z i a n 函数，易知日几乎处处可微，构 成g 的可微点集合像，称日在点x r ”半光滑的，如果极限 l i m v h 。 ( v h r ”) v e o h ( x + t h ) ， f 上0 存在，其中o h 表示函数日在c l a r k e 意义下的广义j a c o b i a n 矩阵，即 o h ( x ) = c o n v q r ”。”ij x ) 量p 日：x 争x ，h 。( x 七) q ) 一般为m ，z 阶矩阵集合 定义7 【1 i 称f ：r ”寸r 是一个l c l 函数，若它是连续可微的，且导数z i p 一连续： 若导数是半光滑的，则说f 是一个s c l 函数 对于非光滑方程组的产生，p a n g 3 3 1 利用下面的c 尸函数 矗p l ( a ，6 ) = m i n a ，b ) ( 1 9 ) 即取o ( t ) = - 0 5 t ，将n c p ( f ) 转化为如下非光滑方程组 f ，m i n x ，巧( x ) 1 h t ( x ) = l ； i = o ( 1 1 0 ) ( m i n x n ，e ( x ) ) 第一章绪论 并证明了若f 连续可微，则q ( x ) 是b 一可微的，由此建立了一个带非精确线搜索的 广义n e w t o n 方法 x n e w = x + a d ，日( x ) + b h ( x ) d = 0 ( 1 1 1 ) 证明了在某种正则条件下，大范围收敛性及局部超线性收敛性一般地，( 1 11 ) 中 的n e w t o n 方程都是非线性的，因而d 不易求出：p a n g1 3 4 1 提出一个n e s o p 法，仅 求解一个二次子规划就可得d ；m o n t e i r o 2 8 1 改造为仅求解一个线性方程组就可得 d ，但要求迭代点在正数范围内，w a n g 4 3 1 用降势内点法求解一类非负约束方程组 ( 实际上，变分与互补问题都是此类问题) ，然后求解( 1 1 0 ) h a rk e r 和x i a o1 1 5 1 用 另一种非光滑方程 吼( x ) = f ( m a x o ，x ) + m i n o ，x = 0 ( 1 1 2 ) 后来h a rk e r 1 6 , 1 7 1 将此思想推广到求解变分不等式问题1 9 9 2 年，f i s c h e r 引入一种 结构简单而又奇特的n c p 函数( 又称f i s c h e r b u r m e i s t e r 函数) 仍( 口，6 ) = a 2 + 6 2 一口一b ( 1 1 3 ) 记生成的方程为见( x ) = o ，f a c c h i n e i 和s o a r e s 4 6 1 证明了马( x ) 是半光滑的，但其 自然势函数圳马( x ) 1 1 2 = 绣( x ) 是连续可微的，当f 是昂一函数时，j a c o b i a n 矩阵 v 皿( x ) 在任何点均是非奇异的这样，建立的n e w t o n 法可以取任意初始点，然而不 能处理单调的c 尸，原因在于不能保证水平集有界，l u o 和t s e n g 4 4 1 变更了f b 函 数，c h e n c h e n k a n z o w 给出的n c p 函数为 既( 口，b ) = 兄西p 3 ( a ，6 ) + ( 1 - t ) a + b + ，允( o ，1 ) ( 1 1 4 ) 其中口+ = m a x o ，a q i 3 8 1 对此类函数作了进一步总结与研究k u m m e r 2 4 1 ，o i 、 s u n1 3 7 1 提出了一类求解非光滑方程组的非光滑n e w t o n 法：每一步迭代求解一个广 义n e w t o n 方程 圪d = 一( x ) ( 1 1 5 ) 其中圪刮t j ( x ) q i 给出了两个解非光滑方程组的信赖域算法，k a n z o w 和 z u p k e 2 7 1 利用卯函数 仍( 口，6 ) = ( 口+ 6 ) 2 + a a b - a - b 将非线性互补问题n c p ( f ) 转化为非光滑方程组以( x ) = 0 ，试探步d 。是信赖域的 6 非线性互补问题的1 f 精确算法研究 子问题的非精确解，该方法适应于一般n c p ( f ) 的非精确信赖域方法，同时具有全 局收敛性和局部超线性或二次收敛性随后，非精确信赖域方法还得到许多发展， 还有大量的成果出现 1 2 3 投影法 投影法是求解互补问题的一类基本而重要的计算方法，就是基于 g o l d s t e i n l e v i t i n p o l y a k1 2 1 , 2 2 1 求解凸规划的梯度投影法思想求解互补问题，所以 又称为g l p 投影法求解互补问题的基本迭代格式为 x n e w = b - e t f ( x ) + ( 1 1 6 ) 其中g t , 0 为步长( 后来对于该方法的下降方向，何炳生教授又找到多个) 可是其 收敛性需要假设f 是强单调和l i p s c h i t z 连续的k o r p e l e v i c h 【刎在1 9 7 6 年提出了外 梯度法( 即把两个相邻迭代合并成一次迭代) ，即 x n 8 * v = 【x - - o t f ( x - c t f ( x ) + ) 】+ ( 1 1 7 ) 它的收敛性只要求f ( x ) 单调且解集x a s u nf 4 7 】应用a r m i j o 搜索技术得到，在 f ( x ) 是伪单调且x + o 的假设下，迭代点列收敛到x 外梯度法是梯度投影法在 互补问题中的推广，最多只有线性收敛速度，然而其运算量小，存储量小，保稀疏 性s o l o d o v 和t s e n g 5 2 1 给出了一个g l p 投影法的一般迭代格式 x k + l = x k r p t o ( x k ) - - r o ( x k a f ( x k ) + ) ( 1 1 8 ) 其中， 0 为步长，死= ，一口f ( 当f ( x ) = m x + q 时，疋= ，+ 口肘r ) ，口 0 使得乞为 强单调，p 选取正定矩阵后来，何炳生建立了一类特殊类型的投影法，即投影收缩 法，并作了大量的工作 4 8 , 4 9 , 5 0 1 此方法的每次迭代都由两步完成，第一步为预测步， 用来提供一个预测值，第二步为校正步，用来产生新的迭代点随后，何炳生【5 1 】揭示 了已有的投影收缩法中的下降方向，都是基于三个基本不等式的不同组 合w a n g x i u w a n g 嘟1 ，n o o r w a n g x i u 3 1 1 等也给出了其他一些下降方向，详 细内容可见相关综述文献随着进一步的研究，x u w a n g z h a n g 【6 7 1 给出了更 多好的性质凡括1 3 5 1 ，l s u e m1 6 3 1 ，m a r c o t t e1 3 0 和z h u1 6 8 , 6 9 , 7 0 1 也做了大量的工作， 在不同的条件下，推广了何炳生的投影收缩法，并在相当弱的条件下证明了算法有 大范围线性收敛性 第一章绪论 7 1 2 4 非精确解法 非精确解法就是对于非线性互补问题，求解精确解的过程难度较大，可以采用 求其近似解或非精确解此类方法在求解非线性互补问题中比较不多见，同时在求 解其他类型的最优化问题中也应用不多，但该方法能简化计算，减少计算量非精 确n e w t o n 法首先由d e m b o ，e i s e n t a t ，s t e i h a u gm 1 于1 9 8 2 年提出，该算法是在经典 n e w t o n 法求解非线性方程组f ( x ) = 0 时，其中 稚+ l = 吒+ 瓴，f ( ) 瓴= - f ( x k ) ，x o 给定 可以由非精确n e w t o n 法来求其近似解 x k + 。= x k + 酞，f ( 吒) 瓴= - f ( x k ) + r k ，l i r k l l l l f ( x k ) l l ，给定 其中 讯) 为不大于1 的均匀序列，收敛速度与残余量 l l 训i i f ( 稚) i i ) 有关，并证明了 该算法有局部收敛性该方法随着问题规模的增大，其优点越来越明显p a n g1 7 3 1 在 每次迭代中用近似矩阵来代替其j a c o b i a n 矩阵，从而减少运算量，对于线性子问题， 可以求其一个非精确解作为下一个子问题的解e i s e n s t a t t 5 5 j 给出了非精确n e w t o n 法的全局收敛性，o i 6 4 1 给出了局部l i p s c h i t z 函数的两个非精确n e w t o n 法，并证明 了解在半光滑和b d - 奇异的假设下的局部线性与超线性收敛性以及全局收敛 性：l i u f 5 6 1 给出了非精确n e w t o n 法的半局部收敛性随着问题的进一步深 入，k a l a s h n y k o v a1 7 4 给出了非精确n e w t o n 法的内部的精确度控制技术，用来减少 计算量1 9 9 7 年，k a n z o w1 6 0 1 还给出了一个非精确驴一b a s e d 法来求解非线性互 补问题的二阶子问题的非精确解，其中采用了线搜索后来，k a n z o w 和z u p k e 【2 7 l 利 用n c p 函数 0 2 ( a ，6 ) = ( 口+ 6 ) 2 + 2 a b - a - b 将非线性互补问题n c p ( f ) 转化为非光滑方程组以( x ) = 0 ，试探步d 。是信赖域的 子问题 m i n g 丑( x 七) + v q ( 矿) r d + l ，、d r 吆圪d ( 1 1 9 ) 二 s j i l d l l - r ”为连续可微函数，假设n c p ( f ) 的解集非空 非线性互补问题n c p ( f ) 在许多领域有重要的作用 6 2 , 7 1 , 7 2 1 ，近年来已有许多求 解n c p ( f ) 的方法 3 8 , 7 2 1 ，目前最活跃的方法为用光滑n e w t o n 法来解 n c p ( f ) 5 7 , 5 8 , 7 4 , 7 5 光滑n e w t o n 法是用光滑函数和光滑参数来解决n c p ( f ) 中 n e w t o n 法每次迭代含光滑参数的方程当光滑参数递减到零时，就找到原问题的解 在解决大型问题时，每次迭代都由线性系统的解来代替，这就增加了大量的计算量 而非精确n e w t o n1 3 , 4 , 6 1 方法可以解决这个难题，主要用来近似地解决线性系统，近似 解的精确度由参数来控制非精确n e w t o n 法已经被用来求解n c p ( f ) 7 6 , 7 7 】下面在 光滑n e w t o n 法的框架下提出一个光滑非精确n e w t o n 法，用来求解非线性互补问题 朋凹( f ) 将r u i 6 5 1 中函数h ( z ) 定义的第一个分量线性函数，推广到非线性函数 一1 ，数据结果表明此法是可行的，计算速度明显加快同时，将光滑参数当作一 个独立变量，非精确n e w t o n 法的强迫参数将当前迭代中残余向量的范数和映射范 数联系起来在较弱互补假设条件下，证明了该算法的收敛性 2 2 预备知识 光滑非精确n e w t o n 法是基于f i s c h e r b u r m e i s t e r 函数的光滑逼近函数 ：r 3 专r ： ( ，口，6 ) = a + b 一叫_ = _ 而 ( 2 2 ) 二l 一 1 卜线性互补问题的非精确算法研究 一二二= 二二二二一= = - 一一 将非线性互补问题转化为非线性方程组求解显然兄踞砘，一跏p 括研函数有许多 引理2 1 3 1 若 0 ，则( ，a ，b ) 是可微的 引理2 2 5 7 1 对于任意( ，a ，6 ) 皿+ r 2 ，有 l i m 矽o , ，a ，b ) = ( 口，b )( 2 3 ) 引理2 3 1 3 对于任意朋，飓耋r + ，有 i 矽( “，a ，6 ) 一矽( 鸬，口，6 ) i 0 ，日在( ，戈) 点连续可微，其砌6 泐矩阵为 日c z ) = ( w ：， c 2 6 ， 其中 1 ，( z ) = v e c c k u ( , t t ，薯，e ( 砌：f m 以z ) = q ( z ) + d 2 ( z ) f 。( 功 第二章光滑非精确n e w t o n 法 球z ) = 蚓卜再南艇) d 2 ( z 刚一丽黑丽涎) ( i i ) 若，是忍一函数，则对于任意 0 ，h ( 2 ，功是非奇异的 引理2 6 1 8 1 假设q o ：r ”专r ”为局部l i p s c h i t z i a n 函数，在x 处是半光滑的，则 ( a ) 对于任意y a 妒o + 办) ，hj o ，有砌一矽。( x ；矗) = o ( 1 l h l l ) ： ( b ) 对于任意办专o ，有妒 + 厅) 一矽( x ) 一缈( x ；办) - - - o ( 1 l h l 引理2 7 令( ，x ) 和h ( z ) 由( 2 5 ) 和( 2 4 ) 定义，则o ( 2 ，x ) 和h ( z ) 在r xr ” 上半光滑 证明 对所有i n ，( ，x ) 由可微函数( 一，巧( x ) ) 7 ：r ”专r 和凸函数 ：r 3 专r 合成，而可微函数和凸函数都是半光滑函数，半光滑函数的复合函数也 是半光滑函数从而，o ( 2 ，x ) 和h ( z ) 都是半光滑的 2 3 光滑非精确n e w t o n 算法 下面给出基于光滑f i s c h e r b u r m e 括w r 函数( 2 2 ) 得到n c p 函数的光滑非精 确n e w t o n 法 4 z = ( 2 ，x ) er + r ”，、 ，( z ) - - i i t ( z ) 1 1 2 = ( 一1 ) 2 + ( z ) ，初始点z 。= ( ，x 。) ， 使得。 o ，y ( o ，1 ) ，形2 0 p ( z ) = y m i n 1 ，甲( z ) ) 以上参数的选取，有以下的简单性质： 性质l ( i ) 对于所有 0 ，且甲( z ) 甲( z o ) 的z = ( ，x ) 都有 y e l ( i i ) 对于任意x r ”，有 ( 2 0 , z ) q 算法2 1 选择参数万( o ，1 ) ，盯( o ，1 ) ，令( ，x o ) 足+ xr ”为任意点，z o = ( 2 0 , x o ) ， 1 2 非线性互补问题的非精确算法研究 y ( o ，1 ) ，使彬。 丢，选择序列 仇) 使仇 o ，7 7 】，刁 o ，1 2 彬。】为常量，七：= o s t e p l 若甲( z ) = 0 ，停止 s t e p 2 计算位= ( ，a x ) ，已知 ) + 匕 其中风= 户( z ) = y m i n 1 ，w ( z ) ， w 龇辫心p k 亿7 ， 使0 r k l l - ( 1 一口) + 印( z ) o r + 当耳+ ，h ( z ) 是连续可微的，则显然有i l 足 ) j j = d ) 当甲( z ) 1 时， p ( z ) = 7 y 孓西= 圳甲( z ) f i 当甲( z ) 1 时，p ( z ) = ( z ) y 孓西= 州甲( z ) 0 ， 因此有 p ( z ) - r l l n ( z ) i l ( 2 1 2 ) 由( 2 1 1 ) 和( 2 1 2 ) ，对于所有口【o ，1 】，刁e o ，1 一y z 。】，z n ( 三) 有 i i m z + 础) 0 = 忙( 口) + h ( z ) + a l l 。o ) a z i l = 0 疋( 口) + ( 1 一口) 日o ) + 口o p ( z ) 。，) 0 - i i r ：( 口) 0 + ( 1 一口) 8 日( z ) 0 + 口 p p ( z ) o + 0 ，0 ) - l i r ：( 口) 0 + ( 1 一口) 0 日( z ) 0 + 2 俐。i i h ( z ) l l + 叼i i h ( z ) l i 收敛到 z ) ，由算法2 1 可知，序列 甲( ) ) 是单调 递减的由甲( z ) 的连续性，有 w ( z 七) ) 专、壬，( 矿) 0 若甲( 扩) = 0 ，则定理结论自然 成立 若甲0 木) 0 时，我们用反证法，假设甲0 木) 0 ，而少q ，即 。尸( z 。) j u o = e u y m i n 1 ，a - ( z 2 ) ) o 0 有t r + ，则h ( z + ) 存在并可逆因此由引理2 8 可知存在z + 的邻域n ( z + ) ，正数 口( o ，1 】，使对于任意z = ( ，x ) n ( z ) ，口 0 ，口】，都有墨+ ，h ( z ) 是可逆的，从 而( 2 1 0 ) 成立所以，对于非负整数，使得万7 ( 0 ，口】，以及对所有z 七n ( z ) w ( z 七+ 万7 止七) 【l 一盯( 1 2 y t o r h ) a 】甲( z 七) 对所有z 后n ( z + ) ，由算法2 1 ，则对于足够大的k ， 甲( z 。+ 1 ) 【l 一仃( 1 2 y p o 一7 7 ) 艿】甲( z ) 【l a ( 1 2 y p o 一，7 ) 艿7 】甲( z ) ( 2 1 4 ) 对( 2 1 4 ) 两边取极限k 一0 0 ，有 甲( z ) i 1 一o - 0 2 y , u o 一刁) 万。】甲( z + ) 第二章光滑非精确n e w t o n 法 从而有甲( 矿) 0 矛盾所以无穷序列 z 的每一个聚点z 都是 h ( z ) = 0 的解 2 4 2 局部收敛性分析 f 向我们来证明算法2 1 的局部收敛性： 定理2 3 假设对所有z = ，x ) 足+ x r ”，日0 ) 是非奇异的，z = ( ，x + ) 为 算法2 1 产生的无穷迭代序列 z ) 的聚点，若h 在z 是半光滑的，任意v a h ( z ) 是非奇异的，仇专o ，则序列 z 超线性收敛到 z ，即忖“一z i i = o ( t l z - - z * 1 1 ) ，并 且“1 = o ( 1 。) 证明由定理2 2 可得z 为日( z ) = 0 的解，又任意v 8 h ( z 。) 是非奇异的，从而 有任意z 专z ，l h ( z k ) 。1 忙c ，其中c o 为常数 因此，由引理2 6 和2 7 有日( z ) 在z 是半光滑的，矿专z ，从而得出 畛+ 止一elli i z + 日( z k ) 。1 【一日( z ) + ( e * p ( z k ) 。，) 卜z 。0 - 1 1 - ( z 。) 一i i l l t ( z ) ( z - z ) - h ( z k ) + ( e p ( z 。) 。，) 0 c 归( z k ) ( z - z * ) - h ( z * ) ( p p p ( z ) 0r 。) l l l = c 归( z ) 一日(