（计算数学专业论文）非精确搜索下重新开始mfr共轭梯度法的收敛速度.pdf

t h e c o n v e r g e n c er a t eo f ar e s t a r tm f r c o n j u g a t eg r a d i e n tm e t h o d w i t hi n e x a c tl i n es e a r c h b y q ua i p i n g b e ( h u n a nu n i v e r s i t y ) 2 0 0 5 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fs c i e n c e l n c o m p u t a t i o n a lm a t h e m a t i c s i nt h e g r a d u a t es c h o o l 7 o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rl id o n g h u i d e c e m b e r ，2 0 1 0 川5 36洲709iiii_y 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 犀铂 日期硼蜊溯7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密嘶 ( 请在以上相应方框内打“ ) 作者签名： 导师签名：日日7月月 勿 莎 晖徉 如 期期日r：丌 _ _ 。一 非精确搜索下重新开始m f r 共轭梯度法的收敛速度 摘要 非线性共轭梯度法是求解最优化问题的一类有效算法，该算法的一个显著优点是其 存储量小，且具有较好的收敛性，因此广泛应用于求解大规模的最优化问题f r 算法 是最著名的非线性共轭梯度法之一众所周知，采用精确线性搜索的f r 共轭梯度法是 全局线性收敛的，如果使用某种重新开始策略，则其收敛速度将为刀步二次收敛近来， z h a n g ，z h o u 和l i 结合谱梯度的思想提出了的一种修正f r 算法( m f r 算法) ，并证明 了其在h r m i j o 型线性搜索下的全局收敛性本文研究h r m i j o 型非精确线性搜索下m f r 算法的收敛速度 第2 章，我们证明了m f r 算法在a r m i j o 型线性搜索下的线性收敛性第3 章， 我们证明了l i 和t i a n 提出的一种精确线性搜索步长估计满足a r m i j o 型非精确线性搜 索，并将其作为线搜索的初始步长来提高算法的效率我们将重新开始策略引入到m f r 算法中提出一种重新开始m f r 算法( r m f r 算法) ，我们证明在一定的条件下，这种 r m f r 算法具有全局收敛性，并证明采用a r m i j o 型非精确线性搜索时，此算法具有以步 二次收敛性 最后我们通过大量的数值试验检验本文提出的r m f r 算法的数值效果我们通过 求解大量的大规模问题，从算法的c p u 时间、函数计算次数和梯度计算次数三个方面 对r m f r 算法与和不采用重新开始策略的m f r 算法、m p r p 算法以及c g d e s c e n t 算法等进行比较结果表明本文提出的r m f r 算法具有明显的优势 关键字：无约束优化问题；f r ：m f r ；初始步长；重新开始方法；n 步二次收敛性 i i a b s t r a c t n o n l i n e a r c o n j u g a t eg r a d i e n t m e t h o d sa r ee f f i c i e n tf o r s o l v i n gu n c o n s t r a i n e d o p t i m i z a t i o n t h e ya r ep a r t i c u l a r l yw e l c o m ef o rt h es o l u t i o no fl a r g e s c a l ep r o b l e m sd u et o t h e i rl o w e rs t o r a g ea n dg o o dc o n v e r g e n c et h e o r y t h ef rm e t h o di sa v e r yf a m o u sc o n j u g a t e g r a d i e n tm e t h o d i ti sw e l l - k n o w nt h a tt l l ef rc o n j u g a t eg r a d i e n tm e t h o dw i t he x a c tl i n e s e a r c hi sg l o b a l l ya n dl i n e a r l yc o n v e r g e n t i fs o m er e s t a r t s t r a t e g yi su s e d ，t h ec o n v e r g e n c e r a t eo ft h em e t h o dc a nb en - s t e p 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 r e c e n t l y ，z h a n g 。 z h o ua n dl ip r o p o s e dam o d i f i e df r ( m f r ) m e t h o d a s s o c i a t e dw i t hs p e c t r a lg r a d i e n t i t w a sp r o v e dt h a tt h em f r m e t h o di sg l o b a l l yc o n v e r g e n ti fs o m ea r r n i j ot y p el i n es e a r c hi s u s e d t h ep u r p o s eo ft h i sp a p e ri st oi n v e s t i g a t et h ec o n v e r g e n c er a t eo ft h em f r m e t h o d w i t ha r m i j ot y p ei n e x a c tl i n es e a r c h i nc h a p t e r2 ，w es h o wt h a tt h em f rm e t h o dw i t ha r m i j ol i n e s e a r c hi sl i n e a r l v c o n v e r g e n t i nc h a p t e r3 ，w es h o wt h a tt h ee s t i m a t i o nt ot h ee x a c tl i n es e a r c hs t e p l e n g t h d e r i v e db yl ia n dt i a nc a l lb ea c c e p t e db yt h ea r m i j oi n e x a c tl i n es e a r c h w et h e nu s e i t2 l s t h ei n i t i a ls t e p l e n g t hi nt h ei n e x a c tl i n es e a r c hi no r d e r t oi m p r o v et h ee f f i c i e n c yo ft h em f r m e t h o d t oi m p r o v et h ec o n v e r g e n c er a t eo ft h em f r m e t h o d ，w ei n t r o d u c ear e s t a r ts t r a t e g y i nt h em f rm e t h o da n dp r o p o s ear e s t a r tm f r m e t h o d ( c a l l e dr m f rm e t h o d ) u n d e r a p p r o p r i a t ec o n d i t i o n s ，w es h o wt h a tt h er m f rm e t h o dw i t ha na r m i j ot y p ei n e x a c tl i n e s e a r c hi sg l o b a l l yc o n v e r g e n t m o r e o v e r , i t r e t a i n s 刀q u a d r a t i cc o n v e r g e n c ep r o p e r t y f i n a l l y ，w ed oe x t e n s i v en u m e r i c a le x p e r i m e n t st ot e s tt h ep e r f o r m a n c eo ft h ep r o p o s e d r m f rm e t h o d w ea l s oc o m p a r et h ep e r f o r m a n c eo ft h er m f rm e t h o dw i t ht h a to ft h e o r d i n a r ym f rm e t h o d ( w i t h o u tu s eo fr e s t a r ts t r a t e g y ) a n dc g d e s c e n tm e t h o d , e t c w e c o m p a r et h e mi nt h ec p ut i m eu s e d ，t h en u m b e ro ff u n c t i o ne v a l u a t i o n sa n dt h en u m b e ro f t h eg r a d i e n te v a l u a t i o n s t h er e s u l t ss h o wt h a tt h ep r o p o s e dr m f r m e t h o do u t p e r f o r m st h e o r d i n a r ym f rm e t h o d ，m p r pm e t h o da n dc g d e s c e n tm e t h o d k e yw o r d s ：u n c o n s t r a i n e d o p t i m i z a t i o n ；f r ；m f r ；i n i t i a l s t e p l e n g t h ；r e s t a i r t s c o n ju g a t eg r a d i e n tm e t h o d ；n s t e pq u a d r a t i cc o n v e r g e n c e i n 非精确搜索下莺新开始m f r 共轭梯度法的收敛速度 目录 学位论文原创性声明和学位论文版权使用授权书i 摘要i i a b s t r a c t i i i 插图索引一v 第1 章绪论1 1 1 非线性共轭梯度法及其收敛性1 1 2f r 算法的研究进展3 1 3 重新开始方法的研究进展4 1 4 本文的主要工作及各章节安排6 第2 章m f r 算法及其收敛性8 2 1 m f r 算法及其全局收敛性一8 2 2m f r 算法线性收敛性9 第3 章重新开始m f r 算法及其收敛性1 2 3 1r m f r 算法1 2 3 2r m f r 算法全局收敛性1 4 3 3r m f r 的n 步二次收敛性15 第4 章数值实验2 5 结论3 0 参考文献31 致 射3 5 i v 一 一 硕上学位论文 插图索引 图4 1 不同，值的r m f r 算法的c p u 计算时间2 6 图4 2 不同，值的r m f r 算法的函数计算次数2 6 图4 3 不同，值的r m f r 算法的梯度计算次数一2 7 图4 4 不同算法的c p u 计算时间一2 8 图4 5 不同算法的函数计算次数2 8 图4 6 不同算法的梯度计算次数一2 9 v 学位论文 第1 章绪论 1 1 非线性共轭梯度法及其收敛性 共轭梯度法具有算法简便，存储需求小等优点，十分适合于求解大规模优化问题， 考虑无约束优化问题【1 】 r a i n 厂( x ) ，x r ” ( 1 1 ) 这里f ：r ”一r 是连续可微函数，求解问题( 1 1 ) 的共轭梯度法具有如下形式： 稚+ l = + a k 以，( 1 2 ) 和 以：j _ 鲰， 拈0 ( 1 3 ) 【一鲰+ 成巩_ 1 ，k 1 其中a 七 0 是步长因子，g 。= v f ( ) ，成为某一参数 迭代格式( 1 2 ) 中的步长由某种线性搜索确定，常用的线性搜索分精确线性搜索 和非精确线性搜索两种 精确线性搜索确定的步长a 七使函数厂在直线+ a 以上达到最小，即a 七是下面的 一维最优化问题的解： f ( x k + 口k u k ) = m 口 i n uf ( x k + a 喀) 这种a t 也叫最优步长因子由于需要求一元函数的最小值，所以求精确步长需花 费相当大的工作量，因而花费计算量较少的非精确线性搜索受到了人们的亲睐 非精确线性搜索通常要求使得f ( x k + 以) 较f ( x k ) 有一定的下降量常用的非 精确线性搜索有以下几种： ( 1 ) a r m i j o 型线性搜索：给定5 ( 0 ，i 1 ) ，p ( o ，1 ) ，求口后= m a x p ，= o ，1 ，2 ， ， 二 满足条件 f ( x k + a k d k ) 一f ( x k ) 6 a 七以( 1 4 ) 在a r m i j o 型线性搜索中，如果p ( 0 ，1 ) 接近于1 ，则两次试探步的改变量相对较小， 此时，需要经过较多的搜索才能得到步长a 七，如果p ( o ，1 ) 接近于o ，则两次试探步的 改变量相对较大，此时，可经过相对较小的试探步得到步长a 七，但获得的步长a 七可能 很小 ( 2 ) w o l f e p o w e l l 型线性搜索【l 】：求a 后满足条件 非精确搜索下重新开始m f r 共轭梯度法的收敛速度 f ( x k + 伍k d k 、) 一f ( x k ) _ 5 a k 匹d k ， t g ( + a 七畋) 盯甑t 巩 其中0 5 仃 1 ，第一个不等式保证充分下降，第二个不等式防止步长过小 ( 3 ) 强w 6 l f e 线性搜索1 】：求满足条件 f ( x k + a 七巩) 一f ( x k ) 她t 畋， d g ( x 七+ d k ) l 仃i 以i 其中0 6 仃 1 ( 3 ) 推广的w o l f e 线性搜索：求a 七满足条件 ( 1 5 ) ( 1 6 ) ( 1 7 ) ( 1 8 ) f ( x k + a 七巩) 一f ( x k ) 5 a k 以， ( 1 9 ) 吼反吨碰g ( x k + o r 七以) 可2 巩( 1 1 0 ) 其中仃1 ( 0 ，1 ) ，仃2 0 ，当仃l - - 0 2 时，推广的w o l f e 线性搜索就是强w o l f e 线性搜 索 ( 4 ) g o l d s t e i n 线性搜索【1 】：求口t 满足条件： , s l 吒吨f ( x k + a 七丸) 一f ( x k ) 5 2 a k 噍， ( 1 1 1 ) 其中：0 5 2 圭 5 1 0 ，i ( o ，1 ) 使得当k 充分大时，序列 ) 满足 0 以+ 1 一x 幸0 6 ，i 。 ( 1 1 2 ) 1 2f r 算法的研究进展 这一节我们从全局收敛性和收敛速度的角度来介绍非线性共轭梯度法f r 算法的相 关研究进展 f r 算法由f l e t c h e r 和r e e v e s 于1 9 6 4 年提出的非线性共轭梯度法，它是求解无约 束优化问题( 1 1 ) 的第一个非线性共轭梯度法 关于f r 方法的收敛性研究取得了重大进展z o u t e n d i j k 证明了采取精确线性搜索 的f r 方法求解非凸无约束最优化问题时的全局收敛性【1 0 】由于精确线性搜索非常耗时， 难以实现，在实际应用中人们通常采用非精确线性搜索a i b a a l i 在1 9 8 5 年证明了如下 结论【1 1 】： 引理1 1 如果强w o l f e 线性搜索( 1 7 ) 和( 1 8 ) 下参数盯 0 并且证明了m f r 算法在线性搜索( 1 1 7 ) 下对非凸无约束优化 问题具有全局收敛性 虽然f r 算法具有全局收敛性。，但是它的数值试验结果并不理想，并且收敛速度很 慢p o w e l l 1 5 在精确线性搜索下分析了f r 方法可能连续产生小步长的性质，即如果 f r 方法在某一步产生很小的步长，则相继的许多步长也可能非常小，这说明f r 方法可 能收敛非常慢，也给出了f r 方法在实际数值计算中表现不好的理论解释m f r 算法一 定程度上解决了产生小步长的问题，但数值结果仍不尽满意 有关求解无约束优化问题的共轭梯度法的其他进展，可参考文献 1 6 3 3 】 1 3 重新开始方法的研究进展 这一节我们主要回顾重新开始共轭梯度法的研究进展 定理1 2 表明，采用精确线性搜索共轭梯度法具有线性收敛速度然而，当采用非 4 硕十学位论文 精确线性搜索时，已有的非线性共扼梯度法不能保证每一步都能产生下降方向，此时人 们一般用负梯度方向作为搜索方向，但是如果频繁的使用负梯度方向会导致收敛速度很 慢，所以人们常常采用重新开始策略如果共轭梯度法在每刀步沿负梯度方向作一次 重新开始，即令 叱+ l = 一+ l ，扛o ，1 ，2 ， 则从z o u t e n d i j k 条件可立即推出收敛关系式【9 】 l i m i n fi g k 10 = o - + o o i i 如果线搜索精确或渐进精确，c o h e n 和b u r m e i s t e r 证明了重新开始的共轭梯度法的 收敛速度可以从原来的线性收敛提高到超线性收敛甚至甩步二次收敛【3 4 1 并给出了如 下定理【3 5 】，并证明了，步重新开始的共轭梯度法具有玎步二次收敛，即 l i + 。一x 木i i = o ( 1 1 靠一x 枣0 2 ) ( 1 1 8 ) 其中x 木是目标函数的极小值点 定理1 3 设f ：r ”专r 是三次连续可微的一致凸函数，序列 是在精确线性搜索 下，采用，步重新开始的f r 或p r p 共轭梯度法产生则存在常数c 0 使得 l i m s u p 料g ， n 其中x 是厂的唯一极小点 可见重新开始的共轭梯度算法无论在全局收敛性还是收敛速度方面，都比原来的共 轭梯度法具有更好的性质然而这种重新开始策略具有以下一些缺点：一是舍弃了算法 沿前一次搜索方向喀一，搜索得到的二阶导数信息；二是重新开始的频率一般与目标函数 的性质有关，而不是简单地取为目标函数f ( x ) 的维数 p o w e l l 使用不同的频率对用最速下降方向作为重新开始方向作了数值试验，结果发 现函数的即刻下降量比不采用重新开始技术时函数的即刻下降量反而小【3 6 】为了充分利 用了算法沿方向以一1 已经得到的二阶导数信息，b e a l e 提出了一个重新开始搜索方向以 的三项方法【3 7 】，其吨具有如下形式： d k = 一g k + 成以一1 + ) ，七4 ，1 f ，) ，：= m 觚 ) ，i ，o ) ，( 1 2 5 ) 同时，对非重新开始的点列要测试充分下降性，在强w o l f e 型线性搜索下，他们给 出了算法对一般非凸函数全局收敛性d a i ，l i a o 和l i 基于b f g s 算法的迭代格式，给 出了两种新的重新开始的共轭梯度法，并且证明了算法的全局收敛性【4 1 1 “和t i a n 4 2 在m p r p 算法中提出的一种精确线性搜索步长估计作为a r m i j o 型 和w o l f e p o w e l l 型非精确线性搜索的初始步长，并且引入重新开始准则在此基 础上提出一种重新开始m p r p 算法( r m p r p 算法) 并证明在一定的条件下，采 用重新开始策略的m p r p 算法在a r m i j o 型和w o l f e p o w e l l 型非精确线性搜索 下具有”步二次收敛速度 1 4 本文的主要工作及各章节安排 由第3 节可知，f r 算法等著名的共轭梯度法在精确线性搜索下具有”步超线性收 敛性甚至玎步二次收敛性l i 和t i a n 证明在一定的条件下，采用重新开始策略的 m p r p 算法在a r m i j o 型和w o l f e p o w e l l 型非精确线性搜索下具有n 步二次收敛 速度【4 2 j ，迄今为止，尚未见其它著名共轭梯度算法采用非精确线性搜索时收敛速度 的研究研究采用非精确线性搜索时共轭梯度法的收敛速度的主要困难在于此时 算法不再具有二次终止性 6 硕上学位论文 近来，z h a n g ，z h o u 和l i 结合谱梯度的思想提出了的一种修正f r 算法( m f r 算法) ，并证明了其在a r m i j o 型线性搜索下的全局收敛性【l4 。本文在m f r 的基础上， 研究采用非精确线性搜索的m f r 法的收敛速度 全文各章节安排如下：第l 章，介绍非线性共轭梯度算法，重新开始方法等背景及 已有成果；第2 章，我们证明采用h r m i j o 型线性搜索的m f r 算法具有线性收敛速度第 3 章，我们证明了l i 和t i a n 提出的一种精确线性搜索步长估计满足a r m i j o 型非精确 线性搜索，并将其作为线搜索的初始步长来提高算法的效率我们将重新开始策略引入 到m f r 算法中提出一种重新开始m f r 算法( r m f r 算法) ，我们证明在一定的条件下， 这种r m f r 算法具有全局收敛性，并证明采用a r m i j o 型非精确线性搜索时，此算法具 有行步二次收敛性第4 章，我们通过大量的数值试验检验本文提出的r m f r 算法的 数值效果我们通过求解大量的大规模问题，从算法的c p u 时间、函数计算次数和梯 度计算次数三个方面对r m f r 算法与和不采用重新开始策略的m f r 算法、m p r p 算 法以及c g d e s c e n t 算法等进行比较结果表明本文提出的r m f r 算法具有明显的优 势 7 非精确搜索下重新开始m f r 共轭梯度泫的收敛速度 第2 章m f r 算法及其收敛性 本章，我们回顾m f r 算法及其全局收敛性，并证明采用a r m i j o 型非精确线 性搜索的m f r 算法具有线性收敛速度 2 1m f r 算法及其全局收敛性 众所周知，当f r 方法使用一般的非精确搜索如a r m i j o 搜索与w o l f e 搜索时， 由( 1 2 ) ( 1 3 ) 所产生的方向巩不一定是下降方向，基于这一点，z h a n g ，z h o u & l i 1 6 1 利用文献 4 3 】提出的在共轭梯度法中结合谱梯度的思想提出了f r 方法的一个修 正形式m f r ，其中搜索方向反的计算公式为： 畋= 汤屯，盛 亿， 其中 胪= 爵m 面d k t _ l y k _ l ，y k - 1 = g k - g k - r 1 4 】中采用下列的广义a r m i j o 线性搜索来计算步长 f ( x k + a 。喀) 0 由( 2 1 ) ( 2 2 ) 容易得出，喀是在毪处的下降方向，且满足 衫g k = - i i g 。| | 2 ， 而且该性质与算法所采用的线性搜索无关 首先我们给出如下的假设 假设a ( 1 ) 水平集q = x | 厂( x ) f ( x o ) ，x r 行) 有界 ( 2 2 ) ( 2 3 ) ( 2 4 ) ( 2 ) f ：r ”一r 是二次连续可微的一致凸函数，存在常数m m 满足 m t l l 2 d7 v 2 ( x ) d m0 d i l 2 ，溉，d r ”， ( 2 5 ) 其中v 2 f ( x ) 定义为厂在x 处的h e s s i a n 阵 下面的定理表明，在a r m i j o 型线性搜索下，m f r 算法具有全局收敛性，证 明详见文献 1 4 】 8 硕士学位论文 定理2 1 设假设1 和2 的条件成立，序列 x k ) 和 以 由a r m i j o 型线性搜索的 m f r 算法产生，则 ! 鲤i n f l = 0 2 2m f r 算法线| 生收敛性 本节，我们研究采用非精确线性搜索m f r 算法的线性收敛速度 从假设2 中很容易得到，问题( 1 1 ) 有唯一解x 幸且满足 ，m i i x - x * 1 1 2 厂( x ) 一厂( 矿) 丢m8 x - - x - 一1 1 2 , v x * r ”， ( 2 6 ) 并且 m i x x 木1 1 2 c ，v k 0 ( 2 8 ) 证明由( 2 3 ) 及假设2 ，有 和 所以 ( 一点仅。g 。t 畋+ 6 ：a 。2 1 2 ) 0 蚓1 2 = 一口。t 反 ok o 憋口。i 么1 1 = o 和l i m a t 蚓1 2 0 ( 2 1 2 ) 由( 2 1 ) 有 dk = 一e t g t + p ：r d k 4 ， 所以 i l a , 1 1 2 = 1 1 0 , 1 1 2i i g 。1 1 2 2 吼繇t p 。f r 喀一。+ i i 卢夕1 1 2 i i 喀一。0 2 9 l q c 5 。p - 1 a 。g 。t 以+ 6 ：p - 2 a 。2 l i 畋1 1 2 由微分中值定理，存在t k ( o ，1 ) 使得 ( + p 一1 a 女d k ) - - f ( x k ) = p l 口。g ；吨+ p l a 。( 夥( + p 一1 a 。以) 一g 。) r 畋 j d 一1 口。g 。t 以+ m p 之a 。20 吨1 1 2 ， 将最后一个不等式代入( 2 1 0 ) 得 口t m + 疋i l 以0 2 m + 疋 1 0 c 2 会一c ( 2 1 4 ) 硕上学位论文 令c = m i n c 2 , c 贝j j ( 2 8 ) 成立 下面的定理表明，在a r m i j o 型线性搜索下，m f r 算法具有线性收敛性 定理2 4 设假设l 和2 的条件成立，x 宰是无约束问题( 1 1 ) 的唯一解，则存在 常数a o ，( o ，1 ) ，使得在a r m i j o 型线性搜索下，由m f r 算法产生的点列 x k 满 足 l i x - - x 水1 1 2 ( 2 1 5 ) 证明由a r m i j o 型线性搜索( 2 5 ) 有 f ( x 。) - f ( x 幸) f ( x k ) - f ( x 木) + 反仅。g ；d k - 8 ：a 。2 i l 畋| 1 2 = ( ) 一( x 幸) 一4 口。u g , u 2 一。a 。2 oiig,。譬i。g。112 = f ( x k ) 川一磊a i 1 1 2 5 2 位毒蚶i i 厂( ) 一( 矿) 一点c m 2 i i x - x , 1 1 2 一疋嘉所z 1 - x * 1 1 2 锁铲弛卜磊c 鲁( 讹h ( ) 一晚等( 他h ( ) ( 1 一磊c 鲁一疋瓦2 c 2 m 矿2 ) ( 厂( 砟) 一m 切 令吲1 嘶等吨2 删c 2 m 2 ) ；，则 f ( x k ) 一f ( x 木) r 2 ( f ( x k 一。) 一f ( x 水) ) l , , 2 k ( f ( x o ) - f ( x 母) ) 结合( 2 7 ) 有 i i x - x * l 2 。2 历( f ( x k ) 一m 宰) ) 0 ，( 2 15 ) 成立，从而证明了m f r 算法的线性收敛性 非精确搜索下重新开始m f r 共轭梯度法的收敛速度 第3 章重新开始m f r 算法及其收敛性 本章我们将重新开始策略引入到m f r 算法中提出一种重新开始m f r 算法， 简记为r m f r 算法，我们证明在一定的条件下，这种r m f r 算法具有全局收敛性， 并证明采用a r m i j o 型非精确线性搜索时，此算法具有刀步二次收敛性 3 1m r 算法 前面我们探讨了m f r 算法的线性收敛性，由于采用精确线性搜索时，m f r 将退化为f r 算法，而文献【4 4 】证明了采用重新开始策略的f r 算法在一定条件下 时以步二次收敛，本节我们将重新开始策略引入m f r 算法中提出一种重新开始 m f r 算法，简记为r m f r 算法n o c e d a l 曾指出，如果能够设计一种自调比的初 始步长策略，则f r 方法和p r p 方法或它们的变种方法的有效性将大大提高为 了提高算法的收敛速度，我们采用精确线性搜索的某种近似作为非精确搜索的开 始步长，若该步长可以被接受，则算法可以被视为某种近似f r 算法，因此，可 望得到该算法的胛步二次收敛性 设a t 是精确线性搜索步长，则 i i g 。i f 2 = 一繇t 以= ( g ( k + 云t 以) 一) r 畋= 云t 彩石t 畋， 们有 其中否t = f v 2 f ( x k + f 瓦d 。) d r ，则可得精确线性搜索步长夏t 的如下近似关系 碓艋丽 b ， 其中吼是一个充分小的常数，如果f 是二次函数，则珞退化为a t ，一般地我 陟l _ i 魁一 一i 衫( g ( 吒+ 毛喀) 一g , ) l g 。1 1 2 一t - - u t 以靠i k 。1 1 2 ：= ：i 。= = = ? 。- ：二_ ig 女矾( g ( x k + 艮以) 一致) 端恬川2 1 2 硕士学位论文 下面的引理给出r k 的一个上界 定理3 1 假设1 和2 的条件成立，序列 x k ) 由g r m i j o 型线性搜索的m f r 算 产生，那么，当k 充分大时，r k 满足a r m i j o 型线性搜索 证明 g ( x k + & 吨) 一g ( ) = f v 2 f ( x k + 和。反) d 毒气以， 且 胪丽捌表面 令 耷= f v 2 f ( x k + 乒。d k ) d 考， 所以 轳牲器鲁 2 ， 由( 2 1 3 ) 式，我们得到 反 专0 ，因此，我们有 f ( x k + r k d k ) = f ( x k ) + r k g r d k + 去彰瓦畋+ 4 0 ( 1 l d 。1 1 2 ) = ( 砟) + r 。t 以一i 1 住g 。t 反+ 4 0 0 i d y l l 2 ) = f ( x k ) + i 1 g 。t 以+ 4 0 ( 1 l d 。1 1 2 ) = 厂( ) + 仃，吒g 。t 矾一砖一仃，) 咯8 9 。8 2 + 4 0 0 1 d 。1 1 2 ) = ( 以) + 口。t 喀一砖一仃。) c 21 1 矾1 1 2 + 4 0 ( 1 l d , 1 1 2 ) 0 选定初始点而r ” 1 3 非精确搜索下重新开始m f r 共轭梯度法的收敛速度 步1 ：令k ：= 0 ，g o = g ( x o ) 步2 ：如果i i g 。忙g ，则停止，否则令d o = 一g 。 步3 ：如果kj 满足 f ( x k + k l 矾) f ( x k ) + c r ，k i g ；d , ， 选择= k i ，否则按下面的a r m i j o 型线性搜索公式计算步长a 七：即求 = m a x i r 。i p j , = o ，1 ，2 ，) 使得其满足 f ( x k + a i 矾) f ( x k ) + 仃1 a i 或畋( 3 3 ) 步4 ：令x k + l = x k + a 女以，k ：= k + l ，计算g k = g ( x k ) 步5 - 如果l i g 8 s ，则停止，否则转步6 步6 ：如果k = ，令x o ：= & ，转步1 步7 ：计算 y k - 。= g k - g k - 1 , 肛持m 爵， d k = 一e k g k + p ：r d k - 1 转步3 3 2r m f r 算法全局收敛性 本节，我们建立r m f r 算法的全局收敛性定理 定理3 3 假设条件1 和2 成立，点列 砟) 由r m f r 算法产生，则 l i m i n ft g 。i l = 0 (34)k-，*o “ 、 证明利用反证法，假设定理不成立，那么存在常数s 0 ，满足 i i g 。i | 占，v k o ( 3 5 ) 由( 2 11 ) 知 一a 。g ；吨 哦p _ 1 a 七g ：吒 ( 3 7 ) 由中值定理，存在常数( o ，1 ) 满足 f ( x k , + p 。1 a 南噍) 一厂( ) = j d 。a t 噍+ p _ 吒( 夥( 屯+ k p a 向d k , ) - g 毛) 7 吒 p a 鼻g ：d k , + m p 。2 a 屯2 1 2 ， 结合( 3 7 ) 式，则砖充分大时，我们得到 蚓1 2 而m a 驯1 2 由假设2 知道，存在正数y 1 0 ，满足 l i g ( x ) l i y 1 ( 3 8 ) 结合( 2 1 3 ) 我们知道噍有上界，则熙1 n f i | 鼠0 = 0 ，与( 3 4 ) 矛盾，所以定理为 真 3 3r m f r 的n 步二次收敛性 上一节我们将重新开始策略引入m f r 算法提出了r m f r 算法，并且证明了在一定 条件下r m f r 算法的全局收敛性，在r m f r 算法中，我们使用精确线性搜索的某种 近似作为非精确搜索的开始步长，并证明该步长满足a r m i j o 线性搜索，所以r m f r 算法可以被视为某种近似f r 算法，本节我们证明r m f