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

《毕业论文无约束最优化问题的拟牛顿法.doc》由会员分享，可在线阅读，更多相关《毕业论文无约束最优化问题的拟牛顿法.doc（31页珍藏版）》请在三一办公上搜索。

1、 毕 业 论 文题 目： 无约束最优化问题的拟牛顿法 院 （系）： 理学院 专业：信息与计算科学班级：xxx学号：xxxxxx学生姓名： xxx 导师姓名： xxx 完成日期： 2012年5月30 日 诚 信 声 明本人声明：1、本人所呈交的毕业设计（论文）是在老师指导下进行的研究工作及取得的研究成果；2、据查证，除了文中特别加以标注和致谢的地方外，毕业设计（论文）中不包含其他人已经公开发表过的研究成果，也不包含为获得其他教育机构的学位而使用过的材料；3、我承诺，本人提交的毕业设计（论文）中的所有内容均真实、可信。作者签名： 日期： 年 月 日毕业设计（论文）任务书 题目： 无约束优化问题的拟

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

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

4、41.2 收敛概念51.3 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矩阵很难计算，甚至不好求出。拟牛顿法通过函数的一阶导数构造出曲率的近似,

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

6、e of the most 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

7、is difficult to 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 sup

8、erlinear convergence 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 n

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

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

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

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

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

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

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

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

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

18、。极小化这个二次模型 ， （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校正公式（关

19、于）如果令，则拟牛顿条件为 ， （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总体收敛 设是任意初始点，是对称正定矩阵的

20、初始Hesse近似。 假设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)在下面的证明中，我们利用了这两个概念来估计Hes

21、se近似的最大和最小特征值的大小。定理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

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

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

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

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

26、于要求无论在长度上还是方向上都趋向于。为此，我们建立以下引理。引理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）从而我们有结论：拟牛顿法超线性收敛的充分必要条件是其位

27、移在长度和方向上都渐进的趋向于牛顿方向。定理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）可知成立，从而

28、对于充分大的k，。 第4章 数值验算 这里将给出6个例题用以验算算法的的可行性。在迭代过程中Armijo准则中的参数，。6个例题的数值结果将列表记录。从这些结果中我们可以看到算法的可行性和有效性。4.1问题模型 问题1 初始迭代点为=1,1 问题2 初始迭代点为=-1.2 ,1 问题3 初始迭代点为=1,2,1,1,1,1 问题4 初始迭代点 =0.4,1,0 问题5 初始迭代点为=-3,-1,-3,-1 问题6 初始迭代点位=1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,14.2 数值结果上述模型所得的数值结果如下表所示，其中k表示迭代次数，t表示运算时间，b表

29、示目标函数维数，val表示目标函数的最优值，表示初始迭代点。如下表4-1。表4-1 数值结果：题号bval k t121,1270.795022-1.2,160.1390361,2,1,1,1,1300.4830430.4,1,030.060054-3,-1,-3,-10.000000694140.342062021200.3590 总 结 本文提出了拟牛顿法的算法，并有程序实现。在程序实现过程中选用了Armijo非精确线搜索求步长。用BFGS校正求。同时对算法的收敛性进行了证明。同时对算法进行了数值验算，从而证明了算法的可行性和有效性。本文吸取了大量前人的经验。因此比前人的拟牛顿法更为有效。

30、收敛性证明更为完善。本文进一步工作将是提出更完善的拟牛顿算法。对其收敛性进行更完善的证明。同时把算法推广到更多的求解最优解问题上。 在毕业论文的写作过程中，我遇到了很多麻烦。刚开始拿到题，很是茫然。通过到图书馆，上网查阅资料。我逐渐掌握了大量的专业知识。扩充了自己对题目的认。，在编程调试的过程中，从刚开始的时候对matlab生疏，对算法的不明白。到最后能够顺利的编写出程序再调试成功。在这个过程中我学到了很多。让我明白了很多道理。要想做成功一件事，你必须要脚踏实地，有充分的准备。这样才能把每件事做好。致 谢 光阴飞逝，转眼四年的大学生活就要结束了。在这四年时间里，很多同学和老师都给了我很多的帮助

31、。至此论文完成之际，在此向尊敬的老师和亲爱的同学们表示深深的谢意。 我要对我的导师xx老师表示诚挚的感谢。，本学位论文是在她的悉心指导下完成的在论文过程中，王老师表现出的严谨的治学态度，忘我的工作作风，还有对待学生的宽厚和耐心都令我深深地折服她就像春天的风一样，当我气馁不安时，恰当的寥寥数语就能让我放下心头所有的包袱重获前进的动力；她也像炎热夏天的凉风，当我焦躁膨胀时，适时的给与警醒提示让我脚踏实地一步一个脚印的前进；她又像秋天的阳光，用她高洁的内涵和渊博的知识抚照着我做出成果；她更像数九严寒天绽放的寒梅，用她那不畏困难坚持向上的精神风貌感召着我永远向前正是她的谆谆教导使我逐渐步入科学的殿堂，

32、逐渐领悟到科研的乐趣，也正是她的谆谆教导和适时鼓励让我能放稳心态忌焦忌躁地完成各方面的工作王老师教会我的东西将使我终生受益，即使步入新的学习和工作生活，我也会将导师的教诲铭记于心 参考文献1 时平平，王希云基于新拟牛顿方程的拟牛顿法对一般目标函数的全局收敛性J太原科技大学学报，2008，62 陈兰平，焦宝聪非凸无约束优化问题的广义拟牛顿法的全局收敛性J-应用数学，2005，4：5735793 王希云，时平平基于新拟牛顿方程的修改Broyden族的全局收敛性J应用数学，2008，21(2)：340-3444 李董辉，童小娇，万中数值最优化北京：科学出版社，20051985 袁亚湘，孙文瑜最优化理

33、论与方法北京：科学出版社，199713306 徐成贤等近代优化方法北京：科学出版社，2005276-2987 Stanley C. Eisenstat Homer WalkerF. Globally convergent inexact Newton methods. SIAM, J.Opti. 1994 ,2:3934228 Xu CX，Zhang JZA Survey of QuasiNewton Equations and Quasi-Newton Methods for OptimizationJAnnals of Operations Research，2001，103：213234

34、9 ZXWei，QXLiA new Huang class and its properties for unconstrained optimization problems Journal of Mathematical Research and Exposition2005，1：647110 HestenesMR，stiefel ELMethodsofconjugate gradientsforsolvinglinearsystems，J Res，Nat Bur Standards Sect1952，5(49)：409-43611 letcherR，Reeves CFunction mi

35、nimizationby conjugategradients，computJ，1964，7：149。1 5412 YaXiang Yuan，A Modified BFGS Algorithm for Unconstrained Optimization，IMA Journal of Numerical AnalysiS，1991，1 1：32533213 赵云彬，易正俊伪Newton一6族的导出和全局收敛性J数值计算与计算机应用，1995，1：53-6214 陈兰平，王丽伟广义拟牛顿算法对一般目标函数的收敛性J应用数学，2002，15(3)：69-7515 杨晓光一类拟牛顿算法的收敛性C清华大学应用数学论文集，1