（应用数学专业论文）具有充分下降性的非线性共轭梯度法.pdf

摘要 最优化是一门应用相当广泛的学科，它讨论决策问题的最佳选择，构造寻求最 优解的计算方法。虽然最优化问题可以追溯到古老的极值问题，但直到1 9 4 7 年 d a n t z i g 提出一般线性规划问题的单纯形法后，它才成为- - i - j 独立的学科。近年来随 着系统科学的发展和计算机的广泛应用，最优化理论和方法在工程、国防、经济、 管理等领域以及许多数学分支都有着直接或间接的应用，成为一门十分活跃的学科。 共轭梯度法是最优化中常用的方法之一，它具有算法简单、存储需求少、易于 实现等优点，十分适合求解大规模无约束优化问题。本文研究求解无约束优化问题 的非线性共轭梯度法，并讨论方法的全局收敛性和数值表现。 第一章，首先简要介绍了最优化问题的提出以及判断最优解常用的最优性条件； 回顾了求解无约束优化问题常用的几类导数下降类算法。 第二章，简单介绍了本文将要研究的问题背景和已有结果以及目前的研究现状。 第三、四章，提出两种修正的非线性共轭梯度法，分别为修正f r 方法和修正h s 方法，这两种修正方法的一个重要特征就是能产生充分下降方向，即搜索方向巩满 足畋= 一恬。n 这种性质不依赖于方法所采用的线性搜索。此外，当采用精确线性 搜索时，本文的修正f r 方法和修正h s 方法分别退化为原始的f r 方法和h s 方法。因 此，当目标函数是严格凸二次函数，且采用精确线性搜索时，这些修正的共轭梯度 法具有共轭性和二次终止性。在一定的条件下，我们证明了采用标准a r m i j o 线搜索 的修正共轭梯度法求解非凸极小化问题的全局收敛性。在第四章中我们还在非单调 a r m i j o 线搜索下证明了修正h s 方法的全局收敛性。数值结果表明本文所修正的共轭 梯度法具有良好的计算效能，适合求解大规模无约束优化问题，且稳定性较好。 在第五章中证明了修正的f r 方法和修正的h s 方法采取固定步长时的全局收敛 性。 关键词：非线性共轭梯度法；线性搜索；充分下降方向；全局收敛性 a b s t r a c t o p t i m i z a t i o ni sas u b j e c tw h i c hi sw i d e l ya p p l i e dt od i s c u s st h eb e s t c h o i c ei nd e c i s i o nm a k i n ga n dt os e e kt h eb e s t s o l u t i o n a l t h o u g ht h e p r a c t i c eo fo p t i m i z a t i o nc a nb et r a c e db a c kt ot h eo l de x t r e m e - v a l u ep r o b l e m ， i tb e c a m ea ni n d e p e n d e n ts u b j e c ti n19 4 7a f t e rd a n t z i gh a dp u tf o r w a r d a l g o r i t h mo fl i n e a rp r o g r a m m i n gb a s e do ns i m p l e xm e t h o d r e c e n t l y ，w i t h t h e d e v e l o p m e n to fs y s t e m a t i cs c i e n c ea n dt h ew i d e l ya p p l i c a t i o no f c o m p u t e r ，t h eo p t i m i z a t i o nh a sb e c o m e a na c t i v e s u b j e c t a p p l i e d i n e n g i n e e r i n g ，n a t i o n a ld e f e n c e ，e c o n o m y ，m a n a g e m e n ta n ds o m eb r a n c h e so f m a t h e m a t i c sd i r e c t l yo ri n d i r e c t l y 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 ，o n eo ft h eo p t i m i z a t i o nm e t h o d s ， i ss i m p l e ，e a s i l yr e a l i z e da n de s p e c i a l l ys u i t a b l ef o rs o l v i n gt h el a r g e s c a l e u n c o n s t r a i n e do p t i m i z a t i o np r o b l e m s i nt h i sp a p e r , s o m en e wn o n l i n e a r c o n j u g a t eg r a d i e n tm e t h o d sa r ep r o p o s e d t h e ya r em o d i f i c a t i o n sf o rt h e w e l l - k n o w ne x i s t i n gc o n j u g a t eg r a d i e n tm e t h o d s w ee s t a b l i s ht h eg l o b a l c o n v e r g e n c et h e o r yf o rt h ep r o p o s e dm e t h o d sa n dr e p o r te x t e n s i v en u m e r i c a l r e s u l t s i nc h a p t e r1 ，t h e d e v e l o p m e n to fo p t i m i z a t i o na n ds o m eo p t i m a l i t y c o n d i t i o n sw h i c ha r ef r e q u e n t l yu s e dt od e t e r m i n et h eo p t i m u ms o l u t i o na r e i n t r o d u c e d s e v e r a lk i n d so fd e r i v a t i v ed e s c e n tm e t h o d sf o ru n c o n s t r a i n e d o p t i m i z a t i o na r ea l s or e v i e w e d i nc h a p t e r2 ，t h eb a c k g r o u n da n de x i s t e dr e s u l to ft h er e s e a r c ha n dt h e c u r r e n tr e s e a r c hs i t u a t i o no ft h i sm e t h o da r ei n t r o d u c e d i nc h a p t e r3a n d4 ，t w om o d i f i e dn 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 r ep r o p o s e d t h e ya r em o d i f i e df rm e t h o da n dm o d i f i e dh sm e t h o d ， r e s p e c t i v e l y a ni m p o r t a n tp r o p e r t yo ft h e s em o d i f i e dm e t h o d si st h a tt h e m e t h o d sc a ng e n e r a t eas u f f i c i e n td e s c e n td i r e c t i o na te a c hi t e r a t i o n ，t h a ti s i i i d ts a t i s f i e sg i t 畋= 一0 9 i1 1 2 t h i sp r o p e r t y i s i n d e p e n d e n to fl i n e s e a r c h m o r e o v e r , w h e ne x a c tl i n es e a r c hi su s e d ，t h em o d i f i e df rm e t h o da n d m o d i f i e dh sm e t h o dr e d u c et ot h es t a n d a r df rm e t h o d ，h sm e t h o d r e s p e c t i v e l y c o n s e q u e n t l y ，w h e nt h e ya r ea p p l i e dt om i n i m i z eas t r i c t l y c o n v e xq u a d r a t i cf u n c t i o n ，t h ep r o p o s e dm e t h o d st e r m i n a t ea tt h es o l u t i o no f t h ep r o b l e m f i n i t e l y u n d e rs o m e m i l dc o n d i t i o n s ，w ep r o v et h a tt h em o d i f i e d c o 玛u g a t eg r a d i e n t m e t h o d sw i t hs t a n d a r da r m i j ol i n es e a r c h c o n v e r g e s g l o b a l l yf o rn o n c o n v e xf u n c t i o n s m o r e o v e r ，u n d e rn o n m o n o t o n el i n es e a r c h ， w ep r o v et h a tm o d i f i e dh sm e t h o dc o n v e r g e sg l o b a l l yi nc h a p t e r4 f i n a l l y ， w ec a r r yo u ta nn u m e r i c a le x p e r i m e n t a t i o n a n dt h en u m e r i c a lr e s u l ts h o w s t h a to u ra l g o r i t h mi so fg o o dc o n v e r g e n c ea n de f f i c i e n c y ，a n di se s p e c i a l l y s u i t a b l ef o rs o l v i n gt h el a r g e s c a l eu n c o n s t r a i n e do p t i m i z a t i o np r o b l e m s i nc h a p t e r5 ，t h eg l o b a lc o n v e r g e n c eo fm o d i f i e df ra n dm o d i f i e dh s w i t hf i x e ds t e p l e n g t ha r ep r o v e d k e y w o r d s ：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 ；l i n es e a r c h ；s u f f i c i e n t d e s c e n td 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 v 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 作者签名： 盘至鲻 日期： 丝丕笸丝 关于学位论文使用权的说明 本人完全了解太原科技大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件、复印 件与电子版；学校可以采用影印、缩印或其它复制手段复制并保存 学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交 流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) 。 作者签名： 尘塑盐日期：竺翌：量：1 2 导师签名：j 筝l l 日期：2 竺& 二_ 堡一 第一章绪论 第一章绪论 本章简要介绍最优化问题的提出及判断目标函数最优解的常用最优性条件；然 后介绍了几种常用的无约束优化问题的导数下降类算法。 1 1 最优化问题的提出及最优性条件 最优化理论与方法是一个重要的数学分支，它所研究的问题是讨论在众多的方 案中什么样的方案最优以及怎样找出最优方案。例如，工程设计中怎样选择设计参 数，使得设计方案既满足设计要求又能降低成本；资源分配中，怎样分配有限资源， 使得分配方案既能满足各方面的基本要求，又能获得好的经济效益；生产计划安排 中，选择怎样的计划方案才能提高产值和利润；原料配比问题中，怎样确定各种成 份的比例，才能提高质量，降低成本；城建规划中，怎样安排工厂、机关、学校、 商店、医院、住户和其他单位的合理布局，才能方便群众，有利于城市各行各业的 发展；在人类活动的各个领域中，诸如此类，数不胜举。最优化这一数学分支，正 是为解决这些问题提供理论基础和求解方法，它是一门应用广泛、实用性强的学科。 早在1 7 世纪，英国伟大科学家n e w t o n 发明微积分的时代就已经提出极值问题。1 8 4 7 年法国数学家c a u c h y 在研究函数值沿什么方向下降最快时提出了最速下降法。1 9 3 9 年苏联数学家i b k 提出了解决下料问题和运输问题这两种线性规划问题的求解方 法。人们关于最优化问题的研究工作，随着历史的发展在不断深入。但是，任何科 学的进步，都受到历史条件的限制，直n - 十世纪三十年代，最优化这个古老的课 题还未形成独立的系统科学。 二十世纪四十年代以来，由于生产和科学研究的发展突飞猛进，特别是电子计 算机的日益广泛应用，使最优化问题的研究不仅成为一种迫切需要，而且有了求解 的有力工具。因此最优化理论和算法迅速发展起来形成一个新的学科。 一般来说，最优化问题的数学模型如下： m 毋f ( x ) ( 1 1 ) 其中，x d r 疗是决策变量，f ( x ) 是定义在天一上的实值函数，我们称厂( x ) 为问题 ( 1 1 ) 的目标函数，集合d 为问题的可行域，可行域中的点为可行点。 根据可行域d 的类型，非线性最优化问题分为约束最优化问题和无约束最优化 1 具有充分下降性的非线性共轭梯度法 问题。即当d = r ”时，无约束最优化问题为： m i nf ( x ) ( 1 2 ) 其中f ：r 玎专尺为非线性连续函数。 一般约束最优化问题通常可记为： 卿( x ) s j c c 艨。0 岩ie 二暑? m 聊2 铆，； n 3 ， f ( x ) = ， = 所+ 1 ，+ ，玎) ； 、7 其中e 和1 分别表示等式约束和不等式约束的指标集，q ( x ) 是约束函数。根据决策 变量、目标函数的要求不同，最优化可划分为多目标规划、动态规划、几何规划、 整数规划等若干分支。当目标函数和约束函数都为线性函数时，问题( 1 3 ) 称为线性 规划问题；当目标函数和约束函数中至少有一个是非线性函数时，问题( 1 3 ) 称为非 线性规划问题。 最优化问题的解分为局部最优解和全局最优解。其定义如下： 定义1 1 对于x 。x ，如果存在x 的某个邻域k ( x ) = x | | | x x 。i l 0 第一章绪论 1 2 求解无约束最优化的导数下降类算法 无约束优化问题算法大致分成两类：一类，在计算过程中只用到目标函数值， 不必计算导数，称为直接法；一类，在计算过程中要用到目标函数的导数，凡属这 类算法的我们称为导数下降类算法。常见的导数下降类算法有牛顿法、拟牛顿法、 最速下降法、共轭梯度法、最小二乘法等。其基本思想是：对于已有的迭代点黾， 首先确定一个使得目标函数f ( x ) 下降的搜索方向以，然后确定步长( 沿以方向 行进) ，从而得到下一个迭代点以= 以+ o r 。巩其中搜索方向巩应满足： 夥( ) 2 以 0 使目标函数f ( x ) 沿着以方向在点以处是下降的。步长吼的确定通常由非精确线搜 索得到。常用的非精确线搜索有： ( 1 ) a r m i j o 线搜索 基本的a r m i j o 线搜索是由l e o n e 【1 】等学者在考虑无约束优化的无导数方法时引 入的：求最小的非负整数m ，使得步长因子= 矿满足下列条件： f ( x k + t t k d k ) 0 ( 1 4 ) 改进的a r m i j o 型线搜索见文献【2 - 5 】 ( 2 ) g o l d s t e i n 1 4 线搜索 磊吒吨厂瓴+ 吼噍) 一厂瓴) 暖以 ( 1 5 ) ( 3 ) a r m i j o 和g o l d s t e i n 线搜索 f ( x k + 以) 厂( ) + 瓴或反 ( 1 6 ) f ( x k + 反) f ( x k ) + ( 1 8 ) a ：k g r 畋 ( 1 7 ) ( 4 ) 标准的w o l f e 线搜索 f ( x j , + 畋) f ( x k ) + & _ t k d d k ( 1 8 ) g b t + a 矗jd 芝。羲d k 3 ( 1 9 ) 具有充分下降性的非线性共轭梯度法 其中万和0 - 是满足0 万 0 - 1 的常数。 ( 5 ) 强w o l f e 线搜索 f ( x k + a k a k ) sf b 0 + 6 a 羲d t i g ( x k + a k d k ) r d k l - - 0 - g r d k ( 1 1 0 ) 当0 - = 0 时，必有g 乙。以= 0 因此强w r o l f e 线搜索是精确线搜索的一种推广。 ( 6 ) 广义的w o l f e 线搜索 f ( x k + o c k d 0sf b + 6 0 c k 酿d t q 畋g ( x k + 吼吮) r 吮0 2 吨 ( 1 1 1 ) 其中0 q 0 ，只要 i i g 。i l 占， ( 2 8 ) 则可接受以为一近似解。要证明算法对任何占 0 都能找到满意的近似解，应当有 u m i n f l l g , i i = 0 上式正是我们分析算法收敛性时需要证明的。虽然它比强收敛 。l i _ m 。1 1 1 1 = o 和点列收敛 舰恢一x i l = o 都弱，但它足以保证对任何g 0 ，都有后使得为满足式( 2 8 ) 的近似解。 2 2 1f r 方法 f l e t c h e r - r e e v e s 共轭梯度法是最早的非线性共轭梯度法，它是由f l e t c h e r 和 r e e v e l 4 1 在1 9 6 4 年将求解线性方程组的共轭梯度法推广用于求解优化问题 血= b ，x r ”而得来的，简称为f r 方法。f r 方法的收敛性分析最早是基于精确 线搜索。 2 2 - 2p r p 方法 1 9 6 9 年，p o l a k 、r i b i e r e 6 】和p o l y a k 7 】独立提出p i 冲方法。目前，该方法是已成 9 具有充分下降性的非线性共轭梯度法 为数值表现最好的共轭梯度法之一。由p r p 方法所定义的搜索方向可知，当该算法 迭代产生小步长时，搜索方向会自动向负梯度方向靠近，从而有效避免了f r 方法容 易产生几个连续小步长的缺点。之后，p o w e u 1 4 】等人证明了p i 冲方法的全局收敛性 ( 在s k = x k + 。一x k = 吼畋趋于零条件下) 。由文献 1 4 q h 的结果可知，在精确线搜索条 件下，可以得到p r p 方法对致凸函数的全局收敛。但在文献【2 0 】中，对于一般的 非凸函数，p o w e l l 给出了三维的反例，也就是说即使按c u r r y 原则选取步长因子，即 当吼为一维函数纯 ) = f ( x k + 口畋) t 0 ) 的第一个极小点时，p r p 方法可能在六 点( 其中任意一点都不是稳定点) 附近循环。p o w e l l 在文献【2 l 】中证明了当丹= 2 时， 对一般的非凸函数，采用c u r r y 原则的p i 冲方法是收敛的。如果假设每个搜索方向 均为下降方向，容易证明p r p 方法在非精确线搜索下对凸函数同样收敛。对一般的 非凸函数，在综述性文献 2 2 】中，p o w e l l 提议p i 冲方法中的参数矿为非负： 羼= m a x 矿，0 ( 2 9 ) 这样做是为了避免当i k i ”艮大时，相邻两个搜索方向会产生相反方向。在文献【2 3 】 中g i l b e r t 和n o e e d a l 采纳p o w e l l 的提议，在一定的线搜索条件下，给出了上述修正 p i 冲方法对一般非凸函数的全局收敛性结果。同时他们还指出，即使对一致凸的目 标函数，矿也可能为负，于是g r i p p o 和l u c i d i 2 4 1 构造了一种新的a r m i j o 线搜索， 并且证明了原始p i 冲方法在新的a r m i j o 线搜索下，对一般非凸函数的全局收敛性。 但数值结果不如p l 冲方法在弱w o l f e 线搜索下的数值表现。 2 2 3h s 方法 1 9 5 2 年，h e s t e n e s 和s t i e f e i s 提出了h s 方法，该方法与p l 冲方法相比一个重 要性质是：不论线搜索是否精确，畋r ( 一g “) = 0 总是成立的。当线搜索精确时由 于以一，r ( 一g ) - - 1 1 鼠一i | 2 ，则有矽量矿由上述对p r p 方法的收敛性分析可知， h s 方法在精确线搜索下对一般非凸目标函数有可能不收敛。在适当的线搜索条件下 当展= m a x , a s ，0 ) 时，该方法的具有全局收敛性证明由g i l b e r t n o c e d a l 在文献【2 3 】 中给出。后来戚厚铎等等人团1 对展册又做了修正：展= m x o ，i i l i n ，南) ，并 在没有充分下降条件下证明了新方法的全局收敛性，在文献 2 6 】中h u a n g 等人给出 1 0 第二章非线性共轭梯度法简介 一种修正麒胪：涨，当1 时，h u a n g 等人棚 线搜索下证明了该方法的全局收敛性，并且数值结果也表现不错。 2 2 4c d 方法 c d 方法又称为共轭下降法( e o n j u g a t cd e s c e n tm e t h o d ) ，该方法是在1 9 8 7 年由 f l e e h e r 1 0 】首先引入的。c d 方法的一个重要性质是：只要强w o l f e 线搜索条件中的 参数o r o ，i i 畋i | 2 可能以指数级数的方向增长。基于此，他们给出了对v c r 2 0 ， c d 方法在满足推广的w o l f e 线搜索时不必收敛。另外他们还设计了一个目标函数是 凸二次函数时，条件仃，= 0 保证c d 方法收敛是必要的。由上述讨论可知，虽然c d 方法在强w o l f e 线搜索下对一般参数即可保证每步产生一个下降的搜索方向，但c d 方法的全局收敛性却不是很好。因为在产用精确线搜索时，舻量矽，可见c d 方 法的数值表现与f r 方法类同，在实际计算中与f r 方法相差不大，数值表现并不是 很理想。 2 2 5d y 方法 d y 方法是由我国学者戴或虹与袁亚湘1 1 i 在1 9 9 5 年提出的一种新的共轭梯度法。 当线搜索精确时d y 方法与f r 方法等价。在文献 2 9 】中戴或虹与袁亚湘严格证明了 产用w o l f e 线搜索时，d y 方法每步产生的搜索方向均下降方向，且全局收敛。由此 可见，在不使用强w o l f e 非精确线搜索而仅使用w o l f e 非精确线搜索对共轭梯度法的 收敛性进行讨论也可以得到较好收敛性结果。对于d y 方法，戴或虹与袁亚湘在文 献【1 3 】中，在不使用任何线搜索的情况下，讨论了其内在性质，给出了方法在远离最 优点时，充分下降条件碣一c 慨| | 2 对大部分的迭代点列必成立。利用此性质，可 证明d y 方法在一般的线搜索下是全局收敛的。 具有充分下降性的非线性共轭梯度法 2 2 6w - y 3 l 方法 近年来，韦增欣等【3 0 】提出一种新的共轭梯度法： 矿：垫掣 g k - i g k - i 事实上它是p i 冲方法的修正，后来被称为w y l 方法，并建立了在弱w r o l f e 线搜索、 g r i p p o l u c i d i 线搜索【2 】下的全局收敛性，得到了较好的数值表现。文献【3 l 】证明了 当仃 0 ，使得 0 9 ( 功一g ( y ) 8 三0 x 一叫l ，v x ，y q ( 2 1 0 ) 由假设条件可知，存在一常量 0 ， 使得 8 9 ( x ) 0 ，v x q 1 3 ( 2 1 1 ) 第三章一种修正的f r 方法 第三章一种修正的f r 方法 本章，对原始f r 方法进行修正，提出一种修正的f r 方法，并在a r m i j o 型线搜 索下证明了修正f r 方法的全局收敛性，通过大量的数值试验来说明新方法的有效 性。 3 1 引言 f r 方法是求解无约束优化问题( 1 2 ) 的最早的非线性共轭梯度法，它是i 妇f l e t c h e r r e e v e s 4 1 于1 9 6 4 年将求解线性方程组的共轭梯度法推广用于求解优化问题 a x = b ，x r ”而得来的。f r 方法具有如下形式： 以+ l = 黾+ 以 k = 0 , 1 ，( 3 1 ) 其中由某种线性搜索得到，搜索方向吨为 以= 二耋，+ 肫，主主：) 8 2 ， 参数展由以下公式给定： 俐r = 器 ( 3 3 ) f r 方法在实际的数值计算中表现并不是十分理想，p o w e l l 分析了f r 方法在精确 线搜索下有可能连续产生小步长，这说明f r 方法可能收敛十分缓慢。但z o u t e n d i j k i 正 明t f r 方法采取精确线性搜索时对一般非凸函数总是全局收敛性1 5 】。由于精确线性 搜索非常昂贵，因此，在实际计算中人们通常使用非精确线性搜索。 使用非精确线性搜索研究f r 方法的一个重要难点是，充分下降条件 一g ：d k a 1 9 七1 1 2 ( 3 4 ) ( 其中a 0 为某常数) 有可能不成立，而对于精确线性搜索g ；以= - i l g 。1 1 2 总是成立 的。 如果采取强w o l f e 线性搜索( 1 8 ) 和( 1 1 0 ) ，a 1 b a a l i t l 6 】在1 9 8 5 年证明了取参数 1 5 具有充分下降性的非线性共轭梯度法 仃 i i 时，戴或虹和袁亚湘给出了反例，说b 芟j f r 方法可能因为产生一 二 个上升的方向而导致不成功。 从以上分析可以看出，f r 方法能否产生下降方向依赖于选取什么样的线性搜索。 那么能否有不依赖线性搜索的某种合理的修正f r 方法，使得修正后的f r 方法能产生 充分下降方向，并且对于目标函数非凸时全局收敛? 本章的目的就是力求寻找这种 方法。在第2 节我们给出了一种满足充分下降条件的修正f r 方法；在第3 节中我们分 析了修正f r 方法全局收敛性；最后我们对算法进行了数值试验，其结果在第4 节中给 出。 3 2 算法 为了改进f r 算法，使其产生的方向是f 的充分下降方向，我们在确定反的公式 ( 3 2 ) 中引入参数吼，即取以具有如下形式： 畋= 盛 + 胪钆咖。，甾 ( 3 5 ) 其中 驴爵， ( 3 6 ) f l 拭( 3 3 ) 、( 3 5 ) 和式( 3 6 ) 得 以叫盯i i + 皆一背叫盯i i ( 3 7 ) 因此搜索方向以具有充分下降性。此外，如果线性搜索是精确的，则g ；d k = 0 此时 由式( 3 6 ) 知吼= 0 ，即上面的方法退化为标准的f r 方法，特别，该算法具有二次终 止性。 基于上面的讨论，我们提出了下面修正的( m o d i 6 e d ) fr 方法。 第三章一种修正的f r 方法 算法3 1 步骤1 给定起始点，参数 o ，p ( 0 ，1 ) ，万( o ，1 ) ，s 0 ，令k - 0 步骤2 若恬。| | ，使其满足 f ( x k + 吼畋) ( 以) 一融1 28 矾| 1 2 ( 3 8 ) 步骤5 计算下一个迭代点诈+ l = 黾+ 吼畋， 步骤6令k = k + l ，转步骤1 由于以是在吒处的下降方向，因而算法是适定的。 3 3 全局收敛性 引理3 3 1 f 1 5 】设目标函数满足本文假设条件，考虑一般方法魂+ l = 黾+ a k d k ， 其中以满足t 占，v k = 1 , 2 ， 由式( 3 5 ) 得 d k + ( 1 + 幺) g t = 展d k - 1 上式两端取模平方，并移项可得 i i d y l l 2 = 群恢一。卜2 ( 1 + o k ) d ： g 。一( 1 + 吼) 2 i g 。2 = 所阪。8 2 + 2 ( 1 + o k ) l l g 七i 2 _ ( 1 + 幺) 2 i i g 七 1 7 具有充分下降性的非线性共轭梯度法 = 所恢玎+ l l s 。1 1 2 ( 1 一钟) 将式( 3 3 ) 代入式( 3 11 ) ，两边除以( g r d k ) 2 ，可得 即得 所以有 1 2 ( d k ) 2 与引理1 中z o u t e n d i j k 条件矛盾 + ：j 噬+ 上一旦 i i g 。一0 4 0 9 。1 1 20 9 。1 1 2 善k 丽1 譬 ( 氍t 以) 2 2 i a ( g ；以) 2 1 2 。证毕。 k l 一醒 蚓1 2 澎k i 妻= 佃 定理3 3 2 若满足假设条件h 1 、h 2 ，r x 七 是算法1 产生的序列，则有 舰i = 0 证明由式( 3 5 ) 得以+ = 孱d k l 一吼瓯 上式两端取模平方，并移项可得 2= 硎以_ l i | 2 2 d r g 七一1 22 a o k g ；d k 一+ o k 2 1 2 = 孱2 卅d - l i | 2 + 1 2 2 , s k o k g ；d k 一+ 皖2 蚓1 2 将式( 3 3 ) 与( 3 6 ) 带入上式得 i z ：划出剑 i i g 川4 + l l g 1 8 川2 一学 = 蚓1 2 ( 3 1 1 ) ( 3 1 2 ) ( 3 1 3 ) 划陬 i 一一 一 = 以一瓯 = 上蚶 + - r q 七一 七d g 百( g r d k ) 2 ：蚓1 2 智1 2 俐眦” 在这一节，我们将给出原始f r 方法和本章所修i e f r 方法在a r m i j o 线性搜索和强 w o l f e 线性搜索下的数值结果。在a r m i j o 线性搜索( 3 8 ) 中，取精度占= 1 0 _ 6 ，取参数 = 0 9 ，p = 0 6 ，万= 0 5 数值计算结果如表3 1 ( a r m i j o 线性搜索下f r 方法和修正 f r 方法的数值结果) 所示；在强w o l f e 线性搜索( 1 8 ) 和( 1 1 0 ) 中，取参数万= 0 0 1 ， o r = 0 6 ，终止条件为恢i | o ，p ( 0 ，1 ) ，万( 0 ，1 ) ，占 0 ，令k _ 0 步骤2 若恬七| i 0 ，满足 i i g k i i 占，1 1 d ：- 儿一。i i - a s ，v k = 1 ，2 ， ( 4 7 ) f i d 。i i - - b l l g 。l i ，v k = l ，2 ， ( 4 8 ) 证明 由式( 4 1 ) 与式( 4 2 ) 对以的定义，以及式( 2 1 0 ) 、式( 2 11 ) 和式( 4 7 ) 可得 俳ii i 卅i i 2 嗤掣 +掣ildk-,iia。s 再由式( 4 5 ) ，知存在常量c ( o ，1 ) 和整数，使得对所有k k o ，有 所以，对任意的k k o ，有 箬训吨小i i i i c 雳吼州如 l i d , i i - 0 ，使得 l i g i i i s , v k = 1 州2 一 由式( 4 3 ) 并1 1 ( 4 5 ) 可知，者：l i m 。一i n fa k o ，则1 1 巴蝉恬女0 = 0 ，这与假设矛盾。 若l i m i n f a 。= o ，则存在无限子集k ，满足 。l i 口吼= 0 i e k j “ ( 4 9 ) ( 4 1 0 ) 第四章一种修正的h s 方法 由式( 4 4 ) ，对v k k 有 f ( x k + ( p ) a ) f ( x k ) - 8 ( t t k p ) 2i i 噍1 1 2 ( 4 11 ) 再由中值定理与式( 4 3 ) 和式( 2 1 0 ) ，对充分大的k k ，存在常数f ( o ，1 ) ，使得 f ( x k + ( 吼p ) 畋) 一( ) = ( p ) g ( x k + t ( a k l p ) d 七) r 畋 = ( 口j i p ) g ；d 七+ ( 口i p ) g ( x 七+ r ( a 七p ) d | | ) 一g ( x 七) 】rd 七 ( a k i p ) g r 以+ 三( 吼p ) 2l i 以0 2 = - ( o c 七i p ) l l g 。i | 2 + l ( m p ) 2o 以| | 2 ( 4 1 2 ) 由式( 4 11 ) 与( 4 1 2 ) n - i 得，对充分大的k k ，有 i i g t i l 2 + 万) 位t i p ) l l d tj j 2 又因式( 4 1 0 ) ，有1 k l 哦f f “g 七8 = o 与假设矛盾。证毕。 4 1 4 数值试验 选取如下算例对本章提出的展公式进行数值试验。 其中厶f _ l = ( x 2 ，一x 2 2 h ) ， 。= ( 1 一x 2 ) ，初始点( 一1 2 ，1 ，一1 2 ，l ，一1 2 ，1 ) 取精度占= 1 0 - 6 ， 参数万= 0 5 ，p = 0 6 ，= 0 9 数值计算结果如表4 i 所示，其中k 表示迭代次数，t 表示 算法运行时间，s 是时间单位秒。 表4 ia r m i j o 线性搜索下修正h s 法和原始h s 方法的数值结果 t a b l e4 1t h en u m e r i c a lr e s u l t so fh sm e t h o da n dm o d i f i e dh sm e t h o dw i t ha r m i j ol i n es e a r c h 修正h s 算法原始h s 算法 维数 kt s i i g 。0 k t s l i g 七0 1 0 0 03 60 5 5 6 08 9 3 4 3 e 0 0 72 0 81 3 0 7 8 07 0 216 e 0 0 7 2 0 0 03 50 9 2 2 2 02 4 2 3 3 e 0 0 71 1 93 5 0 2 9 7 07 38 9 4 e 0