（运筹学与控制论专业论文）非线性共轭梯度法的研究.pdf

摘要非线性共轭梯度法的研究 摘要 共轭梯度法是求解无约束优化的一类有效的方法。它具有算法简便，存储需求 小等优点，适合于求解大规模优化问题。经典的非线性共轭梯度法有：f r 、p r p 、 c d 、h s 等。近几年，韦增欣、张建中、h i r o s h iy a b e 等学者利用d a i 和l i a o 的新 的拟牛顿条件( 正割条件) ，产生了许多新的算法，新算法既有梯度信息，又有函数 值信息，且数值表现比以往的算法好。 本文提出了两类共轭梯度法，第一类在h i r o s h iy a b e 和m a s a h i r ot a k a n o 的共 轭梯度法的基础上，就( 由于雠。= 一。或段一l = y k 一，的良好的数值表现) 的选择， 分别用一，和儿一，的算术平均值和凸组合来修正，以及对鼠的系数进行修正，从而得 到三种新的非线性共轭梯度法，从而扩大了反的范围。然后证明三种新算法在强 w o l f e 线搜索下的全局收敛性，数值验证表明这类共轭梯度法是比较有效的。 c d 方法在使用强w o l f e 线搜索时虽然能够保证每个搜索方向下降，但全局收敛 性质不好。第二类算法是结合c d 法和l i u ys t o r e y c 提出的新共轭梯度法( 简记l s 法) ，提出一类新的非线性共轭梯度法，新方法不但具有下降性质，而且在推广的 w b l f e 线搜索下是全局收敛的，最后进行了数值验证。 关键词：共轭梯度法，强w o l f e 线搜索，全局收敛，下降性，推广的w o l f e 线搜索 a b s t r a c t t h ec o n i u g a t eg r a d i e n tm e t h o dh a sp l a y e da l le f f i c i e n t r o l ei ns o l v i n gu n c o n s t r a i n e do p t 。 i m i z a t i o n e s p e c i a l l yi ns o l v i n gl a r g e s c a l en o n l i n e a ro p t i m i z a t i o nd u e t ot h es i m p l i c i t yo f 也e i ri t e r a t i o i l sa r l dt h e i rv e r yl o wm e m o r yr e q u i r e m e n t s s o m ew e l l 。k n o w nc o n j u g a t e g r a d i e n tm e t h o d sa r ef r , p r p , c d a n dh ss oo n r e c e n t l y , u s i n gan e wc o n l u g a c y c o n d i t i o np r o p o s e db yd a ia n dl i a o ，w e iz e n g x _ i n , z h a n gj i a n z h o n g ，h i r o s h iy a b e e ta l r e s p e c f i v e l yp r o p o s e da c l a s so fn e wn 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 ，w h i c hu s e b o t h a v a l i l a b l eg r a d i e n ta n df u n c t i o nv a l u ei n f o r m a t i o na n d h a v eg o o dn u m e r i c a le x p e r i m e n t s ht l l i sp a p e r w ee s t a b l i s ht w oc l a s s e so fc o n j u g a t eg r a d i e n tm e t h o d s - t h ef i r s tc l a s s ， b a s e do nm ec o n 5 u g a t eg r a d i e n tm e t h o do fh i r o s h iy a b ea n d m a s a h i r ot a k a n o ，g i v e nt h e c h o i c eo f i l ( b e c a u s e ”t l2 & 一lo r 比k 以2 欺_ lh a sg o o dn u m e r i c a le x p e r i m e n t s ) ，i i 1 s m o d i f i e db ya r i t h m e t i cm e a nm e t h o da n dt h e c o n v e xc o m b i n a t i o no f & - la n d 儿一l ， o 也e 州s e 最i sm o d i f i e d ，t h e r e f o r et h r e en e w m e t h o d sa r eo b t a i n e d t h em o d i f i e dt h r e e n e wn o n l k a rc o n j u g a t eg r a d i e n tm e t h o d sm a k e t h ew i d t ho f & w i d e n , w h i c h a r ep r o v e d g l o b a l l yc o n v e r g e n c ew i t ht h es t r o n gw o l f el i n es e a r c h f i n a l l y , t h e n u m e r i c a lr e s u l t ss h o w t i f f sc 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 s i sv e r ye f f 3 f i c i e n t i ni9 8 7 f l e t c h e rp r o p o s e dc o 坷u g a t ed e s c e n tm e t h o d ( c dm e t h o d ) ，w h i c he n s u r e d e v e n rs e a r c hd i r e c t i o nd e s c e n d ，b u tg l o b a lc o n v e r g e n c ep r o p e r t y l sn o tg o o d c o m b l n e d c dm e 也0 da n dan e wc o n j u g a t eg r a d i e n tm e t l l o dg i v e nb yl i u ys t o r e y c ，t h es e c o n d c l a s so fn o l l l i i l e a rc o n j u g a t eg r a d i e n tm e t h o di sp r o p o s e d ，w h i c hn o to t a yh a sd e s c e n t p r o p e 慨b u ta l s oi sp r o v e dg l o b a lc o n v e r g e n c e w i t ht h eg e n e r a lw o l f el i n es e a r c h f i n a l l y ， 也en 啪e r i c a lr e s u l t ss h o w t h i sc 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 s i sv e r ye f f i c i e n t 。 k e yw o r d ：c o n j u g a t eg r a d i e n tm e t h o d c o n v e r g e n c e ，d e s c e n tp r o p e r t y ，g e n e r a l ，s t r o n gw o l f el i n es e a r c h ，g l o b a l w o l f el i n es e a r c h 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 ，i ：；：一 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 研究生签名： 脚8 年7 月 e t 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名： 二d 口8 年_ 7 月ie t 硕士学位论文非线性共轭梯度法的研究 1 绪论 1 1引言 最优化问题是在有限种或无限种可行方案( 决策) 中挑选最优的方案( 决策) 。 随着高新技术、计算机及信息技术的飞速发展，最优化在工农业、国防、交通、金融、 能源、通信等众多领域的应用越来越广泛，问题的规模越来越大、复杂性越来越高。 最优化技术已成为大多数专业领域必修或选修的基本技术课程。 最优化问题的数学模型一般形式为 m i n ，( x ) ， s j 。q ( x ) = 0 , i = 1 ，2 ，m ，( 1 1 ) c j ( 功0 , i = ，l + l ，p 其中x 一“，恐，矗) r ”专r l , q ：r ”专r 1 = 1 ，2 ，p ) 为连续函数，通常还要求连续 可微。x 成为决策变量，厂( 功为目标函数，c j ( 曲，i = l ，2 ，p 为约束函数， c ，( x ) ，i = l ，2 ，m 为等式约束，c ，( x ) 0 ，i = m + l ，p 为不等式约束。 当m = 0 ，p = 0 时，此模型为无约束最优化问题：当模型含有约束条件时，则此模型 为有约束最优化问题。 无约束优化问题是最优化问题的基础，最基本的无约束最优化方法包括最速下降 法、牛顿法、共轭梯度法、拟牛顿法。其中，最速下降法是最基本的方法，牛顿法是 最主要的方法，共轭梯度法是解大型最优化问题的首选，拟牛顿法尤其是其中的方法 b f g s 是目前最成功的方法。我们即将研究的方法就是其中的共轭梯度法。众所周知， 梯度法( 最速下降法) ，牛顿法都有自身的局限性。梯度法程序简单，计算量小，但 收敛速度很慢( 线性敛速) ，牛顿法虽然收敛速度较快( 二阶敛速) ，但对初值的依赖 性较大，并且有许多缺点例如：二阶海森阵g f l 不存在，导致迭代方向以= 一瓯1 9 。无 意义等。 共轭梯度法是介于最速下降法与牛顿法之间的一种方法。它仅需利用一阶导数信 息，但克服了最速下降法收敛慢的特点，又避免了牛顿法需要存储和计算海森阵并求 逆的特点。它不仅是解决大规模线性方程的最有用的技术，而且也适合解非线性优化 问题。 共轭梯度法分为两部分，即线性共轭梯度法和非线性共轭梯度法。共轭梯度法从 1 9 5 2 年被h e s t e n e s 和s t i e f e l 首先提出的，用来作为迭代方法解决系数矩阵是对称 正定系统。线性共轭梯度法作为高斯消去法的一个替代，适合解决大规模问题，它的 执行与系数矩阵的特征值的分布有关，通过变换，或者预处理线性系统，有利于特征 1 绪论硕士学位论文 值的分布，并且显著的提高了方法的收敛性。非线性共轭梯度法是f l e t c h e r 和 r e e v e s 在1 9 6 4 年首先提出的。它是解决大规模非线性问题的最早的技术。近年来， 尤其是1 9 9 9 年以后，人们对非线性共轭梯度法有了进一步的发展，对孱提出了许多 不同的形式，有的还证明了由它们确定的共轭梯度法的收敛性。很多方法证明它们有 局部收敛或全局收敛。但是非线性共轭梯度法的理论和应用还有待于进一步的发展和 完善。 考虑无约束优化问题 r a i n 厂( 功，x r ” ( 1 2 ) 其中厂：r ”一r 是光滑的函数，厂在以点的梯度夥( x k ) = g 。共轭梯度法解( 1 2 ) 的迭代公式： x k + l = & + 吼d t ( 1 3 ) d k = 您地九。f 然o ( 1 4 ) 2 1 一反+ 反畋一l ，七2 u “ 其中 0 , 5 t 为步长；d 。为搜索方向；屈为一个标量；夥( ) = g 。 如果f ( x ) 是严格凸的二次函数并且吼是精确线性搜索的一维最小值即 = a r g r a i n f ( x i + 吼d t ) 时，( 1 3 ) ( 1 4 ) 称为线性共轭梯度法。对于一般的无约束 优化问题，不是线性共轭梯度法( 1 3 ) 一( 1 4 ) 就称为非线性共轭梯度法。 1 2 常见的共轭梯度法 在( 1 3 ) 一( 1 4 ) 中，要求d 。是下降方向，即可( ) o ；而吼由线性搜索准则 确定，一般的可以通过直接搜索法、插值法、精确线性搜索和非精确线性搜索等方法 来求。在非线性共轭梯度法中经常使用精确线性搜索和非精确线性搜索。 精确线性搜索就是要求步长由( 1 5 ) 产生 厂( 磁+ 畋) = i 建5 1 厂( 吒+ 口反) ( 1 5 ) 来获得f ( x ) 的最大可能的下降。但由于精确线性搜索的计算量比较大，并且在实际 求解目标函数最优解时没有必要过分的追求线性搜索的精确度，只要求目标函数在迭 代的每一步都有充分地下降就可以了，因此更多的是应用非精确线性搜索。 非精确线性搜索主要有以下三种方法： 硕士学位论文 非线性共轭梯度法的研究 1 戈德史丹( g o l d s t e i n ) 准则 给定，仃，o p - o v f ( x k ) 1 吱( 1 8 ) 一般而言，o r 越小，线性搜索越精确。然而，仃越小，工作量越大，通常取占= 0 1 ， 仃【0 6 ，0 8 】。 若将w o l f e 准则的( 1 8 ) 改为：l g ( x k + a k d 。) t 畋i 矿i 爵反i ( 1 9 ) 则变为强w o l f e 准则。 若将w o l f e 准则的( 1 8 ) 改为： q 氍t 畋g ( 矗+ 巩) t 巩一吒既t 畋( 1 1 0 ) 其中吼( ，1 ) ，c r 2 0 ，则w o l f e 准则变为推广的w o l f e 线搜索。 3 a r m i j o 准则 给定参数o p 0 ，乞 1 q 0 ，口 0 ，仃( 0 ，1 ) ， 计算铷= 反静硝胁刃；选择= 一“枷。使得以下两式成立： 厂( 矗+ 反) 厂( 以) 一口8 以0 2 ( 1 1 2 ) 一c 2 恬( + 畋) 0 2 g ( 故+ 以) t 畋+ 。一ql l g ( x k + 或) 1 1 2( 1 1 3 ) 当目标函数下方有解，导数l i p s c h i t z 连续时，可以证明后三个准则的步长是存在 i 绪论硕士学位论文 的。 f l e t c h e r 和r e e v e s ( 1 9 6 4 ) 首先提出了解非线性最优化的共轭梯度法。它是解 决大规模非线性问题的最早的技术。许多年后，这个原始的公式被修正，提出了许多 不同的形式。并且被广泛的应用。最著名的共轭梯度法有，f l e t c h e r r e e v e s 共轭梯 度法，p o l a k r i b i e r e p o l y a k 共轭梯度法，d i x o n 共轭梯度法，c r o w d e r - w o l f e 共轭 梯度法【8 1 ，h e s t e n e s s t i e f e l 共轭梯度法。其中确定的尾的公式分别为： 如下g ( k + 1 ) 万r g ( k + 1 ) g 、g 一 矿= 譬笄半 舻= 一7 9 ( k + o 万t g ( t + 1 ) k c w - - 髻等筹 矽二舞务器 ( 1 1 4 ) ( 1 1 5 ) ( 1 1 6 ) ( 1 9 6 9 年) ( 1 1 7 ) ( 1 1 8 ) 对于正定二次函数，若采用精确线性搜索，则以上几种共轭梯度法等价，但在实 际中p r p 方法和f r 方法是最常用。但对于非线性共轭梯度法，p r p 方法和f r 方法就 不同了，因为它们的海森阵不再是常数矩阵，搜索方向不再是共轭方向，在实践中， p o w e l l 发现对于某些问题，p r p 方法的效果比f r 方法的效果要好。f r 方法，如果从 砟一1 到黾产生不好的方向或者是小步长，下一步的方向矾和& 性质不好，除非沿梯 度方向执行一个重新开始。尽管f r 方法有以上的缺点，但z o u t e n d i j k 首先证明了采 用精确线性搜索f r 方法对于一般的非凸函数是全局收敛的。a i - b a a l i 证明了使用参 数盯 1 2 的情形，f r 方法因为产生一个上升方向而导致失败，因而他们提出一种广义线搜索，并证明了在 广义w o l f e 线搜索下f r 方法的全局收敛性。f r 方法在数值计算中表现并不十分理想， p r p 方法和h s 方法都有相似的理论性质，但在实际数值运行中比f r 方法要好，因为 4 硕士学位论文 非线性共轭梯度法的研究 它们在遇到不好的方向时，执行一个重新开始。然而，p o w e l l 表明p r p 和h s 方法在 未达到解时可能无限循环，因而它们没有全局收敛性质。这些方法都是运用原始的共 轭条件，即d ( ) 。g d ( ，) = 0j f 但p r p 方法是目前数值表现最好的共轭梯度法。 c d 方法( 共轭下降法) 由f l e t c h e r 在1 9 8 7 年引入，它的一个重要的特点是只要强 w o l f e 线搜索准则中的参数盯 1 ，则c d 方法在每次迭代均产生一个下降搜索方向， 而因f r 方法和p r p 方法即使对一致凸函数都有可能产生一个上升搜索方向。不过c d 方法的收敛性质不好，并且当线搜索精确时，舻= 矿，因此c d 方法与f r 方法有 同样的数值缺点，即可能连续产生许多小步长。文献【l 】中指出使用参数q 1 和叽= 0 是 必要条件。d y 方法是由d m 和y u a n 在研究c d 方法时发现的一种新的共轭梯度法， 它在w o l f e 非精确线搜索下即可保证在每次迭代产生一个下降方向，且方法全局收敛， 但数值表现一般。l s 方法是由l i u 和s t o r e y 在1 9 9 1 年提出的，且其性质类似于h s 方法。 1 3 重新开始的共轭梯度 标准的共轭梯度法如果采取每n 步沿负梯度方向重新开始的 丸+ l = 一g 州f - o ，1 ，2 ，( 1 1 9 ) 则收敛速度可从原来的线性收敛速度提高到n 步超线性收敛性【2 】【3 】；数值计算也表明 采取每n 步沿负梯度方向重新开始的策略将改善共轭梯度法的表现。然而，这种重新 开始策略具有以下一些缺点：一是它舍弃了算法沿前一次搜索方向站，搜索得到的二 阶导数信息；二是重新开始的频率一般与目标函数的性质有关，而不是简单地取为目 标函数的f ( x ) 的维数n p o w e l l t 4 1 使用不同的频率对于最速下降方向作为重新开始方 向作了数值实验，结果发现函数的即刻下降量比不采取重新开始技巧时函数的即刻下 降量反而小。由于在最优解邻近目标函数接近于一个正定二次函数，并注意到共轭梯 度法的二次终止性依赖于取负梯度方向作为初始搜索方向，故当迭代点进z f ( x ) 可 由二次函数很好逼近的区域时，重新取负梯度方向作为搜索方向，则其后n 次的迭代 方向接近于共轭方向，从而具有较快的收敛速度。因此将共轭方向法应用于非二次函 数的极小化，每迭代n 次就周期的取负梯度方向作为搜索方向。 因此将这种算法称作重新开始的共轭梯度法。 b e a l 【5 1 给出了反具有形式： 5 1 绪论 硕士学位论文 巩= 一g k + 展畋一l 十以呸( 1 2 0 ) 其中1 广 k 为某整数， 展2 我t ( 1 2 1 ) f 0若k = t + l 以2 t g j ”解只否则 l 2 2 ) m c g u i r e 6 1 和w o l f e 就b e a l 的三项方法作了数值验证，但数值结果却令人失望。 p o w e l l 通过引入一个新的重新开始准则，即如果下式 l 磊g 卜。l c i i g 。0 2 ( 1 2 3 ) 不成立，也使方法重新开始，克服了m c g u i r e 和w o l f e 的困难，并且获得了令人满意 的数值结果。因此称此算法为b e a l p o w e l l 重新开始的方法。 对于b e a l p o w e l l 重新开始方法的收敛性，即使采用精确线搜索，原始的 b e a l p o w e l l 算法不一定收敛，d a i 和y u a n 提出修正的b e a l p o w e l l 重新开始方法，即 限制其中的参数展和以为非负，即令 厍= m a x ( 展，0 ) ，疗= m a x 圪，o )( 1 2 4 ) 此外算法仅对非重新开始的点列测试充分下降条件 断 2 展= 粤( 1 3 1 ) 苁= 旯痧+ ( 1 一兄) 疗y( 1 3 2 ) 其中参数旯( 埘，佃) ，矿= 8 i | 2 ，茚y = 一繇t 反。单参数共轭梯度法簇可看成是由 f r 方法和d y 方法的某种线性组合组成的。d y 方法当满足一定的条件时，每一个搜 索方向都为下降方向，且收敛。 n a z a r t h 1 1 1 认为f r 方法、p r p 方法、h s 方法和d y 方法是其中主要的共轭梯度 法，并提出如下带有两个参数的共轭梯度法簇： 反：掣嗥等挚 ( 1 3 3 ) 心肌0 一，1 1 2 + ( 1 一段) d l 。y k 一。 u 。叫 其中五，段 0 , i 】为参数。 d a i 和y u a n 1 2 】基于上述的四种方法以及共轭下降法以及共轭下降法( c d ) 、l s 方法等六种形式较为简单地共轭梯度法提出了如下三参数共轭梯度法簇： 展= 而高等缝 m 3 4 ， 其中屯【0 , 1 】，以 o ，1 】与q 0 , 1 一以】为参数。上述的三参数共轭梯度法不但可 看成六种共轭梯度法的某种凸组合，它即可包含单参数共轭梯度法簇，以及双参数共 轭梯度法簇，还包括( 1 2 7 ) ，( 1 2 8 ) 的杂交共轭梯度法。 另外还有许多学者对于杂交共轭梯度法进行研究，提出一些具有良好性质的共轭 梯度法，如：d a i z f ，c h e nl p 【9 】中给出了一个新的h s - d y 的混合算法，其中 尻= 朦t 跟l 曲( 2 ，胁一1 2 3 5 ， 算法不需给定下降条件，在标准w o l f e 线搜索下，证明了算法的全局收敛性。同时得 8 硕士学位论文 非线性共轭梯度法的研究 0 盯 1 2 ，成= r 2 劈y ，f 2 ( - 1 ，1 】 1 2 0 )( 2 7 ) 【b l = 6 ( 五一l 一五) + 3 ( + 一1 ) 1 s k l 张建中等在文献【1 4 】【2 4 】中提出版的几种选择，如& ，y k ，g k ，g k l 等，但文献【2 5 】 中的数值验证表明，当段= s k ，以= y k 时，新方法具有良好的数值表现。 gl i ，e ta 1 在文献【17 】中根据d a i 和l i a o 的新的共轭条件和韦增欣的新的拟牛顿 方程，且令以= ，皖一。用i n a x 皖小0 ) 替代，提出几种新的展，并证明了新方法的 文献【16 】【1 7 1 中的展的选择都具有以下相同的优点： 1 、新的参数展不但包括梯度信息，而且包含函数值信息；而传统的屏只利用梯度信 2 、新的拟牛顿方程对目标函数的h e s s e n 阵估计得更精确，因而采用新的展可能数 值表现相对较好。 基于上面的参数展的优点及版的不同的选择，本文在文献f 1 6 】的基础上，令以为 & 与儿的算术平均值，进而取& 与以的凸组合，提出了孱n ，群“n ，孱2 1 ，矿孙， 对皖的系数修正，得到孱3 1 ，群”孙，并证明三种新共轭梯度法的全局收敛性。最后， 2 2 三种修正方法的提出 我们分别用& 与儿的算术平均值、凸组合对参数孱进行修正，从而确定本章的 前两种方法，另外通过对吼一。的修正，又提出本章的第三种方法。这三种方法的屈分 ( 1 ) 算术平均值修正 令段一。：妻( 儿一。+ 一。) 卜州- “岫b + - 1 丽。毕 【幺一l = 6 ( 以一i 一五) + 3 ( 既+ - 1 ) 1 - 1 2 一类新的带有函数值信息的共轭梯度法 硕士学位论文 乏，2 虮一t + p c 南c 儿一- + 一- ， 【晚一1 = 6 ( l l 一五) + 3 ( 繇+ g k 1 ) 1s k l 其中p 0 ，下面证明这样选择的合理性： 当段一l = s k l 时，若& 一l = o ，则一1 = 0 ，算法在第k 步终止，所以& 一l 0 ； ( 2 8 ) 当心一t2 儿一t 时，若& 一o ，则囊。儿一t = 圣。最- l o ，所以选择版一。= 丢( 儿一。+ _ 1 ) ， 只要& 一。0 ，确- i i s , 一。0 2 + 吐。儿一，o 。 由产生新的厦1 为： ( k 1 ) - - 犁 k 酬基肿f 豪 ( 2 9 ) ( 2 1 0 ) 其中f 0 。如果目标函数是严格凸的二次函数，且步长由精确线性搜索计算，则有 皖一l = 0 ，乏一l = 败- 1 ，且西一l = o ， ( 2 ) 凸组合修正 若式( 2 8 ) 变为 此时( 2 9 ) 变为袅，退化为h s 公式。 2 鼽。州西丽 = 6 ( 0 l 一五) + 3 ( 繇+ 一i ) t 一i 2 儿q 州而瓦鲁丽 = 6 ( 五一l 一五) + 3 ( + 一1 ) t & 一l 由磊一。产生的新的厦孙，矿2 分别为 = 紫 k 酬爨辩一r 基 对q 一。系数的修正 ( ( 1 目) 儿一l + 6 一1 ) ) ( ( 1 一口) 儿一i + 6 k 1 ) ) ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) o d d 乙 免 ，j、l，fl 、， 和 p 硕士学位论文非线性共轭梯度法的研究 对式( 2 8 ) 中的皖一。的系数用更一般的正整数一。，魄一l 代替，从而得到下式 其中a k 4 ，坟一l 都为有界的正整数，p 0 。 由式( 2 1 4 ) 是产生的新的孱3 为 f l k 3 ) = 掣 ( 2 1 4 ) ( 2 1 5 ) 对一般的目标函数是非凸函数，为确保其全局收敛性，提出了群舢3 、，公式为 俨= 一 袭，o ) 一，爨t ( 2 1 6 ) 由式( 2 1 5 ) 显然得到：当吼一。= 2 ，6 七一1 = 1 时为韦增欣的新的拟牛顿方程中的纯一。的系 数的取值；当吼q = 6 ，巩一l = 3 时为张建中的新的拟牛顿方程中的皖一。的系数的取值。 因而( 2 1 5 ) 式扩大了幺。的取值范围，从而扩大了屁的取值范围。 2 3 三种修正产生的共轭梯度法的全局收敛性 我们把算术平均值修正由( 2 9 ) 、( 2 1 0 ) 产生的共轭梯度方法称作方法( 2 9 ) ，方法 ( 2 1 0 ) ：把凸组合修正由( 2 1 2 ) 、( 2 1 3 ) 产生的共轭梯度方法称作方法( 2 1 2 ) 、方法 ( 2 1 3 ) ；把对皖一，的系数的修正由( 2 1 5 ) 、( 2 1 6 ) 产生的共轭梯度方法称作方法( 2 1 5 ) 、 方法( 2 1 6 ) 。在给出三种修正方法产生的共轭梯度方法的全局收敛性前，我们给出预 备知识。 对所有的k ，我们假设每个搜索方向吨满足下降条件 或反 0 ，使得方向吮满足下降条件 露畋 o 使 s 口 ( 2 1 9 ) 对所有的x l 都满足。 段 扣一 ，l 纠 h 坼 2 一类新的带有函数值信息的共轭梯度法 硕士学位论文 2 、在水平集厶= x r ”：厂( x ) 厂( 五) ) 的一个邻域u 内，厂连续可微，其导数g 满足 l i p s c h i t z 条件，即存在常数三使得 0 9 ( x ) 一g ( 少) 0 三l k y 0( 2 2 0 ) 假设h 意味着存在歹0 ( 歹为常数) ，对一切的x l 使得： i i v f ( x ) l ( 2 2 1 ) ( 一) 方法( 2 9 ) 和方法( 2 1 0 ) 的全局收敛性。 如果厂是一致凸函数，存在 o 使得 ( v f ( x ) - v f ( x - - ) ) t o 一习圳x 邓 ( 2 2 2 ) 或者等价的，对所有的x ，i 三， 厂( x ) ( 习+ v 厂( 习t ( 石一i ) + 等0 x i 2 ( 2 2 3 ) 成立。 由式( 2 2 2 ) 和式( 2 2 3 ) 得： 正。败一忙一i 8 2( 2 2 4 ) a - ! - - f k 一甑t & 一l + 铡& 胛 ( 2 2 5 ) 由式( 2 1 6 ) 和式( 2 2 0 ) 知： 0 & 一。0 2 圣。y k 三0 & 一，1 1 2( 2 2 6 ) 考虑式( 2 8 ) 中的皖和z k ，由中值定理得： o k = 6 ( 以一五+ 1 ) + 3 ( + g k + 1 ) 1 = 6 ( v f ( r k ) t ( 吒- x k + 1 ) + 3 ( 耽+ + 1 ) t = - 6 v f ( r h ) t + 3 ( + + 1 ) t & = 3 一夥慨) + 耽+ 。一夥魄) ，t 其中f ( 0 ，1 ) ，仇= r x k + ( 1 - r ) x k + l 。进而 川3 ( i i 耽一v f ( 叩a l + 1 1 + 。- v ( 仇) 1 ) i s , 3 ( 三i k 一仇8 + 三0 稚+ 。一仇l 叫& 0 硕士学位论文 非线性共轭梯度法的研究 = 3 ( l ( 1 一z - ) l l x , 一x k + i l l + l , i i x t + l x i l l ) l l s , i l - 3 l i i s 。1 1 2 ( 2 2 7 ) 由式( 2 2 0 ) 、( 2 2 6 ) 、( 2 2 7 ) 知： 例= 卜捻( y k + s k ) l l 驯i + 丽p l o t l ( 阱i i i i 虬i i ) “1 1 1 1 + 簪) 1 1 i i ：1 2 ( i + 3 户( 三+ x ) ) l l j 。i i t m i i & i i ( m o )( 2 2 8 ) 引理2 1 如果满足假设h ，考虑一般的共轭梯度法( 2 1 ) - ( 2 2 ) ，其中或满足下降 条翩7 ) ，且由强w 0 1 f e 线搜瓤7 ) ，( 1 9 ) 确定。令卿，4 ，如果铱zi i g k 酽l r o o ， 那么满足l 觋i n f a t i i - - o 。证明参见文献3 9 1 。 定理2 1 如果满足假设h ，且厂是一致凸函数，考虑方法( 2 9 ) ，其中瓯满足下 降条件( 2 1 7 ) ，且由强w o l f e 线搜索( 1 7 ) ，( 1 9 ) 确定，如果三= 2 ，只要p 0 ，则 刚l l ：o 。蜾三 ，只要。p ，则对于0 p 斌亍0sp r 使得。p 夏万1 j - - 豸o - 丽，那么畋。，且乏。魄一q 一，i i o o 其中魄= d d l l d t l ( 2 3 1 ) 证明：引理的证明类似于文