（概率论与数理统计专业论文）一族修正拟牛顿算法及其收敛性.pdf

a t h e s i s a 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 二士士二 思0 学位论文作者签名：灵1 麓弓 日期：7 陟 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： - t1 东北大学硕士学位论文 摘要 一族修正拟牛顿算法及其收敛性 摘要 对于非线性优化问题寻找快速有效的算法一直是优化专家们研究的热门方向之一，经 理论证明和实验检验，拟牛顿法已经成为无约束下最优化方法中最有效，理论上也是最 成熟的算法之一在拟牛顿法中，拟牛顿方程起着至关重要的作用最初的拟牛顿方程 仅仅利用了目标函数的一阶导数，而忽略了可利用的目标函数。为了更多的利用信息， 很多人进行了研究。 本文首先对文献【l 卅构造的一类拟牛顿方程进行了改进，保证了它的正定性。该类方 程具有广泛的应用性其次，基于该类拟牛顿方程，建立了相应的b r o y d e n 族拟牛顿法， 并讨论了该算法的全局收敛性和超线性收敛性，并证明在k 充分大的时候仍还是原来的 拟牛顿方程。 关键词：拟牛顿法，拟牛顿方程，b r o y d e n 族拟牛顿法，全局收敛性，超线性收敛性 k l ； am o d i f i e d q u a s i - n e w t o nm e t h o da n di t s c o n v e r g e n c e a b s t r a c t s e e k i n g f a s tt h e o r e t i c a l c o n v e r g e n c e a n de f f e c t i v e a l g o r i t h m s i nu n c o n s t r a i n e d o p t i m i z a t i o nl sav e r yi n t e r e s t e dr e s e a r c ht o p i cf 0 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 de n g i n e e r s q u a s i - n e w t o nm e t h o dh a sb e e np r o v e dt ob eo n eo 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 d t ou n c o n s t r a i n e d o p t i m i z a 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 q u a s i - n e w t o ne q u a t i o n sp l a yak e yr o l ei nq u a s i n e w t o nm e t h o d sf o ro p t i m i z a t i o np r o b l e m s t h e o r i g i n a lq u a s i - n e w t o ne q u a t i o ne m p l o y so n l yt h eg r a d i e n to ft h eo b j e c t i v ef u n c t i o n b u t i g n o r e st h e a v a i l a b l ef u n c t i o nv a l u ei n f o r m a t i o n i n t h i s p a p e r , ac l a s so fm o d i f i e d q u a s i n e w t o ne q u a t i o n sa r ed e r i v e d ，w h i c ha p p l yb o t ht h eg r a d i e n ta n df u n c t i o nv a l u e m o r e o v e rt h eb r o y d e nq u a s i - n e w t o nm e t h o d sb a s e do nt h ec l a s so fm o d i f i e dq u a s i n e w t o n e q u a t i o n s a r e p r o p o s e d f u r t h e ro b s e r v a t i o n sa r e c o m p l e t e d ，s u c h a s h e r e d i t yo f p o s i t i v e - d e f i n i t eu p d a t e s ，g l o b a lc o n v e r g e n c e ，a n ds u p e r l i n e a rc o n v e r g e n c e i nt h j sp a p e r , t h e g l o b a lc o n v e r g e n c ea n a l y s i so fr e s t r i c t e db r o y d e nm e t h o d sb a s e do nt h ec l a s so fm o d i f i e d q u a s i n e w t o ne q u a t i o n si s 西v e n k e yw o r d s ：q u a s i n e w t o ne q u a t i o n ；b r o y d e nq u a s i - n e w t o nm e t h o d s ；g l o b a lc o n v e r g e n c e ； s u p e r l i n e a rc o n v e r g e n c e 、r i 东北大学硕士学位论文 目录 目录 声明i 中文摘要i i a b s t r a c t i i i 第l 章引言l 1 1 背景1 1 2 论文结构2 第2 章预备知识3 2 1 牛顿法的由来3 2 2 拟牛顿法的推导4 2 3 经典拟牛顿法的介绍5 2 3 1 对称秩一结构5 2 3 2 对称秩二结构6 2 3 2 1b r o y d e n 族算法6 2 3 2 2h u a n g 族算法_ _ - - - - - - - 8 2 4 拟牛顿法的搜索方法9 2 4 1 精确线性搜索9 2 4 2 不精确线性搜索一1 0 2 5 拟牛顿法的研究现状1 1 2 5 1 算法的性质与结构_ 1 l 2 5 2 目标函数的近似表达”1 3 第3 章一族新拟牛顿算法及全局收敛性1 5 3 1 一族新拟牛顿方程1 5 3 2 对新拟牛顿算法的改进：1 7 3 - 3 基于改进拟牛顿方程的拟牛顿算法1 7 3 4 新拟牛顿算法的全局收敛性1 8 东北大学硕士学位论文 目录 第4 章新拟牛顿算法的超线性收敛性2 7 第5 章总结和展望3 0 参考文献3 1 致谢3 3 攻读学位期间发表的论文3 4 东北大学硕士学位论文 第1 章引言 1 1 背景 第1 章引言 最优化问题根据有无约束条件可以分为约束和无约束最优化问题。对于约束 最优化问题，目标函数可微的情况算法研究已经十分成熟。对于无约束最优化问 题，首先因为许多实际问题是无约束的，也因为无约束问题的问题相对容易的多， 而解法的思想常常可以推广到一般的约束问题情况。因此从这个意义上讲，研究 无约束优化问题的计算方法就显得尤其重要，人民对它的研究也非常重视，出现 了许多新的计算方法，如共轭梯度法、拟牛顿法、以及信赖域法等，其中拟牛顿 法自上个世纪6 0 年代末开始被广泛的研究。目前已成为应用最广泛的算法之一。 拟牛顿法是牛顿法的一种推广。它在牛顿法的基础上，随着计算机的发展而 产生的一种新的算法。牛顿法的优点是成功利用了h e s s e 矩阵提供的曲率信息， 但另一方面，计算h e s s e 矩阵的工作量大，并且难以计算，甚至不好求出，而以 拟牛顿方程为基础来构造的的拟牛顿算法克服了牛顿法的不足。 自拟牛顿法问世以来，对拟牛顿法性质的研究一直是非线性最优化理论研究 的热点。1 9 5 9 年d a v i d o n 首先提出了变尺度方法即拟牛顿法，他的方法于1 9 6 3 年被f l e t c h e r 和p o w e l l 所简化，这就是我们通常称为得d p f 方法的拟牛顿法。 带非精确拟牛顿法的研究是从1 9 7 6 年p o w e l l 开始，他证明了带w o l f e 搜索的 b f g s 算法的整体收敛性和超线性收敛性。1 9 7 8 年，b y r d ，n o c e d a l ，y u a ny a x i a n g 成功的将p o w e l l 的结果推广到带有限制的b r o y d e n 凸族。1 9 8 9 年，b r y d 和 n o c e d a l 在目标函数一致凸的条件下，证明了带回追搜索的b f g s 算法的整体收 敛性和超线性收敛性。近年来，基于修正拟牛顿方程的拟牛顿算法也吸引了不少 国内的学者。1 9 9 1 年，袁亚湘提出了一种修正的b f g s 算法。1 9 9 5 年，袁亚湘、 r i c h a r d 和h b y r d 又给出了一类非拟牛顿校正算法。1 9 9 7 年，陈兰平、焦宝聪 提出了一类新的拟牛顿算法，并采用w o l f e 线性搜索，在目标函数一致凸的情况 下，证明了非拟牛顿法凸族具有整体收敛性和超线性收敛性，使b r o y d e n 凸族成 为它的特例。 东北大学硕士学位论文第1 章引言 1 2 论文结构 本文工作摘要可概括为以下几点： ( 1 ) 本文对文献【1 6 1 构造的一族拟牛顿方程做了改进，保证了方程的正定性。当 p = 6 。时，已有比较系统的研究，本文着重对p = y 。时做分析。 ( 2 ) 本文给出了基于该族拟牛顿方程的b r o y d e n 族拟牛顿算法，并讨论了算法的 正定性，二次终止性。 ( 3 ) 本文讨论了基于拟牛顿方程的限制b r o y d e n 族拟牛顿算法的全局收敛性。 ( 4 ) 本文还讨论了基于拟牛顿方程的b r o y d e n 族局部超线性收敛性。 本文的结构安排如为：第一章引言及本文工作。第二章给出拟牛顿的由来， 研究现状。第三章推导一族拟牛顿方程并给出相应拟牛顿算法的正定继承性，二 次终止性，全局收敛性证明。第四章给出了该算法的超限性收敛性。 东北大学硕士学位论文第2 章预备知识 2 1 牛顿法的介绍 第2 章预备知识 设( x ) 是定义在丹维欧式空间r ”上的函数，我们把寻找厂( x ) 的无约束极小 点的问题称为一个无约束最优化问题问题表示为： m i n f ( x ) ，x = ( 墨，x 2 ，) 7 r ”( 2 1 ) 其中f ( x ) 称为目标函数 求解无约束最优化问题的方法大都属于迭代法许多迭代法是根据下属思想 建立的，从某一点五出发，先找一个比五取值小的而，然后再找一个取值更小的 五，以此下去，最终找到极小点或者接近极小点这类算法的特点是每进行一步 都要求数值下降，因此称为下降算法当下降方向为负梯度方向时，下降量最大， 因此称为最速下降法它是无约束最优化中最简单的方法作速下降法，具有全局 收敛性，需要的内存量较少，适合解决大型问题，但它的缺点是收敛速度较慢且容 易产生锯齿现象，为改善收敛速度，人们提出了牛顿法 考虑无约束最优化问题( 2 1 ) 其中f ：r ”专r 是二阶连续可微函数。 牛顿法的基本思想是利用目标函数的泰勒展式逼近目标函数，并将其最小化具 体地说，在目标函数厂( x ) 的极小值点x 的近似点砟处将f ( x ) 二阶泰勒展开，即 f ( x ) q k ( x ) = f ( x k ) + 夥( t ) r o 一而) + i 1 ( x - - 坼) r v 2 f ( x k ) o 一) 1 用该二阶泰勒展式去逼近f ( x ) ，并把该二次函数的最小点作为x 的一个新的近 似点+ l ， 令 v g 七( x ) = w ( 诈) + v 2 f ( x k ) ( x - - x k ) = o 即 v 2 f ( x k ) ( x - x k ) = 一耵( 而) 那么 + l = 稚一v 2 厂( 以) 一w ( 砟) 然后在新的近似点，将厂( 工) 二阶泰勒展式展开，求出下一个近似点，用一系列 东北大学硕士学位论文第2 章预备知识 二次函数的极小值点 坼) 去逼近厂( x ) 的极小值点。这就是牛顿公式，尽管牛顿公 式有很好的局部收敛性，它是二阶收敛的。但若初始点离极小值点比较远时，就 不能保证迭代序列收敛，甚至某些迭代点的函数值上升。为了克服这一缺点，改 进迭代公式为 x k + l 。x k a i 以 其中a 。是一维搜索得到的步长因子，巩为搜索方向即 f ( x k + a 畋) 2 喈f ( x k a 以) 这样修改后的算法称为阻尼牛顿法。它能保证每次的迭代都使函数值下降 ( 至少不上升) ，从而使算法具有全局收敛性。尽管相对于原始的牛顿法而言， 阻尼牛顿法前进了一步，但它也仍存在明显不足 2 2 拟牛顿法的推导 为了保留牛顿法优点的同时，克服牛顿法的种种缺点，现在我们需要构造一 种新的算法，它尽可能保留牛顿法的收敛速度快的优点，而避免矩阵求逆的计算。 因此有人想到利用目标函数及一阶矩阵的导数的信息近似海森矩阵，构造出目标 函数的曲率近似的方法，即拟牛顿法。具体推导如下： 把厂( x ) 在以+ 。处泰勒展开，得 f ( x ) f ( x k + 。) + v f ( x , + ，) r o 一+ ) + 昙 一吒+ 。) r v 2 f ( x k + ，) 7 o 一砟+ 。) 于是 v f ( x ) v f ( x + 1 ) + v 2 f ( x k + i ) ( x - x k + 1 ) 在上式中，令蠹办，则 ，卵， 夥( 以) v f ( x i + 1 ) + v 2 f ( x k + 1 ) ( - x k + 1 ) 即 v 2 f ( x k + 1 ) ( + l - x k ) v f ( k + 1 ) 一v f ( x k ) 作为v 2 f ( x k + 。) 的近似，用最+ 。代替v 2 f ( x k + ) ，便得 甄+ l 瓯= 儿 ( 2 2 ) 东北大学硕士学位论文第2 章预备知识 其中5 k = x k + i - x k ，y k = 耵( t + 1 ) 一w ( 以) 我们称( 2 2 ) 式为拟牛顿方程。 关系式( 2 2 ) 中瓯，儿已知时，由于矩阵的元素为行2 个，而牛顿方程只给 出了拧个条件，因而峨+ 。的选择优很大的灵活性。如何寻找适合方程( 2 2 ) 的 矩阵b + 。，有很多方法，我们常用的是采用校正方法，即令b = b 。+ v 反，当反 已知时，给出修正矩阵v b 。，就可得到b ，修正矩阵不同，得到的也不同，由 此形成的迭代算法也不同，我们称这类算法为拟牛顿算法，拟牛顿算法是在不 同尺度下的最速下降法。 2 3 经典拟牛顿法的介绍 无约束最优化问题( 2 1 ) ，其海森矩阵一股是对称的，因此研究具有对称性 的迭代公式有重要意义，现在介绍具有对称传递性的拟牛顿法。 因为取+ 。= 最+ a b k ，与反，瓯，儿有关，其结构由具体算法决定通常可 以分为以下两种最简单的校正形式： 2 3 1 对称秩一结构 s r l 校正公式a b k = o z z t , r a n k ( z z 7 ) = l ， 其中常数仃及列向量z ，与最，瓯，魄有关 秩一校正公式： 因为是衄的秩为一，此时色+ 。的修饰公式可写成 b k + l = 毋+ l z o r ( 2 3 ) 使眈+ 。满足拟牛顿方程( 2 2 ) ，其中p ，d r ”，通过分析推导，当u r 瓯0 时， 可以得到一般秩为一的修正矩阵 = 反+ 紫 ( 2 4 ) d d 。 从( 2 4 ) 容易看出，当最为对称矩阵，最+ 。也为对称矩阵的充要条件是 u = 败一瓯 ( 2 5 ) 东北大学硕士学位论文 第2 章预备知识 此时 钆却辫 眩6 ， k y k b p k ) 0 k ( 2 6 ) 是唯一的秩为一的对称拟牛顿修正，它首先由于d a v i d o n 【1 3 】1 9 5 9 年得到 b r o y d e n 2 l 于1 9 6 7 年又重新推导这一算法在( 2 4 ) 中，不同的| “得到不同的算 法，卢也可以取为瓯或者是儿。秩一修正公式具有遗传对称性功能，且对正定 二次函数有很好的性质因而受到广泛的关注但它不具有遗传正定性因此需要 改进 2 3 2 对称秩二结构( s r 2 ) a b , = o i z z r + d r 2 国r 其中常数d r ，仃：及列向量z ，仍与反，瓯，儿有关下边分别介绍这两种结构 的拟牛顿公式 2 3 2 1b r o y d e n 算法族 为了克服秩一对称拟牛顿算法计算的困难，p o w e l l t 9 i 提出了一种用秩一方法 构造对称拟牛顿法的技巧，利用这种技巧可以导出常见的拟牛顿校正公式。 = 最+ 六队蝴矿+ u ( 以嘞) 】- 皆u u r ( 2 7 ) ( 2 7 ) 是一类重要的具有对称性传递性的拟牛顿修正，它是秩二修正。 对( 2 7 ) ，若取u = 瓯，则得到 廿反+ 去一删n 诹懒) 】_ 皆科( 2 2 8 ) 在( 2 7 ) 式中，适当选择d ，还可以使之具有正定性的传递性。分析正定的条件 可知： 当u = y k 满足条件，此时( 2 7 ) 式变为 母号警+ 裔地地蝴) 耐 ( 2 9 ) 其中q = 去一志， 东北大学硕士学位论文第2 章预备知识 ( 2 9 ) 最早由d a v i d o n ( 1 9 5 9 ) 叫导出，并由f l e t c h e r 与p o w e l l ( 1 9 6 3 ) p 1 所改普， 称为d f p 校正。 当归去( 儿飞反讪其帆= c 箍j 2 也满足条件， 此时( 2 7 ) 式变成为 嘶等警+ 袅 称为b f g s 校正。 因为q 瓯= 0 ，故对( 1 9 ) 式中含q q r 的项前乘以非负常数，便得到一 个依赖于参数妒的一族校正公式硪。，酸，满足拟牛顿条件且保持正定。 耻最一筹警+ 袅堋如碱吐仲，l 】 ( 2 ( 2 1 1 ) 式称为b r o y d e n 族拟牛顿校正公式。当 o ，1 】时，我们称为限制b r o y d e n 族拟牛顿校正公式。可以看出在上式中：令驴= 1 即得d f p 校正公式；令驴= 0 ， 即得b p g s 校正公式。 以上是比较常用的反的校正公式，有时为了减少计算工作量，我们利用峨 ( 以= 何1 ) 的校正公式。此时拟牛顿方程可以写成 h k y 产6 k b r o y d e n 族拟牛顿校正公式的逆矩阵为 戤，= 风+ 羞一掣州椭眺气r 眨 其忙而丽错臻心击一惫 当妒= 1 时，0 = 0 ，从( 2 1 2 ) 式得关于峨的d p f 校正公式 = 巩+ 籍一样 此式称为d p f 的对偶公式，它们具有相同的性质 当西：0 时，0 ：1 ，从( 2 1 2 ) 式得关于矾的b f g s 校正公式 东北大学硕士学位论文第2 章预备知识 = 巩+ 羞一掣慨砧。r 此式称为b f g s 的对偶公式，它也与b f g s 公式具有相同的性质 2 3 2 2 h u a n g 族算法 1 9 7 0 年，h u a n g 例提出了一类比b r o y d e n 族更广泛的算法族，该算法不要求 风对称性，而令搜索方向以由 反= 磁反 ( 2 1 3 ) 所确定，并且不要求校正矩阵满足拟牛顿方程，只要求当算法应用于二次函数时， 产生的搜索方向是共轭的，从而具有二次终止性 按照上述条件，他导出了h u a n g 族校正公式的形式与关系式如下： 玩+ i = 峨+ s k z r + 风y k 0 7 ( 2 1 4 ) 其中向量 p = 口l i 瓯- i - a 2 2 2 儿 ( 2 1 5 ) u = 0 1 2 瓯+ 吃2 日7 儿 ( 2 1 6 ) 且满足关系式 一儿= ( 2 1 7 ) u 1y k = 一l 由于关系式( 2 1 7 ) ，五个参数甜( f ，= 1 ，2 ) 及国中只有三个自由参数，在公式 ( 2 1 4 ) 中，利用条件( 2 1 7 ) 便得 风+ 1 以= 国瓯 ( 2 1 8 ) 当c o = l 时，( 2 1 8 ) 变成拟牛顿方程，而国l 时，h u a n g 族不是拟牛顿算法，通 常称为h u a n g 族变尺度算法h u a n g 族校正公式依赖于三个参数，选取不同的参 数，便得不同的算法事实上，当国= 1 时，若让风为对称矩阵，并要求以+ 。也 对称，即只要q ：= 口2 1 此时h u a n g 族只有一个自由参数，可导出b r o y d e n 族 拟牛不妨设q ，为自有参数，令 玛l ：昙y k r h k y i ，0 0 k k o k q - 2 而魄- 瓯) z 联合( 2 1 5 ) ( 2 1 6 ) ( 2 1 7 ) 式可得 东北大学硕士学位论文 第2 章预备知识 q 2 卸2 i 一而0 2 22 而 将这些参数代入( 2 1 4 ) 式，便得 硼。+ 强一掣坝y 氓t ? 其中气= 立y k r t 多k 一硒h k 瓦y k 这就是关于吼的b r o y d e n 族拟牛顿校正公式所以在h u a n g 族校正公式中： 令= 1 ，0 = 0 ，得口1 2 = a 2 l = 0 ，便得d f p 校正公式： 令= 1 ，臼= 1 得q 22 口2 。一瓦百1，吒z2o ，便得b f g s 校正公式 从上边关系可以看出h u a n g 族算法，当算法中的峨满足对称性要求且算法中的 c o = 1 时，h u a n g 算法族就变成含一个参数的b r o y d e n 族，因此h u a n g 算法族是 b r o y d e n 算法族的拓展 2 4 拟牛顿算法的搜索方向 在用拟牛顿法求解无约束优化问题的迭代过程中，为了保证函数值的“充分 下降 和迭代序列的全局收敛性，我们引入了步长因子口。，其中a 。由线性搜索 策略确定。求的方法精确搜索法，求根法，直接法，插值法和不确定搜索法等 类，各种方法具有各自的特色。在拟牛顿方法中经常使用的是不精确线性搜索法。 2 4 1精确线性搜索方法 精确线性搜索就是要求选择步长a 七满足 八x + 反) = m 。卸i n 厂( 矗+ a 女矾) 以此获得f ( x ) 的最大可能下降，精确线性搜索使得目标函数在迭代过程中下降 量最大，但是精确线性搜索的计算量很大，况且在迭代过程中，在求目标函数的 过程中，往往没有必要把线性搜索搞的很精确，特别是在计算的初始阶段更是如 此，过分的追求线性搜索的精确度会影响整个方法的效率。因此我们在求解无约 束最优化算法的收敛性和收敛速度都基于非精确线性搜索。 东北大学硕士学位论文 第2 章预备知识 2 4 2 不精确线性搜索方法 1 a r m i j o 线性搜索 a r m i j o 线性搜索主要是找一个九使九为集合 p 斗= o ，1 ，p ( o ，1 ) ) 满足如下不 等式 f ( x k + a 吨) 厂( ) + 眺g ( 坼) 7 以p ( o ，去) 2 戈德史丹准则 给亨p ，仃，0 p 盯 _ - 1 1 c t 夥( 以) r 吃 【g ( 矗+ 以) o ，从而失去了正定继承性为了克服这一困难，可以采用以 下策略进行改进 y t 。 y k 。o a , 6 , 0 ，令七= 0 ； ( 2 ) 如果8 & 0 s ，停止；否则，转( 3 ) ； ( 3 ) 构造迭代点序列) ，满足+ 。= + 喀，其中反= 一吼& ，满足精确线 性搜索准则厂( x + 口t d ) = 1 密厂( x + a d h 或起始用口= 1 来试的w o l f e 线性搜索准则，即 五+ l 五+ 脾以 砍，反仃反 东北大学硕士学位论文 第3 章一族新拟牛顿算法及全局收敛性 否则取口 0 ( 4 ) 利用最限制b r o y d e n 类迭代公式产生反即 嘶鬻+ 鞣州如跳似【o l 】 其中魄= 矗一箍，4 = 虹唑铲鼬p 一 j ，。2y i 们赢。南出k 订i y k 龇y k y k 0 4 a , 一志订瓯 1“ ( 5 ) 令k = k + 1 ，转入第二步； 3 4 拟牛顿算法的全局收敛性 下面仅对= 奠时的一族拟牛顿方程的全局给出证明 假定：( a 1 ) 厂( x ) 是定义在集合d 上的二阶连续可微函数：( a 2 ) 厂( ：) 一致凸， g ( 工) 是它的海森矩阵，则存在m m 0 使 m | i z ! 1 2 z r g ( x ) z m i i z l l 2 v x d ，v z r “其中d = xl ( x ) f ( x 。) ，x 为r ”中任意一点 记x 为厂( x ) 在d 上的唯一极小值点，o k 为一与瓯的夹角，有 一反瓯- - i i g 圳瓯l c o s 吼，则对新拟牛顿法有如下引理 引理3 1 对上式定义的矿，有 或r 瓯( 1 + d ) j ，：疋 t 证明我们很容易看出只需证明或= 坛+ 。由t a y l o r 公式有 l + i - - 石+ 柏+ 三硭g ( 备) 瓯 ( 3 其中磊k ，耳+ 。】。将( 3 1 1 ) 代入( 3 1 0 ) 得 - l 厣：r r l 4 j 东北大学硕士学位论文 第3 章一族新拟牛顿算法及全局收敛性 夕：7 瓯= 彰( 儿+ o a k s k ) = 6 y k + o 2 ( f k + i 一五) + ( g “l + ) 7 瓯】 = 硭虬+ 9 炸t 瓯一配g ( 毒。) 瓯】 = ( 1 一r 瓯一噼g ( 考。) 瓯 由于g 的正定性，歹：r 瓯( 1 + 9 ) 订瓯 引理3 2 若f ( x ) 满足上面假设条件， 们有： 吒 为由拟牛顿法产生的序列，那么我 m l l 瓯1 1 2 所t 瓯 m i i 占3 2 ( 3 1 2 ) ( 1 + o ) m - o m l , & 1 1 2 咧t 炸【( 1 + 日) m o m l u 1 1 2 ( 3 1 3 ) m i 【( 1 + 日) m p 聊帆0 证明：( 1 ) 证明( 3 1 2 ) 式 6 ：y k = 6 ：( g k “一9 3 = 轴f g ( 以 = 瓯7 g ( 考) 瓯 + f ) 卉蛾 f 【，x k + 。】，厂( 石) 由厂( x ) 一瓣m l i , u 2 瓯7 g ( 考) 瓯m 0 瓯0 2 即m 0 瓯1 2 坛t 瓯 m i i 瓯1 1 2 ( 2 ) 下面证明( 3 1 3 ) 式， 欺= 硭( y k + p 4 妖) = y k + p 2 ( 石+ l 一五) + ( 既+ l + 鼠) r 瓯】 = y k + 研允瓯一群g ( r l 。) 瓯】 = ( 1 + 日) 联瓯一叫g ( o 。溉 = ( 1 + 日) ( 既+ l 一& ) 7 瓯一群g ( 岛) 瓯 = ( 1 + p ) 群g ( 乞) 瓯一群g ( 白) 瓯 其中乞= 稚+ 卢( + l 一耳) ，卢e ( o ，1 ) ，i = ( 1 ，2 ) 由假设( a i ) 知： 1 9 ( 3 1 4 ) 东北大学硕士学位论文第3 章一族新拟牛顿算法及全局收敛性 ( 1 + 钏酬2 ( 1 + 9 ) 硭g ( 考：) s k _ ( i + o ) ml a , 1 1 2 一o m i i a 。1 1 2 一噼g ( 氧) 瓯一o n6 , 1 1 2 上面两式相加即( 3 1 3 ) 式。 ( 3 ) 下面证明( 3 1 4 ) 式 由4 的定义，有 4 = 虹警产 一( + 。+ 繇) r 瓯一2 繇t 瓯一彰g ( 岛) s k 6 ：y k ：! 鱼l 二鱼2 益二笠g ! 圭! ! 垒 6 ：y k ：篓g ! 鱼! 垒= 壑g ! 圭z ! 鱼 6 ：y k e h 假设( a ) 可知： m l l 6 , 1 1 2 s k r g ( 毒：) 瓯- - - m l l a , 1 1 2 一m i l 6 , 1 1 2 瓯7 g ( 考。) 瓯s m l l 6 , l l ? 所以1 4 n i - - ( m - m ) l l , 多, l i 由假设( a ) 可知0 几| i m 1 6 , i i 根据范数的性质可知： 0 奠0 = 0 欺+ 9 4 几0 0 欺i | + 1 9 4 儿l i | 皖l l 综合上面两不等式可知： m i o j 布鲁丹族拟牛顿校正公式 醴。保持正定。 证明：见定理5 1 3 。 因此我们在0