假設(shè))
是
上具有二階連續(xù)偏導(dǎo)數(shù)的函數(shù)，要求解的無約束最優(yōu)化問題是
%5Ctag1)
表示目標(biāo)函數(shù)的極小點(diǎn)挑社。
在牛頓法的迭代中，需要計(jì)算海塞矩陣的逆矩陣
巡揍，這一計(jì)算比較復(fù)雜痛阻，考慮用一個(gè)
階矩陣%7D))
來近似代替%7D))
。這就是擬牛頓法的基本想法腮敌。
假設(shè)在第
次迭代時(shí)阱当，找到的點(diǎn)是%7D)
，讓在點(diǎn)附近進(jìn)行二階泰勒展開：
%3Df(x%5E%7B(k)%7D)%2Bg_k%5ET(x-x%5E%7B(k)%7D)%2B%5Cfrac12(x-x%5E%7B(k)%7D)%5ETH(x%5E%7B(k)%7D)(x-x%5E%7B(k)%7D)%5Ctag2)
其中%7D)%3D%5Cnabla%20f(x%5E%7B(k)%7D))
是在點(diǎn)的梯度糜工，%7D))
是的海塞矩陣（類似于二階導(dǎo)數(shù)）在點(diǎn)的值：
![H(x)=\bigg[\frac{\partial^2f}{\partial x_i\partial x_j}\bigg]_{n\times n}\tag3](https://math.jianshu.com/math?formula=H(x)%3D%5Cbigg%5B%5Cfrac%7B%5Cpartial%5E2f%7D%7B%5Cpartial%20x_i%5Cpartial%20x_j%7D%5Cbigg%5D_%7Bn%5Ctimes%20n%7D%5Ctag3)
公式(2)兩邊對(duì)
求導(dǎo)：
%3Dg_k%2BH(x%5E%7B(k)%7D)(x-x%5E%7B(k)%7D)%3Dg_k%2BH_k(x-x%5E%7B(k)%7D)%5Ctag4)
將點(diǎn)%7D)
代入公式(4)得到：
%7D)%3Dg_k%2BH_k(x%5E%7B(k%2B1)%7D-x%5E%7B(k)%7D)%5Ctag5)
所以
%7D-x%5E%7B(k)%7D)%5Ctag6)
記
弊添，%7D-x%5E%7B(k)%7D)
，則
或者說
公式(7)或公式(8)叫做擬牛頓條件捌木。
如果
是正定的（
也是正定的）油坝，那么可以保證牛頓法搜索方向
是下降方向还栓。對(duì)公式(2)只展開到1階：
%3Df(x%5E%7B(k)%7D)%2Bg_k%5ET(x-x%5E%7B(k)%7D)%5Ctag9)
而的更新公式為：
%7D-%5Clambda%20H_k%5E%7B-1%7Dg_k%5Ctag%7B10%7D)
將(10)中的代入(9)得到：
%3Df(x%5E%7B(k)%7D)%2Bg_k%5ET(x%5E%7B(k)%7D-x%5E%7B(k)%7D-%5Clambda%20H_k%5E%7B-1%7Dg_k)%3Df(x%5E%7B(k)%7D)-%5Clambda%20g_k%5ETH_k%5E%7B-1%7Dg_k%5Ctag%7B11%7D)
因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=H_k%5E%7B-1%7D" alt="H_k^{-1}" mathimg="1">正定比肄，所以
饺鹃。當(dāng)
為一個(gè)充分小的正數(shù)時(shí)汗侵，總有%5Clt%20f(x%5E%7B(k)%7D))
，也就是說
是下降方向极舔。
綜上所述凤覆，擬牛頓法使用
近似（DFP算法）或者使用
（BFGS算法）近似，需要滿足滿足兩個(gè)條件：
-
或正定
- 滿足擬牛頓條件拆魏，即
或
或通過迭代的方式進(jìn)行更新盯桦，即
或
。
DFP算法
DFP算法使用近似渤刃，需要滿足擬牛頓條件拥峦，通過迭代更新。
使
即
公式(13)兩邊乘上
令
則公式(14)為
滿足擬牛頓條件卖子，也不難找出滿足條件(15)和(16)的
和
：
于是得到矩陣
的迭代公式：
算法
輸入：目標(biāo)函數(shù)略号，梯度%3D%5Cnabla%20f(x))
，精度要求
洋闽；
輸出：的極小點(diǎn)玄柠。
- 選定初始點(diǎn)
%7D)
，取
為正定對(duì)稱矩陣诫舅，置
- 計(jì)算
%7D))
羽利。若
，則停止計(jì)算刊懈，得近似解%7D)
这弧；否則轉(zhuǎn)(3)
- 置
- 一維搜索，求
使得
%7D%2B%5Clambda_kp_k)%3D%5Cmin_%7B%5Clambda%5Cgeq0%7Df(x%5E%7B(k)%7D%2B%5Clambda%20p_k))
- 置
%7D%3Dx%5E%7B(k)%7D%2B%5Clambda_kp_k)
- 計(jì)算
%7D))
虚汛，若
匾浪，則停止計(jì)算，得近似解%7D)
卷哩；否則按公式(20)算出
- 置
户矢，轉(zhuǎn)(3)
BFGS算法
DFP算法使用近似，需要滿足擬牛頓條件殉疼，通過迭代更新。
使
即
公式(22)兩邊乘上
令
則公式(23)為
滿足擬牛頓條件捌年，也不難找出滿足條件(24)和(25)的和：
于是得到矩陣的迭代公式：
算法
輸入：目標(biāo)函數(shù)瓢娜，梯度，精度要求礼预；
輸出：的極小點(diǎn)眠砾。
- 選定初始點(diǎn)，取
為正定對(duì)稱矩陣托酸，置
- 計(jì)算褒颈。若柒巫，則停止計(jì)算，得近似解谷丸；否則轉(zhuǎn)(3)
- 置
- 一維搜索堡掏，求使得
- 置
- 計(jì)算，若刨疼，則停止計(jì)算泉唁，得近似解；否則按公式(29)算出
- 置揩慕，轉(zhuǎn)(3)
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
