牛顿法与修牛顿法

1、牛顿法与修正牛顿法牛顿法与修正牛顿法 牛顿牛顿 简介简介 艾萨克艾萨克牛顿（牛顿（isaac newton）是英国伟大的）是英国伟大的数学家、物理学家、天文学家数学家、物理学家、天文学家和和自然哲学家自然哲学家，其研究领域包括了其研究领域包括了物理学、数学、天文学、物理学、数学、天文学、神学、自然哲学和炼金术神学、自然哲学和炼金术。 牛顿的主要贡献有发明了牛顿的主要贡献有发明了微积分微积分，发现了，发现了万有引力定律万有引力定律和和经典力学经典力学，设计并实际制造了，设计并实际制造了第一架第一架反射式望远镜反射式望远镜等等，被誉为人类历史上等等，被誉为人类历史上最伟大，最有影响力的最伟大，最有

2、影响力的科学家科学家。为了纪念牛顿。为了纪念牛顿在经典力学方面的杰出成就，在经典力学方面的杰出成就，“牛顿牛顿”后来成为后来成为衡量衡量力力的大小的物理单位。的大小的物理单位。牛顿法牛顿法 1.1.基本思想基本思想 在求目标函数在求目标函数 的极小值时，先将它在的极小值时，先将它在 点附近展开点附近展开成泰勒级数的二次函数式，然后求出函数的极小值点，并以此点作成泰勒级数的二次函数式，然后求出函数的极小值点，并以此点作为欲求目标函数的极小值点为欲求目标函数的极小值点 的一次近似值的一次近似值。 设目标函数是连续二阶可微的，将函数在点设目标函数是连续二阶可微的，将函数在点 按泰勒级数按泰勒级数展开

3、，并取到二次项：展开，并取到二次项：)(kx)()(21 )()()()()()()()()()()()(kktkktkkkxxxhxxxxxfxfxxf)(xf)(kx*x对对x x求导，其极值点必满足一阶导数为零，所以，求导，其极值点必满足一阶导数为零，所以，得到得到 式中式中， 为为hessianhessian矩阵的逆矩阵。矩阵的逆矩阵。 0)()()()()()()(kkkxhxxxfxxfx)()()(1)()(minkkkxfxhxx1)()(kxh 1 在一般情况下，在一般情况下， 不一定是二次函数，因而不一定是二次函数，因而 也不也不可能是可能是 的极值点。但是在的极值点。但是

4、在 点附近，函数点附近，函数 和和 是近似的，所以可以用是近似的，所以可以用 点作为下一次迭代，点作为下一次迭代，即得即得 如果目标函数如果目标函数 是正定二次函数，那么是正定二次函数，那么 是个常矩阵，是个常矩阵，逼近式逼近式 是准确的。因此由是准确的。因此由 点出发只要迭代一次既可点出发只要迭代一次既可以求以求 的极小点。的极小点。)(xfminx)(xf)(kx)1( kx)(x)(xf)(xf)(kx)(xf)()()(1)()(1kkkkxfxhxx 1 2)(xh)(xf)(kx 1 )(xh 在一般情况下，在一般情况下， 不一定是二次函数，因而不一定是二次函数，因而 也不也不可能

5、是可能是 的极值点。但是在的极值点。但是在 点附近，函数点附近，函数 和和 是近似的，所以可以用是近似的，所以可以用 点作为下一次迭代，点作为下一次迭代，即得即得 如果目标函数如果目标函数 是正定二次函数，那么是正定二次函数，那么 是个常矩阵，是个常矩阵，逼近式逼近式 是准确的。因此由是准确的。因此由 点出发只要迭代一次既可点出发只要迭代一次既可以求以求 的极小点。的极小点。)(xf)(xf)(kx 1 )(xh 式与一维搜索公式式与一维搜索公式 比较，则有搜索方向比较，则有搜索方向 ， 步长因子步长因子 )()()()1(kkkksxx)()()(1)()(ktkkxfxhs1)(k 2)(

6、)()1()(1)()()()(kkkkkksxxxfxhs牛顿法的牛顿法的迭代算式迭代算式其中其中 称为称为牛顿方向。牛顿方向。)(ks2.2.迭代步骤迭代步骤 一一 给定给定初始点初始点 ，计算精度，计算精度，令，令k=0k=0； 二二 计算计算 点的梯度点的梯度 、 及其逆矩阵及其逆矩阵 。 三三 构造搜索方向构造搜索方向)0(x)(kx)()(kxf)()(kxh1)()(kxh)()()(1)()(kkkxfxhs 四四 沿沿 方向进行一维搜索，得迭代点方向进行一维搜索，得迭代点 五五 收敛判断：收敛判断：若若 ，则，则 为近似最优点，迭代停止，为近似最优点，迭代停止， 输出最优解输

7、出最优解 和和 终止计算。终止计算。若不满足，令若不满足，令k=k+1，转第二步继续迭代。，转第二步继续迭代。)(ks)()()1(kkksxx)()1(kxf)1( kx)1(minkxx)()()1(minkxfxf3.3.举例举例 用牛顿法求函数用牛顿法求函数 的极小值。的极小值。60410)(21212221xxxxxxxf解：解：(1)(1)取初始点取初始点(2)(2)计算牛顿方向计算牛顿方向00)0(x41042102)()0(1221xxxxxxxf2112)(222122212212)0(xfxxfxxfxfxh211231)(1)0(xh68182431410211231 )

8、()()0(1)0()0(xfxhs故故(3)(3)极小值极小值8)(min6868*100)0()0()0(1xfsxx由由matlab得到得到 的曲面和等值线，如下图所示的曲面和等值线，如下图所示)(xf 数学分析表明，牛顿法具有很好的局部收敛性质，对数学分析表明，牛顿法具有很好的局部收敛性质，对二次函数来说，仅一步就达到优化点，二次函数来说，仅一步就达到优化点， 但对一般函数来说，在一定条件下，当初始点的选取但对一般函数来说，在一定条件下，当初始点的选取充分接近目标函数的极小点时，有很快的收敛速度，但若充分接近目标函数的极小点时，有很快的收敛速度，但若初始点选取离最小点比较远，就难保证收

9、敛；初始点选取离最小点比较远，就难保证收敛； 牛顿法必须求一阶、二阶导数及求逆阵，这对较复杂牛顿法必须求一阶、二阶导数及求逆阵，这对较复杂的目标函数来说，是较困难的。的目标函数来说，是较困难的。修正牛顿法修正牛顿法 当目标函数为非二次函数时，目标函数在 点展开所得的二次函数是该点附近的一种近似表达式，所求的极小点，当然也是近似的，需要继续迭代。但是当目标函数严重非线性时，用式 进行迭代则不能保证一定收敛，即在迭代中可能会出现 ，所得到的下一点不如原来的好。这和初始点的选择是否恰当有很大的关系。)()()()1(kkxfxfkx2 为了克服牛顿法的上述缺陷，可以通过在迭代中引入步长因子和一维搜索

10、加以解决，即令 式中， -一维搜索所得的最优步长因子。 因而将 称为牛顿方向。 经过这种修改后的算法称为修正牛顿法。也称牛顿方向法or阻尼牛顿法。 3)()()(1)()()()1(kkkkkxfxhxx)(k)()()(1)()(kkkxfxhs举例举例：用修正牛顿法求解下列无约束优化问题，已知：用修正牛顿法求解下列无约束优化问题，已知解：因为所以22122210422)(. 1 . 0,) 1, 1 (xxxxxxfx()(2121211)(;24)(4222)(;42422)()0(1)0()0(1)0()0()0(2121xfxhsxhxfxhxxxxxf由修正牛顿法，得带入原函数对 求导解得代入因为 故迭代终止；所以最优解为1012)31 (2)1 (6)1 (4)31 (6)()()31 (4)1)(31 (2)1 (2)31 ()(131131122)1()0()0()1(xfsxx8)(241311311)1()0()0()1(xfsxx1 . 00|)(|,00)()1()1(xfxf8)(,24min)1(minxfxx牛顿法的评价牛顿法的评价由于采用了目标函数的二阶导数信息，收敛速度比梯度法快。牛顿法迭代公式与一般迭代公式的区别在于，没有最优步长因子。这使得在接近最优点时，由于步长不