Hessian矩陣逆矩陣的近似

一、擬牛頓法的基本思路

????令H0,H1,H2,…表示Hessian矩陣逆矩陣F(x(k))?1的一系列近似矩陣。我們要討論的是這些近似矩陣應(yīng)該滿足的條件，這是擬牛頓法的基礎(chǔ)。首先，假定目標(biāo)函數(shù)f的Hessian矩陣F(x)是常數(shù)矩陣，與x無關(guān)，即目標(biāo)函數(shù)是二次型函數(shù)，F(x)=Q，Q=QT則：

g(k+1)?g(k)=Q(x(k+1)?x(k))
令
Δg(k)=g(k+1)?g(k)Δx(k)=x(k+1)?x(k)
可得
Δg(k)=QΔx(k)
記對(duì)稱正定實(shí)矩陣 H0作為近似矩陣的初始矩陣，在給定的 k下，矩陣Q?1應(yīng)該滿足：
Q?1Δg(i)=Δx(i),0≤i≤k
因此，近似矩陣 Hk+1應(yīng)該滿足
Hk+1Δg(i)=Δx(i),0≤i≤k
如果共展開 n次迭代，則共產(chǎn)生n個(gè)迭代方向 Δx(0),Δx(1),…,Δx(n?1)。由此可得 Hn應(yīng)該滿足條件：
HnΔg(0)=Δx(0)HnΔg(1)=Δx(1)?HnΔg(n?1)=Δx(n?1)
將其改寫為
Hn[Δg(0),Δg(1),…,Δg(n?1)]=[Δx(0),Δx(1),…,Δx(n?1)]
矩陣 Q能夠滿足：
Q[Δx(0),Δx(1),…,Δx(n?1)]=[Δg(0),Δg(1),…,Δg(n?1)]
和
Q?1[Δg(0),Δg(1),…,Δg(n?1)]=[Δx(0),Δx(1),…,Δx(n?1)]
這說明， 如果 [Δg(0),Δg(1),…,Δg(n?1)]非奇異，那么矩陣 Q?1能夠在 n次迭代之后唯一確定， 即
Q?1=Hn=[Δx(0),Δx(1),…,Δx(n?1)][Δg(0),Δg(1),…,Δg(n?1)]?1
由此，可得如果 Hn能夠使得方程 HnΔg(i)=Δx(i),0≤i≤n?1成立， 那么利用迭代公式 x(k+1)=x(k)?αkHkgk,αk=argmina≥0f(x(k)?αHkgk)求解 n維二次優(yōu)化問題，可得x(n+1)=x(n)?αnHngn,這與牛頓法的迭代公式是一致的， 說明能夠在 n+1次迭代內(nèi)完成求解。

二、 擬牛頓法的的迭代公式

????擬牛頓法的的迭代公式為：

d(k)=?Hkg(k)αk=argmina≥0f(x(k)+αd(k))x(k+1)=x(k)+αkd(k)
其中， H0,H1,H2,…是對(duì)稱矩陣。
????目標(biāo)函數(shù)為二次型函數(shù)時(shí)，它們必須滿足
Hk+1Δg(i)=Δx(i),0≤i≤k
其中， Δx(i)=x(i+1)?x(i)=αid(k),Δg(i)=g(i+1)?g(i)=QΔx(i)
實(shí)際上，擬牛頓法也是一種共軛方法。

三、定理

????將擬牛頓法應(yīng)用到二次型問題中， Hessian矩陣為Q=QT， 對(duì)于0≤k≤n?1, 有：

Hk+1Δg(i)=Δx(i),0≤i≤k 其中Hk+1=HTk+1。如果αi≠0,0≤i≤k, 那么d(0)，d(1)，?，d(k+1)是Q共軛的。

????由以上定理可知，對(duì)于n維二次型問題，擬牛頓法最多經(jīng)過n部迭代即可求出最優(yōu)解。注意，矩陣Hk并不能唯一確定，這就給計(jì)算矩陣Hk的自由發(fā)揮空間。

總結(jié)

以上是生活随笔為你收集整理的最优化学习笔记(十六)——拟牛顿法(2)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。