无约束最优化问题的拟牛顿法毕业论文

1、题 目：无约束最优化问题的拟牛顿法毕业论文诚信声明本人声明：1、本人所呈交的毕业设计（论文）是在老师指导下进行的 研究工作及取得的研究成果；2、 据查证，除了文中特别加以标注和致谢的地方外，毕业 设计（论文）中不包含其他人已经公开发表过的研究成果，也不包含为获得其他教育机构的学位而使用过的材料；矚慫润厲钐瘗睞枥庑赖。3、我承诺，本人提交的毕业设计（论文）中的所有内容均 真实、可信。作者签名:日期：年 月曰或全部内容残骛楼静锩瀨濟溆塹籟。毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教 师的指导下进行的研究工作及取得的成果。 尽我所知，除

2、文中特别加 以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研 究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。聞創沟燴鐺險爱氇谴净。作者签名：日期：指导教师签名：日期：使用授权说明本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电 子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供 目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制 手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分作者签名： 日

3、 期：学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外， 本论文 不包含任何其他个人或集体已经发表或撰写的成果作品。 对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律后果由本人承担。 酽锕极額閉镇桧猪訣锥。作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩

4、印或扫描等复制手段保存和汇编本学位论文。彈贸摄尔霁毙攬砖卤庑。涉密论文按学校规定处理。作者签名：日期： 年 月 日导师签名:日期： 年 月指导教师评阅书指导教师评价：一、撰写（设计）过程1、学生在论文（设计）过程中的治学态度、工作精神优 良 中 及格 不及格2、学生掌握专业知识、技能的扎实程度优良中及格不及格3、学生综合运用所学知识和专业技能分析和解决问题的能力优良中及格不及格4、研究方法的科学性；技术线路的可行性；设计方案的合理性 优 良 中 及格 不及格5、完成毕业论文（设计）期间的出勤情况优良中及格不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？优良中及格不及格2、

5、是否完成指定的论文（设计）任务（包括装订及附件）？优良中及格不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义优良中及格不及格2、论文的观念是否有新意？设计是否有创意？优良中及格不及格3、论文（设计说明书）所体现的整体水平优 良 中 及格 不及格建议成绩：优 良 中 及格 不及格（在所选等级前的内画“ V”）指导教师：（签名）单位：（盖章）评阅教师评阅书评阅教师评价：一、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？优良中及格不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？优良中及格不及格二、论文（设计）水平1、论文（设计）的理论意义或对解

6、决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？优良中及格不及格3、论文（设计说明书）所体现的整体水平优良中及格不及格建议成绩：优 良 中 及格 不及格（在所选等级前的内画“ V”）评阅教师：（签名）单位：（盖章）年 月 日教研室（或答辩小组）及教学系意见教研室（或答辩小组）评价：一、答辩过程1、毕业论文（设计）的基本要点和见解的叙述情况优 良 中 及格 不及格2、对答辩问题的反应、理解、表达情况优良中及格不及格3、学生答辩过程中的精神状态优良中及格不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？优良中及格不及格2、是否完成指定的论

7、文（设计）任务（包括装订及附件）？优良中及格不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？优良中及格不及格3、论文（设计说明书）所体现的整体水平优良中及格不及格不及格（签名）日评定成绩：优 良 中 及格（在所选等级前的内画“ V"）教研室主任（或答辩小组组长）：年 月教学系意见:（签名）系主任:毕业设计（论文）任务书题目 无约束优化问题的拟牛顿法姓名 XX 院（系） xx 专业信息与计算科学 班级 xx 学号 XX指导老师 xx 职称教研室主任 xx一、基本任务及要求：1.基本任务:在牛

8、顿法基础上提出拟牛顿法，设计拟牛顿法的算法，了解拟牛顿法的优点及用途。在一定的条件下证明该算法的合理性并对其收敛性进行分析。讨论算法的收敛速度，通过数值试验对算法的有效性进行验证。謀荞抟箧飆鐸怼类蒋薔。2 基本要求：对拟牛顿法给岀合理的算法；利用理论知识对算法合理性进行证明对其收敛性以及收敛速度进行分析证明。写出毕业设计说明书， 完成全部研究工作和毕业论文。厦礴恳蹒骈時盡继價骚。.、进度安排及完成时间：第一阶段（第1 4周）：进行调研，查阅相关资料，撰写开题报告，并于第4周星期五交开题报告；第二阶段（第5- 12周）：在指导教师的指导下，对课题进行研究，按预定要求获得毕业论文开题报告中的预期结

9、果（即进行算法设计，研究算法的合理性，实现算法等工作），并撰写毕业论文，第 12周五之前交初稿；第三阶段（第13 - 14周）：指导教师对毕业论文进行批阅，提出修改意见并指导学生进行毕业论文的修改，并检查算法的实现情况（如程序的可行性和通用性等）第四阶段（第15周）：指导教师指导学生将毕业论文定稿，并准备毕业论文答辩；第五阶段（第16周）：进行毕业论文答辩。摘 要茕桢广鳓鯡选块网羈泪。前 言鹅娅尽損鹤惨歷茏鴛賴。第1章最优化基础籟丛妈羥为贍债蛏练淨。1.1无约束最优化问题的最优性条件 3預頌圣鉉儐歲龈讶骅籴。1.2 收敛概念渗釤呛俨匀谔鱉调硯錦。1.3 Wolfe准则和 Armijo准则洗誅卧

10、泻噦圣骋贶頂廡。第2章拟牛顿法算法设计 8擁締凤袜备訊顎轮烂蔷。2.1拟牛顿法条件贓熱俣阃歲匱阊邺镓騷。2.2 算法设计坛搏乡囂忏蒌鍥铃氈淚。第3章收敛性证明1.1蜡變黲癟報伥铉锚鈰赘。3.1总体收敛 11買鯛鴯譖昙膚遙闫撷凄。3.2 局部超线性收敛 1儀镝鯛駕櫬鹕踪韦辚糴。第4章数值验算2驅踬髏彦浃绥譎饴憂锦。4.1 问题模型2猫虿驢绘燈鮒诛髅貺庑。4.2 数值结果2锹籁饗迳琐筆襖鸥娅薔。总 结2構氽頑黉碩饨荠龈话骛。致谢2輒峄陽檉簖疖網儂號泶。参考文献25尧侧閆繭絳闕绚勵蜆贅。附 录26识饒鎂錕缢灩筧嚌俨淒。无约束最优化问题的拟牛顿法摘要：拟牛顿法是求解无约束最优化问题最常用的方法之一，拟

11、牛顿法是在牛顿法的基础上提出来的。牛顿法成功的关键是利用了Hesse矩阵提供的曲率信息，但计算Hesse矩阵工作量大，并且有的目标函数的Hesse矩阵很难计算，甚至不 好求出。拟牛顿法通过函数的一阶导数构造出曲率的近似，从而避免了求函数的Hesse矩阵,不需要求函数的二阶导数,从而大大的减小了计算的复杂度。同时拟牛顿法还具有超线性收敛以及收敛速度快的优点。拟牛顿算法在求解无约束优化 问题中占有不可取代的地位。同时也是很多学者研究的课题。本论文将依靠前人 的基础,对拟牛顿法进行介绍并对其收敛性进行证明,同时给出数值分析。凍鈹鋨劳 臘错痫婦胫籴。关键词：拟牛顿法，无约束优化，收敛性。A quasi

12、-newton method for Unconstrainedoptimization恥諤銪灭萦欢煬鞏鹜錦。Abstract: Newt on method is to solvi ng uncon stra ined optimizati on problem of one of the most commo nly used methods.Quasi-newt on method is in Newt on put forward on the basis of law.Newt on method the key to success is the use of the Hesse

13、matrix the curvature of the in formatio n but provide Hesse matrix calculati on workload is big, and some of the objective function Hesse matrix is difficult to calculate, even bad work out.Quasi-newt on method through the first derivative con structed out of the curvature approximate avoid a for th

14、e Hesse matrix could n't ask the sec ond order derivatives.Thus greatly reduced the complexity of the calculati on and quasi-newt on method also has superlinear convergenee and convergenee speed advantages quasi-newt on algorithms in sol ving uncon stra ined optimizati on has irreplaceable posit

15、ion in also many scholars research project of this paper will be depend on the basis of predecessors' to be Newt on method and the con verge nee proof and prese nts nu merical an alysis鯊腎鑰诎漣鉀沩懼統庫。Key words:Quasi-newt on ,U neon strai ned optimizati on ,Co nv erge nee硕癘鄴颃诌攆檸攜驤蔹。最优化方法是近几十年形成的，它主要运

16、用数学方法研究各种系统的优化 途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种 有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究 的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效 能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生 产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺 少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领 域，发挥着越来越重要的作用。本章将介绍最优化方法的研究对象、特点，以及 最优化方法模型的建立和模型的分析、 求解、应用。主要是线性规划问题的模

17、型、 求解（线性规划问题的单纯形解法） 及其应用一一运输问题；以及动态规划的模 型、求解、应用 资源分配问题。 阌擻輳嬪諫迁择植秘騖。无约束优化问题是最优化问题的基础，是数值计算领域中十分活跃的研究 课题之一，历时较长，获得的成果也较多，有关的方法和理论比较成熟。其中非 线性无约束最优化方法在科学计算和工程分析中起着越来越重要的作用。牛顿法作为求解最优化问题最有效的方法之一。它的基本思想是利用目标函数的二次泰 勒展开，并将其极小化。在非线性无约束最优化问题中，对于正定的二次函数， 牛顿法一步即可达到最优解。对于非二次函数，牛顿法并不能保证经有限次迭代 求得最优解，但由于目标函数在极小点附近似于

18、二次函数，故当初始点靠近极小点时，牛顿法的收敛速度一般是很快的，因此这种方法得到了很多人的认可与利 用。但牛顿法中每次迭代都需要计算 Hessian矩阵，但计算Hessian矩阵工作量 大，并且有的很难计算，甚至不好求，而以拟牛顿方程为基础构造的拟牛顿算法 克服了牛顿法的这一不足。因此拟牛顿法被广泛的认可，她的应用相当广泛。可 以剞劂很多问题。并有很多人多拟牛顿法做了研究。氬嚕躑竄贸恳彈濾颔澩。对于拟牛顿法的算法设计，也已经有不少学者提出过，早年袁亚湘与孙文 瑜合作最优化理论与方法2一书中对其进行了详细的设计， 而后也有不少学 者对其进行研究。釷鹆資贏車贖孙滅獅赘。对于拟牛顿法的收敛性证明，时

19、平平在2008年其硕士论文关于无约束最 优化问题的拟牛顿算法研究 中详细的做了证明。怂阐譜鯪迳導嘯畫長凉。第1章最优化基础在这一章里我们首先简要介绍判断无约束最优化问题的最优解常用的最优 性条件，接着给出拟牛顿算法的概述，最后说明本文的主要工作.谚辞調担鈧谄动禪泻類。1.1无约束最优化问题的最优性条件最优化理论与方法是一门应用性很强的年轻学科，它研究某些数学上定义的 问题的最优解，即对于给出的实际问题，从众多的方案中找出最符合要求的最佳 方案在电子计算机的推动下，最优化理论与方法在经济计划、工程设计、生产 管理、交通运输等方面得到了广泛应用，成为一门十分活跃的学科.嘰觐詿缧铴嗫偽純铪锩。最优化

20、问题根据有无约束条件可分为约束和无约束最优化问题.现实生活中存 在的主要是有约束的问题，但我们可以通过某些处理将有约束的问题转化为无约 束的问题处理，并且无约束最优化问题的求解相对容易的多，而解法的基本思想又常常可以推广到一般有约束的情况，因此使得研究无约束最优化问题的计算方 法显得尤为重要，人们对它的研究情况也十分重视.熒绐譏钲鏌觶鷹緇機库。对于无约束问题min f (x), x Rn .(1.1 )的最优性条件可以分为一阶条件和二阶条件.设f(x)的一阶导数和二阶导数存在，且分别表示为g(x)二 '、f (xGd)八2 f(x),则我们有以下定理.定理1.1( 一阶必要条件)设f

21、: D Rn > R1寸R1在开集； D上连续可微。若X： D (1 . 0)的局部极小点，贝Ug(x*) =0.定理1.2(二阶必要条件)设f :Rn > R1在开集X* D上二阶连续可微，若x* D是(1 . O)的局部极小点，则g(x*) =O,G(x*) _0 .定理1.3(二阶充分条件)设f :Rn > R1在开集D上二阶连续可微，则x*D是f的一个严格局部极小点充分条件是g(x ) = 0， G(x*)是正定矩阵.满足g(x*)=O的点x*称为函数f的平稳点或驻点，一般目标函数的平稳点不定是极小点，但若目标函数是凸函数，则其平稳点就是其极小点，且为总体极小 占八、

22、定理1.4 (凸充分性定理)设f : D Rn > R1是凸函数，且 f C1。则x*是总体极小点的充分必要条件是g(x*) =0.1.2收敛概念收敛速度是迭代方法的又一重要性质。对于一个不可能在有限步内找到最优 解的最优化方法，我们不仅要求它收敛，还要要求它有较快的收敛速度，这是因 为一个收敛很慢的方法往往需要很长的时间才能得到满足精度要求的最优解的 近似。因而不是一个有效的方法。设向量序列x(k) Rn收敛于x*，定义误差序列鶼渍螻偉阅劍鲰腎邏蘞。(k)39如果存在常数C和r使成立就说序列x(k)以C为因子r阶收敛于x*。最常见的为r=1和r=2的情形，当 r =1，0 C ：1时称

23、为线性收敛，这是的误差序列具有以下性能:际呵e.1,如果C=0.5，则误差序列依最简单的情形，在上式中取等号，设初始误差为 为1，0.5，0.25，0.125, 0.0625，如果C =0.1，则误差序列为1，0.1，0.01，0.001,，可以看出C越小，收敛越快。如果从同一初始点开始，收敛快的算法可以用较少 的迭代次数达到预定的精度，而收敛慢的算法则需要较多的迭代次数才能得到相 同精度要求的点。 纣忧蔣氳頑莶驅藥悯骛。当r =1,C =0时，称序列X（k）超线性收敛于X*，超线性收敛是一种比线性收敛快的收敛，多数的最有化方法具有超线性收敛的特性，在上述收敛率的定义 中，所有r 1的收敛独属

24、于超线性收敛。事实上，由 颖刍莖峽饽亿顿裊赔泷。ek 1k_：:Xc-Jrkeee1-称r =2时的收敛为二次收敛，这时误差序列的性能可以用下述不等式表示2d 1 _C ek -二次收敛是一种更快的收敛，还要考察上式取等式时的情形，设初始误差为1，C =1,则误差序列为1，0.01，0.0001，0.00000001,，可以看到，二次收敛的方法每一次迭代近似解得精度就增加一倍 一个理想的算法终止准则为H.|l (k 十)v(k)|HX一x(k)*|llXx|-1然而由于X*是未知的，这样的准则并不具有任何实用价值。但是由于II (k_b*X-xX（宀-x（k）+x（k）-X*|(k)*II (

25、k)*|X-X卜_X|(k +)(k)(k)*|lX -x-Ilx 一X|II (k)*|HX一x|-0.在序列x(k)超线性收敛于x*时，我们可以得到(k(X上式表明对于一个超线性收敛的算法卜心-X畀|是|x(k)-X |的一个估计。因此对于超线性收敛速度的方法，(k 1)(k)X-X 八是一个比较合适的终止准则。1.3Wolfe准则和 Armijo准则Wolfe准则为f(xk akdQ 乞 f (xQ Skgldkg(Xk akdJTdk 一 丙®.其中,0：1。Armijo准则为：1给定：(0,1)， - (0,-)，- 0，设mk是使得下述不等式A：f (Xk + P%dk)

26、兰 f (Xk) + PP 叫g(xJTdk.( 1.2)成立的最小非负整数，令='叫。由于dk是下降方向，当m充分大时,不等式(1.2)总是成立的，因此上述mk总是存在的。由于mk是使得上述不等式成了的最小非负整数，因而:k不会太小，从而保证了目标函数f(x)的充分下降，令 C )= f(x : dk)。实际上，不等式 (1.2就是充分下降条 件濫驂膽閉驟羥闈詔寢賻。(k)(0) L k '(0).( 1.3)如果上式满足，则终止搜索，否则，我们可以缩小:k，或者在区间0, : k上用二次插值公式求近似极小点or(1.4 )厂4(0)魔a 一2(®k)®(

27、0)-叫O)Gk)将其作为一个新的:k 0第2章拟牛顿法算法设计2.1拟牛顿法条件考虑目标函数f(x)在当前点Xk处的二阶模型1mk(d) = f(xO+g：d+dTBkd .( 2.1.)其中，Bk是n n对称正定矩阵，是 Hesse近似，它将在每次迭代中进行校正。 极小化这个二次模型dk =-Bgk，( 2.2)从而新的迭代点为xk i 二 xk akdk 二 xk -akBkb .( 23)其中，ak是线性搜索步长因子，上述迭代(2.3)称为拟牛顿迭代，他与牛顿迭 代的主要区别在于在(2.3)中我们用Hesse近似Bk代替了牛顿迭代中的 Hesse 矩阵Gk o銚銻縵哜鳗鸿锓謎諏涼。设f

28、 : Rn > R在开集D Rn商二次连续可微，f (x)在xk .1附近的二次近似 为f(X)f(Xk 1)g：1(x-Xk 1) 1 t( 2.4)(x - Xk 1) Gk 1(x -Xk J2对上式两边求导，有g(x) : gk 1 Gk1(x-Xk 1) ，(2.5)令Sk二 Xk 1 -Xk, yk 二gk 1-gk(2.6)(2.6)成为Gk 何yk .(2.7)显然，如果f（x）是正定二次函数，上述关系式（2.7）精确成立。现在，我们要 求在拟牛顿法中构造出来的 Hesse近似Bk 1满足这种关系，从而得到 挤貼綬电麥结鈺（2.8）贖哓类。Bk 1Sk = yk上式称为拟

29、牛顿条件或拟牛顿方法。利用拟牛顿条件，我们可以得到BkSkSk BkSk Bk SkT yk yk Bk 1 = BkT_yk Sk上述公式成为BFGS校正公式（关于Bk）如果令Hk =Bk，则拟牛顿条件为Hk 必二 Sk，（ 2.9）拟牛顿迭代为Xk 1 二akkdk 二 Xk -akBkgk（2.10）或xk 1 = xk akdk = xk -akBk gk .（2.11）拟牛顿条件使二次模型具有如下插值性质：如果Bk 1满足拟牛顿条件（2.8），那么在Xk卅点的二次模型mk 1（x） = f（Xk J g：1（x-Xk1）1 t（ 2.12）（x - Xk J Bk 1（x-Xk J2

30、满足mk 1（Xk 1）= f（Xk J' mk 1（Xk 1） = gkmk（Xk）二 gk.（2.13）上式中的第一、第二等式是显然的，第三个等式是利用拟牛顿条件（2.8）得到的。2.2算法设计步 1.给出初始点 X。 Rn，Bo （或 H0）- Rn n，:0,k =0。步2如果Igk ；，停止。步3解Bkd二gk，得搜索方向dk;（或计算dk二-HkgQ。步4.由wolfe准则步长因子ak，并令xk d = xk - akdk。步5是用BFGS校正公式校正Bk产生的（或校正Hk产生的H）,使得拟 牛顿条件（2.8）或（2.9）成立。步6.k k 1，转步2。第3章收敛性证明3.

31、1总体收敛设x0是任意初始点，B0是对称正定矩阵的初始Hesse近似。假设3.1(a) f :Rn > R1在开凸集D Rn上二次可微；(b) 水平集0 =xe Rn f(x)兰f(x0)是凸的，存在正的常数 m和M使得Hesse矩阵G(x)满足2 2m ZztG(x)zM z ，一z Rn,xw ：. .(3.1)(c) 在x*的领域N(x*,；)内，G(x)是Lipschitz连续的，即|g(x)G(x)| 兰 L x-耳,Wx,xE N(x , e) .(3.2)上述假设条件(b)意味着Hesse矩阵G(x)式门上是正定的，f有唯一的极 小点x*。由Taylor定理，1g(Xk s

32、j 二 g(Xk) 0G(Xk sjd ,令1 1Gk = .0G(Xksjd =.0G(Xkakdjd，( 3.3)则yk 二 gk 1 gk 二 GkSk .(3.4)于是，利用(3.1)和(3.4)，有卒二-m .( 3.5)sk sksk sk1令 Zk - Gk 2sk，则Tyk SkSk 2*GkZk(3.6)注意矩阵A的迹trace (A)是A的对角元的和，也是 A的特征值的和，即nntrace(A)=、 a”，trace( A) _、；i£7(3.7)矩阵的行列式det (A)是A的特征值的乘积，即nd etAO ： | 丨；7(3.8)在下面的证明中，我们利用了这两

33、个概念来估计 Hesse近似的最大和最小特 征值的大小。定理3.2 设B。是任意初始对称正定矩阵，X。是初始点，使得假设3.1( a)(b)成立，则由算法3.1产生的序列xk收敛到f的极小点x* 。赔荊紳谘侖驟辽輩袜錈。证明 定义TykSk mk -Sk SkmkTyk ykTykSk(3.9)由(3.5)和(3.6)得(3.10)T由BFGS校正Bki二Bk 毕YkSkBkykykASk BkSk计算其迹和行列式，得T r a CBk -i) =T r a CQ _|BkSkJ|yk|Sk BkSkyk Sk(3.11)mk _ m， M k _ M .T(3.12)detBU "

34、etBU-Sk BkSk定义S _ Sk Bk SkCoSkCqkS BkSkT ，Sk Sk(3.13)这里A是Sk和BkSk之间的夹角，于是IBkskl2l|Bksk|sk|sk BkskqkT'Sk B.s.(sk Bk sk )|scok(3.14)又由(3.12) 和( 3.9),有TT(3.15)detBU "etBk)华 普detBk) .sk sk sk Bkskqk现在我们定义(3.16)' (B)二Trace(B) -1 n(det(B).其中ln(*)表示自然对数。不难证明,'(B) 0。由(3.16), (3.12) (3.15),(B

35、kJ =TraCBk1) -ln(det(Bk)二T r a CBJ M kqkCOS2 vk-ln( det(Bk)-l ng lnqk(3.17)=' (Bk) (Mk -lnmk -1)1-2 ln2 lncoBk cos 日kcos 日k注意到对所有的t 0，h(t)=1-t lntO,上面方括号中的项是非正的，因而由(3.10),并反复利用(3.17), 得塤礙籟馐决穩賽釙冊庫。k0 八(Bk 1) r (BJ ck 、Tncosj ,(3.18)jm其中 c = M -ln m -10。下面，我们利用Wolfe不精确线性搜索的总体收敛性定理证明结果。由于 Sk =akBgk

36、, BkSk =akgk，故 skks. = kafglBjgk =-akgkdk，这表 明由(3.13)定义的玉也是最速下降方向-gk和拟牛顿搜索方向d-Bgk之间 的夹角。于是，由于Wolfe不精确线性搜索的总体收敛性定理得 裊樣祕廬廂颤谚鍘芈蔺。gk cosk > 0 .(3.19)为了证明lim inf gk =0，只要证明存在子序列kj，使得cosj-0假定coj > 0。则存在k1 0，使得对所有j k1，有(3.20)In c 0站：-2c.其中c = M -Inm 一1 .0是上面定义的常数。利用(3.18)得到:对所有k k,kik0 八(B) kc 'T

37、ncos2 j、 (_2c)j 土i 卅,、k( 3.21)2=(Bi) -二 Incosj 2kiC-kc.j4在(3.17 )中，第一项和第三项是正的，但有限，第二项小于零，第四项也小于零，且与k有关，故当k充分大时，上式右边是负的，从而给出矛盾。仓嫗盤紲嘱珑詁鍬齊驚。(3.22)这矛盾表明存在子序列kJ，使得cosj _ 0，从而Lmnfg=0 .由假设3.1 (b),问题是强凸的，这表明XkT x*上述定理证明了：采用Wolfe不精确线性搜索的BFGS拟牛顿算法是总体收 敛的。这个结果可推广到所有 0,1)的Broyden族，即不包括DFP校正。绽萬璉轆娛閬蛏鬮绾瀧。下面，我们研究BF

38、GS方法的局部超线性收敛。首先我们给出拟牛顿法超线 性收敛的充分必要条件。3.2局部超线性收敛定理3.3 设f : Rn，R，满足假设3.1 (a) (b)成立。考虑迭代xk厂xk dk，dk =Bgk。设 Xk收敛到解点x*。则当且仅当讪冒浮=0.宀dk(3.23)时，序列 xk超线性收敛到x证明 设拟牛顿步为dk =-Bgk，牛顿步为=-Ggk，由于G(x*)是正定 的，故当Xk充分靠近x*时，Gk4是上有界的。我们先证明(3.23)等价于dk -d" =o(dk ) .(3.24)假定（3.1）成立，则(3.25)dk dk =GiT(Gkdk gk) 二Gk'(Gk

39、-Bk)dk=0( G -BJdk )=o( dk ).最后一个等式来自（3.23）反之，设（3.24）成立，则由Gk左乘以（3.24）两边，得Gkdk -Gkdo（dk）.（3.26）注意到-Gkd, =gk 二-Bkdk，从而（2.2.44）成为G-BJdk=o（|dk|）.此即（3.23）。下面，借助牛顿发的二次收敛性结果来完成证明。|dk|xk - / 乞 Xk dk x*乞 Xk dN -x*- dk d,=0（ Xk -x*| ） o dk."3.27）从上式易知|dk| =O（|xk -x*|），代入（3.27），得到IX十-x*| =|xk +dk -x*| =o|x

40、k -x*|这表明Xk是超线性收敛的。这个定理告诉我们三点：（1）超线性收敛的充要条件使（3.23）成立，即Bk只要沿搜索方向dk收敛到 Hesse矩阵G（x*），则拟牛顿法超线性收敛。骁顾燁鶚巯瀆蕪領鲡赙。（2）（3.24）也是拟牛顿法超线性收敛的充要条件，即当且仅当拟牛顿步dk在长度和方向上都趋向于牛顿步dN，则拟牛顿法超线性收敛。瑣钋濺暧惲锟缟馭篩凉。如果将（3.23）用“m害凹 j lldd代替，定理仍然成立。这个定理是基本的和一般的，当我们讨论每个具体的拟牛顿法的超线性收敛性时，都要验证充要条件(3.23)。鎦诗涇艳损楼紲鯗餳類。定理3.4设f : R“ ； Rn，满足Xk 1 =

41、Xk - bJ f (Xk)，设Bk是非奇异矩阵序列。假定对某个D，由Xk 1 = Xk - akBk f (xk)，( 3.28)产生的序列Xk都在D中且收敛到X*。如果(2.23)成立，那么Xk超线性 收敛到X*且f (x*) =0的充要条件是ak收敛到1.证明 先假定 Xk超线性收敛到X*且f (x*) = 0。必有意- 1)Bk(Xk 1Hklimk_.aEf(x*) Xk) =0 ,Xk 1 -Xk|(3.29) Xk ) / Xk 卅一 X=0.由于Bk(Xk彳-兀)=-ak f(Xk)，故上式可写成km(a： -1)f 区)|/収心-X=0 .(3.30)由于f '(x*

42、)非奇异。故存在:0，使得f(xj 一 ： Xk-x*，又因 Xk超线 性收敛。又有m_-Xk卞-xk / xk -x* =1，从而有(3.2.23)得ak收敛到1.下面我们进一步阐述拟牛顿法超线性收敛的几何意义。设Sk =兀4 - Xk，又该序列的牛顿校正为 S = -f (xk)J * f (xk)。由于 f (Xk)二-BkSk，则Sk=Sk f'(Xk)4f (Xk)二 f'(Xk)"f'(Xk) - Bk)Sk.因此lim:二0等价于Bk - f(X )( Xk 1 -Xk)Xk 1 _Xkl(3.31)上式表明当 Xk 超线性收敛时，Q作为sN的近

43、似向量，其对称误差应趋于零。容易证明这等价于要求Sk无论在长度上还是方向上都趋向于 £。为此，我 们建立以下弓I理。栉缏歐锄棗鈕种鵑瑶锬。引理 3.5 设u , v e Rn , u , v 护0且口乏（0,1）。如果|u - 寸"|u|，则u ,v 为正且(3.32)反之，如果u,v为正且（3.32）成立，则u -v|3 |u .(3.33)证明首先假设|u - v _ U，则于是（3.32）中第一个不等式成立。记 =u,v/（|u|v），注意到u-v2-2u vv2_u2（1- ）这证明了（ 3.32）中第二个不等式。此外，若 0，则由上面的等式部分可知u-v“|u，从

44、而篇汽1。因此，若爲”1，则必有VU ,v 为正。辔烨棟剛殓攬瑤丽阄应。反之，若u,v为正且（3.32）成立，则|u-v|2=（|uHM）2+2（i）MM "2忖21+2（1*）由于:-1，故得（3.33）。由这个引理可得，若（）成立，即对任意给定的（0,1），当kko时,NSk Sk根据引理3.5，应有c sk,Sk »0且当k>k）时有sN和N31( -Sk, Sk、2 .2Sk sN|)这表明(3.31)等价于鬧| .Sk sNlimlimN - 1.(3.34)k>：SkSk |sN从而我们有结论：拟牛顿法超线性收敛的充分必要条件是其位移 Sk在长度和方

45、向上都渐进的趋向于牛顿方向SkN。定理3.6设f : Rj R满足假设条件3.1中的（a）和（b）,又设Bk为一 非奇异矩阵序列。假定对某X。，D，迭代序列Xki二Xk-akBk'gk产生的xk都在 D中且xk = x* （-k _0）。又设该序列收敛到x*。 ak由不精确线性搜索 Wolfe准则 |Bk -灯2f（x*）sJ产生，若lim j1 =0成立，则当k充分大时，ak =1，从而序列XkY|Sk超线性收敛至U x*。峴扬爛滾澗辐滠兴渙藺。证明 本定理要证明对于一切充分大的 k，Wolfe准则成立，从而ak =1，余下的结果直接从定理3.3得到。由于Bksk二-akgk故由li

46、m.Bkf(x*)SkSki=0可彳得詩叁撻訥烬忧毀厉鋨骜。所以gjBFgk -(Bkpk八 2f (x*)(BFgQ2* d T = (gk -' f (x )Bk gk) (Bk gk)=o( Bk1 g)glBFk =做©円2心*）何©）+0（|浄山）.（3.35）由于i 2f（x*）正定，故存在0，使得对于充分大的k,gkAFk B,gk【成立，从而有泰勒展式和（2.12）有心-Bk'gQ-f-gWgk 扣如七（皿如(3.36)乞-呵：Bgk其中；位于xk与Xk-Bkgk之间。又由泰勒展式可得g(Xk -BkgQT B/gk -glBfgk (Bgk

47、)T' 2f (x*)(BgQ=0( Bk gk )利用(3.36)，有1 T _1II _12t _1g(XkBkgQ Bkgk=o(|Bkgk )"gkBkgk(3.37)g(x -Bk4gk)TBk4g rgk'Bk'g由(3.36)和(3.37)可知 f(xk _Bk gk) ' f(xk)gkBk gk成立，从而对于充分大的k， ak =1第4章数值验算这里将给出6个例题用以验算算法的的可行性。在迭代过程中Armijo准则中的参数= 0.4，匸=0.6。6个例题的数值结果将列表记录。从这些结果中我们可以看到算法的可行性和有效性。则鯤愜韋瘓賈晖

48、园栋泷4.1问题模型问题1yi 二1.5 -咅(1 - x2)2讨2 二 2.25 - x(1 - X?)?2y3 2.625 -片(1 - x?)22 2min y 二 y1y2y3x R初始迭代点为Xo=1,1问题22 2 2min y = 100(X2 - 为)(1 - xj初始迭代点为x°=-1.2 ,1问题30.10-0.1x,丄q1x,-(e1-5e七e4)比=x3e 1 _ x4e 2 x6 e-0.2x1亠-0.2 x,丄亠-0.2x5-(ed2-5e2 七e8)y2 二花 e 1 _ % e 2x6e 5ye0.3x x ” e_0.3x'x ” e&quo

49、t;0.%5 "“3 不3 32)-0.4x-0.4x0.4x (e-0.4 -5e4 "3e丄6)y4 = x3e- x4e 灼e5-0.5x1亠-0.5程 丄亠-0.5x5-(ed'-ge5 七e2)y5 = x3e_ x4 exey6_0.6x1=x3 e _0.6x,-xe 骨x6 e_0.7为-0.7 x2y7=沧 e-x4ex6 e_0.8x1-0.8x2y二 X3e- ex6 e_0.9 X1亠.0.9x2y9* - e7 ex6 e_Q.6x5_(e26_5e6 3eZ4).0.8x5 _(e-.8 _5e8 3e22)_Q.7x5 _(e27 _5

50、e7 3e-2.8)_0.9x5 _(e-.9 _5e；3e-.6)y10 =E * e_x4 * e2+x6 * e仝-书e)yn n d"乜飞叫飞上化心®14）yi2_1.2Xi_1.2x2=x3e 1 - x4 e 2_1.2 x5 4e -12 _5e12 书e 48) x6eA.3x14.3x2,_1.3x -(3 -5e13 H3e -5;2 )%3 =X3e - X4e冷 e2丄 2丄 2丄 2丄 2丄丄 2丄 2丄 2min y 二 y1 N2纸牡 yn%2丫13 初始迭代点为x°=1,2,1,1,1,1(3.5 -O2(丄2 (33) 2问题4y

51、12二 x1e2-0.00092y2 = x1e-0.0044(7(2.5 玉)2（丄2 （2 丄3）2y32=x1e2-0.01752y4 二"2-0.0540(心(1.5 丄3) 2(丄2(13) 2y52二 xe2-0.12952y6 ="-0.2420 (0.5 丄3)2（火（03）2y72=x1e2-0.35212讨8 二"2-0.3989（和q5亠）2（丄2（f ）2y9=X1e2-0.3521ye = X1e2-0.2420(»2( 4.5 知)：2(»2( “3)2yn2-x1e2-0.12952%2 工 X©2-0.

52、0540(-2 ( 2.5 丄3 )2(f 3)2y132-x1e2-0.01752%4 二"2-0.0044(-2 ( 3.5 心3 ) 2y1x1e2- 0.00092 +2.2 +2 +2.2土 2+2miny1y2y3y4y5y6y7y82 2 2 2 2 2 2*y10yn%2%3%4%5初始迭代点x0=0.4,1,0问题 5y1 =10(石-X；)y2 =1 F* =3,10(X4 -xf)y4 = 1 - X3y 10(x2 X4 -2)丫6 =丄卜2 - X4),10min y = y： y； yf y： yj y：初始迭代点为 Xo =-3,-1,-3,-119问题6min y =(3 -2Xn)Xn -Xn1 ' (3 - 2Xn)Xn - Xn/ - 2Xn 1 1)n：4初始迭代点位 Xo=1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,14.