阻尼牛顿法定稿-课件

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