（应用数学专业论文）基于拟牛顿修正技术的两类修正梯度法.pdf

| | i i iiii iii ii i i ii ii iiil y 19 0 7 6 3 7 t w om o d i f i e dg r a d i e n tm e t h o d sb a s e dq u a s i n e w t o n u p d a t et e c h n i q u e b y t a os i j u n b s ( j i a n g x is c i e n c e t e c h n o l o g yn o r m a lu n i v e r s i t y ) 2 0 0 3 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 a p p l i e dm 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 a s s o c i a t ep r o f e s s o rl i ut a o w e n d e c e m b e r ，2 0 1 0 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：曲鬈j 是 日期；卯，年，月多日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书。 2 不保密曰。 ( 请在以上相应方框内打”) 作者签名形勤髫友日期：勿口年f 月易日 导师签名袱孤日期：厶解心月7 日 硕- f j 学位论文 摘要 众所周知，共轭梯度法和拟牛顿法是求解无约束优化问题的两类非常重要且 有效的梯度法共轭梯度法的优点是其存储量小、计算简单，适合于求解大规模 问题，而拟牛顿法的优点是其快速收敛性，并且被改善后能有效求解较大规模问 题因此对这两类方法的研究一直受到国内外许多学者的极大关注在本文中， 基于拟牛顿修正技术，对上述的两类梯度法进行了修正，提出了修正h s 共轭梯 度法及混合谱尺度b f g s 方法在第一章，我们首先简单介绍了最优化的一些基 础知识、下降算法的结构以及共轭梯度法和拟牛顿法的研究现状 在第二章，基于拟牛顿法中m b f g s 的修正技术，我们首先对h s 共轭梯度法 中搜索方向的计算公式进行了修正，其优点是所产生的搜索方向总是下降的，而 且能结合更弱的线性搜索技术来计算步长在较弱的条件下，结合非单调a r m i j o 线性搜索技术我们证明了所提出的修正h s 共轭梯度法具有全局收敛性，最后通 过数值实验验证了所提出的算法的有效性 在第三章，基于已有的m b f g s 方法、c b f g s 方法及谱尺度技术，提出了一 类混合谱尺度b f g s 方法，其优点是能有效阻止拟牛顿矩阵趋于病态，而且拟牛 顿矩阵总是被有效校正在较弱的条件下，我们证明了所提出的混合谱尺度b f g s 方法在a r m i j o 线性搜索和w o l f - p o w e l l 线性搜索下是全局收敛的，最后通过数值 实验比较了该算法与m b f g s 算法、c b f g s 算法及传统的b f g s 算法的数值表现， 数值结果表明所提出的方法具有较好的数值效果 关键词：无约束优化问题；共轭梯度法；b f g s 方法；谱尺度技术；非单调a r m i j o 线性搜索；全局收敛性 1 1 基于拟卜顿修正技术的两类修正梯度法 a b s t r a c t i ti sw e l l - k n o w nt h a tt h ec o n j u g a t eg r a d i e n tm e t h o da n dt h eq u a s i n e w t o nm e t h o d a r et w ok i n d so fv e r y i m p o r t a n ta n d e f f e c t i v e g r a d i e n t m e t h o d sf o r s o l v i n g 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 t h ea d v a n t a g eo ft h ec o n j u g a t eg r a d i e n tm e t h o d i so fl e s ss t o r a g es p a c ea n ds i m p l ec a l c u l a t i o n ，a n dh e n c ei ti ss u i t a b l ef o rs o l v i n g m i d d l e l a r g e s c a l eo p t i m i z a t i o np r o b l e m s ，w h i l et h ea d v a n t a g eo ft h eq u a s i n e w t o n m e t h o di so fr a p i dc o n v e r g e n c e ，a n da f t e ri m p r o v e m e n ti tc a ne f f e c t i v e l ys o l v e m i d d l e s c a l eo p t i m i z a t i o np r o b l e m s i nr e c e n td e c a d e s ，t h e r eh a sb e e ng r o w i n gi n t e r e s t i nt h ed e v e l o p m e n to ft h e s et w ok i n d so fm e t h o d s t h e r e f o r e t h i st h e s i si sc o n c e r n e d w i t ht h em o d i f i c a t i o nt ot h ea b o v et w ok i n d so fg r a d i e n tm e t h o d sb a s e do nt h e q u a s i - n e w t o np r i n c i p l ea n dp r e s e n tam o d i f i e dh sc o n j u g a t eg r a d i e n tm e t h o da n da m i x e ds p e c t r u ms c a l eb f g sm e t h o d i nt h ef i r s tc h a p t e r , w eb r i e f l yi n t r o d u c es o m e b a s i ck n o w l e d g e ，t h es t r u c t u r eo fd e s c e n ta l g o r i t h ma n dt h ep r e v i o u sw o r k so nt h e c o n j u g a t eg r a d i e n tm e t h o da n dt h eq u a s i - n e w t o nm e t h o d i nc h a p t e r2 ，b a s e do nt h em b f g su p d a t et e c h n i q u e ，w ef i r s t l y m o d i f yt h e c a l c u l a t i o nf o r m u l ao ft h es e a r c hd i r e c t i o ni nt h eh sc o n j u g a t eg r a d i e n tm e t h o d t h e a d v a n t a g eo f t h i sm o d i f i c a t i o ni st h a ti tc a ne n s u r et h eg e n e r a t e ds e a r c hd i r e c t i o nt ob e d e s c e n ta n dc a ne m p l o yw e a kl i n es e a r c ht oc a l c u l a t e s t e pl e n g t h u n d e rm i l d c o n d i t i o n s ，w ep r o v et h eg l o b a lc o n v e r g e n c eo ft h ep r o p o s e dm o d i f i e dh sc o n j u g a t e g r a d i e n tm e t h o d w i t ht h ea r m i j ol i n es e a r c h f i n a l l y , t h en u m e r i c a lr e s u l t ss h o wt h a t t h ep r o p o s e dm e t h o di se f f e c t i v e i n c h a p t e r3 ，b a s e d o nt h e e x i s t i n gm b f g sm e t h o d ，c b f g sm e t h o da n d 删- s c a l i n gs t r a t e g y , w ep r e s e n tam i x e ds p e c t r u ms c a l eb f g sm e t h o d i t sa d v a n t a g e i st h a ti tc a ne f f e c t i v e l yr e d u c et h ec o n d i t i o nn u m b e rt op r e v e n tt h eq u a s i - n e w t o nm a i r i 0 9 8f r o m i l l - c o n d i t i o na n dq u a s i - n e w t o nm a t r i xi s a l w a y su p d a t e de f f e c t i v e l y u n d e rm i l d c o n d i t i o n s ，w ep r o v et h eg l o b a lc o n v e r g e n c eo ft h ep r e s e n t e dm i x e ds p e c t r u ms c a l e b f g sm e t h o dw h e ni tu s e st h ea r m i j ol i n es e a r c ho rt h ew b l f p o w e l ll i n es e a r c h a t l a s t ，w ec o m p a r ei t sp e r f o r m a n c ew i t ht h em b f g sm e t h o d ，t h ec b f g sm e t h o da n d t h ec l a s s i c a lb f g sm e t h o d t h en u m e r i c a lr e s u l t ss h o wt h a tt h ep r o p o s e dm e t h o di s p r a c t i c a le f f e c t i v e 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 np r o b l e m ；c o n j u g a t eg r a d i e n tm e t h o d ；b f g s m e t h o d ；s p e c t r u ms c a l et e c h n i q u e ；n o n - m o n o t o n ea r m i j ol i n es e a r c h ； g l o b a lc o n v e r g e n c e i i i 硕i j 学位论文 目录 湖南大学学位论文原创性声明和学位论文版权使用授权书i 摘要i i a b s t r a c t i i i 第1 章绪论l 1 1 无约束最优化方法概述l 1 1 1 最优化方法的结构1 1 1 2 线性搜索1 1 1 3 常用的梯度法2 1 2 拟牛顿法的收敛理论及其修正方法：一5 1 3 共轭梯度法的研究结果与现状6 1 4 非单调线性搜索技术7 1 5 本文的主要工作8 1 6 符号表8 第2 章结合非单调线i 生搜索的修正h s 共轭梯度法1 0 2 1 引言一1 0 2 2 算法的建立1 1 2 2 1 非单调a r m i j o 线性搜索1 1 2 2 2 修正搜索方向1 l 2 2 3 修正m h s 算法1 2 2 3 全局收敛性1 2 2 4 数值实验1 5 第3 章求解无约束优化问题的混合谱尺度b f g s 方法1 8 3 1 引言18 3 2 三种常用的b f g s 算法一18 3 3 算法2 2 3 4 全局收敛性2 3 3 5 数值实验一2 7 结论3 0 参考文献3 3 致谢3 6 i v 硕二f ：学位论文 第l 章绪论 i 1 无约束最优化方法概述 最优化在现代的科技生活中有着非常广泛的应用范围，其应用领域涵盖工程、 军事、生产管理及经济等各方面，目前已成为许多工程技术人员、管理工作者和 研究人员必备的工具 1 1 1 最优化方法的结构 无约束最优化问题的一般数学模型为： m i n f ( x j ，v z q r ”，( 1 1 ) 其中函数厂为定义在尺“上的实值函数，称函数厂为问题( 1 1 ) 的目标函数，集合q 是问题的可行域 无约束最优化问题的一般求解方法为迭代法，其基本思想：事先给定一个初 始点x 。r ”，按照某个规则产生一个点列 屯) ，使当 吒) 为有限点列时，最后一 个迭代点为问题的最优解；或当其为无穷点列时，存在它的极限点为问题( 1 1 ) 的解一般地，点列 x 。) 由 x k + i = 赡+ 巩 ( 1 2 ) 迭代公式产生，其中吼 0 为步长，它由某类线性搜索确定；d 。为第七次搜索方 向，又称为下降方向，产生讫+ 。的常用准则是使得函数在+ ，处的函数值厂( 砟+ 。) 教厂( ) 要小吼及d 。的不同确定方法构成了求解问题( 1 1 ) 的不同算法 1 1 2 线性搜索 常见的线性搜索确定步长吼的方式有： ( 1 ) 精确线性搜索 要求满足： ( & + 吼以) 2 噢5 l 厂( 扳+ 口噍) ( 1 3 ) ( 2 ) a r m i j o 线性搜索 给定q ( o ，1 ) ，选取吒= m a x p ，i = o ，1 ，2 满足： 厂( 气+ 反) 厂( 五) + q g ( 吒) 7 畋， ( 1 4 ) 其中满足条件的p ( o ，1 ) 为常数 ( 3 ) w o l f e p o w e l l 型线性搜索要求步长吼满足w o l f e 条件； 基于拟，f ：顿修正技术的两类修正梯度法 ( 1 5 ) 其中常数q 、o - ：满足o q 圭，仃。 c r 2 0 时，只要初始矩阵鼠对称正定，则由修正 公式产生的矩阵序列f 鼠l 是对称正定序列；同时，在上述校正公式中，b f g s 法 最受欢迎，据大量的数值试验结果表明，b f g s 法的数值稳定性比其它校正公式 的要好，而且，它与不精确线性方法结合使用时能收到更好的效果，所以，在实 际应用中，b f g s 法应用最广 前面介绍的拟牛顿法具有很快的收敛速度，被广泛认为是非线性规划的求解 中最有效的方法之一，但算法需要存储对称正定矩阵及，因而难于求解大规模问 题共轭梯度法具有算法简便、存储量少且收敛速度较快的特点，特别适用于求 解大规模问题，近十几年来，由于计算问题规模的增大，使得其在许多领域有着 非常广泛的应用 2 0 世纪5 0 年代初计算数学家h e s t e n e s 和几何学家s t i e f e l 为求解线性方程组 a x = b ，x r ”( 1 1 4 ) 而独立提出了共轭梯度法，他们合著的文章【7 】现已成为研究共轭梯度法的重要文 献，从等式( 1 1 4 ) 中我们可以看出，当矩阵彳对称正定时，上式的求解等价于 解二次最优化问题 m i n 一1x r a x b r x ( 1 1 5 ) 2 、 从而，h e s t e n e s 和s t i e f e l 的方法也可认为是求二次函数极小值的共轭梯度法，该 方法具有有限步终止性，即最多经，z 步达到问题的最优解1 9 6 4 年f l e t c h e r 和 r e e v e s 较早的把线性共轭梯度法的思想应用于求解非线性最优化问题，得到求解 一般非线性函数极小值问题的共轭梯度法 非线性共轭梯度法求解无约束极小值问题( 1 1 ) 的迭代格式为： x k + l = 赡+ 巩，k = o ，1 ，2 ，( 1 1 6 ) 其中，步长口。由某种线性搜索得到搜索方向d 。由下式定义 d k - = j 黔肫。鬻， 其中以是参数，以的不同取法对应于不同的非线性共轭梯度法著名的有1 9 5 2 硕十学位论文 年h e s t e n e s 和s t i e f e l 提出的h s 万法 7 】，1 9 6 4 年f l e t c h e r 和r e e v e s 提出的f r 万 法 8 ，1 9 6 9 年p o l a k ，r i b i e r e 和p o l y a k 分别独立提出p r p 方法【9 ，1 0 ，1 9 8 7 年f l e t c h e r 提出的c d 方法【1 1 】，1 9 9 1 年l i u 和s t o r e y 提出的l s 方法 1 2 】，2 0 0 0 年d a i 和y u a n 提出的d y 方法 1 3 】，这些方法中的参数反分别由下面各式给出： 肛爵， m 埘 圹2 爵 ( 1 1 9 ) k h s - - 糕t ， ( 1 2 。) p c o = - 口i i 衙g , i i 。， ( 1 2 1 ) 以蹦= 盟d y k - i ， ( 1 2 2 ) 胪一糕t ， ( 1 2 3 ) 其中| | i i 为e u c l i d 范数，y k 一。= g 女- g h ，g 。= g ( 吒) 我们称相对应的共轭梯度法为 f r 、p r p 、h s 、c d 和l s 方法 这些非线性共轭梯度法的表达式形式简单，易于编程，且只需要计算和存储 目标函数的梯度值与牛顿型算法相比，共轭梯度法的存储量大大减少，因而更 加适用于求解大规模问题，事实上，共轭梯度法现已成为求解大规模最优化问题 的最受欢迎的算法之一 1 2 拟牛顿法的收敛理论及其修正方法 拟牛顿法由于相比牛顿法而言条件更宽松，不需直接计算其h e s s i a n 矩阵，且 没有要求函数厂的h e s s i a n 矩阵正定，又具有较快的收敛速度及很好的数值试验效 果，因此，近几十年来，一直备受欢迎目前，对拟牛顿法求解无约束最优化问 题在局部收敛性分析方面取得了丰硕的成果，见参考文献 1 4 ，1 5 ，1 6 】；另外，在全 局收敛性分析方面也取得了重大的突破，如p o w e l l 和d i x o n 分别在文献 1 7 】和 1 8 】 中运用精确线性搜索很好地证明了b r o y d e n 族方法凸极小化问题的全局收敛性； 另外，在1 9 8 7 年，b y r d 等在文献 1 9 】中证明了除了d f p 方法之外的b r o y d e n 族 方法在w o l f e 线性搜索( 1 5 ) 下，解凸极小化问题的全局收敛性；随后，1 9 8 9 年， b y r d 和n o c e d a l 在文献 2 0 】中证明了厂为凸函数的前提下，b f g s 方法在a r m i j o 基于拟7 卜顿修证技术的两类修正梯度法 线性搜索( 1 4 ) 的的全局收敛性 容易看出，前面我们介绍的拟牛顿法的全局收敛性都要求其目标函数厂为凸 函数，而当目标函数为非凸函数时，前面的全局收敛性是否仍然成立呢? 为此， d a i 在文献【2 1 中举出了一个反例，反例说明当采用w o l f e p o w e l l 型线性搜索时非 凸函数的b f g s 算法不全局收敛性为了克服这一缺陷，“和f u k u s h i m a 做了创 新性研究，他们分别在文献 2 2 ，2 3 中提出了修正的b f g s 算法( m b f g s ) 和保守 的b f g s 算法( c b f g s ) ，证明了在采用a r m i j o 线性搜索和w o l f e 线性搜索下， 这两种方法对非凸函数的最优化问题具有全局收敛性 1 3 共轭梯度法的研究结果与现状 在早期，非线性共轭梯度法收敛性分析的工作主要在于采取精确线性搜索 ( 1 3 ) 下求解凸极小化问题时的全局收敛性分析上，详见文献 6 】由于当时同时 创立的拟牛顿法具有良好的数值表现和全局收敛性，从而共轭梯度法在很长一段 时间被研究者所忽视 近年来，由于g i l b e r t 和n o c e d a l 2 4 给出了尸! r p 方法良好的数值结果及对该 方法关于非凸函数的全局收敛性的证明，d a i 和y u a n 2 5 对传统非线性共轭梯度法 的研究，以及许多大规模问题的出现，使得非线性共轭梯度法的研究再次受到了 大家的关注其中比较成功的是1 9 9 7 年g r i p p o 和l u c i d i 在文献【2 6 中证明了基于标 准的p r p 公式采取新的a m i j o 型线性搜索的p r p 算法的全局收敛性，及2 0 0 1 年d a i 在文献 2 7 】中提出的杂交共轭梯度法 最近h a g e r 和z h a n g 在文献 2 8 】中提出了一种新的下降共轭梯度法，该算法总 产生充分下降的方向，而且其下降方向与所采用的线性搜索无关；另夕b c h e n g 在文献【2 9 】所提出的新的二项共轭梯度法也具有上述性质 在共轭梯度法中，我们要特别提到h s 共轭梯度法h s 方法是一种收敛性与 数值表现都比较好的共轭梯度法之一而且h s 方法总是满足如下的共轭关系： d ：y = 0 ( 1 2 4 ) 并且不管是否是精确搜索，上式总是成立的 p o w e l l 证明了当步长趋于零时的全局收敛性，以及采取精确线性搜索时的求 解一致凸极小化问题时的全局收敛性但是对于非凸极小化问题，h s 算法此时不 一定收敛g i l b e r t 和n o c e d a l 讨论了下面的方法 3 0 】： 反肌= m a x t i f f s ，o ) ( 1 2 5 ) 并在搜索方向满足充分下降条件并且目标函数的导数满足l i p s c h i t z 条件时，证明 了该方法在强w o l f e 线性搜索下的全局收敛z h a n g 在文献【3 l 】中对h s 方法的下 硕上学位论文 降方向d 。利用b f g s 方法进行了修正，并在强w o l f e 下证明了其全局收敛性 1 4 非单调线性搜索技术 前面讲的线性搜索都是单调线性搜索，所谓单调线性搜索是指在每次迭代中 都能使得函数值减少，即对一切k 0 ，都有k + 。) k ) ，这类搜索方法在求最 小化问题的前提下看上去好像是非常自然的，因为问题本身就是求最小值，但这 类搜索方法存在一个缺点，即当目标函数在可行域中存在细长弯曲的峡谷的时( 在 非线性程度较高情形经常出现，女n r o s e n b r o e k 函数) ，单调搜索算法将运行缓慢为 此，1 9 8 6 年g r i p p o ，l a m p a r i e l l o 和l u e i d i 在文献 3 2 】最早提出了非单调线性搜索技 术，文中考虑了如下的非单调线性搜索方式： 厂( 而+ 畋) 。s m a 。x ( 。) 厂( 效一) + & r k g ( x k ) r 畋 ( 1 2 6 ) 基中，万( o ，1 ) ，m ( o ) - - o ，o m ( k ) m i n m ( k 一1 ) + l ，m ，m 为正整数当m = o 时， ( 1 2 5 ) 式的非单调线性搜索变为a r m i j i o 线性搜索 非单调搜索技术的一大优点是不要求函数值减少，从而使得步长o f 。的选取有 了更大弹性，即可使步长尽可能的大大量的数值试验表明，非单调搜索可以提 高算法的收敛效率，其数值表现也比单调搜索要好的多，数值计算也更加稳定， 详见文献 3 3 - 3 7 】1 9 8 9 年g r i p p o 等在文献 3 3 】中将非单调搜索技术应用到了 n e w t o n 法中，文中假设在水平集有界、充分下降条件g ( x k ) 7 d 。c l l i g ( 吒) i | 2 ， 0 以| | c 2 恬( 以) l i 都成立的条件下，证明了牛顿法的全局收敛性此后，很多人开始 关注非单调搜索技术，并将其应用于求解无约束最优化问题中 传统的非单调线性搜索主要有非单调w o l f e 线搜索和非单调a r m i j i o 线性搜索 两类，分别为： ( 1 ) 非单调w o l f e 线搜索要求步长满足： 鹏+ a k d k ) o ，0 o r o ，吒为 j ，s p ，j 2 中满足条件( 1 2 5 ) 的最大者，庸为 基于拟牛顿修正技术的两类修正梯度法 一正常数，且对m ( k ) 满足 所( o ) = o ，o m ( k ) 0 下，证明了该方法在强w 6 l f e 线性搜索下的全局收敛性 3 0 】；z h a n g 对h s 方法的 下降方向d 。利用b f g s 方法进行了修正，并在强w o l f e 下证明了其全局收敛性 3 1 】；王开荣在文献 1 】中提出了一种改进的h s 算法 展鹏：j暑耋差誊删如果。 o ，万( o ，1 ) ，仃( o ，1 ) ，砑为一给定的非负正整数( 其取值在1 0 左 右) ，步长因子口t = m a x a o ，i = o ，1 ，2 ，) ，使得 厂| k + 喀) 。溉) l 厂 州) 】十酝g k ) 1 喀， ( 2 2 ) 其中m ( o ) = o ，o _ m ( k ) = m i n m ( k - 1 ) + l ，詹 ，k 1 2 2 2 修正搜索方向 受到文献 3 1 ，3 9 15 i = h s 算法修正思想的启发，我们给出如下的修正公式： 矾磊懒r 纯。煮嚣 仁3 ， 式中 缸全 儿踽竖未秽如果害t 孟，o c 2 川 缸一1p 慨纠& 否则， ( 2 4 其中吼= + l x k = 畋，p 0 以及， o 均为常数 反：萼挲丑， ( 2 5 ) 吼= 皆， ( 2 6 ) 乙的定义( 2 4 ) 是非常重要的，它利用了拟牛顿法中m b f g s 算法的修正思想， 使得所提出的修正h s 共轭梯度法在使用非单调a r m i j o 线性搜索时具有全局收敛 性，这有效地节省算法在线性搜索时的计算量，而文献 3 1 】提出的修正h s 共轭梯 度法必须结合w o l f e 线性搜索才确保全局收敛性 根据以上两式以及破的定义，n - - l 矢n 慕十拟牛顿修正技术的两类修正梯度法 d j g ( x 。) = ( - g ( x k ) + 尾d l 。- o k z l 。) g ( 以) 一) | 1 2 + 爱磬c 咿甓等z k c 以) = 一i i g ( 以) 1 1 2 ( 2 7 ) 即在这种修正下，d j g ( x 。) = - i i g o ，s o ，r o ，万( o ，1 ) ，仃( 0 ，1 ) ，正整数厨，选取初始点 x o r ”，令k ：= 0 步1 若i i g ( x 。) i l 占，则终止算法；否则转到步2 步21 土1 ( 2 3 ) - ( 2 6 ) 计算搜索方向d 。 步3 由非单调a r m i j o 线性搜索( 2 2 ) 确定搜索步长口。 步4 计算下一个迭代点以+ l = x t + d i 步5 令k ：= k + l ，转步1 2 3 全局收敛性 为了求解方便，我们先给出本章的两个基本假设，并设为假设a ： ( 1 ) 水平集q = x r ”i f ( x ) f ( x o ) ) 有界； ( 2 ) 目标函数厂在q 上具有l i p s c h i t z 连续的梯度，即存在常数l 0 ，使得 i i g ( x ) - g ( y ) 1 l l l x - y l iv x ，y d ( 2 8 ) 同时，令刀( 尼) = m a x i i o - k f 柳( 后) ) ，厂( ) = 哟m 驯a x 。) f ( x k 一，) 显然有k m ( k ) n ( k ) k 现在，我们对新算法m h s 进行全局收敛性分析，为了证明算法的全局收敛性， 我们先给出如下引理： 引理2 1 若函数厂满足假设条件a ，d t ，口i ， 以) 由算法m h s 产生， 硕一i 二学位论文 r l 。= 施。g ( 以) 7 d 。，则序列 厂( x 啡) ) ) 单调递减，且 。l i + m 。c t 。( 。) i i g ( x n ( 。) ) 0 2 = ：o ( 2 9 ) 证明：根据( 2 2 ) 式可得： f ( x k + 1 ) 八( ) ) + 仇 ( 2 1 0 ) 由于d k g ( x 。) = - i i g ( x k ) 0 2 ，所以仇= 甄g ( 以) 7 d 。= 一融。i i g ( x k ) 1 1 2 0 ，使得 0 d k 1 m ( 2 1 3 ) 此定理的证明类似于文献【3 1 中命题3 4 2 ，省略其证明过程 下面我们给出算法m h s 的全局收敛性分析 定理2 3 在假设条件a 下，且 t ) 由m h s 算法产生的序列，则有 ! i m i n f g ( x , ) l l = o ( 2 1 4 ) 证明：利用反证法证明假设式( 2 1 4 ) 不成立，即存在常数s 0 ，使得 0 9 ( ) 0 占，v k 0 成立 由式( 2 9 ) 式可知，若! i m i n f a t 0 ，则! i m i n f l l g ( x ) 卜0 与假设矛盾 x - 若k l i 。m 。i n f a 七20 ，则存在无穷指标集k 使得 ! i _ m 。吼2 0 ( 2 1 5 ) 由非单调a r m i j o 线性搜索可知，对于充分大的k k ，f _ 1 不满i f ：( 2 2 ) ，即 有 f ( x k + f 一1 口t d ) 。；m ，；a 。x ( 女) f ( x k 一，) 】+ 万f 一1 a k g ( x k ) r d i f ( x i ) + 8t 一1 口ig ( x i ) rd t ，( 2 1 6 ) 再利用中值定理，存在。( o ，1 ) ，使得 硕l ：学位论文 k + f - 1 呸破) = 门k ) + f _ 1 a k g ( x k + 以f - 1 a a ) r 咴，( 2 1 7 ) 结合( 2 1 6 ) ，( 2 1 7 ) n - i 得 g ( x k + 段f - 1 吹) 7 咴如( 蕞) r 反 g 瓴+ 版f 一反) 7 哦- g 瓴) r 反弋1 6 ) g ( x k ) r 矾， ( 2 18 ) 又由畋的定义( 2 3 ) 有 g ( x k ) r 畋= 一i l g ( x 。) 1 1 2 所以( 2 1 6 ) 可变形为 g 瓴+ 1 4 t - 1 a a ) 7 a r k - - g ( x k ) r 畋( 1 一酬g 瓴灯 ( 2 1 9 ) 再由假设条件a ，以及以( 0 , 1 ) ，可得 i g ( x k + 4 t - 1 呸畋) r 反一g ( x k ) r 以i 上鸺f - 1 呸0 反1 1 2 厶- 1 0 以0 2 ( 2 2 0 ) 再结合( 2 1 7 ) ，( 2 1 8 ) 可得 l t 一1 训盯( 1 一。乃l l g ( x o l l 2 ， 所以，由引理2 2 q 铲一( 1 - 8 ) e a 北 这与( 2 1 5 ) 矛盾，假设不成立，即原结论成立 2 4 数值实验 本节，我们主要测试算法2 1 取不同的詹值的数值表现在算法中，我们采 用a r m i j o 搜索来计算步长，所用的测试函数来自文献 4 0 】，采用m a t l a b 7 0 编程， 全部在c p u 为2 6 6 g h z 、内存为4 8 0 m b 的电脑上运行我们使用l i g ( x 。) 0 1 0 “作 为算法的终止条件，有关的常数与参数值的选取如下： 仃= 0 6 ，万= 1 0 - 2 ，口= 1 ，p = 1 0 。6 ，= 1 表2 1 中各列的意义分别代表： p r o 测试问题的名字； n 测试问题的维数； i t e r 迭代的次数； f l l 目标函数的计算次数； g n 目标函数的梯度的计算次数； 基于拟牛顿修正技术的两类修币梯度法 算法不能有效求解测试问题 表2 1 庸取不同值时算法2 1 的数值结果 p r on m = 0 i t e rf n g n m = 3 i t e rf n g n m = 6 i t e rf n g n r o s c f r o t h b a d s c p b a d s c b b e a l e j e a s a m h e l i x b a r d g a u s s g u l f 9 l 8 l 1 2 2 1 3 8 6 8 4 7 9 4 8 4 1 5 3 6 8 7 3 1 4 0 9 9 3 5 2 3 8 2 7 l 9 3 5 8 6 5 1 1 0 9 2 3 2 2 1 7 4 6 8 8 2 凹 n m m ” 9 凹 7 ：2 “ 控 毋 卯 8 2 强 如 弘 他 的 9 3 巧 m 9 他 拍 8 勰 m 7 弱 跎 卯 孔 2 如 他 m ：2 如 m 如 拍 m 2 2 2 2 2 2 3 3 3 3 硕士学位论文 从表2 1 中我们容易看出，对大部分测试函数，算法2 1 是有效的，而且采用 非单调线性a r m i j o 搜索比采用线性a r m i j o 搜索数值表现要好，这进一步说明了 非单调技术在部分问题上的有效性和优越性，但对于函数“b a n d ”，算法不稳定， 计算失败 基于拟牛顿修正技术的两类修正梯度法 第3 章求解无约束优化问题的混合谱尺度b f g s 方法 3 1 引言 对于无约束优化问题 m i n f ( x ) ，x er ”， ( 3 1 ) 其中厂：尺”一r 的连续可微函数 我们知道，若采用拟牛顿法求解问题( 3 1 ) ，则其全局收敛性都要求目标函数厂 为凸函数，而当目标函数为非凸函数时，全局收敛性不成立为此为此，l i 和 f u k u s h i m a 分别在文献 2 2 ，2 3 中提出了修正的b f g s 算法( m b f g s ) 和保守的 b f g s 算法( c b f g s ) ，并证明了在采用a r m i j o 和w o l f e 线性搜索下，这两种方法 对非凸函数的最优化问题也具有全局收敛性 本章，我们在利用m b f g s 和c b f g s 算法的基础上，结合谱尺度b f g s 算法， 引入一种新的混合谱尺度b f g s 方法，并证明这种新的混合谱尺度在a r m i j o 和 w o l f 线性搜索下的全局收敛性，同时给出数值实验具体安排为：在3 2 节我们 简要介绍三种常用的b f g s 算法，在3 3 节给出新的算法的具体步骤及其说明， 在3 4 节证明算法的全局收敛性，最后，在3 5 节给出初步的数值实验 3 2 三种常用的b f g s 算法 由于式( 3 1 ) 只有在厂为凸函数时才能保证b f g s 算法的全局收敛性，为了 克服这种缺陷，我们介绍三种b f g s 的修正算法考虑到本文是对谱尺度b f g s 方法的修正研究，所以下面将重点介绍第三种谱尺度b f g s 算法 ( 1 ) m b f g s 算法 设厂二次连续可微，令包+ l = v 2 厂( 故+ 。) + v k l ，i r ”为单位矩阵，可得： 喀+ 。( 奴+ 。一) = ( v 2 厂( t + 。) + 咋，) ( 矗+ 。一) g ( 以+ 。) 一g ( 以) + 唯( + 。- x , ) 令= + ，一x k ，兵= g ( x k + 。) 一g ( x k ) + v k