第6章梯度法为基础的数值求解.课件.ppt

1、梯度法为基础的数值求解内容提要最优梯度法共轭梯度法牛顿法及阻尼牛顿法变尺度法无约束非线性问题的数值求解，应用于连续可导的目标函数。以梯度法为基础，要计算目标函数的一阶和二阶偏导数。1.最优梯度法目标函数的负梯度方向作为每一步迭代的搜索方向，每一步都取负梯度方向的最优步长。（柯西提出）n维非线性函数f(X)的梯度定义如下：12(),nfffff XXxxx1.最优梯度法最优梯度法的迭代公式1kkkkXXS其中单位向量和最优步长分别是：()()kkkf XSf X()TkkTkkf X SS AS1.最优梯度法迭代过程1.最优梯度法收敛准则梯度准则：梯度的模达到充分小点距准则：相邻两迭代点之间的距

2、离达到充分小函数下降量准则：相邻两迭代点的函数值下降量达到充分小1()kf X1kkXX1()()kkf Xf X优缺点分析优缺点分析最速下降方向是局部性质而非全局性质开始步长大，越接近极小点，步长越小。所以在开始范围能较快接近最优点，适合解决问题的开始阶段，作为收局结尾是不利的（一般是锯齿状的收敛方向）1.最优梯度法2.共轭梯度法对负梯度方向进行修正（Fletcher&Reeves）kP()kf XkX1kP每一步迭代均利用上一步的 的负梯度方向 与上一步搜索方向的向量 进行线性组合，构成一个与 方向互相共轭的方向 然后再沿 方向做唯一寻优1kPkP2.共轭梯度法共轭方向的构成迭代公式条件：

3、 与 关于 互为共轭，即近似的取 为11()kkkkPf XP 1kPkPQ1()0kTkPQPk212()()kkkf Xf X 对于正定的二次函数， ，最多经过n次迭代就能得到最优点nXE2.共轭梯度法迭代过程3.牛顿法及阻尼牛顿法（1）牛顿法）牛顿法又叫二阶梯度法，不仅考虑了目标函数的梯度，而且考虑了目标函数的二阶导数（即梯度的变化方向），能更快的搜索出最优点。 其迭代公式如下：11()kkkkXXAf X3.牛顿法及阻尼牛顿法迭代过程优缺点分析收敛速度很快用到了赫森矩阵，考虑了等值线曲率的意义在极值点附近可以一步到达计算繁琐有可能是发散的NY*kXX停0,0nXE给出0k ()kf X

4、计算()?kf X11kAAA计算11()1kkkkXXAf Xkk3.牛顿法及阻尼牛顿法（2）阻尼牛顿法）阻尼牛顿法解决了牛顿法的计算繁琐问题，构造一个矩阵代替牛顿法中的赫森矩阵。因迭代过程中使用最优步长，故能保障每步函数值都有所下降，即使初始点选取不当，也能搜索成功。 其迭代公式如下：111()()kkkkkkkAf XXXf XA3.牛顿法及阻尼牛顿法A）当 时，则为最优梯度公式：B）当 时，则为牛顿法迭代公式：kAI1()kkkAf X1()()kkkkkf XXXf X11()kkkkXXAf X4.变尺度法变尺度法是结合最优梯度法和牛顿法的优点一种综合算法，也称为拟牛顿法。这种方法用一个对称矩阵 去逼近 ，得到的搜索方向为： 其迭代公式为：kH1kA()kkkPHf X 1kkkkXXP迭代过程NY0?g*kXX停000,()HI gf X0,0nXE给 出0k kkkPH g ,min()()kkkkkkf XPf XP求使1kkkkXXP1?kg*1kXX停?kn0nXX11,kkkkkkkkkkggXZBCHHBC计算1kkYYNN4.变尺度法算法特点算法特点以逐次逼近的算法实现对 的计算当目标函数可以用二次函数近似时，其方向矩阵 可以很快收敛应用于二次函数时，变尺度法与共轭梯度法一样具有二次终结性质，计算具有稳定性。1AH谢谢 谢！谢！