最速下降法与牛顿法及其区别

1、最速下降法与牛顿法及其区别摘要：无约束优化方法是优化技术中极为重要和基本内容之一。它不仅可以直接用来求解无约束优化问题，而且很多约束优化问题也常将其转化为无约束优化问题，然后用无约束优化方法来求解。最速下降法和牛顿法是比较常见的求解无约束问题的最优化方法，这两种算法作为基本算法，在最优化方法中占有重要的地位。其中最速下降法又称梯度法，其优点是工作量少，存储变量较少，初始点要求不高；缺点是收敛慢，效率低。牛顿法的优点是收敛速度快；缺点是对初始点要求严格，方向构造困难，计算复杂且占用内存较大。同时，这两种算法的理论和方法渗透到许多方面，特别是在军事、经济、管理、生产过程自动化、工程设计和产品优化设

2、计等方面都有着重要的应用。因此，研究最速下降法和牛顿法的原理及其算法对我们有着及其重要的意义。关键字：无约束优化 最速下降法 牛顿法 Abstract: unconstrained optimization method is to optimize the technology is extremely important and basic content of. It not only can be directly used to solve unconstrained optimization problems, and a lot of constrained optimizati

3、on problems are often transformed into unconstrained optimization problem, and then use the unconstrained optimization methods to solve. The steepest descent method and Newton-Raphson method is relatively common in the unconstrained problem optimization method, these two kinds of algorithm as the ba

4、sic algorithm, the optimization method plays an important role in. One of the steepest descent method also known as gradient method, its advantages are less workload, storage variable is less, the initial requirements is not high; drawback is the slow convergence, low efficiency. Newtonian method ha

5、s the advantages of fast convergence speed; drawback is the initial point of strict construction difficulties, directions, complicated calculation and larger memory. At the same time, these two kinds of algorithm theory and methods into many aspects, especially in the military, economic, management,

6、 production process automation, engineering design and product optimization design has important applications. Therefore, to study the steepest descent method and Newton-Raphson method principle and algorithm for us with its important significance.Keywords: unconstrained optimization steepest descen

7、t method1、 算法的基本原理1. 1 最速下降法的基本原理在基本迭代公式中，每次迭代搜索方向取为目标函数的负梯度方向，即，而每次迭代的步长取为最优步长，由此确定的算法称为最速下降法。为了求解问题，假定我们已经迭代了次，获得了第个迭代点。现在从出发，可选择的下降方法很多，一个非常自然的想法是沿最速下降方向（即负梯度方向)进行搜索应该是有利的，至少在邻近的范围内是这样。因此，去搜索方向为.为了使目标函数在搜索方向上获得最多的下降，沿进行一维搜索，由此得到第个跌带点，即，其中步长因子按下式确定， . （1）显然，令就可以得到一个点列,其中是初始点，由计算者任意选定。当满足一定的条件时，由式（

8、1）所产生的点列必收敛于的极小点。下面为书写方便，记。因此.1.2 牛顿法的基本原理设最优化问题为，其中二阶可导，矩阵正定。不妨设经过次迭代已获点，现将在处展成二阶泰勒公式，于是有显然是二次函数，特别由假设知还是正定二次函数，所以是凸函数且存在唯一全局极小点。为求此极小点，令即可解得，亦即 。 （2）对照基本迭代公式易知，式（2）中的搜索方向 ， （3）步长因子。换句话说从点出发沿搜索方向并取步长即可得的极小点。因此，是直指点处近似二次函数的极小点的方向。此时称为从点出发的方向。从初始点开始，每一轮从当前迭代点出发，沿方向并取步长的算法称为牛顿法。2、 算法的迭代步骤及流程图2.1 最速下降法

9、迭代步骤已知目标函数及其梯度，终止限和.（1） 选定初始点，计算；置.（2） 作直线搜索：；计算.用终止准则检验是否满足：若满足，则打印最优解，结束；否则，置，转（2）（3） 最速下降法算法流程图如图所示.结束 终止准则满足？ 选定开始YN2.2 牛顿法迭代步骤已知目标函数及其梯度，矩阵，终止限.（1） 选定初始点；计算；置.（2） 计算.（3） 由方程解出.（4） 计算.（5） 判别终止准则是否满足：若满足，则打印最优解结束；否则，置，转（2）。牛顿法的流程如图所示。终止准则满足？ 开始选定 N Y结束3、 实例分析分别用牛顿法和最速下降法求解,选取.3.1 最速下降法求解由题意可知，故.记

10、，则.为最佳步长，应满足.则有或故有.继续迭代，要经过10次迭代才可满足精度的要求，以下计算从略。3.2 牛顿法求解由题意可知,故有是正定矩阵。又.由（3）式计算.由计算.计算为故有.停止迭代，并输出作为极小点。4、 算法的优缺点分析4.1 最速下降法的优缺点分析最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，且对初始点要求不高，即使从一个不好的初始点出发，往往也能收敛到局部极小点，但它有一个严重缺点就是收敛速度慢，特别是当椭圆比较扁平时，最速下降法的收敛速度越慢。4.2 牛顿法的优缺点分析牛顿法收敛速度非常快，具有二次收敛的优点，但它存在下面四个严重的缺点：（1） 每次迭代不能保证下降，当矩阵非正定时，牛顿法的搜索将会失败；（2） 对初始点要求严格，一般要求比较接近或有利于接近极小点，但这在实际生活中很难办到；（3） 在进行迭代时可能求不出搜索方向；（4） 构造困难，计算复杂，占用机器内存较大。5、 设计总结通过上面的实例中两种算法的对比，可以看出牛顿法对于二次正定函数只需作一次迭代就得到最优解，特别是在极小点附近，收敛性很好、速度快，而最速下降法在极小点附近收敛速度很差。但牛顿