本科毕业论文-—无约束最优化问题的拟牛顿法.doc

《本科毕业论文-—无约束最优化问题的拟牛顿法.doc》由会员分享，可在线阅读，更多相关《本科毕业论文-—无约束最优化问题的拟牛顿法.doc（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、签名：日期： 年 月 日导师签名： 日期： 年 月 日指导教师评阅书指导教师评价：一、撰写（设计）过程1、学生在论文（设计）过程中的治学态度、工作精神 优 良 中 及格 不及格2、学生掌握专业知识、技能的扎实程度 优 良 中 及格 不及格3、学生综合运用所学知识和专业技能分析和解决问题的能力 优 良 中 及格 不及格4、研究方法的科学性；技术线路的可行性；设计方案的合理性 优 良 中 及格 不及格5、完成毕业论文（设计）期间的出勤情况 优 良 中 及格 不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及

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

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

7、设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格评定成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）教研室主任（或答辩小组组长）： （签名）年 月 日教学系意见：系主任： （签名）年 月 日毕业设计（论文）任务书 题目： 无约束优化问题的拟牛顿法 姓名 xx 院（系）

8、 xx 专业 信息与计算科学 班级 xx 学号 xx指导老师 xx 职称 讲师 教研室主任 xx 一、 基本任务及要求： 1基本任务： 在牛顿法基础上提出拟牛顿法，设计拟牛顿法的算法，了解拟牛顿法的优点及用途。在一定的条件下证明该算法的合理性并对其收敛性进行分析。讨论算法的收敛速度 ，通过数值试验对算法的有效性进行验证。 2基本要求： 对拟牛顿法给出合理的算法；利用理论知识对算法合理性进行证明 对其收敛性以及收敛速度 进行分析证明。写出毕业设计说明书，完成全部研究工作和毕业论文。 二、 进度安排及完成时间： 第一阶段 (第14周) ：进行调研，查阅相关资料，撰写开题报告，并于第4周星期五 交开

9、题报告； 第二阶段 (第512周): 在指导教师的指导下，对课题进行研究，按预定要求获得毕业 论文开题报告中的预期结果（即进行算法设计，研究算法的合理性，实现算法 等工作），并撰写毕业论文，第12周五之前交初稿； 第三阶段 (第1314周): 指导教师对毕业论文进行批阅，提出修改意见并指导学生进行 毕业论文的修改,并检查算法的实现情况（如程序的可行性和通用性等）； 第四阶段 (第15周): 指导教师指导学生将毕业论文定稿，并准备毕业论文答辩； 第五阶段 (第16周): 进行毕业论文答辩。 目 录摘 要1前 言2第1章 最优化基础41.1 无约束最优化问题的最优性条件41.2 收敛概念51.3

10、Wolfe准则和Armijo准则7第2章 拟牛顿法算法设计92.1 拟牛顿法条件92.2 算法设计11第3章 收敛性证明123.1 总体收敛123.2 局部超线性收敛16第4章 数值验算214.1 问题模型214.2 数值结果23总 结24致 谢25参考文献26附 录27无约束最优化问题的拟牛顿法摘要：拟牛顿法是求解无约束最优化问题最常用的方法之一，拟牛顿法是在牛顿法的基础上提出来的。牛顿法成功的关键是利用了Hesse矩阵提供的曲率信息,但计算Hesse矩阵工作量大，并且有的目标函数的Hesse矩阵很难计算，甚至不好求出。拟牛顿法通过函数的一阶导数构造出曲率的近似,从而避免了求函数的Hesse

11、矩阵,不需要求函数的二阶导数,从而大大的减小了计算的复杂度。同时拟牛顿法还具有超线性收敛以及收敛速度快的优点。拟牛顿算法在求解无约束优化问题中占有不可取代的地位。同时也是很多学者研究的课题。本论文将依靠前人的基础,对拟牛顿法进行介绍并对其收敛性进行证明,同时给出数值分析。关键词：拟牛顿法，无约束优化，收敛性。 A quasi-newton method for Unconstrained optimization Abstract:Newton method is to solving unconstrained optimization problem of one of the most

12、commonly used methods.Quasi-newton method is in Newton put forward on the basis of law.Newton method the key to success is the use of the Hesse matrix the curvature of the information but provide Hesse matrix calculation workload is big, and some of the objective function Hesse matrix is difficult t

13、o calculate, even bad work out.Quasi-newton method through the first derivative constructed out of the curvature approximate avoid a for the Hesse matrix couldnt ask the second order derivatives.Thus greatly reduced the complexity of the calculation and quasi-newton method also has superlinear conve

14、rgence and convergence speed advantages quasi-newton algorithms in solving unconstrained optimization has irreplaceable position in also many scholars research project of this paper will be depend on the basis of predecessors to be Newton method and the convergence proof and presents numerical analy

15、sis.Key words:Quasi-newton,Unconstrained optimization ,Convergence1前 言 最优化方法是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、

16、工程建设、国防等各个领域，发挥着越来越重要的作用。本章将介绍最优化方法的研究对象、特点，以及最优化方法模型的建立和模型的分析、求解、应用。主要是线性规划问题的模型、求解（线性规划问题的单纯形解法）及其应用运输问题；以及动态规划的模型、求解、应用资源分配问题。 无约束优化问题是最优化问题的基础，是数值计算领域中十分活跃的研究课题之一，历时较长，获得的成果也较多，有关的方法和理论比较成熟。其中非线性无约束最优化方法在科学计算和工程分析中起着越来越重要的作用。牛顿法作为求解最优化问题最有效的方法之一。它的基本思想是利用目标函数的二次泰勒展开，并将其极小化。在非线性无约束最优化问题中，对于正定的二次函

17、数，牛顿法一步即可达到最优解。对于非二次函数，牛顿法并不能保证经有限次迭代求得最优解，但由于目标函数在极小点附近似于二次函数，故当初始点靠近极小点时，牛顿法的收敛速度一般是很快的，因此这种方法得到了很多人的认可与利用。但牛顿法中每次迭代都需要计算Hessian矩阵，但计算Hessian矩阵工作量大，并且有的很难计算，甚至不好求，而以拟牛顿方程为基础构造的拟牛顿算法克服了牛顿法的这一不足。因此拟牛顿法被广泛的认可，她的应用相当广泛。可以剞劂很多问题。并有很多人多拟牛顿法做了研究。 对于拟牛顿法的算法设计，也已经有不少学者提出过，早年袁亚湘与孙文瑜合作最优化理论与方法一书中对其进行了详细的设计，而

18、后也有不少学者对其进行研究。 对于拟牛顿法的收敛性证明，时平平在2008年其硕士论文关于无约束最优化问题的拟牛顿算法研究中详细的做了证明。第1章 最优化基础 在这一章里我们首先简要介绍判断无约束最优化问题的最优解常用的最优性条件，接着给出拟牛顿算法的概述，最后说明本文的主要工作1.1无约束最优化问题的最优性条件 最优化理论与方法是一门应用性很强的年轻学科，它研究某些数学上定义的问题的最优解，即对于给出的实际问题，从众多的方案中找出最符合要求的最佳方案在电子计算机的推动下，最优化理论与方法在经济计划、工程设计、生产管理、交通运输等方面得到了广泛应用，成为一门十分活跃的学科最优化问题根据有无约束条

19、件可分为约束和无约束最优化问题现实生活中存在的主要是有约束的问题，但我们可以通过某些处理将有约束的问题转化为无约束的问题处理，并且无约束最优化问题的求解相对容易的多，而解法的基本思想又常常可以推广到一般有约束的情况，因此使得研究无约束最优化问题的计算方法显得尤为重要，人们对它的研究情况也十分重视 对于无约束问题, . （1.1）的最优性条件可以分为一阶条件和二阶条件设的一阶导数和二阶导数存在，且分别表示为 ,则我们有以下定理定理1.1(一阶必要条件)设：寸R1在开集上连续可微。若(10)的局部极小点，则 .定理1.2(二阶必要条件)设：在开集上二阶连续可微，若是(1O)的局部极小点，则 .定理

20、1.3(二阶充分条件)设：在开集D上二阶连续可微，则是的一个严格局部极小点充分条件是 ，是正定矩阵. 满足的点称为函数的平稳点或驻点，一般目标函数的平稳点不定是极小点，但若目标函数是凸函数，则其平稳点就是其极小点，且为总体极小点定理1.4(凸充分性定理)设：是凸函数，且 。则是总体极小点的充分必要条件是 .1.2收敛概念 收敛速度是迭代方法的又一重要性质。对于一个不可能在有限步内找到最优解的最优化方法，我们不仅要求它收敛，还要要求它有较快的收敛速度，这是因为一个收敛很慢的方法往往需要很长的时间才能得到满足精度要求的最优解的近似。因而不是一个有效的方法。设向量序列收敛于，定义误差序列 ,如果存在

21、常数和使成立 .就说序列以为因子阶收敛于。最常见的为和的情形，当，时称为线性收敛，这是的误差序列具有以下性能： .依最简单的情形，在上式中取等号，设初始误差为1，如果=0.5，则误差序列为 1，0.5，0.25，0.125，0.0625，如果，则误差序列为 1，0.1，0.01，0.001，可以看出越小，收敛越快。如果从同一初始点开始，收敛快的算法可以用较少的迭代次数达到预定的精度，而收敛慢的算法则需要较多的迭代次数才能得到相同精度要求的点。 当时，称序列超线性收敛于，超线性收敛是一种比线性收敛快的收敛，多数的最有化方法具有超线性收敛的特性，在上述收敛率的定义中，所有的收敛独属于超线性收敛。事

22、实上，由 ,有 . 称时的收敛为二次收敛，这时误差序列的性能可以用下述不等式表示 .二次收敛是一种更快的收敛，还要考察上式取等式时的情形，设初始误差为1，则误差序列为 1，0.01，0.0001，0.00000001，可以看到，二次收敛的方法每一次迭代近似解得精度就增加一倍。 一个理想的算法终止准则为 .然而由于是未知的，这样的准则并不具有任何实用价值。但是由于 在序列超线性收敛于时，我们可以得到 .上式表明对于一个超线性收敛的算法是的一个估计。因此对于超线性收敛速度的方法， .是一个比较合适的终止准则。1.3Wolfe准则和Armijo准则Wolfe准则为 .其中，。Armijo准则为： 给

23、定，设是使得下述不等式A： . （1.2） 成立的最小非负整数，令。由于是下降方向，当m充分大时，不等式(1.2)总是成立的，因此上述总是存在的。由于是使得上述不等式成了的最小非负整数，因而不会太小，从而保证了目标函数的充分下降，令。实际上，不等式(1.2就是充分下降条件 . （1.3） 如果上式满足，则终止搜索，否则，我们可以缩小，或者在区间0,上用二次插值公式求近似极小点 . （1.4） 将其作为一个新的。第2章 拟牛顿法算法设计2.1 拟牛顿法条件 考虑目标函数在当前点处的二阶模型 . （2.1.）其中，是对称正定矩阵，是Hesse近似，它将在每次迭代中进行校正。极小化这个二次模型 ，

24、（2.2） 从而新的迭代点为 . （2.3）其中，是线性搜索步长因子，上述迭代（2.3）称为拟牛顿迭代，他与牛顿迭代的主要区别在于在（2.3）中我们用Hesse近似代替了牛顿迭代中的Hesse矩阵。 设：在开集商二次连续可微，在附近的二次近似为 （2.4）对上式两边求导，有 ， （2.5）令 （2.6）（2.6）成为 . （2.7）显然，如果是正定二次函数，上述关系式（2.7）精确成立。现在，我们要求在拟牛顿法中构造出来的Hesse近似满足这种关系，从而得到 . （2.8）上式称为拟牛顿条件或拟牛顿方法。利用拟牛顿条件，我们可以得到 .上述公式成为BFGS校正公式（关于）如果令，则拟牛顿条件为

25、 ， （2.9）拟牛顿迭代为 （2.10）或 . （2.11） 拟牛顿条件使二次模型具有如下插值性质：如果满足拟牛顿条件（2.8），那么在点的二次模型 （2.12）满足 . （2.13）上式中的第一、第二等式是显然的，第三个等式是利用拟牛顿条件（2.8）得到的。2.2算法设计步1.给出初始点，（或），。步2.如果，停止。步3.解，得搜索方向；（或计算）。步4.由wolfe准则步长因子，并令。步5.是用BFGS校正公式校正产生的（或校正产生的），使得拟牛顿条件（2.8）或（2.9）成立。步6.，转步2。 第3章 收敛性证明3.1总体收敛 设是任意初始点，是对称正定矩阵的初始Hesse近似。 假设

26、3.1 （a）在开凸集上二次可微； (b）水平集是凸的，存在正的常数m和M使得Hesse矩阵满足 . （3.1） (c）在的领域内，是Lipschitz连续的，即 . （3.2） 上述假设条件（b）意味着Hesse矩阵式上是正定的，有唯一的极小点。由Taylor定理， ,令 ， （3.3）则 . （3.4）于是，利用（3.1）和(3.4)，有 . （3.5）令，则 . （3.6）注意矩阵A的迹trace（A）是A的对角元的和，也是A的特征值的和，即 （3.7）矩阵的行列式det（A）是A的特征值的乘积，即 . (3.8)在下面的证明中，我们利用了这两个概念来估计Hesse近似的最大和最小特征值

27、的大小。定理3.2 设是任意初始对称正定矩阵，是初始点，使得假设3.1（a）（b）成立，则由算法3.1产生的序列收敛到的极小点。证明 定义 ， . （3.9）由（3.5）和（3.6)得 ， . （3.10）由BFGS校正，计算其迹和行列式，得 （3.11）和 . （3.12） 定义 ， （3.13）这里是和之间的夹角，于是 . （3.14）又由（3.12）和（3.9），有 . （3.15）现在我们定义 . （3.16）其中表示自然对数。不难证明，。由（3.16），（3.12）（3.15），得 . （3.17） 注意到对所有的，上面方括号中的项是非正的，因而由（3.10）,并反复利用（3.17）

28、，得 ， （3.18）其中。下面，我们利用Wolfe不精确线性搜索的总体收敛性定理证明结果。由于，故，这表明由（3.13）定义的也是最速下降方向和拟牛顿搜索方向之间的夹角。于是，由于Wolfe不精确线性搜索的总体收敛性定理得 . （3.19）为了证明 ，只要证明存在子序列，使得。假定。则存在，使得对所有，有 . （3.20）其中是上面定义的常数。利用（3.18）得到:对所有， （3.21）在（3.17）中，第一项和第三项是正的，但有限，第二项小于零，第四项也小于零，且与k有关，故当k充分大时，上式右边是负的，从而给出矛盾。这矛盾表明存在子序列，使得，从而 . （3.22）由假设3.1（b），问

29、题是强凸的，这表明。上述定理证明了：采用Wolfe不精确线性搜索的BFGS拟牛顿算法是总体收敛的。这个结果可推广到所有的Broyden族，即不包括DFP校正。下面，我们研究BFGS方法的局部超线性收敛。首先我们给出拟牛顿法超线性收敛的充分必要条件。3.2 局部超线性收敛定理3.3 设：，满足假设3.1 (a) (b)成立。考虑迭代，。设收敛到解点。则当且仅当 . （3.23）时，序列超线性收敛到。证明 设拟牛顿步为，牛顿步为，由于是正定的，故当充分靠近时，是上有界的。我们先证明（3.23）等价于 . （3.24）假定（3.1）成立，则 (3.25)最后一个等式来自（3.23）反之，设（3.24

30、）成立，则由左乘以（3.24）两边，得 . （3.26）注意到，从而（2.2.44）成为 .此即（3.23）。 下面，借助牛顿发的二次收敛性结果来完成证明。 . （3.27）从上式易知 ，代入（3.27），得到 这表明是超线性收敛的。这个定理告诉我们三点： (1) 超线性收敛的充要条件使（3.23）成立，即只要沿搜索方向收敛到Hesse矩阵，则拟牛顿法超线性收敛。 (2)（3.24）也是拟牛顿法超线性收敛的充要条件，即当且仅当拟牛顿步在长度和方向上都趋向于牛顿步，则拟牛顿法超线性收敛。 (3)如果将（3.23）用 代替，定理仍然成立。这个定理是基本的和一般的，当我们讨论每个具体的拟牛顿法的超线

31、性收敛性时，都要验证充要条件（3.23）。定理3.4设：，满足，设是非奇异矩阵序列。假定对某个，由 , （3.28）产生的序列都在D中且收敛到。如果（2.23）成立，那么超线性收敛到且的充要条件是收敛到1.证明 先假定超线性收敛到且。必有 ， (3.29)意味着 .由于，故上式可写成 . （3.30）由于非奇异。故存在，使得，又因超线性收敛。又有，从而有（3.2.23）得收敛到1.下面我们进一步阐述拟牛顿法超线性收敛的几何意义。 设，又该序列的牛顿校正为。由于，则 .因此等价于 . （3.31）上式表明当超线性收敛时，作为的近似向量，其对称误差应趋于零。容易证明这等价于要求无论在长度上还是方向

32、上都趋向于。为此，我们建立以下引理。引理3.5 设，且（0，1）。如果，则为正且 ， （3.32）反之，如果为正且(3.32)成立，则 . （3.33）证明 首先假设 ，则 ，于是（3.32）中第一个不等式成立。记，注意到 .这证明了（3.32）中第二个不等式。此外，若，则由上面的等式部分可知，从而。因此，若，则必有为正。反之，若为正且（3.32）成立，则 .由于，故得（3.33）。由这个引理可得，若（）成立，即对任意给定的，当时， .根据引理3.5，应有且当时有 和 3.这表明（3.31）等价于 . （3.34）从而我们有结论：拟牛顿法超线性收敛的充分必要条件是其位移在长度和方向上都渐进的趋

33、向于牛顿方向。定理3.6 设：满足假设条件3.1中的（a）和（b），又设为一非奇异矩阵序列。假定对某，迭代序列产生的都在D中且。又设该序列收敛到。由不精确线性搜索Wolfe准则产生，若成立，则当k充分大时，从而序列超线性收敛到。 证明 本定理要证明对于一切充分大的k，Wolfe准则成立，从而，余下的结果直接从定理3.3得到。由于故由可得 . 所以 .即 . （3.35）由于正定，故存在，使得对于充分大的k， .成立，从而有泰勒展式和（2.12）有 （3.36）其中位于与之间。又由泰勒展式可得利用（3.36），有. （3.37）由（3.36）和（3.37）可知成立，从而对于充分大的k，。 第4章 数值验算 这里将给出6个例题用以验算算法的的可行性。在迭代过程中Armijo准则中的参数，。6个例题的数值结果将列表记录。从这些结果中我们可以看到算法的可行性和有效性。4.1问题模型 问题1 初始迭代点为=1,1 问题2 初始迭代点为=-1.2 ,1 问题3 初始迭代点为=1,2,1,1,1,1 问题4