（计算数学专业论文）一族扩展的拟牛顿法及其全局收敛性.pdf

中文摘要 拟牛顿算法是求解无约束最优化问题的最有效方法之一，其基本思 想足用已算得的一阶导数来估计二阶导数。不同类型拟牛顿方法的主要 差别在于：从一次迭代到另一次迭代二阶导数估计值的改变方式以及所 用线性搜索的类型和精度不同。因此它产生了一系列对目标函数二阶 导数的近似矩阵鼠+ 1 。校正产生的矩阵段+ l 其实质是在展的基础上 加一修正矩阵a ，即：鼠+ l = 研+ 氐。本文首先得到修正矩阵a 南应 志喇m 3 池= 器训看+ 器枷枷1 ) ，其 娜= 即l | ，a = 黑u 虿+ 络蜊州t a 2 = 1 ) ；( 3 ) 让蠡； 麓o k 蕊v k 誓t s ku k ) b k s i 鹊藩篱慧1 ) ( 4 ) u l + 去舰一，“南= 器喇五+ 格哆m + 敛的。最后应用流行的1 8 个测试函数给出了这三种算法的数值实验结果。结 果表明所设计的方法有效。 关键词 无约束优化；拟牛顿方程；全局收敛性。 a b s t r a c t ( 英文摘要) t h eq u a s i n e w t o nm e t h o d si so n eo ft h em o s te f f e c t i v em o t h o d sf o rs o l v - i n gt h eu 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 h o s eb a s i ci d e ai st oe s t i m a t e t h es e c o n do r d e rd e r i v a t i v e sw i t ht h ef i r s to r d e rd e r i v a t i v e s t h em a i nd i 丘b r e n c e s b e t w e e nd i f f e r e n tt y p e so fth eq u a s i n e 毗o nm e t h o d sa r e ：t h e c h a n g ew a yo f e s t i m a t eo ft h es e c o n do r d e rd e r i v a t i v e sf r o mo n ei t e r a t et oa n o t h e ri t e r a t e ，a n d t h et y p e sa n da c c u r a c yo fl i n es e a r c h s oi t p r o d u c e sas e r i e so fa p p r o x i m a t i o n m a t r i xb k + lt ot h es e c o n do r d e rd e r i v a t i v e so ft h e o b j e c t i v ef u n c t i o n t h en a t u r e o f 鼠十1i s 鼠+ 1 = b k + a k ，i nw h i c h 鼠i st h ea p p r o x i m a t i o nm a t r i xa tt h el a s t i t e r a t i o n ，a ki ss o l n em a t r i x i nt h i sp a p e r ，t h ew r i t e rf i r s tp r o p o s et h ec o n d i t i o n a n dt h e nt h r e ef o r m u l a u ei os a t i s 母a a r e 百v e n ：( 1 ) a 犀乳：。粤乱凫；( 2 ) 4 惫： 志乱醒；蕊= 器让心+ 善咐，孤入，a ：鸶妇w h i 出 u k , v k 冗礼，a n ds a t l s 母s ；锃七o ，s ；o f r o m 皆出s 没r e a s o n a b l e c h 、o i c e sa r eg o t t e n ：( 1 ) 钍凫。鲰- b k s k , 如2 丽t 哥k 札南钍蚕；( 2 ) u 七2 舭知小祷郴吾+ 器哪孤文2 _ 1 ) 巾胁= 时志口：咄耻器喇彳+ 格蚶，孤“= 1 ) ；c 4 ) 乱膏= ( 1 + 去舰，毗= 鼠s _ | ! ，五二器札：；。矗备磺，c 入，+ a 2 = 1 ) ；( 5 ) u k = s 七， a k s k = 至乱j c ；( 6 ) u 是= b i i c s 南，a 是s 是。罢l 牡是 8 ku k s ；i t k “ s e s sg l o b a lc o n v e r g e n c ep r o p e r t y a tl a s te i g h t e e np o p u l a rt e s tf u n c t i o n sh a v e c o n d u c t e dw h i c hs h o wt h a tt h ep r o p o s e da l g o r i t h m sa x ev e r ye n c o u r a g i n g k e y w o r d s u n c o n s t r a i n e do p t i m i z a t i o n ；q u a s i n e w t o ne q u a t i o n ；g l o b a lc o n v e r g e n c e 1 l l 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适 学位论文作者签名：指导教师签名： 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名： 二卟 两北大学硕士学位论文 1 1引言 第一章绪论 1 9 5 9 年，由d a v i d o n 提出的拟牛顿法利用目标函数梯度夕的信息， 用拟牛顿方程瞰+ 1 s 女= y k 构造出h e s s i a n 矩阵的近似矩阵凤+ 1 ，以此 来代替牛顿法迭代公式中的g ，该方法不仅解决了目标函数的h e s s i a n 矩阵计算量大，难以计算的缺点，还大大的提高了迭代速度。因此，拟 牛顿算法成为解决无约束优化问题最好的方法之一。其中最著名的校 正方法有：s r l 校正( 秩一校正) ，d f p 校正( 秩二校正) ，b f g s 校 正( 秩二校正) ，p s b 校正( 秩二校正) 等成熟，优良的方法。拟牛顿 方程仅仅利用了目标函数梯度值的信息，而忽略了函数值的信息。于 足，1 9 9 6 年徐成贤，张建中教授等人提出了新拟牛顿方程：b k + l 鼠= 蟊， 其中蟊= y k + 半札，弧= 3 ( g k + l + 鲰) t 8 k - 4 i - 6 ( 焱一a 十1 ) 。经证明该方程的 5 ；。u 近似精度比原拟牛顿方程高一阶，且数值实验显示出该方程优于原拟牛顿方 程。基于新拟牛顿方程得到b k + l & = 蠡z d c ，磊z d c = y j + ；堡- 酿【文献3 ； 6 七5 七 b 七+ 1 s 知= 蠡日u ，蟊h u = ( 1 + ；l 纨) 文献2 等方法。以上方法均属于秩二 6 七七 校正。 经研究整理发现，不论基于原拟牛顿方程还是新拟牛顿方程，校正产生的 矩阵鼠+ 1 其实质足在磁的基础上加一修j e 矩阵a 砖，即：b k + 1 = b k + a k 。 从而只要搞清楚修正矩阵a 满足什么样的条件，就可以非常容易的构造出近 似矩阵鼠+ 1 ，这样就使迭代方法有明显的改进和计算速度有极大的提高；更 能把原拟牛顿方程和新拟牛顿方程置于个方程b k + 1 = b k + a k 中，从而使 原有的，成熟的方法能从新的式子b 膏+ 1 = b 七+ a 奄中得到。而且还能将原有 的秩一，秩二校j 下推广到秩佗，构造出秩礼校正公式，这样得到的校正矩阵 列 b k ，容易成为一非奇异矩阵列，由此出发只要其满足一些条件，那么其就 具有超线性收敛速度。 】 第一章绪论 所以，本文的主要工作为： ( 1 ) 、研究修正矩阵凡满足的条件； ( 2 ) 、基于a 得到近似矩阵b k + 1 ； ( 3 ) 、基于近似矩阵吼+ 1 设计出解决无约束优化问题的算法； ( 4 ) 、证明这些算法的全局收敛性，并且通过现在流行的1 8 个测试函数 对算法做出数据分析。 1 2 预备知识 考虑无约束优化问题： m i n f ( x ) 其中z r ”，厂：r 礼_ 月是一个连续可微函数。 牛顿法的基本思想是利用目标函数的二次t , l a r 展开，并将其极小化。 其具体操作足：在x k 附近用二次t a y l a r 展开近似目标函数厂( z ) ， 厂( z ) 竺r e ( x ) = f ( x k ) + x z 七) r 9 知+ x 1 ( z z 七) ? g k ( x z 七) 其中 仂是目标函数厂在x i 点处的梯度值， g i 为第k 次迭代时，目标函数- 厂在x 点处的h e s s i a n 矩阵。 将上式右边极小化，则 x k + l = x k g i l g k 这就足牛顿法的迭代公式。 对于二次正定函数，牛顿法一步即可达到最优解。对于非二次函数，牛顿 法并不能保证经有限次迭代求得最优解，但由于目标函数在极小点附近近似于 二次函数，故当初始点靠近极小点时，牛顿法的收敛速度般足很快的。 牛顿法成功的关键足利用h e s s i a n 矩阵提供的曲率信息，得到搜索方向， 从而进行迭代。在每次的迭代中，均需计算目标函数的h e s s i a n 矩阵。在实 际计算中，计算h e s s i a n 矩阵工作量很大，并且有些目标函数的h e s s i a n 矩 2 两北大学硕士学位论文 阵很难计算，甚至不好求出。这就要求对实际的计算作出简化。于是，1 9 5 9 年d a x 4 d o n 提出了拟牛顿法。 拟牛顿法的基本思想是利用目标函数，的函数值和梯度g 的信息，构造 出目标函数的曲率近似，而不需要明显的形成h e s s i a n 矩阵，同时具有收敛速 度快的优点。 1 2 1拟牛顿条件 设厂：舻_ r 在开集dcr n 上二次可微，在x k + 1 附近的二次近似 为 ，( z ) 型f ( x k + 1 ) + ( t x k + 1 ) ? g k + 1 + 去( z z 七) 丁g k + l ( x x k + 1 ) 对上式两边求导，有 g ( x ) 型g k + 1 + g k + l ( x x k + 1 ) 令x 兰x k ，8 k = x k + 1 一x k ，y 知= g 七+ 1 一g 七，得 g i l y k28 k 或 g k s k 竺y k ( 1 1 ) ( 1 2 ) 显然，对于二次函数，上述关系式( 1 1 ) ，( 1 2 ) 精确成立。现在，要求 在拟牛顿法中构造出的h e s s i a n 矩阵逆近似凰+ l 满足( 1 1 ) ，h e s s i a n 矩阵近 似b k + 1 满足( 1 2 ) ，即 h k + l y k = 8 k( 1 3 ) 或 b k + l s k = y k( 1 4 ) 通常把上述关系式( 1 3 ) 和( 1 4 ) 称作拟牛顿条件或拟牛顿方程。 拟牛顿法的主要步骤为 ( 1 ) 令d k = 一凰鲰； 3 第一章绪论 ( 2 ) 沿方向也作线性搜索，得到x k + 1 = x k + o c k d k ； ( 3 ) 校正巩产生h k + 1 一般的拟牛顿法算法如下( g q n m ) ： s i ：选取初始值。z o 舻，g o 舻煳，0 0 ， 令x k + 12x k + a k d k ； s 5 ：校正凰产生风+ l ，使得拟牛顿条件( 1 3 ) 成立： s 6 ：k ：= k + 1 转s 2 。 在上述拟牛顿算法中，初始h e s s i a n 矩阵逆近似凰通常取为单位矩 阵，h o = i 。这样，拟牛顿法的第一次迭代等价于一个最速下降迭代。 与牛顿法相比，拟牛顿法有下列优点： ( 1 ) 仅需一阶导数，牛顿法需二阶导数； ( 2 ) h k 保持正定，使方法具有下降性质，在牛顿法中，g k 可能不定； ( 3 ) 每次迭代需d ( 扎2 ) 次乘法，牛顿法需o ( n 3 ) 次乘法。 更多的时候，拟牛顿法的迭代形式采用h e s s i a n 矩阵近似： ( 1 ) 解风也= 一g k 得d k ； ( 2 ) 沿方向出作线性搜索，得x k + 1 = x k + o 屉比； ( 3 ) 校正鼠产生鼠+ 1 1 2 2对称秩一校正公式( s r l 校正) 设凰是第k 次迭代的h e s s i a n 矩阵逆近似，现在希望从风产生凰+ l ， 即 风+ 1 = h k + e k 其中风是一个低秩矩阵。在秩一校正中，有 h k + l = 风+ 钍t f 丁 4 两北大学硕士学位论文 由拟牛顿条件( 1 3 ) 可知， 即 h k + 1 y 知= ( h k + 牡，) y k = 8 k ( v t y k ) z t = 8 七一风鲰 故乱必定在方向8 k h k y k 上。假定8 七一h k y k 0 ( 否则，风已经满足拟牛 顿条件) ，向量t ，满足v t y 0 ，则 风1 ：h k + 赤( s 七一h k y 庇) u t ( 1 5 ) 由于h e s s i a n 矩阵足对称的，故要求h e s s i a n 矩阵逆近似也足对称的，从 而取口= 8 k h k y k ，得 h k + 1 = h k + 坠皋替 ( 1 6 ) 公式( 1 6 ) 称为对称秩一校正公式( s r l 校正) 。 对称秩一校正的突出性质足它天然具有二次终止性，即对于二次函数，它 不需要进行一维搜索，而具有佗步终止的性质。但s r 1 校正校正不保持迭代 矩阵风的正定性。仅当( s 七一巩弧) 丁y k 0 时，s r l 校正才具有正定性。而 这个条件往往很难保证。即使( s 南一凰鲰) 丁y k 0 满足，它也很可能很小，从 而导致数值计算困难。 校正保持正定性是非常重要的。如果，的h e s s i a n 矩阵在x 4 处正定，则 驻点x 4 就足强局部极小点。因此，希望h e s s i a n 矩阵近似矩阵瞰或h e s s i a n 矩阵逆近似矩阵风正定。此外，如果_ 玩) 或 凰) 正定，则f 的局部二 次模型就有唯一的局部极小点，由算法产生的搜索方向d 盘就是下降方向。因 此，通常要求校正保持正定性，即若风正定j 则风+ 1 也正定。 1 2 3对称秩二校正公式( d f p 校正) 设对称秩二校正为 h k + 1 = h k + a 7 t u 丁+ b v v 丁 5 第一章绪论 由拟牛顿条件( 1 3 ) 可知， h k y 奄+ a u l t 丁y k + b v v 丁y k = 8 k 这里札和t ，并不唯一确定，但u 和u 的明显的选择足 于是 乱= 8 k 舭= 日七鲰 a i t 丁y k = 1 b v t y _ i c = 一1 从而 1l n = 鬲一= 吊一 u 1y k 8 。y k ， 11 d 2 一v t y k2 一y 吾h k y k 因此 h k + 1 - - - - 风+ 舞一面h k y k y i t h k ( 1 7 ) 这个公式称为d f p 公式，它足由d a 。4 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 年) 发展的。 d f p 校正公式是典型的拟牛顿校正公式，它有许多重要性质： 1 对于二次函数( 采用精确线性搜索) ： ( 1 ) 具有二次终止性质，即凰= g - 1 ( 2 ) 具有遗传性质，即凰y i = 8 i ，j 0 时，d p f 校正公 式( 1 7 ) 保持正定性。 两北大学硕士学位论文 证明证明过程见文献【1 6 】的定理5 1 3 ，从略。 定理中保持正定性的条件s r k y k 0 是实际的，并且可以满足。 对于正定二次函数， s t 七锹= s ：g 0 对于一般函数， mmt s 鑫y k2 夕孟+ 1 s k g 五8 k 当采用精确线性搜索时，鲧t + 1 8 k = 0 ，靠8 k 0 。 当采用近似线性搜索时，如果准则i 矗1 d kl - - a g t d k 满足，那么s t y k 0 。 定理1 2 2 ( d f p 方法二次终止性定理) 如果，足二次函数，g 足其正 定h e s s i a n 矩阵，那么当采用精确线性搜索时，d f p 方法具有遗传性质和方 向共轭性质。即对于i = 0 ，1 ，2 ，m ，有 既+ 1 协= s j ， j = 0 ，l ，2 ，i s t g s j = 0 ， j = 0 ，l ，2 ，i 一1 方法在m + l 扎步迭代后终止。如果m + 1 = 扎，则凰= g _ 1 。 证明证明过程见文献 1 6 的定理5 1 4 ，从略。 d f p 方法足一个实际上广为采用的方法，它在理论分析和实际应用中都 起了很大作用。但是，迸一步的研究发现，d f p 方法具有数值不稳定性，有 时产生数值上奇异的h e s s i a n 矩阵。下面给出的b f g s 校正克服了d f p 校正 的缺陷。 1 2 4b f g s 校正 前面已经知道 h k + l y k = 8 k( 1 3 ) 是关于逆h e s s i a n 矩阵近似的拟牛顿条件，而 b k 。1 8 k2y k 7 ( 1 4 ) 第一帝绪论 是关于h e s s i a n 矩阵近似的拟牛顿条件类似于从( 1 3 ) 得到关于吼的d f p 校正公式，可以从( 1 4 ) 得到关于b 膏的b f g s 校正公式 b k + l - - - - b k + 舞8 k 一挚s k l ：了k 8 k ( 1 8 ) 班 事实上，只要通过对 、 砜，= 凰+ 蓑y k 一铭1 - 1 墼k y k ( 1 7 ) s 鑫纸 作简单的交换日hb ，sh 可，关于鼠的b f g s 校正就可得到。因此， 把( 1 8 ) 称为互补d f p 公式。 b f g s 校j 下足迄今最好的拟牛顿公式。它具有d f p 校正所具有的各种性 质。此外，当采用不精确线性搜索厶+ 1 厶+ 6 a k g t d k 和9 & 1 d k a g t d k 时，b f g s 公式还具有总体收敛性质，这个性质对于d f p 公式还未能证明成 立。在数值实验中，b f g s 公式也优于d f p 公式，尤其足它常常能与低精度 线性搜索方法一起连用。 1 2 5 b r o y d e n 族 d f p 校正和b f g s 校正都是对称秩二校正，都足由日惫弧和s 知构成，因 此d f p 校正和b f g s 校正的加权组合也具有同样的类型，即 j e 7 备1 = ( 1 一砂，、b d f p + y , “一r 七b + f 1 g s ( 1 9 a ) 其中妒是一个参数。( 1 9 a ) 称为b r o y d e n 族校正。 显然，b r o y d e n 族( 1 9 a ) 满足拟牛顿条件( 1 4 ) ，它也可以写成 其中 在( 1 9 b ) 中， b 玉l = 。b 七b + f 1 g s + 础岛。蚕 = 鼠+ 舞一笔l ：墼；k s k + 帅蚕雠s 蠢 u 七= ( s 融s 南) 卸磊y k 一霹b 聃k s k 1 ( 1 9 功 8 两北大学硕士学位论文 取多= 0 ，得b f g s ( i 8 ) ： 取妒= 1 ，得d f p ( i 7 ) ； 眦= 面，牖s r l ( 1 6 ) ； 定理1 2 3 ( b r o v d e n 族校正的正定性) 设参数多0 ，当且仅当s t y k 0 时，b r o y d e n 族校正公式( 1 9 ) 保持正定性。 ， 证明证明过程见文献 1 6 】的定理5 2 2 ，从略。 这个定理说明，在b r o y d e n 族中，并不是所有的成员都保持正定性。显 然，当0 时，磙1 保持正定：对于 0 。 扩展拟牛顿法( e q n m ) ： s i ：选取初始值。z o 舻，b o 0 舻黼，0 o 时，b k + 1 0 ( 3 1 ) i , t n 证明同文献【1 6 】中定理5 1 3 ，从略。 定理3 1 对任意的k ，由e q n m 迭代产生似七，x k + 1 ，g k + 1 ，d k + 1 ) 。设也 的选择满足公式( a ) ，再假设f 是二次连续可微的，且 z r c ( x ) z 0 v x ，z r n( 3 2 ) 则对任意的k ，b k + 1 0 证明假设a 选取满足公式( a ) 。 ( 1 ) 由算法的初始选择知，b o 0 ； 1 7 第三章重要的r 丰质 ( 2 ) 假设n = k 时，b k 0 即s t b s k 0 当n = k + 1 时， s t 七玑= s t b k + 1 s 詹= s 五b 七s 后+ s 蚕a 七8 , k = s t b k s k + o k 所以 = 8 t b k 8 詹+ 2 ( a 一 + 1 ) + s ；( 夕七+ 1 + g k ) = s 融s 七+ 2 【一夕矗 + 拯g ( z 南+ 丁( z k + l - - x k ) ) s - 一c 】+ s 融+ t + 瓠) = s t b k s 后+ f f a ( x k 十 r ( x k + 1 一z 七) ) s 凫一s t 知可七 丁( 0 ，1 ) 由( 3 2 ) 知 2 s t ky 七= f i b 七s 七+ f f a ( x k + r ( x k + 1 一z 七) ) s 七 t 舭 0 从而，由引理3 1 得：对任意的k ，b k + 1 0 。 定理3 2 对任意的k ，由e q n m 迭代产生( q 知，z 七+ l ：g k + 1 ，c f 豇+ 1 ) 。设a 的选择满足公式( a ) ，则当o k 0 时，b k + 1 0 证明假设a 七选取满足公式( a ) 。 ( 1 ) 由算法的初始选择知，b o 0 ； ( 2 ) 假设n = k 时，b k 0 即s t b k s k 0 当n = k + 1 时， 瓤t 蛳= s r b k + 1 8 k = s t b k s k + s t a k s k = s t b k s k + o k 0 所以，由弓l 理3 1 矢口，b k + 1 0 由以上两定理的证明过程看，若条件( 3 2 ) 不能满足，( 例如：f 为非凸 函数) ，b k 的正定性就不能保证。因此，需要对其加一些必要的限制。 定义指标集： k 却：志 , 3 1 1 棚i i ) 1 8 ( 3 3 ) 两北大学硕： ：学位论文 _ - ! ! ! ! ! ! ! ! ! 竺! ! ! ! = = ! ! = = = = = ! ! = = ! ! ! 竺竺! = = ! ! ! ! = 竺! ! ! ! = ! ! ! 竺! ! ! ! 竺= ! ! ! 竺! ! ! 其中 卢 0 ，y p 1 ，p 2 】，0 0 舻黼，0 0 。 证明假设a ，选取满足公式( a ) 。 不失般性，假设l 鲰l i 0 ，否则e q n m c u 终，止a ( 1 ) 由算法的初始选择知，b o 0 ； ( 2 ) 假设n = k 时，b k 0 。 当n = k + l 时，由( 3 ，3 ) 知 若k k ，0 是 0 贝0 由定理3 2 知，b k + 1 0 ； 若k 譬k ，则b 七+ l = b k 0 综上所述，该定理成立。 1 9 第硼章算法 4 1 最优化方法的结构 第四章算法 最优化方法通常采用迭代方法求它的最优解，其基本思想足；给定一个初 始点x o r n ，按照某一迭代规则产生一个点列【z 七) ，使得 ( 1 ) 当 z 七) 足有穷点列时，其最后一个点足最优化模型问题的最优解； ( 2 ) 当 z 七) 是无穷点列时，它有极限点，且其极限点是最优化模型问题 的最优解。 一个好的算法应具备的典型特征为：迭代点z 七能稳定地接近局部极小 点x 的领域，然后迅速收敛于x + 。当给定的某种收敛准则满足时，迭代即终 止。 一 设z 七为第k 次迭代点，比为第k 次搜索方向，a 七为第k 次步长因子， 则第k 次迭代为： xk+l 2 x k + o 。k d k 从这个迭代格式可以看出，不同的步长因子。七和不同的搜索方向d 七构成了 不同的方法。在最优化方法中，搜索方向如是j r 在点x k 处的下降方向， 即d 七满足 g d k 0 ，使得 熙篱= 口屉一o 。i l z 七一z + l i n 1 则称算法产生的迭代点列 z 如) 具有q q 阶收敛速度。特别地， ( 1 ) 当q = 1 ，q 0 时，迭代点列 。岛) 叫做q 一线性收敛速度： ( 2 ) 当1 0 只积忆，0 0 ，使对任意 的k 有 l 恢l l m 1 ，i l g 南i l a 龟 ( 5 2 ) 5 2 重要定理 引理5 1 ，满足a ( 1 ) ，a ( 2 ) 。b k 和 丁七) 足由算法4 1 ，4 2 ，4 3 迭代产 生的，假设存在常数a 1 ，a 2 ，使满足： 则 b k u k l l a l ll 钍k l l ， u t b k u k a 2 1 1 u k l l 2 ，v u k r n ( 5 。3 ) 1 她耐g ( x k ) = 0 矗，。c 2 4 ( 5 4 ) 两北大学硕士学位论文 证明 因为g k = 一b k d k ，则由( 5 3 ) 知： 鼠如兰0 2 i t d 七1 1 2 ，n 2 j i d 七f lsl i g k t j a l i l d a l l( 5 5 ) 记指标集q = i ：l il b k u k l l 0 1 l i u 七虬u t b k u k 0 2 i i u 知i f 2 ) 由w o l f e 条件( 4 2 ) 知 又由于 ( g 辩+ 1 一g k ) 丁d 七一( 1 一o ) f f d , , ( 肌+ 1 一弧) 丁d k i i g k + l g k l li l d k l f l i i s k l | i d k 故对v k q j 有 因为 s 知| | = l | 一a k d k l i | l n 彪i d k 一( 1 一仃) 腰kb k d k= 二二二 l l l d k l 2 ( 1 0 r ) a 2 ：= ：- - _ _ _ _ - _ - - - - 一 l o 。 n ( 靠一 + t ) = 长( 一 十z ) = l i m f ( z t ) 一，p ) k = l七= 1 则由c ( 2 ) ：1 i m = f + 知存在一常数厂4 ，使满足 抒一 ( 一 + z ) = ， 1 ) 一，+ 一 七 口 第五章伞局收敛性 所以 即有 l i m 仇d k = k e g ! 惫“ l 、i m ， 一鲰t d 膏= 0 k e g l i m i n fg ( x k ) = 0 七o 【， 引理5 2 设b 0 是对称正定矩阵，b 盎是由公式( a ) 迭代得到。假设存 在m ，m 0 ，使满足对任意的m ，m 有 蒜狐襞m 其中 蟊= 鲰+ a 哥8 凫，则存在常数t ，使满足s t b k s k 圳s 七1 1 2 。 证明证明过程同文献【8 的定理2 1 ，从略。 定理5 1 设f 满足a ( 1 ) ，a ( 2 ) ，b k 和 z 豇) 是由算法4 1 迭代产生，则 l i m i n fg ( x k ) = 0 七一o 。 证明假设t i m i n fg ( x k ) 0 片o o 则必存在常数e ( 0 ，1 ) ，使满足对任意的k ，有i | m | | e 。 对v k k ，由( 3 3 ) 知 又由于 舔= 丽s t y k + o k = 可s t b k s k + 2 0 k磊驴21 矿2 可矿 器删州r 2 p ( 1 2 t i c 芦2 0 七i = 1 2 ( a 一 十1 ) + s 吾( 夕自+ 1 + g k ) = i - 2 9 ( x 七+ 丁s 七) + 9 恐+ l + g k 7 s 南 l i s k l | 【| 夕蠡+ 1 9 ( z 膏+ 丁s ) l + l g k 一9 ( z 七十丁s 七) i 】 2 6 两北大学硕士学位论文 所以 i i s 后| | 【l ( 1 一丁) i i s 知l i + l 7 - l l s k l l 】 = l i i s 七| | 2 丁【0 j1 】 刮时争氆鬻乎一掣k = + 扣+ 淼s 免一耶川i 扣硎+ 互1 丽i g k + 三1 1 s 知s 删 孰删+ 沙删+ 知k i | ：( 2 l + 1 m = ) i i | | 所以对v k k ，有 氅 兰：量孥型l 兰：丝兰 s 舌蟊。 2 b ej 。：恢1 1 2 2 3 0 z z 一 所以由弓l 理5 2 知，对于 b k k e k ，存在常数a 1 ，n 2 ，使满足( 5 3 ) 成立。 从而与引理5 1 矛盾。 所以，l i mi n fg ( x k ) = 0 。 k - - c o 定理5 2 设，满足a ( 1 ) ? a ( 2 ) ，b k 和 z 七) 是由算法4 2 迭代产生，则 l 却i n fg ( x k ) = 0 七 证明前半部分证明同定理5 1 i | 磊i | = l + a 詹s 忌 =”“【一(1+sk-瓦yk)yk(1+k y k 一嘻b k s k ( b k s k ) r k 2 7 第五章伞局收敛住 = i l y k + 扣+ 去) y k - b k s k = l 争蓑一b s k l l 狐i i + 1 2 。s 0 剖k y k + 互1 慨s 南i i 2 l i i 鼠i i + 丢尬怙岛i i 1 = f 2 l + s m 2 ) j l s k l j 所以对v k k ，有 一i i 蠡- 1 1 2 竺圭竺坐坐一竺：型j - 竺2s 吾蟊二2 芦畔恢1 1 2 2 多出 所以由引理5 2 知，对于 b 膏 k e k 。存在常数a l ，a 2 ，使满足( 5 3 ) 成立。 从而与引理5 1 矛盾。 所以，l 徊i n fg ( x k ) 等0 。 膏_ + 定理5 3 设j r 满足a ( 1 ) ，a ( 2 ) ，b k 和 z _ | c ) 足由算法4 3 迭代产生，则 l i m i n fg ( x k ) = 0 向 证明前半部分证明同定理5 1 记椤奄为一鲰与乳的夹角，即 由于 所以 则 一夕, t s = | i ll i s 8 k耙l c o s 移知夕= i 夕知耙l 秽知 b k 8 k = 一n 七玑 s t b k s k = 一e t 夕七， q 七= 锚 l | 鼠s 七| |q k l l v k l |l | 8 t b k s k2 - - a k q t s k2 丽丽孤c o s 西f 2 i i m 洲s 七i ； k 2 8 5 七i lc o s o 七 ( 5 7 ) 两北火学硕士学位论文 所以 所以对v k k ，有 i | 蟊1 1 2 ， f 丁s s ；弧 蟊= l l 鲰+ a k s k l y k + j s 看b l k s k 鼠s 七 二鼠s 七 洲+ 甄i i b 膏s k i 以 s 之6 南s 七 s ( 1 + c o s 秽七 ) l l l s k i ( 1 + 赢) 2 工2 | s k i t 2 2 e 肛2 i i s k l l 2 ( 1 + 丽1 ) 2 三2 2 6 e ： 所以由引理5 2 知，对于( 鼠) 南k ，存在常数a l ，a 2 ，使满足( 5 3 ) 成立。 从而与引理5 1 矛盾。 所以，l 卸i n fg ( x k ) = 0 。 & 一 第六帝数值结果 6 1 数值结果 第六章数值结果 在本单元中，给出算法4 1 ，4 2 ，4 3 的数值实验结果。 测试函数均来源于文献 17 】。程序语言为m a t l a b 7 0 。 对于所有的测试函数，终止条件为l l 鲰1 0 6 ；初始矩阵b o = ，；步 长q 良的计算满足( 4 1 ) ，( 4 2 ) ，其中6 = 0 0 1 盯= 0 9 。 在算法4 1 ，4 2 ，4 3 中：芦= 1 0 一 若l i9 七j i 1 ，贝07 = 3 ：否贝0 ，7 = o 0 1 在表中： d i m ( d i m e n s i o n ) ：测试函数的维数； ni ( t h en u m b e ro fi t e r a t i o n s ) ：迭代次数； nff t h en u m b e ro ff u n c t i o ne v a l u a t i o n s ) ：函数值计算的次数； n gf t h en u m b e ro fg r a d i e n te v a l u a t i o n s ) ：梯度值计算的次数。 t a b l e1 ：( n i n f n g ) 3 0 两北大学硕士学位论文 t a b l e 】：( n i n f n g1 _ _ _ _ l _ - _ _ _ - _ - - - - - - _ _ _ - _ _ _ - _ - - l - 一_ 一_ p r o b l e md i ma l g o r i t h m 4 1 a l g o r i t h m 4 2a l g o r i t h m 4 3 b f g s - 一 k o w o s b4 2 8 3 2 2 9 2 8 3 1 2 92 8 3 2 2 9 2 8 3 2 2 9 b i g g s 6 o s b 21 1 韬么s o n2 0 r o s e x8 3 5 4 6 3 6 5 6 8 2 5 7 5 6 9 3 5 8 7 4 1 3 3 7 5 3 8 4 9 3 9 5 3 7 9 5 5 5 6 9 2 5 7 7 6 1 3 4 7 7 3 6 4 7 3 9 5 3 8 0 5 4 5 5 9 1 5 6 3 6 4 7 3 9 5 3 8 0 5 4 5 5 9 1 5 6 7 6 1 3 5 7 87 7 1 3 8 7 8 5 0 2 6 6 6 3 4 2 6 7 2 6 6 6 5 7 2 6 7 3 0 2 6 9 9 3 0 32 4 6 6 4 0 2 4 7 1 0 0 3 8 1 1 1 3 6 3 8 24 0 8 1 1 9 9 4 0 9 4 0 7 1 2 0 1 4 0 84 1 5 1 1 9 2 4 1 6 l i n2 1 3 2 1 3 21 3 2 i 3 2 5 0 1 3 21 3 2 1 3 2 1 3 2 1 0 0 1 3 2 i 3 21 3 2 1 3 2 t r i d3 1 2 2 9 1 3 1 3 3 1 1 41 2 3 1 1 4 1 2 3 1 1 4 5 0 6 7 3 3 5 6 8 6 2 3 4 0 6 36 3 3 4 0 6 4 6 3 3 4 0 6 4 1 0 0 1 1 2 6 4 4 1 1 3 1 1 2 6 4 1 1 1 31 1 2 6 3 7 1 1 3 1 1 2 6 3 7 1 1 3 2 0 0 1 9 5 1 1 5 5 1 9 62 2 5 1 2 5 3 2 2 6 2 1 6 1 2 2 3 2 1 72 1 8 1 2 2 8 2 1 9 v a x d i m2 5 1 3 6 5 1 3 6 6 1 4 76 1 4 7 5 0 2 7 7 4 3 1 2 3 6 3 2 6 2 6 6 7 3 02 6 6 7 3 0 1 0 0 4 2 1 0 1 4 7 3 1 9 6 3 3 3 3 8 0 3 63 5 1 4 0 3 8 2 0 0 8 7 2 4 0 9 0 3 6 1 3 2 3 8 4 3 1 7 4 5 3 3 4 1 1 2 4 0 t r i g 3 1 3 1 9 1 7 1 2 1 9 1 7 1 5 2 3 1 9 1 5 2 3 1 9 5 0 4 2 4 3 4 3 4 2 4 3 4 3 4 4 4 8 4 5 4 4 4 s 4 5 1 0 0 4 9 5 2 5 0 4 9 5 4 5 04 8 5 1 4 9 4 8 5 1 4 9 b v 3 6 1 4 7 6 1 4 7 6 1 4 76 1 4 7 1 0 1 8 3 9 1 91 8 3 9 1 9 1 8 3 9 1 9 1 8 3 9 1 9 - _ _ - _ _ i _ - 一一一 第六章数值结果 表中针对本文所设计的三种算法与传统的最有效的b f g s 算法问进行了 比较，该数值试验表明本文所设计的算法4 1 是这四种算法中最有效的算法， 并且算法4 2 ，4 3 比传统的最有效的算法b f g s 还要有效。从而，本文所设计 的三种算法与传统的最有效的算法b f g s 相比有着自身的优势，这说明本文 所设计的三种算法是成功的，可以