（计算数学专业论文）重新开始的mprp共轭梯度法及其n一步二次收敛.pdf

ar e s t a r tm p r p c o n j u g a t eg r a d i e n tm e t h o da n d i t sn - s t e pq u a d r a t i cc o n v e r g e n c e t i a nb o s h i b e ( h u n a nu n i v e r s i t y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fs c i e n c e l n c o m p u t a t i o n a lm a t h e m a t i c s i nt h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rl id o n g h u i a u g u s t ，2 0 1 0 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体 已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：y 矽寸薅享日期：h d 年夕月 g 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密刚 ( 请在以上相应方框内打“”) 作者签名：印寸鲻士 剔帷圈吲 日期：伽o 年9 月g 日 日期：矿哞7 月g 日 硕士学位论文 摘要 p r p 算法是最著名的非线性共轭梯度法之一在精确线性搜索下，该算法具有 全局收敛性和线性收敛速度如果在算法中采用重新开始的策略，则采用精确线性 搜索的p r p 算法具有n 一步超线性或二次收敛性最近，一种修正的p r p ( m p r p ) 算法被提出，该算法具有充分下降性在一定的条件下，采用某种非精确线性搜索 的m p r p 算法具有全局收敛性本文研究采用非精确线性搜索的m p r p 算法的 收敛速度 在本文第二章，我们首先证明采用a r m i j o 型线性搜索和w o l f e - p o w e l l 型线性 搜索的m p r p 算法具有线性收敛速度进一步，我们给出一种精确线性搜索步长 估计，利用此估计作为非精确线性搜索的初始步长，以提高算法的效率为了提高 算法的收敛速度，我们在m p r p 算法中提出一种重新开始准则在此基础上提出一 种采用重新开始策略的m p r p 算法( 称为r m p r p 算法) 在一定的条件下，我们 证明，采用重新开始策略的m p r p 算法在a r m i j o 型和w o l f e - p o w e l l 型非精确线性 搜索下具有n 一步超线性或二次收敛速度 最后我们通过大量的数值试验检验本文提出的r m p r p 算法的数值效果首 先，我们选取规模较小的问题，检验r m p r p 算法的扎一步二次收敛性然后，我们 运用r m p r p 算法求解大量的大规模的问题，并对r m p r p 算法与不采用重新开 始策略的m p r p 进行比较我们从算法的c p u 时间，函数的计算次数和梯度的计 算次数三个方面对r m p r p 算法与和不采用重新开始策略的m p r p 算法进行比 较结果表明本文提出的r m p r p 算法具有明显的优势 关键词：无约束最优化；p r p 法；m p r p 法；重新开始的共轭梯度法；初始步长； 礼一步二次收敛性 i i a b s t r a c t t h ep r pm e t h o di so n eo ft h em o s tf a m o u sc o n j u g a t eg r a d i e n tm e t h o d s i t i sw e l l - k n o w nt h a tt h ep r pm e t h o dw i t he x a c tl i n es e a r c hi s g l o b a l l ya n dl i n e a r l y c o n v e r g e n t i fs o m er e s t a r ts t r a t e g yi sa d o p t e d ，t h ec o n v e r g e n c er a t eo ft h em e t h o d c a nb en - s t e ps u p e r l i n e a x q u a d r a t i c r e c e n t l y , as o - c a l l e dm o d i f i e dp r p ( m p r p ) m e t h o di sp r o p o s e d t h em p r pm e t h o dw i t hs o m ei n e x a c tl i n es e a r c hi sa l s og l o b a l l y c o n v e r g e n t t h ep u r p o s eo ft h i sp a p e ri st oi n v e s t i g a t et h ec o n v e r g e n c er a t eo ft h e m p r pm e t h o dw i t hi n e x a c tl i n es e a r c h i nc h a p t e r2 w ef i r s ts h o wt h a tt h em p r pm e t h o dw i t ha r m i j ol i n es e a r c h o rw o l f el i n es e a r c hi sl i n e a r l yc o n v e r g e n t i no r d e rt oi m p r o v et h ee f f i c i e n c yo ft h e m p r pm e t h o d ，w ed e r i v ea ne s t i m a t et ot h ee x a c tl i n es e a r c hs t e p l e n g t ha n du s e i ta st h ei n i t i a ls t e p l e n g t hi nt h ei n e x a c tl i n es e a r c h w et h e ni n t r o d u c ear e s t a r t s t r a t e g yi nt h em p r pm e t h o da n dp r o p o s ear e s t a r tm p r pm e t h o d ( c a l l e dr m p r p m e t h o d ) u n d e ra p p r o p r i a t ec o n d i t i o n s ，w es h o wt h a tt h er m p r pm e t h o di sg l o b a l l y c o n v e r g e n t m o r e o v e r i tr e t a i n s 讫一s t e ps u p e r l i n e a r q u a d r a t i cc o n v e r g e n c ep r o p e r t y f i n a l l y ，w ed oe x t e n s i v en u m e r i c a le x p e r i m e n t st ot e s tt h ep e r f o r m a n c eo ft h e p r o p o s e dr m p r pm e t h o d w ef i r s tt e s tt h eq u a d r a t i cc o n v e r g e n c eo ft h er m p r p m e t h o do ns o m es m a l lp r o b l e m s t h er e s u l t ss h o wt h a tt h er e s t a r tm p r pm e t h o d d o e sc o n v e r g eq u a d r a t i c a l l y w et h e nc o m p a r et h ep e r f o r n m n c e o ft h er m p r pm e t h o d w i t ht h a to ft h eo r d i n a r ym p r p m e t h o d ( w i t h o u tu s e o fr e s t a r ts t r a t e g y ) w ec o m p a r e t h e mi nt h ec p ut i m eu s e d ，t h en u m b e ro ff u n c t i o ne v a l u a t i o n sa n dt h en u m b e ro ft h e g r a d i e n te v a l u a t i o n s t h er e s u l t ss h o wt h a tt h ep r o p o s e dr m p r pm e t h o do u t p e r f o r m s t h eo r d i n a r ym r p rm e t h o d k e yw o 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 ；p r pm e t h o d ；m p r pm e t h o d ；r e s t a r t c o n j u g a t eg r a d i e n tm e t h o d ；i n i t i a ls t e p l e n g t h ；n - s t e pq u a d r a t i cc o n v e r g e n c e i i i 硕士学位论文 目录 学位论文原创性声明和学位论文版权使用授权书i 摘要i i a b s t r a c t i i i 第1 章绪论1 1 1 求解无约束最优化问题的下降算法1 1 2 共轭梯度法及其收敛性4 1 3 重新开始的共轭梯度法9 1 4 本文的主要工作1 1 第2 章重新开始的m p r p 算法及其收敛性分析1 3 2 1m p r p 算法的线性收敛性1 3 2 2 重新开始的m p r p 算法及其全局收敛性1 7 2 3 重新开始的m p r p 算法的n 一步二次收敛性2 0 第3 章数值试验2 5 3 1 小规模问题的数值试验2 5 3 2 大规模问题的数值试验2 7 结论3 1 参考文献一3 2 附录a 3 5 附录b 3 7 致j 谢4 0 i v 硕士学位论文 第1 章绪论 1 1 求解无约束最优化问题的下降算法 在本文，我们用舻表示扎维的实向量空间，舻x ”表示m 礼的实矩阵空间 设向量3 7 舻，我们用一表示其第i 个元素一般情况下，我们假设x 是列向量， 即 我们用z t 表示向量z 的转置对，我们用表示其第i 行第j 列 处的元素，x 丁表示矩阵x 的转置 若函数f ：r n _ r 二次连续可微，我们用v f ( x ) 和v 2 ，( z ) 分别表示，在点 z 处的梯度向量和h e s s i a n 矩阵，即 v f ( x ) =v 2 f ( x 1 = 为了简便起见，我们在本文记夕( z ) = v f ( x ) 考察如下无约束最优化问题： m i n ，( z ) ，z 月，( 1 1 ) 其中，设函数，：船一r 连续可微求解无约束最优化问题( 1 1 ) 常用下降算法 为此，我们先引入下降方向的概念我们称d 是函数，在点z 处的一个下降方向 若它满足： g ( z ) t d 0 令k ：= 0 步1 若l i 鲰l i ，则算法终止，得问题的解x k 否则，转步2 步2 确定下降方向噍，使得 菇d k 0 步3 确定步长q 七，使得 j f ( x k + o l k d k ) f ( x k ) 一1 一 fl， 科抟； 舭 s ， x = 阵 z 矩 、上n 上m 壤；毪皆貉锯；壤挚瓣裂；掣 币新开始的m p r p 共轭梯度法及其n 一步二次收敛 步4 令z 七+ 1 = x 南+ q 七d k ，k ：= k + 1 转步1 注算法i 中纨是夕( z 忌) 的简写，i i 0 表示向量的欧式范数，l i 鲰i l e 称为算 法的终止准则步3 中的参数o t 七称为步长确定步长的方法有很多，我们将在下一 节中介绍几种常用的确定步长o t 七的线性搜索算法 算法i 中确定步长o l 七的线性搜索方法可分为两种，即精确线性搜索和非精确 线性搜索 精确线性搜索确定的步长o l 七使函数，在直线z 七+ a d k 上达到最小，即o l 南是 下面的一维最优化问题的解： ，( z 后+ a k d k ) = 理i 羿，( + a d k ) ( 1 2 ) 这种o 七也叫最优步长因子由于求一元函数的最小值问题也是一件不容易的事情， 因此精确线性搜索方式所需的计算量较大 非精确线性搜索通常要求o k 使得厂( z 七+ q 七d k ) 较，( z 七) 有一定的下降量下 面介绍几种常用的非精确线性搜索 a r m i j o 型线性搜索【1 】：给定口l ( 0 ， ) 和p ( 0 ，1 ) ，确定q 南= m a x f i i = 0 ，1 ，2 ，) 使得 f ( z k + a k d k ) f ( x k ) + a x a k g 吾d k ( 1 3 ) 在a r m i j o 型线性搜索中，若p ( 0 ，1 ) 接近于1 ，则相当于两次试探步的改变量 相对较小此时，需要经过较多的搜索才能得到q 七，若p ( 0 ，1 ) 接近于0 ，则相当于 两次试探步的改变量相对较大此时，可经过相对较少的试探步得到a 七但获得的 步长o t 七可能很小为了克服a r m i j o 型线性搜索的不足，可采用下面的w o l f e - p o w e l i 型非精确线性搜索 w o l f e - p o w e l l 型线性搜索【2 ，3 1 ： 给定o 1 ( 0 ，) ，盯l 0 2 1 和p ( 0 ，1 ) ，确定 q 知= m a x p i l i = 0 ，1 ，2 ，) 使得 m 七+ q 七d 惫) f ( x k ) + 啪七鳍呶， ( 1 4 ) i 夕( z 七+ q 七毗) t d 七 a 2 9 t d k 、7 除了上面的a r i i l i j o 型线性搜索和w o l f e - p o w e l l 型线性搜索外，比较常用的还 有下面的a r m i j o - g o l d s t e i n 型线性搜索和强w o l f e 型线性搜索 a r m i j o - g o l d s t e i n 型线性搜索1 1 , 4 1 ：给定0 1 ( 0 ，石1 ) 和口1 c r 2 0 使得 f ( x k + a k d k ) ，( z 七) + 盯1 q 七夕吾d 知，( 1 5 ) 、i 上uj i ( z k + o e k d k ) y ( z k ) + a 2 9 t d k 、 。 强w o l f e 型线性搜索：给定o 1 ( o ，互1 ) 和o 1 0 使得当k 充分大时， i x k + l z + 0 m i i x , 一z + 0 2 成立，则称 z 七) 二次收敛于矿，或称 x k 】的收敛速度是二次的 在算法i 中不同算法的主要区别在于确定下降方向噍的方式若取下降方向 为d k = = - - g 南，相应的下降算法称为最速下降法最速下降法是求解问题( 1 1 ) 的最 古老方法之一1 5 j ，该算法的全局收敛性定理如下 定理1 1 1 设厂：舻_ 只在r ，1 上连续可微且下有界，9 ( z ) 在水平集q = z l f ( z ) 。f ( x o ) ) 上连续且满足l i p s c h i t z 条件序列 z 七】是由精确线性搜索，或 a r m i j o 型线性搜索，或w o l f e - p o w e l l 型线性搜索的最速下降法生成，则 1 i ml i g ( x 七) l i = 0 下面的定理给出了最速下降法求解严格凸二次函数极小值问题时的线性收敛 速度估计证明可参考文献 6 】中定理3 3 和 7 】中定理5 1 定理1 1 2 设矩阵q 舻跏对称正定，q 舻记入和a 州n 分别是q 的 最大和最小特征值，k = ；竺考察如下二次函数极小化问题： a m i n 1 m i n ，( z ) = 石z t q x + q t z ( 1 7 ) 设 z 七) 是采用精确线性搜索的最速下降法求解上述问题得到的序列则下面的不 等式对所有的k 0 成立： i i 嘶1 一矿i i q ( 鬲) 恢一矿 更精确的，我们有下面的不等式对所有的k 0 成立： l x k t - 1 - - x * 0 使得 矿v 2 f ( x ) d m 1 1 2 ，vd r n ，vz q 其中q = x l f ( x ) ，( z o ) ) 序列 z 七) 由牛顿法产生，其中步长q 七由精确线性搜 索，或a r m i j o 型线性搜索，或w o l f e - p o w e n 。型线性搜索确定，则_ 【z 七) 收敛于，在 q 中的唯一全局最小值点 定理1 1 - 4 设定理1 1 3 的条件成立，序列 z 知) 是由采用a r m i j o 型线性搜索 或w o l f e - p o w e l l 型线性搜索产生，则 。七) 超线性收敛于，的全局最小值点矿此 外，若假设v 2 ，( z ) 在矿处l i p s c h i t z 连续，则 z 七) 二次收敛于矿 牛顿法的主要优点是其具有二次收敛性，但该算法要求对所有的k ，v 2 ，( 飘) 正定否则，不能保证所得到的方向为下降方向因此牛顿法对求解严格凸函数的 极小值比较合适在实际应用中，一般情况下很难保证对所有的k ，v 2 ( x 七) 正定 从( 1 8 ) 式我们知道，牛顿法需要计算函数，的二阶导数信息，当问题规模较大时： 计算函数，的二阶导数的工作量将会很大 1 2 共轭梯度法及其收敛性 共轭梯度法是介于最速下降法和牛顿法之间的一种方法它仅需利用目标函 数一阶导数信息，这不仅克服了最速下降法收敛慢的缺点，而且避免了存储和计算 牛顿法所需要的二阶导数的信息共轭梯度法分为线性共轭梯度法和非线性共轭 梯度法下面我们首先简单回顾线性共轭梯度法 设q r n 肌是对称正定矩阵我们知道求解如下的线性方程组 q x = b ( 1 9 ) 等价于求解下面的严格凸二次函数极小值问题： 1 m i n ( x ) = 言z 丁q z + q t z ，z r n( 1 j o ) 一4 一 硕士学位论义 其中q 舻也就是说，问题( 1 9 ) 和问题( 1 1 0 ) 有相同的唯一解为了求解问题 ( 1 1 0 ) ，在2 0 世纪5 0 年代，h e s t e n e s 【8 】和s t i e f e l 【9 】提出了线性共轭梯度法我们首先引 入向量组共轭的概念 定义1 2 1 设q 舻煳对称正定，d l ，d m 是舻中非零向量，若对i ，歹= 1 ，m a t q d j ：0 ，t j ， 则称向量组d 1 一，d m 关于矩阵q 相互共轭 求解问题( 1 1 0 ) 的线性共轭梯度法的思想是：从某个初始点z o 出发，依次沿 关于q 相互共轭的礼个方向d i ，i = 1 ，礼进行精确线性搜索，即令 z 七+ 1 = z 七十o e k d k ，k = 0 ，1 ，n 一1 ，( 1 1 1 ) 其中，q 七由( 1 2 ) 式产生 对线性共轭梯度法我们有如下定理 定理1 2 1 对正定二次函数，线性共轭梯度法至多经过礼步精确线性搜索终 止；且每一x k + 1 都是，在x o 和方向d o ，d 1 ，靠所张成的线性流形 z i z = x o + 七 a i d i ，v o q 月! ) 中的极小点 i - - - - 0 上述定理又叫子空间扩展定理，它给出了线性共轭梯度法的一个重要性质一 二次终止性。 定义1 2 2 若一个算法用于求解严格凸的二次函数极小值时，从任意的初始 点出发，算法经过有限次迭代后可达到函数的最小值点，则称该算法具有二次终止 性 下面我们给出线性共轭梯度法的线性收敛性证明可参考文献【1 0 】中定理8 2 定理1 2 2 设矩阵q 的特征值为a 1 入2 h ，序列 z 七) 是基于上述求 解问题( 1 1 0 ) 的线性共轭梯度法产生，下面的不等式对所有的奄0 成立： o z 七+ l 一2 7 o q ( 安n - k - - , a 1 ) l l z 七一z i i q a n - k 1 其中矿是问题的唯一解 求解一般无约束问题( 1 1 ) 的非线性共轭梯度法是在线性共轭梯度法的基础 上发展起来的非线性共轭梯度法利用负梯度方向一鲰与算法的前一个搜索方向 的线性组合作为第次迭代的搜索方向，且初始方向为一g o ，即 也= 一- - 鲰g k + 反畋一。，：蓁呈： c 1 1 2 ， 其中，参数仇的确定使得算法用于求解问题( 1 1 0 ) 时，以和d k 一1 关于q 相互共 轭 一5 一 鼋新开始的m p r p 共轭梯度法及其n 一步二次收敛 最早的非线性共轭梯度法是由f l e t c h e r 和r e e v e s 在1 9 6 4 年提出的f r 算法【1 1 】， 其中参数仇取为 臼k f r - - - 黔 在此基础上，我们给出非线性共轭梯度法的计算步骤如下： 算法i i ( 非线性共轭梯度法一f r 算法) 步0 取初始点z 舻，d o = 一v f ( x o ) ，精度e 0 令k ：= 0 步1 若l i v f ( x k ) l l ，则算法终止，得问题的解否则，转步2 步2由线性搜索确定步长q 七 步3 令x k + 1 = x k + o e k d k 。 步4由( 1 1 2 ) 式确定以+ 1 ，其中凤= 硝兄令k ：= k + 1 转步2 在( 1 1 2 ) 式中选取不同的更新参数仇，我们将会得到不同的非线性共轭梯度 法除了上面的f r 算法外，比较著名的非线性共轭梯度法有h s ( h e s t e n e s - s t i e f e l ) 法【1 2 】：p r p ( p o l a r k - r i b i b r e - p o l y a k ) 法 1 3 , 1 4 ，c d ( f l e t c h e r - r e e v e s ) 法f 1 5 1 ，l s ( l i u - s t o r e y ) 法【1 6 1 ，d y ( d a i y u a n ) 法1 1 7 这些算法中风的选取方式分别如下： 8 k = 8 k = 凤= 反= 雎s = 老t 篆k 鹄， p 3 七k p r p = 智， 酽= 磊i l g k l l 2 ， 磁s 一掣， 厥= 卯y = 瓦而i l g k l l = ( k - - - 1 “1iu 一j 若将算法i i 步4 中的凤= 硝r 分别改为凤= 雕s ，反= 雎r p ，凤= 鳄d ， 凤= 磁s 或风= 卯y ，我们称相应的算法为h s 算法，p r p 算法，c d 算法，l s 算 法或d y 算法当这些算法用于求解严格凸二次函数极小化问题( 1 1 0 ) 时，若步长 q 詹由精确线性搜索得到，那么f r 算法，p r p 算法，c d 算法，l s 算法或d y 算法 等价证明可以参考文献【1 8 1 中定理5 2 1 下面的定理表明，当用于严格凸二二次函数极小化问题的求解时，f r 算法产生 的方向关于目标函数的h e s s i a n 矩阵相互共轭 定理1 2 3 设序列x k l 由精确线性搜索的f r 算法求解严格凸二次函数极 小化问题产生，则向量组 以) 活n - 0 1 关于q 相互共轭，而且，对任何k 佗，有 d j = 0 ，鲥g j = 0 ，坳 写1 ，他们在相同的文献中举出了反例，表明f r 法可能产生一个上升方向而导 致失败z h a n g ，z h o u 和l i 2 3 1 在2 0 0 6 年提出了修正f r ( m f r ) 法在m f r 算法中 下降方向也是由下面的方式确定： 以2 一- 鲰( 1 + 巩) g k + 硝r d k 一。，七k 三。1 ： ( 1 1 3 ) i + 巩+ 磁一一1 ， ， 、。 其中，硭r 是由f r 算法确定， o k - - - - 替酽= 器 m f r 算法与f r 算法的区别存于系数以若0 k = 0 ，则m f r 算法与f r 算 法一致特别地，若采用精确线性搜索，则巩= 0 此时，m f r 算法与f r 算法足同 一算法他们证明由m f r 算法产生的方向毗具有充分f 降性同时他们给出了 如下步长q 七的修正a r m i j o 型线性搜索给定0 1 ( 0 ， ) ，0 2 0 和p ( 0 ，1 ) ，取 q 七= m a x ( p i = 0 ，1 ，2 ，) 使 ，( z 七+ o r k d k ) f ( x k ) + a l o l k g t d k 一0 2 l i q 七d k l l 2 ( 1 1 4 ) 并且证明了m f r 法在线性搜索( 1 1 4 ) 下对非凸无约束优化问题具有全局收敛性 虽然f r 法具有全局收敛性，但是它的数值试验结果并不理想，并且收敛速度 很慢p o w e l l1 2 4 在精确线性搜索下分析了f r 法可能连续产生小步长的性质，即如 果f r 法在某一步产生很小的步长，则相继的许多步长也可能非常小这说明f r 法可能收敛非常慢，也给出了f r 法在实际数值计算中表现不好的理论解释m f r 算法一定程度上解决了产生小步长的问题，但数值结果仍不尽满意 ( 2 ) p r p 算法 p r p 方法是由p o l a k 和r i b i 爸r e ，p o l y a k 在1 9 6 9 年独立提出的一种非线性共轭 梯度法，它是目前被认为数值表现最好的共轭梯度法之一当算法产生小步长时，由 p r p 方法定义的搜索方向以能自动靠近负梯度方向，从而具有自动重新开始的功 能，能够有效的避免像f r 方法可能产生小步长的缺点 一7 一 审新开始的m p r p 共轭梯度法及其扎一步二次收敛 p o w e l l 在文献【2 4 】中证明了当步长8 七= z 七+ 1 一巩趋向于零时p r p 方法的全 局收敛性，并且证明了采取精确线性搜索的p r p 方法求解一致凸极小化问题时的 全局收敛性但是，即使对于一致凸的目标函数，g i l b e r t 和n o c e d a l 【2 5 】举出例子表 明，臃r p 也可能为负因此，当i i d k l i 很大时，相邻两个搜索方向会趋于相反为了 避免这种现象，g i l b e r t 和n o c e d a l 考虑了如下的p r p + 方法： 硝r p + = m a x 【雕r p ，o ) 他们证明了在a r m i j o - w o l f e ( 或强w r 0 1 f e ) 型线性搜索下，p r p + 方法求解非凸函数 极小化问题时的全局收敛性 为了保证p r p 方法产生下降方向，z h a n g ，z h o u 和“【2 6 】基于l - b f g s 【2 7 】法的 迭代格式，构造出一种新的共轭梯度法m p r p 法该算法中方向也由下式给出： d k ： 一g k ， k = 0 ， ( 1 1 5 ) l g k + 心p k p r p u a 知一1 一目七鲰一l ，k l ， 其中o k - 蠹蒂，y k - 1 g k 一鲰。从而，我们可以得到 靠d k = 一0 玑1 1 2 即m p r p 法能始终保证充分下降性，这种充分下降性不依赖于算法所采用的线性 搜索特别地，m p r p 算法具有二：次终止性，而且当我们采取精确线性搜索，即 0 七= 0 时，m p r p 法的迭代格式还原到通常的p f u p 方法的迭代格式此时，m p r p 方法就是我们传统的p r p 方法他们同时给出了m p r p 在另一种修正的a r m i j o 型线性搜索，即q 七满足 f ( z k + e z k d k ) f ( z k ) 一6 a 2 | | 毗1 1 2 条件下的全局收敛性 ( 3 ) h s 算法 h s 方法与p r p 方法非常类似，它们的收敛性和数值效果表现都差不多，由前 面的讨论可知，采取精确线性搜索的h s 方法求解一般非凸极小化问题时不一定收 敛类似于p r p + 方法，g i l b e r t 和n o c e d a l 在文献【2 5 】也讨论了下面的h s + 方法： 雎s + = m a x 雎s ，o 一 戚厚铎等f 2 8 】考虑了如下修正的h s 方法： 凤= m a x 。，m i n 雎s ，南) ， 并且在无充分下降条件下，建立了方法的全局收敛性 最近，d a i 和l i a o 2 9 】利用拟牛顿方程和h s 方法的共轭性质，提出下面的d l + 公式： 卯扩= m a x 耠，。) 一石t g t s 磊k _ l ， 硕士学位论文 其中y k l = g k g k l ，8 k l = z l | 一z 七一1 ，t 0 是参数 基于文献f 2 9 】中d l 方法的思想和上面新的割线条件，y a b e 和t a k a n o 【删提出 了一种新的共轭梯度法： 硝p = m a x 器，旷珏t g t s 磊k _ l ， 其中p 0 为参数， 卜一- = y k - 1 - 4 - p ( 。石o k 石- 1 s m l0 k l = 6 ( f ( x k l 一，( z 七) ) ) + 3 ( g k 一1 - 4 - 纸t s 七一1 ) 如果搜索方向满足充分卜降条件，则h s + 方法，d l + 方法，y t + 方法在强 w r o l f e 线性搜索下求解非凸极小化问题时具有全局收敛性，参见文献【2 5 ，2 9 ，3 1 3 3 】 尽管如此，若采用a r m i j o 型线性搜索时，这几种方法都不能保证产生下降方 向最近，h a g e r 和z h a n g 在文献【3 2 】也提出了一种不依赖线性搜索就能产生下降 方向的非线性共轭梯度法： 倚片z 9 吾( 玑一1 2 ：i 亍l y 七_ - _ , 1 1 2 0 k _ l y k - 1 s 知一1 ) 盘h z 版2 1 西云一 为了证明h z 方法的全局收敛性类似于d l + 方法和y r r 十方法，他们提出了下面 的修正公式： 雎z + = m a x 硭z ，孤) ，讯= 呶一1 1 im i n y ，i i 鲰一1 吣 其中叼 0 为常数同时，他们证明了h z + 方法满足g t d k 一副肌i | 2 这种充分下 降性不依赖于任何线性搜索 下面，我们对非线性共轭梯度法的收敛速度进行估计以下定理表明，采用精 确线性搜索的非线性共轭梯度法至少具有线性收敛速度证明参考文献【1 8 】中定 理5 4 1 定理1 2 4 设函数，：舻_ r 二次连续可微，序列 z 七) 收敛于矿，是由采 用精确线性搜索的非线性共轭梯度法得到并且在点矿有g ( x ) = 0 和v 2 f ( x ) 正定那么存在常数b 0 ，r l ( 0 ，1 ) 使得当k 充分大时，点列 z 七) 满足 i i z 七十1 一z + 0 6 l r ： 下一章，我们将主要研究采用非精确线性搜索的共轭梯度法的收敛速度 有关求解无约束优化问题的共轭梯度法的其它进展，可参考文献【3 4 4 4 】 1 3 重新开始共轭梯度法 本节我们主要回顾重新开始的方法从上一节我们知道，采用精确线性搜索的 共轭梯度法具有线性收敛速度如果对标准的共轭梯度法采用每r ( r n ) 步沿负 一9 一 苇新开始的m p r p 共轭梯度泫及其n 一步二次收敛 梯度方向的重新开始策略，即 d i r + 1 = - g i r + 1 ，i = 0 ，1 ，2 ，( 1 1 6 ) 则收敛速度可以从原来的线性收敛提高到礼一步超线性收敛甚至n 一步二次收敛性 数值计算也表明采用每r 步沿负梯度方向重新开始的策略将改善共轭梯度法的表 现c o h e n 4 5 1 和b u r m e i s t e r 【4 6 】给出如下定理，证明了r 步重新开始的共轭梯度法具 有n - - 步二次收敛性，即 i i z 七r + n z 4 i l = o ( 1 l x k r z + i | 2 ) 其中矿是目标函数的极小值点 定理1 3 1 设厂? 舻一r 是i 次连续可微的一致凸函数，序列 z 七) 是在 精确线性搜索下，采用r 步重新开始的p r p 或f r 共轭梯度法产生则存在常数 c 0 使得 h m 七。s 。u p 蹦c 其中，矿是厂的唯一极小点 然而，上面的重新开始策略具有以下缺点：一是它舍弃了算法沿着前一次搜索 方向d 七一1 得到的二阶导数信息；二是重新开始的频率一般与目标函数的性质有关 p o w e l l 在文献 2 4 】中使用不同的频率对用最速下降方向作为重新开始方向做了数 值试验，结果发现函数的即刻下降量比不采用重新开始技巧时反而小b e a l e 【4 7 1 给 出了一种新型的重新开始策略，其下降方向如具有如下形式： d k = 一鲰+ 仇d k 一1 + 饥d t ，( 1 1 7 ) 其中1 f k 为某整数， 凤2 蓑篆茜， ( 1 1 8 ) io ，若k = t - i - 1 ； 讯2 1 爨坐掣， 其它 ( 1 - 9 ) i 田( g t + 1 一g t ) 硝 从( 1 1 7 ) 式我们知道，b e a l e 的重新开始方法充分利用了算法沿方向毗一l 已经 得到的二阶导数信息当采用精确线性搜索和目标函数为凸- 次函数时，上述定义 的搜索方向仍能相互共轭从理论卜来说，b e a l e 重新开始方法克服了7 - 步重新开 始方法的缺点但是，m c g u i r e 和w o l f e 【镐】就b e a l e 重新开始方法做了大量数值试 验，数值结果却令人失望p o w e l l 在文献【2 4 】通过引入一个新的重新开始准则，即 如果下式不成立： l g t g k 一1i c l l g k1 1 2 ， 其中c ( 0 ，1 ) 为常数，也使方法重新开始，克服了m c g u i r e 和w | o l f e 的困难，并且 获得了令人满意的数值结果p o w e l l 的重新开始策略较好的避免了方法收敛到一 一1 0 硕士学位论文 个非稳定点此外，当目标函数，包含较多对称信息，或v 2 f ( x ) 有少量大的特征 值而其余的特征值聚集在一起时，这种重新开始策略也使得算法在小于n 步时重 新开始我们把b e a l e 的重新开始策略和p o w e l l 的重新开始策略结合起来，统称为 b e a l e - p o w e l l 重新开始法 p o w e u 在文献【4 9 】中构造的一个例子说明了，即使采用精确线性搜索，上面的 b e 如p o w e l l 重新开始法也不一定收敛为了建立b e a l e - p o w e u 重新开始法的全局 收敛性，d a i 和y u a n 【剐给出了修正的b e a l e - p o w e l l 重新开始法，即令 鲇= m a x 凤，o 】，付= m a x t k ，o ) 同时，对非重新开始的点列要测试充分下降性，在强w b l f e 型线性搜索下，他们给 出了算法的全局收敛性d a i ，l i a o 和l i 【5 l 】基于b f g s 算法的迭代格式，给出了两 种新的重新开始的共轭梯度法，并且证明了算法的全局收敛性 1 4 本文的主要工作 共轭梯度法具有存储量少的特点，适合求解大规模优化问题此外，若采用精 确线性搜索，则p r p 算法等著名的共轭梯度法还具有仃一步超线性收敛性或n 一步 二次收敛性迄今为止，共轭梯度法的收敛速度研究都集中于采用精确线性搜索 的算法对于用非精确线性搜索，尚未见有关共轭梯度法收敛速度的研究研究采 用非精确线性搜索时共轭梯度法的收敛速度的主要困难在于此时算法不再具有二 次终止性本文在z h a n g ，z h o u 和l i 在文献【2 6 】提出的修正p r p ( m p r p ) 算法的 基础上，研究采用非精确线性搜索的m p r p 法的收敛速度 首先我们证明m p r p 法在a r m i j o 型线性搜索或w o l f e - p o w e l l 型线性搜索下 具有线性收敛性为了提高算法的效率，我们在文献2 6 1 的基础上给出一种精确 线性搜索步长的估计形式，并将此估计作为非精确线性搜索的初始步长进而提 出一种采用重新开始策略的m p r p 算法，称之为r m p r p 算法在适当的条件下， 我们证明r m p r p 算法具有全局收敛性和n 一步二次收敛性最后，我们通过大量 的数值试验检验