牛頓法和擬牛頓法課件

1、牛牛頓頓法和擬法和擬牛頓法牛頓法無約束優(yōu)化問題無約束優(yōu)化問題 線搜索方法線搜索方法 dk ：搜索方向 （下降就可）： dk f(xk) 0 k ： 搜索步長： 1） 精確搜索： f(xd ) 達(dá)到最小 2） Wolfe 搜索： （兩個(gè)條件） 精確搜索精確搜索 Wolfe 非精確搜索非精確搜索 Wolfe 非精確搜索非精確搜索 線搜索方法的下降線搜索方法的下降 方法收斂之關(guān)鍵：估計(jì) 搜索方向與最速下降方向的夾角 線搜索方法的收斂性線搜索方法的收斂性定理定理 如果 f(x) 下方有界，如果搜索方向與最速下降法的夾角不靠近/2,則由線搜索方法產(chǎn)生的點(diǎn)列 xk 滿足： | gk | 0 搜索方向搜索方

2、向最速下降法：共軛梯度法：牛頓法： 牛頓方向牛頓方向牛頓方向是如下問題的解 牛頓法的優(yōu)缺點(diǎn)牛頓法的優(yōu)缺點(diǎn)收斂快收斂快 二次收斂二次收斂程序簡單程序簡單計(jì)算量大計(jì)算量大 需要二階導(dǎo)數(shù)需要二階導(dǎo)數(shù)要求高要求高 需要二階導(dǎo)需要二階導(dǎo)數(shù)數(shù)需要計(jì)算需要計(jì)算HesseHesse矩陣，而此矩陣可能非正定矩陣，而此矩陣可能非正定，可可能導(dǎo)致搜索方向不是下降方向。能導(dǎo)致搜索方向不是下降方向。 找替代牛頓法的方法找替代牛頓法的方法目標(biāo)：目標(biāo)： 收斂快收斂快 程序簡單程序簡單 同時(shí)同時(shí) 不需要二階導(dǎo)數(shù)不需要二階導(dǎo)數(shù)找：找： 像牛頓像牛頓 又不是牛頓又不是牛頓 的家伙！的家伙！ )()()(1)(2)(kkkxfxf

3、d )()()1(kkkkdxx 與一階導(dǎo)數(shù)的關(guān)系：首先分析1)(2)(kxf)()(21)()()()1()1(2)1()1()1()1()1( kkTkkkkkxxxfxxxxxfxfxfTaylorx展開：展開：處進(jìn)行二階處進(jìn)行二階在點(diǎn)在點(diǎn))()()( )1()1(2)1( kkkxxxfxfxf)()()( )1()()1(2)1()( kkkkkxxxfxfxf)(1)1(2)()()1(2)()()1()()()1()()( )( )()(:kkkkkkkkkkkkqxfppxfqxfxfqxxp)(1)(kkkqHp kHkkkHHHIH 11;TkkkkzzH)()( )(1)

4、(kkkqHp )()()()(kTkkkkqzzH )()()()()(kTkkkkkkqzqHpz )()()()()(2)()(kkkTkkTkkqHpqqz )()()()()()()()()(kkkTkTkkkkkkkqHpqqHpqHpH ?0 TkkkTkkkkvvuuH)()()()( )(1)(kkkqHp )()()()()()(kTkkkTkkkkqvvuuH )()()()()()()()(kkkkTkkkkTkkkqHpqvvquu )()()()()()()()(1;1kTkkkkkkTkkkkqvqHvqupu ；令令)()()()()()()()(kkTkkTk

5、kkkTkTkkkqHqHqqHqpppH 計(jì)計(jì)算算步步驟驟：0,)1( x )()(kxf否否是是)(kxx )()()1()()(0)()()(minarg)(kkkkkkkkkkdxxdxfxfHd nk 否否是是1:)()(1)()1()()()1()( kkHHHHxfxfqxxpkkkkkkkkkk)1()1( nxx1),(,)1()1(1 kxfdIHn1001,12242min13. 41)1(12221HxxxxDFP初始點(diǎn)方法求解：用例1294980118513617130538388630612H. 0DFP),.,1(0)(:)(kkHnkxf方法構(gòu)造的則若定理)()

6、()(kkkxfHd 0)()()( kTkdxf 1 10 021)(min)()()1()(1)()(1)1(iiiii(i)(i)kjTiTTdxxpnkipApHnjiAppHxcxbAxxxfDFP其中則，令任取方法求解正定二次函數(shù)設(shè)用定理11 AHn)(1)(kkkqHp )(1)(kkkpBq )()()()()()()()(kkTkkTkkkkTkTkkkpBpBppBpqqqB )()()()()()()()(kkTkkTkkkkTkTkkkqHqHqqHqpppH 互換互換)()(,kkqp1111 kkkkkBHBBB)()()()()()()()()()()()()()

7、(11)()1 (11111kTkTkkkkTkkkTkkTkkTkkkTkkBFGSkuMvMuvMMuvMqppqHHqpqpppqpqHqHHTTT BFGSkDFPkkHHH111)1( TkkDFPkvvH)()(1 )()()()()()(21)()()()(kkTkkkkTkkkkTkkqHqqHqppqHqv其中其中0 為保持正定性，取為保持正定性，取 擬牛頓公式擬牛頓公式Davidon(1959), Fletcher-Powell(1963)Davidon(1959), Fletcher-Powell(1963)DFP DFP 方法方法 DFP公式的逆形式公式的逆形式如果如果

8、 H H 是是B B 的擬矩陣的擬矩陣 BFGS公式公式BFGS BFGS 方法：方法： ( (最常用的方法）最常用的方法） Broyden(1970), Fletcher(1970), Broyden(1970), Fletcher(1970), Goldfarb(1970), Shanno(1970)Goldfarb(1970), Shanno(1970) SR1公式公式對稱秩一方法對稱秩一方法 非對稱秩一公式非對稱秩一公式優(yōu)點(diǎn)：克服對稱秩一方法的分母為零的困難優(yōu)點(diǎn)：克服對稱秩一方法的分母為零的困難缺點(diǎn)：缺點(diǎn)： 不對稱不對稱 PSB公式公式Powell Powell 對稱化技巧：對稱化技巧： 交替利用交替利用 秩一方法秩一方法 和和 對稱化對稱化有