【优化方法】拟牛顿法之DFP算法

一、牛顿法回顾

  • 上一篇牛顿法(Newton Method)中介绍了牛顿法的基本思路,牛顿法具有二阶收敛性,相比较最速下降法,收敛的速度更快。
  • 但是牛顿法也有一个缺点就是:求解Hessian矩阵复杂度比较大

1、下面是第k+1步的牛顿迭代:

  • 对于函数 f ( X ) f(X) ,其中 X = [ x 1 , x 2 , , x n ] T X=[x_1,x_2,…,x_n ]^T 为向量。在牛顿法的求解过程中,首先是将 f ( X ) f(X) 函数在 X k + 1 X^{k+1} 处展开,并且令 f ( X ) f(X) 函数在 X k + 1 X^{k+1} 处的梯度为: f ( X k + 1 ) = [ f x 1 , f x 2 , , f x n ] T ∇f(X^{k+1} )=[\frac{∂f}{∂x_1},\frac{∂f}{∂x_2},…,\frac{∂f}{∂x_n}]^T
  • 泰勒展开为: f ( X ) = f ( X k + 1 ) + f ( X k + 1 ) T ( X X k + 1 ) + 1 2 ( X X k + 1 ) T G k + 1 ( X X k + 1 ) + + o f(X)=f(X^{k+1})+∇f(X^{k+1} )^T (X-X^{k+1})+\frac{1}{2} (X-X^{k+1} )^T G_{k+1} (X-X^{k+1})+⋯+o
  • G k + 1 X = X k + 1 G_{k+1}为X=X^{k+1} 的Hesse矩阵,省略高价无穷小量: f ( X ) = f ( X k + 1 ) + f ( X k + 1 ) T ( X X k + 1 ) + 1 2 ( X X k + 1 ) T G k + 1 ( X X k + 1 ) f(X)=f(X^{k+1})+∇f(X^{k+1} )^T (X-X^{k+1})+\frac{1}{2} (X-X^{k+1} )^T G_{k+1} (X-X^{k+1})
  • X X 求导,并令导数为 0 0 f ( X ) = f ( X k + 1 ) T + G k + 1 ( X X k + 1 ) = 0 ∇f(X)=∇f(X^{k+1} )^T+G_{k+1} (X-X^{k+1})=0
  • 求出 X X X = X k + 1 f ( X k + 1 ) G k + 1 = X k + 1 G k + 1 1 f ( X k + 1 ) X=X_{k+1}-\frac{∇f(X^{k+1} )}{G_{k+1}} =X_{k+1}-G_{k+1}^{-1} ∇f(X^{k+1} )

二、DFP拟牛顿法:

  • 由于求解Hessian矩阵复杂度比较大,于是下面我们利用上一步即第 k k 步的信息来求Hessian矩阵:
  • 上面得到公式: f ( X ) = f ( X k + 1 ) + G k + 1 ( X X k + 1 ) ∇f(X)=∇f(X^{k+1} )+G_{k+1} (X-X^{k+1} )
  • 我们令 X = X k X=X^k f ( X k ) = f ( X k + 1 ) + G k + 1 ( X X k + 1 ) ∇f(X^k)=∇f(X^{k+1} )+G_{k+1} (X-X^{k+1} )
  • 利用上面公式我们可以使用 f ( X k ) , f ( X k + 1 ) , X k , X k + 1 ∇f(X^k ),∇f(X^{k+1} ),X^k,X^{k+1} 来模拟出Hesse矩阵的构造过程,此方法便称为拟牛顿法(QuasiNewton)。
  • 在拟牛顿法中主要包括:DFP拟牛顿法,BFGS拟牛顿法。这里我们讲解DFP拟牛顿法。
  • 化解上面式子: G k + 1 1 ( f ( X k ) f ( X k + 1 ) ) = X k X k + 1 G_{k+1}^{-1}(∇f(X^k )-∇f(X^{k+1} ))=X^k-X^{k+1} G k + 1 1 ( f ( X k + 1 ) f ( X k ) ) = X k 1 X k G_{k+1}^{-1}(∇f(X^{k+1} )-∇f(X^k ))=X^{k-1}-X^k
  • G k + 1 1 = H k + 1 G_{k+1}^{-1}=H_{k+1} 得: H k + 1 ( f ( X k + 1 ) f ( X k ) ) = X k 1 X k H_{k+1}(∇f(X^{k+1} )-∇f(X^k ))=X^{k-1}-X^k
  • 假设下面式子成立: H k + 1 = H k + E k H_{k+1}=H_k+E_k
  • 这样只要我们求出 E k E_k 就就可以得到 H k + 1 H_{k+1} ,这样我们就将其带入上面的方程中: ( H k + E k ) ( f ( X k + 1 ) f ( X k ) ) = X k + 1 X k (H_k+E_k)(∇f(X^{k+1} )-∇f(X^k ))=X^{k+1}-X^k
  • 令矩阵 E k E_k 用下面式子构造: E k = α u k u k T + β v k v k T E_k=αu_k u_k^T+βv_k v_k^T 其中 u k , v k u_k,v_k n × 1 n×1 的向量。
  • 令: f ( X k + 1 ) f ( X k ) = y k X k 1 X k = s k ∇f(X^{k+1} )-∇f(X^k )=y_k,X^{k-1}-X^k=s_k : H k + 1 y k = s k H_{k+1} y_k=s_k ( H k + E k ) y k = s k (H_k+E_k)y_k=s_k ( H k + α u k u k T + β v k v k T ) y k = s k (H_k+αu_k u_k^T+βv_k v_k^T)y_k=s_k α u k u k T y k + β v k v k T y k = s k H k y k αu_k u_k^T y_k+βv_k v_k^T y_k=s_k-H_k y_k
  • u k T y k , v k T y k u_k^T y_k,v_k^T y_k 为常数,所以可以移到前面去: α ( u k T y k ) u k + β ( v k T y k ) v k = s k H k y k α(u_k^T y_k)u_k+β(v_k^T y_k)v_k=s_k-H_k y_k
  • 将上面式子中α,β视为变量,其他部分视为常量,这样上面式子就是一个非齐次的线性方程组,它解的可能性有很多,我们取特殊的情况,假设: u k = r H k y k , v k = θ s k u_k=rH_k y_k,v_k=θs_k 则有: E k = α r 2 H k y k y k T H k T + β θ 2 s k s k T E_k=αr^2 H_k y_k y_k^T H_k^T+βθ^2 s_k s_k^T
  • H k T H_k^T 为对称矩阵: E k = α r 2 H k y k y k T H k + β θ 2 s k s k T E_k=αr^2 H_k y_k y_k^T H_k+βθ^2 s_k s_k^T
  • 代入: α ( ( r H k y k ) T y k ) ( r H k y k ) + β ( ( θ s k ) T y k ) ( θ s k ) = s k H k y k α((rH_k y_k )^T y_k)(rH_k y_k)+β((θs_k )^T y_k)(θs_k)=s_k-H_k y_k [ α r 2 ( y k T H k y k ) + 1 ] ( H k y k ) + [ β θ 2 ( s k T y k ) 1 ] ( s k ) = 0 [αr^2 (y_k^T H_k y_k )+1](H_k y_k )+[βθ^2 (s_k^T y_k )-1](s_k)=0
  • 令: α r 2 ( y k T H k y k ) + 1 = 0 αr^2 (y_k^T H_k y_k )+1=0 β θ 2 ( s k T y k ) 1 = 0 βθ^2 (s_k^T y_k )-1=0
  • 得: α r 2 = 1 y k T H k y k αr^2=-\frac{1}{y_k^T H_k y_k } β θ 2 = 1 s k T y k βθ^2=\frac{1}{s_k^T y_k}
  • 最后: E k = H k y k y k T H k y k T H k y k + s k s k T s k T y k E_k=-\frac{H_k y_k y_k^T H_k}{y_k^T H_k y_k }+\frac{s_k s_k^T}{s_k^T y_k }
  • H k + 1 = H k + E k H_{k+1}=H_k+E_k 可得到, H k + 1 H_{k+1} 的递推公式: H k + 1 = H k H k y k y k T H k y k T H k y k + s k s k T s k T y k H_{k+1}=H_k-\frac{H_k y_k y_k^T H_k}{y_k^T H_k y_k }+\frac{s_k s_k^T}{s_k^T y_k }

更多精彩内容