（基础数学专业论文）非线性共轭梯度法的收敛性.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本声明的法律责任由本人承担。 学位论文作者：寺蔓鸯啼 日期：庆。i 。年i 月，日 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。 根据郑州大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部 门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州 大学可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、 缩印或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学 位论文或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑 州大学。保密论文在解密后应遵守此规定。 学位论文作者：程毒萌 吼圳口年占月r 日 摘要 摘要 非线性共轭梯度法是求解一些大规模非线性无约束优化问题的基本迭代方 法，具有算法简单、存储空间需求小的特点。随着计算机的飞速发展和实际问 题中大规模优化问题的不断涌现，这些方法的重要性日益凸显。本文主要研究 非线性共轭梯度法的全局收敛性，共有四章： 第一章简要介绍非线性共轭梯度法的研究内容，研究价值及研究的现状与 本文的研究要点 第二章提出了一般函数的p r p 共轭梯度法的一个g r i p p o l u c i d i 型步长准 则。它仅利用当前的梯度和共轭方向信息来决定步长，却可以保证整个梯度模 序列收敛于o 。初步的数值试验显示了它的实用性和优越性。 第三章给出了一类新的混合共轭梯度法，其搜索方向的下降性不依赖于任 何线搜索条件，并在w o l f e p o w e l l 线搜索条件下证明了该算法具有全局收敛性， 同时还给出了比较好的数值结果。 第四章提出一种非单调a r m i j o 型线搜索方法，并将此方法与具有性质( 水) 的一类共轭梯度法相结合，导出了一类新的非单调共轭梯度算法，证明了这类 新算法是全局收敛的，p i 冲方法为其一个特例。 关键词：无约束优化；共轭梯度法；非精确线搜索：全局收敛性 a b s t r a c t n o n l i n e a rc o n j u g a t eg r a d i e n tm e t h o d sa r ef u n d a m e n t a l i t e r a t i v es c h e m e sf o r s o m el a 玛e s c a l en o n l i n e a ro p t i m i z a t i o np r o b l e m s ，d u et os i m p l ec o m p u t a t i o na n d l e s s m e m o r ys t o r a g er e q u i r e m e n t w i t h o c c u r r e n c eo fm a n yl a r g e s c a l en o n l i n e a r r a p i dd e v e l o p m e n t o fc o m p u t e ra n d p r o b l e m s i np r a c t i c e ，t h e s em e t h o d s b e c o m em o r ea n dm o r ei m p o r t a n t t h i st h e s i sm a i n l ys t u d i e sg l o b a lc o n v e r g e n c eo f t h en o n l i n e a rc o n j u g a t eg r a d i e n tm e t h o d s ，a n di sd i v i d e di n t of o u rc h a p t e r s t h ef i r s tc h a p t e rb r i e f l yi n t r o d u c e sn o n l i n e a rc o n ju g a t eg r a d i e n tm e t h o d sa n d t h e i rv a l u e s a n dt h e i rs t a t e o f - t h e a r td e v e l o p m e n t s ，a n dk e yp o i n t so f t h er e s e a r c h e s o ft h i st h e s i s t h es e c o n dc h a p t e rp r o p o s e sag r i p p o l u c i d i t y p es t e pl e n g t hr u l eo ft h ep r p c o n j u g a t eg r a d i e n tm e t h o df o rg e n e r a lf u n c t i o n i to n l yu s e sc u r r e n ti n f o r m a t i o no f g r a d i e n ta n dc o n j u g a t ed i r e c t i o nt od e t e r m i n es t e pl e n g t h ，a n dc a n e n s u r eg l o b a l c o n v e r g e n c et o z e r oo ft h er e s u l t i n gs e q u e n c eo fg r a d i e n tn o r m p r e l i m i n a r y n _ u m e r i c a it e s t ss h o wt h a ti f se f f e c t i v ea n ds u p e r i o ri np r a c t i c e t h et h i r dc h a p t e rp r o p o s e sac l a s so fn e wh y b r i dc o n j u g a t ef o r m u l a e ，a n dt h e r e s u l t i n gc o n j u g a t eg r a d i e n tm e t h o d sc a ng u a r a n t e et h a te a c hs c a r e hd l r e c t l o n 1 sa d e s c e n td i r e c t i o nw i t h o u ta n yl i n es e a r c ht e c h n i q u e s f u r t h e r m o r e ，w i t h w o l f e _ p o w e l ll i n es e a r c h ，t h e ya r ep r o v e dt ob eg l o b a l l yc o n v e r g e n t p r e l i m i n a r yn u m e r i c a l r e s u l t ss h o wt h a tt h e s eh y b r i dc o n j u g a t e 铲a d i e n tm e t h o d sa r ev e r ye f f i c i e n t - t h ef o u r t hc h a p t e rp r o p o s e san e wn o n m o n o t o n ea r m i j o t y p el i n es e a r c hr u l e ， a n ds t u d i e sac l a s so fc o n j u g a t eg r a d i e n tm e t h o d sw i t hp r o p e r t y ( 木) u n d e rt h el i n e s e a r c hr u l e ，w h i c hi n c l u d et h ew e l l k n o w np r p m e t h o da sas p e c i a lc a s e lh e c o r r e s p o n d i n gg l o b a lc o n v e r g e n c e i sp r o v e d 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 ；i n e x t l i n es e a r c h ；g l o b a lc o n v e r g e n c e i l 目录 目录 第一章绪论e eeoooooo ooo eeo bboooo oo o ooooooooo 1 1 1引占1 1 2 共轭梯度法的一般形式2 1 3 几种常见的共轭梯度法6 1 4 主要研究内容8 第二章p i 冲共轭梯度法的一个步长准则1 0 2 1引言1 0 2 2 全局收敛性1 1 2 3 数值试验1 6 第三章一种新的混合共轭梯度算法1 7 3 1引言1 7 3 2 算法与性质1 8 3 3 算法的全局收敛性1 9 3 4 数值试验2 l 第四章一类非单调共轭梯度算法的全局收敛性o ooooo 2 5 4 1 引言2 5 4 2 算法2 6 4 3 几个引理2 9 4 4 全局收敛性3 2 第五章结论与展望o ooooo 3 4 参考文献3 5 个人简历在学期间研究成果3 8 i i i 目录 致谢3 9 1 v 第一章绪论 1 1引言 最优化理论和方法是一门应用性非常强的年轻学科。它诞生于2 0 世纪4 0 年代，以线性规划模型和单纯形算法的出现为标志。近年来，随着计算机的飞 速发展和实际问题中大规模优化问题的不断涌现，最优化理论和方法在经济规 划、政府决策、生产管理、交通运输和军事国防等各大领域都得到了广泛的应 用。 共轭梯度法是最优化中最常用最有效的方法之一。它具有算法简单、易于 编程、存储空间需求小等优点，特别适合求解大规模优化问题。在石油勘探、 大气模拟、航天航空、国防、化工等不同领域出现的特大规模的优化问题一般 都是利用共轭梯度法来求解的。 共轭梯度法是求解大规模无约束非线性规划问题的一类有效算法。所有需 要计算梯度的优化方法中，最速下降法是最简单的，但是它在实际计算中收敛 速度非常缓慢。拟牛顿方法收敛速度比较快，其中b f g s 算法因其稳定的数值 结果和快速收敛性被广泛认为是处理中、小规模非线性规划优化问题的最有效 的方法之一，但拟牛顿方法需要存储矩阵以及通过求解线性方程组来计算搜索 方向，这对于求解大规模优化问题几乎是不大可能办到的。共轭梯度算法在算 法的简便性，所需存储量等方面均与最速下降法相差不大，并且收敛速度比最 速下降法要快，因此在处理大规模非线性优化问题时共轭梯度法倍受广大实际 部门的工程师们的青睐。 共轭梯度法最早是由计算数学家h e s t e n e s 和几何学家s t i e f e l 在2 0 世纪5 0 年代初为求解具有正定系数矩阵的线性方程组 a x = b ， v x r ”( 1 1 1 ) 而独立提出的。他们合作的著名文章【l 】被认为是共轭梯度法的奠基之作。该文 详细讨论了求解具有正定系数矩阵的线性方程组的共轭梯度法的性质以及它和 其它方法的关系。在a 为一r x 刀j 下定对称矩阵时，线性方程组( 1 1 1 ) 等价于最 优化问题 1 m i n 二x 7 彳z b r 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 2 j 将此方法推广到非线性优化领域，得到了求解 一般函数极小值问题的共轭梯度法。 非线性共轭梯度法的收敛性分析工作早期主要是由f l e t c h e r 、p o w e l l 、b e a l e 等学者给出的。近年来，n o c e d a l 、g i l b e r t 、n a z a r e t h 、s t o r e y 、a i b a a l i 、d a i 、 y u a n 、w a n g 和w e i 等中外学者对共轭梯度法继续不断地深入研究，在收敛性 方面得到了不少新结果，使得共轭梯度法在理论和应用上的发展r 趋进步。但 共轭梯度法的理论和应用还有待于进一步开拓和完善，因而共轭梯度法仍然是 一个非常值得研究的方向。 1 2 共轭梯度法的一般形式 非线性共轭梯度法是解决下述无约束优化问题 m i n f ( x ) ，x r ”) ( 1 2 1 ) 的一种重要方法，其中函数f ：r ”专r 一阶非线性连续可微，其梯度向量记为 g 。共轭梯度法的迭代格式为 x k + i = x k + 吼a k ( 1 2 2 ) 其中x l 是给定的初始值，哝为搜索方向，一般要求搜索方向以是下降方向，即 v f ( x k ) r 以 0 ；吼 0 是满足某些线搜索条件的步长因 子。在确定步长因子吼时，通常会用到以下几种方法： ( 1 ) 精确线搜索：寻找 0 满足条件 f ( x k + 吼以) = m i n f ( x k + 口以) ( 1 2 3 ) 从理论上讲，采用精确线搜索方法得到的步长可以使目标函数得到最大限度的 下降量，精确线搜索是最理想的线搜索方法。但从计算的角度来讲，采用精确 线搜索方法求步长需要求一个单变量函数的极小值，计算量较大，代价较高， ， 第一章绪论 用这种方法求解步长并非一种理想的选择。在实际计算中人们常常采用非精确 线搜索策略。下面是几种常见的非精确线搜索方法。 ( 2 ) w o l f e 线搜索( w w p ) ：寻找吼 0 满足条件 f ( x k + 吼巩) 厂( 吒) + 瓴彩 ( 1 2 4 ) t g ( + 吼吮) 0 - d i g , ( 1 2 5 ) 其中g k = v f ( x k ) ，常数万和盯满足万( o ，1 2 ) ，盯( 万，1 ) 。第一个不等式要求目标 函数值的下降量至少要与切线的下降量成正比。第二个不等式防止步长过小， 保证目标函数值有足够的下降量。 ( 3 ) 强w o l f e 线搜索( s w p ) ：寻找 0 满足条件( 1 2 4 ) 和 l g ( 晚+ 吼) i 0 - i l ( 1 2 6 ) 其中艿( o ，1 2 ) ，0 - ( 艿，1 ) 。当0 - = 0 时，必有g ( 瓦+ 以) 7 1 吮= 0 ，因此当0 - 一0 时，强w o l f e 线搜索的结果接近于精确线搜索。 ( 4 ) 推广的w o l f e 线搜索：寻找吼 0 满足条件( 1 2 4 ) 和 q 衫g k d r g ( x , + 吼巩) - 0 - 2 d r g ( 1 2 7 ) 其中0 i ( 万，1 ) ，0 2 0 。当0 1 = 0 - 2 时，推广的w o l f e 线搜索即为强w o l f e 线搜索； 当c r 2 = + o 。时，推广的w o l f e 线搜索即为w o l f e 线搜索。 ( 5 ) g o l d s t e i n 线搜索：寻找吼 0 满足条件 磊吼卅g t 厂( + 吼以) 一厂( 吒) 如g t ( 1 2 8 ) 其中0 嘎 1 2 0 ，艿 0 ro q 1 0 ，满足条件 f ( x k + 矾) 。郇m a 。x ( t ) f ( x k 一) + p a k g ；d k ( 1 2 1 1 ) lg ( x k + a k d k ) r 矾匿一万g ：以 ( 1 2 1 2 ) 4 第一章绪论 其中0 p 万 0 ： 第一章绪论 4 = - g i ，k ：= 1 步骤2 如果1 | g ki i s ，则停止； 否则，利用某非精确线搜索求吼； x k + l = x k + 吃 步骤3 利用某公式计算展+ 。： 巩+ l = 一g k + l + 成+ l 以； k ：= k + 1 ；转步骤2 本文仅考虑线搜索型的非线性共轭梯度算法。 1 3 几种常见的共轭梯度法 式( 1 2 1 3 ) 0 0 参数屈的计算公式有很多，不同的鼠计算公式对应着不同的 共轭梯度算法。一些著名的羼计算公式有： 矽= i 慨1 1 2 1 1g | 1 2 戌即= 反t 儿一。j lg 1 1 2 p ：s = 羲y k d g _ 、d k d 舻= 一i ig 。州t 一。g 川 臃s = 一或y k 一；。一， 劈y = i i 既1 1 2 以：。儿一， 等，其中儿一l = g k - g k 一。我们称相应的共轭梯度法为f r 方法、p l 冲方法、h s 方法、c d 方法、l s 方法、d y 方法。这些方法在目标函数二次正定和精确线 搜索下是等价的。但对于一般的目标函数或者不精确线搜索时，它们的收敛性 质和数值表现各不相同。 f r 方法是最早的非线性共轭梯度法，是由f l e t c h e r 和r e e v e s 2 】在19 6 4 年 提出的。f r 方法具有良好的全局收敛性，但其数值表现很不理想。对f r 方法 的收敛性分析在早期是基于精确线搜索的。z o u t e n d i j k | 9 j 证明了在精确线搜索下 f r 方法对一般非凸函数总收敛。p o w e l l i l o 】分析了在精确线搜索下f r 方法收敛 6 第一章绪论 非常慢的原因主要是可能产生连续小步长。非线性共轭梯度法的第一个非精确 线搜索的全局收敛性结果是由a 1 一b a a l i 在1 9 8 5 年给出的【1 1 】，他证明了使用参数 仃 0 为一个步长，以为一个搜索方向：在迭代过程中，以下面方式自动 地生成 d k 一- - - 二耋+ 屈吨一。篓主芸 c 2 3 ， 其中g k 为厂在x k 处的梯度。关于展，相应的计算公式较多，一个实用的选择是 矿= ( g k 一一。) 瓯一。1 1 2 ( 2 1 4 ) 在1 9 8 4 年，p o w e l l 1 6 1 举例说明了：对于一般的目标函数而言，即使在精确 线搜索 f ( x k + 巩) = m i n f ( x k + 口矾) ：口0 ) 下，p i 心共轭梯度法( 2 1 2 ) ( 2 1 4 ) 也可能不收敛。那么，对于一般的目标函数 而言，如何选择步长，才能保证它的全局收敛性呢? 这个问题一直到1 9 9 7 年 才由g f i p p o 和l u c i d i 4 】从理论上予以解决。 考虑到g f i p p o - l u c i d i 步长准则并不实用，在2 0 0 2 年戴或虹【2 2 1 提出并研究了 下面的步长准则：计算 吼= m a x 8 ：0 护 1 ；j = 0 ，l ，2 ，) 使之满足 f ( x k + a k d k ) f ( x k ) + a t z k g ：以，0 兄 0 ，使得 吒打i g ki f l 2 ( 2 2 2 ) ( c ) i | 吃l i - ( 1 + l p ) l l | i ( 2 2 3 ) 本引理的证明类似于文献 2 3 ，3 0 。为了文章的完整性，现将整个证明过程 叙述如下。 证明( a ) 首先证明如果吃 0 ，则一定存在一个矗，对w j o ，( 2 1 5 ) 式都成立。假设结论不成立，则存在一个无穷点列 工) ，使得 f ( x k + 0 j , 锵咿地m 秒等以 两边同除以砂唰孥告，并令力一o o ，得g ；以力爵以。由以 1 。 这与条件名( 0 ，1 ) 矛盾。 其次证明如果彰矾 0 ，则一定存在一个 ( s o ，佃) ，使得( 2 1 6 ) 式成立。 假设结论不成立，则对w 矗，都有 一c l l g ( z d ) 1 1 2 g ( ) 7 ( 一g ( ) + 屏+ 。以) 一i ig ( ) 1 1 2 + l 屈+ ，g ( ) 矾i i 一i lg ( z ：) 1 1 2 + l 呈生笙! 掣l ig ( z j ) i ii igi i 其中z - x , + e g - ，p i l i 吼ig , _ i i u 。畋。上式两端取极限，令一o o 得 一cl ig ( 坛) 1 1 2 一i fg ( k ) 1 1 2 这与c ( 0 , 1 ) 且i lg 。i l 0 矛盾。 综上证明可知，如果矾 o ，则一定存在一个五，使得步长 1 2 第二章p r p 共轭梯度法的一个步k = 准则 吼朝 等刚靛( 2 1 5 ) 蜘( 2 1 6 成 注意到一4 = 一| | g 。1 1 2 _ 一el l & f 2 o ，由归纳法即得对v k ，都有 反以一c | | 1 1 2 x ( 口, l o ) g j l 以 两端同除以吼乡，然后同减去巩得 ( g ( + 善( 吒目) 巩) 一g 。) r 以 一( 1 一无) g ：以 由( 2 2 1 ) 得 f ( 瓯p ) i i 以i i 2 - ( 1 - 2 ) g ：, 哦 由条件( 2 1 6 ) 及f ( 0 ，1 ) 得 吼 坠竺塑! q 墨塑必 2 三善 i l 以1 1 2 三 | l 以2 若o 不能满足( 2 1 6 ) ，令比= 以+ ( 矽) 畋，即有 叩l i g ( m ) | | 2 一| | g ( ) f | 2 + l 呈q 丝! 笋l l g ( w , ) l l l l d , i i 一i ig ( ) | 1 2 + 旦墨垒竺立卫； 掣i i 哝i i 两端同除以i ig ( ) | | 2 得 一c 一l + 盟掣i i d , i i 第二章p r p 共轭梯度法的一个步长准则 一c 一1 + l | | ( g a t , - 0 ) 1 t d , 1 1 2 i i - 所以 吼丁( 1 - c ) o 丽l g , 1 1 2 lj | 口o | | - 综上硼，协血n p 竿，半卜有他2 成立。 ( c ) 由( 2 1 3 ) ，( 2 1 4 ) ，( 2 1 6 ) 和( 2 2 1 ) 得 i j 巩j i - - - i i 舰| j + j 展i | | 咴一。j j 弧i l + 智慨| i - 0 ； ( b ) 酬以1 1 2 f l ( f ( x 。) - f ) ； ( c ) 酬1 1 2 y ( f ( x i ) - f ) 其中f 为递减有下界序列 f ( x k ) ) 的极限。 证明 ( a ) 由( 2 2 2 ) 和( 2 2 3 ) 可得 石两t 2 2 4 1 4 由上式和( 2 1 5 ) 得 即有 g ；巩一ci ig k1 1 2 一兰吼i i 畋1 1 2 p f ( x k + c t k d k ) f ( x k ) 一竽彳慨1 1 2 p ；t _ s c 2i l 矾1 1 2 ( ) 一厂( 坼+ 吼巩) p 又由于 厂( ) ) 是下降序列，所以一定存在一常数厂，使得! 鳃厂( 故) = f 。于 是有 等何2 1 2 咿( 坼) 一f ( x k + o q d k ) ) = f ( x 1 ) 一! i m f ( x k ) = f ( x - ) 一f + ( 2 2 5 ) k = l k = l 又由( a ) ，可得 慨1 1 2 p ( z c c t 2 ) 一( 厂( 五) 一厂) ( 2 2 6 ) 七= l 然后令= p ( a c a 2 ) 。1 即可。 ( c ) 由( 2 2 2 ) 得 i i 繇1 1 2 一1 吼i i 以1 1 2 i 结合引理2 2 1 的结论( 2 2 3 ) 得 i i 反1 1 1 ( 1 + l p ) 吒j l 以| | z 从而 慨忙去( 1 + l p ) 2 - 吼2 慨1 1 2 ( 2 2 7 ) ( 2 2 8 ) 第二章p r p 共轭梯度法的一个步长准则 再利用( 2 2 5 ) ，得 慨1 1 2 7 ( 厂( 而) 一厂) 其中y = 吉c + 三p ，2 ( 害) 。 注意：这个定理表明在步长准则( 2 1 9 ) ，( 2 1 5 ) ，( 2 1 6 ) 下，p r p 共轭梯度法所 产生的梯度模序列收敛于0 。 2 3 数值试验 本节我们通过数值试验来比较p i 冲共轭梯度法在g r i p p o l u c i d i 步长准则下 与在步长准则( 2 1 9 ) ，( 2 1 5 ) ，( 2 1 6 ) 下迭代步数和c p u 时间的差异。所用电脑操 作系统是微软w i n d o w sx pp r o f e s s i o n a l ，处理器是a m ds e m p r o n3 0 0 0 + ，频率 为1 8 0 g h z ，编程软件为m a t l a b7 0 4 。数值试验中的函数来自文献 3 1 ，终 止条件为l ig ( 坼) 临1 0 一。 下表中的相关符号：p r p o 表示g r i p p o l u e i d i 步长准则下的p r p 共轭梯度 法，其中参数秒= 0 9 ，p = 1 0 5 ，艿= 0 0 1 ，q = 1 0 2 , q = 1 0 - 2 ；p r p l 表示步长准则 ( 2 1 9 ) ，( 2 1 5 ) ，( 2 1 6 ) 下的p i 冲共轭梯度法，其中参数0 = 0 9 ，p = 1 0 5 ，a = 0 5 ，c = 1 0 ；“一 表示迭代次数超过5 0 0 0 次，方法对这个数值例子失效。 表2 1p r p 0 和p r p l 的数值结果 由上表可以看出，p r p l 方法的迭代步数和c p u 时间都比p r p 0 方法少得 多，优势明显，说明步长准则( 2 1 9 ) ，( 2 1 5 ) ，( 2 1 6 ) 是实际有效的。 1 6 第三章一种新的混合共轭梯度算法 第三章一种新的混合共轭梯度算法 3 1 引言 考虑如下无约束优化问题： m i n f ( x ) i x r ”) 其中函数厂：r ”jr 是非线性的连续可微函数。共轭梯度法是求解上述无约束 优化问题常用的方法，由于它迭代简单、所需存储空间小、收敛速度快，所以 非常适合于求解大规模优化问题。其迭代格式为： 砟+ l = x k + 吼以 ( 3 1 1 ) 以：l - g t = 1 ) ( 3 1 2 ) 【一+ 屏以一l ( 尼2 ) 【一j 吼+ 屏口t l l 尼2 ) 其中吼为步长因子，以为搜索方向，g k = v f ( x k ) ，标量成的不同选取方式对 应不同的共轭梯度算法，一些较著名的展公式有鼠肼、屏觥、孱螂、屏w 等。 为了建立共轭梯度法的全局收敛性结果，通常要求步长瓯满足一些线搜索 条件，比如常用的w o l f e p o w e l l ( w w p ) 线搜索条件 f ( x k + 以) f ( x k ) + 8 a t k g 7 巩 ( 3 1 3 ) g ( x k + a t k d k ) 7 以c r g , 7 畋 ( 3 1 4 ) 以及常用的强w o l f e ( s w p ) 线搜索条件( 3 1 3 ) 和 g ( + 巩) 7 以i 仃i 7 以i ( 3 1 5 ) 其中0 万 1 2 ，8 1 。这种方法在w w p 条件下全局收敛，且数值结果比较好。 受文献 2 6 ，3 2 】的启发，结合公式( 3 1 6 ) ，本章提出了一种新的混合共轭梯度 算法。该方法在任何线搜索下都能保证搜索方向的下降性，且在w w p 条件下 全局收敛，同时数值表现也比较理想。 3 2 算法与性质 考虑到精确线搜索时7 d k 一。= 0 以及公式( 3 1 6 ) 对应的共轭梯度算法的好 的收敛性，我们提出了一种新的展的公式，即 矿：型弦止兰罂丝岛出业 ( 3 2 1 ) h l lg i | 2 + 如ig ：以一l 其中0 0 ，便 | | g ( x ) 一g ( y ) i i - - l | x yl l ，v x ，y u 算法3 1 步骤1给定五r ”，g 0 ，吐= - g l ，k ：= 1 ； 步骤2 如果i ig k1 1 g ，则停止；否则，由w w p 条件( 3 1 3 ) 、( 3 1 4 ) 求 得吼，令+ l = 4 - o r k 矾； 步骤3 由( 3 2 2 ) 式计算+ ，以+ l = 一g 川+ 硝+ 以，k ：= k + l ，转步骤 2 。 引理3 2 1对于迭代格式( 3 1 1 ) 和( 3 1 2 ) ，如果屏取为矿+ ，则对于 任意k 1 ，都有 彰吃 一( 1 - 阜) j | g 。1 1 2 ( 3 2 3 ) 证明 若+ = 0 ，则g 吾以= - i ig 。1 1 2 。显然满足( 3 2 3 ) 式。 若胪+ = 删反t 以一恬川2 + 业絮融舞砦地g r d k 一， 0 ，使得 i l 氍1 1 m ，v k 1 ( 3 3 1 ) 由于 ( 吒) 是一个下降序列，显然由算法3 1 生成的迭代序列 吒) 包含在 1 9 第三章一种新的混合共轭梯度算法 水平集1 - 2 中。故存在常数厂，使得l i m f ( x k ) = 厂。 引理3 3 1 t 2 0 】设目标函数满足假设3 1 ，考虑一般方法黾+ l = x k + a k d k ，其 中搜索方向以满足g r d k l k + c 其中， o ，c 为常数，则 善= 佃 纠e a i 定理3 3 1 设目标函数满足假设3 1 ， x k ) 是由算法3 1 生成的迭代序列， 则有 j i m i n f | ig ki i _ 0 ( 3 3 3 ) 证明由( 3 1 2 ) 得，对所有的k 2 都有 d k + g k = p 0 h “d k 对上式两端取模并平方得 i i 以1 1 2 = 一l lg 。1 1 2 2 矾+ ( 矿+ ) 2i | d k 一。1 1 2 苗+ 的定义易知矿+ 黔，代入上式得 2 l 南r k 一惫以1 1 2白气一厶l 一 所以有 y 蝉1 2 ：佃 智l l 矾1 1 2 这与z o u t e n d i j k 条件( 3 3 2 ) 矛盾，表明定理结论成立。 从定理3 3 1 的证明可知，对于任何一个鼠取为+ 的共轭梯度法而言， 只要步长技术能确保z o u t e n d i j k 条件( 3 3 2 ) 成立，则该共轭梯度算法一定全 局收敛。特别地，如果把算法3 1 中的w w p 条件更换为s w p 条件，算法仍然 是全局收敛的。 2 1 第三章一种新的混合共轭梯度算法 3 4 数值试验 为了考察本章提出的算法的数值表现，我们用文献 3 1 】中的函数进行数值 试验，并将数值结果与p i 冲方法进行比较。试验所用的数学软件为m a t l a b 7 0 4 。每次执行线搜索前都用下式计算初始步长【3 3 】 l i i 耵( 五) | | - l ， k = 1 弘卜觜一列 终止条件为i i g ( x k ) 临1 0 - 6 。结果见表3 1 。 表中的相关符号表示分别为：p r p s w p ：试验参数为矿+ s w p ，其中 万= o 0 1 ，盯= o 1 ；n c g s w p ：试验参数为彤( ) + s w p ，其中万= o 0 1 ，仃= o 1 ， = 1 2 5 ；n w s w p - 试验参数为+ + s w p ，其中万= 0 0 1 ，盯= o 1 ，丑= 如= 1 ； n h + w w p ：试验参数为+ + w w p ，其中万= 0 0 1 ，仃= o 1 ， = 乃= 1 ；p r o b l e m ： 测试问题的名称；d i m ：目标函数的维数；n i n f n g ：迭代次数目标函数计 算次数梯度函数计算次数。 表3 1p r p s w p 、n c g s w p 、n h + s w p 和n h + w w p 的数值结果 第二章一种新的混合共轭梯度算法 续表 下面我们根据表3 1 的数据来分析比较一下这四种算法的数值表现的优劣。 第三章一种新的混合共轭梯度算法 首先利用下面的公式计算出每一个测试函数在每种算法下函数值和梯度值 的计算次数 n t 删= n f + m 宰n g 其中m 为某一给定的正整数。根据自动微分的知识知【3 4 1 ，m 一般取为5 。其次， 设e m 为上述四种共轭梯度算法中的一种，对于每一个测试问题i ，分别计算出 n t o t l d , i ( e m ) 与t o t a i 。( p r p s w p ) 的比值，记为r , ( e m ) ，即 ，：( e m ) ：坠：! ! 型! ” 7 n t o t a l ，( p r p s w p ) 最后，计算出这些比值的几何平均值，记为r ( e m ) ，即 ，、l 倜 r ( e m ) = i 兀l ( e m ) l i e s 其中s 为测试问题的集合，isi 为测试问题的总个数。若r ( e m ) 0 ，使 i ig ( x ) 一g ( y ) i i li ix - yi | ，v x ，y u ( 4 2 1 ) 由上述假设知，存在常数歹 0 ，使 第 | ig ( x ) 临歹，v x q ( 4 2 2 ) 下面给出性质( 水) ，这个性质的严格表述最早是由g i l b e r t 和n o c e d a l t l 9 给 出的。 性质( 木)考虑一般共轭梯度法( 4 1 2 ) - ( 4 1 3 ) ，并假定 0 1 和见 0 ，使对所有的k 有下式成 立： l 展i b ( 4 2 4 ) 以及 s k - 1i i 允j i 孱i 万1 ( 4 2 5 ) 具有性质( 木) 的展公式很多。例如，p r p 方法，g i l b e r t 和n o c e d a l 1 9 1 证明 了可取6 = 2 y 2 r 2 和旯= y 2 ( 2 l y b ) ，使( 4 2 4 ) 和( 4 2 5 ) 两式成立，即胖 具有性质( 水) 。显然，9 ；r p = m a x 0 ，矿) 亦具有性质( 水) 。再如，文献 2 7 】 中，w e i 、y a o 和l i u 提出一种新的展计算公式： r 眦g ；( g k 一鼢趾t ) = 唰产 对于上述w y l 方法，n - - j 取b = 4 歹2 r 2 和旯= 7 2 ( 4 l f b ) ，使( 4 2 4 ) 和( 4 2 5 ) 两式成立，即矿亦具有性质( 木) 。事实上， 胛一圳魄一鼢缸l i i l 矿l 、芒铲l 旷鼬嗨，一黜酬 第四章一类非单调共轭梯度算法的全局收敛性 ! ! 垒幽堕二坠刿l 鱼= ! 蚪也业 一 i i 一。酽 ，2l ig l ii i g k g i | i lg i f 2 由( 4 2 3 ) 有 i , a ui 韭掣等勘 l i 一lf f _厂 而若| is k 一。临兄，则由梯度向量的l i p s e h i t z 连续性知 掣等= 万1 l ig 一ii i _7 z d 本章用到如下非单调线搜索： 定义i i gi i 级2 厩矛口t2 鼎，其屹