（应用数学专业论文）无约束优化问题的记忆梯度法的若干研究.pdf

海南大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取 得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写 过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律结果由本人承担。 论文作者签名：建爪 吼7 , o 0 年乡月夕 学位论文版权使用授权说明 本人完全了解海南大学关于收集、保存、使用学位论文的规定，即：学校有权保留并向 国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权海南大 学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。本人在导师指导下完成的论文成果，知识产权归属海 南大学。 保密论文在解密后遵守此规定。 论文作者签名： 日期：秒o 年 导师签名： e lm ：彬年角吵日 本人已经认真阅读“c a l l s 高校学位论文全文数据库发布章程”，同意将本人的学位论 文提交“c a l l s 高校学位论文全文数据库”中全文发布，并可按“章程”中规定享受相关 权益。回童迨塞堡銮压澄卮；旦坐生i 旦= 笙i 旦三生苤查。 论文作者签名： 日期：加fd 年。io 3洲0 删889 7，ii0_删y 海南大学硕士学位论文 摘要 摘要 无约束优化方法是最优化方法研究领域中较重要的分支之一在众多的无约 束优化方法中，记忆梯度法，超记忆梯度法是利用前面迭代点的信息来产生下一 个迭代点这类算法具有较强地收敛性和较快地收敛速度，以及较小的计算量和 存储量，因此这类算法具有较大的应用价值 本论文的主要研究成果是：第二章对带线性搜索记忆梯度法进行修正，由于 对目标函数的要求降低，因此扩大了该算法的适用范围；第三章中提出了一个无 约束优化问题的新的超记忆梯度法，由于该算法仅需要求解一个线性方程组系 统，而不必求解带信赖域界的子问题一般来说，这样可减少计算量，从而提高 计算效率；第四章给出了带记忆模型信赖域梯度的算法的具体实现方案，数值实 验结果表明该方案是可行的 关键词：无约束优化记忆梯度法超记忆梯度法全局收敛性数值实验 i 海南大学硕士学位论文a b s t r a c t _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ 。_ _ - - _ _ _ - _ - - _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ - _ _ - _ _ _ _ _ _ _ _ _ _ - - _ _ _ _ _ _ _ - - _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ - _ - _ _ - - _ _ _ _ _ _ - - - _ _ _ - - _ - _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ - _ - - _ _ - _ _ _ _ _ _ _ _ _ _ - - _ _ _ _ _ _ - _ _ _ - _ _ _ _ 。_ 一 a b s t r a c t t h em e t h o df o rs o l v i n gu n c o n s t r a i n e do p t i m i z a t i o ni sa ni m p o r t a n tb r a n c hi n o p t i m i z a t i o nm e t h o d s a m o n gm a n yu n c o n s t r a i n e do p t i m i z a t i o nm e t h o d s ，t h e m e m o r yg r a d i e n tm e t h o da n ds u p e r m e m o r yg r a d i e n tm e t h o dg e n e r a t et h en e x t i t e r a t i o np o i n tb yu s i n gt h ep r e v i o u si t e r a t i v ei n f o r m a t i o n b e c a u s eo fs t r o n g c o n v e r g e n c ea n dl i t t l ec a l c u l a t i o ne f f o r t t h e s ea l g o r i t h m sh a v eaw i d ea p p l i c a t i o n t h em a i nr e s u l t si nt h ed i s s e r t a t i o na r ea c h i e v e da sf o l l o w s ： i nc h a p t e r2 ，am o d i f i c a t i o nt oam e m o r yg r a d i e n tw i t h o u tl i n es e a r c hi sg i v e n ， w h i c he x p a n d st h e e x i s t i n ga l g o r i t h m i nt h e l i t e r a t u r e ；i nc h a p t e r3 。an e w s u p e r - m e m o r yg r a d i e n tm e t h o 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 np r o b l e mi sp r o p o s e d s i n c et h i sa l g o r i t h mo n l ys o l v eas y s t e mo fl i n e a re q u a t i o n si n s t e a do faq u a d r a t i c s u b p r o b l e mw i t hat r u s tr e g i o nb o u n d t h ec o m p u t a t i o n a le f h c i e n c yi si m p r o v e d ；i n c h a p t e r4 ，ai m p l e m e n t a t i o nv e r s i o ni sg i v e nf o rt h et r u s tr e g i o ng r a d i e n tm e t h o d 埘t h m e m o r ym o d e l n u m e r i c a lr e s u l t ss h o wt h a tt h i ss c h e m ei sf e a s i b l e k e y w o r d s ：u f i c o n s t r a i n e d o p t i m i z a t i o nm e m o r yg r a d i e n t m e t h o d s u p e r - m e m o r yg r a d i e n tm e t h o d g l o b a lc o n v e r g e n c en u m e r i c a le x p e r i m e n t s 海南大学硕士学位论文 符号说明 符号说明 本文所用符号，除文中特别说明外，均按如下表示： 1 火”表示玎维欧氏空间，尺+ 表示正实数集； 2 w ( x ) 表示函数的梯度，v 2 f ( x ) 表示函数的h e s s i a n 阵： 3 g 。1 表示矩阵g 的逆矩阵，特指相应的单位矩阵； 4 1 1 i i 表示r ”空间或h i l b e r t 空间中向量或矩阵的范数，一般为2 范数； 5 上标丁表示转置，g r d 表示g 与d 的内积； 6 k ：= 1 表示k 从1 开始以l 为单位增加，即k = 1 ，2 ， 海南大学硕士学位论文目录 目录 第一章绪论1 1 1 无约束优化问题算法的介绍1 第二章关于无线性搜索记忆梯度法的一个修正4 2 1 引言4 2 2 算法及收敛性分析5 2 3 数值检验8 2 4 小结1 0 第三章无约束优化问题新的超记忆梯度算法1 1 3 1 引言1 1 3 2 超记忆梯度法1 2 3 3 全局收敛性1 4 3 4 数值检验1 5 3 5 小结1 8 第四章无约束优化问题带记忆模型的信赖域梯度算法1 9 4 1 引言1 9 4 2 带记忆的信赖域算法及其收敛性2 0 4 ，3 数值检验2 2 4 4 小结2 4 参考文献2 5 附录1 2 8 附录2 3 1 附录3 3 3 在学期间发表的学术论文3 9 后记4 0 i v 海南大学硕士学位论文l 结论 第一章绪论 本章主要介绍无约束优化方法，首先介绍最基本的无约束优化方法，并讨论 其现有的方法；接着阐述它的研究现状及发展状况，最后扼要的介绍了作者研究 的问题和结果 1 1 无约束优化问题算法的介绍 在科学工程实际中有很多问题是无约束优化问题，而且许多约束优化问题都 是可以化成无约束优化问题来处理的因此探讨无约束优化问题的方法有其重要 意义 考虑下列无约束优化问题： r a i n f ( x ) x r ” ( 1 1 ) 其中f ：r ”专月1 是连续可微的函数 求解问题( 1 1 ) 的主要算法是迭代法般采用如下形式： x k + l = x k + a k d k ( 1 2 ) 其中表示通过某种线性搜索策略确定的步长因子，也是下降方向对吼及畋 取不同的选择，就得到不同的迭代方法 求解问题( 1 1 ) 的最基本的方法是最速下降法( 见文献【l 】) ，它常采用如下形 式： x k + i2x k a k g k 其中吒是由某种线性搜索策略确定的步长因子，既垒可( ) 0 最速下降法具 有程序设计简单，计算工作量小，存储量小，对初始点没有特别要求等优点但 是，最速下降方向仅是函数的局部性质，对整体求解过程而言，该方法下降缓慢 且在最优点附近容易产生拉锯现象 。 求解问题( 1 1 ) 的最主要的方法是牛顿法( 见文献【1 】) ，它常采用如下形式： 以+ l = x k 一何。颤 其中q 皇v 2 f ( x 。) ，g 。= a 盯( 以) 牛顿法对于中小型优化问题具有很好的收敛特 海南大学硕士学位论文 i 结论 征，但是每次迭代所需要的存储量大，计算工作量多，不适合大型优化问题求解 类似于牛顿法，拟牛顿法( 见文献 1 】) 是求解问题( 1 1 ) 的最成功的方法，它与牛顿 法的主要区别在于用h e s s i a n 阵的近似反代替h e s s i a n 阵q 由于不需要求目标 函数的h e s s i a n 阵，因此它具有收敛速度快，数值稳定性强的优点，但同样的， 其所需要的存储量大，计算工作量多，不适合大型优化问题求解 求解大型优化问题( 1 1 ) 的方法有共轭梯度法常采用如下形式： 7 j x k + i = x k 一等( 一+ p i d k 1 ) “t u “i 其中q 会v 2 f ( x k ) ，d k = 一g k + 色反一，展为参数共轭梯度法是介于最速下降 法与牛顿法之间的一个方法，具有收敛快，存储量和计算量小的特点但该方法 数值稳定性差且不具备全局收敛性，不适于求解大型病态优化问题 上面提到的各种方法都是线搜索方法，而信赖域方法( 见文献【1 】) 是另一类求 解问题( 1 1 ) 的常用方法信赖域方法思想新颖，算法可靠，具有快速收敛和数值 稳定的优点它不但能很快地解决“良态”问题，而且也能有效地解决“病态” 优化问题因而对信赖域方法的研究是近3 0 年来最优化领域的一个重要的研究 方向，已成为当今构造新的优化方法的主要途径信赖域方法的缺点是每一步迭 代都需求解带信赖域界的子问题，花费代价高，存储量和计算量大，不利于求解 大型优化问题 其它求解问题( 1 1 ) 的方法还有插值法，负曲率方向法，内点算法( 见文献【l 】) 等等这些算法都只是运用了当前迭代信息来寻找最优解，对于科学计算中出现 的非凸，大型和病态的优化问题不易求解因此，我们需要寻求和构造更有效的 算法，这种算法应该具有收敛性和较快的收敛速度，且具有数值稳定性和记忆性 在上个世纪6 0 年代，m i e l e 和c a n t r e l l ( 见文献 2 】) 提出了记忆梯度算法，该 算法的特点是在每一步迭代中不仅利用当前迭代点的信息，还利用到上一迭代点 的信息来产生下一个迭代点该算法不需要计算h e s s i a n 阵，计算公式简单与 上述的优化方法比较，它具有存贮量小和计算量小的优点，而且还有较好的全局 收敛性和较快的收敛速度，适于求解大规模优化问题c a n t r e l l ( 见文献【2 】) 还证明 了对于二次凸目标函数，该算法与f l e t h e r r e e v e s ( 见文献【3 】) 提出的共轭梯度法 等价7 0 年代未，w o l f $ 口v i a z m i n s k y ( 见文献【4 】) 提出了超记忆梯度算法，该算 海南大学硕士学位论文 l 结论 法除了利用当前迭代信息外，还用到前面几步的迭代信息来产生新的迭代点，但 该算法需要多维搜索p e r r y ( 1 9 7 7 ) ，s h a n n o ( 1 9 7 8 ) ，g i l l 和m u r r a y ( 1 9 7 9 ) ， n o c e d a l ( 1 9 8 0 ) ，l i u 和n o c e d a l ( 见文献 5 】 6 】) 还研究一种有限记忆拟n e w t o n 法， 该方法对拟n e w t o n 矩阵进行有限步修正，减少了每步迭代的存贮量和计算量， 适用于大规模优化问题 近几年出现了多种带记忆优化算法，例如三项和多项共轭梯度算法，非单调 搜索算法和曲线搜索算法( 见文献 7 】【8 】【9 】) 等等这些算法在每步迭代时利用当 前点和前面若干点的信息产生下一个迭代点，这有利于求解全局最优解但是由 于算法中缺少对某些参数的记忆功能，限制了算法的强健性 在本文中，我们对上述提到的某些具体的记忆梯度法，超记忆梯度法和带记 忆优化算法进行了相关研究，并对它们做了进一步的改进工作通过数值实验表 明，用记忆梯度算法解决无约束优化问题是非常有效的 本文具体内容安排如下： 第一章绪论部分介绍了求解无约束优化问题的算法的发展过程，扼要地说 明了各种无约束优化算法的具体作法及其优缺点，说明了对其有进一步研究的必 要性 第二章基于对无线搜索记忆梯度算法的研究，对其做了进一步的修正给 出新的算法，并证明了新的算法具有收敛性通过数值实验结果表明，新的算法 更有效 第三章通过对超记忆梯度算法的了解，提出了新的超记忆梯度算法该算 法的主要特点是：每一步迭代只需要解决线性方程组，因此避免了解决带有信赖 域界的二次规划子问题在某些标准假设下，还可证明它是强全局收敛的数值 实验结果显示该方法是有效的 第四章基于信赖域技术，本文提出了处理无约束优化问题的带信赖域的记 忆算法该算法的特点是：用于逼近原问题的目标函数的近似函数含有过去的迭 代信息，也就是算法的行为被更多的全局信息控制通过验证算法有较好的数值 试验，说明该算法具有较快的收敛速度 海南大学硕士学位论文 ! 茎王垂垡丝垫耋望坚塑鏖鲨塑二全堡里 - = 。一。 第二章关于无线性搜索记忆梯度法的一个修正 2 i 引言 考虑下列无约束优化问题： m i n f ( x ) x r ” ( 2 1 ) 其中f ：r ”一r 1 是连续可微的函数 对问题( 2 1 ) ，文献【1 0 】给出了一种求解它的无线性搜索记忆梯度算法其迭 代步骤如下： s t e p l 选择而尺”，万( o ，2 ) ，s 0 ，k ：= 1 ； s t e p 2 计算= w ( 以) ，如果0 反i l s ，则停止； s t e p 3 通过式子吨= 一既+ 磊善m 展，巩一- 计算以- 其中尾满足下列关系： 尾= l l g 。1 1 2 此，g ；吨。+ l l g 。i i i i d t 一。0 o ，k ：= 1 ； s t e p 2 计算瓯= w ( 以) ，如果0 甑0 s s ，则停止： s t e p 3 通过式子以= 一+ 去善屈，以一，计算吨其中尻满足下列关系： 玩= l l g 。f 此，g r d , 一。+ l l g 。l i l l d , 一，0 v 其中集合4 = x r ”：踞缸处存在) g 在x 处的广义j a c o b i a n 阵( c l a r k e 意义 下) 为 0 2f ( x ) = o g ( x ) = c o 刀v 怫厂( x ) ) c 3 2 f ( x ) 也称为c l a r k e 意义下的广义h e s s i a n 阵 定义2 3 称g ( 工) = 夥( x ) 在x 处是半光滑的，若g 在x 处是局部l i p s c h i t z 连 续的，且对任何s r ”，下列极限 l i mv a t v e 0 2 f ( x + t d ) 存在 利用文献【1 1 】中命题2 6 2 及文献【1 2 】中命题4 1 和4 2 立即得到下列结论 引理2 4 若厂( x ) 满足以下三个条件： ( 1 ) v x r ”，c 3 ；f ( x ) ：g 1 0 2 厂( x ) 是非空的紧集； ( 2 ) 点到集影射a ；厂0 ) 和0 2 f ( x ) 是局部有界的和上半连续的； ( 3 ) 若町( x ) 在x 处是半光滑； 则存在v a 2 f ( x ) ，使得 厂( x + d ) ：( ) c ) + v f ( x ) r d + 昙d r i d + 。( 1 1di i z ) 6 海南大学硕士学位论文 2 关于无线性搜索记忆梯度法的一个修正 下面将考虑算法m m g m 的全局收敛性为此，假设： ( h 1 ) f ( x ) l c l ，且在水平集l = x l f ( x ) 厂( 五) ) 内下有界 ( h 2 ) 存在正数m m 0 ，使得： m 1 1 1 2 t 毋吨- - - m l l d , 1 2v 以r ”，k = 1 ，2 ， ( 2 4 ) ( h 3 ) v 圪0 2 f ( x k ) ，有下列关系 憋哗产= 。 亿5 ， 显然，当f 是二阶连续可微的严格凸函数时，假设( h 2 ) 满足；当f 是二 阶连续可微的函数时，0 2 f ( x k ) = v 2 f ( x k ) ，从而b = v 2 厂( 以) 满足假设( h 3 ) 因 此，本章所提出的算法是文献【1 0 】中算法的一般化 引理2 5 假设( h 1 ) - ( h 3 ) 满足，g ( x ) = w ( x ) 半光滑， 屯) 是由算法m m g m 产生的无穷序列，则有 喜静锄 6 ， 证明利用( 2 4 ) ，( 2 5 ) ，半光滑性和引理2 4 ( 3 ) ，可推得 厂( ) 一厂( + 1 ) = 一g 五t ( 坼+ t 一) 一圭( 黾+ l 一黾) r b ( 以+ l 一黾) 一丢( 故+ 。一五) 7 ( 圪一最) ( 吒+ ，一五) + 。( 8 砟+ 。一x , 1 1 2 ) = 一吼g ：矾一圭口：d j 最或一丢口：d l ( 圪一色) 吨+ 。( o 吼巩1 1 2 ) = 耘瞄q 1 丽8 9 r d , 犯咿互1 搿承) 吨 + d ( 敝训2 ) 她2 m 错i ( 2 - a ) a 2 m2 朋2 l j 吨i l 4 m 于是由上面的两式、假设( h 1 ) 和a 。的定义可推知( 2 6 ) 式成立 利用引理2 4 ，我们就得到算法m m g m 具有如下的收敛性结果 定理2 6 假设( h 1 ) ( h 3 ) 满足，瓴) 是由算法m m g m 产生的无穷序列，则 有 ：i ，m 。g = 0 证明类似于文献【1 0 】中定理i 的证明可证，我们在此略去 2 3 数值检验 为了检验算法m m g m 的可行性，我们选取了5 个标准的试验函数程序的 设计语言是用m a t l a b 7 4 编写而成( 其主程序见附录1 ) 其参数选取为： e = 1 0 西，m = 1 0 ，万的选取视不同的函数而取( o ，2 ) 之间的数，屈。的选取视不 同的函数略有不同，当试验函数为问题l 一问题3 ，则有： 尾= l l g 。1 1 4 此，= l l g 。i i l l 巩一i l + g ：以一。+ 2 0 当试验函数为问题4 ，则有 l 风= l l g 。1 1 此，= l l g 圳吨一。i i + g d , 一，+ 1 0 当试验函数为问题5 ，则有 p h = l l g 。l l 。l f ，乞，i ；，u = l l g k l l l l a 一t 1 1 + g n , 一i + 1 5 问题1r o s e n b r o e k 函数 1 3 】： 厂( x ) = l o o ( x 2 一x ；) 2 + ( 1 一五) 2 而= ( - 1 2 ，1 ) 7 ，万= 0 9 9 问题2c u b e 函数【1 3 】： 厂( x ) = 1 0 0 ( x = 一# ) 2 + ( 1 一五) 2x o = ( 1 2 ，1 ) 7 ，万= 0 9 9 问题3m a r a t o s 函数 1 4 】： ( x ) = 一+ 1 0 ( 砰+ x ；一1 ) 2x o = ( - 1 ，o ) 7 ，艿= 0 9 9 问题4w o o d 函数 1 3 】： 一一一一 一 一_ 海南大学硕士学位论文2 关于无线性搜索记忆梯度法的一个修正 厂o ) - - l o o ( x i 2 一屯) 2 + ( 五一1 ) 2 + ( 而一1 ) 2 + 9 0 ( x ；一_ ) 2 而= 卜3 ，一1 ，一3 ，一l 】r + 1 0 1 ( ( x 2 1 ) 2 + ( _ 一1 ) 2 ) + 1 9 8 ( x ：- 1 ) ( x 4 1 ) 6 = 0 6 问题5 广义r o s e n b r o c ki g _ l 数 1 3 - ( x ) = n - i 1 0 0 ( 五+ l _ # ) 2 + ( 1 一薯) 2 x o“8 = 0 6 ( x ) = 1 0 0 ( 五+ l _ # ) 2 + ( 1 一薯) 2 ，= 【0 ，】7 ， 通过自己编写两种算法的程序计算结果如下： 参考文献【1 0 】中的算法： 问题 k f ( x ) x 问题1 4 8 6 【1 ，1 】t o 问题2 1 1 2 4 【1 ，1 】t o 问题3 9 【1 0 1 2 3 ，0 】t 1 0 0 6 2 问题4 1 9 6 8 【1 ，1 , 1 ，1 】t o 问题5 1 4 9 l 【1 ，1 】t 0 算法m m g m ： 问题 七 f ( x ) x 问题l 4 9 5 【1 ，l 】t o 问题2 5 7 0 【1 ，1 】t o 问题3 7 【一1 0 1 2 3 ，0 】t - 1 0 0 6 2 问题4“7 6 【1 ，1 ，1 ，1 】t 0 问题5 1 5 9 l 【1 ，1 】t o 表中k 表示迭代次数，x 表示最优解，f ( x ) 表示最优目标函数值 通过上述数值结果比较说明本章提出的m m g m 算法是可行的，有效的 9 一一 海南大学硕士学位论文2 关于无线性搜索记忆梯度法的一个修正 2 4 小结 由于通过引入b f g s 公式来修正步长因子吼，对目标函数的要求降低，因 此扩大了算法的适用范围相对的，由于算法不需要求解目标函数的h e s s i a n 阵， 这就使算法的速度得到提高且存贮量减少因此对无线搜索记忆梯度算法进行修 正是有必要的 1 0 海南大学硕士学位论文3 无约束优化问题新的超记忆梯度算法 第三章无约束优化问题新的超记忆梯度算法 3 1 前言 考虑无约束优化问题 m i n f ( x ) x r ” ( 3 1 ) 其中f ：r ”一r 1 ，是连续可微的解决问题( 3 1 ) 的主要方法是迭代法如：线搜 索和信赖域方法线搜索方法具有如下形式： x k + i = x k + 吼攻 k = 0 ，1 ，2 ， ( 3 2 ) 其中或是f ( x ) 在点吒的下降方向，吼是步长为了简便起见，分别用以表示 f ( x k ) ，g 。表示夥( 黾) 在线搜索方法中，算法的每一步迭代中仅使用当前的迭代信息产生新的迭代 而忽略以前的迭代信息，这样在算法设计中就浪费了信息共轭梯度法在每一步 迭代中使用前一次迭代信息产生下一次迭代具体的迭代形式如下： 吨- - i i t g 。+ p ，耋主三：)c33，ka 矾 一&一l 当七l ) 不同的屏决定不同的共轭梯度法，展的一些著名的公式是： 醪= 器 酽= 孚 胪= 掣 肛畿t 具体详情见文献【1 6 】，【1 7 ( f l e t c h e r - r e e v e s ) ( p o l a k r i b i e r e p o l y a k ) ( h e s t e n e s s t i e f e l ) ( d a i - y u a n ) 共轭梯度法的好处是可避免存贮和记忆矩阵因此常用它来解决大规模的优 化问题记忆梯度法和超记忆梯度法是共轭梯度法的一般化( 详见文献【1 8 】， 一 海南大学硕士学位论文 3 无约束优化问题新的超记忆梯度算法 【1 9 】) ，因此它们具有与共轭梯度法相同的性质然而比起共轭梯度法，它们的 主要优点在于记忆梯度法和超记忆梯度法可使用前面更多的迭代信息，这有助于 设计带有全局收敛性和快速收敛率的算法详情见文献 2 0 】 当使用传统的非精确线性搜索时，些共轭梯度法没有全局收敛性( 详见文 献【2 1 】) 在某些情况下，许多超记忆梯度法也没有全局收敛性为了保证超记忆 梯度法的全局收敛性，一些学者提出了一些新的非精确线性搜索和曲线搜索法则 ( 详见文献 2 2 1 1 2 3 ) 然而在分析超记忆梯度法的特性时仍有很多困难需要克 服例如：在一般情况下的全局收敛性和局部收敛性是令人感兴趣的热点在设 计算法时，如何使用信赖域方法以保证全局收敛性是另一个挑战最近，时贞军 等专家提出了一类具有全局收敛性的超记忆梯度，该方法是利用信赖域的技术来 保证其全局收敛性( 详见文献 2 4 】) 综上所述，并受到文献【1 8 】，【2 5 1 ，【2 6 】中提出的超记忆梯度法和文献 1 9 d p 提出的o d e 型信赖域方法的启发，我们提出了一个新的解决无约束优化问题的 超记忆梯度法与文献【1 8 】中提出的s h i 方法不同，该方法的优点是：在每步迭 代中不需要解决带有信赖域界的二次规划子问题，只需要求解线性方程组一般 情况下，这种技巧可减少计算量此外该方法不要求f ( x ) 的h e s s i a n 阵的近似是 正定或半正定的 本章余下部分结构如下：第3 2 节中描述算法和分析一些基本性质：第3 3 节中证明在某些主要条件下该方法的全局收敛性：第3 4 节中给出数值试验的结 果；第3 5 节小结本章的意义 3 2 超记忆梯度法 为了定义我们的算法，给出如下假设 假设a ： a 1 ：水平集l ( x o ) = x l f ( x ) f ( x o ) ) 有界 a 2 ：在包含水平集l ( x o ) 的开凸集b 上，f ( x ) 的梯度g ( x ) = 町( x ) 是l i p s c h i t z 连续的，即存在一个常数，使得 8 9 ( x ) 一g ( j ，) 0 l i i x - y l l ，v x ，j ，b ( 3 4 ) 1 2 海南大学硕士学位笙壅 ! 垂丝壅垡垡塑望堑塑塑望坚壁壁簦鲨 _ _ _ _ - _ _ - _ _ - _ _ _ - - _ _ 一一 引理3 1 如果假设a 满足，则 m + 旷似) g ( x ) 7 p + 扣p l l 2 执，x + p b 证明：见文献【l8 】 用m 表示记忆的过去迭代次数，我们的算法如下所示： 算法t r s m g s t e p l 给出x o ，p o ( o ，1 ) ，所2 ，x o r ”，占= 1 0 一，h o = 1 0 0 ，v o = ( g o ) r “1 ，风 取为n 阶单位阵，令七：= 1 ； s t e p 2 如果0 凰0 占，则停止，否则转到s t e p 3 ； s t e p 3 定义o 朋ism i n 七，m ) ，令k = ( ，鼠1 ，g 七一帆) r “机+ 1 ； 如果矩阵仇圪r 。v 。, + ，是正定的，则转到s t e p 4 ，否则，令t 为最小正整数，使得 2 一钆曙色圪+ j 是正定的，令魄= 2 一钆； s t e p 4 求解下列线性方程得儿r 仉+ 1 ( 魄曙b 圪+ ，) y = 一h 。v r g , s t e p 5 计算 成= 掣嵩毋 其中p k = 圪m 且 吼( y ) = 五+ g ：圪y + l y r 曙b 圪j ， s t e p 6 如果成 o ，使得l i 暖0 ，v k 1 4 海南大学硕士学位论文3 无约束优化问题新的超记忆梯度算法 粉反0 岛，v k k ( 3 1 1 ) 由引理3 2 和( 3 5 ) 式，可知： f ( x k ) - f ( x , + 1 ) p o ( q ( o ) 一q i ( 儿) ) 了1 0 0m ty t t 反圪+ 瓦1 慨 = 一譬( 曙r 儿 0 海南大学硕士学位论文3 无约束优化问题新的超记忆梯度算法 对所有的k ，可得 ( 坼) ) 是下降的由假设a 1 知 f ( x k ) 有界，即。够口f ( x k )、 膏毫k 丘 存在且 l i m ，。( 哆既) r 儿2o ( 3 1 2 ) 另一方面，由注4 ，( 3 5 ) 式和( 3 1 1 ) 式，得 i ( 曙反) 7 几l = l ( 曙鼠) r ( 形最圪+ 去) - l ( 曙) l 乓 v k k c + 三 一 h 但该式与( 3 1 2 ) 式矛盾因此1 段设不成立，引理3 5 得证 接下来，证明算法t r s m g 的全局收敛性 定理3 6 在引理3 5 的条件下，有“譬恐。i i g t i i = 0 证明：通过圪的定义，知 畛盯= ( g r g 。) 2 + ( g 二2 + + ( g 二g 。) 2 1 4 ( 3 1 3 ) 由引理3 5 和( 3 1 3 ) 式知，结论成立 3 4 数值试验 为了检验算法t r s m g 的可行性，我们选取了5 个试验函数程序的设计语 言是用m a t l a b 7 4 编写而成( 其主程序见附录2 ) 其参数选取为： 6 = 1 0 6 , h = 1 0 0 ，p = o 1 ，m 2 问题1c u b e 函数 1 3 】： ( x ) = l o o ( x ：一# ) j + ( 1 一五) 2 其计算结果如下： 初始点 k j r kd k 极值点x 极值f ( x ) ( o ，o ) 7 2 68 05 2 【1 ，l 】t o ( 一1 2 ，1 ) 7 2 28 2 4 4 1 ，l 】t 0 1 6 海南大学硕士学位论文3 无约束优化问题新的超记忆梯度算法 问题2p o w e l l 函数 1 3 】： 厂( x ) = ( 五一l o x ：) 2 + 5 ( x 3 一_ ) 2 + ( x ：一2 x 3 ) 4 + 1 0 ( 五一x 4 ) 4 其计算结果如下： 初始点j c o k f kd t 极值点x 极值f ( x ) ( 1 1 1 1 ) 7 3 9 1 1 6 7 8 0 , 0 ，0 ，0 1 t 1 9 0 4 6 e 一1 2 ( 一2 ，- - 2 ，- 2 ，一2 ) 7 3 61 1 27 2 0 , 0 ，0 ，o l t 1 1 3 1 6 e 1 1 问题3w o o d 函数 1 3 】： 厂( x ) = 1 0 0 ( x 2 一而) 2 + ( 五一1 ) 2 + ( 黾一1 ) 2 + 9 0 ( 霉一毛) 2 + l o 1 ( ( x 2 一1 ) 2 + ( 毛一1 ) 2 ) + 1 9 8 ( x 2 1 ) ( 一1 ) 其计算结果如下： 初始点 k f kd t 极值点x 极值f ( x ) ( o ，0 ，0 ，o ) 7 2 61 0 45 2 【l ，1 ，1 ，l 】t 1 0 0 2 1 e 一1 4 ( 一1 , - - 1 ，一1 ，一1 ) 7 2 51 1 25 0 【l ，1 ，1 ，1 1 t 4 3 6 3 6 e 一1 5 问题4r o s e n b r o c k 函数 1 3 1 ： ( x ) = 1 0 0 ( x 2 一砰) 2 + ( 1 一_ ) 2 其计算结果如下： 初始点而 k f kd k 极值点x 。 极值f ( x ) ( o ，o ) 7 2 06 44 0 【1 ，1 】t o ( 一1 ，o ) 7 l87 0 3 6 【1 ，l 】t o 问题5 广义r o s e n b r o c k 函数 1 3 1 ： m ) ：n - i 1 0 0 ( k 。一# ) ：+ ( 1 一) z 刀：1 0 其计算结果如下： 1 7 海南大学硕士学位论文3 无约束优化问题新的超记忆梯度算法 初始点 k f kd k 极值点x 极值f ( x ) ( o ，o ) 7 6 12 3 01 2 2 1 ，川t o ( 一2 ，一2 ) 7 4 91 0 29 8 【1 ，1 】t 0 以上各表中，k 表示迭代次数，以表示函数的计算次数，以表示梯度的计算 次数 3 5 小结 本章中我们提出了一个无约束优化问题的新的超记忆梯度法该方法的主要 特点是：在每次迭代中，只需要求解线性方程组，而不需要求解带有信赖域界的 二次规划子问题另外，当试验步长不被接受时，该方法不需要重新求解线性方 程组，而是产生一个满足h r m i j o 线搜索的迭代点来进行新的迭代同时，在某 些标准假设条件下，可推导出我们提出的新的算法具有强全局收敛性数值试验 表示，在实际计算中，尤其对大规模问题该方法更有效 海南大学硕士学位论文4 无约束优化问题带记忆模型的信赖域梯度算法 第四章无约束优化问题带记忆模型的信赖域梯度算法 4 1 引言 本章考虑下列无约束优化问题： m i n f ( x ) x r ”( 4 1 ) 其中目标函数f ：r ”一r 是连续可微的函数如果使用拟牛顿法解决该问题，则 每步迭代使用厂的泰勒展开式的前三项来( 局部) 代替目标函数，并由此来判定是 否找到了更好的逼近近似解的方向，或者至少找到了下降方向对于这类算法来 说，已有很多学者证明了它们具有全局收敛性和在某些条件下具有二阶收敛速 度，并且有较好的数值试验表现( 详见文献 2 7 】【2 8 【2 9 】) 给定迭代点也，拟牛顿 法的迭代形式是由下式： 反= 何。( 4 2 ) 来确定搜索方向的其中g k = v f ( 故) ，峨是对v f ( x k ) 进行修正的一个正定对称 矩阵，然后进行线搜索，以得到下一个新的迭代点： x k + l = x k + 吨 ( 4 3 ) 它是通过对步长 0 的选择来近似i 亘i 丘f ( x k + 口畋) 的最小值而信赖域算法与 线搜索算法不同的是它在确定方向的同时也确定了步长，且不要求目标函数的 h e s s i a n 阵( 或其近似阵) 是正定的其迭代形式如下： ：p 畋 【x k 如果狐 (44)：不：ro 日外u 1 1 、7 以是由下面的信赖域子问题决定的： m i n 纵炉低) + ( d ) + 圭( d ，风d )( 4 5 ) k 5 色 其中r 0 是戮d = x - x k , 咯= 面a r e d = 搿是实际下降量与预 1 9 海南大学硕士学位论文4 无约束优化问题带记忆模型的信赖域梯度算法 测下降量的比值，h k r “”是一个对称矩阵，它是厂在x k 处的h e s s i a n 阵或其近 似，参数。 0 为信赖域半径 无论是拟牛顿法还是信赖域方法，如果风= v 2 厂( 玫) ，则反的取值是由目标 函数在吒点的梯度值和h e s s i a n 阵决定的( 对于信赖域方法还取决于。的选取) ， 这说明该方法的迭代点的选取是由目标函数f ( x ) 的局部信息决定的同理，如 果风是通过对h e s s i a n 阵进行因式分解修正，而使得娥正定或对称，则吨的选 取仍是依赖于f ( x ) 的局部信息总之，拟牛顿法或信赖域方法的迭代点的选取 与前面的k 次迭代信息积累完全无关，因而具有无记忆性事实上，在迭代过程 中，如果丢弃过去的某些迭代信息，则对算法的收敛性质是有害的特别是当目 标函数是高度非线性时，此时用于逼近原函数的二次泰勒展开式的迭代点变化迅 速，使得算法的迭代过程极不稳定消耗了大量的时间和精力，不利于最优解的 寻找由此我们可以预期，在记忆目标函数过去迭代信息的情况下，将有利于决 定搜索方向以本章旨在这方面做一些探讨 本章余下的结构如下：第4 2 节中介绍了带记忆模型的信赖域梯度算法及该 方法的全局收敛性；第4 3 节给出数值试验的结果；第4 4 小结本章的意义 4 2 带记，i i 乙的信赖域算法及其收敛性 实施信赖域算法的关键是：信赖域子问题( 4 5 ) n 求解，而信赖域半径的调整 策略又直接影响迭代式( 4 4 ) 的实现因此我们考虑下列这类模型： j m i n 衫( 加+ ( g + 如日y d )( 4 6 ) 【i l d l l 0 ，常数0 p 1 ，m ，并计算 f ( x o ) ，g o = v f ( x o ) 和凰= v 2 f ( x o ) ，令k ：= 1 ，p ( 一1 ) = 0 ，几= 0 ： 2 l 海南大学硕士学位论文4 无约束优化问题带记忆模型的信赖域梯度算法 s t e p 2 计算颤= 町( ) ，如果l k0 s ，则停止；否则，令色= o ； s t e p 3 计算，硝，p r e d k ，岛并通过( 4 6 ) 式计算矾，通过( 4 1 1 ) 式计算z 其中p ( k ) = m i n p ( k ) + l ，m ； s t e p 4 如果, o k 1 0 e - 6 ) & ( k o b = b + d 丰d ，( d + s ( ：，k ) ) - b s c ，k ) 丰s c ，k ) ”b ( s c ，k ) 嶂b s c ，k ”； e l s e b = b ： e n d a ( k