一、牛顿法回顾
- 上一篇牛顿法(Newton Method)中介绍了牛顿法的基本思路,牛顿法具有二阶收敛性,相比较最速下降法,收敛的速度更快。
- 但是牛顿法也有一个缺点就是:求解Hessian矩阵复杂度比较大
1、下面是第k+1步的牛顿迭代:
- 对于函数
f(X),其中
X=[x1,x2,…,xn]T为向量。在牛顿法的求解过程中,首先是将
f(X)函数在
Xk+1处展开,并且令
f(X)函数在
Xk+1处的梯度为:
∇f(Xk+1)=[∂x1∂f,∂x2∂f,…,∂xn∂f]T
- 泰勒展开为:
f(X)=f(Xk+1)+∇f(Xk+1)T(X−Xk+1)+21(X−Xk+1)TGk+1(X−Xk+1)+⋯+o
-
Gk+1为X=Xk+1的Hesse矩阵,省略高价无穷小量:
f(X)=f(Xk+1)+∇f(Xk+1)T(X−Xk+1)+21(X−Xk+1)TGk+1(X−Xk+1)
- 对
X求导,并令导数为
0:
∇f(X)=∇f(Xk+1)T+Gk+1(X−Xk+1)=0
- 求出
X:
X=Xk+1−Gk+1∇f(Xk+1)=Xk+1−Gk+1−1∇f(Xk+1)
二、DFP拟牛顿法:
- 由于求解Hessian矩阵复杂度比较大,于是下面我们利用上一步即第
k步的信息来求Hessian矩阵:
- 上面得到公式:
∇f(X)=∇f(Xk+1)+Gk+1(X−Xk+1)
- 我们令
X=Xk:
∇f(Xk)=∇f(Xk+1)+Gk+1(X−Xk+1)
- 利用上面公式我们可以使用
∇f(Xk),∇f(Xk+1),Xk,Xk+1来模拟出Hesse矩阵的构造过程,此方法便称为拟牛顿法(QuasiNewton)。
- 在拟牛顿法中主要包括:DFP拟牛顿法,BFGS拟牛顿法。这里我们讲解DFP拟牛顿法。
- 化解上面式子:
Gk+1−1(∇f(Xk)−∇f(Xk+1))=Xk−Xk+1
Gk+1−1(∇f(Xk+1)−∇f(Xk))=Xk−1−Xk
- 令
Gk+1−1=Hk+1得:
Hk+1(∇f(Xk+1)−∇f(Xk))=Xk−1−Xk
- 假设下面式子成立:
Hk+1=Hk+Ek
- 这样只要我们求出
Ek就就可以得到
Hk+1,这样我们就将其带入上面的方程中:
(Hk+Ek)(∇f(Xk+1)−∇f(Xk))=Xk+1−Xk
- 令矩阵
Ek用下面式子构造:
Ek=αukukT+βvkvkT其中
uk,vk为
n×1的向量。
- 令:
∇f(Xk+1)−∇f(Xk)=yk,Xk−1−Xk=sk:
Hk+1yk=sk
(Hk+Ek)yk=sk
(Hk+αukukT+βvkvkT)yk=sk
αukukTyk+βvkvkTyk=sk−Hkyk
-
ukTyk,vkTyk为常数,所以可以移到前面去:
α(ukTyk)uk+β(vkTyk)vk=sk−Hkyk
- 将上面式子中α,β视为变量,其他部分视为常量,这样上面式子就是一个非齐次的线性方程组,它解的可能性有很多,我们取特殊的情况,假设:
uk=rHkyk,vk=θsk则有:
Ek=αr2HkykykTHkT+βθ2skskT
-
HkT为对称矩阵:
Ek=αr2HkykykTHk+βθ2skskT
- 代入:
α((rHkyk)Tyk)(rHkyk)+β((θsk)Tyk)(θsk)=sk−Hkyk
[αr2(ykTHkyk)+1](Hkyk)+[βθ2(skTyk)−1](sk)=0
- 令:
αr2(ykTHkyk)+1=0
βθ2(skTyk)−1=0
- 得:
αr2=−ykTHkyk1
βθ2=skTyk1
- 最后:
Ek=−ykTHkykHkykykTHk+skTykskskT
- 由
Hk+1=Hk+Ek可得到,
Hk+1的递推公式:
Hk+1=Hk−ykTHkykHkykykTHk+skTykskskT
更多精彩内容