本章要点最速下降法的基本思想及特点牛顿方向newton法

《本章要点最速下降法的基本思想及特点牛顿方向newton法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本章要点：最速下降法的基本思想及特点牛顿方向Newton法基本思想及特点共轭方向、共轭方向法的基本定理共轭梯度法基本思想拟Newton法的基本思想第四章无约束非线性问题的解法学习的重要性：1、直接用于无约束的实际问题；2、其基本思想和逻辑结构可以推广到约束问题；3、约束问题可以转化成无约束问题求解。方法分类：1、间接法：对简单问题，求解必要条件或充分条件；2、迭代算法：零阶法：只需计算函数值f(x)一阶法：需计算▽f(x)二阶法：需计算▽2f(x)直接法梯度法本章主要介绍无约束最优化方法，它的应用比较广泛，理论比较成熟。另一方面，通常可以把一些约束优化问题转化为无约

2、束问题来处理，所以它是最优化方法中的基本方法。这些方法通常要用到函数的一阶或二阶导数。在实际问题中，也常遇到函数的解析表达式比较复杂，有的甚至写不出明显的解析表达式，因而导数很难求出或无法求出，这时基于梯度的方法不能用，需要采取另一种所谓的直接法（或直接搜索法）。直接法是仅仅利用函数值的信息，去寻找最优解的一类方法。在后面第九章有介绍。考虑无约束优化问题：直接搜索法收敛速度一般比较慢，需要计算大量的函数值。梯度反映了函数值变化的规律，充分利用梯度信息构造算法，能加速收敛。使用函数的梯度（一阶导数）或Hesse矩阵（二阶导数）的优化算法统称为梯度法。算法目标：求出平稳

3、点（满足f(x)=0的x*）。由于f(x)=0一般是非线性方程组，解析法往往行不通，所以梯度法通常是逐次逼近的迭代法。假定：f(x)和2f(x)连续存在§4.1最速下降法(Cauchy法)（一）基本思想x(k+1)=x(k)+tkd(k)x(k)x*d(k)=－f(x(k))x(k+1)d(k+1)=－f(x(k+1))瞎子下山：由于他看不到哪里是山谷，不可能沿直接指向山谷的路线走，他只能在当前位置上，靠手杖作局部探索，哪里最陡就往哪里前进一步，然后在新的位置上再用手杖寻找最陡方向，再下降一步。这就是最速下降法的形象比喻。？多变量最优化迭代解法的一般迭代

4、公式：可用一维搜索技术解决关键是如何确定搜索方向d(k)最速下降法迭代公式x(k+1)=x(k)－tkf(x(k))1847年Cauchy提出。特点是直观易懂，但收敛速度慢。下面看一下理论推导：设函数f(x)在xk附近连续可微，且gk=f(xk)≠0，由Taylor展式可知，若记x-xk=tdk，则满足(dk)Tgk<0的方向dk是下降方向。当t取定后，(dk)Tgk的值越小，即-(dk)Tgk的值越大，函数下降的越快。由Cauchy-Schwartz不等式当且仅当dk=-gk时，(dk)Tgk最小，从而-gk是最速下降方向。最速下降法的迭代格式为：（二）算法开

5、始给定x(0),M,1,2,令k=0计算f(x(k))

6、

7、f(x(k))

8、

9、<1否k>Mx*=x(k)是结束是一维搜索求tk精度为2否x(k+1)=x(k)－tkf(x(k))k=k+1（三）最速下降法的搜索路径呈直角锯齿形定理4.1设从点x(k)出发，沿方向d作精确一维搜索，tk为最优步长因子，即f(x(k)+tkdk)=minf(x(k)+tdk)则成立f(x(k)+tkd)Td=0,即新点处的梯度与搜索方向垂直。即t>0x(k+1)d(k)x(k)f(x)等值面f(x(k+1))tkd(k+1)二维情形下最速下降法搜索路径：由此可以看出，最速

10、下降法仅是算法的局部性质。对于许多问题，全局看最速下降法并非“最速下降”，而是下降的较缓慢。数值试验表明，当目标函数的等值线接近于一个圆（球）时，最速下降法下降较快，而当目标函数的等值线是一个扁长的椭球时，最速下降法开始几步下降较快，后来由于出现“锯齿”现象，下降就比较缓慢。x(0)x(1)x(2)f(x(k+1))Tdk=0，即f(x(k+1))Tf(x(k))=dk+1Tdk=0，这表明在相邻的两个迭代点上函数f(x)的两个梯度方向是互相直交的，即，两个搜索方向互相直交，这就产生了锯齿形状。当接近极小点时，步长愈小，前进愈慢。这就造成了最优步长的最速下降法

11、逼近极小点过程是“之”字形，并且越靠近极小点步长越小，移动越慢，以至在实际运用中在可行的计算时间内得不到需要的结果。这似乎与“最速下降”的名称矛盾。其实不然，因为梯度是函数局部性质，从局部看，函数在这一点附近下降的很快，然而从整体看，则走过了许多弯路，因此反而是不好的。其原因就是精确一维搜索（最优步长）满足为了清除最优步长最速下降法中两个搜索方向正交的不良后果，人们发现了不少方法，如：(1)选择不同初始点例：问题：取初点为求，沿方向从出发求的极小点即进行线搜索则解得然后再从开始新的迭代，经过10次迭代，得最优解计算中可以发现，开始几次迭代，步长比较大，函数值下将