（应用数学专业论文）非线性优化问题的一类无记忆非拟牛顿算法研究.pdf

摘要 对于非线性优化问题寻找快速有效的算法一直是优化专家们研究的热门方 向之一经理论证明和实践检验，拟牛顿法和共轭梯度法已经成为无约束下最优 化方法中最有效的两类算法前者具有许多优点，比如，迭代中仅需一阶导数不 必计算h e s s i a n 矩阵，当矾正定时，算法产生的方向均为下降方向，并且这类 算法具有二次终止佳，在一定的条件下，文1 1 1 ，2 5 ，2 6 ，2 7 ，2 8 】等给出了除d f p 算法外的b r o y d e n 族算法的超线性收敛性，而且还具有n 步二阶收敛速率拟牛 顿算法的缺点是所需存储量较大，对于大型同题，可黥遇到存储方面的困难共 扼梯度法的基本思想是把共轭性与最速下降方法相结合，具有占用内存少，二次 终止性和良好的数值表现然丽当日标函数为一般的非线性函数时，即使在精确 线搜索下，各共轭梯度法的收敛性也很难保证考虑到以上两种算法的优缺点， 文【3 1 3 给出了无约柬优化的一类无记忆拟牛掇算法较求解无约束优化问题的共 轭梯度法，无记忆拭牛顿法无论在内存还是每次迭代的计算量都没有增加多少。 但其计算表现比共轭梯度法好得多本文基予非拟n e w t o n 方程，结合文f 3 】中 的无记忆拟牛顿法。给出了求解无约束非线性优化问题的一类彖算法数值实验 表明，此类算法具有良好的计算效能，特别适合求解大规模的最优化同题 在第一章我们首先简要的介绍了最优化问膊的提出以及判断最优解常用的 最优性条件，回顾了无约束优化问题常用的几类导数下降类算法 在第二章中，就无记忆拟牛顿族在无约束最优化问题上，采用非单调线搜索 下是否具有全局收敛性进行了研究在目标函数为凸函数的条件下，证明了无记 忆拟牛顿算法是全局收敛的 在第三章中，导出了无记忆非拟n e w t o n 公式，并讨论了目标函数在满足一 致凸的条件下，就采用非精确线搜索是否具有全局收敛性的问题进行了研究文 中还将无记忆非拟n e w t o n 公式和p e r r y - s h a n n o 无记忆拟牛顿公式相结合，提 出了另一种混合无记忆菲拟牛顿校正公式，并证明在目标函致是凸函数的条件 下，此校正在w j l f e 线搜索下具有全局收敛性 关键词：无语 乙非拟牛顿公式，非精确线性搜索，无约束最优化，全局收敛性 a b s t r a c t s e e k i n gf a s tt h e o r e t i c a lc o n v e r g e n c ea n d e f f e c t i v ea l g o r i t h m si nu n c o n s t r a i n e d o p t i m i z a t i o ni sav e r yi n t e r e s t e dr e s e a r c ht o p i cf o rt h eo p t i m i z a t i o ns p e c i a l i s t sa n d e n g i n e e r s n o n - q u a s i - n e w t o nm e t h o d sa n dc o n j u g a t em e t h o dh a v eb e e np r o v e d t ob et w oo ft h em o s te f f i c i e n tm e t h o d sw h e na p p l i e dt ou n c o n s t r a i n e do p t i m i z a r t i o nb yt h ef a v o r a b l en u m e r i c a le x p e r i e n c ea n dt h e o r e t i c s i ta l s os h o wc l e a r s u p e r i t i e st h a ti ti sn o tn e c e s s a r y t oc o m p u t eh e s s i a nm a t r i x ，o n l yn e e dt h eg r a - d i e n t d e c e n td i r e c t i o nc a nb er e s u l t e dw h e nt h eh e s s i a nm a t r i xi sp o s i t i v e ，i t h a sb e e ns h o w nt h a tt h ei t e r a t e sg e n e r a t e db yb r o y d e nc l a s se x c e p tt h ed l f p m e t h o dh a ss u p e r l i n ec o n v e r g e n c e 1 l ，2 6 ，2 7 ，2 8 ，2 9 ，a n dh a sn - s t e pc o n v e r g e n c e r a t e t h ed i s 8 c l v a n t a g e so fq u a s i n e w t o na l g o r i t h mi st h eg r e a tm e m o r y , s of o r l a r g ep r o b l e m s m e m o r yd i f f i c u l t i e sm a y b ee n c o u n t e r e d t h eb 蚵ci d e ao f t h ec o n - j u g a t eg r e d i e n tm e t h o d si st h ec o m b i n a t i o no ft h ec o n j u g a t i o na n dt h em o s tr a p i d d e c l i n em e t h o d i ti n v o l v e sl e s sm e m o r ya n dh a ss e c o n d a r yt e r m i n a t i o na n de f f e c - t i v en u m e r i c a lp e r f o r m a n c e h o w e v e r ，w h e nt h ef u n c t i o ni st h eg e n e r a ln o n l i n e a r f u n c t i o n ，e v e nu n d e rt h ee x a c tl i n es e a r c h ，t h ec o n v e r g e n c eo ft h ec o n j u g a t eg r e - d i e n tm e t h o d sc a nh a r d l yb eg o t c o n s i d e rt h ea d v a n t a g e sa n dd i s a d v a n t a g e so f t h ea b o v et w oa l g o r i t h m s , p a p e r1 3 j 舀mac l a s so fm e m o r y l e s sn o n - q u a s i - n e w t o n a l g o r i t h ma b o u tu n c o n s t r a i n e do p t i m i z a t i o n c o m p a r e dt h ec o n j u g a t eg r e d i e u t m 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 n ，m e m o r y l e s sn o n - q u a s i - n e w t o na l g o r i t h m h a sn o tm u c hi n c r e a s e dw h e t h e ri nm e m o r yo re a c hi t e r a t i v ec a l c u l a t i o n s ，b u ti t s n u m e r i c a lp e r f o r m a n c ei sm u c hb e t t e rt h a nt h e c o n j u g a t eg r a d i e n tm e t h o d s b a s e d o nt h en o n - q u a s i n e w t o ne q u a t i o n ，c o m b i n i n gt h em e m o r y k s sn o n - q u a s i n e w t o n a l g o r i t h mi np a p e r 【3 l w eg i v ean e wc l a s so fa l g o r i t h mf 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 n u m e r i c a le x p e r i m e n t si n d i c a t et h a tt h i sa l g o r i t h mi s v e r ye f f e c t i v e ， p a r t i c u l a r l yf o rs 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 np r o b l e m s i nc h a p t e r1 ，w ef i r s ti n t r o d u c et h ed e v e l o p m e n to fo p t i m i z a t i o na n ds o m e e x t e n s i v eo p t i m a l i t yc o n d i t i o n sw h i c ht od e c i d et h eo p t i m u ms o l u t i o n w er e v i e w s e v e r a le x t e n s i v ed e r i v a t i v ed e s c e n tm e t h o d so fu n c o n s t r a i n e dp r o g r a m m i n g i nc h a p t e r2 ，t h em e m o r y l e s sn o n - q u a s i - n e w t o nm 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 ni si n v e s t i g a t e d n o n - m o n o t o n el i n es e a r c hp r o c e d u r ei si n t r o d u c e d ， w h i c hi sc o m b i n e dw i t ht h em e m o r y l e s sn o n - q u a s i - n e w t o n u n d e rt h ec o n v e x - i t ya s s u m p t i o no no b j e c t i v ef u n c t i o n ，t h eg l o b a lc o n v e r g e n c eo ft h em e m o r y l e s s n e w t o nf a m i l yi sp r o v e d i nc h a p t e r 3 m e m o r y l e s sn o n - q u a s i n e w t o nm e t h o di sp r e 8 e n t e d i ti sc o n - c e r n e dw i t ht h ep r o b l e mo fw h e t h e rt h em e t h o dw i t hi n e x a c th n es e a r c hc o n v e r g e s g l o b n yw h e na p p l i e dt ou 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 w ep r o p o s ean e w m i x e dm e m o r y l e s sn o n - q u a s i - n e w t o nu p d a t ea n d p r o v et h em e t h o d 诵t haw o l f e - w p el i n es e a r c hc o n v e r g e sg l o b l l yi ft h ef u n c t i o ni sc o n v e x k e yw o r d s ：m e m o r y l e s sn o n - q u a s i n e w t o nf o r m u l a ，i n e x a c tl i n es e a r c h ，n n - c o n s t r a i n e do p t i m i z a t i o n ，9 1 0 b a lc o n v e r g e n c e 首都师范大学学位论文原创性声明 本人郑重声明t 所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果除文中巳经注明引用的内容外，本论文不含任何其他个人或 集体已经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明本人完全意识到本声明的法律结果由本人承担 学位论文作者签名：j 聿降韵， 。”j e t 期哆一口年幺月l ；日 首都师范大学学位论文授权使用声明 本人完全了解首都师范大学有关保留、使用学位论文的规定，学校有权保留 学位论文并向国家主管部门或其指定机构迭交论文的电子版和纸质版有权将 学位论文用于非赢利日的的少量复制并允许论文进 学校图书馆被查阅有权将 学位论文的内容编入有关数据库进行检索有权将学位论文的标题和摘要汇编出 版保密的学位论文在解密后适用本规定 靴蝴糙各哼韵奄 日期滞徊加 1 非线性优化问题简介 这一章里，我们简要介绍非线性优化问题的发展现状在第一节中， 简要地阐述最优化问题的提出以及刿断最优解常用的最优性条件；在第二 节中总结了无约束优化问题常用的线搜索和几类导数下降类算法。重点是 拟牛顿算法及文【3 】提出的无记忆拟牛顿算法；在最后一节，介绍了我们提 出新算法的主要思想 1 1 最优化问题的提出及最优性条件 最优化理论与方法是一门应用性很强的年轻学科虽然最优化可以追溯到十 分古老的极值问题。但直到1 9 4 7 年d a n t z i g 提出般线性规划问题的单纯形法 之后，它才成为一门独立的学科随着现代科技的发展和计算机的广泛应用，进 一步推动了最优化理论和算法的研究今天，最优化理论与方法在经济规划、政 府决策、生产管理、交通运输和军事国防等方面都得到了广泛的应用，已经成为 一门十分活跃的学科 一般来说，最优化同题可归结为求解如下的极小值问题。 m 砌i n m ) ( 1 1 - 1 ) 其中，z d 是决策变量，( z ) 为目标函数，d 舒为可行域 根据变量的类氆，最优化问题可分为连续型最优化和离散窭l 最优化( 也称组 合优化) 连续型最优化问题又可分为目标函数和约束函数均为线性时的线性规 划问题，以及目标函数和约束函数中至少有个为非线性时的非线性优化同题 根据可行域d 的类型，非线性优化问题又可分为约束优化和无约束优化问题 一般约束优化闻题通常可描述为： 砌r a i n 。m ) s c 0 ) 0 ，i = 1 ，2 ，一，m ； q ( z ) = 0 ， t = 仇+ 1 ，m + 2 ，- ，珥 本文主要研究无约束最优化问题，即 黪m ) 其中：j p 一冗为非线性连续函数 下面我们给出全局最优解和局部最优解的定义 ( 1 1 2 ) ( 1 1 3 ) ( 1 1 4 ) ( 1 1 5 ) 定义1 1 若矿舻具有性质t 比彤，均有，( 工) f ( x + ) ，则称r 为问 题( 1 1 5 ) 的全局最优解 定义1 2 若r 舻具有性质t 存在矿的某个邻域地) = 伽l z 一矿0 0 为某个正数，使得妇眦( r ) ，均有，( z ) ，( 矿) ，则称矿为问 题( 1 1 5 ) 的个局部最优解 当目标函数( x ) 是凸函数时，局部最优解就是全局最优解但在般情形 下找出全局最优解非常困难，通常在非线性优化中我们认为局部最优解即为所求 的解在实际的算法中，我们通常是找出满足局部最优解的必要条件的点若记 9 0 ) = v ，扛) 表示，( 功的梯度，g ( z ) = v 2 f ( x ) 表示，( z ) 的i - l e i s , n 矩阵 下面我们给出最优解的必要条件： 则 引理1 1 【1 1 1 ( 无约束优化一阶必要条件) 若矿为问题( 1 1 5 ) 的个局部最优解。且在r 的某个邻域内f ( z ) g 1 9 ( 矿) = 0 引理1 2 【1 1 】( 无约束优化二阶必要条件) 2 ( 1 1 6 ) 则 若矿为问题( 1 1 5 ) 的个局部最优解，且在工的某个邻域内f ( x ) g 2 ， 9 ( 矿) = 0 ，g ( 矿) 0 1 2 无约柬优化问题的导数下降类算法 导数下降类算法是求解无约束优化问题 ( 1 1 7 ) m 胛i nm ) ( 1 2 - 1 ) 常用的一类算法，它的基本思想是t 对于当前的迭代点孙，首先确定一个搜索方 向以，使得目标函数f ( x ) 的值沿该方向是下降的，然后确定沿呶方向行进的 步长扎并得到下一个迭代点。 + 1 = 巩+ a k d k 在这里，我们要确定的搜索方向应满足t v f ( x k ) r d k o ( 1 2 2 ) 以使，( z ) 在“点沿如方向下降 为了行文的方便，在介绍线搜索和导数下降类算法之前，约定记号如下 a = f ( x k ) ，吼= 9 ( x k ) = v ，( 巩) ，弧= m + 1 一鲰，s b = z + l 一机= k 呔 下面我们介绍常用的两种线搜索 确定h 的过程就是线搜索( 也称一维搜索) 精确的线搜索就是在d k 方向 上寻求“最优”的行进距离h ，使得 m + a k d k ) 2 赌m + a d k ) ( 1 2 3 ) 非精礴线搜索不要求上式成立，而仅要求找到的扎能使目标函数在某种意义上 达到令人满意的下降常用的非精确线搜索如w j i f e 线搜索和a r m i j o 线搜索， 本文正是采用这两种线搜索现介绍如下t 3 w o l f e 线性搜索条件 口( o ，j 1 ) ，( 1 2 4 ) 卢1 ) 记妒( a ) = i c x k + a d k ) ，则，( 0 ) 妒( o ) + 口( o ) 或p ( a _ ，- ) 妒( q ) ，则令 a j + l = a t ，b + 1 = ，转s t e p s ；否则，转s t e p 3 ； s t e p 3 计算( b ) ；若i l p ，( ) is 一卢( o ) ，则接受，迭代过程结束；否则， 转s t e p 4 ； 4 血 瑚 n 0+ 0嚣融槭 + + s t e p 4 令a j + l = 如；若( b j - a j ) # ( a j - ) 0 ，则令吩+ l = b j ，否则，令b j + l = s t e p 5 令j ：= j + 1 ，转s t e p l ； a r m j j o 线性搜索： a r m i j o 线性搜索主要是找个k ，使k 为集合 h = 0 ，1 ，p ( 0 ，1 ) ) 满 足如下不等式 ，+ k 呶) s m ) + 盯a 翘( z ) 丁氐 盯( 0 ，互1 ) ( 1 2 6 ) 的最大值具体实旖a r m i j o 线性搜索的算法如下 a r m i j o 算法【3 3 】： i n i t i a l ：给定矿z ，并令t = 0 计算k = 扩满足 ，( ) 一i ( 0 ) t r p k t f ( o )( 1 2 7 ) 及 ，( 庐“) 一，( o ) o p k t - 1 ，( o )( 1 其中为任一整数 s t e p l 若 = 0 ，则令= 舻；否则令f ；k l 一1 ； s s e p 2 若厩= f 满足( 1 2 7 ) 及( 1 2 8 ) ，定步长过程结束； 8 t e p 3 若岛= f 满足( 1 2 7 ) 但不满足( 1 2 8 ) ，财令k ：= k 7 1 ，转s t e p 2 ； s t e p 4 若觑= 满足( 1 2 8 ) 但不满足( 1 2 7 ) ，贝j 令f ：= + 1 ，转s t e p 2 ； 下面我们介绍几种常用的导数下降类算法 最速下降法 人们在处理无约束最优化问题时，总希望从某一点出发，选择个目标函数 值下降最快的方向，以利于尽快达到极小点正是基于这样一种愿望，早在1 8 4 7 年法国著名数学家c a u c h y 提出了最速下降法后来，c u r r y 等人作了避一步的 研究该方法取d k = 一9 ( 瓢) ，即每一步都以负梯度方向作为搜索方向因为负 梯度方向是目标函数值下降最快的方向，所以该方法称为最速下降法这种方法 5 每次迭代的运算量不大，并且初始点跏不用很接近最优点矿，但最速下降方向 反映了目标函数的一种局部性质从局部看，最速下降方向是函数值下降最快的 方向，选择这样的方向进行搜索是有利的但从全局看，由于锯齿现象的影响， 即使向着极小点移近不太大的距离，也要经历不小的弯路，因此使收敛速率大为 减慢最速下降法并不是收敛最快的方法，相反，从全局看，它的收敛是比较慢 的因此最速下降法般适用于计算过程的前期迭代或间插步骤 牛顿法 牛顿法是求解无约束优化问题最古老的算法之一，但到目前为止它的改进形 式仍不失为最有效的算法之一由于一个函数在一点搿| 近的性态与二次函数很接 近，所以往往通过建立二次模型来构造有效的算法，最直接而自然的= 次模型。 显然就是它的t a y l o r 展开式中直到二次项的部分，基于这样的二次模型，便构造 出著名的牛顿法取咄= - a ( z k ) - 1 9 ( ) ，其中c ( x ) = v 2 ，( z ) ，方向呶源于牛 顿方程g ( z h ) = - g ( x k ) d k ，称为牛顿方向虽然当迭代序列 孤) 充分接近最优 点矿时，该方法二阶收敛并且对二次凸函数具有二次终止性，但是它只是局部 收敛的，即当初始点。l 充分接近最优点矿时才能保证收敛，由于最优点矿是 待求的，很难检验3 ；1 是否接近矿，因而无法保证 收敛甚至不能保证 ) 的收敛性，因为 ) 不一定是单调下降的为了保证 的下降性和 的 全局收敛性，往往要引进阻尼因子即步长，可以证明其在一定条件下是全局收敛 的另外在牛顿法中h e s s i a n 矩阵的存储量、计算量都很大。迭代的每一步都必 须求解线性方程组，计算量也很大，并且在迭代过程中，c ( x ) 可能出现奇异， 使迭代被迫中止 共轭梯度法 共轭梯度法最初由h e s t e n e s s 和s t i e f e l 于1 9 5 2 年为求解线性方程组而提出 的后来，人们把这种方法用于求解无约束最优化问题，使之成为一种重要的最 优化算法共扼梯度法的基本思想是把共轭性与最速下降方法相结合，利用已 知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小 点当目标函数，( z ) 连续可微时，其迭代格式为 z - + ，= 。* + t 以，也= 二赛 + 凤d 七一。，l 薹 6 其中反为标量，著名的公式有t 酽= 卷( f l e e t 沁卜胁e s ) 解丑p ：丛毕二黑型( p l a k - r i b i 6 r e - p o l y a k ) ， “ | i 玑_ u 等当，( 茁) 为凸二次函数时，适当选择系数凤，使得血与d ，d 2 ，血一l 关于 ，( ) 的h e 龉i a n 矩阵共轭。 h 是由精确线搜索确定的步长共轭梯度法具有 二次终止性然而，当目标函数为一般的非线性函数时，即使在精确线搜索下， 各共轭梯度法的收敛性也很难保证在文献【3 l 】中址b 8 a l i 证明了f l e t c h e r - r e e v e s 方法具有全局收敛性。但是p o w e l l 在【3 2 】中指出，即使使用精确线搜索 p l 拉i h e - p 嘶a k 方法也不会有全局收敛性，但此方法具有良好的数值表现 ( 详见 7 ，1 1 ，3 3 1 ) 1 9 9 7 年l g r i p p o 和s l u c i d i 提出了g r i p p o - l u c i d i 线搜索，并 证明了在此线搜索下p l a k - r i b i r e - p o l y a k 方法的全局收敛性( 参见c 2 3 ，2 4 】) 共 轭梯度法在求解高维的无约束优化问题时是一种有效的算法 拟牛顿法 前面介绍了牛顿法，它的突出特点是收敛速度很快但是，运用牛顿法需要 计算二阶偏导数，而且目标函数的h e s s i a n 矩阵可能非正定为了克服牛顿法的 缺点，人们提出了拟牛顿法拟牛顿算法的基本思想是z 用不包含= 阶导数的矩 阵近似牛顿法中的h e s s i a n 矩阵的逆矩阵由于构造近似矩阵的方法不同，因而 出现不同的拟牛顿法但近似“n 阶对称正定矩阵丑( 。 + 1 ) 必须满足搬牛顿 方程t 日“l y k 28 k( 1 2 9 ) 拟牛顿法的搜索方向为矗= - - h ( x k ) g ( z k ) ，在著名的b r o y d e n 族拟牛顿法中， k 的校正迭代公式为t h k + l = 巩一等警+ 舞州旭小嵋( 1 2 1 0 ) 一撩+ 煮 z m ， 7 其中口1 0 ，1 】，当口分别为0 , 1 时，即为著名的d f p 公式和b f g s 公式 d f p 校正公式： h k + l = 风一等警+ 磊s , s t b f g s 校正公式： h k + 1 风一警+ 蓑懈酬仇 ( 1 2 1 2 ) ( 1 2 1 3 ) 经理论证明和实践检验，拟牛顿法已经成为求解无约束最优化问题中最有 效的类算法它有许多优点，比如，迭代中仅需一阶导数不必计算h e s s i a n 矩 阵，当帆正定时，算法产生的方向均为下降方向，并且这类算法具有二次终止 性，在一定的条件下，文i 1 1 ，2 5 ，2 6 ，2 7 ，2 8 】等给出了除d f p 算法外的b r o y d e n 族算法的超线性收敛性，而且还具有i i 步二阶收敛速率可见，拟牛顿算法集中 了许多算法的长处拟牛顿算法的缺点是所需存储量较大。对于大型问题，可能 遇到存储方面的困难 非拟牛顿算法 在研究拟牛顿法的同时，h u a n g ( 1 9 7 0 ) 提出一类比b r o y d e n 族更广泛的校 正公式，不要求校正矩阵满足拟牛顿方程。只要求当算法应用于凸二次函数时， 产生的搜索方向是共扼的，从丽具有二次终止性裒亚湘1 1 5 提出了一类非拟 牛顿方法之后，陈兰平、焦宝聪 1 8 ，2 9 】又提出了基于校正的非拟牛顿方程。 s ：鼠+ l s k = q k ( t ) ，vt 【0 ，1 】 ( 1 2 1 4 ) 其中 钒0 ) = ” 乳+ 2 0 一t ) 兄 r k 垒f 1 一l k 一点8 k 鼠为g k 的近似矩阵，由此得到具有双参数t ，仇的校正公式 凤“* ) = 鼠一訾+ 瓣q k ( t ) 弧靠+ 帆垓曙 其中 记t t k = 巧1 ，则 k = ( s t 。q + 、嚣y k 一；阻b k s k s k a ， 酬w 沪皿一警+ 蒹柏磊霹 ( 1 2 1 1 5 ) 其中 磊= ( 瓠t n t 弧j ! 弋孬s k i 一磊t t 。k y 女k 玑) 文【1 8 】证明了该算法同样具有二次终止性及矩阵的正定对称传递性，并且由上 述算法产生的点列 。 ) 在一定的条件下具有全局收敛性和超线性收敛性其中 矾的校正公式是个具有双参数t ，机的公式当t = l 时，( 2 4 ) 即为b r o y d e n 族校正公式；当t = o 时，得到伪n e w t o n - b 族校正公式【1 6 】 无记忆拟牛顿算法 2 0 世纪7 0 年代末，p e r r y 【1 1 和s h 旦n n o 【z ，j ，4 1 首先提出了无记| 乙拟牛顿方 法较求解问题( 1 1 1 ) 的共轭梯度法，无记忆拟牛顿法无论在内存还是每次迭 代的计算量都没有增加多少，但其计算表现比共轭梯度法好得多因此在求解高 维无约束最优化同题( 1 1 1 ) 时，经常采用无记忆拟牛顿法关于p e n y - s h b n n o 无记忆拟牛顿方法的收敛性有下列结果，对于一致凸函数，在a r m i j o 线搜索或 w o l f e 线搜索条件下算法收敛 工】；对于凸目标函数，在w o l f e 线搜索条件下，算 法也是收敛的州；但是对于非凸目标函数，目前尚无统一的收敛结果随9 ，1 1 1 1 3 本文的创新点 近年来，许多学者巳在牛顿法，拟牛顿法，共轭梯度法等无约束方法中引入 非单调类搜索技巧，并且许多数值实验已经证明了在某些情况，非单调类算法比 单调类算法更加有效隅y t 圳然而，对采取非单调搜索的无记 乙拟牛顿法的讨 论相对较少本文将讨论对于凸目标函数，在非单调搜索条件下的无记忆拟牛顿 法的收敛性另外，目前的无记忆拟牛顿公式都是基于拟牛顿方程导出的，本文 则基于非拟牛顿方程导出了一种新的混合无记忆非拟牛顿公式，并且与非精确搜 9 索相结合，讨论了该算法的收敛性 在第二章中，就p e r r y - s h a n n o 无记忆拟牛顿公式在无约束最优化问题上， 采用非单调线搜索下是否具有全局收敛性进行了研究在目标函数是凸函数的条 件下，证明了全局收敛性 在第三章中，基于非拟牛顿方程提出了无记忆非拟牛顿公式，并就目标函数 满足一致凸的条件下，采用w o l f e 线搜索是否具有全局收敛性进行了研究另 外，本章还将p e r r y - s h a n n o 无记忆拟牛顿公式与无记忆非拟牛顿公式相结合， 提出了一种新的无记忆公式校正，此校正在w o l f e 线搜索下具有全局收敛性 在第二章和第三章中，我们都做了适量的数值实验，其中的测试函数均出自 文献【3 0 】 1 0 2p e r r y - s h a n n o 无记忆拟牛顿方法在非单调搜索下的收敛性 在这一章中。就p e r r y - s h a n n o 无记忆拟牛顿公式在无约柬最优化问题 上，采用非单调线搜索的情况下是否具有全局收敛性进行了研究在目标 函数是凸函数的条t 牛- f ，证明了p e r r y - s h a n n o 无记忆拟牛顿算法是全局收 敛的 2 1 引言 对于无约束最优化问题 m i n ，( 曲， 卫舻 ( 2 1 1 ) 其中，：舻一r 1 是j p 上的连续可徽函数p e r r y - s h a n n o 无记忆拟牛顿方 法是由p e r r y ( 1 1 和s h a n n o 【2 ，3 t4 】首先提出的这种方法的迭代公式如下： f ； k + ；1 = 一x k + a ：k d k , h k g k - - b k 一1 9 k ，k 2 ，( 2 1 2 ) 嗽= 一 = 一1 ，k ，【2 1 2 ) l 廿1 = 一g l 其中，h 为步长，鳜= v ，( 2 k ) ，血为搜索方向， s k + l 蝶n 鞣一谰i l y k 丽l j 2 s 胁7 ( 2 1 3 ) h k - ! - i 一- - 1 = 蒜，+ 2 8 。k 融s k t 一赤( ：托靠) ( 2 1 4 ) 毂= 。k + 1 一z k = ) 、k 呔，瓠= 9 k + 1 一弧，i 为单位矩阵较求解问题( 2 1 1 ) 的共 轭梯度法，无记忆拟牛顿法无论在内存还是每次迭代的计算萤都没有增加多少， 但其计算表现比共轭梯度法好得多因此在求解高维无约束最优化同题( 2 1 1 ) 时，经常采用无记忆拟牛顿法关于p e r r y - s h a n n o 无记忆拟牛顿方法的收敛性 有下列结果，对于一致凸函数，在a r m i j o 线搜索或w o l f e 线搜索条件下算法收 敛( 上】= 对于凸目标函数，在w o l f e 线搜索条件下，算法也是收敛的削；但是对于 非凸目标函数，目前尚无统一的收敛结果阢h ，儿1 近年来，许多学者已在牛顿 法，拟牛顿法，共轭梯度法等无约束方法中引入非单调类搜索技巧，并且许多数 值实验已经证明了在某些情况，非单调类算法比单调类算法更加有效【苎，9 一0 1 然而，对采取非单调搜索的无记忆拟牛顿法的讨论相对较少本章将讨论对于凸 目标函数，在非单调搜索条件下的无记忆拟牛顿法的收敛性 本文用到非单调搜索形式如下t 选择步长k 满足 f ( x k + 1 ) s 。翌他 一) + c l a k 靠。如， ( 2 1 - 5 ) 9 ( z k + 1 ) 7 d 0 2 9 著d k ( 2 1 6 ) 其中，c 1 ( 0 ，1 ) ，血( 0 ，1 ) ，m o 是个非负整数我们将此类搜索记为n o m - 线搜索一本章不仅证明了无记忆拟牛顿方法在n o m - 线搜索下的全局收敛性。 且做了一定量的数值实验结果表明，算法在n o m - 线搜索下具有良好的数值 表现 2 2 算法 首先给出n o m - 线搜索实现步骤t 1 。给定初始值0 e i 0 ，血1 2 。若0 弧0 岛则停止迭代；否则用n o m - 线搜索确定扎，置z + l ：- z k + a 血 3 。计算 s k = k + l 一童，9 k + l 篇v ，( 霉1 ) ，掣k = 弧+ 1 9 k 若一露d kss ，则 也+ t = 一鲰+ 1 ，后：= k + 1 ， 转2 。；否则，转4 。 4 4 利用( 2 1 2 ) 计算d k + 1 ，a a n k ：= k + l ，转2 。 2 3 主要结果 本章给出假设条件； 假设( h ) ：，伊，是l 上的凸函数，其中水平集l = z 舻f ，( z ) s ，( z 1 ) ) 有界即存在m 0 ，使忙| is m ，v z l 对于n o m - 线搜索，由( 2 1 6 ) 可证明鼠+ l 对称正定且满足拟牛顿方程 类似于b r o y d e n 族校正公式i l l 】，p e r r y - s h a n n o 无记忆拟牛顿公式也可以得到 以下结论： 1 3 5 l 埕2 1 征1 豳芟【h 】r ，稃茌埘l 0 ，便得 糕茎帆扣1 2 ( 2 3 1 ) 珑8 女 、7 迥印定义趸= 片g ( 孤+ t s k ) d t ，( 0 ，1 ) ，则酞= 珊+ i 一鲰= 蕊 ，令讯： 虿轧，其中百召一百由假设( h ) 知，存在l 以 o ，i i c ( z k ) l l 尬，v l 因 鐾。爨：z r g z a 尬船1 , 2 , - 一口 磊2 丽3 s 。1 ，府2 一口 i l 理2 2 若步长k 由算法( a ) 产生。则对第次迭代，存在c a 0 ，使得 矗b 奄( 2 3 2 ) 证明由( 2 1 4 ) 和( 露抓) 2 0 s i 雏0 2 可知 n 赫9 ( h n _ 2 ) 蒜+ ：糕n 糕 ( 2 s 3 ) 由8 k = k 如= 沁( 一m 9 ) 及( 2 1 6 ) 可得到 州) 兰糕， ( 2 3 4 ) 因为矾是正定短阵，于是有 訾攀 0 于是h 0 为行文方便，我们定义 ( 女) = m 铲：f ，p m k = ：p m l , ，l 。： m ( ) 一他州) a ( 勺) ( 2 3 8 ) 证明由h ( k ) 的定义及( 2 2 1 ) ( 2 2 2 ) ( 2 2 3 ) ，还有m l ，我们可以得到 m 删一他) - ( 一号西) ( 2 3 9 ) 1 5 即 k ，( 孤+ 1 ) f ( x m ) ) 一9 1 ( - f f g j ) = f ( x h ( 砷) 一1 q o 以| | ( 2 3 i o ) j = h 似)j = h ( k ) 由( 2 1 6 ) 得 ( c 2 1 ) 靠d ks ( 9 k + 1 9 ) 7 d ks0 9 k + 1 一g k l ll l d k 0 ， “9 k + 1 9 k 0 ( 1 一c 2 ) r k 由s ( t ) 的定义。有 l f h 氏8 s ( ( 1 一c 2 ) r k ) ， k 高s ( ( 1 一沈) r 七) ( 2 3 1 1 ) 将( 2 3 1 1 ) 代入( 2 3 x o ) 得 ，( z i + 1 ) sf ( x h c k ) ) 一l q s ( ( 1 一c 2 ) q ) j = ( k ) 令口( t ) = e l s ( ( 1 一c 2 ) t ) ，于是有 k ，( 茹 ( 砷) 一，( 巩+ 1 ) 盯( o ) 口 j = ( i ) 引理2 4 如果t l ，则对于k2 1 ，所有函数序列 ，( z ) ) 是单调下降的 证明由h ( k ) 的定义得，( ( 一1 ) ) ，( z t ) ，于是 m 删2 。要甄m t - j ) 。g m s a 胁x 。翌，( 钆一) ，m t ) 2 。9 m 8 x f ( x h f k 1 ) ) ，( “) ) = ，( z ( i 1 ) ) ，= 1 ，2 ， 即函数序列 ，( h ( ) ) ) 是单调下降的由于，( z h ( 1 ) ) = ，( 吼) ，则可推导出 ，( 嚣k ) ，0 忙一1 ) ) s ，( z h ( 1 ) ) = ，( 1 ) ，z k l 口 1 6 定理2 5 假