1、20XX年度本科生毕业论文（设计）求解无约束最优化问题的一种新的拟牛顿方法院 系： 数学学院 专 业： 信息与计算科学 年 级： XXX 学生姓名： XXX 学 号： XXX 导师及职称： XX（副教授） 20XX年X月20XX Annual GraduationThesis (Project) oftheCollegeUndergraduate A new quasi-Newton equation of the solving unconstrained optimization problemsDepartment:College of MathematicsMajor:Informat
2、ion and Computing ScienceGrade:2011Students Name:Liu XinghongStudent No.:20XXX050064Tutor:Li Can（Associate professor） Finished by June, 20XX毕业论文（设计）原创性声明本人所呈交的毕业论文（设计）是我在导师的指导下进行的研究工作及取得的研究成果。据我所知，除文中已经注明引用的内容外，本论文（设计）不包含其他个人已经发表或撰写过的研究成果。对本论文（设计）的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意。 作者签名： 日期： 毕业论文（设计）授
3、权使用说明本论文（设计）作者完全了解XX学院有关保留、使用毕业论文（设计）的规定，学校有权保留论文（设计）并向相关部门送交论文（设计）的电子版和纸质版。有权将论文（设计）用于非赢利目的的少量复制并允许论文（设计）进入学校图书馆被查阅。学校可以公布论文（设计）的全部或部分内容。保密的论文（设计）在解密后适用本规定。 作者签名： 指导教师签名：日期： 日期： XXX 毕业论文（设计）答辩委员会(答辩小组)成员单姓名职称单位备注副教授数学学院组长讲 师数学学院组员助 教数学学院组员XX学院本科毕业论文（设计） 摘要拟牛顿算法是求解无约束最优化问题最常用的方法之一。也是牛顿法的一种推广，牛顿法中每次迭
4、代都需要计算Hesse阵和Hesse阵的逆，每次迭代计算量和存贮量都很大，而以拟牛顿方程为基础构造的拟牛顿算法克服了牛顿法的不足，不需要明显形成Hesse阵。因为拟牛顿法是通过函数的一阶导数构造出曲率的近似，不需要求函数的二阶导数，从而大大的减少了计算的复杂度，同时拟牛顿法还具有超线性收敛并且收敛速度快的优点。拟牛顿算法在求解无约束优化问题中占有不可替代的位置,同时也是很多学者研究的课题。本文的前半部分简单的叙述拟牛顿法的研究背景，后半部分给出了一个新的拟牛顿方程，并给出了相应于新的拟牛顿方程的一类新算法。本文的主要思路是通过目标函数在点处进行二阶泰勒展开，然后利用泰勒展开式中目标函数值以及目
5、标函数的梯度信息推导出出新的拟牛顿方程，对新的拟牛顿方程进行修正并给出相应的修正公式。本文中得到的新的拟牛顿方程含有一个自由未知变量，本文仅讨论了当时的情形，新的拟牛顿方程还有更多的可能。关键词：无约束最优化；拟牛顿方程；拟牛顿算法AbstractQuasi-Newton method is extensively used inunconstrained optimization problems. And is the extension of the Newton method. The main drawback of the Newton is the calculation of
6、the Hesse and the inverse matrix of Hesse the large amount of calculation and store capacity at each iteration, But the quasi-Newton method based on quasi-Newton equation gets rid of the drawback. In place of the calculation of the true Hesse matrix, because Quasi-Newton method through the first der
7、ivative 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 convergence and convergence speed advantages quasi-Newton algorithms in solvi
8、ng unconstrained optimization has irreplaceable position in also many scholars research project.The first half of this article gives the background of the Quasi-Newton methods, the latter part of this paper gives a new quasi-Newton equation, and then a series of new algorithms corresponding to the n
9、ew quasi-Newton equation are proposed.The main idea of this paper is through the objective function of two order Taylor expansion at point , then, the new quasi-Newton equation is deduced by use of the value of objective function and the gradient information of objective function in the Taylor expan
10、sion, to revise the new quasi-Newton equation and gives the correction formula of the corresponding. In this paper, the new quasi-Newton equation with one unknown variable , but it just discussion when situation in this article, there is more likely with the new quasi-Newton equation.Keywords: uncon
11、strained optimization; Quasi-Newton equation; Quasi-Newton method目录1.引言11.1拟牛顿法提出的背景11.2几种经典的拟牛顿法简介31.3迭代步长的选取61.3.1精确线性搜索61.3.2非精确线性搜索61.4拟牛顿法的研究近况简介72.一个新的拟牛顿方程及其相应的一类新算法102.1 新的拟牛顿方程102.2 相应于新的拟牛顿方程的一类新算法122.2.1 对称秩一修正公式122.2.2 ABFGS修正公式（对称秩二修正公式）与ABFGS算法133.结论18参考文献19致谢21XX学院本科毕业论文（设计） 求解无约束最优化问
12、题的一种新的拟牛顿方法1.引言 1.1拟牛顿法提出的背景一般的非线性无约束最优化问题的求解方法有很多，如牛顿法、最速下降法、拟牛顿法以及修正拟牛顿法等，其中最为重要的数拟牛顿法，许多求解无约束最优化问题的现代方法都是在拟牛顿法的相关算法基础上建立起来的，所以拟牛顿法是许多现代优化方法的基础，下面简要的介绍拟牛顿法的基本原理。牛顿法的基本思想：在目标函数的极小点的近似点处，将目标函数进行二阶泰勒展开，即： （1.1）即，用去逼近，将的极小点作为的一个新的近似点，对式（1.1）两端关于求导，且令：即得若正定，则存在，由此解得的就是二次函数的极小值点：若给定的初始近似点，则迭代点列可由上述公式产生，
13、上述公式称为拟牛顿迭代公式，相应的算法称为牛顿法。牛顿法收敛速度非常快，具有二次收敛的优点，但它存在下面三个严重的缺陷：（1）想要求得新的近似点，需要计算目标函数的Hesse阵及其逆矩阵，计算量很大，在计算机中实现时，时间和空间复杂度都很高。（2）如果目标函数在点处Hesse矩阵是奇异的，则不存在，因而不能构成拟牛顿方向，从而使迭代无法进行。初始点的选取只能在的适当领域内，然而是待求的，因此很难去检验是否靠近于，所以所产生的点列可能不收敛。（3）每次迭代并不能保证下降，虽然目标函数不会上升，当Hesse矩阵非正定时，牛顿法的搜索将会失败。也即，必须保证Hesse矩阵正定，才能保证目标函数的下降
14、性。为了克服牛顿法的缺点，找出既能摆脱牛顿法的缺陷又能保持其收敛速度快的优点，于是人们提出了拟牛顿方法。以下简介拟牛顿法的基本思想。设目标函数具有连续二阶偏导数，将在处展开二阶泰勒公式对上式求导得：令，于是有即当用对称正定矩阵来近似时，也必须满足也即，上式称为近似牛顿条件。我们就得到了拟牛顿方程（标准拟牛顿方程）： （1.2）其中，.如何寻找到合适拟牛顿方程的矩阵，人们提出了许多的方法，我们所接触中的所有方法最常用的是修正方法，即令，当已知时，给出修正矩阵，就可以通过校正公式得到，修正矩阵不同，也就得到不同的，由此所形成的迭代算法也就不同，我们统称这类算法为拟牛顿算法。1.2几种经典的拟牛顿法
15、简介（1）鉴于无约束最优化问题拟牛顿方程对Hesse矩阵的对称性要求，在这里我们介绍具有对称性的迭代方法：秩为一的修正方法1。因为，所以最简单的校正公式的取法应该是其秩为一的形式，进而可以进一步改写为：其中，要使得满足（1.2）式，通过计算整理可得到，当时，能够推导出一般的秩1修正公式, （1.3）（1.3）式是唯一的秩1对称拟牛顿修正，它首先是由Davidon于1959年得到，Broyden与1967年又重新导出这一算式，然而对称秩一修正公式没有正定遗传性，另外，分母可能取零，秩一形式的修正公式也就没有意义了，因此有待于修正改进。但是它有一个显著的优点，就是比其他修正公式近似程度高，因此运用
16、这个优点的一些算法取得了很好的效果，信赖域算法1就是一个很好的例子。（2）Powell为了克服对称秩1修正公式在迭代中没有正定遗传性的缺点，就提出了秩二校正公式，常见的校正公式有如下几种：（a）PSB2校正即Powell导出的对称Broyden校正公式。（b）DFP公式最早是由Davidon与19593年导出，并由Fletcher与Powell(1963)4两个所修正，现称为DFP校正。（c）BFGS公式上式公式是由Broyden-Fletcher-Goldfarb-Shanno提出的。（d）Broyden族拟牛顿校正公式当时，我们称上式为限制布鲁丹族拟牛顿校正公式。可以看出Broyden族拟
17、牛顿校正公式中：令即可得到DFP校正公式；令，即可得到BFGS校正公式。（3）1970年，Huang通过Broyden族算法要求的条件进行放松，提出了一类比Broyden族更广一族的拟牛顿算法，即Huang5族拟牛顿法。它的条件是：（a）矩阵不要求对称性。（b）校正矩阵不要求满足拟牛顿方程，而是要求满足广义拟牛顿方程其中。（c）要求算法应用于二次凸函数时，产生的方向是关于矩阵共轭的，从而其具有二次终止性。根据上述三个要求，他导出了一类含有三个自由参数的Huang族算法，当算法中的满足对称性要求而且参数中的时，Huang族算法就变成含有一个参数的Broyden族算法，因此Broyden族算法是H
18、uang族算法的子族。记校正矩阵为，迭代方向由计算给出，按照上述条件，他导出了Huang族校正公式的形式，如下： （1.4）其中 （1.5） （1.6）且满足关系式 （1.7） （1.8）关系式（1.4-1.8）中五个参数、和中仅有三个自由参数，因此，Huang族校正公式依赖于这三个参数，选取不同的参数，就可以得到不同的算法。事实上，当，若让为对称矩阵，只要，则也对称，这时Huang族算法只有一个参数。将取为自由参数，若令即由（1.5-1.8）式得 以及代入（1.4）式，得 （1.9）其中这表明Broyden族拟牛顿公式是Huang族的子族。特别，令，得DFP公式。令，得BFGS公式。1.3迭
19、代步长的选取在使用拟牛顿法求解非线性无约束最优化问题的迭代过程中，为了保证函数值的充分下降性和迭代序列的全局收敛性，我们引入了步长因子，是由线性搜索策略所确定。一般地，求的方法有精确性搜索法、直接搜索法、插值法和不精确线性搜索法等几类，各类方法各有特色。在拟牛顿法中经常使用的是精确线性搜索和非精确线性搜索法。1.3.1精确线性搜索精确线性搜索就是要求选择步长满足以求获得最大可能的下降。精确线性搜索法能够使得目标函数在迭代过程中拥有最大下降量，但是它有一个缺点，就是计算量比较大，并且在迭代过程中，在求目标函数的最优解时，往往没有必要把线性搜索搞得十分精确，特别是在计算的初始阶段，因为过分的追求线
20、性搜索的精确度会影响整个方法的效率。由此我们在求解无约束优化问题时，放松对的要求，只要求目标函数在迭代的每一步都有充分的下降即可，通常采用不精确线性搜索求解迭代步长。但是，精确线性搜索具有重要的理论价值，许多无约束非线性最优化算法的收敛性和收敛速度都基于精确线性搜索。1.3.2非精确线性搜索精确线性搜索要求步长取到一元函数的最小值，计算量比较大，下面所介绍的非精确线性搜索只要求步长使得函数在点处的值较有一定的下降量，因此，在计算上容易实现。Armijo型线性搜索：给定，取，使得 （1.10）利用函数，上式可等价地写为：由于是在处的下降方向，且满足，容易证明：不等式（1.10）对充分小的正数均成
21、立，而在计算上，希望步长尽可能的大，设常数，。在Armijo型线性搜索中，可取步长为集合中使不等式（1.10）成立的最大者。Wolfe-Powell型线性搜索：给定常数，满足，使得 （1.11）利用函数，上式可等价地写为：可以证明，若是在处的一个下降方向且，再设在射线上有下界，则有，存在区间，使得中的任何点都满足Wolfe-Powell型线性搜索条件（1.11）。1.4拟牛顿法的研究近况简介拟牛顿法作为求解非线性无约束最优化问题运用最成功的方法之一，自从问世以来一直是众多研究学者较为关注的问题。20世纪50年代美国Argonne国家实验室的理学家W.C.Davidon首先提出了变尺度方法，也就
22、是现在的拟牛顿算法，他的算法不久在R.Fletcher和J.D.Powell6的发展下，证实了其比其他算法具有优越的快速性和可靠性，使得非线性优化这门科学得到了突飞猛进的发展，特别是紧接这之后的20年里，拟牛顿法也引起了广大研究学者的关注，并且有了快速的发展，演绎出了大量的变形公式以及众多的拟牛顿算法的相关文献7-10。其中最为著名的数Broyden族和Huang族拟牛顿法。起初的拟牛顿方程为其中，.可以知道，最初的拟牛顿方程及其修正公式只涉及到了一阶导数信息，没有充分利用已知信息，为了更精确的近似值，就要尽可能多的利用已知存在的信息，因此国内外的众多研究人员都致力于研究带有函数值信息的拟牛顿
23、法，并且取得了一些研究成果。1.Biggs2于1970年提出了一种修正形式的拟牛顿算法的公式： （1.12）其中为系数参数，.2.Davidon3于1980年提出了目标函数的一个带有函数值信息和梯度值信息的三次近似模型。3. Spedicato7于1981年提出了Huang族拟牛顿算法中的的一种特殊取法得到了一族秩为一的正定迭代公式。4.1993年，袁亚湘11基于的二次近似值和一些差值条件，得到了类似于式（1.12）的迭代公式，其中取定为5. Anjos12与1993年推广了袁亚湘的成果，运用到了一布鲁丹族拟牛顿法中。6.1994年，焦宝聪13利用目标函数局部二次模型近似也提出了类似于（1.1
24、2）的修正公式，公式中取为，71994年J.A.Ford14提出了一个拟牛顿法，其思路主要是利用了目标函数的近m步梯度值，沿着近m步迭代点所构成的线路，并采用拉格朗日插值公式取得对目标函数梯度值的近似得到。8.1999年张建中，邓乃杨XX利用目标函数值，和一阶导数信息，对进行二次插值，得到了一个新的拟牛顿方程迭代公式：，并且验证了新的拟牛顿方程比先前的拟牛顿方程具有更好地实际应用效果。9.2001年，张建中和徐成贤16提出了一族应用更为优越的新的拟牛顿方程，且，10.2003年，肖运海和叶魂17提出了一类似的拟牛顿方程，11.2005年，焦宝聪和陈兰平18给出了一种广义的拟牛顿算法，其拟牛顿方
25、程为，迭代矩阵公式为，其中。12.2006年，韦增欣19等人提出了一个修正的拟牛顿方程，推导出了的几种迭代公式，并证明了相应的算法的全局收敛性和超线性收敛性。13XX学院本科毕业论文（设计） 2.一个新的拟牛顿方程及其相应的一类新算法 2.1 新的拟牛顿方程假设目标函数具有连续的二阶偏导数，将在处展开二阶泰勒公式，于是有令，则即得进一步化简 此时，用去近似逼近，不妨取整理可得 （2.1）其中，且，使得.说明：这里得到的新的拟牛顿方程式（2.1）通过变换可以得到韦增欣等人得到的新的拟牛顿方程，具体推导过程见下：对于上式的取值，我们假设对于所有的，取，则即为则新的拟牛顿方程为：其中，为一矩阵：上式
26、为韦增欣等人得到的新的拟牛顿方程，可以看出本文推出的拟牛顿方程具有更大的自由性和选择性，因为新的拟牛顿方程（2.1）式含有自由变量，取法的不同就可以得到不同的拟牛顿方程以及相应的迭代格式。本文讨论当时得到的拟牛顿方程和相应的拟牛顿算法。当时，因此，新的拟牛顿方程为其中，2.2 相应于新的拟牛顿方程的一类新算法当时，满足拟牛顿方程的矩阵有很多，确定的原则之一是使其在计算上容易实现，已有的拟牛顿通过对进行低秩修正产生，即令 （2.2）其中，矩阵是秩为1或2的矩阵，我们参照以上低秩修正法对新的拟牛顿方程进行修正并给出相应的修正公式。2.2.1 对称秩一修正公式在式（2.2）中取为秩一的对称矩阵，即令
27、，其中，由新的拟牛顿方程式（2.1）得：即有 （2.3）上式说明，向量平行于，即存在，使得或者从而，由式（2.3）得若，则，故得对称秩一修正公式如下： （2.4）2.2.2 ABFGS修正公式（对称秩二修正公式）与ABFGS算法在式（2.2）中取为秩2的对称矩阵，即令，其中，是待定实数，是待定向量，由拟牛顿方程（2.1）得.即. （2.5）观察可发现，满足上式的向量和不唯一，取，分别平行于和，即令，其中，与是待定参数，则有：.由（2.5）式得故可令，从而故得如下秩2修正公式，即新的BFGS修正公式，命名为ABFGS修正公式：. （2.6）显然，若对称，则也对称。ABFGS修正公式有如下性质：命
28、题2.1 设对称正定，由ABFGS修正公式（2.6）确定，则当且仅当时，对称正定。证明：注意到若正定，则显然有下设且对称正定，我们证明对任何且，有.由公式（2.6）得， （2.7）由的对称正定性，存在对称矩阵，使得，利用Cauchy-Schwarz不等式，得 （2.8）上面放入不等式成立等式的充要条件是存在数使得，即.因此，若不等式（2.8）为严格不等式，则由式（2.7）得若不等式（2.8）中等式成立，即有，使得，则由不等式（2.7）和等式（2.8）得总之，即对称正定。上面的命题表明：若初始矩阵对称正定，且在迭代时保证，则由修正公式（2.6）产生的矩阵序列是对称正定矩阵序列。从而，对所有的，方
29、程组有唯一解。而且，为在处的下降方向。可以证明得知：若在ABFGS算法中采用精确线性搜索或Wolfe-Powell型线性搜索，则不等式成立。并且，对于精确线性搜索，有，因此若采用Wolfe-Powell型线性搜索，则由定理可得：因此，在ABFGS算法中，若采用精确线性搜索或Wolfe-Powell型线性搜索，则只要对称正定，由算法产生的矩阵序列是对称正定矩阵序列。此外，若二次连续可微且正定，则此时，不论采取何种线性搜索，只要对称正定，则由ABFGS算法产生的矩阵序列是对称正定矩阵序列。特别地，当ABFGS算法用于求解一致凸函数极小值问题时，只要对称正定，则由算法产生的矩阵序列是对称正定矩阵序列
30、。下面给出ABFGS算法的步骤：ABFGS算法步1 取初始点，初始对称正定矩阵，精度，令.步2 若，则算法终止，得问题的解.步3 解线性方程组 （2.9）得下降方向.步4 由线性搜索确定步长.步5 令，若，则得解，否则，由，确定，由ABFGS修正公式（2.6）确定.步6 令，转步骤3.注：若在ABFGS算法中的步4中采用Armijo型线性搜索，由于不能保证，此时，的正定性不能由线性搜索保证，为了保证采用Armijo型线性搜索时矩阵的对称正定性，可采用如下的修正方式：若则取若则取.不难看出，只要对称正定，上述修正公式可保证举证序列为对称正定矩阵序列。下面给出一个实例：例：采用精确线性搜索的ABF
31、GS算法求解下面的无约束问题：取初始点，初始矩阵为单位矩阵。解：由题意计算可得，对，令由，得到精确线性搜索的步长为取，有，解线性方程组(2.9)得解，因此，从而，.容易算得：,.故解线性方程组（2.9），即得，。故.23XX学院本科毕业论文（设计） 3.结论 关于求解无约束最优化问题，已经有着非常多的计算方法，其中拟牛顿算法作为最有效的方法之一，其构造是基于拟牛顿方程。传统的拟牛顿方程只利用了目标函数的梯度值信息而忽略了目标函数值的信息，这无疑是对信息资源的浪费。近几年来，对于即利用梯度信息又用到函数值信息的新拟牛顿方程基础上的拟牛顿算法的研究已经有一定的成果。而本文是受前面研究者们思路的启发
32、，利用了二阶泰勒展开，提出了一种新的拟牛顿方程，新的拟牛顿方程中不仅利用了目标函数的梯度信息，而且用到了目标函数值的信息，并且在新拟牛顿方程基础上提出了新的拟牛顿算法。本文新的拟牛顿方程含有一个自由参量，取不同的值可以得到不同的新拟牛顿方程，本文仅讨论了当时的情形，也未给出数值计算与收敛性证明，故还有待于改善和发展。参考文献1徐成贤,陈志平,李乃成.近代优化方法.科学出版社，20022Biggs.M.C.Minimization algorithms making use of non-quadratic properties of the objective function.J.of In
33、stitute of Mathematics and Its Applications.1971(8):3XX-3273W.C.Davidon.Variable metric method for minimization.AEC Res.and Dev.Report ANL-5990(1959)4R.Fletcher and M.J.D.Powell.A rapid convergent descent method for minimization.Computer Journal 6(1963)163-1685H.Y.Huang.Unified approach to quadratic
34、ally convergent algorithms for function minimization.Journal of Optimization Theory and Applications 5(1970)405-4236R.Byrd,J.nacedal,Y.Yuan,Global convergence of a class of quasi-Newton methods on convex problems,SIAM J.Numer.Anal.24(1987)1171-11897E.Spedicato.A class of rank-one positive definite q
35、uasi-Newton updates for unconstrained optimization,Math.Opterations for sch.Stat.Ser.A,Optimization 14(1981)61-708Steihaug T.Quasi-Newton methods for large optimization.PH.D.Dissertation.SOM Technical Repor.49,Yale University,19849Nocedal J.Updating Quasi-Newton matrices with limited storage.Mathema
36、tics of Computation,1980,35:773-18210Gill P.E.and Murray W.Quasi-Newton methods for linearly constrained optimization.In Numerical Methods for Constrained Optimization(Gill P E and Muarray W.eds.)1974,67-92,London:Academic Press11袁亚湘.非线性规划数值方法.上海:上海科学出版社,1993:114-11612M.F.Anjos.A modified Broyden up
37、date with interpolation.SIAM Journal on Scientific Computing 14(1993)1359-136713焦宝聪,陈兰平.一类广义拟牛顿算法的收敛性.数学研究与评论2005,25(1):114-12114J.A.Ford and I.A.Moghrabi.Multi-step quasi-Newton methods for optimization.Journal Computation and Applied Mathematics 50(1994)305-323XXJ.Z.Zhang,N.Y.Deng and L.H Chen.A n
38、ew quqsi-Newton equation and related methods for unconstrained optimization.Journal of Optimization Theory and Application 102(1999)147-16716Zhang J Z,Xu Ch X.Properties and numerical performance of quasi-Newton methods with modified quasi-Newton equations,J.Comput.Appl.Math,2001,137:269-27817Xiao Y
39、 H and Ye Hun.A Modified BFGS Method with Global Convergence for Unconstrained Optimization Problems.Guang xi Science 2003,10(4)253-XX7,26118焦宝聪,陈兰平.一类广义拟牛顿算法的收敛性.数学研究与评论.2005,25(1):114-12119Zengxin Wei,Guoyin Li and Liqun Qi.New quasi-Newton methods for unconstrained optimization problems.Applied Mathematics and Computation 175(2006)1XX6-1188致谢首先感谢我的论文指导教师李灿老师，正是在李灿老师的严格要求和精心指导下，我才顺利完成了毕业论文的撰写，在毕业论文初期的文献搜集以及最后的定稿，导师都给了我极大的帮助，在论文完成之际，谨向导师致以诚挚的谢意！其次，还要向同组同学李继华同学表以真挚的谢意！当我在论文思路和排版上遇到困难时，想她请教，她帮助了我许多。最后，感谢学校与教学老师对我的悉心培养与教育，为我提供了宽松自由的学习环境，使我能够专心于本文的研究。29
