（运筹学与控制论专业论文）三项共轭梯度法的全局收敛性研究.pdf

f ：) 湃大学 t o n g j iu n l v e r s l t y ad i s s e i t a t i o ns u b m i t t e dt o 1 o n 西iu n i v e r s i 锣i nc o n f o 啪i 够w i t l lt l l er e q u i r e m e n t sf o r t h ed e g r e eo fm a s t e ro fs c i e n c e gi o b a ic o n v e r g e n c eo ft hr e e _ - r e r mc o n j u g a t e g r a d i e n tm e t h o d sw i t h o u tl i n es e a r c h c 砸d i d a t e ： l i a n g 一 s m d e n tn u m b e r ：0 7 2 010 2 0 2 4 d e p a r t m e n t ：d 印a r t i l l e n to f m a t h e m a t i c s d i s c i p l i n e ：m a t l l e m a t i c ss c i e n c e m 旬o r ：o p e r a t i o n a lr e s e a r c ha i l dc o n t r o lt h e o 巧 s u p e r v i s o r ：p r o x i o n g d ac h e n m a r c h ，2 0 1 0 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位敝作者签名： 歹耘 z o d 年弓月，日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 7 - 毙 z o 旧年3 月，6 日 摘要 摘要 非线性共轭梯度法广泛用于无约束最优化。它具有算法简单、不需要存储任 何矩阵的优点，特别适合于求解大规模问题。近年来，随着计算机的飞速发展和 实际问题中大规模优化问题的涌现，寻找快速有效的共轭梯度法成为了学者们 研究的热门方向之一。最近，张丽等人提出了满足充分下降条件的三项p r p 方 法( t t p r p ) 和三项h s 方法( t t h s ) ，并证明了这类方法在w 0 l f b 条件下的全局收 敛性；戴或虹和袁亚湘在强w b 条件下，对一般的三项重开始共轭梯度法的收敛 性进行了分析。然而，这类线搜索策略往往需要花费庞大的计算量。为了克服这 个缺点，孙捷和张家普又提出了一种不带线搜索的共轭梯度法。本文在这种不带 线搜索的策略下，证明了三项p r p 方法和三项h s 方法的全局收敛性，并进行了数 值试验得到了较理想的结果。最后，文章在不带线搜索策略下对一般三项重开始+ 共轭梯度法的性质进行了研究。 关键词：无约束最优化，不带线搜索，三项共轭梯度法，全局收敛性 i ，垒堕! ! 型 a b s t r a c t c o n j u g a t e 口a d i e n tm e t h o di sw i d e l yu s e di nu n c 0 璐t r a i n e do p t i m i z a t i o n ，睁 p e c i a j l yf o rl a r g 争s c a l ep r o b l 即 1 s r e c e n t l 弘z h a n ge t 口己p r o p o s e da t h 】? e 争t e h n p r pm e t h o d ( t t p r p ) 锄dat l l r 盼t 咖h sn l e t h o d ( t t h s ) ，b o t h0 fw 1 1 i c hc 趾 p r o d u c es 咂c i e n td e s c e n tc o n d i t i o n s t h e ys h o w dt h e i rg l o b a l lc 咖v e r g e n c eu n - d e rw o h el i n es e a r c h d a ja n dy u 衄8 t u d i e dg e n e r 蛆t h r e 争t e mc o n j u g a t eg r 础e n t m e t h o d 8u n d e rs t r o n gw o h n e 鼬a u r c h h 佣r e v e r ，l i n es e a u r c l ls t r a t e 西e 8 咖吞u y b r i n g 锄p u t a t i o n 甜b l l r d 触t b0 v e r c o m et h i sp r o b l e m ，s l ma n dz h a n gi n t r 伊 d u c e dc o n j u g a t e 擎a m e n tm e t h 0 l sw i t h o u tl i n e8 e a r c ：h i nt h i st h e s 诲，t h eg 知b 址 c o n v e r g e n c eo ft h et t p r p 锄dt t h sm e t h o d si 8s t u d i e d ，i nw h i c ht h el i n es e a r c h p r o c e d u r ei 8r e p l a c e db ya 丑x e df b r m l l l a0 fs t e p s i z e m o r e o v e r ，r e l e v a n tc o m p 小 t a t i o n a lr e 8 u l t s 盯ea l s op r e 8 e n t e d a tl 鹪t ，w e8 t u d i e dg e i l e r a lt h r e e - t e r i i lr e s t a n c o n j u g a t e 口a d i e n tm e t h o d su n d e rt h i s8 t r a t e g y0 fw i t h o u th n es e 缸c h k e yw o r d s ：u n c o n s t r a j n e do p t i m i z a t i o n ，诵t h o u tl i n e a u r c h ，t l l r e 砒e r mc o n - j u g a t eg r a d i e n tm e t h o d ，百o b a lc 0 i i v - e r g e n c e i i 目录 第一章 1 1 1 2 1 3 第二章 2 1 2 2 2 3 2 4 第三章 3 1 3 2 3 3 目录 引言 1 最优化问题介绍 1 最优化方法概述 2 本文的工作 7 共轭梯度法概述 8 共轭梯度法。 8 经典的共轭梯度法 9 共轭梯度法中步长因子的计算 1 1 2 3 1 精确和非精确线搜索n 2 3 2 固定步长策略 1 2 三项共轭梯度方法 1 3 一类三项共轭梯度方法的全局收敛性研究 1 5 带修正项的三项共轭梯度方法 1 5 全局收敛性的理论证明 1 6 3 2 1 预备假设和相关引理 1 6 3 2 2 固定步长策略下t t p r p 和t t h s 方法的全局收敛性 1 8 数值试验结果及总结 2 1 第四章一般三项重开始共轭梯度方法研究 2 4 4 1 全局收敛性研究 2 4 4 2 下降性质研究 2 7 第五章总结与展望 致谢 参考文献 i i i 2 9 3 0 3 1 第一章引言 第一章引言 甏 1 1 最优化问题介绍 最优化是一门应用相当广泛的学科，在国民经济的许多领域中都有着广泛的 应用。所谓最优化就是在众多的可行方案或方法中寻找最好的方案或方法。它讨 论决策问题的最佳选择，构造寻求最优解的计算方法，研究这些计算方法的理论 性质及实际计算表现。最优化问题广泛见于工程设计、经济规划、生产管理、交 通运输、国防等重要领域。例如，在工程设计中，怎样选择设计参数，使得设计方 案既能满足各方面的基本要求，又能获得好的经济效益；在生产计划安排中，选 择怎样的计划方案才能提高产值和利润；在原料配比问题中，确定怎样的比例才 能提高质量、降低成本；在建筑规划中，怎样安排和布局才能最有利于城市发展： 在确定投资项目时，选择怎样的投资组合才能使期望收益最大；在区域经济规划 中，如何发挥地面优势、挖掘潜力、发展生产力，等等。 最优化既是一个古老的问题，又是一门年轻的学科。早在1 7 世 纪，n e w t o n 和l e i b n i z 发明微积分的时代，已经提出函数极值的问题，后来 又出现了l a g r a n g e 乘子法，c a u 吐妙的最速下降法。但直到2 0 世纪3 0 年代，最优化 的理论和方法才得以迅速发展，并不断完善，逐步成为一门系统的学科。到2 0 世 纪7 0 年代，最优化无论在理论和算法上，还是在应用的深度和广度上都有了进一 步的发展。随着电子计算机的迅速发展，最优化的能力越来越强，从而成为一门 十分活跃的学科。 为了应用最优化技术确定最优的方案，需要针对具体的实际问题建立相应的 最优化模型，再根据模型的具体形式和特性选择适当的最优化方法求解。最优化 问题所对应的模型具有如下结构： 第一是决策变量，即所考虑的问题可归结为优选若干个被称为参数或变量的 量z 1 ，z 2 ，矿，它们都取实数值。它们的一组值构成了一个方案。 第二是约束条件，即对决策变量z 1 ，z 2 ，矿所加的限制条件，通常用不等 式和等式表示。 第三是目标函数和目标，比如使利润达到最大或是成本达到最小，通常刻画 为极大化或极小化一个实值函数，( z 1 ，妒，扩) 。 1 第一章引言 因此最优化问题可以理解为确定一组决策变量在满足约束条件下寻求目标函 数的最优解。其数学模型的一般形式为 ， im i n ，( z ) s t c ( z ) = o ，主= l ，2 ，m ( 1 1 ) ic ( z ) o ，茁= m + 1 ，p 其中z = 扛1 ，z 2 ，护) t p ，：p r 1 ，c ：p _ 缺1 = l ，2 ，为 连续函数，通常还要求连续可微。z 为决策变量，( z ) 为目标函数，c i ( z ) ，蕾= 1 ，2 ，p 为约束条件，c i ) = o ，主= 1 ，2 ，m 为等式约束，q ( z ) o ，主= m + 1 ，p 为不等式约束。 通常我们遇到的优化问题大多是非线性优化问题，它是指目标函数和约束函 数中至少有一个是变量z 的非线性函数。此外，根据决策变量、目标函数和约束条 件的不同，最优化还分成了整数规划、动态规划、网络规划、非光滑规划、随机规 划、几何规划、多目标规划等多个分支。 满足约束条件的区域称为可行域，通常记为d 舻，特别地，当d = 融时， 则上述最优化问题成为无约束最优化问题： 吨，( z ) r n 无约束最优化问题是最优化的基础，一则很多实际的最优化问题本身就是无约束 最优化问题，二则许多约束最优化问题可以通过罚函数等方法把约束最优化问题 转换成等价的无约束最优化问题后，用适当的无约束方法求解。本文讨论的也是 无约束最优化问题的三项共轭梯度方法。 1 2 最优化方法概述 现实生活中大量的最优化问题，除极个别例子外，即使一些看似简单的问题， 一般都不可能给出问题的解的显式表达式。以下述简单的无约束最优化问题为例 n 洫，( z ) = e 缸+ z 2 ， 根据最优性的一阶必要条件，最优解必定是方程v ，( z ) = 2 e 缸+ 勉= o 的解。 由v ，( z ) 的连续性，易知上述方程的解存在，但我们却无法得出解的任何解析表 达式。因此求最优化问题的解，一般采用迭代方法。其基本思想是，给定一个初 2 第一章引言 始点z o ，按照某一迭代规则产生一个点列【z 七) ，使得当 z 七) 是有穷点列时，其最 后一个点是最优化模型问题的最优解。当 z 七) 是无穷点列时，它有极限点，其极 限点是最优化模型问题的最优解。一般来说，迭代规则通常选取使目标函数值下 降的原则构造点列 z 七) 使得其中的某个点或某个极限点是问题的解或稳定点。这 类算法因要求函数值要有所下降而称为下降算法。它又可划分为单调下降算法 和非单调下降算法。单调下降算法每进行一步都要求函数值有所下降，即要求点 列 z 七) 满足： ，( z 七十1 ) ，( z 七) ，v 七= 1 ，2 ， 非单调下降算法并不要求每一步都满足上式，但要在一定范围的误差要求的迭代 步数内函数值有所下降，即满足： k ，( z 1 ) ，( z 知一m ) ，v 七 m 无论哪种下降算法，关键问题是要根据目标函数，( z ) 的某些信息，最好是只利用 一阶导数及函数值的信息确定一个由z 七确定下一个迭代点z 七+ 1 的规则。 一个好的算法应该具备的典型特征为：迭代点z 七能稳定地接近局部极小 点z 的邻域，然后迅速收敛于矿。当给定的某种收敛准则满足时，迭代即终止。 从理论上说，最好的收敛准则也许是要求i ，( z 七) 一，( 矿) i g 或0 z 膏一矿0 ，其 中e 为某一正常数。但是这种收敛准则需要预先知道解的信息，所以并不实用。在 实际应用当中，常常用某些必要条件来代替。对于一些具有较快收敛性的算法可 以用，( ) 一，( z 七+ 1 ) e 或i i z 七+ 1 一z 知8 s ，而对于有一阶导数信息，且收敛不太 快的算法，例如共轭梯度法，通常给出一允许误差s o ，设鲰= 夕( z 七) = v ，( 矾) 是函数，在点z 七处的梯度，只要i i 鲰| | s ，则可接受z 七为一近似解。要证明算法对 任何e 0 都能找到满意的近似解，只需证明 l 徊i n f | | 鲰0 = o w 显然，它比收敛准则 1 i m0 鲰8 = 0 要弱，但它足以保证对任何g 0 都有后使得z 七为满足以上收敛准则的近似解。在 研究具体一种算法的全局收敛性时，主要便是要考察上述的某个收敛准则是否成 立。 3 第一章引言 对于多维最优化问题，现有的计算方法可分为两大类：一类是线搜索方法； 另一类是信赖域方法。 线搜索方法是最常见的，也是研究最多的一类方法。它的基本思想是：在每 次迭代中，算法产生一个搜索方向毗，一般说来搜索方向呶可看成是某个近似问 题的解。我们称该近似问题为子问题，它是原问题在当前迭代点z 七附近的一种逼 近。然后算法在方向如上寻求一个步长因子钒 o ，使得点z 七+ q 鼍以在一定意义 下比当前点好。取下一个迭代点为 z 七+ 1 = z 七十口七呶， 这样就完成了一次迭代。 线搜索方法的本质在于以的产生和口七的选取。搜索方向毗的产生依赖于子问 题的构造。为了使算法有效，无疑要求子问题具有容易求解和较好的逼近原问 题等性质。步长因子q 七的确定取决于某种一维搜索技巧和某一评价函数。我们 认为评价函数的值越小的点越好。在无约束的情形，显然评价函数可取成目标函 数，如) 。在约束优化的情形，评价函数常为一个罚函数，它依赖于目标函数，( z ) 以 及约束函数c i ( z ) ，i = 1 ，2 ，p 在迭代式z 七+ l = z 七+ q 七比中，不同的步长因子0 f 知和不同的搜索方向如构成 了不同的线搜索算法，如最速下降法、牛顿法、拟牛顿法、共轭梯度法等。在无约 束最优化的线搜索方法中，搜索方向呶一般要求是，在z 七点处的下降方向，即呶满 足v 厂( z 七) t 毗 1 ， 其中鲰= v 他七) 是， ) 在z 七处的梯度，毗为第七步的搜索方向，口七是第尼步的步 长，反为一标量。步长因子q 七的计算对一个线搜索型的方法也至关重要。在经典 的共轭梯度方法中，步长q 七计算通常是从z 七沿如方向寻找一个“好 的点作为下 一个迭代点。显然，最好的点是在这个方向函数值达到最小的点，即要求 ，( 观+ 口七也) 2 咖，( z 七+ q 以) 这时，我们称线搜索为精确搜索。由于精确搜索需要求一个变量函数的极 小，计算量较大，故在实际计算中常常只进行非精确线搜索。常用的非精确 线搜索有w o l f b 线性搜索、强w 0 l f b 线性搜索、推广的w d 线搜索、舡豇l i j o 线搜 索、g o l d s t e i n 线搜索和非单调搜索等。然而，通常这种线搜索方法的计算量也 比较大，特别在解决大型的优化问题时尤其复杂。为了解决这个问题j s u n 和j z h a n g 提出了一种不带线搜索的方法，即步长口七由固定公式给出，从而减少了计 算量，并且在一定条件下也是全局收敛。 参数凤可取多种不同的形式。当目标函数为非二次函数时，取不同形式的 6 第一章引言 参数仇就形成了不同的共轭梯度法。常用的方法有：f r 方法、p r 方法、h s 方 法、c d 方法、l s 方法和d i y 方法等。 对于佗维最优化问题，共轭梯度法应用于佗维二次凸函数时，最多礼次迭代就 能达到最优解，即所谓的几步终止性。在将共轭梯度法应用于非二次的目标函数 时，常常采用周期性重开始的策略，也就是说，对于佗除余1 的自然数七，搜索方向呶都 需要选取特定的重开始方向。采用这种策略，数值效果将有显著改进，理论上也 可证明可以达到n 步二阶收敛，也即存在正常数丁使对充分大的七，都有 0 z 七+ 竹一z l l 下0 z 七一z + 1 1 这种运用重开始策略的共轭梯度法一般选取最速下降方向为重开始方向，以保证 重开始后共轭梯度法仍然有较好的理论收敛性。但经试验证明用最速下降方向会 减慢收敛速度，因此p a w e h 、b e a l e 等人对一般的重开始下降方向的共轭梯度法进 行了研究，提出了b e a l l e 三项公式。此后就有不少人开始研究三项共轭梯度法，并 提出了多种三项公式，1 9 9 9 年d 越和y - u a n 更对一般的三项共轭梯度法的收敛性进 行了分析【1 2 】。理论上讲，三项共轭梯度法比传统的共轭梯度法收集了更多的目 标函数的信息，应该更有效。 1 3 本文的工作 本文将致力于对三项共轭梯度方法全局收敛性的研究，把固定步长的技巧推 广到一类新的三项共轭梯度方法和一般的三项重开始方法。文章在理论上证明全 局收敛性的同时，也进行了数值试验，得到了新方法用于1 8 种标准测试函数【1 3 】的 数值结果并进行了分析。最后文章还对后续问题和将来的发展作了展望。 7 第二章共轭梯度法概述 第二章共轭梯度法概述 最优化理论是一门应用广泛的学科，它讨论决策问题的最佳选择之特性，构 造寻求最优解的计算方法，研究这些计算方法的理论性质及实际计算表现。随着 高新技术、计算机及信息技术的飞速发展，最优化理论在实际应用中正在发挥越 来越大的作用。无约束优化问题在许多重要领域如工程、国防、经济等都有着直 接的应用。另外，许多约束优化问题也可以借助罚函数等方法转化为无约束优化 的形式进行求解。共轭梯度法是最优化中最常用的方法之一。在所有需要计算导 数的优化方法中，最速下降法是最简单的，但它速度太慢。拟牛顿方法收敛速度 很快，被广泛认为是非线性规划的最有效的方法。但拟牛顿法需要存储矩阵以及 通过求解线性方程组来计算搜索方向，这对于求解大规模问题几乎是不大可能办 到的。共轭梯度法算法简便，存储量需求小，收敛速度又比最速下降法快，特别 适合求解大规模问题。在许多应用领域如电力分配、石油勘探、大气模拟、航天 航空等提出来的优化问题规模往往很大，这时由于拟牛顿方法需要存储大型矩阵 而往往失败，而共轭梯度法只需存储几个礼维向量就显得特别有效，因而研究共 轭梯度法具有很强的应用背景。 2 1 共轭梯度法 共轭梯度法是求解无约束优化问题 鲰，( z ) ( 2 1 ) z r n 的一类非常有效的方法。它具有算法易于实现、存储空间小等优点，因而对于大 规模问题显得特别有效。 随着计算机的飞速发展和实际问题的需要，大规模优化越来越受到 重视，共轭梯度法的研究也日益受到了人们的关注。早期对共轭梯度 法的收敛性分析成果主要由f l e t e h e r 、p o w e l l 、b e 2 l l e 等学者给出的。近年 来，n o o e d a l 、g i l b e r t 、n a z 甜e t h 、a l - b a 址、s t o r e y 等学者以及国内的袁亚湘、戴 或虹、韩继业、张丽等学者也在这方面得到了一些非常好的结果。 当目标函数，( z ) 连续可微时，共轭梯度法的迭代格式为： + l = z 七十口七d ，( 2 2 ) 8 弟一草哭祝梯度纭儆述 ， 反= 二：+ 肫。，篡 仁3 ， 其中鲰= v ，( 瓢) 是，( z ) 在瓢处的梯度，以为第七步的搜索方向，0 f 七是第慰眵的步长 因子，风为一标量。参数臃可取多种不同的形式。当目标函数为非二次函数时，取 不同形式的参数风就形成了不同的共轭梯度法。 2 2 经典的共轭梯度法 求解无约束优化问题的共轭梯度法具有形式( 2 2 ) 和( 2 3 ) 。式( 2 3 ) 中的参 数雠的计算公式有很多，当臃选取不同的计算公式时，就得到了不同的共轭梯 度方法。比较常见的几个计算公式有 矿= 器，( f l e t c h e r - 【2 】) ( 2 4 ) 硝r p2 悉等，( p o l 如b i 宅r e 【1 9 ，2 0 】)( 2 5 ) 磺s = 粤，( h e s t e n 睁s t i e f e l 【1 】) ( 2 6 ) 畈一l 弧一l 。 舻：共，( f l e t c h e r 【3 】) ( 2 7 ) 一d 孟一1 夕矗一1 臃s j 舡( l i u _ s t o r e y 2 8 】) ( 2 8 ) 一d 孟一1 5 k l 和 = 悬，( 。缸y u a n 【2 7 】) ( 2 9 ) 这里1 1 i i = ”忆，p 表示转置，讥一1 = 瓠一鲰一1 。对应地，我们把上述六种方 法分别叫做：f r 方法、p r p 方法、h s 方法、c d ( 下降方向) 方法、l s 方法和d i y 方 法。 f r 方法是最早的非线性共轭梯度法，它由f 1 e t d l e r 和胝v e 8 在1 9 6 4 年提 出，f r 方法理论上具有良好的全局收敛性。z o u t e n 蛔k 【1 4 】首先证明了采取精确线 搜索的f r 方法对一般非凸函数总是收敛的。最早的非精确线搜索的全局收敛性结 果是由a 1 b a a l i 【1 5 】在1 9 8 5 年给出的，他证明了使用参数0 盯 l 2 的强w o 线 搜索的f r 方法一定满足充分下降条件，而且全局收敛：刘光辉、韩继业和尹红 霞 1 6 】将a 1 - b a a h 的结果推广到了0 1 2 的情形，f r 方法可能因为产生一个上升方向而导致失败，因 而他们提出一种广义线搜索【1 8 1 ，并证明了在广义w o 线搜索下f r 方法全局收 敛。戴或虹和袁亚湘不仅提出了广义线搜索而且证明了f r 方法在广义w b 线搜 索和广义a 珊i j o 线搜索下的全局收敛性。但f r 方法在数值计算中表现并不十分 理想。p o e l l 在文献 4 】中给出了一定的解释：在精确线搜索下，如果f r 方法在某一 步产生一个很小的步长，则相继的许多步长也可能非常小，并且当f r 方法进入到 一个，( z ) 为二维二次函数，( z ) = ，z 2 ，z r 2 的区域时，搜索方向与负梯度方 向的夹角始终保持不变，因而可任意接近丌2 ，这样f r 方法可能收敛非常慢。 p r p 方法是由p o l a k ，砒b 渤e 【1 9 】和p o l y a k 【2 0 】在1 9 6 4 年分别独立提出的，是 目前认为数值表现最好的共辘梯度法之一。与f r 方法不同，当产生一小步长 时，p r p 方法定义的搜索方向有一种自动重新取负梯度方向的趋势，从而可以 克服多次进展缓慢的缺点。对于凸函数，袁亚湘 2 1 】给出了p r p 方法在非精确线 搜索下的全局收敛性。但是p 0 w e u 在文献【4 】中指出，对一般非凸函数，即使采用 精确线搜索，p r p 方法也不必然具有全局收敛性。p o w e l l 【2 2 】建议限制p r p 方法中 的参数艘r p 为非负 反= m a x 臃r p ，o ) 这样做的目的是避免当| | 毗0 很大时，相邻两个搜索方向会产生相反的趋 势。g i l b e r t 和n 0 c e d 出f 7 1 接受了n w e l l 的上述建议，并在适当的线搜索条 件下得到了上述修正的p r p 方法对一般非凸函数的全局收敛性结果。然 而，g i l b e r t 和n oc e l d a l 举出反例说明即使对于一致凸的函数，雕r p 也可能为负。于 是，g r i p p o 和l u c i d i 【2 3 】设计了一种a r m i j o 型的线搜索，并证明了在此线搜索下，原 始p r p 方法对一般非凸函数全局收敛。他们的结果是应用当步长s 七= z 七+ 1 一z 七很 小时，p r p 方法的搜索方向接近最速下降方向的性质。 h s 方法由h e s t e n e s 和s t i e f e l 【1 1 给出，它的一个重要性质是共轭关系 式d j 5 玑一1 = o 不论线搜索是否精确总是成立的，它的理论性质和计算 表现都与p r p 方法类似。g i l b e r t 和n o c e d a l f 7 】通过限制参数仇为非负， 证 明了p r p + 、h s + 方法采用w o 线搜索在充分下降条件下是收敛的。 即 取黠= m a x 凤，o ) c d 方法由f l e t c h e r 在1 9 8 7 f 3 1 年引入，它的一个重要特点是只要强w - o 线搜 1 0 - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 。_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 。 笙三皇 索准则中的参数盯 1 ，则c d 方法 共轭梯度法概述 在每次迭代均产生一个下降搜索方向，而此 时f r 方法和p r p 方法即使对一致凸函数都有可能产生一个上升搜索方向【2 4 】。戴 或虹等在文献f 2 5 1 中提到：在强w - o l f e 线搜索下，只要每个搜索方向下降，则共轭 梯度方法是全局收敛的。因此，在强w - o l f b 线搜索下c d 方法是全局收敛的。戴或 虹和袁亚湘还在文献【2 6 】中指出，使用参数盯l 1 和c r 2 = o 的推广的w o 托线搜索 的c d 方法全局收敛，并且盯1 1 和眈= 0 是必要条件。不过c d 方法的收敛性质 并不好，当采用精确线搜索时鳄d = 臃r ，因此c d 方法有着和f r 方法同样的数 值缺点，即可能连续产生许多小步长而收敛缓慢。这和在实际计算中c d 方法的数 值表现和f r 方法相差不大相一致。 d l y 方法是由戴或虹和袁亚湘 2 7 】在研究c d 方法时发现的一种共扼梯度法，它 在w - o l f e 非精确线搜索下即可保证在每次迭代产生一个下降方向，且方法全局收 敛，但其数值表现一般。l s 方法是由“u 和s t o r e y 【2 8 】在1 9 9 1 年提出的，其性质类 似于h s 方法。 这些方法在目标函数是二次正定，线搜索精确时是等价的，即参数风的选择 使得毗与而，d 1 ，呶一1 关于，( z ) 的h 瞅n 矩阵共轭。但对于一般的非线性函 数，它们的性质很不相同。 2 3 一共轭梯度法中步长因子的计算 一 共轭梯度法的迭代格式( 2 2 ) ，( 2 3 ) 中，参数仇的计算公式不同导致搜索方 向呶的计算方式不同，就对应不同的共轭梯度方法。另一方面，由( 2 2 ) 可以看到， 下一个迭代点的确定离不开步长因子的计算。确定步长因子a 南的不同方法以及确 定搜索方向呶的不同方式构成求解最优化问题的不同算法。 2 3 1 精确和非精确线搜索 在经典的共轭梯度方法中，步长因子口七的计算通常是从z 七沿毗方向寻找一个 “好 的点作为下一个迭代点。显然，最好的点是在这个方向函数值达到最小的 点，即要求 ，( z 七+ q 南以) = i i 婪癸，( z 七+ a d 七) ( 2 1 0 ) 这时，我们称线搜索为精确线搜索。另外一种选取q 七的c u r 巧原则也可以认为是 1 1 第二章共轭梯度法概述 一种精确的线搜索，它要求选取q 七满足 q 七= 曲 鲰i 耀9 ( z 七+ q 呶) = o ) ( 2 1 1 ) 但是在实际计算中，理论上精确的最优步长因子一般难以求到，求几乎精确的步 长因子需花费相当大的工作量，因而花费计算量较少的非精确线性搜索日益受到 人们的青睐。常用的非精确线性搜索有以下几种： ( 1 ) w | o 线搜索。要求q 膏满足w o 条件： ，( z 七十q 奄d 知) 一，( z 七) d 1 口七鳍以，( 2 1 2 ) 夕( z 七+ q 后以) t 噍c r 2 蠢呶，( 2 1 3 ) 其中c r l 和眈是满足o 吼 c r 2 1 常数。第一个不等式要求函数，在z 詹+ 1 处的函 数值比在处的值有一定的下降，第二个不等式防止步长过小。 ( 2 ) 强w b l f e 线搜索。除了要求q 七满足( 2 1 2 ) 外，还要求满足： 1 9 ( 轨+ q 七以) t 以l 一c r 2 夕看毗 ( 2 1 4 ) 当c r 2 = 0 时，必有夕( z 七+ q 知以) t 以= o 。因此强w | o l f e 线性搜索可看成是精确线性 搜索的一种推广。 ( 3 ) 删。线搜索。要求选取q 知= 矿，其中参数p ( o ，1 ) ，6 ( o ，1 ) ，九为使 得下式成立的最小非负整数：，( 钆+ q 知也) 一，( z 知) 6 q 七靠呶 还有许多其它类型的线性搜索，如推广的w _ o l f b 线性搜索，g o l d s t e i n 线性搜 索等，然而，通常这些线搜索方法的计算量也比较大，特别在解决大型的优化问 题时尤其复杂。 2 3 2 固定步长策略 上面一节已经说过非精确线搜索方法与精确线搜索方法相比，在计算量上确 实减少了很多，然而在求解大规模的优化问题时，其计算量还是比较大。为此国 内外的许多学者在这方面进行了大量的研究，j s u n 和j z h a n g 在文献【2 9 】中创造 性地提出了一种叫做不带线搜索或者固定步长的策略，即步长因子q 七由下面的计 算公式给出： 驴。靛， ( 2 1 5 ) 1 2 第二章共轭梯度法概述 这里 q 七) 是一系列正定矩阵组成的序列，且对任意d p ，存在两个正常数 和娃满足 i n 矿d 矿仉d 娃矿d ( 2 1 6 ) 其中0 也0 饥：= 历孤，6 ( o ，i n 肛) 且满足 6 p i n o 使得对于任意的z ， 有 v ，( z ) 一v ，( 可) 】t ( z 一可) 入l l z 一秒0 2 成立。 。因为强凸函数的水平集有界，由此容易注意到假设( h 2 ) 暗含假设( h 1 ) 。虽 然在假设( h 1 ) 下就能证明t t p r p 方法的全局收敛性，但是本文只在较强的假 设( h 2 ) 下得到了t t h s 方法的全局收敛性结果。 在证明全局收敛性之前，我们首先给出如下几个与凤无关的结论。 引理3 1 如果z 七由( 2 2 ) 和( 2 1 5 ) 给出，那么对所有的艮都有 函l 呶= 风靠呶( 3 9 ) 成立。其中 m = 1 6 饥0 毗0 2 f | 以l b 知 且 机2 。刊t 。一州黼训，：嚣 证明：见文献 2 9 】中的引理1 。 推论3 2 在假设( h 1 ) 下，对所有的七都有 ( 3 1 0 ) ( 3 1 1 ) 1 一舡n 风1 + 舡i n ( 3 1 2 ) 1 6 第三章一类三项共轭梯度方法的全局收敛性研究 成立；如果还有假设( h 2 ) 也满足，则以上的估计还能缩小为 o 依1 6 入瞰( 3 1 3 ) 证明：见文献【2 9 】中的推论3 。 我们知道，在共轭梯度法的收敛性证明中z o u t e n d j = j k 条件起着举足轻重的作 用。用公式( 2 1 5 ) 计算步长因子口七同样有z o u t e n 蛔k 条件成立，与搜索方向呶的选 取方式无关。 引理3 3 如果假设( h 1 ) 满足且z 知由( 2 2 ) 和( 2 1 5 ) 给出，那么 三群 o o 慨均 铝恻1 2 r 7 证明 2 9 】：首先，根据中值定理，可以得到 。 ，( z 七+ 1 ) 一，( z 七) = 雪r ( z 知+ 1 一z 詹) 这里雪= v ，( 牙) ，牙陬，z 七十l 】又根据c a u d l y - s c h w a l r t z 不等式，( 2 1 5 ) 和假 设( h 1 ) ，进一步得到 耍1 ( z 七+ 1 一z 七) 2【z 奄+ 1 一$ 七) + ( 雪一g ) 。( z 七+ 1 一z 知) 鳍( z 抖1 一z 七) + 0 耍一鲰i | i i z 七+ 1 一z 七0 靠( z 七十1 一z 七) + p 0 牙一z 七00 z 知+ l z 奄l i 鲧( z 七+ 1 一写七) + p i l z l z 七1 1 2 = 讯靠比+ p 口钏以1 1 2 一班巾七姒燃 = 口七靠畋( 1 一雠) 一6 ( 1 一蕞) 鹾 即 他m h ) 一6 ( 1 一差) 雠 ( 3 1 5 ) 当6 足够小使得( 2 1 7 ) 满足时，就有，( z 七+ 1 ) ，( z 七) ，这说明了固定步长策略下的 共轭梯度方法的每一步迭代必然产生下降量。 1 7 第三章一类三项共轭梯度方法的全局收敛性研究 再由( 2 1 6 ) 和( 3 1 5 ) ，我们得到 群沁雠南叭训柏+ 1 ) 】( 3 1 6 ) 将上式两边求和得到 群矿筠商) 一熙m 棚 根据假设( h 1 ) 可知h m 厂( 轨) 存在，因此( 3 1 4 ) 成立。证明完毕。 由7 i ，i l p r p 和t t h s 方法的充分下降性质( 3 6 ) ，容易推出以下推论。 推论3 4 如果假设( h 1 ) 和( 3 6 ) 满足，且z 七由( 2 2 ) 、( 3 5 ) 和( 2 1 5 ) 给出，那么 磊辉 0 使得 | | 鲰| | c ， 七1 ( 3 2 1 ) 根据( 2 5 ) ，我们有 酽l = 矧镤穿 ( 3 2 2 ) 由( 3 2 0 ) 和( 3 2 1 ) ，上式化为 i 臃r p l 享i | 弧一1 l i ， ( 3 2 3 ) 所以，由引理3 5 可以看到当七一o o 时l 罐r p l _ o 另一方面，从( 3 3 ) ，( 3 9 ) 和( 3 6 ) 我们推得 蚓_ 别! 皆地_ 1 | ( 3 2 4 ) 因此通过( 3 1 2 ) 得到 i 畦i = i 风一1 l 1 + 舡i n ， 七2 ( 3 2 5 ) 由引理3 5 和( 3 2 3 ) 可知，对任意g o ，存在正常数j h 和j g 使得i 臃r p l s 对于所 有的后所成立，以及l l 讥一1 0 1 对所有的七鲍成立。 假设对所有的1 七m a x 风，鲍) ，有0 以| | m ，其中正常数m c + l + 舡i n 对任意的七m a x 尬，鲍) ，如果0 以一1 0 m 则 0 政i l = 0 一鲰+ 藤r p 以一1 一酲鲰一1 0 l | 鲰0 + i 臃r p i l l 以一10 + l p ：| i i 鲰一1 8 c + i 臃r p l l i d 七一1 l l + ( 1 + 舡) 0 弧一l i l ， 取= 丝二兰二南雄，我们得到 8 呶i | c + 1 + 舡j n + m = m 1 9 ( 3 2 6 ) ( 3 2 7 ) 第三章一类三项共轭梯度方法的全局收敛性研究 由数学归纳法，式( 3 2 7 ) 对所有的毗成立。因此我们有 磊器磊丢= c 3 蕊， 这与推论3 4 矛盾。所以( 3 1 9 ) 成立，r t p r p 方法全局收敛。证明完毕。 然后我们在假设( h 2 ) 下，给出固定步长策略下的t t h s 方法的全局收敛性定 理。 定理3 7 如果假设( h 2 ) 满足，且步长因子a 七由( 2 1 5 ) 给出，那么t t h s 方法将 产生一个收敛序列使得( 3 1 9 ) 成立。 证明：用反证法进行证明。假设定理的结论不成立 1 i 皿i n f0 鲰0 o ， 七_ ”一” 。 因为水平集有界且，( z ) 连续可微，所以存在常数，y o 使得对所有的尼都有0 鲰0 7 ，以及常数c o 使得对所有的惫都有0 弧