《阻尼牛顿法定稿.ppt.ppt》由会员分享，可在线阅读，更多相关《阻尼牛顿法定稿.ppt.ppt（35页珍藏版）》请在三一办公上搜索。
1、牛顿法与阻尼牛顿法,团队成员：崔尚 金英博 郭向姝 多丽娅 赵丽霞 窦永贵 尹逊增 宋红喜 陈建 王思远 冯文秀牛顿法主讲：崔尚阻尼牛顿法主讲：金英博,牛顿法 1.基本原理 在第K次迭代的迭代点 的邻域内，把 展开成泰勒级数的二次函数式去近似代替原目标函数，然后求出该二次函数的极小点，作为对原目标函数求优的下一个迭代点，依此类推，通过多次重复迭代，使迭代点逐步逼近原目标函数的极小点。,.,释图：,Company Logo,设目标函数是连续二阶可微的，将函数在点 按泰勒级数展开，并取到二次项：,对x求导，其极值点必满足一阶导数为零，所以，得到 式中，为Hessian矩阵的逆矩阵。,在一般情况下，
2、不一定是二次函数，因而 也不可能是 的极值点。但是在 点附近，函数 和 是近似的，所以可以用 点作为下一次迭代，即得 如果目标函数 是正定二次函数，那么 是个常矩阵，逼近式 是准确的。因此由 点出发只要迭代一次既可以求 的极小点。,式与一维搜索公式 比较，则有搜索方向，步长因子,牛顿法的迭代算式,其中 称为牛顿方向。,2.迭代步骤 一 给定初始点，计算精度，令k=0；二 计算 点的梯度、及其逆矩阵。三 构造搜索方向,四 沿 方向进行一维搜索，得迭代点 五 收敛判断：若，则 为近似最优点，迭代停止，输出最优解 和 终止计算。若不满足，令k=k+1，转第二步继续迭代。,。,原始牛顿法的特点 若用原
3、始牛顿法求某二次目标函数的最优解，则构造的逼近函数与原目标函数是完全相同的二次式，其等值线完全重合，故从任一点出发，一定可以一次达到目标函数的极小点。因此，牛顿法是具有二次收敛性的算法。其优点是：对于二次正定函数，迭代一次即可以得到最优解，对于非二次函数，若函数二次性较强或迭代点已经进入最优点的较小邻域，则收敛速度也很快。原始牛顿法的缺点是：由于迭代点的位置是按照极值条件确定的，并未沿函数值下降方向搜索，因此，对于非二次函数，有时会使函数值上升，即 f(xk+1)f(xk)，而使计算失败。,.,3.举例 用牛顿法求函数 的极小值。,解：(1)取初始点(2)计算牛顿方向,故,(3)极小值,数学分
4、析表明，牛顿法具有很好的局部收敛性质，对二次函数来说，仅一步就达到优化点，但对一般函数来说，在一定条件下，当初始点的选取充分接近目标函数的极小点时，有很快的收敛速度，但若初始点选取离最小点比较远，就难保证收敛；牛顿法必须求一阶、二阶导数及求逆阵，这对较复杂的目标函数来说，是较困难的。,阻尼牛顿法的迭代公式,阻尼牛顿法的计算过程和算法框图,阻尼牛顿法计算框图,阻尼牛顿法算例,(3)牛顿方向,OK,验证算法的准确性,Fminsearch（）函数作用是找出使这个目标函数最小化的x值。,首先，注意到 时，所以该问题的目标函数有极小值，梯度和Hesse矩阵如下：梯度，Hesse阵，若取初始点，则对应的梯
5、度，Hesse矩阵的逆 此时牛顿方向 不是目标函数的下降方向，牛顿迭代点 对应的函数值，经过数值实验可以看出，牛顿法不能求出目标函数的极小值。,求解二维优化问题,另外，当沿着方向 进搜索时，由于目标函数 所以线搜索的最小点仍为，无法应用阻尼牛顿法解决该问题。,求目标函数 极小点，初值此时Hesse矩阵奇异，故无法求出它的逆阵，阻尼牛顿法到此不能继续进行。,（阻尼）牛顿法的困难,应用牛顿法的主要困难是Hesse矩阵可能奇异，或者接近奇异；即使该矩阵是可逆的，它也未必是正定矩阵。此时，导出的牛顿法迭代格式的二次函数不一定有极小点，甚至没有驻点。为了保证近似目标函数的二次函数是严格凸的，存在极小点，就需要对二次函数的Hesse矩阵进行修正。修正牛顿法的基本思想是：在确定搜索方向时，对Hesse矩阵增加一个校正矩阵，使之正定，这样可以保证搜索方向是目标函数的下降方向。,简介几种修正方法,牛顿法的效能特点,缺点：1.对目标函数要求高。函数必须具有连续的一阶、二阶偏导数。同时其赫森矩阵必须正定且非奇异性。2.计算复杂。计算梯度外，还要计算其二阶偏导数，矩阵的逆。,变尺度法利用了梯度法和牛顿法的优点，先用梯度法，后用牛顿法并避开Hesse矩阵及其逆的计算。,Thank You!,
