Welcome To My Blog
牛頓法和擬牛頓法是求解無約束最優(yōu)化問題的常用方法,優(yōu)點(diǎn)是收斂速度快.
牛頓法是迭代算法,每一步需要求解目標(biāo)函數(shù)的Hessian矩陣的逆矩陣,矩陣的逆運(yùn)算很耗時(shí).
擬牛頓法通過正定矩陣近似Hessian矩陣的逆矩陣或Hessian矩陣,簡化Hessian矩陣的求逆計(jì)算過程
采用線搜索框架
1.png
搜索方向由牛頓法或擬牛頓法給出,步長可以通過精確線搜索或非精確線搜索獲得
關(guān)于步長,之前的文章有提過:Line search and Step length線搜索與步長
牛頓法
- 假設(shè)f(x)具有二階連續(xù)偏導(dǎo)數(shù).要求解的無約束最優(yōu)化問題是min f(x),x*標(biāo)識目標(biāo)函數(shù)f(x)的極小點(diǎn).
- 若第k次迭代值為x(k),則可將f(x)在x(k)附近進(jìn)行二階泰勒展開(Taylor expansion):
2.png - 函數(shù)f(x)有極值的必要條件是在極值點(diǎn)處一階導(dǎo)數(shù)為0,即梯度向量為0.特別地,當(dāng)H(x^(k))是正定矩陣時(shí),函數(shù)f(x)的極值為極小值.
- 牛頓法利用極小點(diǎn)的必要條件▽f(x)=0
- 每次迭代中從點(diǎn)x(k)開始,求目標(biāo)函數(shù)的極小點(diǎn),作為第k+1次迭代值x(k+1).具體地,假設(shè)x(k+1)滿足▽f(x(k+1))=0
- 由二階泰勒展開,對f(x)關(guān)于(x-x^(k))求梯度得:
3.png - 將x^(k+1)帶入上面的梯度公式:
4.png
算法流程
5.png
擬牛頓法
牛頓法算法流程的步驟(4)涉及Hessian矩陣的求逆,計(jì)算復(fù)雜,所以有其它改進(jìn)的方法,比如
6.png
先看牛頓法迭代中Hessian矩陣H_k滿足的條件,進(jìn)而引出擬牛頓條件.
7.png
下面說明如果H_k正定,則牛頓法的搜索方向是下降方向
8.png
擬牛頓法是用一個(gè)n階矩陣G_k去近似Hessian矩陣的逆,所以矩陣G_k需要滿足Hessian矩陣滿足的條件
9.png
每次迭代時(shí)需要更新G_k矩陣,更新方法有多種類選擇,主要介紹下Broyden類擬牛頓法
DFP算法
DFP(Davidon-Flectcher-Powell)算法選擇G_(k+1)的方法是:
10.png
進(jìn)一步,關(guān)于P_k,Q_k
11.png
P_k,Q_k如上取值的可行性證明:
12.jpg
14.png
DFP算法流程
13.png
BFGS算法
BFGS(Broyden-Flectcher-Goldfarb-Shanno)算法是最流行的擬牛頓算法.
15.png
16.png
17.png
BFGS算法流程
18.png
DFP和BFGS的迭代公式很像
19.png
Broyden類算法
Sherman-Morrison公式
20.png
Broyden類
21.png
22.png
參考:
李航,統(tǒng)計(jì)學(xué)習(xí)方法
