（运筹学与控制论专业论文）非线性互补问题的光滑方程组解法.pdf

内蒙古大学硕士学位论文 非线性互补问题的光滑方程组解法 摘要 本文研究非线性互补问题n c p ( f ) 的光滑方程组解法给出一个新的光滑 n c p 函数，研究其性质，并基此给出求解非线性互补问题的光滑方程组解法当 f 在z 一阶连续可微，f 7 在x + 强半光滑，在x 满足适当的正则性条件时，证 明了光滑牛顿法的局部收敛性及线性收敛速度借鉴c o b e r l i n 和s j w r i g h t 提出的加速牛顿法，证明了方法具有快速线性收敛速度相对非光滑方程组方法 和光滑化方程组解法，本文方法简单易行，便于应用，数值算例表明方法的有效 性。 关键词：非线性互补问题，牛顿法，线性收敛，快速线性收敛，加速牛顿法， 星状域( s t a r l i k ed o m a i n ) as m o o t hn e w t o nm e t h o df 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 a b s t r a c t i nt h i st h e s i s ，an e ws m o o t hn c p f u n c t i o ni sp r e s e n t e da n d i t sp r o p e r t i e si sd i s c u s s e d b a s e do nt h i s ，t h ec l a s s i c a ls m o o t hn e w t o nm e t h o di sa p p l i e dt os o l v i n gn c p ( f ) u n d e r t h ec o n d i t i o nt h a tf 7 ( z ) i ss t r o n gs e m i s m o o t ha n da tz + s a t i s f y i n gs u i t a b l er e g u l a r i t y c o n d i t i o n t h el o c a ll i n e a rc o n v e r g e n c eo ft h em e t h o di sp r o v e d u s i n gt h e r e s u l t so b t a i n e d b yc o b e r l i na n ds j w r i g h t ，t h el o c a l f a s tl i n e a rc o n v e r g e n c ei sa l s op r o v e d t h e n u m e r i c a le x a m p l e ss h o wt h a tt h em e t h o di se f f i c i e n t k e y w o r d s ：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 ，n e w t o nm e t h o d ，l i n e a rc o n v e r - g e n c e ，f a s tl i n e a rc o n v e r g e n c e ，a c c e l e r a t e dn e w t o nm e t h o d ，s t a r l i k ed o m a i n i i 原创性声明 本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究 成果。除本文已经注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得内蒙古大学及其他教育机构的学位或证书而使用过的材料。与我 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：4 逸茑 指导教师签名 日 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权 将学位论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁 盘，允许编入有关数据库进行检索，电可以采用影印、缩印或其他复制手段保存、 l ：编学位 论文。为保护学院和导师的知识产权，作昔在学期问取得的研究成果属于内蒙古大学作 ； 者今后使用涉及在学期间主要研究内容或研究成果，须征得内蒙古大学就读期间导师的同 意：若用于发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表 学位论文作者签名：i i 垒羔 日 指导教师签名：趣 期：毕 日 期：掣 内蒙古大学硕士学位论文 第一章引言 设f ：础_ 耻为非线性向量函数，非线性互补问题( n o n l i n e a rc o m p l e m e n t a r i t y p r o b l e m ) ，简记为n c p ( f ) ，是指：求向量z p ，使得 z 之0 ，y ( x ) 0 ，x r f ( z ) = 0 ( 1 1 ) 如果f ( z ) 是仿射函数，即f ( x ) = m x + q ，其中m 为n 竹矩阵，q 为佗维向量，则非 线性互补问题蜕化为线性互补问题( 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 ) ，记为l c p ( m ，口) 互补问题是运筹学与计算数学的一个交叉研究领域，它与非线性规划、极大极小、对 策论、不动点理论等分支有密切联系，在力学、工程、经济、交通等许多实际部门有广泛的 应用这使得互补问题成为数学规划的一个十分热门的研究课题经过四十多年的发展， 日渐完善、深入和扩大随着优化领域内各种理论不断出现，产生许多互补问题的新的数 值方法【1 0 1 近年来发展的方法主要包括以下几类：( 1 ) 非线性方程组法这类方法是将非线 性互补问题转化为一个与之等价的非线性方程组圣( z ) = 0 一般而言，圣( z ) 是非光滑的， 经典光滑牛顿法不适用于求解西( z ) = 0 研究者提出非光滑牛顿法和光滑化牛顿法前者 利用西在当前迭代点扩的广义j a c o b i 矩阵v 七a 圣( 扩) 进行迭代，如f 3 3 ，3 4 ，3 5 】；后者 构造西( z ) 的光滑逼近函数嚷一圣，e _ 0 + 利用睡。在z 知的j a c o b i 矩阵进行迭代，并 控制七一0 + 保证收敛性，如f 3 6 ，3 7 】( 2 ) 内点法该方法是求解线性互补问题的一类很 重要的算法，其思想来源于1 9 8 4 年k a r m a r k a r 提出的解线性规划的算法这类算法的优点 在于它具有多项式计算复杂性，适合于大规模问题的计算( 3 ) 投影迭代法投影法是求 解互补问题的一类基本而又重要的计算方法它源于g o l d s t e i n - l e v i t i n - p o l y a k 的求解凸 约束优化问题的梯度投影法，包括著名的外梯度法、逐点逼近法、矩阵分裂法等，x i u 和 z h a n g 3 2 给出了最新的综述报告( 4 ) 磨光方程组法这类算法把非光滑方程组用一个含 趋向于零的非负参数的光滑摄动方程组来逼近然后利用求解非线性方程组的经典牛顿法 求解磨光方程组法继承了内点法所采用的以磨光方程组来逼近非光滑方程组的思想但 通过选择与内点法不同的函数作为磨光函数，去掉了对内点法来说必不可少的非负约束 从而其初始点的选择及迭代点的控制非常方便 本文考虑n c p ( f ) 的光滑方程组解法将n c p ( f ) 等价转化为一个处处光滑的非线 性方程组中( z ) = 0 ，进而研究其光滑牛顿类解法因西的处处光滑性，此类方法易于工程 领域所接受，便于应用光滑方程组方法虽然算法中回避了非光滑性，但量在n c p ( f ) 之 解z 4 处的j a c o b i 矩阵是奇异的如何处理该奇异性使方法具备快速收敛性质，是本文研 究的核心问题在1 9 8 0 年前后，r e d d i e n 【2 4 1 ，d e c k e r 和k e l l yf 1 1 1 ，以及g r i e w a n kf 1 2 1 等 l 内蒙古大学硕士学位论文 研究了解上奇异的光滑非线性方程组解法若圣在任意x r ”连续可微，考虑方程组 圣( z ) = 0 ( 1 2 ) 称x + 则是方程组( 1 2 ) 的奇异解，若j a u c o b i 矩阵西7 ( z ) 奇异一般的，利用牛顿迭代 x 2 + 1 = z 奄一西( z 七) 一1 圣( z 奄)( 1 3 ) 逼近( 1 2 ) 的数值解是合理的 若j a c o b i 矩阵圣( z + ) 非奇异，则当初始点z o 在解z + 的一个充分小的球型邻域内 时，牛顿迭代序列收敛到x 4 另外，如果矩阵圣，( 矿) 满足一个已知的l i p s c h i t z 条件，那 么这个球型邻域的半径就是已知的【9 】此时，收敛速度是超线性收敛或二次收敛但是， 当圣( z + ) 奇异，则牛顿法的这些经典理论就不再适用这样，对于奇异或接近奇异的问 题，引出了许多牛顿法的枝生理论与分析奇异性一般会导致数值计算的困难，运用牛顿 法至多可以保证在奇异解处的线性收敛速度r e d d i e n 【2 4 】，d e c k e r 和k e l l y 1 1 】，以及 g r i e w a n k 1 2 等证明了在关于解z + 的一个特殊邻域内，牛顿法( 1 3 ) 产生的迭代序列线性 收敛n x 但他们都要求圣在z 。二次以上l i p s c h t i z 连续可微，并且在x 处满足一定的 正则条件。最近c 。o b e r l i n 和s j w r i g h t 2 2 将g r i e w a n kf 1 2 的光滑性条件弱化，只要求 垂7 在x 强半光滑，并在一定的正则条件下证明g r i e w a n k 的结论仍然成立 不难发现，奇异问题的牛顿法没有进行线搜索这是因为线搜索以后，无法保证所得 到的下一个迭代点仍在关于x + 的特殊邻域内但是，如果在某些迭代步加一个固定的步 长，同时又能保证所有迭代点落在这个邻域内，这样很可能加快收敛速度上个世纪八 十年代，就出现了几种加速方法，但都需要假设圣三次或三次以上可微c o b e r l i n 和 s j w i g h t 【2 2 】提出的加速方法只要求西7 ( z ) 在z + 强半光滑，当满足一定的正则性条件时， 得到快速线性收敛性质本文第三章构造了一个新的光滑n c p 一函数，利用这个n c p 一函 数将n c p ( f ) 等价转化为一个光滑非线性方程组鉴于c o b e r l i n 和s j w r i g h t 提出的 解上奇异问题的牛顿法求解n c p ( f ) ，同样证明算法具有局部收敛性及线性收敛性针对 我们的n c p 一函数的特殊性质，对牛顿步每隔一次迭代进行加速，证明了整个牛顿迭代序 列 z 詹 以3 ( 1 一百t ) 速度快速线性收敛到z + ，即 熙譬爿= 弘1 一争 并且当f 7 为p 矩阵时，正则性条件成立文中给出一些算例，表明该方法的数值有效性 本文由三章内容构成：第一章为引言第二章预备知识，给出本文所要用的主要概念、 符号、术语和基本结论第三章非线性互补问题的光滑方程组解法，给出一个新的光滑 n c p 一函数，分析其性质，证明算法的局部收敛性及其收敛速度，讨论牛顿加速后的收敛性 与快速线性收敛速度，最后进行数值实验。 2 内蒙古大学硕士学位论文 第二章预备知识 本章给出本文用到的主要概念、符号、术语和基本结论本文使用如下符号： 1 融表示扎维欧氏空间，r 表示实数域。 2 r 罩表示r ”的非负卦限，即r 华= z 时：x i 0 ，i = 1 ，2 ，他) 3 忙| i 表示向量z 的欧氏范数，即对zer ”，忙| | = 、z ；i i a | l 表示矩阵a 的谱 范数，即i i a i l = x a m a x ( a t a ) ，其中a m 觚( a 丁a ) 为a r a 的最大特征值 4 z r 表示向量z 的转置，且规定z 舻，x = ( x l ，z 2 ，z n ) 丁 5 d i a g a 1 ，a 2 ，o 。 表示对角线元素为a l ，a 2 ，的对角矩阵 6 记n ：= l ，2 ，仃) ； 7 对任意向量a r n ，记 a + = m a x 0 ，o ，a 一= r a i n 0 ，n ， 其中m i n ，m a x 按分量计算，即 a + = ( n j - ，o 手，o ：) ，a 一= ( o f ，a 2 一，n 二) ， 口产= m a x 0 ，a i ，凸f = m i n 0 ，a i ) ，i = 1 ，2 ，7 1 阵 定义2 1 设m 为n 死矩阵，称m 为 ( i ) p 一矩阵，如果m 的所有主子式皆为正实数； ( i i ) p o 矩阵，如果m 的所有主子式皆为非负数； ( i i i ) 正定矩阵，如果x t m x 0 ，对任意0 z r n 成立； ( i v ) 半正定矩阵，如果x t m x 0 ，对任意x 黔成立； ( v ) 一矩阵，如果线性互补问题l c p ( m 0 ) 只有零解 半正定矩阵必为局矩阵，正定矩阵必为p 一矩阵，p 矩阵既是岛一矩阵又是凰一矩 命题2 11 1 】设m 妒姗( 不必对称) ，则如下叙述等价 ( i ) m 为r 矩阵； ( i i ) 若d 为n 阶正对角矩阵( 每个对角元素都是非负实数) ，则m + d 为p 矩阵； ( i i i ) 对任意0 z r “，存在i n ，使得x i ( m z ) t 0 ； ( i v ) m 及其所有主子矩阵的所有实特征值非负； ( v ) 对任意正对角矩阵d ，矩阵m + d 非奇异； ( v i ) 对任意 0 ，m + ，为p 矩阵 3 内蒙古大学硕士学位论文 命题2 2f 1 】设m r 似”( 不必对称) ，则如下叙述等价 ( i ) a ，为p - 矩阵； ( i i ) 若d 为n 阶非负对角矩阵( 每个对角元素都是非负实数) ，则m + d 的所有主子 式不为零： ( i i i ) 对任意0 z ，存在i n ，使得戤( m z ) 0 ； ( i v ) m 及其所有主子矩阵的所有实特征值严格正； ( v ) 1 o ，v x r n , z 0 ； 命题2 3 【3 3 】设m r “舰，d 。= d i a g ( a l ，a 2 ，8 珏) ，d b = d i a g ( b l ，b 2 ，k ) ， ( i ) 若m 为r 矩阵，d a 和风为负定对角矩阵，则矩阵见+ 眈m 非奇异 ( i i ) 若m 为p - 矩阵，仇和风为半负定对角矩阵，且a ；+ 酵o ，v i n ，则矩阵 仇+ d 6 m 非奇异 定义2 2 设f ：r “_ r ”，称f 为 ( i ) p o 一函数，若对任意z ，y 彤，z y ，存在i n 使得( 祝一鼽) ( 只( z ) 一r ( 可) ) 0 且y i ； ( i i ) p - 函数，若对任意z ，y 郧，z y ，存在i n 使得( x i 一玑) ( r ( z ) 一r ( 可) ) o ； ( i i i ) 一致p - 函数，若存在常数卢 0 ，使得删紧( 而一犰) ( r ( z ) 一只( 秒) ) 圳z 一圳2 ， 对任意z ，y 时； ( i v ) 单调函数，若( z 一可) t 旷( z ) 一j f l ( 3 ，) 】0 对任意z ，y r “成立； ( v ) 严格单调函数，若( z y ) 丁旷( z ) 一f ( y ) 】 0 对任意z ，y r n 成立； ( v i ) 强单调函数，若存在常数t 0 ，使得( z 一可) t p ( z ) 一f ( 夕) 】口忙一训2 对任意 z ，y r n 成立 单调函数必为r 函数，严格单调函数必为p 函数，强单调函数必为一致p 函数 命题2 4 【4 】设f ：r ”_ r n ，为连续可微函数，那么f 为r 一函数当且仅当f 的 j a c o b i 矩阵在任意点处均为昂一矩阵；若f 为一致p - 函数，则f 的j a , c o b i 矩阵在任意 点处均为尸- 矩阵 定义2 3 设x r ”为非空子集，向量函数垂：x _ r n 在点z x 局部l i p s c h i t z 连续，即存在 0 ，l 0 ，使得 圣( z 1 ) 一圣( z 2 ) i l l l l x l 2 c 2 l | ，v x l ，x 2 b ( x ，e ) ， 其中b ( z ，e ) 表示z 的邻域b ( x ，g ) = y 胛：恬一z l i 0 和6 0 ，使得不等式 圣( z 1 ) 一圣( z 2 ) l l l l i x l 一x 2 l i ，v x l ，x 2 x ，1 1 3 ；1 一x 2 i i 6 总成立，则称圣为x 上的( 全局) l i p s c h i t z 函数 引理2 1 ( p 谂d e m a c h e r 定理) 设xcr 竹是一个开集，垂：x _ 舻在x 上是局部 l i p s c h i t z 连续的，则西在x 内几乎处处可微记d 垂为圣的可微点集 定义2 4 设向量函数圣：融_ 妒，称西在点z 沿方向d r 订方向可微，若极限 ， 币( z + t d ) 一币( z ) l l m 。1 。1 。1 。一 t ，o + t 存在，称该极限为圣在点z 沿方向d 的方向导数，记为垂( z ；d ) 若圣在x 沿任意d p 方向可微，则称西在x 方向可微 定义2 5 若圣在任意z r n 局部l i p s c h i t z 连续，矩阵集合 0 b 垂( z ) = l j m 圣7 0 蠡) l 圣在r 住可微) z “- - - 4 x 称为圣在x r n 处的b 次微分称b 一次微分的凸包为圣在x 的c l a r k 广义j a c o b i 矩 阵集，记为 a 圣( z ) = c o ( 0 b 垂( z ) ) ， 定义2 6 若圣在x 方向可微，且对任意de 舯，d _ 0 ，任意v a 圣( z + d ) 有 v d 一虫7 ( z ；d ) = o ( h d l l ) ， 则称圣在x 半光滑若量在z 半光滑且 v d 一圣7 ( z ；d ) = o ( i d l l 2 ) ， 则称圣在3 7 强半光滑 向量函数圣( z ) = ( 垂1 ( z ) ，西2 ( z ) ，圣。( z ) ) 丁在x r ”半光滑当且仅当所有分量函 数圣l ，圣2 ，在x 半光滑半光滑函数介于光滑函数类和l i p s c h i t z 函数类之间，所 有光滑函数、凸函数、分片光滑函数均是半光滑函数半光滑函数的和、差、积及复合运 算也是半光滑的 5 内蒙古大学硕士学位论文 5 嫩= ；( ( 曲) 2 + ( m i n o ，。) ) 2 + ( i i i i n o 如) ) 2 ) ； 西c z ，：= ( 三：二：兰三：) 。 内蒙古大学硕士学位论文 对任意o ，pcn ，记形口( z ) 为j a c o b i 矩阵f 7 ( z ) 的行i q ，列j p 所构成的子阵只 为行i 口，列j n 的口r e 子阵设z 是n c p ( f ) 的解，定义如下指标集： q ( z + ) = i n iz ： 0 ，r ( z ) = o ) ， p ( z ) = i n ix ；= 0 ，r ( z + ) = o ) ， 7 ( z + ) = n ix ：= 0 ，r ( z + ) o ) 定义2 8 设x + 是n c p ( f ) 的解，记1 3 = q ( z + ) ，p = p ( z ) ，y = ，y ( z + ) ， ( i ) 若p 0 ) = 0 ，则称矿为n c p ( f ) 的非退化解； ( i i ) 若对任意指标集qcac 口u ，民矗( z + ) 非奇异，则称x + 为n c p ( f ) 的b - i e 贝0 解； ( i i i ) 若磁。( z + ) 非奇异且蜀p ( z + ) 一昂。( z 咒。( z + ) 一1 只p ( z + ) 为p 一矩阵，则称z + 为 n c p ( f ) 的舜正则解 7 内蒙古大学硕士学位论文 第三章非线性互补问题的光滑方程组解法 3 1 一个光滑n c p 一函数及其性质 ( 口，6 ) = 、西f f 萨j l i f 巧= 严了1 一、百万阿一、币了阿+ 1 ，a ，b ) r 2 ( 3 1 ) 圣c z ，= ( ：二：兰三：) c 3 2 ， 的解若f 在z r “光滑，则( 勋，只( z ) ) 在z 光滑，从而向量函数中在z 也是光滑 的【3 3 】，计算西7 ( z ) 得 西：c z ，= ( ：万葛尹i j 喜爱害手拿暑专兰李犏一了瓦i 手南) e t + r ( z ) + ( x i + r ( z ) ) 一只( z ) + 、( 3 4 ) 1 碍( z ) 1 其中e = ( 0 ，0 ，1 ，0 ，o ) t ，i n 是戳中的讫个单位向量设矿p 是 n c p ( f ) 的解，则有 中：( z + ) = i o ( z + ) ， i ( z + ) ， ( 3 5 ) i 7 ( z + ) 这表明非线性方程组垂( z ) = 0 的解z + 是一个奇异解，臣g j a c o b i 矩阵垂7 ( z + ) 的零空间 k e r 圣7 ( z + ) = 秽r “i 西7 ( z 4 ) 移= 0 = 默 8 内蒙古大学硕士学位论文 根据命题2 5 ，若f 在z 郧光滑，且f 7 强半光滑，则圣7 在z r n 强半光滑，因 此圣7 在x 沿任意方向d 酞n 的方向导数存在通过直接计算，得 ( 虫) ：( z ；d ) 一 也+ r l i ( x ；d ) ( z ) 2 以r 2 i ( x ；d ) = = ：i-4- 一 “再虿盯再可再葛丽厢( ( z ) 2 + 1 ) 3 2 识而 一( x i + ( x i + 只( z ) ) 一) 墨堕墨! 兰! 曼! 兰! ：皇! 兰墨! 兰2 2 二( 堕墨( 兰2 ：皇2 、ie i ( z i + f ( z ) + ( x i + r ( z ) ) 一) 2 + 1 ) 3 2 其中 + ( 日( z ) t d + r l i ( x ；d )r 3 i ( z ；d )( 3 6 ) 币和了琢再可i 爵而旷f 万抓砥玎f 玎 一等琴誓岳善笔鱼1 羔羔一( 尻( z ) + ( 妃+ 只 ) ) 一) ) 3 2( e ( z ) + ) 2 十 q 、4 、机。、4 77 盟篙2 糍篇筹揣鞴坦1 ) 3 2 业) 脚，( 噬+ 砰( z ) + ( ( 兢+ r ( z ) ) 一) 2 +厂八4 7 + ( 丽杀罴蒜) c 眦d ，。正再曩疆再丽再琢两而r “p 严 驴牌黧卜燕薹 驴畦堇 r瓠cz；d，=强写：，+， 差三；三兰； 内蒙古大学硕士学位论文 在解z + 处，有 ( 圣馕( z + ；d ) = ( ：乡器( 碍( z + ) t d ) + ) _ ( z + ) ， i q ( z + ) ， 眩+ ( w ) + 训f ( 3 7 ) + ( ( 蜀( z ) 丁d ) 一+ ( 碍( z + ) 2 d + 盔) 一) 碍( z ) ，i 届( z ) ， ( 志一对) 一 i 刊叫 蹦驴 篡一薏妾陋8 ， 州，= 黟飘一剐 内蒙古大学硕士学位论文 则由f 7x + ) 的p 一性质，只u p ，。u 霹( z ) 非奇异，故线性方程组 砭u p ，。邶( z + ) d , ，u i s = 一e a u p 一只u 芦，1 ( z ) 出 关于d 。u 声有唯一解五u 口，于是 r u p ( 矿) d - - 只u 反。u p ( z ) 五u p + r 岘r ( z 4 ) 五= 一e 。叩， 僻= 一嚣攀叫， u i 仇 d ) 一 d ) 这表明( 面+ 忱( 面 0 ，7 0 ，使得对所有的z = x + + p h ，p r b ，有 j | 圣7 ( z ) 一p b ( h ) l l 7 矿， 其中”i i 表示矩阵的谱范数 伊c，=三in。1，|i雷一，。，|一， 霎暑 ) 若手多 ， 由于雪( ) 在h s 连续，所以口( ) 和o ( ) 是定义在单位球面s 上的连续函数 下面先给出几个有用的引理 函数 使得 ( 3 1 2 ) ( 3 1 3 ) ( 3 1 4 ) 引理3 21 12 】集合即是关于z + 的一个星状域当且仅当存在一个非负下半连续 a ：s _ r u 。o 。= z = z + + p hlh s ，0 p d ( ) ) 1 2 内蒙古大学硕士学位论文 引理3 3 1 2 1 设圣，在z 处强半光滑，则集合 7 已= z = x + + p hh s ，0 p 0 ，使得牛顿步从点x = z + + p k h 七宠迭代到点z 知+ 1 时，满足 i l z 知+ l 一互1 z i l 弘赛 ( 3 1 6 ) 证明利用向量函数的中值定理得到如下垂( z ) 的近似表达式 吣) = 蜘计( z p 叭z 4 + 喇d f ) t ，0 = ( o p ( t 雪( h ) + 。( 例d t ) 九 = ( 等+ o ( p 2 ) ) z ， 上式左乘式( 3 1 5 ) 得到 圣7 ( z ) 一1 巾( z ) = ( 9 1 蜃一1 ( ) + 盯一2 ( ) o ( j d 。) ) ( 罢+ o ( 矿) ) z( 3 1 7 ) = 去z + ( i l 雷一1 ( ) l i o ( p ) + l l l t ) ( h ) 1 1 0 - 2 ( ) d ( p ) + a - 2 ( 九) o ( 矿) ) z ， 因而 f z 奄+ 1 一三z 奄l l = f l z 七一西7 ( z ) 一1 m ( z 南) 一三z 七 i i 口i 1 ( ) o ( ( ，七) + l l 雪( ，产) l b 一2 ( ，。奄) o ( p 詹) + ( 7 - 2 ( 南) o ( p 1 ) 1 1 | i z 岛 肛笔， 仃蠢 这是根据盯1 ，以及d ( ) 的定义得到的- 1 3 内蒙古大学硕士学位论文 记 e ( z ) = 一( 1 l t 雪一1 ( h ) l i o ( p ) + 三i i 雪( ) j 1 0 - 2 ( ) o ( p ) 卜0 - - 2 ( ) d ( 矿) ) z ， ( 3 1 8 ) 则结合式( 3 1 7 ) ，牛顿步的形式变为 z 七+ 1 = z 七一圣7x 南) 一1 西( z 知) = 互1 z k + e ( z 七) ( 3 1 9 ) 从而根据引理3 4 , - j 知 i i e ( 矿) 1 1 肛毳， 且有 pk+l 1 i p 碡p k p k 2 ( 3 2 0 ) l 一 、7 以及 s i 仰卜r a 础i nh h 七。矿+ 1 怄2 唾 ( 3 2 1 ) 其中0 k 表示相邻两个迭代点x 七与z 南+ 1 的夹角 引理3 5 设函数f ：r “_ r n ，z + 是n c p ( f ) ( 1 1 ) 的一个解，若f 7 在z + 强半光滑， 则存在两个非负连续函数 西：s 一琏，声：s _ r 使得对任意d 3 n 0 1 ( 0 ) ，及任意初始点x 1 w d ，牛顿迭代以互1 的速度线性收敛到z 4 ， 即 熙譬并1 1 其中w d 是关于z 的星状域，定义如下 1 忱= z = z + + p hlc o s 一1 ( ，z t d ) 西( d ) ，0 p p ( d ) ， i y 日 我们定义m i n ( 9 1 = 7 r ，定义如下函数 妒( d ) 2 砉n i n ( c o s - 1 ( h t d ) h s o , 9 0 1 ( o ) 】，de s 易知妒( ) 有定义，是一个上界为；的非负连续函数，并且矽- 1 ( o ) = sf - ) n 0 1 ( o ) 考虑如下两个函数 子( d ) = m i n a ( h ) lh s ，c o s 一1 ( 丁d ) 砂( d ) ) ， 庐( d ) = m i n 于( ) ih s ，c o s 一1 ( 丁d ) 砂( d ) 1 4 堕茎直奎堂堡主堂篁鲨奎 - _ _ - _ - _ _ _ _ - _ _ _ _ - _ - _ _ - 一一一一 易知争( ) 与产( ) 存在，在s 上非负连续，而且& - x ( o ) = 声一1 ( o ) = 矽- 1 ( o ) 由于口( h ) 1 ， 从而有a ( d ) 1 ，d s 令 q ( d ) = 丢s i n 矽( d ) 去， d s 定义 咖柏= r a i n 尚，揣) ( 3 2 2 ) 根据定义知s i n 参( d ) s i n 砂( d ) ，并且西( d ) 三，从而每( d ) 妒( d ) 定义 删= ( 1 - f q ( d ) ) 0 2 ( d ) s i n 姗， ( 3 2 3 ) 可以看到s i n ；步( d ) 的定义保证p ( d ) 满足如下性质 p ( d ) f ( d ) f ( d ) r b ， v h s ，c o s 一1h t d 妒( d ) 并且西，卢都是s 上的非负连续函数，且有移一1 ( o ) = 卢一1 ( o ) = 砂一1 ( o ) = s n n 0 1 ( o ) ，从而 对于d s ，讹= 彩当且仅当i i o ( d ) = 0 取定d s x n 0 1 ( o ) ，我们利用归纳法证明对任意初始点z 1 讹，牛顿迭代( 1 3 ) 产生 的序列 z k ) 七2 1 保持如下性质 p 七 p = 声( 硪巩 妒= 矽( d ) ， ( 3 2 4 ) 其中巩是向量d 与胪的夹角由妒的有界性知盯七子= a ( 矗) ，这个结论在后面的证明 中将被频繁使用 首先根据w d 的定义知，x 1 v 满足式( 3 2 4 ) 假设对所有的i 惫，式( 3 2 4 ) 成立， 则由( 3 2 0 ) 得 p 万i + l 一互1l 略p 错s i n 砌) p 罐南( d ) 3 2 5 q 2 ， 即有 从而 塑2 丛p i 地2 ， 7 脚, o l ( 半咫众 1 5 6 2 3 ，i i 、 后 七 ， ， ， ， 1 l l | i i 2 0 内蒙古大学硕士学位论文 这是因为q 趸1 ，故字 1 根据( 3 2 1 ) 0 的定义，有 由于矽1 = c o s 一1 ( 矿 1 ) 够，故 利用( 3 2 1 ) 及( 3 2 6 ) ，我们得到 妻s i n 仇= 毒2 k 1 风 s i n 仇= 季风 t = 1 o t 2 耦 柄 4 “ = 2 s i n 矽( d ) 筹妻c 字广1 从而 s i n o k “s i n 移+ 2 s i n 谚= 3 s i n 移兰， i 扫= f - q = s i n t p 虿1 ，故有s i n o k + l s i n 妒，也即巩+ 1 c 宠，且 以j 1 的速度线性收敛到z 下面给出本文的收敛性定理 定理3 1 设函数f ：r n 一渺，z 是非线性互补问题( n c p ( f ) ) ( 1 1 ) 的一个解若f 7 在z 强半光滑，并且至少存在一个d r n ，使得矩阵( 3 9 ) 非奇异，则存在关于z + 的收 敛星状域 7 已= z = z + + p hlh s ，0 2 7 ， 伊 知汹 t p 一口 一 + 一巩 巩 n吼 詹沮 + 砂 n 5曼 + 一靠 n5暑 内蒙古大学硕士学位论文 有足义，且在s 上连续 对于任意z o = z + p o h o 冗，根据( 3 1 6 ) 和( 3 2 0 ) 有 l l z l 一互1 z 。l l 弘昙；，p ( 丢+ p 詈；) p 。 所以 s i n 嘶o ) - r a i ni i 肚材i i 扣1 一互1 z 。i i 筹胚s i n 姗o ) 醛1 a 2 + r 2 # p o 舡笔竽熹 芦 这表明z ，1 m 。，放根据引理3 5 即可得到结论 定理3 2 设函数f ：r n _ 黔，矿是非线性互补问题( n c p ( f ) ) ( 1 1 ) 的一个解若f 7 为p 矩阵，且f 7 在z 强半光滑，则存在关于z + 的收敛星状域 t i = z = z + + p hh s ，0 o 以 ( 1 一i ) 的速度快速线性收敛到z + 1 7 屯 吼b 妒竹 垭 一 一 = = 内蒙古大学硕士学位论文 证明首先定义如下函数 g ( d ) - 半s i n 蝴d 皤 ( 由定义立即得到q ( d ) 百1s i n e ( d ) ) 以及 咖姗- - - - r a i n 尚，揣) ， 上式定义的角也( d ) 满足0 也( d ) 詈，并且 咖尚觜g 州， 从而 每。( 回矽( d ) 定义 声。( d ) = ! 三二= _ ! 三 掣s i n 够。( d ) ，d s w d ，t = z = z + + p ih s ，c o s 一1 ( 7 d ) 厩( d ) ，0 p s t ( d ) 易知w d 。c 宠收敛星状域死定义如下： 7 乙= z = z + + p hlh s ，0 p r ( ) ) ， 其中 r 。( ) = m i n f ( ) ，揣，! 兰曼竺! l 二掣) 证明过程分三步进行， ( 一) 将式( 3 1 9 ) 代入式( 3 2 8 ) 0 0 ，计算迭代步的具体形式： 记 则 y k + e ( ， x k + l = ( 1 - 兰) 矿+ e ( 扩) ( 3 2 9 ) = 去( 1 - 砉) z 七+ ( 1 一妄) e ( z 詹) + e ( y k ) 邑( x ky k ) = ( 1 一言) e ( z 七) + e ( y 七) ， x k + l = 主( 1 一主) x k + 弓。( z 七，秽) ， ( 3 。3 0 ) 1 8 且根据式( 3 1 6 ) 有 内蒙古大学硕士学位论文 1 一扣e ( z 七) 忡z i i e ( 可七) | l 1 一糍协囊 3 - ， “垒丝2 u 其中扩= z + - t - 矿胪，巩= o ( v 詹) ，蛾= m i n c r k ，巩) 从而由上述可得 1 一弘1 一别阻警 ( 3 3 2 ) ( 二) 若z 1 w h 。，要证( 3 3 0 ) 产生的迭代序列以；( 1 一1 ) 的速度快速线性收敛到 z + 类似引理3 5 的证明，我们要利用归纳法证明：任意初始点z 1 m o 式( 3 3 0 ) 产生 的序列 矿) 岛1 保持如下性质 m 五，巩 妒， 七1 ( 3 3 3 ) 显然后= l 时，式( 3 3 3 ) 成立假设对所有的i 后，上式也成立，则由( 3 2 0 ) 知 q t ) a 2 s l n 妒t 即有 字 尝 t 1 - - q t ，i = i , 2 , - - - ( 3 3 4 ) 对于右边不等式，由于q t 吾1 ，故厩 肌，i 七，从而 两边同除m 得到 z 南+ 1 一丢( 1 一言) z 2 l f 札掣 2 磋 尝坠掣s i n 砒 ( 3 - 3 5 ) u ； 4 t p “ 壶( 1 - 扣一) 上咱q t 肌 ( 1 一互tj 虿q t m 1 9 ( z - 互t 气q t ( 3 3 6 ) 一 一 一 二p 胆酉 丝砖“r：， 卢旷仃 p一霹吼一 一 一 1 2 一成一成 一 一2 1 2 一 业m 内蒙古大学硕士学位论文 故 从而有 丢( 1 - 扣刊丛p k 互1 ( 1 一扣+ 吼) 缎+ ，( 三( 1 一主) ( 1 + 绫) ) 南p ， 声 这是因为j 1 ( 1 一；) ( 1 + q t ) j ( 1 + ) 1 同样令以表示相邻两个迭代点与z 七+ 1 的夹角，则 根据三角函数和差公式，及妒1 也可得 利用( 3 3 4 ) 和( 3 。3 5 ) 因而 再由( 3 3 7 ) 日- f f j 知 岛 s i n o k + 1 s i n e t + s i n 9 t i = 1 s i no i = m i n | j 膣+ 1 一h a r ” 2 ( 1 一t 2 ) p l ! 一( 1 一t 2 ) p i 4 t p p i ( 1 一2 ) m i n a x i + l - 去( 1 一互t ) 一2 、2 唾 k 咖仇若妻以 k 胚圭阻1 一扣怕) 卜。肪融一扣+ q t ) i l - l p - i = li = 1 。 4。 二币历石生丽 l + 子2 2 t # 2 ( 1 一t 2 一q t ) 子2 2 一q l t 2 一q t 1 + t 1 2 一q t 2 0 s l n 砂 ( 3 3 7 ) ( 3 3 8 ) ( 3 3 9 ) ( 3 4 0 ) 晚 站汹 + 一以 一 +一巩 一位 札吼i 4 1 内蒙古大学硕士学位论文 综合( 3 3 9 ) 和( 3 4 0 ) 我们得到 s i no k + 1 s i n 妒+ 4 t i t 彦2 1 一t 2 一q ( 1 一2 ) 讲2 t p1 + t 2 一q t 西n _ 1 5 + 盏志 盏 s i n t f ， 故有巩+ l 砂由上述分析易知p k _ 0 ，当k _ o 。，并且有 吼 1 一吼 im掣硒等=弘1k-oo k - o o p k一争 z “一z z二 ( 三) 证明亿是关于z + 的收敛星状域 设z o = z + + p o h o 7 已，贝0 由( 3 3 8 ) ，有 s t n 玩尚，嚣 ，4 肛0 - 2 ( o ) ( 1 一t 2 ) s i ne t ( o ) s 矿碉