（基础数学专业论文）一类与dy方法有关的共轭梯度法的收敛性研究.pdf

大连理工大学硕士学位论文 摘要 f ( x k + 口女喀) 一f ( x k ) n l a x 缸i g 女t 吨，一p a ；0 吨0 2 ) g ( x i + 口i a k ) r d k 一2 以tl l a t | 1 2 其中，0 6 仃 1 ，0 p 仃 1 并证明了在这种新型线搜索下d y 方法的全局收敛性 第三部分，在d y 方法的基础上，我们提出了一个新的屏公式： 8 竺：二龆型 n 一l ( g 女一g k 1 ) 反：一- z i i g l l 4 , ) 胪= 毪薄一 卢七n 。s + = m a x 0 ，纸n h s ) 其中：a ( o ，1 ) ，0 7 1 l - 2 0 a f 2 g l o b a lc o n v e r g e n c eu n d e rt h en e wl i n e a rs e a r c ho fd yc o n j u g a t eg r a d i e n tm e t h o d i nc h a p t e ri i i ，w i t hd ym e t h o da st h ef o u n d a t i o n ，w ep u tf o r w a r da n e w | b kf o r m u l a ： 肛等磐 i n t r o d u c i n gr e l a t e dp a r a m e t e r s ，w ec a l lf i n a l l ya t t a i nt h eac l a s sc o n j u g m eg r a d i e n t 8 g r ( g _ a , 慨i i g , 一。i i 。a 反= ( a + 1 ) d 主- i ( g 虬, - g k q ) ( a 0 ，1 】) i h ef o r m u l ap r o v e sa g l o b a lc o n v e r g e n c ei nt h i sm e t h o du n d e rw o l f el i n e a rs e a r c h i nc h a p t e ri v ，w ec o m b i n eh sc o n j u g a t eg r a d i e n tm e t h o dw i t hd yc o n j u g a t eg r a d i e n t m e t h o dt of o r m u l a t eam i x e dc o n j u g a t eg r a d i e n tm e t h o da sf o l l o w ： 疗朋他1 2 + ( 1 一a ) ( 酬1 2 i g ；g 。一1 ) m “2g r d k 一。| + 1 ( g t g k - i ) l i i 大连理工大学硕士学位论文 段n 4 5 + m a x 0 ，卢七n h s ) ( a ( o ，1 ) o u 2 悯) t h i sm e t h o di si n d e p e n d e n to fa n yl i n e a rs e a r c ht op r o d u c eas u f f i c i e n td e s c e n d e n t d i r e c t i o n ，a n dc a na l s oa c h i e v eag l o b a lc o n v e r g e n c eu n d e raw e a kc o n d i t i o n k e yw o r d s ：u n c o n s t r a i n e do p t i m i z a t i o n ；c o n j u g a t eg r a d i e n tm e t h o d ；l i n e a rs e a r c h ；d e s c e n t d i r e c t i o n ；g l o b a lc o n v e r g e n c e i i i - 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 作者签名： 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：二娄鱼旦y 左洼查去鲍基堑搓度洼鲍监敛性珏究 作者签名： 支童鲜日期：立堕缸年j 旦月j 日 导师签名：名。：幺 大连理工大学硕士学位论文 1绪论 1 1引言 最优化理论与方法是一门十分活跃的年轻学科，它讨论决策问题的最佳选择之特 性，构造寻求最优解的计算方法，研究这些计算方法的理论性质及实际计算表现。随着 高新技术、计算机及信息技术的飞速发展，最优化理论与方法越来越重要，它已广泛应 用于自然科学，社会科学，生产实践，工程设计和现代化管理等方面。 共轭梯度法是最优化中最常用的方法之一。在所有需要计算导数的优化方法中，最 速下降法是最简单的，但它收敛速度太慢。拟牛顿方法收敛速度很快，被广泛认为是非 线性规划的最有效的方法。但拟牛顿法需要存储矩阵以及通过求解线性方程组来计算搜 索方向，这对于求解大规模问题几乎是不大可能办到的。共轭梯度法能将一个刀维的优 化问题转化为等价的船个一维问题，算法简便，存储量需求小，收敛速度又比最速下降 法快，特别适合求解大规模问题。如电力分配、石油勘探、大气模拟、航天航空等提出 来的优化问题。因而研究共轭梯度法具有很强的应用背景。 共轭梯度法最早是由数学家h e s t e n e s s t i e f e l 瞳1 在2 0 世纪5 0 年代初为求解线性 方程组 a x = b ，x r 刀( 1 1 1 ) 而提出的，他们合作的著名文章口3 被认为是共轭梯度法的奠基工作。该文章详细讨论了 求解线性方程组的共轭梯度法的性质及它与其他方法的关系。当么为对称正定矩阵时， 线性方程组( 1 1 1 ) 等价于最优化问题： r a i n - 】工r 彳工一6 r 工 i e 妒2 x | 出。l x ( 1 1 2 ) 因此，h e s t e n e s 、和s t i e f e l 的方法也可视为求二次函数极小值的共轭梯度法。1 9 6 4 年f l e t c h e r 和r e e v e s 将此方法推广到非线性优化，得到了求一般函数极小值的共轭梯 度法。随后，b e a l e ，f l e t c h e r ，p o w e l l 等学者对非线性共轭梯度法进行了深入的研究， 给出了非线性共轭梯度法收敛性分析的早期成果近年来，国内外的众多学者在非线性 共轭梯度法的收敛性方面作了大量的工作，得到了不少新鲜的结果h 。1 们。但共轭梯度法 的理论和应用还有待于进一步地开拓与完善。 1 2 共轭梯度法一般形式及公式 对于无约束优化问题： 一类与d y 方法有关的共轭梯度法的收敛性研究 m i n f ( x ) j e r “ ( 1 2 1 ) 我们通常是用迭代法来逐步产生它的最优解。其基本思想是给出一个初始点x 1 r ”，按 照一定的准则产生一个点列而，毛，使当吃，而，是有限点列时，其最后一点是最优化 问题的最优解：当x ：，b ，是无穷点列时，它有极限点，且其极限点是最优化问题的最优 解。 在线搜索型的方法中，第k 次迭代从当前点耳产生一搜索方向d k r ”，下一迭代点 为： 坼+ l = + 畋 ( 1 2 2 ) 一般要求以是下降方向，即衫v ( 屯) 0 ：而口。是由某种线搜索得到的步长。线搜 索可以分为精确线搜索和非精确线搜索两大类。精确线搜索的思想是：我们期望在迭代 过程中从五点出发得到一个好的点作为下一个迭代点，也即使得函数值下降量最大， 显然，最好的点是使得函数值达到最小的点，即要求： f ( x k + 吼巩) 2 咖厂( 以+ a d k ) ( 1 2 3 ) 这就是所谓的精确线搜索。由于精确线搜索要求一个单变量函数的极小值，计算量较大， 所以在实际计算中常常用到非精确线搜索。典型的非精确线搜索是w o l f e 线搜索，它要 求步长因子吼满足以下条件： f ( x k + 畋) - f ( x k ) + s a t 酊巩 ( 1 2 4 ) g ( x k + 以) 7 。以仃繇t 反 ( 1 2 5 ) 其中，0 6 a 1 。 若( 1 2 5 ) 式变为： i g ( 吒q - a 。反) r 以l 仃l 配巩l ( 1 2 6 ) 则( 1 2 4 ) 和( 1 2 6 ) 称为强w o l f e 线搜索。 若( 1 2 5 ) 式变为： 仃1 9 r i d k g ( x k + a 反) r 反可2 彩吨 ( 1 2 7 ) 其中，6 仃l 1 ，仃2 ( 0 ，o 。) ，则( 1 2 4 ) 和( 1 2 7 ) 称为广义w o l f e 线搜索准则。 文献n 妇给出了一种新的宽松的w o l f e - 型线搜索： 大连理工大学硕士学位论文 f ( x k + o t d i ) - f ( x ) ：；- p o t ；l i d t l l 2 ( 1 2 8 ) g ( x k + a 女畋) r 矾一2 d 口女l i d y l l 2 ( 1 2 9 ) 其中，0 p 仃 1 。 结合w o l f e 线搜索和文献n q 的w o l f e 一型线搜索，本文第二章给出一种新的w o l f e 一型 线搜索： f ( x k + o t t 矾) 一f ( x k ) _ m a x s a 女g ；反，- p h ；l i d , 1 1 2 ( 1 2 1 0 ) g ( x k + 口巩) 7 巩- 2 x r o t i 慨1 1 2 ( 1 2 1 1 ) 其中，0 艿 仃 1 ，0 p 叮 1 。 a r m i j o 线搜索准则：选取口。= a ”，其中聊为使得下式成立的最小非负整数。 f ( x k + o t d k ) - f ( x ) s o t 繇t 矾 ( 1 2 1 2 ) 其中九( 0 ，1 ) ，6 ( o ，1 ) 。 共轭梯度法是一种基于共轭方向的算法。下面先引入共轭方向的概念。 定义1 2 1 设a 是，2 ，2 对称正定矩阵，若盔，d 2 ，畋是尺甩中的足个方向，它们 满足： d r a d j = 0 ，f 歹，f ，歹= l ，2 ，k ( 1 2 1 3 ) 则称这k 个方向关于彳共轭，或称它们为么的k 个共轭方向。 在定义1 2 1 中，如果彳为单位矩阵，则k 个方向关于a 共轭等价于k 个方向正交。 因此共轭是正交概念的推广。共轭方向的一个重要性质是：对于二次凸函数，若沿一组 共轭方向进行精确线搜索，经有限步迭代必达到极小点。通常，将经过有限次迭代可以 求得凸二次函数精确解的算法称为具有二次终止性的算法。 共轭梯度法的基本思想是把共轭性与最速下降方法相结合，利用已知点处的梯度构 造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。根据共轭方向的基 本性质，这种方向具有二次终止性。 用共轭梯度法求解上述问题( 1 2 1 ) 的最优解，其搜索方向d 。是负梯度方向与上一 次迭代的搜索方向的线性组合，它的迭代公式为： 反= 二耋。 ( 七= 1 ) ( 1 2 1 4 ) ( 尼2 ) 一类与d y 方法有关的共轭梯度法的收敛性研究 计算矾的关键在于展的取法，不同的展对应不同的非线性共轭梯度法。 1 3常用的共轭梯度法 最早的非线性共轭梯度法f r 方法是由f l e t c h e r 和r e e v e s n 3 在1 9 6 4 年将求解线性 方程组的共轭梯度法推广用于求解优化问题( 1 2 1 ) 而得到的，其参数反的公式为： 胪= 丽i g 女1 1 2 ( 1 2 1 5 ) f r 方法具有很好的全局收敛性，n 纠们但有时数值表现不是很好n 6 1 。 由p o l a k r i b i e n 印和p o l y a k n 7 1 在1 9 6 9 年分别独立提出的p r p 方法，其参数反公式 为： 酽。毪掣( i 2 1 6 ， p r p 方法是目前认为数值表现最好的共轭梯度法之一，其原因是当算法产生一个小的步 长时，由p r p 方法定义的搜索方向自动靠近负梯度方向，从而较为有效地避免了f r 方 法可能产生连续小步长的缺点，因而具有很好的数值表现，但得到的全局收敛性结论不 是很好n 5 1 。 由h e s t e n s 、，s t i e f e l b l 提出的h s 方法，其参数反公式为： 胪= 躺 ( 1 2 1 7 ) 它的一个重要性质是共轭关系式( 一g k - i ) = o 不论线搜索是否精确总是成立的，它 的理论性质和计算表现都与p r p 方法类似。 与h s 方法具有相似性质的是由l i u 和s t o r e y n 8 3 在1 9 9 1 年提出l s 方法，其参数佤公 式为： ：一亟掣 q 2 1 8 ) 由f l e t c h e r n 钔在1 9 8 7 年提出的c d 方法，其参数反公式为： 酽= 一簏t ( 1 2 1 9 ) 一4 一 大连理工大学硕士学位论文 c d 方法的一个重要特点是只要强w o l f e 线搜索准则中的参数仃 1 ，则c d 方法在每次 迭代均产生一个下降搜索方向，而此时f r 方法和p r p 方法即使对一致凸函数都有可能 产生一个上升搜索方向n 3 矧。不过c d 方法的收敛性质并不好，并且当线搜索精确时， 酽= 胪，因此c d 方法有着和f r 方法同样的数值缺点，即可能连续产生许多小步长。 由d a i 和y u a n 晴1 提出的d y 方法是一种具有良好收敛性和数值结果的共轭梯度法， 其参数口。公式为： 钟72 琢i 万l g k l l 孬 1 2 2 。) d y 共轭梯度法在对目标函数假设较弱的条件下，不使用强w o l f e 线搜索，而使用w o l f e 线搜索便可以得到很好的收敛结果。详见文献嵋1 ，而且不使用任何线搜索条件便具有良好 的内在性质，详见文献乜。 本文第三章在d y 方法的基础上，提出了一个新的反公式： 。如。一黔“， 旷2 1 嚣 并引进参数，得到一簇共轭梯度法： r 出一始 反2 而丽彘 ( 1 2 2 1 ) ( 1 2 2 2 ) 其中a o ，1 】，并在w o l f e 线搜索下证明了该方法的全局收敛性。 1 4 混合型共轭梯度法 由上一节对几种常用的共轭梯度法的介绍，我们知道不同的共轭梯度法其全局收敛 性和数值表现大不相同。为了结合这些方法的优点，学者们提出了各种混合型算法。比 如说，p r p 方法是数值表现最好的非线性共轭梯度法之一，但即使采用精确线搜索也不 一定收敛；另一方面，虽然f r 方法在计算中并不是十分有效，但其全局收敛性质却很 好。为了结合这两种方法的优点，t o u a t i a h m e d 和s t o r e y 口3 在1 9 9 0 年首次引入了杂交 共轭梯度法，并考虑了f r 方法和p r p 方法的如下杂交方法： 鼠= m a x o ，m i n f l f e u ，卢) ) ( 1 4 1 ) 一类与d y 方法有关的共轭梯度法的收敛性研究 这种杂交方法确实可以避免f r 方法可能连续产生小步长的缺点，并且具有类似f r 方法 的全局收敛性。g i l b e r t 和n o c e d a l 哺1 进一步研究了杂交方法： 3 , = m a x 一胪，m i n 矿，胪) ) ( 1 4 2 ) 杂交方法( 1 4 1 ) 比( 1 4 2 ) 好的一处是，它允许参数口。取负值。上述两种方法的数值 表现虽然比f r 方法好一些，但仍比p r p 方法差得多。类似地，考虑到h s 方法数值表现 较好，而d y 方法收敛性质比较好，d a i 和y u a n 畸1 提出了d y 方法和h s 方法的如下杂交形 式： 成= m a x o ，i 血 胪，雕y ) ) ( 1 4 3 ) 相对于f r 方法和p r p 方法的杂交共轭梯度法( 1 4 1 ) 或( 1 4 2 ) j 杂交共轭梯度法( 1 4 3 ) 的优点在于：它不要求线搜索满足强w o l f e 条件，而只需线搜索满足w o l f e 条件就可以 得到全局收敛的结论。大量的数值试验表明在w o l f e 线搜索下这种杂交方法要优于在强 w o l f e 线搜索下的p r p 方法。 除了形如式( 1 4 1 ) 一( 1 4 3 ) 的杂交共轭梯度法，学者们还尝试了利用不同形式的 参数口。构造混和型共轭梯度法。比如n a z a r e t h 幢列，结合f r 方法、p r p 方法、h s 方法和 d y 方法，给出了如下带有两个参数的共轭梯度法簇： r 一剑剑：! ! 二丝堕亟二坠2 ( 1 4 4 ) 心恢耵+ ( 1 一心) ，( 既一g k - i ) 其中九， o ，1 为参数。d a i 和y u a n 3 基于1 3 节中提到的六种常用的共轭梯度法， 提出了如下三参数共轭梯度法簇： 反= 而高等麓紫亿4 5 ) 其中九， o ，1 】与q 【o ，1 一u i 】为参数。与许多不同的拟牛顿法可以用统一的拟牛 顿法簇形式表示( 如d f p 拟牛顿法和b f g s 拟牛顿法可以用b r o y d e n 簇拟牛顿法表示相类 似，这种三参数共轭梯度法簇可看成是f r 方法、p r p 方法、h s 方法、c d 方法、d y 方法 以及l s 方法等六种共轭梯度法的某种凸组合，它既包含双参数共轭梯度法簇( 1 4 4 ) ， 也包含杂交共轭梯度法( 1 4 1 ) 和( 1 4 2 ) 。但在实际计算中，如何选取九等参数以获得 满意的数值结果还是一个有待深入的问题。 大连理工大学硕士学位论文 为了得到一种在w o l f e 线搜索下保证搜索方向满足下降性的共轭梯度法簇，d a i 于 2 0 0 3 年在文献晗钔中结合杂交共轭梯度法，提出了一种三参数杂交共轭梯度法簇，它的形 式如下： p ，= 坚堕坐堡鱼型：剑剑丝一一 ( 1 4 6 ) 8 ( f 七+ 咄) 巩一1 + “t0 9 七一l i l 2 + ( 1 一“七) ( 一d 三，g 一。) 其中 o ，1 ，魄 0 ，1 - u k 】以及吒【1 ，悯) 为参数。 注意到，当 q = 1 ，“k = o ，q = 0 时，上式等价于式( 1 4 3 ) 。这种共轭梯度法簇可以避免连续产生小 步长，并且在w o l f e 线搜索下就可以达到全局收敛。 本文第四章结合h s 方法、d y 方法，给出了一个杂交的共轭梯度法公式： 酽= 糍杀雠掣 m4 7 ， 卢芦+ = 麟 o ，p 尸) ( 1 4 8 ) 其中：允( o ，1 ) ，0 吃 佃 此方法不依赖于任何线搜索便可以产生一个充分下降方向，且在较弱的条件下便可 一类与d y 方法有关的共轭梯度法的收敛性研究 2 一种w o ir e - 型线搜索下d y 共轭梯度法的全局收敛性 本苹对一种w o l f e 一型线搜累条件f 的d y 非线性共轭梯度法进行了研冗，结合这一 新型线搜索条件和d y 非线性共轭梯度法的方向计算公式提出了一个求解非线性无约束 优化问题的新算法，搜索方向为下降方向时，给出了算法的全局收敛性结果及其证明。 2 1引言 考虑如下无约束优化问题： m i n f ( x ) l x r ” 其中：f ：r ”一r 是连续可微函数，求解这一问题的标准共轭梯度法的迭代形式为： 坼+ l = x k + 口以 ( 2 1 i ) 畋= 二茎：+ 卢。以一。 乏三 c 2 2 ， 而是初始点，繇为厂( 石) 在点t 的梯度向量，反是搜索方向，是由线搜索或由特 定的公式计算出的步长因子。常用的线搜索有精确线搜索，a r m i j o 线搜索，w o l f e 线搜 索等。展为标量，其标准的计算公式有： 盼= 热 雕懈2 气挚 r 册一氲! 鱼二= 】2 耽一1 ( g t g _ 1 ) = d , r - i ( 蛙g k - - g k - ! ) d a i 和y u a n 在文献 1 1 中利用了w o l f e 线搜索，证明了d y 方法的全局收敛性。文 献 4 给出了如下一种宽松的线搜索，并证明了其是可行的。 厂( k + 口。畋) 一f ( x 。) 一p a ；i i 以1 1 2 ( 2 1 3 ) 大连理工大学硕士学位论文 g ( x 。+ a 。巩) r 以_ 2 锨。i i d y l l 2 ( 2 1 4 ) 其中0 p 仃 1 。 本文将这一宽松的线搜索换成： 厂( + a i a r k ) - f ( x k ) m a x 6 a g ；反，一p 口；l i 以1 1 2 ( 2 1 5 ) g ( x k + 口女反) r d k - 2 0 - a 0 d k l l 2 ( 2 1 6 ) 其中，0 6 仃 1 ，0 p 仃 0 ，k ：= 1 ； s t e p2 ：若i k i i 0 ，使： l i g ( x ) - g ( y ) li x y l i ，坛，y eu 引理2 3 1 若假设条件( h t ) 、( h ：) 成立，f ( x ) 为r ”上的严格凸函数，则d y 方法产 生的搜索方向为下降方向，即对v 七= l ，2 ，都有g ；d k 0 。 证明：用数学归纳法 当, = 1 时，西= 一g l ，有g j 碣；一l l g l0 2 o 成立。 一类与d y 方法有关的共轭梯度法的收敛性研究 假设n =k 一1 时有豇，矾一l o ， 又因为口 0 ， 于是有： 故砭1 ( 甑一g k - 1 ) o ， 酊瓯= ( 一+ 展矾一。) = 一慨0 2 + 厦g ；反一。 = 一1 2 + 。( 一& 一，) = 琢；i g 雨k 2 o 口k f - i 一反一， 一1 ( g 一g 一1 ) 叫 0 g ；畋一， 所以对于刀= k 的情况定理也成立。 引理2 3 2 若假设( h - ) ( h 。) 成立，考虑一般方法五+ 。= 毛+ a 。以，其中也是下降方 向，由线搜索( 2 1 5 ) ( 2 1 6 ) 得到，则有 k - i鳟 2 一 证明： 由引理2 3 1 得g ：巩 o ，所以 厂( 孔) ) 为单调下降有界数列。 令： m = 瓴g ；以 一p a 淞nke 1 ，2 ，) 由( 2 1 6 ) 得： = k 1 6 a 。繇t 以一p 吒2o 以1 1 2 一1 0 一 ke 1 ，2 ，2 ) ( 2 3 1 ) 大连理工大学硕士学位论文 ( g 女+ 1 一g k ) 7 反- 2 0 a 0 以一g ：破 ( 2 3 2 ) 由假设( h ：) 得： ( 鼬一g k ) r d k - 0 ，使l i 0 2 c ，v k 1 ，2 ，) ，由( 2 1 2 ) 和d y 公式 得： 吱d k = 羲卜g k + 9 p d 。 = 一i i g 。1 1 2 + j 夏_ 忑i i 五g k 丽l 2 g ；巩一。 一类与d y 方法有关的共轭梯度法的收敛性研究 即 = 砾i i g k 2 孬o 口k ，- i 矾一。一l ( g 一g i 1 ) 叫 酽= 焘一1 口女一l 将( 2 1 2 ) 写成： 吨+ = 将( 2 3 9 ) 式两边分别平方后得： | b k d t - 、 蚓1 2 = 所忆；卜2 9 r d k i g 。0 2 = 、9 9 2 r ，以d k ：2i i 以一。1 1 ：- 2 9 ；巩一0 9 r0 2 将( 2 3 z o ) 式两边同除以( g 。t 以) 2 后得： 川1 2 ( 甑t 以) 2 又k = 1 时，有 1 2 ( g j 吐) 2 将( 2 3 1 1 ) 式依次递推得： j 2 ( 吐) 2 g t k d k i g 2 ( 繇t 以) 2 一喃+ 糕n 奇 1 j g kl l z 。 龆rd 2 9 l + 、 j一j ， 0 9 h i l 2 一1 2 一 ( 2 3 8 ) ( 2 3 9 ) ( 2 3 1 0 ) ( 2 3 1 1 ) 黔 一户拦 上蚶撼 一l 蚶 i i 虹蚶 = 酽矛型 = 一户螳 一口，邙石慨西一( 一 上蚶 + 大连理工大学硕士学位论文 v 上 一铡郇 由假设可知： 喜卉 因此臀昙 所以喜臀= 一类与d y 方法有关的共轭梯度法的收敛性研究 3w olf e 线搜索下一簇共轭梯度法的全局收敛性 本章给出了一个新的共轭梯度公式，并给出了新公式的有关性质。在新公式的基础 上进一步提出了一簇共轭梯度算法，这一簇算法包含了d y 方法，新算法在w o l f e 线搜索 下产生一个下降方向，并证明了算法的全局收敛性。 3 1引言 对于下面无约束优化问题： 其中：f ：r ”一r 是连续可微函数，我们仍考虑一般的共轭梯度法算法： + 1 = + a 女反 巩= 二喜：+ 鼠以一， 妻茎 其中鼠为参数，步长因子吼满足w o l f e 线搜索准则： 魄+ a 女d k ) - f ( x i ) 施g f d , g ( x k + 仅k d k 丫d k 芝a g t k d k 其中，0 6 d 1 。 常用的成的计算公式有： 盼= 热 叫2 瞥 b 嬲：曼：( 星二星 j ! n 一l ( g t g i 一)一l 【g t i _ 1 ) 卯7 = 丽i i g t l l 2 ( 3 1 1 ) ( 3 1 2 ) ( 3 1 3 ) ( 3 1 4 ) 大连理工大学硕士学位论文 r 一一g r ( g k 慨 g k 一。l l 。d , _ , ) 雕纠2 1 意等丁 在精确线搜索下，新公式即为卢，下面我们给出新公式的两个性质。 ( 3 1 5 ) 性质3 1 1 考虑方法( 3 1 1 ) 一( 3 1 2 ) ，步长因子a i 满足w o l f e 线搜索准则( 3 1 3 ) 和( 3 1 4 ) ，成= 矿，则对v 尼1 ，有爵吃 o 成立。 证明： 当k = l 时，g j 嘎= 一慨0 2 o 假设对k 一1 的情况有吐。咴一。 0 成立。 由( 3 1 2 ) 有： g ：吨= g ；( 一g 。+ 反巩一。) 由( 3 1 4 ) 得 川i g , i i + 骥以。 一2 + 1 特彰钆 一ig , 1 1 2 ( “。霸鼬) + | l g i i 。i 2 如一，- 斟( 如- 1 ) 2 。( g k g ) i g , 1 1 2 “一斟瞄w 。( 一g k - i ) 由g , t 1 反- 1 0 于是有 一如。一斟， 矿21 赭 恬川2 一黔如一) 磁一1 ( g k - g 川) 卅一糕器 = 舻7 ( 1 一c o s ( 吼) ) 0 其中吼为繇与瓯一。的夹角 在新公式( 3 1 5 ) 的基础上引入参数，便得到如下一簇共轭梯度公式： r a 脚一g ；( g - a 慨i l g 女一。l l 。d , , ) 钟脚2 而研怎葛 其中，九 o ，1 】，当入= 0 时，即为d y 公式。 3 2算法 s t e p1 ：取五r ”，4 = - 9 1 ，s o ，七：= 1 ( 3 1 8 ) ( 3 1 9 ) s t e p2 ：若0 0 0 ，使： i i g ( x ) 一g c v ) l l - - - l i i z y l l ，v x ，y u 引理3 3 1如果目标函数厂( x ) 满足条件( h t ) 、( h z ) ，考虑方法( 3 1 1 ) 一( 3 1 2 ) ， 其中口女满足w o l f e 线搜索准则( 3 1 3 ) 和( 3 1 4 ) ，成由( 3 1 9 ) 计算，则对v 七= l ，2 ， 都有氍r d t 0 成立。 证明：当k = l 时，4 = - g l ，有 g j 而= 一l i g l i l 2 o 成立。 假设对k - 1 的情况有 g l 。矾一。 0 。 ( 3 3 1 ) 最d k = 吱卜g k + 3 k d k 0 ：一。g。旷+一g；矾一 - ( 1 侧训2 如棚圳胛i i 如“+ i i 圳2 如r a 鹅( “- 1 ) 2 = 高2 + 击鹄盛如一南砖黼 由( 3 3 1 ) 式和豉，玩一。 0 得上式小于0 。 一类与d y 方法有关的共轭梯度法的收敛性研究 即氍t 巩 0 故有 p 工删0 一蚓阳烈i l u k - 1 i i 飙。 雕一2 面丽而 ，2 + a 黔恬川i ：- - - - - - - - - - - j 二：二_ _ e - - - 一 ( z + 1 ) d l l ( g k - g 川) 酬1 2 一，( g 。一d ) = ? 综上有o 卢棚雕r 成立。 g i l a3 3 3 假设目标函数满足条件( h - ) 和( h ：) ，考虑迭代吒+ 。= 五+ 咴，其中反满 足g r d , o ，使0 酽c ， o k 1 ，2 ) ， 由( 3 1 2 ) 有： 以+ g = 卢女d 一l ( 3 3 2 ) 将( 3 3 2 ) 两边平方后移项得： l l 矾1 1 2 = 所0 以一。0 2 2 氍t 盔一i i g 七0 2 ( 3 3 3 ) 由引理3 3 2 知： 0 卢加”卯7 则 l i 巩1 1 2 ( 劈7 ) 20 巩一。0 2 2 9 ：反一i i g 。8 2 ( 3 3 4 ) 又由( 2 3 8 ) 得： 由( 3 3 4 ) 可得： 因为当k = l 时有： 肛撬= 簏r d = 黠t 2 一c l l ：1 + 黔+ 击2 丽弋酾+ 瓦厂+ 吁 ( 3 3 5 ) j k撼 一类与d y 方法有关的共轭梯度法的收敛性研究 圳1 2 ( g e 1 ) 2 将( 3 3 5 ) 式依次递推得： 由假设可知： 因此 所以 ( g k r _ l 以一1 ) 2 ( g l 。矾一，) 2 1 + 砑 11 叶一j i g , - , 2 + 可 妻击 上 生f 上 旦 i j a , 1 1 2 一k k = l筚举： 2 。 + 四 这与引理( 3 3 3 ) 矛盾，因此方法全局收敛 一2 0 1 一i t g , j 1 2 上蚶 i i 虹蚶 = 器 = 盟棚 拦 大连理工大学硕士学位论文 4与d y 方法相关的一类混合共轭梯度法的全局收敛性 结合h s 共轭梯度公式和d y 共轭梯度公式，本章给出了一个新的杂交共轭梯度法公 式，提出了一个新的共轭梯度算法，证明了新算法不依赖于任何线搜索便具有充分下降 性，且无需下降条件便证明了新算法具有全局收敛性。 4 1引言 仍然考虑求解如下无约束优化问题： r a i n f ( x ) i x r ”) 其中：f ：r ”_ r 是连续可微函数的共轭梯度法算法： ( 4 1 1 ) 反= 二喜：+ 卢。反一， 冬茎 c 4 ，2 ， 其中而是给定的初始点，为( z ) 在点坼的梯度向量，吨是搜索方向，步长因子a 。 满足w o l f e 线搜索准则： f ( x k + a 女畋) 一f ( x k ) 施女g t 反 ( 4 1 3 ) g ( x k + 口 畋) 7 也仃瓯t 吨 ( 4 1 4 ) 其中，0 5 仃 1 ，鼠为参数， = 琢万i g l , i2 历 r - s 一星i ! = 星= 12 几一。( g 女一g 。- 1 ) 是比较有效的共轭梯度法。结合d y 公式和h s 公式，我们给出如下杂交共轭梯度法 公式： p k ：型辑卑掣掣生掣 ( 4 - ) 一“2k 刈+ k ( 一g k - 1 ) i 博h 刈 一类与d y 方法有关的共轭梯度法的收敛性研究 胪+ = m a x o ，卢严) ( 4 1 6 ) 其中，a ( o ，1 ) ，0 z l 1 1 2 栩 4 2 性质 定义4 2 1 给定共轭梯度法的一个序列 成) ，若存在一个常数f ( o ，1 ) ( 或f 0 ，1 ) ) ， 使得对于v 七2 ，总有展彰以一， o ) ( 4 2 1 ) 性质4 2 1 假设鼠由( 4 1 6 ) 给出，则有 脚幽 2 2 ， 其中0 0 ，七7 - 1 ； s t e p2 ：若l l g k8 o ，使： i i g ( x ) 一g c v ) l l l i x e l l ，v x ，y a u 引理4 3 1 假设目标函数满足条件( i - i , ) 和( h z ) ，考虑迭代x k 引= x k + 口i 喀，其中反满 足g ：破 o ，使0 8 2 c , v k 1 ，2 ，) ， 由( 4 1 2 ) ，当k 2 时，有 反+ = 反盔一1 将上式两边平方后移项得： l i d 。0 2 - 卢2l i d 。一。1 1 2 2 9 r d 。一0 9 。1 1 2 上式两边同除以( g ；巩) 2 得： 器= f l ：- 黔r d ：一面2 一器t 2 若反= 剧哪+ = o ，由( 4 1 2 ) 知，巩= 一，于是有 故 大连理工大学硕士学位论文 划一2 g 2 -一=-一 ( g ；矾) 2繇t 以( g ；以) 2 2 g 2 = = 一一二- - _ ；一 g1 2i i g 。0 4 一j 二 g1 2 l 当成= 例哪+ 0 时，由( 4 1 5 ) 和( 4 1 6 ) 得： 于是 矿+ = 掣躲一 = i 卵r 2 2 ( 反r d i ) 2( 氍r d i ) 2一三+li丽jd,_,jj29rdk 21 1 - - t - 1i i 一一+ l 颤口。尹 一器t2 三g d k 堋一一! l g k 缸k l 、 ：监一三 ( g 以) 2g ；畋 一2 5 ：慨胛 ( 反r d t ) 2 学 。柚 艘 热 = ：一。厂坳：一户业“盥也 一类与d y 方法有关的共轭梯度法的收敛性研究 故 综上所述得 1 22 睦，吐 一( 氍t 以) 2g ；矾。( g l 。d k 一，) 2 ，1 一哂+ ( g 工。反一，) 2 1 i i g , 1 1 2 。 撼灿击i g( g ；反) 一i 。l f 1 + 砑 这与引理，4 3 1 矛盾，故定理成立。 1 砥 一2 6 一 拦 拦 七一c 一 一旷一& 一。瑚 一 一 。蹦瞥 。腻 学 蹦 大连理工大学硕士学位论文 参考文献 1 3h e s t e n e smr i t e r a t i v em e t h o df o rs o l v i n g 1i n e a re q u a t i o n s j o t a ，1 9 7 3 ，1 ：3 2 2 3 3 4 2 s t i e f e lel u b e re i n i g em e t h o d e md e rr e l a t i o n s r e e h n u n g z e i t s e h r i f i tf u ra n g e w a n d t e m a t h e m a t i k u n d e rp h y s i k 3 。1 9 5 2 3 h e s t e n e smr ，s t i e f e lel m e t h o d so fc o n j u g a t eg r a d i e n t sf o rs o l v i n gli n e a rs y s t e m s jr e s n a tb u rs t a n d a r d ss e c t 1 9 5 2 ，5 ( 4 9 ) ：4 0 9 - 4 3 6 4 f l e t e h e rr ，r e e v e sc f u n c t i o nm i n i m i z a t i o nb yc o n j u g a t eg r a d i e n t s ，c o m p u tj ，1 9 6 4 ， 7 ：1 4 9 - 1 5 4 5 g i l b e r t j c ，n o c e d a l j ，g l o b a lc o n v e r g e n c ep r o p e r t i e so fc o n j u g a t eg r a d i e n tm e t h o d s f o ro p t i m i z a t i o n ，s i a mj o u r n a lo no p t i m i z a t i o n ，1 9 9 2 ( 2 ) ：2 1 4 2 6 d a iyh ，y u a ny an o n l i n e a rc o n j u g a t eg r a d i e n tw i t has t r o n gg l o b a lc o n v e r g e n c ep r o p e r t y ， s i a mj o u r n a lo fo p t i m i z a t i o n ，2 0 0 0 ，l o ：1 7 7 1 8 2 7 t o u a t i - a h m e dd ，s t o r e yc e f f i c i e n th y b r i dc o n j u g a t eg r a d i e n tt e c h n i q u e s ，j o p t i m i z a t i o nt h e o r ya p p l 1 9 9 0 ，6 4 ：3 7 9 3 9 7 8 z o u t e n d i j k g ，n o n l i n e a rp r o g r a m m i n g ：c o m p u t a t i o n a lm e t h o d s ，i n t e g e r a n dn o n l i n e a r p r o g r a m m i n g ，e d i t e db yj a b a d i e ，n o r t h - h o l l a n d ，a m s