（计算数学专业论文）求解非线性互补问题的光滑化方法.pdf

硕士学位论文 摘要 本文研究非线性互补问题的数值解法非线性互补问题在经济、工程中有许多 重要应用，已产生了很多求解方法，也得到了全局收敛性和局部超线性结果近年 来多采用n c p 函数把非线性互补问题转化为非光滑方程组来求解 本文的光滑化信赖域方法推广了y a n g 和q i 的方法，它适合于一般的非线性 互补问题 信赖域方法有较好的可靠性与强适定性，在解决问题时更有效光滑化方法是 解非光滑问题的一类重要方法，有自身的优点本文采用f i s c h e r b u r m e i s t e r 函数把 非线性互补问题转化为非光滑非线性方程组，用k a n z o w 光滑逼近函数逼近 f i s c h e r b u r m e i s t e r 函数，得到相应的光滑方程组；把信赖域方法和线性搜索相结 合，提出了光滑化信赖域方法算法中我们给出了一个特定条件，条件满足时，采 用信赖域步，条件不满足时，采用梯度步我们证明了算法产生的点列包含在一个 水平集中，在此水平集是紧集的条件下，算法产生的点列至少有一个聚点是非线 性互补问题的解在算法求得的解是r 一正则解的条件下，证明了算法产生的点列收 敛到唯一点，且有局部超线性- - 阶收敛速度本文最后对几个具体问题进行了数 值试验，结果表明算法是有效的 关键词：非线性互补问题；信赖域方法；线性搜索；全局收敛性；局部超线性- - 阶 收敛性 求解非线性互补问题的光滑化方法 a b s t r a c t w e s t u d yt h en u m e r i c a lm e t h o d sf o rt h en 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 t h e n o n l i n e a r c o m p l e m e n t a r i t yp r o b l e m h a sm a n y i m p o r t a n ta p p l i c a t i o n si ne c o n o m i c sa n d e n g i n e e r i n g ，a n dt h e r eh a v ed e v e l o p e dm a n y n u m e r i c a lm e t h o d st os o l v ei ta n dg l o b a l a n dl o c a lc o n v e r g e n c er e s u l t sh a v ea l s ob e e no b t a i n e d i nt h el a s ty e a r sm o r ea t t e n t i o n h a sb e e nd e v o t e dt or e f o r m u l a t i n gt h en 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 ma sas y s t e m o fn o n s m o o t h e q u a t i o n sb yu s i n gs o m e n c pf u n c t i o n t h e s m o o t h i n g t r u s tr e g i o nm e t h o dp r o p o s e di nt h i sp a p e ri sa ne x p a n s i o no fy a n g a n dq i sm e t h o d ，i ti sw e l l d e f i n e df o ra na r b i t r a r yc o m p l e m e n t a r i t yp r o b l e m c o m p a r e dw i t hl i n es e a r c h ，t r u s tr e g i o nm e t h o d s a r em o r er e l i a b l ea n dr o b u s t ，a n d m o r ev a l i di nr e s o l v i n gp r o b l e m s a sac l a s so fi m p o r t a n tm e t h o d sf o rt h es o l u t i o no f n o n s m o o t hp r o b l e m s ，s m o o t h i n gm e t h o d sh a v es o m ef a v o r a b l e a d v a n t a g e s i n t h i s p a p e r b yu s i n g f i s c h e r b u r m e i s t e rf u n c t i o n ，w er e f o r m u l a t e t h en o n l i n e a r c o m p l e m e n t a r i t yp r o b l e ma sas y s t e mo fn o n s m o o t hn o n l i n e a re q u a t i o n sa n dw eu s e k a n z o w ss m o o t h a p p r o x i m a t i o n f u n c t i o nf o rt h ef i s c h e r b u r m e i s t e r f u n c t i o n b y c o m b i n i n gt r u s tr e g i o nm e t h o dw i t h l i n es e a r c h s t r a t e g y , as m o o t h i n gt r u s tr e g i o n m e t h o di sp r o p o s e d as p e c i f i cc o n d i t i o ni sp r o p o s e di no u ra l g o r i t h m ：i ft h i sc o n d i t i o n i ss a t i s f i e d ，w ew i l lu s et h et r u s tr e g i o ns t e p ；o t h e r w i s e ，w ew i l lu s et h eg r a d i e n ts t e p w ep r o v et h a tt h es e q u e n c eg e n e r a t e db yo u ra l g o r i t h mr e m a i n si nal e v e ls e t ，a n d u n d e rt h ec o n d i t i o nt h a tt h el e v e ls e ti sc o m p a c t t h e r ee x i s t sa tl e a s to n ea c c u m u l a t i o n p o i n t o ft h e s e q u e n c eg e n e r a t e db y t h e a l g o r i t h m i sas o l u t i o no ft h en o n l i n e a r c o m p l e m e n t a r i t yp r o b l e m i ft h es o l u t i o ni sr r e g u l a r ，t h ew h o l es e q u e n c eg e n e r a t e d b y o u r a l g o r i t h mc o n v e r g e s t oa n u n i q u ep o i n t a n dt h e c o n v e r g e n c e r a t ei s q - s u p e r l i n e a r q q u a d r a t i c n u m e r i c a l r e s u l t si n d i c a t et h a to u r a l g o r i t h m i s q u i t e p r o m i s i n g k e yw 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 ；t r u s tr e g i o n m e t h o d ；l i n e s e a r c h ；g l o b a lc o n v e r g e n c e ；l o c a ls u p l l n e a r q u a d r a t i cc o n v e r g e n c e i i 湖南大拳 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 商勿绣b 日期：印刃年，月训日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密囱。 ( 请在以上相应方框内打“4 ”) 作者签名：断。勿龙日期：磁，月啪日 导师签名：爿蜀冷侈 日期：矿锌j ，月矿。日 硕士学位论文 1 1 非线性互补问题 第1 章引言 令f ：r “一只“连续可微非线性互补问题就是求x e r “使之满足 而2 0 ，e 0 ) 0 且x i e o ) 一0 v i ，净 1 ， ( 1 1 ) 我们将上述问题记为n c p ( f ) ，它在许多方面有着重要应用，如工程中的电路联结 问题、流体力学问题、最优控制问题、经济学中的一般均衡问题、博弈论模型、 能源模拟系统以及运筹学中的相关问题等，详细情况参见 1 ，2 等文献互补问题 与工程和经济学中的问题相互渗透是因为互补的概念和系统平衡的概念具有相同 的含义在一定的条件下这些问题都可以转化为非线性互补问题如交换经济学 ( e x c h a n g ee c o n o m i c s ) 竞争平衡( c o m p e t i t i v ee q u i l i b r i u m ) 理论中经典的w a l r a s i a n 法则( t h ec l a s s i c a l w a l r a s i a n l a w ) 可以改写为价格和边际需求两个变量之间的非线 性互补问题交通理论用户平衡中著名的w a r d r o p 原理自然而然就是非线性互补问 题 有许多求解- v c p ( f ) 的方法，参见 3 近年来t 利用n c p 函数把n c p ) 转 化为非线性方程组的方法备受青睐如果函数妒：r 2 一尺满足条件 妒( d ，6 ) 一0 a 苫o ，b 之0 ，a b - 0 ， ( 1 2 ) 则称e p 是一个n c p 函数本文运用f i s c h e r - b u r m e i s t e r 函数妒：r 2 一只 妒( 口，b ) 一口2 + b 2 一日- b ( 1 3 ) 将u c p ( f ) 转化为非线性方程组 中 ) 一0 这里中：r “一只”被定义为 f 妒0 。，巧o ) ) 1 郇卜k 一。 q 4 i 妒阮，e 0 ) ) j 相应的效益函数为 o ) 。去m o ) 中0 ) 由n c p 函数的定义可知： x 是n c p ( f ) 的解尊x + 是中 ) a 0 的解 求解非线性互补问题的光滑化方法 因此，我们只需求解非线性方程组中 ) = 0 或无约束优化问题m 。i n 。掣o ) 即可- 一般来说，为得到算法的全局收敛性有两种方法，即线性搜索方法和信赖域方 法 1 2 信赖域方法 信赖域方法的思想可追溯到l e v e n b e r g ( 1 9 4 4 ) 和m a r q u a r d t ( 1 9 6 3 ) 求解非线性 最小二乘问题的方法，它是一种较新的方法信赖域方法的基本思想是要求试探步 d 。在信赖域之内，即在每一步迭代时有一正数。，使试探步d 。满足 恢忙。 如果我们已经得到了优化问题的当前近似解，我们可以在该点附近构造一个逼近 模型，即信赖域子问题，把信赖域子问题的解作为试探步进行下一次迭代，每次 迭代后调整信赖域半径如果计算表明近似模型符合原问题，信赖域半径增大，反 之减少信赖域方法的试探步d 。在某种意义下使得+ 以是在以坼为中心的广义 球上最好的点 众所周知无约束光滑优化问题 r a i n f ( x ) 在迭代点附近信赖域子问题可取为 m 删i n 吼( d ) 净g k r d + 矽b i d 舭t s ( 1 5 ) 其中g 。- v ( x 。) ，b 。是v 2 ，0 。) 的某种近似 若d 。是上述子问题的解，则 p r e d - 吼( 0 一妒i ( d i ) ( 1 6 ) 是目标函数的预估下降量因为有钆q ) 一f ( x 。+ d ) ，目标函数的真实下降量为 a r e d tf ( x i ) 一f ( x t + d t ) ( 1 7 ) 真实下降量与预估下降量的比值 。a r e d k( 1 8 ) 5 p r e d 对扎+ 。的选取以及a k + 1 的产生起关键作用 越大说明目标函数下降越多，新的迭 代点也+ 以就越好，故坼+ 。可取为靠+ d ，而且。也可考虑扩大否则 越小， 例如“ 0 是参变量) ， k a n z o w 2 7 ，g a b r i e l 和m o r e 1 2 4 ，b u r k e 和x u 2 8 ，h o t t a 和y o s h i s e 2 9 ，x u 3 0 ， t s e n g 3 1 等提出了光滑化方法该方法的优点在于运用了标准牛顿法：在每步迭代 时求解光滑牛顿方程 中： ) d - 一中。o ) ， ( 1 1 3 ) 缺点是通常要求f 至少是r 函数以保证上式有解利用光滑逼近函数的j a c o b i a n 相 容性，c h e n ，q i 与s u n 2 5 提出了解非光滑问题的光滑化牛顿法( 也称为j a c o b i a n 光滑化方法) ：在每步迭代时求解混合牛顿方程 中：( x ) d 一一m o ) ， ( 1 1 4 ) 并建立了全局收敛性与局部超线性或二阶收敛性与光滑化方法类似，光滑化牛顿 法的收敛性也依赖于混合牛顿方程系统的可解性，因此对般非线性互补问题并 不适用k a n z o w 和p i e p e r 2 2 通过引入梯度步，提出了适用于一般非线性互补问 题的j a c o b i a n 光滑化方法 2 3 ，3 2 ，3 3 等进一步发展了此类方法 综上所述，光滑化方法的研究已取得了不少进展然而，为得到算法的全局收 敛性，上述方法都是使用线性搜索方法最近，y a n g 与q i 3 4 通过引入光滑逼近 函数，提出了求解n c p ( f ) 的光滑化信赖域方法，但要求f 是只函数 由于从非线性互补问题转化而得到的非线性方程组是非光滑的，因此不能应 用光滑优化中的标准信赖域方法而且非光滑性也使人们在证明算法的局部快速 收敛性中遇到困难本文给出了信赖域方法与线性搜索方法相结合的算法，该算法 适用于一般的非线性互补问题，从而推广了y a n g 与o i 3 4 的光滑化信赖域方法 我们证明了算法的全局收敛性与局部超线性或二阶收敛性 本文中我们利用k a n z o w 2 7 的光滑逼近函数 妒。( 口，b ) ：1 4 a 2 + 6 2 + 2 p 一口- b ，f 0 来逼近f i s c h e r b u r m e i s t e r 函数相应的光滑算子国o r “一彤被定义为 细，0 ，f ，o ) ) m 。o ) 一l i l i 吼 ，f o o ) ) j 记 1 一 已o ) 一丢中，o ) 1 垂， ) 1 4 论文的结构 这篇论文的结构安排如下：在第二章中我们将给出后面算法及其收敛性证明中要 硕士学位论文 用到的定义、引理和命题以及本文的一些符号和记法；在第三章中将摄出新的算法并给 出其适定性：算法的全局收敛性与局部超线性或二阶收敛性将分别在第四章与第五章中 给出；在第六章中将给出一些数值实验结果 ! ：=：。：些堡i ! 丝丝皇! 塑壑墼垄塑丝壅鎏 。=! ： 2 1 基本概念 第2 章预备知识 令g ：r 4 一r ”是局部l i p s c h i t z 连续函数c l a r k e 广义j a c o b i a n 3 5 被定义为： o g ( x ) ：- c o n v ( h e r “i 取 d c 做- , x r g 桫) - - , z 4 ， 这里d 。表示d 中的可微点构成的集合，c o n v a 表示集合彳的凸包 一般来说，d g o ) 很难计算，尤其当m ，1 的时候然而c l a r k e 3 5 中命题 2 6 2 ( e ) 给我们提供了如下的估计式： a g 0 ) 1 o g l o ) x a g 。( x ) 上式右边表示尺中的矩阵集，其第f 列由第i 个组成函数g ；的广义梯度给 出q i 3 6 称 1 o c g o ) 7 净o g 。o ) 始。0 ) 为g 在点x 处的c 次可微这个概念在本文中将多次用到 半光滑函数的概念在设计非光滑问题的高阶收敛算法中起关键作用，它最早 由m i f f i n 3 7 引入，凸函数、分段线性函数和光滑函数都是半光滑函数，由半光滑 函数复合而成的函数也是半光滑函数q i 和s u n 1 8 把半光滑函数概念推广到向量 函数若中：r “一胪是局部l i p s c h i t z 连续的向量函数，且有广义j a c o b i a na 币o ) 如果对任意h 彤 。l i 。r a 。一) 一 “o 存在，则我们称垂在x e r ”处是半光滑的 一个更强的概念是强半光滑函数，如果中在x 彤处半光滑，且对任意 v a 零o + 1 1 ) ，h 一0 ， 有 v h 一巾 ；矗) 一o q * 8 2 ) ， 则我们称中在x e r “处是强半光滑的，这里垂o ；，1 ) 是 数 2 2 预备结果 下面的结论可由 3 8 ，3 9 、( 强) 半光滑函数的概念以及q i 3 6 c 一可微的理论 得出 命题2 1 假定扛2 ) c r “是任意收敛序列，极限点z e r ”则下述结论成立 ( i ) 函数m 是半光滑的，因此对任意h 。a 。中 ) ， i 中 ) 一中o ) - h 。 一x 。) 1 l - 0 4 一z 。1 ) ( i i ) 若f 是l i p s c h i t z 连续的，则函数中是强半光滑的因此对任意 h i a c 西o ) ， i i 垂o ) 一m o ) 一h 。o + 一x ) 8 0 4 一工) 对于k a n z o w 2 7 光滑逼近函数吼，类似于e 4 0 中引理3 7 ，我们有下面的命 题及推论 命题2 2 对所有( 口，b ) e r 2 ，脚2 0 ， h 和，6 ) 唧，( n ，6 ) ls 铜石一冈； 特别地，对所有( 口，b ) e r 2 ，卢o ， k ( ，6 ) 一妒( n 加) | s 主扛 推论2 3 对所有x e r “，以，a 2 ：- 0 ，中，满足 i p 。 ) 一垂。( x ) l l s r i 百一i l ； 特别地，对所有x e r “，u 乏o ， j p ，o ) 一中o ) 4 s 茁扛 这里k 净压 为确保本文给出的算法具有局部快速收敛速度，我们必须控制西k 0 ) 和 o c 中 ) 之间的距离，这要用到下述命题，其证明见 2 2 中引理3 1 命题2 4 设x 是r “中任意一个向量则 l i m 如f ：o ) ，a 。中o ) ) 一0 由命题2 4 易知，对任意一个固定值6 ，0 ，存在参量万一芦0 ，d 卜0 ，使得当 p 【o ，司时， d 哑( 币： ) ，a c 币0 ) ) s 6 在本文的算法设计中，耳必须有一个明确的表达式以便我们选择p 的初值因此我 们给出下述命题，其证明见 2 2 中命题3 4 命题2 5 令石是r 4 中任意一个固定向量假定x 不是n c p ( f ) 的解定义常量 与 y o ) 2 掰 k q + e ) v ) 心苫o a ) 净靴m i n ) x ；+ 鼻( z ) 2 卜o ， 这里芦扛) i i f i x , 一曩q ) = 吣。令6 ，0 是一个给定的常数，定义 则 若字一州观 否则 d i s t f ( 中：o ) ，a c 垂o ) ) s d 下面的引理同样来自k a n z o w 和p i e p e r 2 2 ，它将在证明全局收敛性时用到 引理2 6 设工r 一，仁t r “和缸。 尺是两个序列若k 2 一z 且扣t 一o 2 3 符号和记法 溉v p ) 一v v ( x ) 令g ：r 一一r m 是连续可微函数则g ( x ) e r 表示g 在点工r “的j a c o b i a n ， 而v g ( x ) 表示j a c o b i a n 的转置 若x g r 一，则表示x 的欧氏范数，相应地，1 阻4 表示矩阵4 r 的由欧氏范 数导出的范数为不致混淆，有时也记为忙1 | ：或i 陋岵矩阵4 r 的f t o b e n i u s 范数 记为， 若a 尺一”是给定的矩阵，0 r “是r 1 ”中的矩阵组成的非空集合，a 和0 之 悟i 的距离记 d i s t ( a ，e ) 赠忱一丑l 当范数为欧氏范数或f r o b e n i u s 范数时，距离分别记为d i s t 2 ，o ) 或d i s t ，研，e ) 一 向量和同维向量集之间的距离可类似定义 设缸。) 和伽。) 是两个正数序列且敬 一o 若成一o ，我们记为d ( f l t ) ； 若! 鲤s u p a 。几( * ，即存在c ) o ，使得s c 段对所有七： o ，1 ，2 ， 都成立， 则我秆 记为口。一o ( f 1 1 ) 8 、lli-， 第3 章算法及其适定性 3 1 算法的描述 在本节中我们将给出信赖域和线性搜索相结合的光滑化方法 令 g q ) 一圭i 卜。 ) + v 中。o ) 7 d 一1 i ，。( 矿) + 中。0 ) 7 v 中。 ) 7 d + 要d 7 v 中。) r e 。p ) 7 d ( 3 1 ) 本文所提出的算法如下； 算法3 ，1 步0 取正常数a ，a ，7 ，p ，p ，仃，c 1 ，c 2 ，c 3 ，c 使之满足 0 c 2 cc 1 1 ，0 0 即可反之，若存在f ，使 o 。) 一q p 1 ) 一0 ， 则d 。0 是( 3 2 ) 的解，从而v 已 ) 一0 因此币。o ) 一0 利用引理3 1 可得 垂( ) 一0 ，这与v w o ) 0 矛盾 证毕 第4 章全局收敛性分析 4 1 基本结果 在给出算法的全局收敛性结果之前，我们先给出一些预备结果首先不难推出 下述两个命题 命题4 1 令缸) r ”是算法3 1 产生的序列假定x 是缸 的聚点且是 n c p ( f ) 的解，则k 是无限集且 心) - + 0 证明：假定足是有限的，则由( 3 8 ) 和算法中心的修正规则知，存在k 。e n 使 得当k e n 且k 苫k 。时， p k p t 。 日 。垂o “1 ) l i m a x t l , 6 k ，吉。垂o “) - 垂t t k o “1 ) 叶 ：- t i f f , 。哦 这与工是- v c e ( r ) 的解矛盾因此k 是无限集，从而由以的修正规则知，似。 _ o 命题4 2 若k 甚足，则 忙。牡忙。o “ 证明：若d “1 由梯度步产生，则由( 3 4 ) 知 因此由推论2 3 可得 c k ：一忙o “1 ) 卜i i 中 x ) l ，0 0 中，。 ) 0sl p 。 ) 一中o ) 0 + i 卜o ) i i 由( 3 1 0 ) 得 s r 瓦+ 愀) 卜。 s 0 中。o “1 ) 6 + i i 中( x “1 ) 一垂。 “) 0 + r 、i q h o “) 卜2 k 万q ： ：童堡i ! 塑i 里! ! 堡星塑垄望丝童鎏! ：= ： 以s ( 掣) 2 即 所以我们有 i p 。o l 卜。o “1 ) j | 若d “1 由信赖域步产生，则由算法中步6 知， 而由步5 知， 因此我们也有 肛t 。p t 一1 怿。) 忙怿。o “ 0 m 。o ) 0 t l | 垂。o ) 8 薯l m 。一。( 矿4 ) 0 6 中。o “1 ) 证毕 利用上述结果可以证明：算法3 1 产生的序列包含在某一水平集中在标准的 下降算法中，迭代序列扛) 扛l w ( x ) s 掣o o ) ) ，这里x o 为初始点由于算法3 1 使用了不同的效益函数，在梯度步中使效益函数、p 0 ) 下降，在信赖域步中使效益 函数瓢0 ) 下降，而一个效益函数的减小并不意味着另一个效益函数的减小，因此 有不同的结论 命题4 3 令扛 是算法3 1 产生的序列则 协 c l o t 缸r “l 掣( 1 + a ) 2 掣0 0 ) ( 4 1 ) 证明：令 墨2 七k i 帆。苫三忙o ) 一中。 2 ) 哆 ( 4 2 ) 及 酗忙k 。1 。巾 ( 4 is ) 则 k = o u k lo k 2 假定k 中的元素依次为 k o 一0 r 1 2 q l ( x ) 0 下面我们将证明则( 工) 一0 若不然，假设v 掣o ) 0 我们首先证明l i n m i n f t t2 0 假设l n i r a i n f t 0 由于对所有的k e l ， d t v l l ，0 ) ，由( 3 4 ) 知，当k e l 充分大时， v “1 ) 一平o ) s 一讲t i f v 掣o ) 0 2s 一三， ( 4 7 ) 其中c _ o r 。1 1 w x 1 1 2 ，0 ， 由缸t - - - o 和命题2 - 2 可得，七充分大时， i h 。o “) 一l l ，o “) k 三 及 l 半。 ) 一1 l f g ) 卜三 命题4 3 表明序列垂o ) 时是有界的再次利用缸。 - - o g 得，七充分大时， 2 r 厄私r 2 舻三 ( 4 8 ) 令l 包含l o , f ，f ：则对所有充分大的f ，类似予命题4 3 的证明可得 咻k 1 ) - 争沙) i | 2 s ”1 ) 卜射j i f z 掣o ”1 ) + 2 r 历捌中g p l ) 卜2 x 2 ” 一叩 + 三 ( 4 9 ) 这里最后一个不等式( 4 8 ) 由得出 当z ，充分大时，由( 4 7 ) 、( 4 9 ) 可知， 掣 “) 一v o ，) t _ “1 ) 一v o ”1 ) ) + 卜o ”1 ) 一掣 7 ) ) 一三 4 从而j o 。时，七i ，。j ) 一一m ，这与1 王，o ) z o 矛盾，因此罂i i l f 一o 由此我们可 以假定曾一0 ，这样当七三充分大时，步长a “4 总不能满足( 3 4 ) ，即 平+ 一d 卜- a ( x ) 一卅一川1 2 亦即 坚卫凳p 幽，一1 w ri i a ，_ 1 由于在l 中当k 一* ，f 一一0 由单的连续可微性可得 一w 0 + ) 7 即掣0 ) 芑一o v u ：( x ) 7 v 甲o 。) 即1 皇盯，矛盾。因此v 1 王，o ) 一0 证毕 4 2 算法的全局收敛性 现在我们给出算法3 1 的全局收敛性结果 定理4 1 令扛j 是算法3 1 产生的序列若厶是紧集，则k 净少有一个聚点 是掣的稳定点 证明：若k 是无限集，由命题4 3 知，k 的每个聚点都是1 王| 的稳定点下面 假设k 是有限集 若仁 中有无限多步由梯度步产生，由命题4 4 知，b j 的聚点工是l ，的稳定 点因此下面我们考虑梯度步有限的情形 设是k 中最大整数，则对所有量，l ，有 l ks l t ， # k 。0 t ， 及 怿) i ，帆，挣忙) 0 ，0 ( 4 1 0 ) 求解非线性互补问题的光滑化方法 由于缸。 单调递减且有下界，因此收敛设缸。 收敛到肛下面我们将证明= 0 若不然，假设t ) 0 则k 充分大时，以= p + 且 k ( e k - - * i 中，。 ) 7 v 中，。o ) 7 d c m a x 户l d 。0 。o ) ，p i p l l 9 ) 现在我们用反证法证明：至少存在一个聚点x + 使 v e ( x ) ；o ( 4 1 1 ) 假设扛 的任何聚点都不是掣的稳定点，则有 l i m i n f i l 则。 ) 0 ，0t - p 、 ， ：驴e 篇如 若d 是( 3 2 ) 的解，则由 4 2 中定理4 可得 如忙血卜篇 注意到 k o 。) 单调递减有下界，且当k 充分大时，七霞由( 3 5 ) 、( 3 - 6 ) 以及 驴，驯陋卜崩卜 这意味着乏趣。d ，从而有 鳃。o 由4 1 3 知，七充分大时 k ) 一么( d ) 鲁l 叶) 因此我们有 k 一1 l l + d ) 一q h ) i i 掣，o ) 一酝g ) 1 -f 吒 k k女 * 皇 墨 令 = = = = = ：。：，墼呈兰坠垒圣。：， ： s 鬲训 这说明当七充分大时，r k ，c ：，而此时，由算法中信赖域半径的修正规则知，a 。苫。 这与! 鲤一。矛盾因此存在个聚点z 使v ( x ) - o 若中。o + ) t0 ，利用引理3 1 可得中 + ) = 0 ，这说明x +n c p ( f ) 的解根据命 题4 1 ，这与k 是有限集的假设矛盾若中。o ) 0 ，则0 ) 0 ，由( 3 3 ) 知 中。o ) 7 v 中。) 7 d t m a x ! d 肛t i i q , ( x t ) ，一p 忙t t p l 。) 因此我们有 一v 已) 耖忙v 已g ) t p 渺f f k 。o ) 即f f _ ) f ) 畔o ) o 这与( 4 1 1 ) 矛盾 肛ao 也说明由梯度步d 一v v ) 所产生的是无限的利用命题4 2 与命 题4 4 即可得出结论证毕 一愁 ， 求解非线性互聿卜闯题的光滑化方法 第5 章局部收敛性分析 5 1 基本结果 在证明由算法3 1 产生的序列侈 在一定条件下是局部q 一超线性或q 一二阶 收敛的之前，我们首先证明：在一定条件下仁 收敛到唯一点工+ 为此我们用到 下面的命题，它由m o t 6 和s o r e n s e n 给出，见 4 3 命题5 1 设工e r “是妒 g r “( 不一定由算法3 1 产生) 的孤立聚点若对 收敛于x 的任意子列f k 都有 忙“1 一，幢一o ， 则整个序列仁 收敛到工 接下来我们给出卯( f ) 的r 一正则解的概念设x 是m ( f ) 的一个解定义 关于卫的指标集如下： 盘：一誓i 而，o ，墨( x ) 一o ， 卢i f i 一0 ，e 0 ) t o ， y - 矗i x i m 0 ，e ) o ) 如果f o ) 。非奇异，且 f o ) 阳一f o ) 加f ) ：f 0 ) 叩尺d 剧 是p 一阵( 即所有的主子式均为正) ，则我们称工+ 是c _ p ( f ) 的r 一正则解 r 一正则性等价于r o b i n s o n 强正则性 4 4 接下来的命题来自f a c c h i n e i 和 s o a r e s 3 9 命题5 2 若茗+ 是a r c e ( e ) 的r 一正则解，则a 。巾b j 中的每一个矩阵都是非奇 异的 下面我们先证明：若k 的一个聚点x 是n c p ( f ) 的r 一正则解，则整个序列 妒 收敛到x + 定理5 1 令k t 是算法3 1 产生的序列如果它的一个聚点毒是n c p ( f ) 的 r 一正则解，则k 一z 证明：我们只需验证命题5 1 中的条件满足即可 由命题5 2 知：解x + 的r 一正则性意味着a 。中b + j 中的所有元素都是非奇异的， 因此由 4 5 中命题2 ，5 及本文命题2 。1 知，x 是零g ) - 0 的孤立解，当然也是 n c p ( f ) 的孤立解 由命题4 1 知：指标集k 是无限集且k 卜+ o 命题4 3 表明：扛 的任意一 个聚点都是c p ( f ) 的解，从而算必然是k j 的孤立聚点 令仁k 是仁 的子列且 矿) 。一z 若x “由梯度步产生，则 若x “1 由信赖域步产生，则 l x 一工0 _ l p 4 s 川i 因此我们只需验证忙忱一。即可 l 卜+ 1 一并4 _ i p 0 由于x 是c p 陋) 的解，从而也是平的稳定点由掣的连续可微性得， 扣v b 一v 掣b ) - o 如果忙陀中的信赖域步有限，怛幢一。已证 如果怛幢中的信赖域步无限，不妨假设妇k 妇k ，且对任意七。，d 由 信赖域子问题产生由 中。o t ) r v 垂。o t ) r d t 。一m a x d 忙t l 吒o t ) ，p 她t i l 9j 可得 从而我们有 西。o ) 7 v 中。o ) 7 d t p