（运筹学与控制论专业论文）解非线性互补问题的非单调信赖域方法.pdf

摘要 摘要 本文研究非线性互补问题n c p ( f ) 的数值解法，为解决单调算法的迭代点 列在进入狭长区域时效率低下的问题，加快迭代速度，引入了非单调技术来改 进原有算法。通过将非单调技术与较为稳定、可靠的信赖域方法相结合，提出 了一类新的算法。 本文采用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 函数，得到相应 的光滑的非线性方程组。第三章给出了求解该方程组的非单调信赖域算法，算 法在信赖域子问题的下降量估计中引入“非单调比率”，当该比率可接受时即接 受该步迭代。同时，若目标函数下降得足够多，即更新k a n z o w 光滑逼近函数的 光滑化系数。 在假定f 是只函数的条件下，我们证明了算法产生的点列包含在一个水平 集中。且在水平集是紧集的条件下，算法至少产生一个聚点，从而保证了算法 的全局收敛性。进一步地，本文还给出了点列在一定条件下收敛到唯一点，并 有局部超线性收敛性及二次收敛性等性质。第七章进行的若干数值实验表明， 算法是有效的，尤其在等值线狭长的情况下，提高了单调算法的计算效率。 关键词：非线性互补问题；非单调技术；信赖域方法；全局收敛性；超线性收 敛- - 次收敛 a b s t r a c t a b s t r a c t i nt h i sp a p e r ，w es t u d yt h en u m e r i c a lm e t h o d sf o rn 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 s n o n m o n t o n es t r a t e g yi si n t r o d u c e dt oa c c e l e r a t et h ep r o c e s so fi t e r a t i o n s i n c et h et r a d i t i o n a lm o n o t o n ea l g o r i t h mw i l lb eo fl o we f l f i c i e n c yw h e nt h ep o i n t s e q u e n c ee n t e r ss o m en a r r o wa r e a s w i t ht h ec o m b i n a t i o no ft h en o n m o n o t o n e t e c h n i q u ea n dt h et r u s t r e g i o nm e t h o dw h i c hi sm o r es t a b l ea n dr e l i a b l et h a nl i n e a r s e a r c hm e t h o d ，an e w a l g o r i t h mi sp r o p o s e d b yu s i n gt h ef 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 ec o m p l e m e n t a r i t y p r o b l e m st oas y s t e mo fn o n l i n e a ra n dn o n s m o o t he q u a t i o n s f u r t h e r m o r e ，w eu s et h e k a n z o wf u n c t i o nt oa p p r o x i m a t et h ef i s c h e r - b u r m e i s t e rf u n c t i o ns ot h a ts m o o t ha n d n o n l i n e a re q u a t i o n sc a nb eo b t a i n e d t h et r u s t r e g i o na l g o r i t h mu s i n gn o n m o n o t o n e t e c h n i q u ef o rs o l v i n gt h e s ee q u a t i o n si sp r o p o s e di nc h a p t e rt h r e e t h ea l g o r i t h m a d o p t sa n o n m o n t o n er a t i o t oa p p r o x i m a t et h er e d u c t i o no ft h eo b j e c tf u n c t i o n s a n i t e r a t i o ni s a c c e p t e dw h e nt h er a t i oi s n o tv e r ys m a l l o nt h eo t h e rh a n d t h e s m o o t h i n gc o e f f i c i e n to ft h ek a n z o wf u n c t i o ni su p d a t e dw h e nt h eo b e c tf u n c t i o n g e t ss o m es a t i s f y i n gr e d u c t i o n w i t ht h e a s s u m p t i o n t h a tfi sap 0 f u n c t i o n ，w ep r o v et h a tt h es e q u e n c e g e n e r a t e db yt h ea l g o r i t h mr e m a i n si ns o m el e v e ls e t f u r t h e r m o r e t h em e t h o dw i l l g e n e r a t ea tl e a s to n ea c c u m u l a t i o np o i n ti ft h el e v e ls e ti sc o m p a c t w h i c hl e a d st ot h e g l o b a lc o n v e r g e n c e i na d d i t i o n t h es e q u e n c ew i l lc o n v e r g et oo n ep o i n ta n dt h e s u p e r l i n e a rc o n v e r g e n c eo re v e nq u a d r a t i cc o n v e r g e n c eu n d e rs o m ec o n d i t i o n s a s e r i e so fn u m e r i c a le x a m p l e sa r et e s t e di nc h a p t e r7 w h i c hs h o w st h ea l g o r i t h mi s q u i t ep r o m i s i n g e s p e c i a l l yi n t h ec a s ew h e nt h es e q u e n c ee n t e rs o m en a r r o w a r e a s ，t h ee f f i c i e n c eo ft h et r a d i t i o n a lm o n o t o n em e t h o dc a n b ei m p r o v e dal o t 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 s ；n o n m o n t o n es t r a t e g y ；t r u s t r e g i o nm e t h o d ；g l o b a lc o n v e r g e n c e ；s u p e r l i n e a r q u a d r a t i cc o n v e r g e n c e 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 秘农 2 0 矿9 年；月勿e l 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 饧吴孝 以年弓只汐1 3 第一章引言 1 1 非单调算法 第一章引言 我们以下述无约束优化问题为例 m i nf ( x ) x e r “( 1 1 ) 其中目标函数f 光滑。传统的搜索技术大多是单调算法，即每一步的搜索包 含着对目标函数单调下降的要求。假设在当前步最优解的估计为矿，且梯度 g 。= w o ) 0 。在线搜索中，通常要求沿着某个搜索方向d 寻找步长口，使 得下一个近似解”一+ 口。d 。，满足目标函数单调下降条件：f ( x “1 ) f o ) 。 而在另一类搜索方法信赖域法中，每一次在附近的一个信赖域中求解一 个近似问题的最优解。此时，该最优解亦需要使原目标函数有一定程度的下降 量，该步的迭代才能被接受。 由于最优化的课题便是目标函数的极小化，单调算法在直观上是很合理的， 因而它成为了传统搜索技术的主流，并且在实践上取得了巨大的成功。 但随着研究的深入，单调算法的问题也逐渐被发现。一个主要的问题是，在 很多情况下，假使一定要目标函数在搜索方向上取得一定的下降，那么步长因 子将不得不变得很小，从而将极大地降低优化算法的收敛速率。尤其当迭代点 进入等值线狭长的“峡谷”区域时，会出现严重的锯齿现象，使搜索效率极其 低下。如f 3 1 中以著名的r o s e n b r o c k 函数为例，对传统的信赖域方法和n e w t o n 法进行了比较实验，结果信赖域方法经过了五倍于n e w t o n 法的迭代次数，而计 算得的目标函数的精度却不及n e w t o n 法的一半。这是一个很典型的例子。因而， 如何在放松单调性要求的情况下，寻找更合理有效算法，以克服传统单调算法 的种种不足，便成为一个重要的课题。 非单调思想，顾名思义就是试图放松每一步迭代时对目标函数的单调下降的 要求。以线搜索方法的a r m i j o 条件为例，原条件要求步长因子a 满足下列条件： f ( x “) o 来逼近f i s c h e r b u r m e i s t e r 函数，相应的光滑算子m r “- r “定义为： f ，吼“，互 ) ) m o ) ：；i i l i 吼( ，e o ) ) j 记 1 l l ，一( x ) ：丢中 ) 1 币p ( 石) 。 本论文的结构安排如下：第二章中将给出算法及收敛性证明所需要的定义、 引理、命题，及一些符号和记法；第三章我们给出算法及其可行性的证明；第 四章我们证明算法的全局收敛性；第五章将证明算法的局部超线性或二次收敛 性。数值实验结果将在第六章给出。第七章是小结。 5 第二章预备知识 2 1 基本概念 第二章预备知识 设g ：r “呻彤是局部l i p s c h i t z 连续的函数，则由实分析理论，g 几乎处处 可微，且在其存在的任何有界集上，j a c o b i a n 矩阵有界。因此对任何x e r “，可 引入a a r k e r 【4 1 】意义下的广义j a c o b i a n 矩阵。设d g 是g 可微点的集合，则g 在 x u _ r “点的b 可微集定义为： a 矗g ) ； 日e r “i h 一! i mg 协) x k r = d o 贝i jx 处的广义j a c o b i a n 矩阵定义为 a g o ) _ c o n v o 曰g 0 ) ( 2 1 ) 记号c o n v a 表示集合a 的凸包。 然而一般来说，a g 很难计算，但c l a r k e r 4 1 找到了如下估计式： o r ( x ) r a g l o ) o g 2x ) a q ) ( 2 2 ) q i 4 2 d ? 贝j j 定义 a c g ) r ：一o g lx ) o g 2 ( x ) x a ex ) ( 2 3 ) 为g 在点x 处的c 次可微。 半光滑的概念首先由m i f f l i n 4 3 提出，它是一大类函数，包括光滑函数( 连 续可微) 、凸函数、分片光滑函数等，已经证明半光滑函数的和、差、积、复合 仍是半光滑的。半光滑的概念在设计非光滑问题的高阶收敛算法中起着关键作 用。 定义2 1 ：设币：r “一尺“是局部l i p s c h i t z 连续的，称m 在x e r “点半光滑，是指 对任意的he r “和h 0 ，总使 l i m f f h 1 y 曲中“+ t h 。 h - - h , t i o 6 ( 2 4 ) 第二章预备知识 存在极限，如果m 在集合s 尺“的每一点都是半光滑，则称m 在s 上半光滑。 进一步地，如果m 在x g r ”点半光滑，v v e o m ( x + ) 和h 一0 有 v h m g ；| 1 ) = o ( 1 l h1 1 2 ) 则称中在x g r ”点强半光滑，这罩m ( x ；j 1 1 ) 是m 在x 处沿h 的方向导数。 将非线性互补问题n c p ( f ) 转化为非线性方程组并用无约束优化技术求解 会导致一个困难，就是采用优化技术有时会使点列仅仅收敛到一个局部极小点 或稳定点，而非全局极小点。克服这一困难的方法之一就是利用正则性条件。 由【3 9 的定理4 3 ，x 是互补问题n c p ( f ) 的解等价于x 是虫的正则稳定点。 定义2 2 ：称g ：r “呻掣是只函数，若对任意的x ，y 掣且x y ， m a x - y ，) ( g f o ) 一g ( y ) ) 20 ( 2 5 ) l 珥。乃 昂函数实际是正则性条件的特例，因为由【6 6 】的推论5 3 1 0 ，x , r j - t - - g _ , b i h 题( 1 4 ) ， 若f 是一昂函数，则所有的向量都是正则的。这样，f 是昂函数的条件也就保 证了只要采用优化技术得到的收敛点列的极限必定是互补问题的解。 2 2 预备结果 以下结果可由【4 4 】、【5 1 及q i 4 2 q b 的c 一次可微理论得出。 命题2 3 ：设点列 x ) 是一收敛序列且极限石e r “，则以下命题成立： ( 1 ) 函数中半光滑，即v k a c 币 ) ， i i 中o ) 一西 + ) 一圪o 一x ) l l - o ( i l 一z + 1 1 ) ( 2 6 ) ( 2 ) 若f 为l i p s c h i t z 连续，则函数m 强半光滑，即v k a c m ) ， i l m o ) 一西o ) 一k o 一工) l i - o ( 1 l x 一z 0 2 ) ( 2 7 ) 下述结论由k a n z o w 和p i e p e r 在文献【3 7 】给出，它们在分析算法收敛性的过 程中有重要作用。 引理2 4 ：对任意的x e r “及0 ，下式成立： 7 第二章预备知识 其中r - 压。 i im ) 一m 。( x ) l l - ：r 石 ( 2 8 ) 引理2 , 5 ：设x e r “是任一固定向量，假设x 不是互补问题n c p ( f ) 的解，定 义常量： r ) ：5 罂髂 l i 誓龟+ e ) v 互 ) 吣芑。 及 口 ) ：2 嬲僻+ 互0 ) 2 ) o 其中芦o ) - 0l 五一曩o ) 一o ) 。对于给定的6 o ，定义 e ( x ，6 ) 曩 1 ， 若竽一州s 。 煎毒i ，其它 2 n r ( x ) 2 62 口0 ) 一 则对任意满足o 占se ( x ，6 ) 的s ，有 d i s t ( m 。协) ，a c m ) ) s6 ( 2 9 ) 注：令g ：尺”_ 尺”是连续可微函数，则g 协) 尺一表示g 在点x e r ”的j a c o b i a n 矩阵，而v g ( x ) 表示j a c o b i a n 的转置。 8 第二章算法及其适定性 3 1 算法描述 第三章算法及其适定性 本节我们给出非单调技术和光滑化信赖域方法相结合以求解n c p ( f ) 问题 的算法。 首先定义 q k ：= 去0 o ) + v 币“o ) r d0 2 ( 3 1 ) = v “o ) + v 1 l ，气o ) r d + 寺d r v 西“ ) v m ) r d 下面给出算法： 算法3 1 ： 第一步：选取j 下数c 1 ，c 2 ，c 3 ，c 4 ，r ，a 。i 。，a o ，j l ，且满足c 2 c 1 1 ， c 3 1 c 4 ，r 1 ，肛 0 及仞始点石”e r “。令反：- - i im ”) l l ， r 墨压，。：一( 兰风) 2 。令，l ( o ) ：= o ，k ：= o 。 二r 第二步：求解下列子问题的解d e r “： m i n 鲛“) i 忪忙a 。) ( 3 2 ) 第三步： 令 毗一。；m ，；a 。x 。，靠( x k - j ) ， v t v 。( x + d 。) “2 可刁芳丽 ( 3 3 ) 若r k c ：，则令。- 一c 3 色，返回第二步，( 此为内循环) 。否则转入第四步。 第四步：令x “= x + d ， k 产篇 m a x a m i d , a k 蚶 籍轳c 1 9 ( 3 4 ) ( 3 5 ) 第三章算法及其适定性 第五步：若v w ( x “1 ) = o ，算法停止。 第六步： 若0 m “1 ) 1 1 - ：m a x ( r i l k ，肛以l l 中 “1 ) 一m b o “1 ) 盼 则 展+ 。- ( 矿+ 1 ) ，并选取& + 。使满足 o 钆t s m i n 【唼骸- ) 2 ，等，矽”，饿+ - ) 其中f ( ，) 的定义如引理2 2 所示，且令m ( k + 1 ) = 0 。 否则，令展+ 1 - 反，“曩气，m ( k + 1 ) 一m i n 伽 ) + 1 ，m 一玲。 第七步：令k ：k + 1 ，回第一步。( 此为外循环。) ( 3 6 ) ( 3 7 ) 3 2 算法适定性 记n ：= o ，1 ，) 。不失一般性，我们假定算法3 1 不会在有限步内终止，即 对任意的ke n ，v w ( x ) 0 。因为v 1 l ， ) = a 西 ) r 中o ) ，v x e r “，因而这实际 上表明对任意的ke n ，中o ) 0 。 为了下文证明的需要，引入如下集合： k 皇 o u 仕l0 ) 忙m a x ( r i l k 小t _ 10 ) 一中o ) 盼) ( 3 8 ) ； 忌。一0 k l k 2 首先我们可得到下述结论。 引理3 1 ： 0 中( ) 一币缸o ) i i i i ) i i ，v ke n 。 证明：若k 圣k ，则= 龟一1 且由( 3 6 ) 得 t 以i i m ( x ) 一m o ) 0 0 m ) 1 1 所以有 i i ( 矿) 一缸 ) i i 0 中o ) i i 。 若k e k ，则由引理2 4 及( 3 7 ) ， i i ( x ) 一垂 o ) o k 厄 0 ，v m 。( x ) 非奇异。 证明： 记t = 1 擂而 1 属而 ，则有 v m 。 ，i 丁c ( 墨毛 + ( 墨e 即，一，一即 显然，v 。 ) 非奇异等价于下面的矩阵非奇异： 1 1 第三章算法及其适定性 记a = b = 叫葺 。f 是咒函数，则由昂函数性质，v f 是一咒矩阵。 吖 1 。1 v f e j 由昂矩阵性质，一个m 矩阵是昂矩阵的充要条件是m 的全部主子式均为非 负。故由b 的结构及 是昂矩阵易知，b v f 是昂矩阵。 又由a 的结构易知b v f + 彳为正定阵。 则v 。o ) = b v f + 彳为非奇异阵。 这样我们可得到如下结果： 引理3 7 ：若f 是昂函数，则算法3 1 中吒是适定的。 证明：我们只需验证： m 缸) 一q ) 0 ，v k e n 假设命题不真，即存在某个1 e n ，使得 m 。o 。) 一q ) = 0 则d = 0 是下述信赖域子问题的一个解： m i n q f ) l0d 忙a ， 。 从而旬o 。) 一0 。但我们已由引理3 1 得到中唧) 0 ，故矛盾。 1 2 口 口 第三章算法及其适定性 引理3 8 ：对任意的占及，算法3 1 中内循环迭代次数有限。 证明：首先，对占及，设。，d ，r k 分别表示第z 次内循环的信赖域半径， 步长及下降量预估比r 。( z = 1 ，2 ，) 关于信赖域子问题，根据p o w e l l 4 7 中的定理4 ，可得如下重要估计：若 d ，r ”是子问题( 3 2 ) 的一个解，则 哪，删协扣驯i m i n a k ，, 箍蒜 假设命题不真，则显然有当z 呻时，a 。j 一0 ，因此对充分大的， 由r k ，定义： 另一方面， 故 w ( ) 一q 纠) 令笋o v v o ) i i 气，一1 ! ! 气善三； 三群一1 q ( d ) 一v “+ d 。) 2 1 巧两刁而 q ( d 。) 一v o 。+ d ) i i q ) - q k ( d t ，) l 0 l i m i n f r k ，苫1 _ o ( a i j ) 2 阿刀f 丽两 则对充分大的z ，a 聃。a t ，显然与a t _ 0 矛盾。 1 3 口 砑 s 第四章全局收敛性 第四章全局收敛性 本章我们讨论算法的全局收敛性，我们将证明若f 是昂函数，则算法3 1 产生的序列 ) 在某个水平集内，且 矿) 的每个聚点都是互补问题n c p ( f ) 的解。 4 1 基本结果 我们先给出一些预备性的结果，以作为讨论全局收敛性的准备。首先对于 非单调性可以得到以下引理。 引理4 1 ：( i ) 若七，+ 1 - k ，s m ，则对于f 一1 2 ，k ，+ 1 一k ，有 q s i ，+ i - 2 鲥m ；t a 川x 一 ，1 l ，( x k l + t - 1 ) = 。， 7 ) ( 4 1 ) ( i i ) 若后+ 1 - k ， m ，设z ，= m i n k + 1 - k 一m ，m ，l 为正整数且使得 k + l - k f 一埘 0 ，则有 恶努l l ，( x k j + m i + i - 1 ) sm a xi i ，t t io ，埘卜1 “- 1 ) sl 王， ，o 7 )(42)l 1 i j i z ，。 5 i $ m k i j 证明：( i ) 首先，若i - 1 ，因为朋 ) = 0 ，故显然有 王，t ，= v 靠，( x 7 ) 若i = 2 ，同样有1 l ，。，= 1 王，“，x k , ) 。因为x ，“一石7 + d j 由( 3 3 ) 1 l ，气，x k j + 1 ) s v t ，一v 气， ) 故 l l ，。，+ ，一m a x q j 气，( x ) ，v ， _ + 1 ) = 气，o ) 故i = 2 时成立。 以下用归纳法，若i - 1 t - 1 时( i ) 均成立，我们证明i - t 时亦成立。 1 4 因此 由归纳假设，可得： 因为x ，“ v 小f - 2 = v ，x k , ) = z ，一+ d j + ，= z 。+ 口7则有 1 i ，缸，o + ) sl l ，t ，w t = v “， ) l l ，t ，小。一m a x v ，x k j + t - 1 ) ，l 王，t ，小z ) 一v ，o 7 ) ( i i ) 要证不等式第一部分，只要证明对任意的i 且1s is z ， v ，。，o ，+ m 小1 ) s ，m 小a j 】i f xq l 钿 量，+ 盯h 卅1 ) 首先注意到，由函数1 l ，。的定义 i = 1 时， 有 舭= k m a ；肘xq j 一舯1 m ) x ，+ 埘= x j + 埘+ d 。，+ 加一1 。 = x 。+ 口。 ，则由( 3 3 ) v ，0 ，+ 删) s1 l ， ，+ 埘一。一m 。咖a 材xw ，o ，+ m 小1 ) 故i = l 时不等式成立。 以下用归纳法，假设i = l t - 1 时不等式均成立。 则i = t 时，由归纳假设 ( 4 3 ) v 。， ，+ 删伽1 ) s1 l ，t ，+ 埘小zsm a x m m ，a 。x 一， q j h ，g ，+ 刎“- 1 ) ，v t ，+ 删一- ) s l l ， ，+ 埘一。= 霉野v ， j + 肘“4 ) 故命题( i i ) 第一部分成立。 依次类推并由( i ) ， m 龇a 而xw 啊) s 埘m ；a 肼xq ，m h m ) s m 蜥；a f x q j 舢埘一1 ) 量sm ，一；a x q j m “)1 墨j s f 向、 7 1 一 。白、 7 一v ，( x 7 ) 故命题( i i ) 第二部分成立。 ( 4 4 ) 口 第四章全局收敛性 利用以上对非单调性的分析，下面的引理将说明，若fgp o 函数，则算法 3 1 产生的点列矿将包含在某个水平集内。 引理4 2 ：若f 是昂函数，则算法3 1 产生的点列 矿】i 将包含在水平集 厶：= 仁f i s r “lv ( x ) s ( 1 + ) 2 v ( x o ) 】内 证明： 对任一j 下整数k ，记k 为k 中满足k ，七的最大指标。则由算法3 1 的 第三及第五步易知： kis kj ，p k i p k l ， 若k jn ；k k j n 且由引理4 1 1 1 “ ) 1 1 1 1h 。 l ) 1 1 ，若七s 七 0 ，有【，l o 。则显然有x 7 1 l o ，且 1 6 第四章全局收敛性 令 展= 币( x ) 忙( 1 + | i 【1 ) 0 中0 。) k ：一 七ki 叩反一，肛。1i im ( x 。) 一m 一，( x ) 0 k 2 净忙ki 椴一。 o ， 展，syj f l o 一) ，i i , i , ( x 。) 0 且 ，s 百1 。s 了1 2 ，i i ( x 。) i l - - u - ) 1 1 z t j s 石os 孑r 。 。 结合( 4 7 ) ， o m ( x ) 忙y i l 巾o 。) 1 1 + 鲁i l m o 。) 8 s ) ，7 ( 1 + ) 0 ( x o ) 0 ，v x g u i 1 7 ( 4 8 ) ( 4 9 ) ( 4 1 0 ) ( 4 1 1 ) ( 4 1 2 ) 第四章全局收敛性 所以u j 厶，这就证明了( 4 6 ) 。 由( 4 5 ) 、( 4 6 ) 即得 x e u ，厶，k ，s 七 七，+ 1 口 进一步地，由f i s c h e r 4 4 ，若f 是一致p 一函数，或者更一般地，是一尺。函 数，则上述引理定义的水平集厶是紧的。 4 2 算法的全局收敛性 本节给出算法的全局收敛性的证明。 引理3 8 曾利用了以下关于信赖域子问题的估计式： 、p ，一q 。c d ，乏丢i l v v 气c 石，i i r a i n a , , i 孑三；兰i 舌斟， c 4 1 3 ) 本节全局收敛性的证明也将使用这一估计。 引理4 3 ：若k 是一有限集，则存在无穷指标集k + ，使得下式成立： o s 【v t v 气“) 】 + o o 七k 证明：首先v k e n ，由( 3 3 ) 、( 3 4 ) 内循环终止条件，易知v t 一1 l ，qo “1 ) 0 成立。显然帐，o s 【l 王，t 一1 l ，q o “1 ) 】成立。 因为k 是一有限集，不妨假设k 是k 中的最大指标。则v k k ，成立气= ， 9 k = 9 ：o 记作- s ，- 令 k = 仕iv ：o m ) = m 。缸a 村x q j ：o ，+ 埘“_ 1 ) ，z 一1 ，2 ， ( 4 1 4 ) 任取七k ，设七j + ms 七 m a x r ，q0 q ( x ) 0 ) m ( ) = m ) + 日0 ) f 下面证明点列 矿) 至少有一个聚点x e l o 满足下式 v l l ，o ) = 0 f 假设以上结论不真，则必有 l i m i n f0w 七) 0 k ” 、 v v ) 8 h 凹f 丽东矸如。0 v m o ) 旷 则由( 3 3 ) 、( 4 1 3 ) 及引理4 3 可得 1 9 ( 4 1 6 ) ( 4 1 7 ) ( 4 1 8 ) ( 4 1 9 ) ( 4 2 1 ) 第四章全局收敛性 【1 l 气) 一q k ( d ) 】 七k 一 0v ，o ) 0 故 k到。e w ：) l im i “色，赫卜 ( 4 2 2 ) 其中k + 即引理4 3 中( 4 1 4 ) 所构造的子集。 这表明 t ( 4 2 3 ) 七k 因此存在某个聚点x ，使得 l i ma 。一0 ，l i m x 一z t 瓢t 哉 与( 3 5 ) 矛盾，故( 4 1 8 ) 得证。 另一方面，假设有点列缸k 懿收敛至x 。由命题3 6 及( 4 1 8 ) 得 m 。) ) i 懿一中( ；) = o 。故存在七尼，使得v 七局，且七七 i i m 。 。) i b ( 1 一切卢 由此式及( 4 1 6 ) 、( 4 1 7 ) ，v k 匠，且k k i i 中 ) 忙( 1 一) 0 西0 ) s ( 1 一肛) ( i lq ( x ) 0 + 0m ) 0 ) 即 0m ( 矿) 0 ( , t 一0 1 iq ( x ) 从而有 i i 西( 矿) i i 1 l m 0 ) i i + l i q ( x ) 0 声：= fix i = o ，只( 工) = o ， ) ，：； f i 溉= r e o ) o 定义5 1 ： 称n c p ( f ) 的解x + 为r - f 则的，若v 兄。o ) 非奇异，且它在矩阵 n f o o ( x ；f o p ( x ) j i 中h u r 补v f a p ( x ) - 晖) 耽) - 1 是一个脚阵。 由凸分析知识容易证明，由于驴( x ) ，m ( x ) 局部l i p s c h i t z 连续，故垂在尺”的 任意点上具有c l a r k e 意义下的广义j a c o b i a n 矩阵a 中，且有如下性质。证明请见 文献【6 6 】的性质5 2 2 。 引理5 2 - v x e r “，我们有a 垂 ) r 似 ) 一i ) + v f o ) p ) 一i ) 其中i 是咒，l 阶 单位阵，a ( x ) 和b ( x ) 皆为对角阵，即 彳 ) ；d i a g 似o ) ) ，b ) = d i a g ( b u ) ) a 蜘j 南当驰卅咐 i 每， 否则 驯= 黔警删 其中( 毒，n ) 满足条件i i ( 量，p , ) l b l 。 引理5 3 ：设x 为n c p ( f ) 的r 正则解，则o e a ( x ) 中的每个矩阵都非奇异。 证明：任取c o a v ( x ) r ，由引理5 2 和x + 为n c p 的解，可得 f _ 观。v ( 一) 0 。，、i c = i - 。( 一l a a ) + ( 锄一) o 所l 【一曝 v f y a ( b 邸一l a a ) 一，玎j 要证明c 非奇异，只要证明： 一g 夕；一g ( ；：) 2 。 只有零解，其中g 是c 的f i l l - 阶主子块，将此方程展开，即得 f v 只。y 。+ v ( 1 a p b 邸) ) ，卢20 、飞f ，y 。七、f 强q 郾一b 0 yb = 一q 邛一a o b 因v e 。非奇异，可从第一个方程解出虼，再代入第二个方程，即 y ni 飞f ：飞f 邸q 印一b 0 b 孓fb l 一飞fh 孓f 蛰f 。泌礓一bx 舢= 一( i a a a 目a b 于是仅需证方程 ( v f a a v f a ，f ：冀f 。0 q b b 0 ybi q 印一a e 0 yb 0 ，及 k 0 ，使得对任意的k k 且k 尼， 0 ( ) ) 。1l i e u 一 一 则由引理4 4 ，存在k k ，使得对任意的k k 且七k ， 0 ( m o ) ) 。1 巾0 ) i b 血。s 。 此即表明子问题( 3 2 ) 的信赖域半径不积极，故信赖域子问题( 3 2 ) 有唯一 解： 第五章超线性收敛性 d = 一伸“) ) 1 m ) 所以有q 似) = 0 ， l 王，h ) 一姨似) 一去m q o ) 1 1 2 且 v t - q j “( 矿+ d ) l 王， g ) 一1 i ，q o + d ) ；v h o ) 一q “) + 珐( d ) 一l 王，o + d ) = 钏m ) 1 1 2 - o ( 1 l d l | 2 ) = 知垂 ) 1 1 2 - o ( 1 1 “) 1 1 2 ) 故 1 mi n f ，l i mi n f ! 垒生! ! 二! 垒堡：兰：! ：】 h 掣”h 掣k 乓蒜赢f 。1膏 - 一、 ，x 7 这表明存在乏乏，使得对任意的忌k 且尼2 k 。，都有屹 c 2 ，即 5 2 局部收敛性 x ”；x + d 。 口 本节给出算法的局部收敛性方面的结果，为此先给出以下命题。 引理5 5 ：设g ：r ”一尺”是局部l i p s c h i t z 连续函数，x e r ”是g ) 一0 的解，且 使得o g ( x ) 中所有元素非奇异，假设有序列缸。 c 尺“，p c r “，使得 l i m x 一茗且l i x + d 一z i i = o ( 1 l x 。一x + 1 1 ) 则 0 6 ( x + d ) i i = o ( 1 1 6 ( x ) 0 ) 证明：设l 0 为x 某邻域内关于g 的l i p s c h i t z 常数，则由a g ( x ) 中元素的非 第五章超线性收敛性 奇异假设及c l a r k 4 1 1 的隐函数定理可得，在充分靠近g o ) 的某个邻域内，反函 数g - 1 存在且局部l i p s c h i t z 连续，则对充分大的k 0 g o + d ) i i - - i l g ( x + d ) 一c ( x ) 0 s z , l l x + d 一x 0 so ( 1 矿- - x 0 ) 一o ( i lg 。( g ) ) 一g 。1 ( g ) ) 1 1 ) s o ( 1 l g ( x ) 一g ( x + ) 1 1 ) = o ( 0 g g ) 1 1 ) l j