牛顿法，高斯牛顿法以及L-M法的详细推导.pdf-资料库

在工程实际问题的优化设计中，所列的目标函数往往很复杂，为了使问题简化，常常将目标函数在某点邻域展开成泰勒多项式来逼近原函数。泰勒公式： )( xf  )( af !0  )(' axaf  !1 ( )  f )('' axa  !2 ( 2 ) ...  f )( n )( a ! n ( nx  ) n  )( xR n 牛顿法解方程牛顿法是用一个二次函数去近似一个目标函数，然后精确地求出这个二次函数的极小点，以它作为目标函数极小点 x 的近似值。  xf 在 x  处的一阶泰勒展开式为： kx  )( xf  ( k ) ( xf )  f (' x ( k ) )( x  x ( k ) ) 令   0xf ，得：通过变换得出： 0  ( k ) ( xf )  f (' x ( k ) )( x  x ( k ) ) x  x ( k )  ( k ) ( k ( xf (' f x ) ) ) 由此得出迭代公式： x ( k )1  x ( k )  ( k ) ( k ( xf (' f x ) ) ) 迭代原理如下图所示，这里  kx 表示第 k 步迭代时的 x 取值， x 表示精确解，这个迭代过程就是不断逼近 x 的过程，其实就是不断地用曲线的切线与 x 轴交点的横坐标来近似表达曲线与 x 轴交点的横坐标，所以牛顿法也叫切线法。

牛顿最优化方法(一维变量) 最优化问题其实就是求解一个目标函数  xf 的极大极小值问题，即求解方程   0 ' xf 的解，可以利用上述牛顿法进行求解。若一元函数  xf 在处的泰勒展开式为： x  点的某个邻域内具有任意阶导数，则  xf 在   kx kx 点 )( xf  ( k ) ( xf )  f (' x ( k ) ) x  1 2 f ('' x ( k ) )(  x ) 2  其中 x  ( x  ( kx 2) ) 。对  xf 求导得： f )(' x  ( k ) f (' x )  f ('' x ( k ) )( x  x ( k ) ) 0  ( k ) f (' x )  f ('' x ( k ) )( x  x ( k ) ) 令   0 ' xf 可得：求解该方程可得：

x  x ( k )  f f (' x ('' x ( k ) ( k ) ) ) 由此得出迭代公式： x ( k )1  x ( k )  f f 牛顿最优化方法(多维变量) ( k ) ( k (' x ('' x ) ) ) 由一元函数  xf 在  kx 点处的泰勒展开式： )( xf  ( k ) ( xf )  f (' x ( k ) ) x  1 2 f ('' x ( k ) )(  x ) 2  其中 x  ( x  ( kx 2) ) 。可得二元函数 ( , 1 xxf 2 ) 在 X ( k ) k ) ( x ( 1 , ) x ( k 2 ) 点处的泰勒展开式为： ( , xxf 1 2 )  k ) ( ( xf 1 , ) x ( k 2 )  f  x  1 ( k ) X x  1 f  x  2 ( k ) X x  2 1 2     2  x  f 2 1 x  2 1 2 2 f  xx  1 2 ( k ) X ( k ) X xx  1 2 2  x  f 2 2  x 2 2     ( k ) X  其中， x  1 x 1  k ) ( x 1 , x  2 x 2  ) x ( k 2 。将上式以矩阵形式展开，则有： ( Xf )  ( Xf ( k ) )     f  x  1 , f  x  2       x  1 x  2    1 2 ( k ) X  x  1 , x 2 即：其中： ( Xf )  ( Xf ( k ) )  ( Xf ( k ) T ) X  1 2        2 f  2 x  1 2 f  xx  2 1 2 f  xx  1 2 f  2 x  2 2       ( k ) X    x  1 x  2    T XHX ( ( k ) ) X  XH ( ( k ) )        2 f  2 x  1 2 f  xx  2 1 2 f  xx  1 2 f  2 x  2 2       ( k ) X , X     x  1 x  2   ，  ( Xf ( k ) )     f  x  1 , f  x  2    T ( k ) X 称 (kXH ( ) ) 为 ( , 1 xxf 2 ) 在 ) (kX 点处的 Hessian 矩阵。它是由函数 ( , 1 xxf 2 ) 在

) (kX 点处的二阶偏导数所组成的方阵。将二元函数的泰勒展开式推广到多元函数，则 , ( xxf 1 2 ,  在 ) (kX 点处的 nx ) , 泰勒展开式的矩阵形式为： ( Xf )  ( Xf ( k ) )  ( Xf ( k ) T ) X  1 2 T XHX ( ( k ) ) X  其中： (1)  ( Xf ( k ) )     f  x  1 , f  x  2 ,  f  x  n    (2) XH ( ( k ) )            2 f  2 x  1 2 f  xx  2 1  2 f  xx  1 n 2 2 f  xx  1 2 f  2 x  2  2 f  xx  n 2 T ( k ) X     ，它是函数 (Xf 在 ) (kX 点处的梯度。 ) n n 2 f  xx  1 2 f  xx  2  2  x  f 2 n           ( kX ) 为函数 (Xf 在 ) (kX 点处的 ) Hessian 矩阵。       X  (3) 2 x  1 x   x  n    ,    x  1 x 1  k ) ( x 1 , x  2 x 2  ) x ( k 2 ,  x  n x n  ) x ( k n Hessian 矩阵是由目标函数 f 在点 X 处的二阶偏导数组成的 nn 阶对称矩阵。令  Xf ( )  0 ，即：

 , ( xxf 1 2 )  ( ( xf 1 k ) , ) x ( k 2 )      f  x  1 x  1 f  x  ( k ) X 2 ( k ) X  x 2     1 2          2  x  f 2 1 x  2 1 2 2 f  xx  1 2 ( k ) X ( k ) X xx  1 2 2  x  f 2 2  x 2 2         ( k ) X       0 0    ( k ) X  f  x  1 0         0   f   x   2     ( k ) X  x 1       2  x  f 2 1 0       ( k ) X ( k ) X              2 f  xx  1 2 f  xx  1 2  x 2 x 1  2 f  x  1 f  x  2       ( k ) X   ( Xf ( k ) )  2     x   0 f  2 2 x 2     x  1 2 f  xx  2 1 2 f  2 x  2 x  1                   ) ( k 2 X f  2 x  1 2 f  xx  1 2 2 f  2 x  1 2 f  xx  2 1 ( k ) X  x 2  x 2       ( k ) X    x  1 x  2          ) ) 2 2 f  xx  1 2 f  2 x  2  ( x x   ) 1 1 ( k x x   2 2  ( ) XX  k k ) ( k ) X      ( Xf ( k ) )  XH ( ( k ) ( Xf ( k ) )  XH ( ( k )  0  即：(求导过程也可参考矩阵分析 P108) ) XX )( XH (  k k ( ) ( )  - ( Xf ( k ) ) 若 Hessian 矩阵正定，则 ( kXH ( ) )  1 存在，则解上式得出的 X  1 kX ，就是函数 (Xf 的极小点，即： ) ( k )1  X ( k )  X  XH ( ( k )  1 )  ( Xf ( k ) ) 用 1kX 作为 (Xf 极小点 X 的新的近似。上式就是牛顿迭代公式。 )

高斯牛顿法有时候为了拟合数据，常常将要求解的模型转化为非线性最小二乘问题。高斯牛顿法正是用于解决非线性最小二乘问题，以达到数据拟合、参数估计和函数估计的目的，其基本思想是使用泰勒级数展开式去近似地代替非线性回归模型，然后通过多次迭代，多次修正回归系数，使回归系数不断逼近非线性回归模型的最佳回归系数，最后使原模型的残差平方和达到最小。其实，高斯牛顿法是牛顿法在求解非线性最小二乘问题时的一个特例。通常情况下非线性最小二乘问题都可表示为： min Rx  n ( Xf )  1 2 其中， ( XrXr ( ) T )  1 2 m  i 1   ( Xr i 2  ) , nm  X   , xx 1  , 2 T , nx ( Xr )   ( XrXr 1 ), ( 2 ),  , ( m Xr T ) 这里要解决的是非线性问题， ) (Xri 为残量函数，是 X 的非线性函数。当 nm  时，该方程组称为超定方程组；当 nm  时，称为确定方程组。假设对 ) (Xr 的第i 个分量 ) (Xri 在 ) (kX 处泰勒展开，得： ( Xr i )  ( Xr i ( k ) )  ( Xr i ( k ) T )  X ( Xr )  ( Xr ( k ) )  ( XJ ( k ) )  X 为 ) (Xr 在 ) (kX 处的 Jacobin 矩阵，进而推广出 ) (Xr 的 Jacobin 则：其中 (kXJ ( ) ) 矩阵为：         ) ) ) ( Xr  1 x  1 ( Xr  2 x  1  ( Xr  m x  1           ) ) )     ( Xr  1 x  2 ( Xr  2 x   ( Xr  m x  2 2 ( Xr  1 x  n ( Xr  2 x   ( Xr  m x  n n ) ) )           T T ) ) T ) ( XJ )            ( Xr 1 ( Xr 2  ( Xr m 则 (Xf 的梯度为： )

 ( Xf )  )  )  ( Xrd dX  T ) ( Xg  1  2   ( Xrd dX  ( ), Xr   1 T ( ( ) XrXJ   ( Xr ) ( Xr 2 ) T  ( Xr )  T  )  ( Xrd dX ( Xr )    ),  ,  XrXr m ( ) (  ) (Xf 的 Hessian 矩阵为： ) 2  ( Xf ) T ) ( ( XH   ( XrXJ   ( XJd dX  ( Xr  1 ) ) ),  d  T ( Xr )  )   ),  ( Xr 2 dX  ( ), ), ( Xr Xr   2 1  2 2 ), ( ( Xr Xr   2 1 T ) ) ( ( XJXJ 2 ) () ( ( XrXr XJXJ  ( ) ( ( ) XS XJXJ   ,  ,   ), ) )  T ( T )  ( Xrd dX ,   T  ) ) ( XJ  ) Xr m ( ( Xr )   ) ( ( XJXr m  2 ) ( XrXr  m ) ( )  因此，目标函数 (Xf 在 ) (kX 点处的二次泰勒展开式为： ) ( Xf )  ( Xf ( k ) )  ( Xg ( k ) ) 1 X  2  ( XJ  k ( T XHX ( ) T ) ( Xr (  X X  ( ) ) k k T )  )  X   1 2 1 2 ( Xr ( k ) T ) ( Xr ( k ) )  T XSX (  ( k ) )  ( XJ ( k ) T ) ( XJ ( k ) ) 将 (XH 和 ) (Xg 带入牛顿法迭代公式便得到解决上述非线性最小二乘问题 ) 的牛顿迭代公式：  )1  k ( X  ( k ) ( k ) X X   ( XH  ( XS ( k ) ( k ) ) )  1  ( Xg ( XJ ( k ) ( k ) ) ) T ( XJ ( k ) 1   ) ( XJ ( k ) T ) ( Xr ( k ) ) 高斯牛顿法是通过舍弃其 Hessian 矩阵的二阶偏导数实现的，也就是忽略 ( (XS 的重要性，而且由于其计算量较大，所以令中的二阶信息项 ) ) 2 Xf ( XS ) 0 ，则 (Xf 在 ) (kX 点处的二次泰勒展开式成为： )

( Xf )  1 2 1 2 ( Xr ( k ) T ) ( Xr ( k ) )   ( XJ T ( Xr ( k ) T  ) X   T XJX (  ( k ) T ) ( XJ ( k ) ) ( ) k )  X  因此，Gauss-Newton 法的第 K 次迭代公式为： ( k )1  X ( k )  X  ( XJ  ( k ) T ) ( XJ ( k ) 1   ) ( XJ ( k ) T ) ( Xr ( k ) ) Levenberg-Marquardt 方法在 Gauss-Newton 算法的迭代过程中要求矩阵 (kXJ ( ) ) 为满秩的，但是 (kXJ ( ) ) 奇异的情形经常发生，这会使得算法经常收敛到一个驻点，算法只有局部收敛的特性，这个时候 Gauss-Newton 法就会出现不好用甚至不能用的情况。为了克服这个困难，考虑信赖域策略，因为通常情况下 ) (Xr 是非线性函数，而 Gauss-Newton 法用线性化模型代替 ) (Xr ，这样可以得到最小二乘问题，这种线性化并不是对所有的 ( 即考虑信赖域策略： x  都成立，因此我们考虑约束线性最小二乘问题， ) kx ( XJ ( k ) )  X 2 min  ( Xr ( k ) ) .t.s  X  2  ( k ) h 这个模型的解可以由解下列方程组来表征：  ( XJ ( k ) T ) ( XJ ( k ) )   ( sIu k )  ( XJ ( k ) T ) ( Xr ( k ) ) 这其实相当于是 L-M 算法对高斯牛顿法做出了改进，加入了一个正定对角矩阵，从而有： ( k )1  X ( k )  X  ( XJ  ( k ) T ) ( XJ ( k ) )  k ) ( Iu 1   ( XJ ( k ) T ) ( Xr ( k ) ) 其中， I 是一个单位矩阵， ) (ku 是一个正实数。当 ) ( ku 0 时，L-M 算法退化为高斯牛顿算法。当 ) (ku 很大时， X ( k )1  X ( k )  ( XJ ( k ) T ) ( Xr ( k ) ) ，此时 L-M 算法退化为梯度下降法。 ) (ku 的值会随着优化的进行状态随时进行自适应调整，这个参数控制着 X 前进的方向，也控制着前进的步长。

资料库

牛顿法，高斯牛顿法以及L-M法的详细推导.pdf

相关推荐

人工智能

热门标签

最新资料