（数学专业论文）无约束最优化共轭梯度算法研究.pdf

摘要 本文对无约束最优化中的共轭梯度算法进行了研究共轭梯度算法在无约束最优化 问题中有着广泛应用，是解决大规模优化问题的最有效算法之一通过广泛的阅读和研 究，在前两章中我们综述了共轭梯度法的背景、意义及研究现状，并提供了研究共轭梯 度算法所需要的基础知识 尽管许多学者对共轭梯度算法做了大量的工作，但共轭梯度算法仍有许多值得深视 和深入研究的地方，这其中，混合共轭梯度算法就是热点之一为了利用不同共轭梯度 算法所表现出来的良好的数值性和收敛性，采用混合策略进行研究，不得不说是一种较 好的研究策略 在第三四两章中，我们以d y 方法良好的收敛性为基础，提出了两类新的混合共轭 梯度算法，并在给定假设条件的前提下，证明了算法的下降性质和全局收敛性质 对无约束最优化的研究，一般是从搜索方向和搜索条件两个方面入手在最后一章 中，我们以w o l f e 搜索条件为基础，给出新的搜索条件，加快了算法的收敛速度，同样 在给定假设条件的前提下，证明算法在新的搜索条件下具有下降性质和全局收敛性质 不论是对搜索方向的改进还是对搜索条件的改进，我们均用数值例子说明了算法的 有效性 关键词：无约束最优化，共轭梯度法，w o l f e 线搜索，下降方向，全局收敛性 r e s e a c ho fc o n ju g a t eg r a d i e n tm e t h o d sf o r u n c o n s t r a i n e do p t i m i z a t i o n l i uy u j i a n ( m a t h e m a t i c s ) d i r e c t e db y p r o f h u a n gb i n g j i a a b s t r a c t t h i s p a p e r r e s e a r c h e s c o n ju g a t eg r a d i e n t m 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 n c o n j u g a t eg r a d i e n tm e t h o d sa r ew i d e l yu s e df o ru 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 y f o r s o l v i n gl a r g e s c a l eu n c o n s t r a i n e dp r o b l e m s i nt h ef i r s tt w oc h a p t e r s ，w e s u mu pt h e b a c k g r o u n da n ds i g n i f i c a n c ea n dt h ep r e s e n ts i t u a t i o no fc o n ju g a t eg r a d i e n tm e t h o d st h r o u g h e x t e n s i v er e a d i n ga n dr e s e a r c h f u r t h e r m o r e ，w ep r e s e n tb a s i c k n o w l e d g ef o rs t u d y i n g c o n ju g a t eg r a d i e n tm e t h o d s c o n j u g a t eg r a d i e n tm e t h o d sa r es t i l lw o r t hr e s e a r c h i n gt h o u g hm a n ys c h o l a r sh a v e d o n el o t so fw o r ka b o u tt h e m u s i n gh y b r i ds t r a t e g yi sae x c e l l e n tm e t h o dt os t u d yc o n j u g a t e g r a d i e n tm e t h o d sf o rm a k i n gt h eb e s tu s eo ft h ec o n v e r g e n c ea n dt h eg o o dn u m e r i c a l p e r f o r m a n c e i nc h a p t e r3a n d4 , w ep r e s e n tt w on e wh y b i r dg r a d i e n tm e t h o d so nt h eb a s i so fg o o d c o n v e r g e n c eo f d y m e t h o d f u r t h e r m o r e ，w ep r o v et h ed e c e n tp r o p e r t ya n dg l o b l ec o n v e r g e n c e o ft h en e wm e t h o d s i ng e n e r a l ，w ew i l lp a ya t t e n t i o nt ot w oq u e s t i o n sw h e nr e s e a c h i n gu n c o n s t r a i n e d o p t i m i z a t i o n ：s e a r c hd i r e c t i o na n ds e a r c hc o n d i t i o n i nl a s tc h a p t e r , w ep r e s e n tan e ws e a r c h c o n d i t i o no nt h eb a s i so fw o l f el i n es e a r c ha n dp r o v et h ed e c e n tp r o p e r t ya n dg l o b l e c o n v e r g e n c eo f t h en e wm e t h o d s t h en u m e r i c a lr e s u l t si l l u s t r a t et h a tt h en e wm e t h o d sa l ee f f e c t i v ew h e t h e rt h e i m p r o v e m e n to fs e a r c hd i r e c t i o no re a r c hc o n d i t i o n k e y w o r d s ：u n c o n s t r a i n e do p t i m i z i 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 ，w l o f el i n es e a r c h ，d e c e n t d i r e c t i o n ，g l o b a lc o n v e r g e n c e 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料与我一同工作的同志对 研究所做的任何贡献均已在论文中做出了明确的说明 若有不实之处，本人愿意承担相关法律责任 学位论文作者签名：三亟邋 日期吻吵一年月7 日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印 刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机 构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、 借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、 缩印或其他复制手段保存学位论文 保密学位论文在解密后的使用授权同上 学位论文作者签名：型尘整 指导教师签名：蚕6 1 映 。v 日期：矽7 d 年厂月日 日期：抄c 口年6 月j 曰 中国石油人学( 华东) 硕上学位论文 1 1 课题提出背景及研究意义 第一章绪论 最优化理论是一门应用性很强的学科，它研究某些数学上定义的问题的最优解，构 造寻求最优解的计算方法，并研究这些计算方法的理论性质及实际计算表现随着高新技 术、计算机及信息技术的飞速发展，最优化理论在经济计划、生产管理、工程设计、交 通运输等实际应用中正在发挥越来越大的作用 共轭梯度法是最优化中最常用的方法之一在以梯度法为基础的众多优化方法中，最 速下降法虽然简单，但是在两次迭代中，由于搜索方向相互正交，使得逼近极小值的路 线是锯齿状的，并且越靠近极小点越小，即越走越慢，从而降低了收敛的速度牛顿方法 收敛速度很快，被公认为是求解非线性规划问题的非常有效的方法，但是牛顿法需要存 储矩阵并且需要通过求解线性方程组来计算搜索方向，这对于求解大规模问题几乎是不 大可能办到的共轭梯度法算法只需利用函数的一阶导数信息，存储量很小，并且算法简 便，另外收敛速度比最速下降法快，所以非常适合求解大规模问题在许多应用领域所涉 及优化问题规模往往很大，拟牛顿方法由于比较大的存储量而往往不能成功，而共轭梯 度法的存储量仅限于n 维矩阵，使得结果一般是有效的，故而共轭梯度法的研究具有较 强的实际背景 对于无约束最优化问题 r a i n ( x ) j e h 其中f ：r ”j r 连续可微有下界，共轭梯度法是解决该类问题中的最有效的数值方法之 一特别是在大规模问题上，共轭梯度法因其算法简便、所需存储量小、收敛速度快等特 性而在许多工程科学领域采用 2 0 世纪5 0 年代初，在求解线性方程组 a x = b 的过程中，数学家h e s t e n e s 0 1 和s t i e f e l l 2 1 分别提出了共轭梯度算法在文献 3 】中，h e s t e n e s 和s t i e f e l 所做的工作是开创性的他们详细讨论了求解线性方程组的共轭梯度法的性质 以及它和其他方法的关系在a 为对称正定阵时，a x = b 等价于 最优化问题 第一章绪论 1 m i n 三x 7 a x b y x x e r ”2 由此，h e s t e n e s 和s t i e f e l 的共轭梯度法也可用来求解求二次函数的极小值f l e t c h e r 和 r e e v e s 4 1 将此方法推广到非线性优化，得到了求一般函数极小值的共轭梯度法 对于无约束最优化问题 m删in。f(x)(1-1) 我们通常是用迭代法来逐步产生它的最优解其基本思想是给出y ( x ) 的极小点t 一个初 始初始估计值x o r ”，按照一定的准则计算一系列的点五，x 2 ，扳，形成一个点列 吒 ，希望 & 是有限点列时，其最后一点是最优化问题的最优解；当 x k ) 是无穷点列 时，它有极限点，且其极限点是最优化问题的最优解问题在于点列 坼) 的产生过程，也 就是在得到矗后怎样来求x k 考虑到k + 。一磁是一个向量，本质上是由其方向和长度决 定的，即有 x k “一x k2 a k d k 也就是 雉+ l = 稚+ 咏以( 1 - 2 ) 这里畋为搜索方向，吼称为搜索步长选取搜索方向以和步长的方法不同，形成的算 法也不相同在后面的研究中，我们所讨论的都是下降算法并研究算法的收敛性我们要 求以是下降方向，即畋7 v y ( x ) 0 ；而是由某种线搜索得到的步长 共轭方向法介于最速下降法和牛顿法之间，它是从研究二次函数的极小化产生的， 但是可以推广到处理非二次函数，最典型的共轭方向法就是本文所研究的共轭梯度法 我们首先给出共轭方向的概念 定义1 1 设a 是刀n 对称正定矩阵，4 吐，以是足”中行维非零向量，如果 z7 a d j = o ，f ，f ，歹= l ，2 ，k 则称这k 个方向共轭，或称它们为a 的k 个共轭方向 在上述定义中，当a 为单位矩阵时，碣，吐，以关于a 共轭与碣。吃，攻关于么正 交是等价的由此可见，正交只是共轭的一种特殊情况共轭方向法的一个基本性质是： 2 中国z i 油人学( 华东) 硕士：学位论文 对于二次凸函数，只要线搜索条件是精确的，就能得到二次终止性，即经有限步迭代函 数必将达到极小点关于这个理论有下面的定理： 定理1 1 t 2 7 1 ( 共轭方向法基本定理) 对于正定二次函数，共轭方向法至多经过胛步精 确线搜索终止；且每一薯+ 。都是( x ) 在而和方向西。吃，谚所张成的线性流形 协= 咭啊，) 中的极小点 这个定理告诉我们，共轭性和精确线搜索产生二次终止性共轭梯度法就是把共轭性 与最速下降方法相结合，使得最速下降方向具有共轭性 我们给出共轭梯度法的一般推导过程【2 7 】： 设 厂( x ) ：昙x r 彳x + 6 r x + c ( 1 - 3 ) 其中a 是豫玎对称正定矩阵，b 是”1 向量，c 是实数厂的梯度为g ( x ) = a x + b ， 令如= 一g 。，则_ = x o + 吃，由精确线性搜索性质知，g l r d o = o 令 珥= 一g l + a d o ( 1 - 4 ) 令屈满足4 7 a d o = o 对上式两边同乘以硫7 a ，可得 届= 蕊g f a d o 了= 玎g , r ( 瓦g l - 习g o ) = 忑g l r g l 以此类推，在第七次迭代，取 k - 2 矾= - g k + 屈矾一。+ 屈z t = o 使得畋7 4 盔= o ，i = o ，1 ，k - 1 利用数学归纳法可证 r z = 0 ，i = 0 , 1 ，k - 1 ( 1 - 5 ) ( 1 - 6 ) 所以，只要0 ，则可由式( 1 - 5 ) 求出一个与d o ，嘎，巩一。关于a 共轭的下降方向事实 上，7 吨= 一0 反0 ，由式( 1 5 ) 可知& 是4 ，z 的线性组合，再由式( 1 6 ) 可得 g k7 g f = 0 ，i = 0 , 1 ，k - 1 于是 3 第一章绪论 & ，彳z = 7 ( g ，+ l g 。) ，i = o ，l ，k - 1 在等式( 1 - 5 ) 的两边同乘以z7 a ，i = o ，1 ，k 一1 ，就得到 屈= 0 ，i = 0 ，1 ，k 一1 展= 毪= 粼= 磊g k r g k - gg k _ l r g ( 1 - 7 )心 矾一l7 彳吨一l 矾一l r ( h ) r 叫 因此，共轭梯度法的迭代公式为： ，f 一， 巩2 t 一繇+ 屈以一。 k = 0 k 1 ( 1 8 ) ( 1 9 ) 其中繇是目标函数厂( x ) 在坼点处的梯度，孱为标量由式( 1 7 ) 看出，参数屈可以取多 种不同形式，取不同形式的参数屏就形成了不同的共轭梯度法 1 2 无约束共轭梯度法的研究现状 2 0 世纪5 0 年代初，在求解线性方程组 a x = b 的过程中，数学家h e s t e n e s t l l 和s t i e f e l 2 1 分别提出了共轭梯度算法在文献 3 】中，h e s t e n e s 和s t i e f e l 所做的工作是开创性的他们详细讨论了求解线性方程组的共轭梯度法的性质 以及它和其他方法的关系在a 为对称正定阵时，a x = b 与最优化问题 m i n 三x r a x b r 工 x a r 2 是等价的由此，h e s t e n e s 和s t i e f e l 的共轭梯度法也可用来求解求二次函数的极小值 在文献 4 】中，f l e t c h e r 和r e e v e s 把h e s t e n e s 和s t i e f e l 的方法应用到非线性优化，得 到了求一般函数极小值的f r 方法 众所周知，f r 在精确线搜索下具有下降性质z o u t e n d i j k | 6 】证明了f r 在精确线搜索 的情况下是全局收敛的a 1 b a a l i 7 扩展了上述结果，他在强w o l f e 搜索条件下证明了算 法的全局收敛性p o w e l l l 5 】在精确线搜索下，发现了f r 方法的一个严重的缺陷，如果f r 方 法在极小点附近产生了一个非常小的步长则后续的的许多步长也可能非常小，从而造成 了f r 方法的数值表现往往不能令人满意的局面 4 中国石油大学( 华东) 硕上学位论文 在实际计算中，精确线搜索是不实用的，人们一般使用非精确线搜索，例如著名的一 般w o l f e 线搜索、强w o l f e 线搜索及推广的w o l f e 线搜索，此外还有a m i j i o 线搜索 等a 1 b a a l i l 7 1 在19 8 5 年证明了在强w o l f e 线搜索的f r 方法一定满足充分下降条件，而且 是全局收敛的不过他的证明过程需要满足条件仃 l 2 时，他们通 过反例证明，f r 方法将会产生一个上升方向 在文献【1 1 】和 1 2 1 a l p ，p o l a k 和r i b i 色r e ，p o l y a k 提出了p r p 方法从数值表现上来讲， p r p 方法远比f r 要成功，被认为是数值表现最好的共轭梯度算法之一p r p 方法克服了 f r 方法的缺陷，因为当步长很小时，p i 冲方法可以自动转向负梯度方向，从而避免了f r 方法由于连续产生小步长而进展较慢的缺陷依次理论为基础，在文献【5 】中，p o w e l l 提 出并证明了如下理论：若s k = x k + 。一吒j0 ，则p r p 方法是全局收敛性的在文献 1 3 1 a l p ， p o w e l l 指出，若函数是一般非凸函数，则可以举出反例证明，即使按c u r r y 原则，p l 冲方 法可能在若干点附近进行循环，但是任意一点都不是稳定点对于二维的情况，p o w e l l 在文 献【1 4 】中证明了采取c u r r y 原则的p r p 方法对一般非凸函数的收敛性 对一般非凸函数，p o w e l l 在文献 1 6 中把参数屈脚设置为非负，即 反= m a x ( f l f 泸，0 ) ，这样就避免了当0 以0 较大时，相邻两个搜索方向会产生相反的趋势 依据p o w e l l 的理论，在文献 17 】中，g i l b e r t 和n o c e d a l 在适当的线搜索条件下，得到了算 法展= m a x ( i l k p r o ，0 ) 对一般非凸函数的全局收敛性结果然而，即使目标函数是一致凸 的，尾p r p 也可能为负值鉴于此，在文献【1 8 】中，g r i p p o 和l u c i d 证明了在新的a r m i j o 线搜索条件，证明了p i 冲方法一般非凸函数的全局收敛性 文献 2 0 1 中，f l e t c h e r 引入了c d 方法( 即共轭下降法) 下降性质是c d 方法的一个非 常重要的性质：在强w o l f e 搜索下，对于任意的k l ，有繇7 矾 0 成立文献【2 1 中，戴 或虹等证明了：对于强w o l f e 线搜索下，如果每个搜索方向是下降的，即有断7 1 畋 0 ，使得对所有满足xe r ”和忙一x 0 - s ( x 1 ，则称x + 为的总体极小点如果 对所有满足x r n , x # x ，厂( 工) 厂( x 。) ，则称x 为的严格总体极小点 注：在实际当中，我们所求的往往只是一个局部( 或严格局部) 极小点，而不是总 体极小点，尽管求解总体最小点也是有可能的，但一般说来这是一个相当困难的任务 令g ( x ) = w ( x ) ，g ( x ) = v 2 f ( x ) 分别表示函数的一阶和二阶导数，我们有以下 最优性条件： 定理2 i t 2 5 1 ( 一阶必要条件) 设厂：dcr ”寸r 在开集d 上连续可微，若x d 是 ( 2 2 ) 的局部极小点，贝, l jg ( x + ) = o 定理2 2 1 2 5 1 ( 二阶必要条件) 设厂：dcr ”_ r 在开集d 上二阶连续可微，若x d 是( 2 - 2 ) 的局部极小点，贝l g ( x + ) = o ，g ( x ) o 定理2 3 吲( 二阶充分条件) 设厂：dcr ”寸r 在丌集d 上二阶连续可微，则x d 是厂的一个严格局部极小点的充分条件是g ( x ) = o 和g ( x ) 是正定矩阵 2 1 3 解决最优化问题的一般步骤 r 中国石油大学( 华东) 硕上学位论文 最优化j 可题通常采用迭代方法来求最优解，其基本结构如下： 1 ) 给定初始点：c o ，确定搜索方向嚷，即按照一定的规则，构造厂在以点处的下降 方向作为搜索方向 2 ) 确定步长因子，使目标函数值有某种意义的下降 3 ) 令而+ l = 政+ a k d k ，若+ 。满足某种终止条件，则停止迭代，得到近似最优解+ l ， 否则，重复以上步骤 2 2 以梯度法为基础的最优化方法 无约束问题的求解一般是通过一系列的一维搜索来实现的，搜索方向的选择是求 解无约束最优化的核心问题，搜索方向的不同选择，形成不同的最优化方法 2 2 1 最速下降法 算法2 1 步1 给定初始值：c o r ”，精度占，令七：= 0 ； 步2 计算巩= 一g k ；如果0 忙s ，则停止； 步3 由f ( x k + 以) = r 咖f ( x k + 口畋) 确定步长因子； 步4 计算x k + l = 吒+ 矾； 步5 令k ：= k + 1 ，转步2 关于最速下降法有如下的收敛性定理： 定理2 4 2 5 1 设厂c 1 ，在最速下降法中采用精确一维搜索，则产生的迭代点列 碗 的每一个聚点是驻点 定理2 5 瞄1 设函数厂( 石) 二次连续可微，且i l v 2 厂( z ) | i 0 ，算法2 2 1 或有限终止，或! i m ，厂( 稚) = - - 0 0 ，或! a m v f ( x , ) = 0 七 r ， 定理2 6 2 5 1 设厂c 1 ，若最速下降法采用不精确一维线搜索，则迭代点列 稚) 的每 一个聚点是驻点 注：所谓最速下降方向反= 一g k ，仅反映厂( z ) 在x 。点局部的性质，对局部来说是最 9 第一二章基础知识 速下降方向，对整体来说却不一定是最速下降方向另一方面，由步长的定义知 g k + f d 。= o ，故在两次迭代中，搜索方向是相互正交的，所以，最速下降法逼近极小值 的路线是锯齿状的，并且越靠近极小点越小，即越走越慢在实际当中，通过对最速下降 法的改进或者是把它与其它收敛速度快的算法相结合，可以得到一些有效的算法因此， 最速下降法是基本算法之一，但不是有效的实用算法 2 2 2 牛顿法 最速下降法的本质是用线性函数去近似目标函数，因此要得到快速算法，需要考虑 对目标函数的高阶逼近牛顿法就是用二次模型近似目标函数得到的 算法2 2 步1 给定初始值x 0 r ”，精度s ，令k ：= 0 ； 步2 计算g k ； 步3 若0 | i 0 ，使得对x 三，且 m l y l 2 y7 1 v 2 f ( x ) y ，r ”， 则采用精确线性搜索的p r p 共轭梯度法产生的点列 收敛于唯一的极小点z 定理2 1 2 1 设厂( x ) 二阶连续可微，水平集= x r ”i 厂( x ) 厂( ) ) 有界，步长 由w 6 l f e p o w e l l 准则 厂( 惋+ 哝矾) 厂( 坼) + 鹏繇7 哦 l 反+ 。7 畋l 一仃繇7 畋， 确定，其中0 p 1 7 1 2 ，那么，f r 方法产生的点列总体收敛，即有 ! 觋i n f g t l l = o 定理2 1 3 2 5 1 设函数厂( x ) 连续可微，w ( z ) 满足l i p s c h i t z 条件 i v f ( x ) - v f ( y ) _ mi x - y l l ， 若在共轭梯度法中步长瓯由w o l f e p o w e l l 准则 1 3 第二章基础知识 ( 故+ o t k d k ) f ( x k ) + p f z k g j d k 反“t 巩o g k r 矾， 其中0 p 伊 1 ，且下降方向以和- v f ( x , ) 之间的夹角o k 满足 o k 一 。，皖。，三 定义为c 。s 皖= 一既7 a 。( 1 l i 吼以| i ) 则对于共轭法产生的点 列 x k ) ，或者存在某个七，使得耵( ) = o ，或者( ) 一，或者夥( ) 专0 2 3 本章总结 本章以去繁就简为原则，给出最优化课程所需的最基本的知识和结论，本章内容 是整篇论文的理论依据；在第二部分，给出几种以梯度法为主的共轭梯度算法，并给出 了几个经典的收敛定理，依此为基础，展开本论文的研究工作 1 4 中国石油人学( 华东) 硕 j 学位论文 3 1 引言 第三章一类新的轭共梯度算法及其全局收敛性 考虑无约束最优化问题 m i n f ( x ) ，x r 。 ( 3 - 1 ) 这里f ：r 专r ”是一阶可微函数，共轭梯度算法是求解问题( 1 1 ) 的重要方法，特别是对 于大规模问题共轭梯度法更加有效，其迭代形式如下： 以= 二美+ 履畋一。 ：主三 其中g 。= 夥( j c k ) ，吼是通过一维搜索得到的步长，屏为参数 ( 3 2 ) ( 3 - 3 ) 关于参数展的不同取法对应于不同的共轭梯度法，著名的有： k h s = 粼 p 4 ， 胆爵 办罐产 矿= 衰岛 尼k c d = g 。k 石2 l s = 一甓掣 ( 3 5 ) ( 3 - 6 ) ( 3 - 7 ) ( 3 8 ) ( 3 9 ) 上述算法的总体收敛性已经被广泛研究例如，a 1 b a a l i 7 1 在19 8 5 年给出了f r 方 法在非精确线搜索的全局收敛结果，他证明了使用参数盯 t r 新的算法能够保证反是下降方向在本文的第三部 分，我们将对算法的下降性质及在w r o l f e 搜索下的全局收敛性进行证明 3 2 新的共轭梯度算法 记五为初始点，以为下降方向，如果反满足r 吨 0 ，使得： i i g ( x ) l y ，执l ( 3 - 1 4 ) 本文中步长吼由文献 3 2 所提出w o l f e 准则 f ( x k + 瓯) 一f ( x k ) _ r g k r 矾( 3 1 6 ) 得到，其中0 刁 1 ，0 ( - 0 0 ，4 = - g l ，置k ：= 1 ； 步2 如果0 既0 占，则停止；否则，由w o l f e 准则( 3 - 1 5 ) 和( 3 - 1 6 ) ，计算吼；令 砟+ l = 气+ 吼以 步3 计算繇+ 。，i l g k + 。i i c ，则停止；否则，令 矾+ ，= 一g 川+ 成+ 。或 其中，鼠+ 。f l 拭( 3 1 1 ) 计算所得令k _ k + l ，转步2 3 3 主要结果及证明过程 引理3 1 考虑方法( 3 2 ) - - - ( 3 3 ) ，步长由线搜索( 3 一1 5 ) 、( 3 1 6 ) 求得，屈取为( 3 1 1 ) 时，对所有七1 ，我们有g k7 1 咴 0 证明我们分两步来证明： 1 7 第三章一类新的共轭梯度算法及其伞局收敛性 1 。当弦屯m 州虬| l 时，展= 拦口r g k 对( 3 3 ) 式中畋= - g k + 屈屯， 两边同时与g 。作内积有 7 矾= - i i g 。1 1 2 + f l k g k r 畋一，= 一( 卜仃) 0 繇0 2 由盯 1 可知 g k 7 畋= 一( 1 一仃) 0 9 。1 1 2 o 2 。 当i 7 矾一。l 万i i 一。0 时，孱= 织d y ，五 o ，i i 下面用数学归纳法证明引理结论 当七= l 时，有g ，r 吐= 一怯1 1 2 o ，显然结论成立 假设结论对后一1 成立，i 郊= f f g k _ l r d k l 0 对( 3 3 ) 中畋= - g 。+ 孱以一。两边同时与g 。作内积，注意到反= 碱d y ，令 儿一，= & 一g ，我们有g k7 矾= 一1 1 1 1 2 + p 。g j 破一。 令 一g k - 1t d k 一1 + ( 五- 1 ) g j 以一l 破一l7 1 儿一l 则由( 3 1 7 ) 及( 3 1 9 ) 萑j g k r d k = 酬 联系0 1 6 ) 9 1 1 ( 3 - 1 8 ) ，贝j j 有厶7 0 f l j ( 3 2 1 ) n i ( 3 2 2 ) ，可知苁 o 再由( 3 - 2 0 ) ，可得繇7 以 0 从而对所有后1 ，均有 g ? d k q 引理3 1 表明了算法的下降性质 1 8 ( 3 1 7 ) ( 3 1 8 ) ( 3 - 1 9 ) ( 3 2 0 ) 0 2 0 ( 3 2 2 ) 畿等 中国石油人学( 华东) 硕一 ：学位论文 引理3 2 设目标函数满足假设h 成立考虑一般方法： 兵甲以为卜降万i 司，即g k 。畋 0 戚卫；看吼满足w o l f e 线搜索条件( 3 - 1 5 ) 相( 3 1 6 ) ，则有： 荟皆 证明由引理1 知7 巩 o ，故 ( ) ) 单调递减有下界，从而收敛 令 n l = 七l 繇7 畋 c 皆2 撇 1 ，2 ，) ，又抓训蚍从而有 荟皆 定理3 1 设目标函数满足假设h ，考虑方法( 3 - 2 ) - - - ( 3 3 ) ，步长由w o l f e 线搜索 r 3 1 5 1 、f 3 1 6 1 求得，反取n ( 3 1 1 ) ，则有 1 9 第三章一类新的共轭梯度算法及j 全局收敛性 ! i m i n f i g i i i i = o 七，w “ 证明我们分两步来证明结论 当l 反7 畋一l i 万i i 鼠繇一。0 时，对反= - g 。+ 屏以- i ，两边取模平方，得 以0 2 - - i g 。1 1 2 + 屈2 l 以一。0 2 2 p k g k r 吨一。 - l | 1 1 2 + 黠1 i 酬2 z ”矿”2 ( g k r 屯) ( 1 砌) i i g , 1 1 2 + 斟1 l 训2 ( 3 - 2 5 ) 因为7 以一，- o 时，则了c o ，使得对所有的后，有0 以| l c 对反= 一g 。+ 展反一。两边与g k 作内积，则有 以叫k | | 2 + 拦u 。 ( 1 - 仃) 1 2 对上式两边平方并同除以0 巩n 得 即 ( 既r 畋) 2 2卅叫2 爵 ( 3 2 6 ) 中国石油大学( 华东) 硕上学位论文 再由引理3 1 ，我们有 故 l 鱼7 1 哦y 一 ( 1 一盯) 2 22 荟丽ig14=荟砑1la,ii 惫i2 告( 1 一盯) 2 ( g _ k r _ d 了k ) 一2 0 ，则j q o ，使得对所有的七，有i l 反0 q 再由( 3 - 2 7 ) 可知 善丽1 - 8 1 1 9 。繇一。0 ，对矾= - g 。+ 反咴- l ，两边取模平方， 1 2 = l l g 。1 1 2 + 羼20 矾一。1 1 2 2 f l k g k r 畋一。 ( 3 - 2 8 ) 我们有 = i g 。l 2 2 拦枞。+ 貉| | 屯1 2 i i g 。1 1 2 砌蚺i i 剖甜 i l g k l2 勘蚶i + 籍怡i 川2 = ( 1 2 盯+ o 。2i l g a 。 一_ 。, 。i i ) i i 反0 2 ( 1 + ( 1 + 万2 慨 慨 恢。0 2 k g 。1 1 2 业) i 埘川 ) 1 2 圳2 蹲外爵外，+ 斟m + 辟引3 功， 由假设条件h ，( 3 1 4 ) 成立，即i i g ( x ) l l j 二 上 2 一后7 2 矛盾因此我们有! i m i n f g t l l = o 2 0 g k7 1 反一，l o ，则j q o ，使得对所有的七，有 由( 3 1 7 ) ) 及f l k 肼定义( 3 7 ) ，有 这里 其中，厶由( 3 - 1 8 ) 确定 k = 九b p 。 l i g k l l - - - c 。 2 9 k t d k 反一l r 吨一】+ ( 旯一1 ) g k r 瓯一l 由以+ g k = 屏以一i ，我们有 1 + ( 名一1 ) 1 k = 受一】吼一l 0 畋20 = 展28 巩一。1 1 2 - 2 9 k r 吨一0 反2 上式两边同除以( 以7 g k ) 2 并由( 3 2 0 ) 和( 3 - 3 1 ) ，我们有 器卅怂 v j 一卉c 云+ 旁 ( 哝一1 7 9 k 1 ) 2 2 2 + 卉卜叶扣 ( 3 3 0 ) ( 3 3 1 ) ( 3 - 3 2 ) ( 3 3 3 ) ( 3 3 4 ) 上妒 材 一 一： 上 捌 中国石油大学( 华东) 硕上学位论文 1 t t ( 3 2 1 ) 及旯 o ，1 】，y o r 1 ，我们有 1 + ( 五一1 ) l k 1 + ( 力一1 ) 1 7 1 + ( 允一1 ) = 旯 从而有0 鱼 0 矾1 1 2 一k 又因为丢 2 佃，从而善臀。佃，驯理褫故定理脏 综上1 。、2 。，可知! i n fi g t i i = o 成立 3 4 数值例子 我们从文献 1 5 1 选取数值例子并与f r 和p l 冲方法的迭代次数作比较来检验本章的 算法取精度g = 1 0 。6 ，并且不采用重开始策略，试验结果如下表： 表3 - 1 数值结果 t a b l e3 - 1n l i m e r i c a lr e s u l t s 函数名维数 p rf rz j c gn e w e x t e n d e dr o s e n b r o c k1 0 0 03 36 43 5 3 0 e x t e n d e dr o s e n b r o c k1 0 0 0 03 36 23 3 3 2 e x t e n d e dp o w e l l 1 0 0 02 9 0 1 7 92 0 01 7 6 e x t e n d e dp o w e l l1 0 0 0 0 2 4 2 2 2 22 1 21 5 0 p e n a l t yi 1 0 05 0 p e n a l t yi 1 0 0 01 95 01 81 5 上蚶牿 严撼 第三章一类新的共轭梯度算法及其伞局收敛性 由表3 1 可以看出，本文算法对大部分函数还是比较有效的，对于大规模的最优化 问题还是比较适合的 一 3 5 本章总结 本章研究了一类混合共轭梯度算法，对原算法进行了改进，扩大了搜索方向的适 用范围，并证明了新算法的下降性质和收敛性，数值结果证明算法是有效的我们知道 f r 与c d 方法也具有比较良好的收敛性质，把新算法中的d y 方法部分换为上述两种方法 或是与他们进行结合研究，能够得到何种结果还有待于验证和计算 2 4 中国石油大学( 华东) 硕上学位论文 4 1 引言 第四章与d y 方法有关的新的混合共轭梯度算法 考虑无约束最优化问题 m i n f ( x ) ，x r “( 4 1 ) 其中：r j r ”是是连续可微的函数。共轭梯度算法是求解问题( 4 1 ) 的非常有效的算法， 特别是对于大规模的尢约束优化问题，由于存储量小，算法简便，共轭梯度算法的优势 更加明显 共轭梯度算法的一般迭代公式为 + l = x k + 喀( 4 - 2 ) 以= _ g ：+ 屏畋一。 ：主三 c 4 3 ， 其中，g 。= w ( 黾) 为函数f 的梯度，吼为搜索步长，通过一维搜索得到，展为一标量， 不同的反的选择便构成不同的共轭梯度算法著名的算法有k h s = 粼， 展硝= 捣等这些算法的总体收敛性已经得到了广泛的研究，这其中包括 z o u t e n d i j k t 6 1 ，a i b a a l i t 7 1 ，g i l b e r t 和n o c e d a l 17 1 ，戴或虹和袁亚湘例以及p o w e l l | 1 3 1 等为确定 这些法的收敛性结果，一般要求步长满足强w o l f e 线搜索条件，即 f b k + 仅k d i ) f b 0 + p 仅k g ?