（应用数学专业论文）记忆梯度算法研究.pdf

摘要 摘要 最优化方法是运筹学的一个重要组成部分，在自然科学、社会科学、生产实践、工 程设计和现代化管理中具有广泛的应用。近年来，随着计算机的飞速发展以及实际问题 的需要，大规模优化问题越来越受到重视，很多实际问题都可以归结为最优化问题来解。 最优化问题的一个核心是设计有效的算法。而记忆梯度法正是求解大规模无约束优化问 题的一种有效方法，于是记忆梯度法的理论研究又受到人们的关注。本文对近年来受关 注的非线性记忆梯度法进行了研究，主要研究结果归纳如下： 第一章、主要介绍了优化问题的基本算法以及记忆梯度法的一些基本知识和本文 的主要工作。 第二章、在水平集有界的情况下通过构造一个新的级，提出一种新的无约束优化问 题的记忆梯度算法，并在a r m i j o 线搜索下证明了该算法的全局收敛性，同时对其收敛速度 进行了分析，且证明了该算法在a r m i j o 搜索下至少是r 线性收敛的。数值实验表明了新 算法的有效性。 第三章、本章对文献 1 搜索方向中的参数尾给了一个假设条件，从而确定了它的 一个新的取值范围，保证了搜索方向是目标函数的充分下降方向，由此提出了一类新的 记忆梯度算法。在去掉迭代点列有界和广义a r m i j o 步长搜索下，讨论了算法的全局收敛 性，且给出了结合形如f r ，p r ，h s 共轭梯度法的记忆梯度法的修正形式。数值实验表明， 新算法比a r m i j o 线搜索下的f r 、p r 、h s 共轭梯度法和文献 1 】中的超记忆梯度法更稳定、 更有效。 关键词：共轭梯度法；记忆梯度法；线搜索；线性收敛速度 记忆梯度算法研究 a b s t r a c t a b s t r a c t o p t i m i z a t i o nm e t h o di s a ni m p o r t a n tp a r to fo p e r a t i o n sr e s e a r c h i th a s w i d ea p p l i c a t i o nt om a n yf i e l d s ，s u c ha s ，n a t u r a ls c i e n c e ，s o c i a ls c i e n c e ， p r a c t i c a lp r o d u c t i o n ，e n g i n e e r i n gd e s i g n ，a n dm o d e mm a n a g e m e n te t c w i t h t h e r a p i dd e v e l o p m e n to fc o m p u t e rs c i e n c e a n du r g e n tn e e d sf o rp r a c t i c a l p r o b l e mi nr e c e n ty e a r s ，t h el 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 mh a sd r a w n m o r e a n dm o r ea t t e n t i o n m a n yp r a c t i c a lp r o b l e m sc a nb er e d u c e dt oo p t i m i z a t i o n p r o b l e m s t h ek e yt oi n v e s t i g a t i n go p t i m i z a t i o np r o b l e m si s t od e s i g ne f f i c i e n t a l g o r i t h mf o rs o l v i n g i t a sm a i nw a yo fs o l v i n gl a r g e s c a l eo p t i m i z a t i o n p r o b l e m ，t h em e m o r yg r a d i e n tm e t h o dh a sp a i ds p e c i a la t t e n t i o n t h i sp a p e r m a i n l ys t u d i e st h et h e o r e t i c a lp r o p r i e t i e so fm e m o r yg r a d i e n tm e t h o d t h e m a i n r e s u l t so b t a i n e di nt h i sd i s s e r t a t i o nm a yb es u m m a r i z e da sf o l l o w s ： 1 i nt h ef i r s tc h a p t e r ，n o n l i n e a rm e m o r yg r a d i e n t m e t h o d so ft h e o p t i m i z a t i o np r o b l e mi si n t r o d u c e d ，t h ec o n t e x to f t h i sd i s s e r t a t i o na n dt h em a i n r e s u l t so b t a i n e di nt h 【i sd i s s e r t a t i o n 2 i nt h es e c o n d l yc h a p t e r ，an e wc l a s so fm e m o r yg r a d i e n tm e t h o df o r s 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 np r o b l e mi sd e v e l o p e db yc o n s t r u c t i n g a n e w 】| 3k t h eg l o b a lc o n v e r g e n c e w i t ht h e a r m i j ol i n es e a r c hr u l e i s p r o v e d n u m e r i c a lr e s u l t ss h o w st h a tt h en e w m e t h o di se f f i c i e n t 3 i nt h et h i r d l yc h a p t e r ，a na s s u m p t i o na b o u tp ko ft h el i n es e a r c hi n p a p e r 1 】i sp r o p o s e d ，a n dan e wr a n g ei s i d e n t i f i e d t oe n s u r i n gt h es e a r c h d i r e c t i o ni sf u l l yd e c l i n ei nt h eo b j e c t i v ef u n c t i o n ，an e wc l a s so fm e m o r y g r a d i e n ta l g o r i t h mi sp r o p o s e d o nt h eb a s eo fr e m o v i n gt h e i t e r a t i v ep o i n t s l i s t e di nt h ec o m m u n i t ya n dt h eg e n e r a l i z e da r m i j os t e p s i z es e a r c h ，w ed i s c u s s t h eg l o b a lc o n v e r g e n c eo ft h ea l g o r i t h m ，a n dg i v ea na m e n d m e n to fm e m o r y g r a d i e n ts u c ha st h es h a p eo ff r ，p r ，h sm e t h o d c o m p a r e d w i t ha r m i j ol i n e s e a r c ho ft h ef r ，p r ，h sc o n j u g a t eg r a d i e n tm e t h o da n dt h el i t e r a t u r e 【1 】i n t h e s u p e r m e m o r yg r a d i e n tn u m e r i c a le x p e r i m e n t ss h o w t h a tt h en e w a l g o r i t h m ism o r es t a b l ea n dm o r ee f f e c t i v e 记忆梯度算法研究 k e yw o r d s ：g r a d i e n tm e t h o d ；m e m o r yg r a d i e n tm e t h o d ；l i n es e a r c h ； l i n e a rc o n v e r g e n c er a t e i v 目录 目录 第1 章绪论1 1 1 最优化方法概述1 1 2 几种常用的非精确线搜索2 1 3 几种常用的导数下降类算法4 1 3 1 最速下降法4 1 3 2 牛顿法5 1 3 3 拟牛顿法5 1 3 4 共轭梯度法6 1 3 5 记忆梯度法7 1 4 记忆梯度法和其他几种算法的比较7 1 5 记忆梯度算法的分类及其研究现状7 1 5 1 记忆梯度算法分类7 1 5 2 记忆梯度算法的研究现状8 1 6 本文的主要工作1 4 第2 章一类新的a r m i j o 搜索下的记忆梯度算法15 2 1 引言15 2 2 算法及其性质l5 2 3 全局收敛性1 7 2 4 线性收敛速率18 2 5 数值实验2 l 第3 章结合广义a r m i j o 步长搜索的一类记忆梯度算法2 3 3 1 引言2 3 3 2 算法及其性质2 3 3 3 算法全局收敛性2 5 3 4 数值实验2 7 总结与展望31 参考文献3 3 致谢3 5 硕士期间发表学术论文目录3 7 v 记忆梯度算法研究 v i 第1 章绪论 第1 章绪论 1 1 最优化方法概述 最优化理论与方法是- - f - j 应用性很强的年轻学科。它是研究一些数学上定义的、u j 题 的最优解，即对于给出的实际问题，从众多的方案中选出最优方案。 虽然最优化可以追溯到十分古老的极值问题，但是，它成为一门独立的学科是在上 世纪4 0 年代末，是在1 9 4 7 年d a n t z i g 提出求解一般线性规划问题的单纯形法之后。现 在，解线性规划、非线性规划以及随机规划、多目标规划、非光滑规划、整数规划、几 何规划等各种最优化问题的理论研究发展迅速，许多新方法不断出现，实际应用日益广 泛。在电子计算机的推动下，最优化理论与方法在经济计划、生产管理、工程设计、交 通运输等方面得到了广泛的应用，成为一门十分活跃的学科。 最优化问题的一般形式为： m i n 厂( 工) ， j ，x 肖 ( 1 1 ) 其中x r ”是决策变量，f ( x ) 为目标函数，xc r ”为约束集或可行域。 约束集x = r ”，则最优化问题( 1 1 ) 称为无约束最优化问题： m x e i r n ，f ( x ) 特别地，如果 ( 1 2 ) 否则称为约束最优化问题。 约束最优化问题通常写为： m i n f ( x ) s a t c ，( x ) = 0 ，i e c ，( x ) o ，j 1( 1 3 ) 这罩e 和，分别是等式约束的指标集和不等式约束的指标集，c 。( x ) 是约束函数。当目标 函数和约束函数均为线性函数时，问题称为线性规划。当目标函数和约束函数中至少有 一个是变量x 的非线性函数时，问题称为非线性规划。此外，根据决策变量、目标函数 要求的不同，最优化还分成了整数规划、动态规划、网络规划、非光滑规划、随机规划、 几何规划、多目标规划等若干分支。 最优化方法通常采用迭代法求解，其基本思想是：给定一个初始点x 。r ”，按照 某一迭代规则产生一个点列 ) ，当 x 。) 是有穷点列时，其最后一个点是最优化问题的最 优解；当 ) 是无穷点列时，其极限点是最优化问题的最优解。一个好的算法应具备的 典型特征为：迭代点x 。能稳定地接近局部极小点x 的邻域，然后迅速收敛于x + 。当给 定的某种收敛准则满足时，迭代即终止。一般地，我们要证明迭代点列 坼) 的聚点为一 记忆梯度算法研究 局部极小点。 设以为第k 次迭代点，d 。为第k 次搜索方向，为第k 次步长因子，则第k 次迭代 为： x + l = x + a d t ( 1 4 ) 从这个迭代格式可以看出，不同的步长因子和不同的搜索方向d 。构成了不同的算法。 最优化方法的基本结构如下： 给定初始点x 。 ( 1 ) 确定搜索方向d 。，即按照一定规则，构造在坼点的下降方向作为搜索方向。 ( 2 ) 确定步长因子吼，使目标函数有某种意义的下降。 ( 3 ) 令x k + 。= x 。+ 巩，若x 川满足某种终止条件，则停止迭代，得到近似最优解 以+ 。否则，重复上述步骤。 在以上的迭代格式中，关键的两步是构造搜索方向d 。和确定步长因子。通常要求搜 索方向d 。是下降方向，它是在迭代点x 。处局部逼近原最优化模型的某一子问题的解， 一般采用线性逼近或二次逼近。 迭代步长应使最优化的评价函数伊( x ) 沿射线x 。+ o rd 0 ) 有所下降，即 缈( + d k ) q ，( x k ) 。评价函数用于评价迭代过程的进展，在无约束最优化问题中，一 般评价函数为目标函数。由于和d 。已知，评价函数是关于口的一元函数，故求解吼的 问题称为一维搜索或线性搜索。 一维搜索方法的优劣及收敛的快慢直接影响到最优化算法的收敛速度，最理想的情 况是步长使目标函数f ( x ) 下降最大，即要求步长满足 f ( x k + 吒以) = 1 必f ( x k + c t d k ) ( 1 5 ) 若记缈以) = 妒( + 谢。) ，则求满足( 1 5 ) 的嘶，归结为求一元函数矽似) 的极小化问题 r a i n 够( 口)(16rain) 缈哆j l1 ) 由于这种搜索是以取得最优步长为目的，因此称它为精确线性搜索或精确一维搜 索，所取得的步长口。称为最优步长或最佳步长。因精确线性搜索要求一个单变量函数的 极小值，计算量较大，所以在实际计算中常常用到非精确线性搜索。 1 2 几种常用的非精确线搜索 非精确线搜索不要求取得最优步长，而仅要求找到的口。能使目标函数在某种意义 上达到令人满意的下降。常用的非精确线搜索有： ( 1 ) 标准的w o l f e 线搜索 2 第l 章绪论 f ( x k + 吼以) f ( x k ) + 8 9 k g ：以 g ( x k + q k d k 了a k2 0 9 ：d k 其中万和0 - 是满足0 艿 0 - l 的常数 ( 2 ) 强w o l f e 线搜索 f ( x k + 吼矾) ( 坼) + 鲰g f 巩 i g ( x k + 以) r 以l - 0 - g ：以 当0 - = 0 时，必有g i ，咴= o 因此强w b l f e 线搜索是精确线搜索的一种推广。 ( 3 ) 广义的w o l f e 线搜索 f ( x k + 吼以) f ( x k ) + & r k g ：以 q 或巩g ( x k + 以) 7 或吼反r d 其中0 o i 0 f ( x + a k d ) f ( x t ) + i t l a g 女7d 且 a 7 l 或者口 y 2 a ： 0 其中口：满足：f ( x t + 以：d t ) f ( x ) + 2 a k g k i d ( 7 ) g o l d s t e i n 线搜索【1 4 1 6 l a g t d s ， + a t d t ) 一，( x t 、) 墨6 2 0 k 吱d k 记忆梯度算法研究 ( 8 ) a r m i j o 和g o l d s t e i n 线搜索 f ( x k + o c k dk 、) s f ( x k ) + d a k g ：d k f ( x k + 巩) 厂( 坼) + ( 1 8 ) a k g ：以 ( 9 ) 一种新的线性搜索【7 1 以一( x 。+ 差 d 。) 一差 g ；以+ 三日1 1 9 。| 1 2 ， k 。一卜酬) ( 1 0 ) 一种灵活的线搜索1 0 1 s ( x + 1 ) 厂g t ) + o a g t t d t i g l d k - o r 川g ；d k 2 端 丢峨 i g k l l ( 1 1 ) 基于w o l f e 搜索提出的一种新步长搜索【1 2 1 ( x ) i ( x t + t r a d k i g l 。d 。l 一仃。+ g 。t d 。 - 2 耩 圭。 g i g t l l 1 3几种常用的导数下降类算法 我们把无约束问题的算法大致分成两类：一类是在计算过程中要用到目标函数的导 数，这类算法我们称为下降类算法；另一类只用到目标函数值，不必计算导数，称为直 接法。在这里主要介绍下降类算法。其基本思想是：对于已有的迭代点托，首先确定一 个搜索方向以，使得目标函数f ( x ) 沿该方向是下降的，然后确定沿d 。方向行进的步长 ，从而得到下一个迭代点以卅= 坼+ 以 在这里，我们要确定的搜索方向d 。应满足：夥( ) 7 吃 0 ，使( x ) 在坼点沿d 。方 向下降。常用的下降类算法有： 1 3 1 最速下降法 取d 。= 一g ( x 。) ，即每一步都以负梯度方向作为搜索方向。因负梯度方向是目标函 数值下降最快的方向，所以该方法称为最速下降法。最速下降法具有计算工作量少、存 4 第1 章绪论 等优点，并且具有全局收敛性等优点。但遗憾的是，在 点j l 止_ f ( x ) 沿最速下降方向下降的最快，这仅是算法的局部性质。对整个求最优解的 过程并不一定是最快的。从全局来看，当目标函数的等值线接近于一个圆球时，最速下 降法下降较快。而当目标函数的等值线是一个扁长的椭球时，最速下降法开始n 步下降 较快，后来就出现锯齿现象，即使向着极小点移近不太大的距离，也要经历不少的弯路， 因此下降速度十分缓慢。 1 3 2 牛顿法 牛顿法的基本思想是在目标函数f ( x ) 的极小点x 。的近似点x 七附近将f ( x ) 二阶泰 勒展开，用展开的二次函数去逼近f ( x ) 将这个二次函数的极小点作为x 的一个新的近 似点x 七+ 1 用一系列二次函数的极小点 吒+ 1 ) 去逼近厂( x ) 的极小点x 由牛顿方程 g ( x t ) = 一o ( x i ) 以 解得牛顿方向 d k = 一g ( x ) g ( x ) ，x “l = x + d 其中g ( x ) = v 2 f ( x ) 对于正定的二次函数，牛顿法经过一次迭代即可达到问题的最优 解。对于非二次函数，由于目标函数在极小点x 的附近近似于二次函数，因此当初始 点靠近最优解时，牛顿法的收敛速度较快，但若初始点远离最优解时，g 。不一定 正定，即牛顿方向有可能不是下降方向，所以就不能保证其收敛性。此外，在确定搜索 方向时，需要计算目标函数f ( x ) 的二阶导数，迭代的每一步都必须求解线性方程组，因 此计算量非常大。 1 3 3 拟牛顿法 拟牛顿法的基本思想是用不包含二阶导数的矩阵近似牛顿法中的h e s s i a n 矩阵的逆 矩阵。由于构造近似矩阵的方法不同，因而出现了不同的拟牛顿法。 目前常用的拟牛顿算法主要有： ”即 等黔警 ”即筹一筹癸 却筹一鬻 记忆梯度算法研究 即蓑一第舞佃一，辄。以劬。声 牟。，ky k 一惫 ( 巩的b r o y d e n 族校j 下) = 反+ 鬻一鬻桃其中州班瓯) 轰一羔 ( 色的b r o y d e n 族校j 下) 这罩和够的关系为 ( ( p 一1 一囝u ) 其中 = 紫 。 ( 瓯。儿) 2 当矽= 0 ，得d f p 校正； 当矽= 1 ，得b f g s 校正； 当矽= 历，得s r l 校正； 由此可看出b r o y d e n 族校正包含了s r l 校正、d f p 校正和b f g s 校j 下，它们可统一称为 b r o y d e n 类算法。 1 3 4 共轭梯度法 共轭梯度法是求解无约束优化问题的一类非常有效的方法，其基本思想是把共轭性 与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜 索，求出目标函数的极小点。当目标函数f ( x ) 连续可微时，其迭代格式为： 以+ 。= 以+ 以， 以= 二耋，+ 展矾书：三：) 其中口。是搜索步长，以表示搜索方向，g 。= v f ( 以) 当目标函数( x ) 为二次凸函数时， 适当选择参数孱，使得巩与d 。，d ：，d 关于( x ) 的h e s s e n 矩阵共轭。若步长由 精确线搜索确定，则共轭梯度法具有二次终止性。但是当目标函数为一般的非线性函数 时，即使在精确线搜索下，某些共轭梯度法的收敛性也很难保证。 参数孱的不同选取 就形成许多不同的共轭梯度法，常用的共轭梯度法有f r 、p i 冲、c d 、h s 、d y 、l s 方 法等。 6 第1 章绪论 1 3 5 记忆梯度法 记忆梯度法也是求解无约束优化问题的有效方法之一，它实际上是共轭梯度法的一 种推广，其基本思想是所设计的算法在每步迭代时，除利用当前的迭代信息外，还用到 前面若干点的迭代信息，这种算法无需计算二阶导数，计算公式简单，能有效避免存贮 和计算矩阵，又因增加了参数选择的自由度，由此可以构造稳定的快速收敛算法【l - 3 】， 且具有较好的全局收敛性，对于求解大型病态问题是一种有效的算法途径。记忆梯度法 的缺点是记忆步数越多，一般迭代公式越复杂，在实际问题中，记忆二步到三步比较合 适。 1 4 记忆梯度法和其他几种算法的比较 在所有的需要计算梯度的无约束优化方法中，最速下降法是最简单的，但大量的数值 实验表明，它的收敛速度十分缓慢，不是可行有效的优化方法。拟牛顿方法收敛速度很快， 被广泛认为是非线性规划的最有效方法，但拟牛顿方法需要存储矩阵以及通过求解线性 方程组来计算搜索方向，这对于求解大规模的优化问题有时会产生数值困难。共轭梯度法 在计算简单性和所需存储量方面与最速下降法类似，而收敛速度却与拟牛顿法相媲美。但 是由于共轭梯度法是针对正定二次函数设计的，虽然在精确搜索下具有二次终止性，但对 一般非线性目标函数，有些共轭梯度法不具有全局收敛性，而记忆梯度法能更充分地利用 前面迭代点的信息，增加了参数选择的自由度，由此可以构造快速稳定的收敛算法，对于 求解大型病态问题是一种有效的算法途径因此，记忆梯度法一直为广大工程和科技人 员所重视。 1 5 记忆梯度算法的分类及其研究现状 1 5 1 记忆梯度算法分类 根据记忆梯度法的搜索方向所用前面的迭代信息大致可分为两类：一类是搜索方向 d 。由当前迭代点的负梯度方向一g 。和前一迭代点的搜索方向以一。线性组合而成 5 - s ；形 如： 驴溉m 吐。七芝。； 另一类搜索方向d 。由当日订迭代点的负梯度方向一g 。和前一迭代点的负梯度方向 一g 川线性组合而成，形如： d 。= 二黧g 。+ 孱g 。一。 七亍! 。 7 记忆梯度算法研究 我们知道，求解无约束优化问题( 1 2 ) 的下降算法一般是产生一序列扛。) 使对任意 k ， f ( x 川) s ( x 。) 但是，序列杪k ) 并不一定收敛到问题( 1 2 ) 的最优值，即使厂k ) 是凸函数且! 受0 耵g t ) i i = o 显然我们可以考虑序列k 是否产生聚点大致划分为两类， 一类是在水平集有界的条件下，分析记忆梯度算法的收敛性质，这类问题最常见i 1 1 4 】； 另一类是在去掉迭代点列k ) 有界的条件下，分析记忆梯度算法的收敛性质，孙清滢等 对此问题作了深入的讨论 1 5 1 6 】。 1 5 2 记忆梯度算法的研究现状 自从记忆梯度法产生以来，人们对它的收敛性研究一直有着浓厚的兴趣：尝试步长 选取的各种条件，参数也有多种变形。由于记忆梯度法对一般函数来说，其收敛性是有 条件的，因此，不少学者采用了这样或那样的条件对其收敛性加以研究，产生了一些好 的结果。比较经典的有如下一些。 1 5 2 1 在水平集有界的条件下 ( 1 ) 搜索方向d k 由当前迭代点的负梯度方向一g 。和前一迭代点的搜索方向d 线性 组合： 时贞军在文献【4 】中，提出一种新的无约束优化超记忆梯度算法： f g t k 历 + - 2 坼+ 吼以，以2 1 一成瓯一芝鼠讲。y + 。 七聊 其中y + 。= 砟讲：一椎讲。( f = 2 ，m ) ，当k 所时，屏讲。【o ，s 。ij ( f = l ，朋) ， 且 c 反，尾一。+ 。，= a r g m i n l i g 。一g 。一。+ 屏g 。+ 善f l k - i + l y k - i + l0 2 这里 s ：= 0 ，s ：= 0 p 1 ，0 0 是一个正整数。 f = 2 ，m ； 埘 以讲，= 1 ， i = i 假设( x ) 在水平集厶= 仁r ”i 厂g ) 厂k ) ) 上有下界，梯度g ( x ) 在包含水平集厶 的丌凸集b 上一致连续，采用a r m i j o 搜索，并在较弱的条件下证明了算法的全局收敛 性。 汤京永、董丽等在文献【5 】中提出一类新的求解无约束优化问题的记忆梯度法： x k + i = x k - j r - a k d k , 以= - g k + 屏九尼k = 2 1 第l 章绪论 其中反= 列， o 7 7 l ，o q 虿1 仃2 1 假设厂( x ) 在水平集厶= 备r ”i 厂g ) 厂k ) ) 上有下界，梯度g ( x ) 在包含水平集。 的开凸集b 上一致连续。采用w o l f e 搜索，在较弱的条件下证明了算法的全局收敛性。 时贞军在文献 6 】中提出一种新的无约束优化超记忆梯度算法： l g 庀 m 卅。坼+ 吼巩，以2 1 一以鼠一芝屏讲吨讲 七所 其中 0 p 1 ，o a o 是一个正整数，当七聊时，展讲。t o , s ；jo ：1 ，所) 且 ”“扣删n l i g , - g k - i + 1 3 k g k + 瑚p k - i + l d k - i + l1 1 2 这里 托牡砉+ 撬 f = 2 ，m ； 埘 履机= 1 j - 1 假设厂( x ) 在水平集厶= 扛r ”i 厂g ) f ( x 。) 上有下界，梯度g ( x ) 在包含水平集厶 的开凸集b 上一致连续。采用a r m i j o 非精确线性搜索步长，在较弱条件下证明了算法 的全局收敛性。 张租华、时贞军、王长钰在文献【7 中提出一种新的无约束优化记忆梯度算法： 魂+ l = + _ a k 以h ) ，这里绋为满足下式的口s k ，p ，& p 2 ， 中的最大者 以一( 砟+ 专以 一专 以+ 互1 训1 1 2 ，以= 二占2 口k + 口味。乏i ： 其中 1k ：0 i赫t：()：，：；，() 0 在新的线搜索条件下分 析了算法的全局收敛性。 9 记忆梯度算法研究 x k + i - - - - x k4 - a k d k d 。= 二嚣一屏k 。+ 级d 。一。】羔茎 其中 o p 1 ，o 丢，仃缸，1 ) ， 这里成【0 ，s 。】，而s 。= 【p p o 9 2 。o z i l g 。o z k + = i g l ：，以一。i 】后2 假设厂( x ) 在水平集厶= & r ”i 厂b ) k ) 上有下界，梯度g ( x ) 在包含水平集厶 的开凸集b 上l i p s c h i t z 连续。分析了w o l f e 搜索下该算法的全局收敛性和线性收敛速 讳 ，又。 汤京永时贞军在文献【2 】中对记忆梯度算法： 确强蝇以，以= 置+ 肫c l k 1 1 c 芝2 i g 女+ 女 一 2 其中 厩= 粒( 。，丢) 一( 。击) 假设厂( x ) 在水平集厶= & r ”i g ) k ) 上有下界，f ( x ) z ( e l 。上连续可微， 梯度g ( x ) 在包含水平集厶的开凸集b 上l i p s c h i t z 连续。在强w o l f e 搜索下证明了其全 局收敛性。当目标函数为一致凸函数时，对其线性收敛速度进行了分析。 汤京永，时贞军在文献 3 】中对记忆梯度算法： x t + ，= x t + d t 以， d 。= 二嚣一孱k 。+ 孱以一。】 ：茎 其中 屏= p o 0 2 i l g 。1 1 2 一仃g o ，哝一。 后2 ，o p 盯 吾 假设厂( x ) 在水平集。= & r ”is x ) - f ( x 。) ) 上有下界，厂( x ) 在三。上连续可微， 梯度g ( x ) 在包含水平集厶的开凸集b 上l i p s c h i t z 连续。同样在强w o l f e 搜索下证明了 其全局收敛性。当目标函数为一致凸函数时，对其线性收敛速度进行了分析。 范林等人在文献【1 2 】中对记忆梯度法： x t = x t + 口t d t ，以= 二嚣一屏k 。+ 屏d 。一l 】 羔茎 1p 2 k = 1 一 这里反【0 ，s t 】，而瓯21 二6 9 。i l z i i g 。i i z + i g ：。d 。一； 】七2 ，o p l ，。 仃 0 为参数，吼是夥k ) 和s 的夹角。 ( b ) 误差项w k 满足 以b + p l l v f ( x 。) ， 其中p ，q 0 为常数，九满足 乙b = ， 后1u ， i 叽 丛 一成 以 戗 “一 帕 尾一 一 庀 驭 。心阿 屏 2卜犹 献 艾 仿 7 式由 记忆梯度算法研究 躲 竺帝措 璺()=coso。+lzx-coso,盟iis。_,i x k + - = x k + c r k d k 唯咖鼢k = l 成麓( - o o 笺, 黪 这罩幺表示甑和跟- 之问的央角，而( 1 - c o s 咖同i i g , i i ，b k ( 1 + c o s 咖斟， o “ ， o 2 丢 - m 以，喀= 二嚣一孱k + 孱繇二一m 其中成 等， ，而瓯= 【硎p 繇21 1 2 i 陬o z ：i 三一，j 】尼2 ，o p 1 1 2 第l 章绪论 一 1 其中 x k + i = x k + a k d k , c = 二兰i = l 石k 一，+ ；。一j + ，k 七 m 刀吁 靴聊时“2 告。器呻，卅 屏= 1 一麒小。，0 p 0 是一个正整数。 t = 2 假设厂( x ) 在水平集厶= 冬r ”i 厂g ) 厂g 。) 上有下界，梯度g ( x ) 在包含水平集三。 的开凸集b 上一致连续。采用一种更为灵活的线搜索，并在一般条件下得到算法的全局 收敛性，提高了超记忆算法设计的灵活性。 公锦风在文献 1 1 】中提出t - - 利f 记忆梯度法： x 。卅= x 。+ 以。以，以= 二嚣一成k 。+ 屈g 二。i 1 后2 其中 孱【o ，s 。】， 而s t = p 9 2 。l z i g 。z k + = l i ：o i l l l ii i g l g 。一。i 】后2 而 s 女2 g 。1 2 g 。2 +l g 。一。】后2 0 p 1 ，0 i 1 ，口0 ，1 ) 假设厂( x ) 在水平集三。= 仁r ”i 厂g ) 厂g 。) 上有下界，梯度g ( x ) 在包含水平集三。 的丌凸集b 上l i p s c h i t z 连续。分析了该算法在w o l f e 搜索下的全局收敛性和线性收敛 速度。 杨峰，陈忠在文献【1 4 】中对记忆梯度算法： x t + t = 砟+ 口t 以， 以= 二嚣一鼠k 。+ 反g 。一。】 乏茎 其中成 ， ，= 【尸p 8 9 2 。l l z i l g 。o z k + = l g l ；以一。j 】后2 ，。 p ，0 ( 1 + ) i 成i g 。i i | i 以一。0 其中a 0 是一个常数。 于是成可取值为： 屏一础 ， 其中力。( ) = 雨甄1 面网i i g , i i 式中皖为瓯和d 的夹角。 ，e ( ) = 耳驴i 丽网i g , i i 在去掉迭代点列有界且分别在广义a r m i j o 步长搜索、a r m i j o 搜索下讨论了算法的 全局收敛性。 1 6 本文的主要工作 本文所做的主要工作如下： 1 在文献 1 】的理论基础上，通过对文献【2 】中的搜索方向及其孱的结构研究，试探 性地构造了一个新的成，并分析了该算法的收敛性及其收敛速度，证明了该算法至少是 r 线性收敛的，通过与a r m i j o 线性搜索下f r 、p i 冲和h s 共轭梯度法的比较发现此记 忆梯度法具有明显的优越性。 2 根据文献 1 5 - 1 6 对参数屏的假设，本文对文献 1 的搜索方向中的参数反做了相 应的假设，从而确定了反的一个新的取值范围，使其在此范围内取值均能得到目标函数 的充分下降方向，从而建立了求解问题( 1 2 ) 的一个新的记忆梯度算法，并在较弱的条件下 ( 去掉迭代点列k ) 有界和广义a r m i j o 线搜索) 证明了算法的全局收敛性。 1 4 芝j 屏 + g g 一 一 d ，1叫 以 丛 七 吼 一成 = 成一 坼1 屏 中 其 笙!章一类新的a r m i j o 搜索下的记忆梯度算法 一类新的a r m o o 搜索下的记忆梯度算法 2 1引言 考虑无约束优化问题 m i n f ( x ) x r ” 其啊：r ”专r 为连续可微函数。在本文中，简记五= f ( x 。) ，g 。= v f ( x 。) ，厂= 厂g + ) 文献 1 】中提出的算法是一个算法类，搜索方向以中的参数孱的选取范围很广，其 中： 唯慷星协隧卺 文献【2 】提出的算法中搜索方向矾及其参数展取值为： 以镌讹一，笼，反= 粒 本章在文献 1 】的理论基础上，通过对文献 2 】的搜索方向以及其参数屈的结构研究， 试探性地构造了一个新的展，从而提出一种新的记忆梯度算法，并分析了在a r m i j o 线 性搜索下该算法具有全局收敛性和至少r