阻尼牛顿法定稿[中小学堂]

1、LOGO 牛顿法与阻尼牛顿法牛顿法与阻尼牛顿法 团队成员：崔尚 金英博 郭向姝 多丽娅 赵丽霞 窦永贵 尹逊增 宋红喜 陈建 王思远 冯文秀 牛顿法主讲：崔尚 阻尼牛顿法主讲：金英博 牛顿法牛顿法 1.1.基本原理基本原理 在第在第K K次迭代的迭代点次迭代的迭代点 的邻域内，把的邻域内，把 展开成展开成 泰勒级数的泰勒级数的二次函数式二次函数式去近似代替原目标函数去近似代替原目标函数 ，然后，然后 求出该求出该二次函数二次函数的极小点，作为对原目标函数求优的下一个的极小点，作为对原目标函数求优的下一个 迭代点迭代点，依此类推，通过多次重复迭代，使迭代点逐步逼近，依此类推，通过多次重复迭代，使

2、迭代点逐步逼近 原目标函数的极小点。原目标函数的极小点。 )(k x )(xF )(xF 2课堂特制 . 释图： 3课堂特制 设目标函数是连续二阶可微的，将函数在点设目标函数是连续二阶可微的，将函数在点 按按 泰勒级数展开，并取到二次项：泰勒级数展开，并取到二次项： )(k x )()( 2 1 )()()()()( )()()( )()()()( kkTk kTkkk xxxHxx xxxfxfxxf 4课堂特制 对对x x求导，其极值点必满足一阶导数为零，所以，求导，其极值点必满足一阶导数为零，所以， 得到得到 式中，式中， 为为HessianHessian矩阵的逆矩阵。矩阵的逆矩阵。 0

3、)()( )( )( )()()( kkk xHxxxf x xf x )()( )( 1 )()( min kkk xfxHxx 1 )( )( k xH 1 5课堂特制 )(xf min x )(xf )(k x )1( k x )(x )(xf )(xf )()( )( 1 )()(1kkkk xfxHxx 2 )(xH )(k x )(xf 1 6 课堂特制课堂特制 式与一维搜索公式 比较，则有搜索方向 ， 步长因子 )()()()1(kkkk sxx )()( )( 1 )()(kTkk xfxHs 1 )( k 2 )()()1( )( 1 )()( )()( kkk kkk sx

4、x xfxHs 牛顿法的牛顿法的 迭代算式迭代算式 其中其中 称为称为牛顿方向。牛顿方向。 )(k S 7 课堂特制课堂特制 2.2.迭代步骤迭代步骤 一一 给定给定初始点初始点 ，计算精度，计算精度，令，令k=0k=0； 二二 计算计算 点的梯度点的梯度 、 及其逆矩阵及其逆矩阵 。 三三 构造搜索方向构造搜索方向 )0( x )(k x)( )(k xf)( )(k xH 1 )( )( k xH )()( )( 1 )()(kkk xfxHs 8课堂特制 四四 沿沿 方向进行一维搜索，得迭代点方向进行一维搜索，得迭代点 五五 收敛判断：收敛判断： 若若 ，则，则 为近似最优点，迭代停止，

5、为近似最优点，迭代停止， 输出最优解输出最优解 和和 终止计算。终止计算。 若不满足，令若不满足，令k=k+1，转第二步继续迭代。，转第二步继续迭代。 )(k s )()()1(kkk sxx )( )1(k xf )1( k x )1( min k xx )()( )1( min k xfxf 9课堂特制 原始牛顿法的特点原始牛顿法的特点 若用原始牛顿法求某二次目标函数的最优解，若用原始牛顿法求某二次目标函数的最优解， 则构造的逼近函数与原目标函数是完全相同的二次式，则构造的逼近函数与原目标函数是完全相同的二次式， 其等值线完全重合，故从任一点出发，一定可以一次其等值线完全重合，故从任一点出

6、发，一定可以一次 达到目标函数的极小点。达到目标函数的极小点。 因此，牛顿法是具有二次收敛性的算法。其因此，牛顿法是具有二次收敛性的算法。其优点优点 是：对于二次正定函数，迭代一次即可以得到最优解，是：对于二次正定函数，迭代一次即可以得到最优解， 对于非二次函数，若函数二次性较强或迭代点已经进对于非二次函数，若函数二次性较强或迭代点已经进 入最优点的较小邻域，则收敛速度也很快。入最优点的较小邻域，则收敛速度也很快。 原始牛顿法的原始牛顿法的缺点缺点是：由于迭代点的位置是按照是：由于迭代点的位置是按照 极值条件确定的，并未沿函数值下降方向搜索，因此，极值条件确定的，并未沿函数值下降方向搜索，因此

7、， 对于非二次函数，有时会使函数值上升，即对于非二次函数，有时会使函数值上升，即 f(xk+1) f(xk)，而使计算失败。，而使计算失败。 10课堂特制 . 11课堂特制 3.3.举例举例 用牛顿法求函数用牛顿法求函数 的极小值。的极小值。 60410)( 2121 2 2 2 1 xxxxxxxf 解：解： (1)(1)取初始点取初始点 (2)(2)计算牛顿方向计算牛顿方向 0 0 )0( x 4 10 42 102 )( )0( 12 21 xx xx xx xf 12课堂特制 21 12 )( 2 2 2 12 2 21 2 2 1 2 )0( x f xx f xx f x f xH

8、 21 12 3 1 )( 1 )0( xH 6 8 18 24 3 1 4 10 21 12 3 1 )()( )0( 1 )0()0( xfxHs 故故 (3)(3)极小值极小值 8)(min 6 8 6 8 0 0 )0()0(1 xf sxx 13课堂特制 数学分析表明，牛顿法具有很好的局部收敛性质，对数学分析表明，牛顿法具有很好的局部收敛性质，对 二次函数来说，仅一步就达到优化点，二次函数来说，仅一步就达到优化点， 但对一般函数来说，在一定条件下，当初始点的选取但对一般函数来说，在一定条件下，当初始点的选取 充分接近目标函数的极小点时，有很快的收敛速度，但若充分接近目标函数的极小点时

9、，有很快的收敛速度，但若 初始点选取离最小点比较远，就难保证收敛；初始点选取离最小点比较远，就难保证收敛； 牛顿法必须求一阶、二阶导数及求逆阵，这对较复杂牛顿法必须求一阶、二阶导数及求逆阵，这对较复杂 的目标函数来说，是较困难的。的目标函数来说，是较困难的。 14课堂特制 1 ()() ()() kk f Xf X 牛顿法的缺点：由于迭代公式中没有 步长因子，而是定步长迭代，对于非二次 型目标函数，有时会使函数值上升，即出 现的情况，这表明牛顿 法不能保证函数值稳定的下降，有时甚至 迭代发散，从而导致计算失败。 为了消除牛顿法的弊病，提出了”阻尼 牛顿法。 15课堂特制 阻尼牛顿法的迭代公式阻

10、尼牛顿法的迭代公式 1 11 ()()() () ()()() ()()()()() () )() , min )() kkk k kkk kkkkk k SH Xf X fXS XXH Xf X 阻尼牛顿法的迭代方向依然与牛顿法一样，采用牛 顿方向： -（ 但每次迭代需沿此方向作一维搜索，求其最优步长因子 使得 将牛顿法的迭代公式改为 （ 此即阻尼牛顿法的迭代公式。称为阻尼因子，通 () () ) k f X H X 过牛顿方向进行一维搜索获得。当目标函数的赫 森矩阵 （处处正定时，阻尼牛顿法能保证每次迭 代点的目标函数值均为下降，从而保持了二次收敛的 特性。 16课堂特制 阻尼牛顿法的计算

11、过程和算法框阻尼牛顿法的计算过程和算法框 图图 0 (1) (2) 0k () , n XR n 阻尼牛顿法的具体迭代步骤如下： 给定初始点迭代精度 ， 维数 。 置 17课堂特制 12 222 12 (3) () ()()() () ()()() () ()()() (), ()()() ()()()() k kkk kT n kkk k n X fXfXfX fX xxx fXfXfX fX xxx 计算迭代点的梯度 计算梯度的模 18课堂特制 1 1 (4) 5 6 () ()* ()* ()()() ()()() () () ()() ( )(),() () )() k k k kkk

12、 kkk k f X XX f Xf X XH XHX SH Xf X X 检验是否满足迭代终止条件？ 若满足，停止迭代，输出最优解：， 。否则进行下一步。 计算处的并求其逆。 计算牛顿方向 -（ 从点出发，沿牛顿方向进行一维搜索求最优 () ()()() , min k kkk fXS 步 长使得 19课堂特制 (k+1)(k)(k)(k) (7) XXS 计算迭代新点 = (8) 13,( )kk 置返回步骤进行下一次 迭代计算。 12 222 12 (3) () ()()() () ()()() () ()()() (), ()()() ()()()() k kkk kT n kkk k

13、 n X f Xf Xf X f X xxx f Xf Xf X f X xxx 计算迭代点的梯度 计算梯度的模 20课堂特制 阻尼牛顿法计算框图阻尼牛顿法计算框图 否 停 1()()()()kkkk XSX ()() (),() kk f Xf X计算： () ()? k f X 1kk 0 k0 () ,Xn给定初始值：，。置 。 ()()()() ,min kkkk fXS求使得 ()* ()* ()() k k XX f Xf X 输出：， 。 是 1() () k HX 计算： 1 ()()() )() kkk H Xf XS -（ 21课堂特制 阻尼牛顿法算例阻尼牛顿法算例 22

14、1212 (0) ()4(1)2(2)10 0 00.01 fxxxx, , T X X 已知目标函数 设初始点迭代梯度精度 ，试用阻尼牛顿 法求目标函数的极小点和极小值。 22课堂特制 )(),( )()(kk XfXf计算 22)0( 79)(Xf ）（XH ）（01 计算 7 7 23课堂特制 )()( ) 0 (1) 0 () 0 ( XfXHS T XfXHS 4 7 8 9 7 9 4/10 08/1 )()( )0(100 (3) 牛顿方向 7 7 10 4 7 8 9 )2 4 7 (2)1 8 9 (4)( 22 aaaaaf 24课堂特制 7 7 8125.10 ?)( )

15、 1 ( Xf 25课堂特制 验证算法的准确性验证算法的准确性 Fminsearch（）函数作 用是找出使这个目标函数 最小化的x值。 26课堂特制 27课堂特制 首先，注意到 时， 所以该问题的目标函 数有极小值，梯度和Hesse矩阵如下： 梯度 ，Hesse阵 ，若取初始点 ，则对应的梯度 ， Hesse矩阵的逆 此时牛顿方向 不是目标函数的下降方向，牛顿迭代点 对应的 函数值 ，经过数值实验可以看出，牛 顿法不能求出目标函数的极小值。 求解二维优化问题求解二维优化问题 2 221 4 1 )1 ()(minxxxxxf x)( xf )1(2 4 )( 21 2 3 1 xx xx xf

16、 21 112 )( 2 12 x xf T x0 , 0 0 T xf)2 , 0()( 01 12 )( 12 xfT S)0 , 2( 0 T x)0 , 2( 1 1)(17)( 01 xfxf 28课堂特制 另外，当沿着方向 进搜索时，由于目标函数 所以线搜索的最小点仍为 ，无法应用阻尼牛顿法解决 该问题。 0 S 116)( 400 aaSxf 0 x 0 )( da adf 0a )0()0()0()0()1( XSaXX 29课堂特制 求目标函数 极小点，初值 此时Hesse矩阵奇异，故无法求出它的逆阵，阻尼牛顿法到 此不能继续进行。 2 2 3 1 xxy 2 2 1 2 3

17、 )( x x xf 20 00 20 06 )( 1)0(2 x xf T x0 , 0 0 30课堂特制 （阻尼）牛顿法的困难（阻尼）牛顿法的困难 应用牛顿法的主要困难是Hesse矩阵可能奇异，或 者接近奇异；即使该矩阵是可逆的，它也未必是 正定矩阵。此时，导出的牛顿法迭代格式的二次 函数不一定有极小点，甚至没有驻点。为了保证为了保证 近似目标函数的二次函数是严格凸的，存在极小近似目标函数的二次函数是严格凸的，存在极小 点，就需要对二次函数的点，就需要对二次函数的Hesse矩阵进行修正。矩阵进行修正。 修正牛顿法的基本思想是：在确定搜索方向时， 对Hesse矩阵增加一个校正矩阵，使之正定，这样 可以保证搜索方向是目标函数的下降方向目标函数的下降方向。 31课堂特制 简介几种修正方法简介几种修正方法 32课堂特制 牛顿法的效能特点牛顿法的效能特点 牛顿 而牛顿法不仅使用函数 法具有二次收敛性 的一阶导数，还进一步 利用了二阶导数，较好的考虑了梯度的变化趋势， 因而能够更全面的确定合适的搜索方向