（应用数学专业论文）一类新拟牛顿算法及其收敛性(1).pdf

摘要 拟牛顿法是求解非线性无约束优化问题的最有效、理论上也是最成熟的算法之 一在拟牛顿法中，拟牛顿方程起着至关重要的作用最初的拟牛顿方程仅仅利用了 目标函数的一阶导数，而忽略了可利用的耳标函数值。为了利用更多的可利用信息， 很多人对拟牛顿方程进行了研究，取得了较好的进展。 本文首先构造了一类拟牛顿方程，该类方程包含了张建中等n ”的新拟牛顿方程， 肖运海等嘲的拟牛顿方程，以及最初的拟牛顿方程，具有广泛的应用性。其次，基 于该类拟牛顿方程，建立了相应的b r o y d e n 族拟牛顿法，并讨论了该算法的正定继承 性，二次终止性，该算法包含了肖运海等的b f g s 算法。再次，本文还讨论了基于 该类拟牛顿方程的限制b r o y d e n 族拟牛顿法的全局收敛性。肖运海等嘲算法作为此 限制b r o y d e n 族拟牛顿法的特例，其全局收敛性从b f g s 方法推广到整个限制b r o y d e n 族。最后，本文证明了基于该类拟牛顿方程的b f g s ，p s b ，d f p 拟牛顿法的收敛阶。此 收敛阶分析拓宽了新拟牛顿方程“”和肖运海等拟牛顿方程的超线性收敛性结果。 关键词：拟牛顿方程，b r o y d e n 族拟牛顿法，全局收敛性，局部超线性收敛性 a b s t r a c t q u a s i - n e w t o nm e t h o d sa 聪t h em o s te f l i c i e n to 1 e 8f o ru n c o n s t r a i n e do p t i m i z a a o m 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 n p r o b l e m s t h eo 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 f t h eo b j e c t i v e f u n c t i o n , b u ti g n o r e st h ea 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 ht h i sp a p e r , ac l a s so f m o d i f i e dq 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 n v a l u e + t i f f sc l a s so f m o d i f i e dq u a s i - n e w t o ne q u a t i o n si n c l u d en e wq u a s i - n e w t o ne q u a t i o n p r o p o s e db yc h e n g x i a nx u r 嘲，q u a s i - n e w t o ne q u a t i o np r o p o s e db yy u n h a ix i a o 2 6 1a n d t h eo r i g i n a lq u a s i - n e w t o ne q u a t i o n m o r e o v e r , t h e8 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 d o nt h ec l a s so fm o d i f i e dq u a s i - n e w t o ne q u a t i o n sa 托p r o p o s e d f t a + t h e ro b s e r v a t i o n sa r c c o m p l e t e d , 飘曲a sq u a d r a t i ct e r m i n a t i o n , h e r e d i t yo fp 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 l c o n v e r g e n c e ，a n di c o a ls u p e r l i n e a rc o n v e r g e n c e i nt h i sp a p e r , t h eg l o b a lc o n v e r g e n c e a 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 d0 1 1t 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 si sg i v e n a tl a s t , t h i sp a p e rc o m p l e t e st h el o c a ls u p e r l i n e a tc o n v e r g e n c eo f b f g s ， d f p , p s bm e t h o d sb a s e do nt h ec r a s so fq u a s i - n e w t o ne q u a t i o n s t h ea n a l y s i so f c o n v e r g e n c ee x t e n d st h ee x i s t e dc o n v e r g e n c e 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 , g i o b a j f a 3 n v e r g e l 3 c e , l o c a ls u p e r l i n e a rc o n v e r g e n c e 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其饱人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 研究生签名：鱼笠泐6 年6 月印日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的全部或部分内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的全部或部分内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名：鱼坚如年j 月刁日 南京理工大学硕士论文一类新拟牛顿算法及其收敛性 第一章绪论 i i 拟牛顿法的早期背景 拟牛顿法是在牛顿法的基础上改进而来。考虑无约束最优化问题 m i n 厂( x ) ，工r ” ( 1 1 ) 其中f ：r ”寸r 是二阶连续可微函数。牛顿法的基本思想是在目标函数，( 功的极小 点，的近似点毛将，( 力二阶泰勒展开，即 厂( z ) * 吼( 力= 厂( 矗) + w 。( ) 7 0 一毛) + 去 一矗) v 2 f ( x , x x - x , ) 二 用该二阶泰勒展式去逼近八x ) ，并把该二次函数的最小值点作为，的一个新的近似 点鼍+ l ， 令 v q , ( z ) = 可瓴) + v 2 厂瓴一黾) = o 即 审2 ( 黾) ( x 一) = - 盯( 孔) 那么 = 以- v 2 ( 黾) - 1 v ( 黾) 然后在新的近似点。将厂( x ) 二阶泰勒展开，求出下一个近似点，用一系列二次函数 的极小点 黾 去逼近，( 功的极小点r 。从推导过程可以看出，拟牛顿法存在以下四 点不足： ( 1 ) 若求新的近似点而+ l ，需要计算目标函数的海森阵及其逆，计算量很大。 ( 2 ) 海森阵的逆矩阵可能不存在，使得牛顿法无法进行。 ( 3 ) 初始点的选取只能在工的适当领域内，否则算法产生的点列可能不收敛。 ( 4 ) 只有当海森阵正定，求得的搜索方向才是下降方向，序列 才能越来越接 近极小点r ，算法才有意义。 为了在保留牛顿法优点的同时，克服牛顿法的种种缺点，需要构造一种新算法 牛顿法是二次逼近算法，因此有人想到能否以某种正定矩阵色来代替海森阵q 并使 迭代有近似于牛顿法的特点与性质。为了要找寻与q 有菜种近似的b k ，我们需要来 考虑q 的各种相关关系。为此目的，我们将厂( 功在五+ 。处作寨勒展开，得 f ( x ) * 厂( 吆。) + 可y ( 而。) r o 一黾。) + 去o x k + 。) 7 v 2 厂( 黾。) r o 一黾。) 于是 l 曼堕墨坚盔兰堡主丝苎 二鲞堑垫塑兰鲨墨茎堡墼丝 v 厂( z ) m v ( ) + v 2 ，( 黾+ 。) ( 工一) 在上式中，令x f x 。，则 v 厂( 鼍) * 百歹( 吆。) + v 2 厂( 黾。) ( 黾一黾+ ，) 即 v 2 f ( x k + ，) ( 而。- x , ) * v ( 。) 一夥“) 作为v 2 ，( 五。) 的近似，用召0 ，替代v 2 ( ) ，便得 疋= 儿 ( 1 2 ) 其中五- - x t + l 一五，欺= 可( 毛“) 一v 厂( 气) 我们称( 1 2 ) 式为拟牛顿方程。 关系式( 1 2 ) 中4 ，儿已知时，由于矩阵最。的元素为矿个，而拟牛顿方程只给出 疗个条件，因而岛+ 。的选择有很大的灵活性。如何寻找适合方程( 1 2 ) 的矩阵占0 ，有 很多方法，我们常用的是采用校正方法，即令占厶= 最+ a 吼，当盈已知时，给出修正 矩阵b 就可得到且。，修正矩阵不同，i 0 的忍。不同，由此形成的迭代算法也 不同，我们统称这类算法为拟牛顿算法。 1 2 经典拟牛顿法介绍 无约束最优化问题( 1 1 ) ，其海森矩阵一般是对称的，因此研究具有对称性的迭 代公式有重要意义，现在介绍具有对称性传递性的拟牛顿法。 1 2 1 秩一修正法 因为2 盈+ 蝇，最简单的校正形式是曲的秩为一，此时瓦。的修正公式可 写成 b b n = b t + l f p 使b + 。满足拟牛顿方程( 1 2 ) ，其中，v 彤，通过分析推导， 到一般的秩一修正矩阵 耻b + 警 ( 1 3 ) 当i ，r 盈0 时，可以得 ( 1 4 ) i x ( 1 4 ) 容易看出，当鼠为对称矩阵，占厶也为对称矩阵的充要条件是 。 v 2 儿一皿4 ( 1 5 ) 此时 。 2 南赢理工大学硕士论文 一类新拟牛顿算法及其收敛性 b k , i = b k + 紫 m 回 i 以一版吱j 吼 ( 1 6 ) 是唯一的秩一对称拟牛顿修正，它首先由d a v i d o n m j 于1 9 5 9 年得到，b r o y d e n m 于1 9 6 7 年又重新导出这一算式。在( i 4 ) 中，不同的v 得到不同的算法，1 ，也可以取 为喀或者是儿。然而，秩一修正公式不能保证 盈 的正定性。另外，分母可能取零， 于是修正公式不再有意义，因此，需要改进。但是，它有一个突出的优点，就是往往 比别的修正公式逼近v 2 厂( 而) 的程度高，利用这个特点，近年来把它用在其他类型的 算法框架中，如信赖域算法，取得了很好的效果。 1 2 2b r o y d e n 算法族 为克服秩一对称拟牛顿算法数值计算的困难，p o w e l l 嘲提出一种用秩一方法构造 对称拟牛顿法的技巧，利用这种技巧可以导出很多常见的拟牛顿校正公式。 设对称矩阵盈五”，开始按照秩一修正的方式构造矩阵q ，一般q 不对称，根 据c 1 构造对称矩阵c 2 ，一般c ：不满足拟牛顿方程，再从龟出发，按照秩一修正的方式 构造矩阵6 ，然后将c ，对称化，如此继续下去，得到一个有极限的矩阵序列，把极限 记为忍。，则 耻反+ 壶陟矧几啾嘞) ，卜学引，7 ) ( 1 7 ) 是一类重要的具有对称性传递性的拟牛顿修正，它是秩二修正 若对于( 1 7 ) 中的v = 嗄，则得到 却去弦圳n 地蝴) r 卜学料( 1 8 ) 称为p s b 嘲校正( p o w e l l 导出的对称b r o y d e n 校正公式) 。 在( 1 7 ) 式中，适当选择v ，还可以使之具有正定性的传递性，这是重要的一类 算法，使得搜索方向总是下降方向。分析艮。正定的条件可知： 当v = 儿满足条件，此时( 1 7 ) 式变成为 唧鼍簪+ 裔+ ( 如医) 耐 ( 1 9 ) 其中q 2 蠢一志，( 1 9 ) 最早由d a v i d o n ( 1 9 5 9 ) 嘲导出，并由f 1 e t c h e r 与 p o 哥e l l ( 1 9 6 3 ) 嘲所改善，现称为d f p 校正 南京理工大学硕士论文 一类新拟牛顿算法及其收敛性 当归去( 欺+ 仉忍跏其中仇= ( 杂 i 也满足条件，此啪7 ) 式变成 为 哪并一鼍掣 m - 现称为b f g s 校正。 因为q 7 五= o ，故对( 1 9 ) 式中含嚷的项前乘以非负常数妒，便得到一个依 赖于参数妒的一族校正公式最+ ，耳“满足拟牛顿条件且保持正定性。 b k + 1 # - - 盈一筹掣+ 鲁+ ( 如引k a o k t , 纠o 1 1 ( 1 1 1 ) ( 1 11 ) 式称为布鲁丹族拟牛顿校正公式当妒【o ，1 ) 时，我们称为限制布鲁丹族拟牛 顿校正公式。可以看出在上式中；令= 1 即得d f p 校正公式；令= 0 ，即得b f g s 校 正公式 以上是比较常用的盈的校正公式，有时为了减少计算工作量，我们利用- , 的校 正公式，其中皿是尾的逆矩阵。此时拟牛顿方程可以写成 皿+ 。段= 最 布鲁丹族拟牛顿校正公式的逆矩阵为 n k + l = - 致+ 籍一铧+ 疗( 旭雎) w ( 1 1 2 ) = 丽若等丽 气= 者一摄 当妒= 1 时，0 = 0 ，从( 1 1 2 ) 式得关于风的d f p 校正公式 = 皿+ 籍一掣 当= o 时，0 = i ，从( 1 1 2 ) 式得关于凰的b f g s 校正公式 ”峨+ 籍一样+ ( 帆欺) 梯 4 南京理工大学硕士论文一樊新j 茧【牛顿算法及其收敛性 通过比较两种形式的d f p 公式和b f g s 公式，可以看出在关于皿的d f p 公式中， 将晟换为以，几与暖互换，便得关于趣的b f g s 公式。在关于尾的b f g s 公式中， 作同样的变换，便得关于皿的d f p 公式，这种现象称为对偶现象，即d f p 公式与b f g s 公式互为对偶。 1 2 - 3h u a n g 族算法 1 9 7 0 年，h u a n g 删提出了一类比b r o y d e n 族更广的算法族，该算法族中包含三个自 由参数，将b r o y d e n 族算法要求的条件放松，他的条件是： ( i ) 矩阵吼不要求对称性； ( 2 ) 不要求校正矩阵满足拟牛顿方程，而是满足广义拟牛顿方程 h l n y k 2 6 t 。t r ( 3 ) 要求当算法应用于二次凸函数 g ( x ) = 去，缸+ 6 0 + c 二 时，产生的方向关于g 互相共轭，从而具有二次有限终止性。 根据上述要求，他导出了一类新的含三参数的h u a n g 算法族，当算法中的巩满 足对称性要求且参数中的国= 1 时，h u a n g 算法族就变成含一个参数的b r o y d e n 族， 因此b r o y d e n 算法族是h u a n g 算法族的子集。 记校正矩阵为风，迭代方向由 畋= 一皿1 既( 1 1 3 ) 给出。 按照上述条件，他导出了h u a n g 族校正公式的形式及关系式如下： 珥+ l ；皿+ 暖7 + l - l , y , v 7( 1 1 4 ) 其中向量 = q i 反+ 巩1 y k( 1 1 5 ) y = q 2 喀+ 皿7 儿 且满足关系式 矿y t = ，1 咒= 一1 由于关系式( 1 1 7 ) ，五个参数q 。，q ：，啦。，a n ，m 中只有三个自由参数， 中，利用条件( 1 1 7 ) ，便得 ( 1 1 6 ) ( 1 1 7 ) 在公式( 1 1 4 ) 5 南京理工大学硬士论文 一类新拟牛顿算法及其收敛性 巩。儿= 碱 ( 1 1 8 ) 当彩= 1 时，( 1 1 8 ) 变成拟牛顿方程，而缈1 时，h u a n g 族不是拟牛顿算法，通常称 为h u a n g 族变尺度算法。h u a n g 族校正公式依赖于三个参数，选取不同的参数，便得 不同的算法。事实上，当国= 1 ，若让皿是对称矩阵，只要= a 2 lr 则也+ l 也对称， 这时h u a n g 族只有一个参数。例如，岛。取为自由参数，若令 岛，；士+ 趣口 2 而+ 南矛f 联合( 1 1 5 ) ( 1 1 6 ) ( 1 1 7 ) 式可得 占日一1 2 一而2 y t t h k y k 将这些参数代入( 1 1 4 ) 式，便得 = 叫籍一样+ 口( 旭以) w 其中k = 去一盘 这就是关于峨的布鲁丹族拟牛顿校正公式。所以在h u a n g 族校正公式中： 令曲= 1 ，占= o ，得q 2 = 啦i = 0 ，便得d f p 校正公式； 令口= 1 ，口= l 得q 2 = 啦l = 一瓦百1 ，= 。，便得b f g s 校正公式 1 3 迭代步长的选取 在用拟牛顿法求解无约束优化问题的迭代过程中，为了保证函数值的“充分 下降”和迭代序列的全局收敛性，我们引入了步长因子吼，其中吼由线性搜索 策略确定。求吼的方法有精确线性搜索法，直接搜索法，插值法和不精确线性搜 索法等几类，各类方法具有各自的特色。在拟牛顿方法中经常使用的是精确线性 搜索和不精确线性搜索法。 一精确线性搜索 精确线性搜索就是要求选择步长满足 f + 吼以) ) = l 密厂( 而+ 口或) 以便获得厂厶) 最大可能的下降。精确线性搜索使得目标函数在迭代过程中下降 6 南京理工大学硕士论文一类新拟牛顿算法及其收敛性 量最大，但是精确线性搜索的计算量较大，况且在迭代过程中，在求目标函数的 最优解的时候，往往没有必要把线性搜索搞得十分精确，特别在计算的初始阶段 更是如此。过分的追求线性搜索的精确度会影响整个方法的效率。因此我们在求 解无约束优化问题时，放松对吒的要求，只要求目标函数在迭代的每一步都有充 分的下降即可，通常采取不精确线性搜索求解迭代步长瓯。然而，精确线性搜索 具有理论价值，许多无约束最优化算法的收敛性和收敛速度都基于精确线性搜 索 二不精确线性搜索主要有如下方法 1 戈德史丹准则： 给定，盯，0 0 ，令m = o ，l ，2 ，检验不等式 二 厂( 黾) 一厂瓴+ ”，壤) ，矿”r v f ( x i ) 7 反 是否成立，记使得上面不等式成立的第一个r a 为，则令 a t = 眇y 因为五是下降方向，当坍充分大时，上面不等式总是成立，因此上述的总是存在。 1 4 拟牛顿法的研究现状 自拟牛顿法问世以后的几十年来，对拟牛顿法的研究一直是非线性最优化算法理 7 南京理工大学硕士论文一类新拟牛顿算法及其收敛性 论研究的热点。1 9 5 9 年o a v i d o n 啮j 首先提出了变尺度方法即拟牛顿算法，他的方法 于1 9 6 3 年被f l e t c h e r 与p o w e l l 啕3 所简化，就得到了我们通常称为d f p 方法的 拟牛顿法。拟牛顿法也引起了广泛的关注，根据拟牛顿方程或校正矩阵的不同，结合 不同的搜索原则，先后出现了众多的拟牛顿算法，其中最著名的是b r o y d e n 族和h u a n g 族拟牛顿法。最初的拟牛顿方程为 2 k i 盈= 以，4 = 毛“- x k ，儿= v ( 赡+ 1 ) 一w 。( 鼍) 而 儿= v ，( 矗“) 一可( 毛) 。if v 2 ，( 磁+ 0 4 ) a o l 4 ( 1 1 9 ) 比较( 1 1 9 ) 式和最初的拟牛顿方程可以看出，& + 。应该逼近海森阵在黾和毪+ 1 的均值， 若让置。逼近海森阵q 。，对予非二次函数，毋。暖和儿之间存在误差，因此拟牛顿 方程和恳的校正公式有待进一步提高。而且从最初的拟牛顿方程和b r o y d e n 和h u a n g 族修正公式可知，最初的拟牛顿方程和修正公式仅仅涉及至l j g k + l ，g k ，而忽略了目标 函数的函数值。为了利用更多的可利用信息，例如以， + ，g 一。 一，等等，国内外大量 研究人员致力于拟牛顿法的研究，拟牛顿算法的拓广有了很多研究成果。一类是从算 法的性质与结构入手进行推广，一类从目标函数的近似表示形式入手，得到了众多的 拟牛顿方法。 一考察算法性质与结构 i 吴一桂嘲具有n + 1 个参数的拟牛顿算法 在h u a n g 算法族的基础上，吴方一桂湘云根据h u a n g 族的公式结构与性质进行 了推广，得到了含有一+ 1 个参数的新算法族。h u a n g 算法族的公式可写成 玩。= 巩+ 瓯h 。瓯+ q ：可以】r + 耳耽 瓯+ 巩7 儿， ( 1 2 0 ) 满足关系式 【q l 瓯+ q 2 皿7 ) i 】7 以= 国 【口2 1 4 + 风7 y k r y t = - 1 ( 1 2 1 ) 五个参数与国中有三个自由参数。( 1 2 0 ) 与( 1 2 1 ) 也可以写成 月：。=风一兰；：；粼t t+q一aa。+92hkrykryk 而h u a n g 算法族可以由下面三个条件所刻划： ( 玩败，皖) i 以。一以，( 以7 坛，坑) l ( 皿。- a , ) l 皿+ 。雎= q 反 ( 1 2 2 ) ( 1 2 2 ) 式中前两式的定义是：若( 口，6 ) 表示由列向量口，6 组成的矩阵，为与( 口，6 ) 有 相同行数的矩阵，( 口，b ) l 彳表示存在列向量c 与d ，使得 a = 记+ b 茁 8 南京理工大学硕士论文一类瓤拟牛顿算法及其收敛性 吴一桂嘲发现，在证明h u a n g 族算法所具有的一切性质中，( 1 2 2 ) 中的第一个条 件可以省去，因此由( i 2 2 ) 中后两式确定了以h u a n g 族为其予族的新算法族，并且保 持了h u a n g 族具有的所有性质。由于( l2 2 ) 式的第二式与风+ l = 皿+ a k y k 7 珥+ b k a , 等价，嚷，6 k 为两个列向量。以此式带入( 1 2 2 ) 式的第三个条件，可知新的算法族含 有n + 1 个独立参数，其中的一个参数为吃 2 1 9 8 3 年，s p e d i c a t o 对h u a n g 族拟牛顿算法中的国取一特殊值 = 了兰z l ：1 ，得到一族正定秩一迭代。 2 l 石一丘l + 五7 反+ 1l 3 修正拟牛顿算法 ( 1 ) 1 9 7 1 年，b i g g s 嘲给出了拟牛顿算法的一种修正形式，修正公式为 小掣掣+ 气壤 皿2 s ， 其中为参数，f i = i 寺l 厂( 毛) 一，( t ) + 五7 “】一2 v | ，k 这个修正公式与b f g s 公式比较只差参数t ，当气= 1 时，( i 2 3 ) 即为b f g s 公式 ( 2 ) 1 9 9 1 年，袁亚湘咖根据厂g ) 的二次近似与某些插值条件，得到与( 1 2 3 ) 式 类似的修正公式，他的公式中t 的取值为 2 表旷( 毛) 一胞_ ) + 壤7 鼬】 ( 3 ) 1 9 9 3 年，a n j o s “”把袁亚湘的成果推广到一参数布鲁丹族拟牛顿法。 ( 4 ) 焦宝聪基于目标函数局部二次模型近似，1 9 9 4 年亦提出了一个类似公式， 其中的取值为 = 等 石一如- y , r a , + 0 , 0 e 【o 1 】 ( 5 ) 对于( 1 ) ( 2 ) ( 4 ) 这三种情况，王海滨于2 0 0 4 年推广到1 9 9 9 年提出的新拟牛 顿方程，仅仅把其中的儿换成新拟牛顿方程中的n ( 6 ) l a l e e 和n o c e d a l m 在1 9 9 1 提出了一类自调节b f g s 方法，并在非精确搜索 的假设下证明了该方法对于一致凸函数的收敛性，而且局部收敛速度是超线性的。 二考察目标函数的近似表达 1 d a v i d o n 于1 9 8 0 年利用当前迭代点的函数值和梯度值提出了一个三次近似 模型。 量堕墼兰坠堡苎 = 鲞堑丝生堡兰鲨墨苎坚竺堡 2 j 九f o r d m l 于1 9 9 4 年提出了m 步拟牛顿法，它涉及到目标函数在最近脚步 的梯度值，通过沿着最近脚步产生的迭代点构成的曲线，利用拉格朗日插值多项式对 g ( 进行多项式近似得到。加步拟牛顿法的拟牛顿方程为 e + i = q 其中 = 艺( ) 五一，嘞；窆( ) g ( 靠。h 。) z k = k - r e + l , 触。0 1 ，2 ，( f ) 2 县若 3 伪n e w t o n - b 族公式删 记厂( x ) 在黾处的海森阵为q ，则厂o ) 在黾处的二次近似展开式为 ( 苫) * 厂( ) + 7 五十去4 7 6 ；喀 取j = ，并令，k ) = 五，墨；- a 一& 7 盘，则有 五7 q 盈* 2 墨 ( 1 2 4 ) 称为弱拟牛顿方程。 与得到拟牛顿秩二修正公式的推导类似，最后得到校正公式为 耻皿一等+ 裔埘懈盈州 其中国= 老一播 公式( 1 2 5 ) 称为伪n e w t o n - b 族校正公式，它是非拟牛顿算法族。 4 张建中，邓乃杨“”利用厂( 以) 八x m ) ，g i ，g 。的值对g ( 功进行二次插值，于 1 9 9 9 年给出了一新的拟牛顿方程 其中 5 剐t + 蠢 ，= 3 ( g t + l + g i ) 7 盈- 6 仉+ i 一五) 通过验证，新拟牛顿方程的右边比一般的拟牛顿方程的右边更好的接近目标函数在点 以+ 。的二阶导数g + l 与瓯的乘积，邓乃扬啪1 对一致凸函数的限制布鲁丹族算法的全局 收敛性进行了分析，证明了p s b ，d f p 算法的超线性收敛性悯 1 0 南京理工大学硕士论文 一类新拟牛顿算法及其收敛性 5 张建中，徐成贤“”于2 0 0 1 年提出了一族新拟牛顿方程， 蟊2 以+ 彘 ( 1 2 6 ) 其中y = 3 ( g i “+ g k ) 7 以一6 ( _ 厶“一五) ，乒震“且4 7 卢0 从( 1 9 ) 式可以看出： 当= 五时，就是新拟牛顿方程( 1 2 5 ) ，所以新拟牛顿方程是( 1 2 6 ) 式的特例。 当。儿时，( 1 2 6 ) 式可写成垦“五2 【1 + 面玺j 儿，属于h u 锄g 族拟牛顿法 而且这族拟牛顿方程具有和新拟牛顿方程一样的性质。 6 肖运海，叶魂嘲于2 0 0 3 年给出了一拟牛顿方程 耻”爵 o 2 7 ) 其中，= ( “+ & ) 7 壤- 2 魄+ l 一五) 并且对一致凸函数的b f g s 算法给出了全局收敛性分析。 2 0 0 4 年，魏增新嘲等人对基于( i 2 7 ) 式的b f g s 算法给出了超线性收敛性证明。 7 焦宝聪，陈兰平于2 0 0 5 年给出了一广义拟牛顿算法，非拟牛顿方程为 壤7 展。瓯= g ( 口) - 其中q ( p ) = 2 ( 1 一口) 墨+ 岛& 7 以- 口仨【o , i 】 迭代矩阵为 啪咖b 一警+ 踹科+ 丸( 珊粥军 舯五= 去一蔫 i 5 拟牛顿法的性质及研究意义 i 5 1 拟牛顿法的性质 拟牛顿法具有正定继承性，使得初始矩阵若为正定矩阵，那么搜索方向始终是下 南京理工大学硕士论文 类新拟牛顿算法及其收敛性 降方向拟牛顿法具有二次终止性，由泰勒展式可知，一个函数在一点附近的性态与 二次函数是很接近的，具有二次终止性质的算法收敛性较高。对于一般的非二次函数， 关于拟牛顿法的收敛性和收敛速度的研究，以鲍威尔教授为首的许多科学家在这方面 作了大量的研究工作，取得了丰硕的成果。最具代表性的成果是，鲍威尔 ( p o w e l l ，1 9 7 1 ) “”证明了当目标函数( z ) 是二阶连续可微的一致凸函数时，采用精确 线性搜索的d ip 方法的全局收敛性及，( 苫) 的海森阵满足利酱希茨条件时的超线性收 敛性。稍后( 1 9 7 2 ) ，鲍威尔舯1 又在b ) 为凸函数的较弱假定下，证明了d f p 方法的 全局收敛性鲍威尔( 1 9 7 6 ) 嘲又证明了，( 工) 是二阶连续可微且有下界的凸函数时， 采用沃尔夫准则的b f g s 方法的全局收敛性和在一致凸且其海森阵满足利普希茨条件 时的超线性收敛性。伯德，诺赛德尔，袁( b y r d ，n o c e d a la n dy u a n , 1 9 8 7 ) 彻将鲍威 尔的结果推广到除了d f p 方法以外的所有限制布鲁丹族算法，证明了对二阶连续可微 且有下界的凸函数，线性搜索采用沃尔夫准则的限制布鲁丹族算法的全局收敛性和 ( x ) 是一致凸函数且其海森阵为霍尔德ih o l d e ri 连续条件下的局部超线性收敛性。 伯德，刘和诺赛德尔( b y r d ，l i ua n dn o 晶d a l ，1 9 9 0 ) 懈将超线性收敛的条件换为了一 个等价条件，给出了一个超线性收敛定理。后来人们不断修改拟牛顿方程或拟牛顿校 正公式，构造了许多新的拟牛顿算法，并通过已有的收敛性定理对算法的收敛性进行 了分析 1 5 2 拟牛顿法研究的意义 最优化问题根据有无约束条件可分为约束和无约束最优化问题。对于无约束优化 问题，首先因为很多实际问题的数学模型本身就是无约束的，也由于无约束优化问题 的求解相对容易得多，而解法的基本思想又常常可以推广到一般有约束的情形。因此， 从这个意义上讲：研究无约束优化问题的计算方法就显得尤为重要，人们对它的研究 也十分重视，新的数值计算方法不断出现，如共轭梯度法、拟牛顿法以及信赖域法等， 其中解决无约束优化问题的拟牛顿算法自从上个世纪6 0 年代末开始就已被广泛地 研究，成为目前最成熟，应用最广泛的解法之一。拟牛顿算法是牛顿法的一种推广， 是在牛顿法的基础上，随着计算机技术的发展而产生的一种新型算法。牛顿法的优点 是成功地利用了h e s s e 矩阵提供的曲率信息，但另一方面，计算h e s s e 矩阵工作量 大，并且有的很难计算，甚至不能求出，而以拟牛顿方程为基础构造的拟牛顿算法克 服了牛顿法的不足。它利用目标函数厂( x ) 一阶导数g b ) 的信息，构造出目标函数的 曲率近似而不需要明显形成h e s s e 矩阵，同时具有收敛速度快的优点。在这一方面， 已经形成了较为完整的算法体系，在理论和应用上都有十分重要的意义。拟牛顿算法 不仅成为无约束优化问题的一个好算法，而且也已被推广到求解约束优化问题。 南京理工大学硕士论文一类新拟牛顿算法及其收敛性 1 6 预备知识及本文工作概要 1 6 1 预备知识 定义1 6 1 设，厶) 是定义在集合d 上的二阶连续可微函数，g o ) 是它的海森矩阵， 若存在m 所 0 ，使得v x d ，耽e 掣，有 m n z l f ，g ( x ) zs m 雠 则称( z ) 在d 上是一致凸函数。 引理1 6 2 设d c 彤是非空凸集，：d c 科一r l ，( x ) 在d 上二阶连续可微， 且存在常数所 0 ，使得 m l l z 0 2sz r v 2 ，o ) z ，v x 工( 毛) ，z r “ 则水平集上( 而) = x l x d ，f ( x ) 厂“) 是有界闭凸集 引理1 6 3 设( 工) 是q 上的一致凸函数，则厂( x ) 在q 上的极小点存在且唯一。 1 6 2 本文工作概要 本文工作可以概括为以下几点： ( 1 ) 本文利用多项式函数近似梯度的方法构造了一族拟牛顿方程。该族拟牛顿方 程有较强的适应性，包含了张建中“”等1 9 9 9 年提出的新拟牛顿方程，2 0 0 3 年肖运海 等嘲提出的拟牛顿方程，以及最初的拟牛顿方程。 ( 2 ) 本文给出了基于该族拟牛顿方程的b r o y d e n 族拟牛顿法，并讨论了算法的对 称正定性，二次终止性。该族拟牛顿法包含了存在的很多算法，例如2 0 0 3 年肖运海等 嗍提出的修改b f g s 算法。 ( 3 ) 本文讨论了基于该族拟牛顿方程的限制布鲁丹族拟牛顿算法的全局收敛性。 利用本文全局收敛性分析，可以把肖运海等拟牛顿法的全局收敛性从b f g s 方法推 广到整个限制b r o y d e n 族。 ( 4 ) 文中还讨论了基于该族拟牛顿方程的b f g s ，p s b ，d f p 算法的局部超线性收敛 性。肖运海等嘲的拟牛顿方程作为该族方程的特例，增加了p s b ，d f p 算法的超线性 收敛性，而且通过本文的收敛阶分析，用一种较简单的方式，给出了新拟牛顿方程嘲 的超线性收敛性证明。 本文的结构安排为：第一章绪论，给出拟牛顿法的由来，研究现状，拟牛顿法 研究的意义，以及本文工作。第二章推导一族拟牛顿方程并给出相应拟牛顿算法的正 定继承性，二次终止性，全局收敛性。第三章证明了算法的局部超线性收敛性。 南京理工大学硕士论文一类新 鼠牛顿算法及其收敛性 第二章一族新拟牛顿算法及全局收敛性 本章将推导一族新拟牛顿方程，并给出基于该族新拟牛顿方程的拟牛顿算法的全 局收敛性，正定继承性，二次终止性。 2 1 推导一族新拟牛顿方程 首先，我们将构造族形式上类似于新拟牛顿方程但比新拟牛顿方程更广泛的拟 牛顿方程。 记 五= ，( ) ，= 可( 黾) ，欺= g 。一& ，g ；= 俨( 黾) ，壤= 一黾 令 x ( f ) 2 黾+ 赢 那么对g o ( r ) ) 求导有 导( g ( 删l 卅地- ) 南 或者 g “喀= 慨l 暑( g ( 删) l f 啦l ( 2 1 ) 首先，我们考虑用下面的二次型 g ( r ) = 胛2 + r r + c 来近似g b ( f ) ) ，其中4 ，b ，c 科。由文献“。可知，我们可以得到新拟牛顿方程 互+ ，五= 以 其中 以2 儿+ s 4 五，4 = 立立立羔生产 然而如果我们采用q p ) = 盯3 + 6 r + c 来近似g e p ) ) ，则q ( r ) 满足下列条件： q ( o ) = c = g ( 黾)( 2 2 ) g ( 1 暖1 1 ) = 口0 反1 1 3 + 6 i 投0 + c = g ( + )( 2 3 ) 1 4 南京理工大学硕士论文 一类新拟牛顿算法及其收敛性 f 。g ( f ) 7 ，( f ) 出= 厶。一五 ( 2 4 ) 式可写成 r 。学= 几一五 求积分得 剑骅剑州( 氐叫 由( 2 2 ) ( 2 3 ) ( 2 5 ) 。我们得到 ( ，反l 广+ 2 矿0 反4 + 矿 4 = 4 ( f k 。一五) , , 1 1 8 , 1 f + b l i s d = y , c 2 9 k 化简( 2 6 ) 式，则( 2 6 ) 式可以写成： 2 y k 7 五一，l i s t f8 k + 4 9 k 7 盈= 4 ( 五+ ，一五) 从而我们得到 刎盯= 塾型掣 为了计算与描述方便，我们把取作五，从而我们得到 训哪= 堑产嗄 把( 2 7 ) ( 2 8 ) 代入( 2 1 ) 式可得： g 0 五= 儿+ 4 4 暖 舯4 = 虹产幽 因此我们可以构造新拟牛顿方程 b i i = y ： 其中欺2 欺+ 4 4 哦，4 = 鱼鱼二鱼! 产 另一方面，如果我们直接对目标函数厂( x ) 泰勒展开，则 m ) = ，( 黾+ - ) + 耵( 黾+ t ) 7 ( x 一- ) + j i ( z 一耳+ ，) 7 v 2 厂( t ) ( 工一黾“) 当x = 茸时， ( 2 4 ) ( 2 6 ) ( 2 7 ) ( 2 8 ) 南泉理工大学硕士论文 一类新拟牛顿算法及其收敛性 ，( 鼍) = 厂( 黾+ 。) + v ( 政+ ) 7 ( 鼍一鼍+ 。) + 三( 一黾+ 。厂v y ( k 。) ( 黾一黾+ ) 即 8 k r v 2 厂( 五。) 盈= 2 9 。7 4 + 2 ( a 一厶。) ；2 ( 五一厶。) + ( + + 敫) 五+ 儿五 所以v 2 厂( 。) 4 - - y ：4 4 因此我们可以构造新拟牛顿方程 b k k = y t 其中雎= 以+ 4 五， 从上面的构造过程可以看出，虽然对目标函数或其导函数采用了不同的多项式函 数进行逼近，却得到形式相似的拟牛顿方程，因此我们希望给出一族新拟牛顿方程： 。瓯= 儿( 2 9 ) 其中 儿k 欺+ 口4 盈 ( 2 1 0 ) 4 = 虹产趔 2 2 基于新拟牛顿方程的拟牛顿算法 ( 2 1 1 ) f 面给出基于该族新拟牛顿方程的基本算法： ( 1 ) 给出初始点而掣和初始正定矩阵岛或风e r ，给f o ，寻1 ，盯o ，1 ) ，选择 充分小的f 0 ，令k = 0 ； ( 2 ) * m m l l g , d o ，其中满足精确线性搜索准则：即 ，( + ”) = 咖，( + 耐) 或起始用口= 1 来试的w o l f e 线性搜索准则，即 五“- - - a + * a , g k 7 以 9 1 0 d t a g d t 1 6 ( 5 ) 利用互或皿的布鲁丹族迭代公式产生盈。l l k , t ，即 其中 其中 牡皿一筹掣+ 籍+ ( 珊暖) 硝加【0 ，- 】 q = 主毫一瓦鼍，玎2 儿+ 矽4 暖， w 哪籍一样叫以r 酬w 口： 哩监：垒z。 ( i - 妒) ( 几”& ) 2 + 妒( 喀7 忍五) ( 儿盯皿几) = 去一蒜， 欺2 几+ 口4 瓯，4 = 垒坠立羔立产 ( 6 ) 令k = k + l ，转入第二步5 2 3 拟牛顿算法的正定继承性和二次终止性 引理2 i 如果，是二次函数，g 是其正定海森阵，那么，当采用精确线性搜索时， 对于算法有如下的关系式成立： 2 五= 0 ( 2 。1 2 ) 儿= g 瓯( 2 1 3 ) 4 = 0( 2 1 4 ) 证明：由精确线性搜索的性质知，( 2 1 2 ) 成立。 因为厂是二次函数，其海森阵g 是一个正定矩阵，由泰勒公式有 败= g l “一g k = 哦 即( 2 1 3 ) 式成立， 同时由泰勒公式，我们有 n - l = g ? 6 t + 妥6 7 g 6 t 1 7 l t l a = 一9 05 l 8 ：g 8 t 将上面两式分别乘以( 一1 ) 和1 ，再相加，则易知( 2 1 4 ) 成立。 定理2 2 ( d f p 方法的二次终止性)如果厂是二次函数，g 是其正定海森阵，那么， 当采用精确线性搜索时，d f p 方法具有遗传性质和方向共轭性质，即对于f = o 1 2 t n , 有 只。乃+ = 4 。j = o , 1 ，值传性质) 巧7 g 玩= o ，j f f i0 , 1 ，f 一1 ( 方向共轭性) 方法在r e + l o ，布鲁丹族拟牛顿校正公式最。 保持正定性。 证明：见定理5 1 3 嘲 根据后面的引理证明，我们可以看出4 7 玎 o 可以满足。 2 4 拟牛顿算法的全局收敛性 在后面关于全局收敛性的讨论中，我们总是假设，( x ) 满足下面的假设条件： ( a ) ，( x ) 是二阶连续可微的一致凸函数，即存在正常数a ，五，使得 a w z 7 g ( x ) z 创z n 眠z f 引理2 4 若，( x ) 满足假设条件( a ) ， 最) 为由拟牛顿法产生的序列，那么我们有： l 睃酽s 瓯7 以s 五0 瓯旷 ( 2 1 5 ) 【( 1 + 们五一邱瓯8 2 最7 肛s ( 1 + p ) 五一铭】慨l f 恢+ l + 一铭) 慨8 证明：( 1 ) ( 2 1 5 ) 式的证明仿照脚。 ( 2 ) 下面我们证明( 2 1 6 ) 式， 根据( 2 1 0 ) ( 2 1 1 ) 式和泰勒展式，我们有 6 7 y = 硭( y 。+ 8 & 酗 = 氓+ 口 2 ( 五一如) + ( 。+ 厂五 2 正7 儿+ 护 欺7 反一五7 g ( 编) 唾 ( 2 1 6 ) ( 2 1 7 ) 苎堕墼兰堡主丝苎= 耋堑塑塑! 鲨墨基堕竺丝 2 ( 1 + 护)