毕 业 论 文

题 目： 无约束最优化问题的拟牛顿法

诚 信 声 明

本人声明：

1、本人所呈交的毕业设计（论文）是在老师指导下进行的研究工作及取得的研究成果；

2、据查证，除了文中特别加以标注和致谢的地方外，毕业设计（论文）中不包含其他人已经公开发表过的研究成果，也不包含为获得其他教育机构的学位而使用过的材料；

3、我承诺，本人提交的毕业设计（论文）中的所有内容均真实、可信。

作者签名： 日期： 年 月 日

毕业设计（论文）原创性声明和使用授权说明

原创性声明

本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。

作 者 签 名：　　 　 　　日　 期：　　 　 　　

指导教师签名：　　 　 　　 日　　期：　　 　 　　

使用授权说明

本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。

作者签名：　　 　 　　 日　 期：　　 　 　　

学位论文原创性声明

本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。

作者签名： 日期： 年 月 日

学位论文版权使用授权书

本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权　　 　 　大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。

涉密论文按学校规定处理。

作者签名： 日期： 年 月 日

导师签名： 日期： 年 月 日

指导教师评阅书

评阅教师评阅书

教研室（或答辩小组）及教学系意见

毕业设计（论文）任务书

题目： 无约束优化问题的拟牛顿法

姓名 xx 院（系） xx 专业 信息与计算科学 班级 xx 学号 xx

指导老师 xx 职称 讲师 教研室主任 xx

一、 基本任务及要求：

1．基本任务：

在牛顿法基础上提出拟牛顿法，设计拟牛顿法的算法，了解拟牛顿法的优点及用途。在一定的条件下证明该算法的合理性并对其收敛性进行分析。讨论算法的收敛速度 ，通过数值试验对算法的有效性进行验证。

2．基本要求：

对拟牛顿法给出合理的算法；利用理论知识对算法合理性进行证明 对其收敛性以及收敛速度 进行分析证明。写出毕业设计说明书，完成全部研究工作和毕业论文。

二、 进度安排及完成时间：

第一阶段 (第1－4周) ：进行调研，查阅相关资料，撰写开题报告，并于第4周星期五

交开题报告；

第二阶段 (第5－12周): 在指导教师的指导下，对课题

进行研究，按预定要求获得毕业

论文开题报告中的预期结果（即进行算法设计，研究算法的合理性，实现算法

等工作），并撰写毕业论文，第12周五之前交初稿；

第三阶段 (第13－14周): 指导教师对毕业论文进行批阅，提出修改意见并指导学生进行

毕业论文的修改,并检查算法的实现情况（如程序的可行性和通用性等）；

第四阶段 (第15周): 指导教师指导学生将毕业论文定稿，并准备毕业论文答辩；

第五阶段 (第16周): 进行毕业论文答辩。

摘 要 1

前 言 2

第1章 最优化基础 4

1.1 无约束最优化问题的最优性条件 4

1.2 收敛概念 5

1.3 Wolfe准则和Armijo准则 7

第2章 拟牛顿法算法设计 9

2.1 拟牛顿法条件 9

2.2 算法设计 11

第3章 收敛性证明 12

3.1 总体收敛 12

3.2 局部超线性收敛 16

第4章 数值验算 21

4.1 问题模型 21

4.2 数值结果 23

总 结 24

致 谢 25

参考文献 26

附 录 27

无约束最优化问题的拟牛顿法

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

关键词：拟牛顿法，无约束优化，收敛性。

A quasi-newton method for Unconstrained optimization

Abstract:Newton method is to solving unconstrained optimization problem of one 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 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 couldn't 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 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 analysis.

Key words:Quasi-newton,Unconstrained optimization ,Convergence

前 言

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

无约束优化问题是最优化问题的基础，是数值计算领域中十分活跃的研究课题之一，历时较长，获得的成果也较多，有关的方法和理论比较成熟。其中非线性无约束最优化方法在科学计算和工程分析中起着越来越重要的作用。牛顿法作为求解最优化问题最有效的方法之一。它的基本思想是利用目标函数的二次泰勒展开，并将其极小化。在非线性无约束最优化问题中，对于正定的二次函数，牛顿法一步即可达到最优解。对于非二次函数，牛顿法并不能保证经有限次迭代求得最优解，但由于目标函数在极小点附近似于二次函数，故当初始点靠近极小点时，牛顿法的收敛速度一般是很快的，因此这种方法得到了很多人的认可与利用。但牛顿法中每次迭代都需要计算Hessian矩阵，但计算Hessian矩阵工作量大，并且有的很难计算，甚至不好求，而以拟牛顿方程为基础构造的拟牛顿算法克服了牛顿法的这一不足。因此拟牛顿法被广泛的认可，她的应用相当广泛。可以剞劂很多问题。并有很多人多拟牛顿法做了研究。

对于拟牛顿法的算法设计，也已经有不少学者提出过，早年袁亚湘与孙文瑜合作《最优化理论与方法》一书中对其进行了详细的设计，而后也有不少学者对其进行研究。

对于拟牛顿法的收敛性证明，时平平在2008年其硕士论文《关于无约束最优化问题的拟牛顿算法研究》中详细的做了证明。

第1章 最优化基础

在这一章里我们首先简要介绍判断无约束最优化问题的最优解常用的最优性条件，接着给出拟牛顿算法的概述，最后说明本文的主要工作．

1.1无约束最优化问题的最优性条件

最优化理论与方法是一门应用性很强的年轻学科，它研究某些数学上定义的问题的最优解，即对于给出的实际问题，从众多的方案中找出最符合要求的最佳方案．在电子计算机的推动下，最优化理论与方法在经济计划、工程设计、生产管理、交通运输等方面得到了广泛应用，成为一门十分活跃的学科．

最优化问题根据有无约束条件可分为约束和无约束最优化问题．现实生活中存

在的主要是有约束的问题，但我们可以通过某些处理将有约束的问题转化为无约束的问题处理，并且无约束最优化问题的求解相对容易的多，而解法的基本思想又常常可以推广到一般有约束的情况，因此使得研究无约束最优化问题的计算方法显得尤为重要，人们对它的研究情况也十分重视．

对于无约束问题

, . （1.1）

的最优性条件可以分为一阶条件和二阶条件．设的一阶导数和二阶导数存在，且分别表示为

,

则我们有以下定理．

定理1.1(一阶必要条件)设：寸R1在开集上连续可微。若 (1．0)的局部极小点，则

.

定理1.2(二阶必要条件)设：在开集上二阶连续可微，若

是(1．O)的局部极小点，则

.

定理1.3(二阶充分条件)设：在开集D上二阶连续可微，则

是的一个严格局部极小点充分条件是

，是正定矩阵.

满足的点称为函数的平稳点或驻点，一般目标函数的平稳点不

定是极小点，但若目标函数是凸函数，则其平稳点就是其极小点，且为总体极小点．

定理1.4(凸充分性定理)设：是凸函数，且。则是总体极小点的充分必要条件是

.

1.2收敛概念

收敛速度是迭代方法的又一重要性质。对于一个不可能在有限步内找到最优解的最优化方法，我们不仅要求它收敛，还要要求它有较快的收敛速度，这是因为一个收敛很慢的方法往往需要很长的时间才能得到满足精度要求的最优解的近似。因而不是一个有效的方法。设向量序列收敛于，定义误差序列

,

如果存在常数和使成立

.

就说序列以为因子阶收敛于。最常见的为和的情形，当，时称为线性收敛，这是的误差序列具有以下性能：

.

依最简单的情形，在上式中取等号，设初始误差为1，如果=0.5，则误差序列为

1，0.5，0.25，0.125，0.0625，…，

如果，则误差序列为

1，0.1，0.01，0.001，…，

可以看出越小，收敛越快。如果从同一初始点开始，收敛快的算法可以用较少的迭代次数达到预定的精度，而收敛慢的算法则需要较多的迭代次数才能得到相同精度要求的点。

当时，称序列超线性收敛于，超线性收敛是一种比线性收敛快的收敛，多数的最有化方法具有超线性收敛的特性，在上述收敛率的定义中，所有的收敛独属于超线性收敛。事实上，由

,

有

.

称时的收敛为二次收敛，这时误差序列的性能可以用下述不等式表示

.

二次收敛是一种更快的收敛，还要考察上式取等式时的情形，设初始误差为1，，则误差序列为

可以看到，二次收敛的方法每一次迭代近似解得精度就增加一倍。

一个理想的算法终止准则为

.

然而由于是未知的，这样的准则并不具有任何实用价值。但是由于

在序列{}超线性收敛于时，我们可以得到

.

上式表明对于一个超线性收敛的算法是的一个估计。因此对于超线性收敛速度的方法，

.

是一个比较合适的终止准则。

1.3Wolfe准则和Armijo准则

Wolfe准则为

.

其中，。

Armijo准则为：

给定，，，设是使得下述不等式A：

. （1.2）

成立的最小非负整数，令。由于是下降方向，当m充分大时，不等式(1.2)总是成立的，因此上述总是存在的。由于是使得上述不等式成了的最小非负整数，因而不会太小，从而保证了目标函数的充分下降，令。实际上，不等式(1.2就是充分下降条件

. （1.3）

如果上式满足，则终止搜索，否则，我们可以缩小，或者在区间[0,]上用二次插值公式求近似极小点

. （1.4）

将其作为一个新的。

第2章 拟牛顿法算法设计

2.1 拟牛顿法条件

考虑目标函数在当前点处的二阶模型

. （2.1.）

其中，是对称正定矩阵，是Hesse近似，它将在每次迭代中进行校正。极小化这个二次模型

， （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校正公式（关于）

如果令，则拟牛顿条件为

， （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近似。

假设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近似的最大和最小特征值的大小。

定理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），得

， （3.18）其中。

下面，我们利用Wolfe不精确线性搜索的总体收敛性定理证明结果。

由于，，故，这表明由（3.13）定义的也是最速下降方向和拟牛顿搜索方向之间的夹角。于是，由于Wolfe不精确线性搜索的总体收敛性定理得

. （3.19）

为了证明，只要证明存在子序列{}，使得。

假定。则存在，使得对所有，有

. （3.20）

其中是上面定义的常数。利用（3.18）得到:对所有，

（3.21）

在（3.17）中，第一项和第三项是正的，但有限，第二项小于零，第四项也小于零，且与k有关，故当k充分大时，上式右边是负的，从而给出矛盾。

这矛盾表明存在子序列{}，使得，从而

. （3.22）

由假设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.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）用

代替，定理仍然成立。

这个定理是基本的和一般的，当我们讨论每个具体的拟牛顿法的超线性收敛性时，都要验证充要条件（3.23）。

定理3.4设：，满足，设是非奇异矩阵序列。假定对某个，由

, （3.28）

产生的序列都在D中且收敛到。如果（2.23）成立，那么{}超线性收敛到且的充要条件是收敛到1.

证明 先假定{}超线性收敛到且。必有

， (3.29)

意味着

.

由于，故上式可写成

. （3.30）

由于非奇异。故存在，使得，又因{}超线性收敛。又有，从而有（3.2.23）得收敛到1.

下面我们进一步阐述拟牛顿法超线性收敛的几何意义。

设，又该序列的牛顿校正为。

由于，则

.

因此等价于

. （3.31）

上式表明当{}超线性收敛时，作为的近似向量，其对称误差应趋于零。容易证明这等价于要求无论在长度上还是方向上都趋向于。为此，我们建立以下引理。

引理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）

从而我们有结论：拟牛顿法超线性收敛的充分必要条件是其位移在长度和方向上都渐进的趋向于牛顿方向。

定理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

问题4

初始迭代点 =[0.4,1,0]

问题5

问题6

4.2 数值结果

上述模型所得的数值结果如下表所示，其中k表示迭代次数，t表示运算时间，b表示目标函数维数，val表示目标函数的最优值，表示初始迭代点。如下表4-1。

表4-1 数值结果：

总 结

本文提出了拟牛顿法的算法，并有程序实现。在程序实现过程中选用了Armijo非精确线搜索求步长。用BFGS校正求。同时对算法的收敛性进行了证明。同时对算法进行了数值验算，从而证明了算法的可行性和有效性。本文吸

取了大量前人的经验。因此比前人的拟牛顿法更为有效。收敛性证明更为完善。本文进一步工作将是提出更完善的拟牛顿算法。对其收敛性进行更完善的证明。同时把算法推广到更多的求解最优解问题上。

在毕业论文的写作过程中，我遇到了很多麻烦。刚开始拿到题，很是茫然。通过到图书馆，上网查阅资料。我逐渐掌握了大量的专业知识。扩充了自己对题目的认。，在编程调试的过程中，从刚开始的时候对matlab生疏，对算法的不明白。到最后能够顺利的编写出程序再调试成功。在这个过程中我学到了很多。让我明白了很多道理。要想做成功一件事，你必须要脚踏实地，有充分的准备。这样才能把每件事做好。

致 谢

光阴飞逝，转眼四年的大学生活就要结束了。在这四年时间里，很多同学和老师都给了我很多的帮助。至此论文完成之际，在此向尊敬的老师和亲爱的同学们表示深深的谢意。

我要对我的导师xx老师表示诚挚的感谢。，本学位论文是在她的悉心指导下完成的．在论文过程中，王老师表现出的严谨的治学态度，忘我的工作作风，还有对待学生的宽厚和耐心都令我深深地折服．她就像春天的风一样，当我气馁不安时，恰当的寥寥数语就能让我放下心头所有的包袱重获前进的动力；她也像炎热夏天的凉风，当我焦躁膨胀时，适时的给与警醒提示让我脚踏实地一步一个脚印的前进；她又像秋天的阳光，用她高洁的内涵和渊博的知识抚照着我做出成果；她更像数九严寒天绽放的寒梅，用她那不畏困难坚持向上的精神风貌感召着我永远向前．正是她的谆谆教导使我逐渐步入科学的殿堂，逐渐领悟到科研的乐趣，也正是她的谆谆教导和适时鼓励让我能放稳心态忌焦忌躁地完成各方面的工作．王老师教会我的东西将使我终生受益，即使步入新的学习和工作生活，我也会将导师的教诲铭记于心．

参考文献

[1] 时平平，王希云．基于新拟牛顿方程的拟牛顿法对一般目标函数的全局收敛性

[J]．太原科技大学学报，2008，6．

[2] 陈兰平，焦宝聪．非凸无约束优化问题的广义拟牛顿法的全局收敛性[J]-应用数学，2005，4：

573．579．

[3] 王希云，时平平．基于新拟牛顿方程的修改Broyden族的全局收敛性[J]．应

[4] 李董辉，童小娇，万中．数值最优化．北京：科学出版社，2005．1~98

[5] 袁亚湘，孙文瑜．最优化理论与方法．北京：科学出版社，1997．1～330

[7] Stanley C. Eisenstat Homer WalkerF. Globally convergent inexact Newton methods. SIAM, J.Opti. 1994 ,2:393—422

[8] Xu C．X，Zhang J．Z．A Survey of Quasi·Newton Equations and Quasi-Newton Methods for Optimization[J]．Annals of Operations Research，2001，103：213—234．

[9] Z．X．Wei，Q．X．Li．A new Huang class and its properties for unconstrained optimization problems． Journal of Mathematical Research and Exposition．2005，1：64—71

[10] HestenesMR，stiefel EL．Methodsofconjugate gradientsforsolvinglinearsystems，J Res，Nat Bur Standards [11] letcherR，Reeves C．Function minimizationby conjugategradients，computJ，1964，7：149。1 54

[12 ] Ya—Xiang Yuan，A Modified BFGS Algorithm for Unconstrained Optimization，IMA Journal of Numerical AnalysiS，1991，1 1：325—332．

[13] 赵云彬，易正俊．伪Newton一6族的导出和全局收敛性[J]．数值计算与计算机应用，1995，1：53-62．

[14] 陈兰平，王丽伟．广义拟牛顿算法对一般目标函数的收敛性[J]．应用数学，2002，15(3)：69-75．

[15] 杨晓光．一类拟牛顿算法的收敛性[C]．清华大学应用数学论文集，1991．113—117．

[16] A．Griewank，．The global convergence of partitioned BFGS on problems with convex decompositions and Lipschitzian gradients， Math．Programming，1991，50：141—175．

[18] Fletcher R．Practical Methods of Optimization v01．1：Unconstrained Optimization，New York．John Wiley&Sons，1987

附 录

源代码

function [data,uu,cc]=nfu(m,x)

%num---所要求解的题目编号,x0初始点，n是维数

tic

if size(x,1)==1,

x=x;

end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 初始化各个常量

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

n=length(x);

epsilon=1e-5;

rho=0.55;

sigma=0.4; %每次alpha缩小的倍数

c=0.1;

global F;

%F=strcat('of',num2str(num));%F='funnum'

F='of';

data.fk=of(x,m); %计算f0,

data.gk=gradientof(x,F,m)%计算g0

data.xk=x; %设初始点x0

data.bk=eye(n); %初始化B0

bk=data.bk;

data.k=0;

cc=cell(2*n,1);

while norm(data.gk,2)>epsilon

data.dk=-data.gk/data.bk; %解方程组, 计算搜索方向

data_old=data;

t=0; tk=0;

while (t<20) % 用Armijo搜索求步长

data.xk=data_old.xk+rho^t*data_old.dk; %计算新的试验点xk

xk=data.xk;

data.fk=of(xk,m);

data.gk=gradientof(data.xk,F,m);%计算g

if(data.fk

tk=t; break;

end

t=t+1;

end

%BFGS校正

data.xk=data_old.xk+rho^tk*data_old.dk;% x=x0+rho^mk*dk;

sk=data.xk-data_old.xk

yk= data.gk- data_old.gk

%yk=feval(gfun,x,varargin{:})-gk;

if(yk*sk'>0)

data.bk=data_old.bk-(data_old.bk*sk'*sk*data_old.bk)/(sk*data_old.bk*sk')+(yk'*yk)/(yk*sk');

end

data.k=data.k+1;

uu(data.k,1)=norm(data.gk,2); %记录f和theta的变化轨迹

uu(data.k,2)=data.fk;

uu(data.k,3)=rho^tk;

%uu

data_old=data;

end

data.uu=uu;

%data.cck=cck;

%data.xn=xn;

disp('f* : ');

disp(num2str(data.fk));

disp('x* : ')

disp(num2str(data.xk));

disp('迭代次数');

disp(num2str(data.k));

data=rmfield(data,{'gk';'dk'});

toc

学位论文原创性声明

本人郑重声明：所呈交的学位论文，是本人在导师的指导下进行的研究工作所取得的成果。尽我所知，除文中已经特别注明引用的内容和致谢的地方外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式注明并表示感谢。本人完全意识到本声明的法律结果由本人承担。

学位论文作者（本人签名）： 年 月 日

学位论文出版授权书

本人及导师完全同意《中国博士学位论文全文数据库出版章程》、《中国优秀硕士学位论文全文数据库出版章程》(以下简称“章程”)，愿意将本人的学位论文提交“中国学术期刊（光盘版）电子杂志社”在《中国博士学位论文全文数据库》、《中国优秀硕士学位论文全文数据库》中全文发表和以电子、网络形式公开出版，并同意编入CNKI《中国知识资源总库》，在《中国博硕士学位论文评价数据库》中使用和在互联网上传播，同意按“章程”规定享受相关权益。

论文密级：

□公开 □保密（___年__月至__年__月）(保密的学位论文在解密后应遵守此协议)

作者签名：_______ 导师签名：_______

_______年_____月_____日 _______年_____月_____日

独 创 声 明

本人郑重声明：所呈交的毕业设计(论文)，是本人在指导老师的指导下，独立进行研究工作所取得的成果，成果不存在知识产权争议。尽我所知，除文中已经注明引用的内容外，本设计（论文）不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明。

本声明的法律后果由本人承担。

作者签名:

二〇一〇年九月二十日

毕业设计（论文）使用授权声明

本人完全了解滨州学院关于收集、保存、使用毕业设计（论文）的规定。

本人愿意按照学校要求提交学位论文的印刷本和电子版，同意学校保存学位论文的印刷本和电子版，或采用影印、数字化或其它复制手段保存设计（论文）；同意学校在不以营利为目的的前提下，建立目录检索与阅览服务系统，公布设计（论文）的部分或全部内容，允许他人依法合理使用。

（保密论文在解密后遵守此规定）

作者签名:

二〇一〇年九月二十日

致 谢

时间飞逝，大学的学习生活很快就要过去，在这四年的学习生活中，收获了很多，而这些成绩的取得是和一直关心帮助我的人分不开的。

首先非常感谢学校开设这个课题，为本人日后从事计算机方面的工作提供了经验，奠定了基础。本次毕业设计大概持续了半年，现在终于到结尾了。本次毕业设计是对我大学四年学习下来最好的检验。经过这次毕业设计，我的能力有了很大的提高，比如操作能力、分析问题的能力、合作精神、严谨的工作作风等方方面面都有很大的进步。这期间凝聚了很多人的心血，在此我表示由衷的感谢。没有他们的帮助，我将无法顺利完成这次设计。

首先，我要特别感谢我的知道郭谦功老师对我的悉心指导，在我的论文书写及设计过程中给了我大量的帮助和指导，为我理清了设计思路和操作方法，并对我所做的课题提出了有效的改进方案。郭谦功老师渊博的知识、严谨的作风和诲人不倦的态度给我留下了深刻的印象。从他身上，我学到了许多能受益终生的东西。再次对周巍老师表示衷心的感谢。

其次，我要感谢大学四年中所有的任课老师和辅导员在学习期间对我的严格要求，感谢他们对我学习上和生活上的帮助，使我了解了许多专业知识和为人的道理，能够在今后的生活道路上有继续奋斗的力量。

另外，我还要感谢大学四年和我一起走过的同学朋友对我的关心与支持，与他们一起学习、生活，让我在大学期间生活的很充实，给我留下了很多难忘的回忆。

最后，我要感谢我的父母对我的关系和理解，如果没有他们在我的学习生涯中的无私奉献和默默支持，我将无法顺利完成今天的学业。

四年的大学生活就快走入尾声，我们的校园生活就要划上句号，心中是无尽的难舍与眷恋。从这里走出，对我的人生来说，将是踏上一个新的征程，要把所学的知识应用到实际工作中去。

回首四年，取得了些许成绩，生活中有快乐也有艰辛。感谢老师四年来对我孜孜不倦的教诲，对我成长的关心和爱护。

学友情深，情同兄妹。四年的风风雨雨，我们一同走过，充满着关爱，给我留下了值得珍藏的最美好的记忆。

在我的十几年求学历程里，离不开父母的鼓励和支持，是他们辛勤的劳作，无私的付出，为我创造良好的学习条件，我才能顺利完成完成学业，感激他们一直以来对我的抚养与培育。

最后，我要特别感谢我的导师赵达睿老师、和研究生助教熊伟丽老师。是他们在我毕业的最后关头给了我们巨大的帮助与鼓励，给了我很多解决问题的思路，在此表示衷心的感激。老师们认真负责的工作态度，严谨的治学精神和深厚的理论水平都使我收益匪浅。他无论在理论上还是在实践中，都给与我很大的帮助，使我得到不少的提高这对于我以后的工作和学习都有一种巨大的帮助，感谢他耐心的辅导。在论文的撰写过程中老师们给予我很大的帮助，帮助解决了不少的难点，使得论文能够及时完成，这里一并表示真诚的感谢。

精编完整版无约束最优化问题的拟牛顿法毕业论文设计