（计算数学专业论文）一类共轭梯度法的研究.pdf

塑塞堕窒塾墨查堂堡主堂焦笙茎 摘要 共轭梯度法在二十世纪六七十年代是国内外学者研究的热点。近年来，随着计算 机的飞速发展以及实际问题中大规模优化问题的涌现，共轭梯度法又一次成为人们关 注的热点。 本文主要研究了共轭梯度法的算法和理论，得到了一些理论和数值结果。文中首 先介绍共轭梯度法的发展概况，对几种著名的共轭梯度法f r 方法，p r p 方法，h s 方法，c d 方法和d y 方法的全局收敛性，全局有效性及数值计算作了综述。然后对 共轭梯度法理论研究的基础上，得到了几种新的共轭梯度法，并对它们的收敛性进行 了分析，证明了新算法的全局收敛性。大量数值试验结果也表明了这些算法的有效性。 同时对已有的共轭梯度法进行了一些理论分柝，得到了一些有益的结论。 关键词：无约束优化，共轭梯度法，线搜索，w o l f e 条件，全局收敛性 二鲞苎堑塑星鲨塑竺塑 一一一 a b s t r a c t c o n j u g a t eg r a d i e n t m e t h o d e n j o y e dg r a t e i n t e r e s t a m o n g s t b o t hd o m e s t i ca n d o v e r s e a sr e s e a r c h e r sb e t w e e n1 9 6 0 sa n d1 9 7 0 s n o w , t h er a p i dd e v e l o p m e n to fc o m p u t e r a n dag r a t ed e a lo fl a r g es c a l eo p t i m i z a t i o np r o b l e m sm a k et h er e s e a r c hi nc o n j u g a t e g r a d i e n tm e t h o d r e v i v e i nt h i st h e s i s ，w em a i n l yd i s c u s st h ea l g o r i t h ma n dt h et h e o r yo fc o n j u g a t eg r a d i e n t m e t h o d t h es t r u c t u r eo ft h i sp a p e ri so r g a n i z e da sf o l l o w s ： i nt h ef i r s tc h a p t e rw es u r v e yt h eh i s t o r yo fc o n j u g a t eg r a d i e n tm e t h o d ，a n dd i s c u s s f i v e c o n j u g a t eg r a d i e n tm e t h o d sr e s p e c t i v e l yw h i c ha r ef rm e t h o d ，p r pm e t h o d ，h s m e t h o d ，c dm e t h o d ，d ym e t h o d t h e ya r ec u r r e n t l yc o n s i d e r e dt o b ew e l l - k n o w n m e t h o d sf o rl a r g es 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 ne a c hs e c t i o n ，w ed i s c u s s e v e r y m e t h o d sg l o b a l c o n v e r g e n c ep r o p e r t i e sa n d n u m e r i c a lb e h a v i o r se t c i nt h es e c o n dc h a p t e r , w e d e v e l o ps e v e r a ln e wc o n j u g a t eg r a d i e n ta l g o r i t h m s ，e x p l o r e t h e i r c o n v e r g e n c ep r o p e r t i e s a n d a n a l y z e t h en u m e r i c a l r e s u l t s b yc o m p a r i n gt h e n u m e r i c a lr e s u l t s ，w ec a nf i n dt h ea d v a n t a g e so ft h e s en e w a l g o r i t h m s w h a t sm o r e ，w e m a k ead e e pi n v e s t i g a t i o no nt h eh sm e t h o da n do b t a i na c o n v e r g e n c e r e s u l tt h e o r e t i c a l l y i nt h el a s tc h a p t e r , w es u m m a r i z et h ec o n t e n t so ft h ea b o v et w oc h a p t e r sa n d p r o p o s e s e v e r a lp r o b l e m st h a ta r ew o r t h w h i l et of u r t h e rr e s e a r c h k e yw a 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 es e a r c h ，t h e w o l f e c o n d i t i o n ，g l o b a lc o n v e r g e n c ep r o p e r t y 壹室堕窒堕丕查堂堡主堂垡笙苎 前言 无约束优化问题在许多重要领域如工程、国防、经济、管理等都有着直接的应用。 在计算数学中的数值逼近、常微分方程数值解、偏微分方程中的变分原理、微分方程 反演以及非线性代数方程数值解等分支也可经常见到。另外，许多约束优化问题也可 借助罚函数等方法转化为无约束优化的形式进行求解。 一般而言，当目标函数的维数并不很大时，拟牛顿方法是求解无约束优化问题的 非常有效的一类方法。而且这类方法在理论分析和算法上都已经相当成熟。但用共轭 梯度法来求解却有很强的应用背景。在许多应用领域如电力分配、石油勘探、经济管 理和天气预测等提出来的无约束优化问题规模往往很大，这时由于拟牛顿方法需要存 储大型矩阵而往往失效。而共轭梯度法只需存储几个刀维向量就显得特别有效。共轭 梯度法自1 9 6 4 年f l e t c h e r 和r e e v e s 首先提出至今，各国学者都一直深入研究并取得 了许多令人可喜的成果，使得共轭梯度法在理论和应用上的发展日趋进步。但共轭梯 度法的理论和应用还有待于进一步开拓和完善，因而共轭梯度法仍然是一非常值得研 究的方向。 本文在第一章中概述了五种著名的共轭梯度法。这五种方法是：f r 方法、p r p 方法、h s 方法、c d 方法和d y 方法。对每一种方法的特点、全局收敛性、全局有效 性等理论和数值效果方面做了较为系统的概述。在第二章中我们对共轭梯度法深入探 讨，提出了几种新的共轭梯度法对它们的收敛性进行了分析和证明。对这些算法我 们进行数值实验，大量的数值实验结果表明了这些算法的有效性。此外还对h s 方法 的收敛性进行了分析。这些都进一步丰富了共轭梯度法的内容。在本文的最后，我们 对前两章的内容作了总结，指出日后还需进一步深入研究的一些问题。 二耋苎堑塑堕鲨堕竺塞 第一章共轭梯度法概述 共轭梯度法是最优化中最常用的方法之一。在所有需要计算导数的优化方法中， 最速下降法是最简单的，但它速度太慢。拟牛顿方法收敛速度很快，被广泛认为是非 线性规划的最有效的方法。但拟牛顿方法需要存储矩阵以及通过求解线性方程组来计 算搜索方向，这对大规模问题几乎是不可能办到的。而共轭梯度法算法简便，存储需 求小，收敛速度又比最速下降法快，特别适合求解大规模问题。在石油勘探、大气模 拟、航天航空等领域出现的大规模问题常常是利用共轭梯度法来求解的。 共轭梯度法最早由计算数学家h e s t e n e s 和几何学家s t i e f e l 在二十世纪五十年代初 为求解线性方程组 爿x = b ，x r ” 而独立提出的( 参见文献【l 】) 。1 9 6 4 年f l e t c h e r 和r e e v e s 将此方法推广到非线性最优 化，得到了求一般函数极小值的共轭梯度法( 详见文献【2 ) 。 求解无约束优化问题 m i n f ( x 1 ，x r “ ( 1 1 ) 的共轭梯度法具有如下形式： x t “= x 七+ 口 d ， ( 1 2 ) 巩= k 兹钆，越 ， 其中g 。= v f ( x 。) ，d k 为搜索方向，而吼 0 是通过某种线搜索获得的步长。纯量从 的选取应满足共轭性，即当f ( x ) 为严格凸二次函数且采用精确线搜索时，由方法 ( 1 2 ) ，( 1 3 ) 产生的搜索方向d 。关于f ( x ) 的海赛阵共轭。此外，当f ( x ) 为严格凸 二次函数时，共轭梯度法在精确线搜索下具有有限步终止性，但对一般连续可微目标 函数，这一性质很难保证。 屏的不同取法构成了不同的共轭梯度法，比较常见的展的计算公式有 ( 1 4 ) 2 盟蚶 | | 船 反 塑坚璺至璺奎丕兰堡圭量堡堕苎 圹5 瞥， ( 1 5 ) 屏“= 黜， s ， 胪：理业。 ， 近年来，d a i ，y u a n ( 参见文献 3 】) 又提出了屈的另一计算公式： k d y = 搞。 幻 对于无约束优化问题( 1 1 ) ，我们假定其中的目标函数厂( 曲满足： 假设1 1 ：( 1 ) ，( x ) 在水平集三= 扛r i f ( x ) 0 ，使得 j i v ( x ) 一v s ( z ) l i l l x 一譬m v x ，譬n ( 1 9 ) 共轭梯度算法可概括如下 算法1 1 ： 步l ：给定x 1 r “，s ( o ，1 ) ； d = 一g ，= 一v f ( x ) ，k = 1 。 步2 ：如果8 鼠j | 占，则停： 利用某种线搜索方法求吼 耳+ l = t + 吼d i 。 步3 ：利用某公式计算反+ ，： d i + l = 一g i + i + 孱+ i d i 。 k = k + l ，转步2 。 一类共轭梯度法的研究 在算法1 1 的步2 中，线搜索方法是用来确定步长的。线搜索可分为精确线搜索 和非精确线搜索两大类。下面介绍几种确定步长的原则： ( 1 ) 极小化原则：沿射线e 。+ 吼陋 o ) 求，o ) 的极小，即选取吼 o 使得 f ( x 。+ 口。d k ) = m i n f ( x , + a 以) 口 o 。 ( 1 1 0 ) ( 2 ) c u r r y 原则：选取吼 0 为 口。：m i n k 0 1 d , r g ( x k + 耐。) = o j 。 ( 1 1 1 ) 上述原则都要求吼是函数厂( t + a d 女) ，口 0 的稳定点，故称为精确线搜索。在 无约束优化算法的收敛性分析中，这两种线搜索是非常重要的。但在计算机上实现时， 即使允许有一定误差，也要付出很大代价。因此通常人们采用如下一些较弱的步长原 则，它们属于非精确线搜索。 ( 3 ) w o l f e 原则：给定参数0 p 盯 0 ，使得 f ( x ) 一f ( x l + 口k d ) 一p 口d i 。g k ( 1 1 2 ) d k 7 9 ( x k + 吼d i ) o f f , r g i 。 ( 1 1 3 ) ( 4 ) 强w o l f e 原则：给定参数0 p 0 为 吼= 舻， ( 1 1 5 ) 其中整数m 。等于 巩。= m i n 如o 厂( 孔) 一厂( 以+ 3 y d 。) 一删鼠7 矾j 。 ( 1 1 6 ) 在对目标函数的假设1 1 成立时，可以证明满足( 3 ) ，( 4 ) 和( 5 ) 原则的步长是 存在的。 在算法1 1 的步3 中，若屈+ 1 分别按( 1 ，4 ) ，( 1 5 ) ，( 1 6 ) ，( 1 7 ) ，( 1 8 ) 取值， 则称相应的算法为f r 方法，p r p 方法，h s 方法，c d 方法和d y 方法。本章将在以 下几节中对上述方法从全局收敛性，有效性等方面加以介绍。 4 南京航空航天大学硕士学位论文 下面的引理在分析一般的下降算法的收敛性时经常要用到，它是由w o l f e 和 z o u t e n d i j k 给出的( 见文献 4 】和 5 ) 。 引理1 2 ：设f ( x ) 满足假设1 1 ，考虑形如( 1 2 ) 的一般方法，其中d i 满足以。g i 0 ， 步长因子吼满足w o l f e 条件即( 1 1 2 ) 式矛n ( 1 1 3 ) 式，其中0 p 盯 t a n 吼锗。 ( 1 z ，) 假设在第k 步，幺一q “- ，则算法产生的步长可能非常小，从而梯度的变化g 。一g 。 也很扎以至于谢趋近于，。由z - 胤在第m 步钆也接近三，因此下 一步的步长仍可能很小。 由于上述缺点，f r 方法可能收敛很慢，这解释了f r 方法在数值计算中有时并不 十分理想的原因。 由于精确线搜索非常昂贵，在实际计算中人们通常使用非精确线搜索。当采用强 w o l f e 线搜索即吼满足( 1 1 2 ) 和( 1 1 4 ) 时，a i b a a l i ( 1 9 8 5 ) 给出了结论：当 0 p c r ：1 ，他们给出了反例， 表明f r 方法可能因为产生一个上升方向而导致失败。在这些分析基础上，他们得到 6 南京航空航天大学硕士学位论文 如下较为完善的定理 定理1 3 ：设目标函数f ( x ) 满足假设1 1 ，考虑f r 方法( 1 2 ) ，( 1 3 ) 和( 1 4 ) ，若 满足一般强w b l f e 条件即( 1 1 2 ) 和 盯l g k r d d 女g ( z i + 口女d 女) 一盯2 9 l t d 女， ( 1 2 2 ) 其中0 p 盯l l ，盯2 0 ，则 ! i m 。i n f 恢g i i = 0 成立的充要条件是q + o - ：1 。 注意：在假设1 1 成立的条件下，对任意耳r “，若以均为下降方向，则存在步长 满足一般强w o l f e 条件( 1 1 2 ) 和( 1 2 2 ) 。( 参见文献【9 】) 1 2p r p 方法和h s 方法 p r p 方法是目前认为数值表现最好的共轭梯度法之一。与f r 方法不同，在精确 线搜索下，当p r p 方法产生一小步长时具有自动靠近最速下降法的优点。 当线搜索精确时，( 1 1 9 ) 和( 1 2 0 ) 仍成立。由( 1 5 ) 显然有 如虹挚， ( 1 2 3 ) 临 0 由( 1 1 9 ) ，( 1 2 0 ) 及( 1 2 3 ) 得 t a n o 0s e c 吼掣，( 1 2 4 ) 故若幺接近三且导致步长吒。一砟非常小以及l 旧一戥i i 恬。则由( 1 2 4 ) 知 t a n 吼“ 0 j 的第一个极小点， p r p 方法也可能在六点之间循环，而其中任意一点都不是目标函数的稳定点。 当采取非精确线搜索时如强w o l f e 搜索，即使f ( x ) 一致凸且参数盯( o ，1 ) 充分 小，p r p 方法都可能产生一个上升搜索方向。但若每个搜索方向下降，则采取非精确 线搜索的p r p 方法对凸函数有全局收敛性( 见文献 1 0 1 ) 。对一般非凸函数，p o w e l l 建议限制p r p 方法中的参数a ”为非负。这样做的目的是避免i k l 很大时，相邻两 搜索方向会趋于相反。g i l b e r t 和n o c e d a l 考虑了p o w e l l 的上述建议，在适当的线搜 索条件下，建立了一种修正p i o 方法，并给出其对一般非凸函数的全局收敛性( 见 文献 1 2 1 ) 。他们的结果可写成如下定理。 定理1 5 ：设置为任一给定初始点，f ( x ) 满足假设1 1 ，考虑( 1 2 ) 和( 1 3 ) 构成的 基本算法，若厂( x ) 的水平集有界，步长吼满足w o l f e 条件( 1 1 2 ) 和( 1 1 3 ) 且充 分下降条件吼7 以一c 恬。0 2 对某常数c 和所有j j 成立，( 1 3 ) p k = m a x 溉e r e , 0 ， 则对该方法有舰i n f l l g t i i - - o 。 对于h s 方法，它有一个重要性质是共轭关系式 以7 y k 一= 0 无论线搜索是否精确总是成立的( 由( 1 3 ) 和( 1 6 ) 直接可得) 。 当线搜索精确时，因吐一。t y 。- - i i g 。0 2 ，于是有反”= 屏”。故由上面对p i 冲 方法的介绍知，采取精确线搜索的h s 方法对一般非凸目标函数不一定收敛。h s 方 法的计算表现与p r p 方法很相似，数值表现较好，然而关于h s 方法的收敛性结果却 r 塑塞堕窒堕鲞查堂堡主堂堡堡塞 很少。在第二章中我们将讨论当采用非精确线搜索时h s 方法的理论性质，得到了 h s 方法对一致凸函数全局收敛的一些充分条件。 1 3c d 方法 c d 方法的一个重要性质是当吼满足一般强w o l f e 条件即( 1 1 2 ) 和( 1 2 2 ) ，其 中0 p 吼 1 , 0 盯： 1 ，则c d 方法可以保证每一搜索方向均为下降方向。 事实上，因一g 。r 矾= 一r ( 一鼠+ 单以- 1 ) 一“ 一ig t i = l l g k l l 2 ( 1 + 麓) ， 只要l k 。l | 0 ，由( 1 2 2 ) 得 l - 静m 吼 ( 1 2 5 ) 从而有g 女。d 0 。 因此当满足强w o l f e 条件即( 1 1 2 ) 和( 1 1 4 ) ，参数0 0 - 1 时，c d 方法在 每次迭代便产生一个下降搜索方向。而由1 1 节和1 2 节知，f r 方法和p r o 方法在 这时对一致凸函数都有可能产生一个上升搜索方向。 当吼满足一般强w o l f e 条件即( 1 1 2 ) 和( 1 2 2 ) ，其中0 p 0 - l 1 ，0 - 2 = 0 时， c d 方法具有全局收敛性，见如下定理。( 见文献【3 】) 定理1 6 ：设x 为任一给定初始点，f ( x ) 满足假设1 1 ，考虑c d 方法( 1 2 ) ，( 1 3 ) 和( 1 7 ) ，其中步长吼满足一般w o l f e 条件( 1 1 2 ) 和( 1 2 2 ) ，这里0 p 0 1 1 ，盯2 = 0 则啤i n 啦。i l - - 0 。 由上可见虽然使用一般强w o l f e 线搜索的c d 方法在每步产生一个下降方向，但 一类麸轭梯度法的研究 其收敛性质并不十分好。 此外，由于线搜索精确时，鼠c d = 展”，因此c d 方法与f r 方法有着同样的数 值缺点即可能连续产生小步长而不恢复。在实际计算中c d 方法的数值表现和f r 方 法相似，它们都常比p r p 方法要慢。 1 4d y 方法 d y 方法是由d a i 和y u a n 在1 9 9 5 年首先提出的。d y 方法是一种具有良好收敛 性质的共轭梯度法。 当线搜索精确时，鼠“= a ”，此时全局收敛性同f r 方法。 当采用非精确搜索时，d a i 和y u a n 证明了其全局收敛性( 见文献【3 ) 。 定理1 7 ：设x 。为任一给定初始点，f ( x ) 满足假设1 1 ，考虑( 1 2 ) ，( 1 3 ) 和( 1 8 ) 构成的d y 方法，吼满足w o l f e 条件( 1 1 2 ) 和( 1 1 3 ) ，0 p 盯 1 ，则对所有尼 都有鼠7 1 d t o 进一步地，k 丕：n i m i n f g 。1 1 = o 。 由此可见，在共轭梯度法领域不使用强w o l f e 线搜索而使用w o l f e 线搜索也可以 获得很好的收敛结果。而且，定理1 7 对目标函数0 ) 的假设也很弱，它不需要水 平集有界的假定，而和引理1 2 所需的函数假定一致。此外，使用w o l f e 线搜索的 d y 方法还可推广到由( 1 2 ) 和( 1 3 ) 构成的一般方法。 定理1 8 ：设x 。是初始点，厂( z ) 满足假设1 1 ，考虑( 1 2 ) 和( 1 3 ) 的一般方法，其中步 鼬t 满足w o l f e 条件( 2 ) 和( 1 1 3 ) ， 2 务，若参数展使得 斗一等，”l 一而1 j 则必有! 骢i n f | | g | | = o 。 南京航空航天大学硕士学位论文 此定理证明见文献f 1 3 】。 在不使用任何线搜索的情况下，d y 方法还有其固有的内在性质即方法在远离最 优点时，充分下降条件7 矾一c 恬。j 1 2 必对大部分的迭代点列成立。利用这一性质 可得到d y 方法在一般线搜索条件下的全局收敛性，详见文献 1 4 】。 第二章一类共轭梯度法的研究 由于共轭梯度法没有一种统一的参数屈的公式，因而无法用一种统一的手段去分 析共轭梯度法的理论性质。由前面一章对几种常用的共轭梯度法的诸方面介绍，我们 知道不同的共轭梯度法其全局收敛性和数值表现也大不相同。例如，f r 方法的全局 收敛性很好，数值表现却往往比p r p 方法要差；与之相反，p r p 方法的数值表现虽 然往往比f r 方法要好，但即使采用精确线搜索，这种方法也不一定收敛。再譬如， f r 方法在定理1 3 条件下全局收敛，而c d 方法在同样条件下只能得到方法的下降性， 当且仅当盯，= 0 时才能得到全局收敛性。对于d y 方法，只要目标函数厂( 曲满足假 设1 1 ，步长满足w o l f e 原则( 而不必强w o l f e 原则) 即可得其全局收敛性。从数值表现 来看，d y 方法也是一种比p r p 方法更有效的方法。 以上所述都表明了共轭梯度法的方法和分析具有多样化的特点。多年来，学者们 对这些不同共轭梯度法的理论分析和研究使共轭梯度法的理论更加完善，也为我们提 供了产生更有效的共轭梯度法的思路。在本章中，我们对共轭梯度法进一步探讨研究。 首先，提出了一种带参数的共轭梯度法族，它可视为几种著名共轭梯度法的推广，对 它的收敛性给予分析及证明，并给出数值实验结果，进一步丰富了共轭梯度法的内容； 其次，我们对h s 方法进行了深入研究给出了h s 方法对一致凸函数全局收敛的一 个充分条件；最后，我们结合不同共轭梯度法的特点，提出了- - t e e 较为有效的混合共 轭梯度法，它同样具有全局收敛性，数值实验结果也表明它的效果较好。 2 1 一种带参数的共轭梯度法族 对于无约束优化问题 m i n f ( x ) ，x r ” 可用共轭梯度法求解。它具有如下形式 工“l2 t + 口i d k ( 2 1 ) ( 2 2 ) 南京航空航天人学硕士学位论文 驴k 该越 旺， 展的几个著名公式在第一章己叙述过。此外，文献【1 5 】中又提出了l s 方法，即由( 2 2 ) 和( 2 3 ) 确定的方法中，夙由如下公式 展“：建掣 ( 2 4 ) 决定。注意到从”与鼠“有相同形式的分子，我们取 8k = g t _ y k - ir g + 一，+ ( 1 ) l l g 。一，| 2 ( 2 5 ) 其中y h = g g n ，0 a 1 。这样由( 2 2 ) ，( 2 3 ) 和( 2 5 ) 定义了一族带参数 的共轭梯度法。显然如果取0 和1 ，则方法( 2 2 ) ，( 2 3 ) 和( 2 5 ) 分别对应了 p r p 方法和l s 方法。 在这一方法中，通常吼的选取由线搜索获得。考虑这族共轭梯度法的收敛性。 若采用精确线搜索有以7 9 ( x 。+ 吼t ) = 0 ，又由( 2 3 ) 有一既一t 以一= l l g n k 2 。 因此当采用精确线搜索时，对任意实数0 1 有反= 展”，k 2 ，此时该族共 轭梯度法的全局收敛性与p r p 方法在精确线搜索下的全局收敛性相同，即其对一致 凸函数全局收敛。下面着重考虑非精确线搜索的情形。 设吼满足强w o l f e 条件： f ( x ) 一厂( 黾+ “ d k ) 一户口 g 女。d k ， ( 2 6 ) l g ( “+ 吼d k ) 7 d k c r g 畋| ， ( 2 7 ) 其中0 户 0 均有 厂( x ；) 一，( x 。+ 口。d 。) 堕产i i g 。1 1 2c 。s 2 ( 以，一g 。) 。 以下为算法2 1 的主要收敛性结果。 定理2 2 ：设目标函数厂( x ) 在d c r “上连续可微且下方有界，导数g ( x ) l i p s c h i t z 连 续虽 i 3 m o ，对砂，z d ，均有恬( j ，) 一9 0 ) 1 1 - - - m i i y - z 若算法2 1 产生的点列 孔) 有界且满足慨+ 一_ j o ( 七斗) ，则或者对某个i 有乳= o ，或憋i n f i l e 。i l = o 成 立。 4 南京航空航天大学硕士学位论文 证明：用反证法证明。不失一般性，设对任意k 均有g 0 ，假设结论不成立，则j y 0 ， 使得 l i g 。忙y ( 2 8 ) 对所有k 1 成立。根据引理2 1 有 f ( x k ) 一厂( 以+ 口。d 。) 堕；产l l g 。1 2 c o s ；( 吐，一g 。 ， 将上式累加，由于，( x ) 在d 上下方有界，故有 妻慨lc o s 2 ( 矾，一既) 帼。 ，l 由算法2 1 知对所有七有以7 9 。 盟 慨1 1 2 4 1 1 d 。1 1 2 。 于是掘( 2 8 ) 和( 2 1 0 ) 得 鼠+ l | = i 习舞葡) l l g 卜酬g k r d k 卜- 旭。7 d 。+ ( 1 一。刑l l 堑掣坐墼掣寸毗_ 咄 0 9 。旷 ，2 、7 因此当k 充分大后，i 展i c l 成立，则 ( 2 1 1 ) i k + 。= 卜g 。+ 反+ 。d , l l - l l g 。u + i p , + l | | | 哦0 l + c l l d , ij 。 ( 2 1 2 ) 不妨设对任意k 均有( 2 1 2 ) 成立，则有 阻( 1 + 2 + c “1 ) + c 忙击啪i i ， 因而 d 。) 有界，可设0 巩0 r ，于是当k 充分大后，由( 2 8 ) 和( 2 1 1 ) 知 i i g 。1 1 2 c o s 2 o 满足非精确线搜索条件 f ( x t ) - f ( x + 口i d k ) 一p o t i g r d t ， 其中0 0 ，使得对任意x ，冤d 有 ( x + f ) 一厂( 譬) g ( 聋) 7 x + 4 x l l 2 。 ( 2 1 4 ) 显然( 2 1 4 ) 右端为严格凸二次函数，因而其在d 上有极小值设为歹，即 f ( x + 量) 一( 聋) 歹a 所以f ( x + i ) 2 ( 习+ 歹，即f ( x ) 下有界。又由引理2 3 可 知 f ( x 。) 一厂( 以。) m b , 一x k + l8 2 ， ( 2 1 5 ) 将( 2 1 5 ) 式累加，哇a - t f ( x ) 下有界，所以有 m z i i x , 一x k + i 雌+ o o ， 故有 i k 一以+ ，l f 。o ( k 斗。) 。 x x 蛳) f f f k ，d 。7 既 3 0 0 0f a i l e df a i l e d ，1 3 81 4 51 1 2 8 0 8 75 7 ，6 25 7 6 23 9 4 1 5 9 6 7 53 ( 0 ，l o ，2 0 ) f a i l e d ，2 71 8 ，1 8，1 11 9 1 9 1 61 9 2 02 0 ，2 0 1 8 1 6 2 ( 0 5 ，0 ) f a i l e df a i l e d 6 n，76 ( o 8 ，0 6 ，0 4 ， 2 5 f 1 72 3 1 72 3 1 7 2 3 1 72 3 1 7 5 f a i l e d 0 2 ，o ) 1 66，6，66 6 ( 0 9 ，0 8 ，0 7 ， 2 8 1 8 2 4 1 72 4 1 72 4 1 7 f a i l e df a i l e d1 0 ，0 3 ，0 2 ， ，76 66 0 1 ，0 ) ( o 9 5 ，0 9 0 ， 3 4 f 1 95 2 ，2 9 5 2 ，2 94 7 2 64 8 2 9 f a i l e d2 00 8 5 ，0 1 5 ， 1 6，9，9 ，89 0 1 0 ，0 0 5 ，o ) 1 4 ，1 3 1 7 1 617 1 6 1 7 1 6 2 ( 1 ，2 )f a i l e df a i l e d 3 3，3 3 ( 1 , 2 3 89 ， 2 9 2 5 1 3 ，i o1 9 1 1 82 2 2 4 71 0 f a i l e df a i l e d 1 0 1，8 4，6 8 ( 1 ，2 , 3 ，1 8 ， 2 3 ，2 l 2 0 1 92 0 1 92 0 ，2 0 2 0 f a i l e d f a i l e d 1 9 ，2 0 ) n 6，6，6 3 4 犹7 02 2 ，2 5 2 l 2 4 1 9 ，2 12 4 2 5 82 ( 0 5 ，0 5 )f a i l e d 8 8，8 8n 峥 3 4 1 2 6 3 3 1 l ，2 6 14 5 4 3 6 2 6 2 6 4 9 1 93 ( 5 ，2 5 ，0 1 5 ) f a i l e d f a i l e d 8 4 1 7 8，1 1 2 1 5 3 9 二鲞茎堑塑堕鲨塑塑塞 _ 一 1 7 9 1 8 1 2 5 2 92 5 ，2 9 2 5 2 92 5 2 9 2 5 2 9 2 ( o 5 ，o 5 ) 挎 6 0 ，9，9 | 9玛 4 ( 0 2 5 ，o 2 5 ， 6 8 7 7 3 0 3 93 6 ，4 82 7 3 63 6 4 8 3 7 5 0 1 0 o 2 5 ，o ，2 5 ) ，2 6i 21 4 1 11 4 1 5 1ll i i i 4 4 5 1 4 4 96 5 1 8 65 7 7 56 1 7 9 5 9 1 8 05 3 7 2 6 l1l 1 4 8，2 62 22 4 ，2 42 1 i i i 2 8 4 1 9 l 1 0 6 7 71 1 5 ，8 99 7 7 4 2 ( 6 3 9 ，一o 2 2 1 ) f a i l e df a i l e d ，6 0 ，2 3，2 52 l 1 l ( - 1 2 ，1 ， 2 0 3 1 5 11 2 8 9 41 4 2 1 0 61 3 0 1 0 l 4f a i l e df a i l e d - 1 2 ，1 ) ，4 2，2 5，2 82 7 4 7 5 3 5 81 9 1 1 1 5 31 2 8 1 0 31 5 9 1 2 92 3 5 1 9 62 6 1 2 1 7 4 ( 3 r 1 。o ，1 ) ，1 1 95 13 4，4 2，6 2，7 l 8 ( 3 ，- 1 ，o ，1 ， 5 4 7 4 1 21 9 9 1 6 01 3 6 1 0 91 5 9 1 2 92 0 6 1 7 02 2 3 i8 4 i 2 3 ，- 1 ，0 ，1 ) 1 3 75 33 6，4 2f s 3，6 l ( 3 ，- 1 ，0 1 ， 6 3 1 “7 51 9 9 1 6 01 3 6 1 0 91 5 9 1 2 92 7 8 2 3 33 5 8 2 9 2 2 0 3 ，- l ，0 ，1 ) ，1 5 85 33 64 27 49 5 | 钔3 3 ，3 1 3 1 2 83 9 3 64 1 3 7 f a i l e d2 ( 1 ，1 ) ，2 2，1 11 01 21 2 1 3 9 6 8 33 7 3 43 1 2 84 2 ；3 94 1 3 7 4 ( 1 ，1 。1 ，1 ) f a i l e d 2 7，1 21 01 31 2 1 8 9 1 3 94 2 2 ，3 1 l9 2 0 6 8 24 6 1 ，3 4 l4 1 8 ，3 1 l5 3 2 3 9 8 1 44 ( - 3 , - 1 ，- 3 , - 1 ) ，4 59 2，2 0 8，1 0 2，9 31 2 2 l2 1 1 9 9 99 99 9 1 3 1 5 f a i l e d 1 52 i ，i 4 | al a 46 4r 三三三! 、 4 1 3 6 2 9 2 72 5 ，2 22 5 2 4 、5 5 5 5 ， f a i l e df a i l e d 9，8傀 1 2 l2 3 亍了i ，1 2 3 4 9 0 8 4 i ，3 4 8 6 7 24 5 3 74 1 3 7s 2 ，4 2 6 456 2 9 4，1 2 2 41 3，1 31 5 亍，了，i ) 南京航空航天大学硕士学位论文 ( 0 1 ，o 2 ，o 3 ， 2 9 5 2 2 59 1 7 71 3 3 l l l9 0 7 69 8 8 l 1 1 8 ，9 9 9 ，0 7 ，o 8 ， n 4，2 5，3 5，2 4 2 73 2 o 9 1 ( - 2 ，- 2 , - 2 ， 2 3 l 2 2 92 7 8 2 7 62 2 8 2 2 82 5 9 2 6 22 7 3 2 7 1 1 6l o 3 0 0 0 一2 , - 2 、 1 7 49 07 38 48 8 1 2 8 1 9 11 1 6 1 3 31 2 7 1 5 26 8 ，7 21 0 2 1 2 11 2 1 1 4 3 4 ( 1 ，2 ，2 ，2 ) 6 14 2，4 8，2 33 84 5 1 7 ( 1 ，2 , 2 ，2 ， 1 7 8 1 9 11 1 6 ，1 3 31 2 7 1 5 26 8 ，7 21 0 2 1 2 11 2 l 1 4 3 8 1 ，2 , 2 ，2 ) ，6 14 2“8，2 33 8，4 5 ( 1 ，2 ，2 2 ， 1 8 7 2 0 01 1 6 1 3 31 3 0 1 5 6 8 1 8 81 0 2 1 2 11 2 1 1 4 3 2 0 1 ，2 , 2 ，2 ) 6 4，4 24 92 7，3 8 “5 从表二中可见。f r 方法在求解问题4 和问题1 6 时，迭代次数超过3 0 0 0 ；对其 余1 5 个问题虽然都能求解，但明显不如算法2 1 的数值效果。p r p 方法对6 个问题 求解失败，对其余的问题能较好地计算。在1 7 个测试问题中，l s 方法只求解出了其 中的7 个。而算法2 1 对这1 7 个问题都能成功地求解，总体来看，它的数值效果要 好于其它三种方法。 2 2 a s 方法的收敛性 2 2 1 一个例子 由第一章的介绍知，h s 方法具有较好的数值表现。采取精确线搜索的h s 方法 对一致凸函数全局收敛a 但当采取非精确线搜索时如强w o l f e 搜索，即使，( x ) 一致 凸且参数盯( o ，1 ) 充分小，h s 方法都不能保证在每一步迭代产生下降搜索方向。如 下，我们举出一个例子来说明。 考虑问题罢扣，( x ) = j ix 2 ，显然o ) 为r 1 上的二次连续可微的一致凸函数。取 一类共轭梯度法的研究 初始点x ，= 1 ，并考虑步长吼 o 满足o p 互1 ，p 盯 l 的强w b l f e 条件( 2 6 ) 和( 2 7 ) 。 因w ( x ) = x ，所以g 。= v f ( x 。) = x = 1 。由( 2 3 ) 得d ，= 一g 。= 一1 ，于是有 g i r d = 一1 0 。 取= m i n 2 ( 1 一p ) ，1 + 盯) ，则 1 o ，对v y ，z d ，均有 i i g ( y ) 一g ( z ) 0 m i l y z ( 2 1 9 ) 成立，x 。r ”为任意给定初始点，如果步长吼由w o l f e 条件( 1 1 2 ) 和( 1 1 3 )