（计算数学专业论文）几类信赖域算法的研究.pdf

摘要 线搜索方法和信赖域方法是求解最优化问题的两类最基本的算法，求解线搜 索方向和信赖域子问题分别是其关键的组成部分之一，另一个关键点自然就是算 法框架本身了本文主要着眼于信赖域算法子问题的求解和算法框架的改进上 在信赖域子问题求解方面引进了自适应的思想，在框架的改进方面引入了非单调 技术和过滤( f i l t e r ) 技术等策略，而后从理论上对这些改进后的算法框架进行收敛 性分析，并将其应用于许多典型的优化测试模型中，通过数值实验检验了新算法 的效果 第一章叙述了信赖域算法研究的情况和本文研究的主要内容，并简单介绍了 自适应思想，非单调技术和过滤器技术以及它们的发展状况 在第二章到第四章的内容中，我们主要考虑无约束的优化问题的信赖域算法 以传统的信赖域方法作为基础，先后提出了无约束优化问题的非单调自适应信赖 域算法及其改进算法、非单调过滤器自适应信赖域算法，并在一定的条件下证明 了这些算法的全局收敛性其后，给出了这些算法求解无约束问题的数值实验的 结果，这些数值结果很好的说明了改进的信赖域算法比传统的信赖域算法在计算 效率上有较好的效果 第五章结合前面的非单调思想、过滤器思想，将这些思想推广到带等式约束 的优化问题上为了避开单纯的过滤器技术不能完全排除m a r a t o s 效应的干扰， 考虑用非单调过滤器技术来判定试探步的可接受性在试探步的求解方面，不再 采取前面几章通过求解传统信赖域子问题的方式得到，而是通过分别求得切向步 和法向步从而得到试探步最后我们在一定的条件下，对提出的算法进行了详细 的收敛性分析和数值实验 关键词：无约束优化；信赖域：自适应技术；非单调技术；过滤器；全局收敛性 a bs t r a c t l l n e a rs e a r t hm e t h o d sa n dt r u s t r e g i o nm e t h o d sa r et w om o s ti m p o r t a n t a i g o r l t h m 8t ot h eo p t i m i z a t i o np r o b l e m s t h ek e y c o n s t i t u t ep a r t so ft h e ma r es e a r c h d l r e c t i o na n dt r u s t r e g i o ns u b p r o b l e mr e s p e c t i v e l y a n o t h e r i m p o r t a n tp a r ti s 舱t u r a l l yt h ef r a m e w o r kt h e m s e l v e s i nt h i s p a p e r , w ef o c u so ni m p r o v i n gt h e s l o v l n go ft h et r u s tr e g i o ns u b p r o b l e mb yi n t r o d u c i n gt h es e l f - a d a p t i v ei d e aa n d t h e t r a m e w o r kb yu s i n gs o m en c w s t r a t e g y ss u c ha sn o n m o n o t o n et e c h n o l o g ya n df i l t e r t e c j l n l q u e 。i h e nw ea n a l y s et h e c o n v e r g e n c eo ft h ei m p r o v e da l g o r i t h m su n d e r c e r t a l nc o n d i t i o n sa n d e x a m i n et h e i r p r a c t i c a lc o m p u t i n gr e s u l tb ym a n y e x p e r i m e n t s i nc h a p t e f1 ，w eb r i e f l yi n t r o d u c et h ea c h i e v e m e n to ft r u s t r e g i o nm e t h o da n d o u rm a l nr e s e a r c h t h e nw ei n t r o d u c et h e s e l f - a d a p t i v ei d e a ，t h en o n m o n o t o n e t e c h n o l o g ya n df i l t e rt e c h n i q u e f r o mc h a p t e r2t oc h a p t e r4 ，w em a i n l yc o n s i d e rt h et r u s t r e g i o nm e t h o do f u n c o n s t r a i n t e do p t i m i z a t i o np r o b l e m s b a s e do nt h et r a d i t i o n a lt r u s tr e g i o nm e t h o d w ef i r s t g j r e t h en o n m o n o t o n e s e l f - a d a p t i v et r u s t r e g i o na l g o r i t h ma n di t s l m p f 0 v e m e n t t h e ni n t r o d u c et h en o n m o n o t o n ef i l t e r s e l f - a d a p t i v et r u s tr e g i o n a j g o r i t h m l a t e r l y , w ep r o v et h ec o n v e r g e n c eo ft h ei m p r o v e da l g o r i t h m su n d e r c e r t a i n c o n d i t i o n sa n dr e p o r tt h er e s u l t so ft h e s e n e wa l g o r i t h m s o ns o m e u n c o n s t r a l n e do p t i m i z a t i o n p r o b l e m s a l lt h er e s u l t ss h o wt h a t o u ri m p r o v e d a l g o r i t h m sa r eb e t t e rt h a nt h et r a d i t i o n a lt r u s t r e g i o nm e t h o di ne f f i c i e n c vo ft h e p r a c t i c a lc o m p u t i n g 1 nc h a p t e r5 w ee x t e n dt h en o n m o n o t o n e t e c h n o l o g ya n df i l t e rt e c h n i q u et 0t h e o p t i m i z a t i o np r o b l e m sw i t he q u a l i t yc o n s t r a i n t e d b e c a u s et h ep u r ef l l t e rt e c h n i q u e c a nn o tg c ir i do fm a r a t o se f f e c tc o m p l e t e l y ，w et r yt oj u d g et h ea c c e p t a n c eo f t r i a l p 0 i n tb yn o n m o n o t o n ef i l t e rt e c h n o l o g y i nt h ea s p e c to ft h et r i a ls t e p ，w ec o m p u t e a q u a s l 。n o r m a ls t e pa n dat a n g e n t i a ls t e pt og e ti ti n s t e a do fs o l v i n gt h et r u s tr e g i o n s u b p f o b l e m l a s t l y , w ea n a l y s et h ec o n v e r g e n c eo ft h ei m p r o v e da l g o r i t h m su n d e r c e r t a i nc o n d i t i o n s k e yw o r d s ：u n c 。n s t r a i n t e d 。p t i m i z a t i o n ；t r u s tr e g i o n ；t h es e l f - a d a p t i v ei d e a ； n o n m o n o t o n et e c h n o l o g y ；t h ef i l t e r ；t h eg l o b a lc o n v e r g e n c e i l 符号 尺 尺“ ”l 故 a i 五 g i 、耽 v 2 暖 l 符号说明 含义 实数集 刀维实数集空间 欧几里德范数 第k 个迭代点 迭代点毪处的信赖域半径 f ( z ) 在迭代点处的函数值 ，( x ) 在迭代点处的梯度值 ，( x ) 在迭代点黾处的h e s s i a n 矩阵 厂扛) 在迭代点处的h e s s i a n 矩阵或其近似 单位矩阵 i i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写的成果作品对本文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明本人完全意识到本声明的法律后果由本人承担 作者签名：李耘3 易日期：加晨年f 月，夕日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅 本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密团 ( 请在以上相应方框内打“ ) 作者签名：季在击当 日觏：纱暑年 具。： 日 导师签名：割振诲日期：非，月日 第一章绪论 最优化理论和方法是一门应用性很强的学科，经济、管理工程和自然科学研 究的许多问题都可以归纳为一个优化模型 v a i n ，( x ) ， s j q ( z ) 一0 ，f e ， ( 1 1 ) c j ( z ) so i e i 其中厂，c i ：r “_ 尺的函数，e 、，是等式约束、不等式约束的指标集，e 的模 i e i = 他，的模l ，i 一，并记m - 他+ 对模型( 1 1 ) ，可根据不同的角度进行分类根据函数的线性性可分为线性优 化和非线性优化，根据函数的可微性可分为光滑优化和非光滑优化，根据是否有 约束条件可分为约束优化和无约束优化本文中，分别对无约束优化和约束优化 中的非线性优化问题的算法进行研究 1 1解最优化问题的基本方法 迭代法是解非线性优化问题的基本方法在具体算法中，可分为线搜索方法 和信赖域方法两种不同的算法策略，我们以无约束优化问题 m i n ，( x ) ，( 1 2 ) 为例来说明 在线性搜索策略中当前迭代点& 处，算法需要确定一个搜索方向d k 和沿此 方向的搜索步长九，并通过x k + 。一五+ 九以得到新的迭代点，从而实现算法绝大 多数线搜索算法要求噍是一个下降方向，也就是d j c o ( c o ( o 1 ) ) 则接受试探步，令 + ，一t + 畋，并扩大信赖域半径；否则， 缩小信赖域半径并且重新求解子问题( 1 4 ) 这种传统的根据吃的值，人为的按常 数倍来调节信赖域半径，完全没有利用当前迭代点处g 。、v 2 厂( t ) 等信息，初 始信赖域半径也只是不加分辨的给出一个常量的机制，当在目标函数的非线性程 度提高时，这种迭代由于缺乏全局的信息，可能会使收敛过程过早地陷入局部极 小点为克服此缺陷，结合前面的迭代点的信息与当前点信息而构建的信赖域半 径选取机制称为自适应信赖域机制近期的研究中，许多自适应信赖域算法被提 出1 4 1 删s a r t e n a e 首先提出了一个自动确定初始信赖域半径的i t r r 算法章样荪 2 l 叫等提出了一种新的自适应信赖域算法信赖域半径选取机制为4 。刿，其中 o c 0 ，o r 1 ，0 o 使 得：i 恢i i k 成立，且i i v 2 厂( z ) l i o ( 2 3 ) 由( 2 3 ) 式和算法2 1 中步4 可得： 厂( ) 一厂( + 噍) 2 r p r e d t 之2 - 蠹m i n 4m i n 仙k ) ，1 ) 。2 o ， 即厂( ( t ) ) 2 厂( 鼍+ ，) + 去i i i i n 4m i n 仕k ) ，1 ) 。2 ，故有 f ( x l ( m ，) sf ( x l ( ) ) 一去i i l i n m i n 仙k ) ，1 ) 2 ( 2 4 ) 而 正( 。) ) 是收敛的，所以( 2 4 ) 式表明： ( 。) _ o 令磊靴她旷丽 叫晶忙舡) i l ，l | 飘一l 卜解 由算法的机制可知：磊。丽a r e d t ( t ) ，7 ，这与磊 o ， 成立的最小的非负整数 改进算法中仍然通过求解如下的信赖域子问题 m i n 敛( d ) = g 一+ 1 2 d t 嘎d ，s t 忙0 。 ( 3 1 ) 得到试探步畋，其中t c p & m a x t l g 。吼时，p 为非负整数 在迭代点故处若恒取吼一一g 。，则m a x l l g 。吼0 ) ；恬。| l ，此自适应信赖域半径 就退化为 。! 埋正的情形，而且本章的色总有 盛b kg k 色：c p 殴m a x l l g , l l ，i i 吼) 2 坚正，信赖域半径的扩大有利于得到较大的试探步， g i 也g k 使得迭代点以更快的速度收敛到稳定点 关于非单调思想，以第一章中的非单调思想为基础进行改进在第一章中非 单调的主要思想体现在对正( 。) 的取法上，即五( 。) = ，( _ ( 。) ) ；。翼蒜) f ( x k 一，) 本节正( 。) 的取法采取如下的机制为了得到( 。) ，首先在点吆处找到一组系数 ( ，使得 蠢。丸( ，) = 1 ，且对任意的j o ，1 , 2 ，m ( k 一1 ) ) 满足疋( j ) a ，其中a ( o ，1 ) 是常数， o s 所( 七) sl i l i n 肌( 七一1 ) ，n ) ，k 苫1 ，m 是非负常整数，垅( o ) 一o 乃( 。) 采用如下机 制 石c t ，2 。：m ，。a 。x 。， 厂( c t ) ，”喜九t ，- ，( 】气，) 从上面的力( t ) 的选法可以看出，当t 篆 x - 1 1 九( ) f ( x k ，) 。；m 。a x ( 。) ( x k 4 一，) 时，本章的正( t ) 选 取机制就退化为第二章中的机制，所以第二节中的非单调思想是本章的非单调思 想的特殊情形类似的定义实际下降量为a r e d k 一厂( ( 。) ) 一，( + d k ) ，预测下降量 为删。= 敛( o ) 一纯( 矾) ，定义气= 器 算法3 1 非单调自适应信赖域改进算法 步1 给定x oe r “，b o r ，f 0 ，0 o 使得l l 嘎忙m 为了方便后文表述，在算法3 1 中步2 到步5 间的循环，称为外循环，步2 到步4 间的循环，称为内循环d 。( ，) 表示在迭代点吒处第p 次内循环对应的信赖 域子问题( 3 1 ) 的解， 此时的信赖域半径a 。用a 。( ，) 表示， 即 。( p ) 一c p & m a x l l g 。| i | i 吼| i ) ，c 的值用气( p ) 表示而d ：表示在迭代点处内循环结束 时信赖域子问题( 3 1 ) 的解，q 是吒处内循环结束时c p 的值 引理3 1 若假设3 1 、假设3 2 成立，则对任意的七有 札问k 叫”蚪 2 ， 证明：类似于引理2 2 的证明 引理3 2 算法3 1 是适定的，即算法3 1 的内循环有限终止 证明：类似于引理2 4 的证明 引理3 3 若假设3 1 、假设3 2 成立， _ ) 由算法3 1 产生，则有 ( x k + ) s 厂( ) 一a 善鬼一九s ，( ) 一a 荟以， ( 3 3 ) 1 2 ；g e e 吃2 焉矗恢1 1 2 m i n r q ，1 证明： 由算法3 1 的步4 可知 气- 等一等总铲 由( 3 2 ) 掰1 1 ( 3 4 ) 式有 胞+ 1 ) 乩州嗍( 训娟雌恬删i i n 卜，粉 又由菇磊级一菇盈级+ i h q 。1 1 2 和l l b , i i g 可知 s 慨+ f ，| f s2 m “ 从而有 书川幽卜，阱习u 1 1 击c p 音，计 妯蹦趴铲烈3 6 ) 婀得 书川m m 卜，糊s 一面 伊i it i l 2 晌h ，1 ) 、 ( 3 4 ) ( 3 5 ) ( 3 6 ) ( 3 7 ) ，( + 。) s ，( 而( 。) ) 一气 在，( 以+ ，) s ，( 。) ) 一噍成立的基础上，下面用数学归纳法证明引理的结论 若k = 1 ，引理明显成立假设( 3 3 ) 式对t , 2 ，3 ，k 都成立，分两种情况讨论 k + 1 的情形： 情形( 1 ) ：若正c t ，。乖m a 。x 厂( 气) ，“荟( k - 1 ) 九t ，( & 一，) ) 2 ，( & ) 2 吲m 酬a x 和吼乳) ，( 叫- ，( 枷惰 厂( + t ) s 厂( 而) 一魄s 厂( ) 一a 萎啊一吃s 厂( ) 一a 妻啊 袱2 瞄靠爿m 删a x ，苫w ( 叫一r e 乳( k - 1 肚a 1 3 记乏= m i n 露一1 ) ，由厂( “) s 厂( 薯( 。) ) 一丸可知： ，( 以以) s ；| ；疋e ，( k ，) 一心s 耋五t ，( ，( ) 一a 妻2 嚏一吃毒4 ) 一嘎 r e ( k - 1 ) 而系数九( 力满足薹九( j ) 一1 且对任意的j o ，1 ，2 ，册( 七一1 ) ) 有九( j ) a ，故可得 ，( + t ) s ，( ) 一a 妻2 ( ( ；| ：九t ，) 啊) 一妻( 九r ，心一，) 一噍 s 厂( ) 一a 善噍一a 荟，盖，噍吨 s ，( x o ) 一九吃一魄 s ，( 工。) 一a 鬼 综合上述分析可得引理3 3 为真 引理3 4 对任意的x o ，若假设3 1 、假设3 2 局2 - 亡r ， 黾) 由算法3 1 产生，则 & ) q 。 定理3 1 若假设3 1 、3 2 都成立且= 0 ，则 m l l g 。f _ 0 让明：由引理3 3 司知： a 善魄墨厂( ) 一盹+ ，) t 根据假设3 1 和引理3 2 ，令k _ 则有y 鬼 0 0 ，即 智 ! i m 噍一0 t 而由心的定义可得 ! i m 。gl = o 或憋气一o ( 3 8 ) 下面用反证法说明也i m 。c k 乒o 设。l i m 。c , , t0 令喀a 是信赖域子问题( 3 1 ) 在信赖域半径- ：1 ：时的解，其 中：是在迭代点处的内循环结束时信赖域半径的值 1 4 又由算法3 1 可知 疆轷 p i 蒲叫 由假设3 1 、引理3 3 和密i m 。c k 。o 可以类似第二章中引理2 6 中当z ( 尼) 呻时 磊_ 1 的方法可以证明 于是l i m r k = 1 与 o ，o r 1 ，o 0 ，当k 充分大时有 恢1 1 c o 根据迭代点进入过滤器的机制，我们可知：v k 。k ，毛充分大后， 3 ：e 0 , 2 ，甩) 满足 m 气) _ i g ，( 气) i s 叱i i g ( - ) h ( 4 6 ) 根据假设4 2 ，可得 g k ) 是有界的，因此存在一个收敛的子歹i j ，不失一般性， 就假设为 g 岛1 从而取七- - - ，0 0 ，则可f 1 3 ( 4 6 ) 式得 l i m 。i n 。f i i g tu - o 定理4 2 若假设4 1 、4 2 、4 3 都成立，= o 且k l i 0 ，对任意的k 使得 8 & 忙 o ，而0 k 0 o 和乏 o 使得对任意的七 石 o 都有幺 毛且气t 7 不妨令如； 七i 气2r , k 石) 由( 4 4 ) 式和气，7 可得： 荟( 如) 一，( ( & + 训 芑磊一仰( d ：) ( 4 7 ) 2 骖叫i i 徊卜铷川煳 由( 4 7 ) 式和吼 毛、0 0 苫 o 可得 l i m 。气= o 类似于定理2 7 中a 似) 呻0 ( 七_ ) 的证明，我们可得出世i m 。q o 此式与! i m 。c k 一0 矛盾，由此可得假设是不成立的，则定理4 2 的结论是正确的，即有： m i n f i i g 。8 - 0 一 4 4 数值实验 本节中，我们从【5 0 1 1 5 1 】中选取了一组标准的实验模型来检测算法 4 1 ( f i l t e r t r ) 对应的参数选择如下： = 1 0 。6 ， 叼= 0 7 5 ， c = 0 2 5 ， r11 以一m i n o 0 0 1 , # 寿 出于比较，我们也同时用传统的信赖域算法t t r 忡1 来求解 l二v 玎j 这组标准的实验模型实验结果如下表4 1 ，其中以，和行。分别表示实验中目标函 数及其梯度的迭代次数，c p u 表示实验所需时间，正表示算法4 1 得到目标函数 的最优值，a ( b ) 表示口x 1 0 6 表4 1f i l t e r t r 算法和t t r 算法数值实验结果 模型f 1 1 月e r t r t t r 名称 托 捍， 拧暑 c p u 1 玎，以g c p u e x t e n d e d r o1 0 02 92 9 1 3 ( - 1 )0 3 ( - 1 1 ) 3 92 1 6 ( - 2 )0 2 ( 3 ) s e s e n b r o n k p e n a l t yi 1 0 0 4 34 3 7 8 ( - 2 )0 9 ( - 5 ) 5 54 5 0 7 ( - 2 )0 9 ( 一5 ) t r i g o m o e t r i 1 0 03 13 l 0 1 ( - 2 ) 0 3 ( - 1 3 ) 3 12 30 1 ( - 2 ) 0 7 ( - 7 ) v a r i a b l y 1 0 02 82 8 0 6 ( - 3 )0 6 ( - 1 7 ) 2 8 2 8 0 3 ( - 3 )0 3 ( - 1 9 ) e x t e n d e d r o5 0 04 4 3 4 4 3 0 9 ( 0 )0 4 ( - 1 5 ) 4 02 0 7 ( - 3 )0 1 ( 2 ) s p e n a l t yi 5 0 03 53 5 0 1 ( - 1 )0 4 ( - 3 ) 4 44 0 0 1 ( 1 )0 4 ( - 2 ) t r i g o m o e t r i 5 0 03 33 3 0 3 ( o )0 1 ( - 6 ) 4 53 3 0 3 ( o ) 0 9 ( - 7 ) v a r i a b l y 5 0 03 73 7 0 1 ( o ) 0 8 ( 1 7 ) 3 63 6 0 1 ( 1 ) 0 2 ( - 1 1 ) 数值结果表明，对于e x t e n d e d 问题，t t r 算法效果不如我们的f i l t e r t r 算法，对于其他的问题，两个算法都得到了较好精度的结果总的来说，虽然对 于小规模的问题，f i l t e r t r 算法的计算效果不如t t r 算法，但对于大规模问 题，f i l t e r t r 相比t t r 算法的改进效果更加明显 第五章约束优化问题的非单调过滤器自适应信赖域 算法 前面几章我们给出了无约束优化问题的信赖域算法，本章将在前面介绍的非 单调思想、过滤器思想的基础上结合信赖域的基本框架，提出一类解决等式约束 优化问题的新算法 5 1 引言 考虑如下的等式约束问题 玎as,llt3：fxj)：-o，iee：，。，2，刀曙 ( 5 1 ) q ( ， = 仙2 ，肌一 r 一7 其中厂、q ：r 4 呻r 的二次连续可微的函数，e 是等式约束的指标集 文中记f ( 工) 一( c 1 ( z ) ，c ：( x ) ，q ( z ) y 和彳( z ) = ( ( 工) ，v c ：( 工) ，v 巳( z ) ) ，设 蟊阳；矽( x 厂g ( z ) ，其中矽( 工) 表示由4 ( z 厂的零子空间的一组基构成的矩阵 5 2 非单调过滤器信赖域算法 在第四章中介绍了，过滤器技术的基本思想，对于带约束条件的优化问题的过 滤器算法，两迭代点的优、次的比较原则和迭代点被过滤器接受的条件都不同于 无约束优化问题在本章中，定义| i l ( 工) = 0 c ( z ) d 显然j i l ( z ) 一。等价于x 是可行点 任意两点鼍、屯若满足 h ( x 1 ) ( x ：) 且厂( 毛) i ( x ：) ， 则称点鼍优于点屯，也称点屯次于点毛 在传统的约束优化问题过滤器算法中，被过滤器接受当且仅当对任意的 ( j l l ( 而) ，厂( 而) ) 巩。有 矗( ) 卢| l ( 而) 或 ，( ) s ，( 而) 一) ， ( ) ， 其中0 ， 1 不同于传统的信赖域过滤器的接受标准，采取结合非单调技术 的策略，我们称能被当前过滤器吼接受当且仅当对任意的( j l ( 而) ，厂( 而) ) 趼。有 i l l ( ) s 。小m 啡a x ) - 1 h ( 以一，) 或厂( ) s m a x 厂( 以) ，薹, k o ) f ( x k - j ) 一，j l ( ) ， ( 5 2 ) 其中os s 掰( 七) 一1 ，o o ，o x i ，o p o 使得8 反忙膨口 假设5 3 在q 内a ( x ) 、4 ( x ) r 彳( z ) 一、形( x ) 和( z ) r 形( x ) 。1 都是一致有界的 对于假设5 3 ，不妨假设对任意的k 分别存在m 一 o 、e o ，m 矽 o 、 厩 0 ，使钏钏s m ，x ) 丁彳( x ) 以0s 矿，1 1 哌1 1 s m ，l 暇哌。1 | | s 正类似前 面，在算法5 1 中步2 到步6 间的循环，称为外循环，步2 到步4 、步5 间的循 环统称为内循环d k ( p ) 表示在迭代点处第p 次内循环对应的试探步，此时的信 弛叭菰叭叫一 黑川小毗菰穆 示在迭代点黾处内循环结束时对应的试探步，z 是黾处内循环结束时z p 的值 引理5 1 若假设5 1 、5 2 、5 3 都成立则对任意的k ，都存在常量五 o 使得 i i n k i i s 酬q l | 证明： 由玎。定义可知 而i k + 畋忙i i c , i i ，故有 l i _ 陋( 鬈4 ) 。1 群畋0 一忆( 鬈4 ) 一c k + 群以一q ) 8 s 眦群4 ) t l ( 1 l c , + 彳仆o m i i n , i i s2 性( 4 ) 以l l i | c 。i i = , ，, l l c , i i 其中磊2 m 矿2 l b ( 4 ) d 8 ，因此引理5 1 的结论是成立的 引理5 2 若假设5 1 、5 2 、5 3 都成立则对任意的k ，分别存在常量晚 o 、 岛 o 使得 恢0 2 一i i c , + a 参h k 卜6 ：i i c k l t m i n h c 。峪。) ( 5 6 ) 和 ( n k ) 一铱( 畋) 6 ，膀v 依( 仇) 1 1 m i n 睃v 吼( 训，。) ( 5 7 ) 引理5 3 算法5 1 是适定的，即算法5 1 中步2 和步4 、步5 间的内循环有 限终l 卜 证明：假设在迭代点处算法5 1 中步2 和步4 、步5 间的内循环不有限终 止，即p 呻，则色( p ) - 0 下面我们将分两种情形说明： ( 1 ) 若 一o ，不失一般性，我们不妨假设存在毛 o 使得恢忙q o 算法5 1 中步2 和步5 问的循环不有限终止，由信赖域半径的变化机制可知：( ，) 呻o ， 于是存在吃 o 使得a k p ) 0 使得 j i l ( 以+ 吱( p ) ) s 6 3 ，( 耳) s 以o ，m ；。a ( x 。) - l ( 黾一) ) ( 5 1 0 ) 由式( 5 1 0 ) 和算法过滤器的接受机制( 5 2 ) 式可知- 五+ 噍( ，) 被过滤器接受因此 当。( p ) 充分小时，算法5 1 中步2 和步4 间的内循环终止 堕训篇 由 卜删磊p ，一p r 甜磊p “= ，( 坼) 一厂( + 噍。，) + 或。，+ 三攻r 晟，) s l l ( 三d 。p ，r ( 最一v 2 ，( + d 。，) ) 畋。，) l s 三8 反一v 2 厂( 砍+ 以。p ，) 4 。2 。p ， s m - “ 其中m 。是色和v 2 f ( x ) 的界的较大者，故当a 。- - , o 时有 1 l 。可l a r e d - p r e d ： s 篆乩 因此当a 。充分小时，p ，此时算法5 1 中步2 和步5 间的循环终止 ( 2 ) 若吃= 0 ，n ( 5 1 0 ) 式成立，根据算法5 1 中步2 和步4 间的循环条件已知， 步2 和步4 间的内循环有限终止下面说明步2 和步5 间的内循环有限终止 根据算法可知存在常数d i 4 o 使得g ( 以) 苫6 。，否则算法在步2 中就终止，所 以有 弦v 吼( ) h 瞻g 。+ b k n k ( p ) ) 6 一瞻| i _ | | 吆最9 ( 5 1 1 ) 之以一m w m 口a i ( p ) 而以一o 表明像( ，) = o ，结合( 5 7 ) 式可得 p r e d 磊，) 一铱( o ) 一铱( 畋( p ) ) 6 ，l ( 6 。一m m 丑色( p ) ) m i n p 。一m 嚣。( p ) i ，蜘) ) 当a k ( p ) 0 时有 r t ( p ) - 1 2 舒s 而瓦蒜睾一一o 同理可知此时算法5 1 中步2 和步5 间的循环终止 综上证明，算法5 1 是适定的且贝i jz 0 ，其中z 是故处内循环结束时z p 的 值 引理5 4 若假设5 1 、5 2 、5 3 都成立且算法产生无穷的迭代点列 x t ) ，则 憋魄= 0 证明： 算法产生无穷的迭代点列 x k ) 且没有终止于步2 ，则说明无穷 的迭代点列 黾) 进入到过滤器内，由过滤器的接受条件( 5 2 ) 式可知