【正文】 1( ) ( ) m i n ( )k k k k kkkf f s f s???? ? ? ? ?x x x經過一次迭代即求得極小點 函數(shù)極小值 開始給定結束0, ?x21[ ( ) ] ( )k k kff?? ? ? ?d x x1: m i n ( )k k kkkkkf????????x x dxd1kk????xx*1 k ??xx否是1kk??0k ? 阻尼牛頓法程序框圖 方法特點 （ 1） 初始點應選在 X*附近，有一定難度； （ 2） 若迭代點的海賽矩陣為奇異，則無法求逆矩陣，不能構造牛頓法方向； （ 3） 不僅要計算梯度，還要求海賽矩陣及其逆矩陣，計算量和存儲量大。此外，對于二階不可微的 F(X)也不適用。 雖然阻尼牛頓法有上述缺點，但在特定條件下它具有收斂最快的優(yōu)點，并為其他的算法提供了思路和理論依據(jù)。 1 ( 0 , 1 , 2 , )k k kk sk?? ? ? ?xx1 ( ) ( 0 , 1 , 2 , )k k kka f k? ? ? ? ?x x x1 2 1[ ( ) ] ( ) ( 0 , 1 , 2 , )k k k kf f k??? ? ? ? ?x x x x1 2 1[ ( ) ] ( ) ( 0 , 1 , 2 , )k k k kk f f k???? ? ? ? ?x x x x一般迭代式： 梯度法： 牛頓法： 阻尼牛頓法： 梯度法與牛頓法： 1 ()k k k kk f?? ? ? ?x x A x43 變尺度法 DFP變尺度法首先有戴維頓（ Davidon）與鮑維爾（ Powell）于 1959年提出，又于 1963年由弗萊徹（ Fletcher）和鮑維爾加以發(fā)展和完善，成為現(xiàn)代公認的較好的算法之一。 DFP法是基于牛頓法的思想又作了重要改進。這種算法僅用到梯度，不必計算海賽矩陣及其逆矩陣，但又能使搜索方向逐漸逼近牛頓方向，具有較快的收斂速度。 1. 基本思想 變量的尺度變換是放大或縮小各個坐標。通過尺 度變換可以把函數(shù)的偏心程度降到最低限度。 例如在用最速下降法求 的極小 2212( ) 2 5f x x??x值時 ,需要進行 10次迭代才能達到極小點 [0 , 0 ]Tx ? 如作變換 y1=x1, y2=5x2 把 的尺度放大 5倍，則目標函數(shù)等值線由一簇橢圓變成一簇同心圓。 x2 221 2 1 2( , )y y y y? ?? 消除了函數(shù)的偏心，用最速下降法只需一次迭代即可求得極小點。 梯度法構造簡單，只用到一階偏導數(shù)，計算量小，初始點可任選，且開始幾次迭代，目標函數(shù)值下降很快；其主要缺點是迭代點接近 X*時，即使對二次正定函數(shù)收斂也非常慢。 牛頓法收斂很快，對于二次函數(shù)只需迭代一次便達到最優(yōu)點，對非二次函數(shù)也能較快迭代到最優(yōu)點，但要計算二階偏導數(shù)矩陣及其逆陣，對維數(shù)較高的優(yōu)化問題，其計算工作和存儲量都太大。 能不能將兩種算法的優(yōu)點綜合起來，揚長避短？ 1 ()k k k kk f?? ? ? ?x x A xAk 是需要構造 n n的一個對稱方陣 ， 如 Ak=I, 則得到梯度法 ； 21[ ( ) ]kkf ???Ax 則得到阻尼牛頓法 ； 如 當矩陣 Ak 不斷地迭代而能很好地逼近 21[ ( ) ]kf ?? x時，就可以不再需要計算二階導數(shù)。 變尺度法的關鍵在于尺度矩陣 Ak的產生 。 對于二次函數(shù) : 1()2TTf ? ? ?x x G x b x c?x Q x進行尺度變換 在新的坐標系中，函數(shù) f(x)的二次項變?yōu)椋? 1122T T T?x G x x Q G Q x目的：減少二次項的偏心 如 G是正定，則總存在矩陣 Q，使得： T ?Q G Q I 用矩陣 Q1右乘等式兩邊，得： 用矩陣 Q左乘等式兩邊，得： 1T ??Q G QT ?Q Q G I所以 1T ??Q Q G上式說明：二次函數(shù)矩陣 G的逆陣，可以通過尺度變換矩陣 Q來求得。 1 2 1[ ( ) ] ( ) ( 0 , 1 , 2 , )k k k kk f f k???? ? ? ? ?x x x x牛頓迭代公式： 1 ( ) ( 0 , 1 , 2 , )k k T kk Q Q f k?? ? ? ? ?x x x記： T A?搜索方向： 1 ( ) ( 0 , 1 , 2 , )k k ks f k? ? ? ? ?Ax迭代公式： 1 ( ) ( 0 , 1 , 2 , )k k k kk fk?? ? ? ? ?x x A xA 稱為變尺度矩陣 2212( ) 2 5f x x??x在例 4－ 2中 1221 2 1 222022( ) 250 5022Txf x x x xx????? ? ? ????????? ?? ??x x G x200 50???????G如取 1021052?????????Q11002 0 1 0221 0 50 1 0 1005 2 5 2T? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?Q G Q I求得： 111 100 022 2111000505 2 5 2T?? ? ? ? ??? ? ? ? ??? ? ? ?? ? ? ??? ? ? ? ??? ? ? ? ????? ? ? ?G Q Q2. 構造尺度矩陣 Ak 從初始矩陣 A0=I(單位矩陣 )開始，通過對公式 1k k k? ? ? ?A A A因此，一旦達到最優(yōu)點附近，就可望達到牛頓法的收斂速度 。 1） DFP法（ DavidonFletcherPowell) [ ] [ ][ ] [ ]Tk k k k k T kkk T k k T k k? ? ? ?? ? ?? ? ? ?x x A g g AAx g g A g111( ) ( )k k k k kk k kff???? ? ? ? ? ? ???? ? ??g g g x xx x x式中 中修正矩陣 的不斷修正，在迭代中逐步逼近于 k?A11()k??Gx。 2） BFGS算法 (BroydenFletcherGold frobShanno ) ? DFP算法由于舍入誤差和一維搜索不精確，有可能導致構造矩陣的正定性遭到破壞，以至算法不穩(wěn)定。 BFGS算法對于維數(shù)較高問題具有更好的穩(wěn)定性。 1 [ ] [ ]{ [ ][ ] [ ][ ] [ ] }k k T k T k kk k k Tk T k k T kkk k T k k T? ? ? ?? ? ? ? ?? ? ? ?? ? ? ? ? ?x x g A gA x xx g x gA g x x g A開始給定結束0, ?x000()f???gxAI1: m i n ( )k k kkkkkf????????x x dxd1kk????xx*1 k ??xx否是1kk ??kn ?11111()kkk k kk k kf???????? ? ?? ? ?gxg g gx x x11k k k??? ? ?A A A01 k ??xx0k ?k k k??d A g是否例 43： 用 DFP算法求下列問題的極值： 221 2 1 2 1 1 2( , ) 2 4 2f x x x x x x x? ? ? ??解： 1）取初始點 ，為了按 DFP法構造第一次搜尋方向 d0，需計算初始點處的梯度 0 [1 1]T?x01200212 2 4 4()42 2xxfxx?? ??? ??? ? ? ??? ??? ????xgx取初始變尺度矩陣為單位矩陣 A0=I，則第一次搜尋方向為 0 0 0 1 0 4 40 1 2 2?? ? ? ? ? ?? ? ? ? ?? ? ? ? ? ??? ? ? ? ? ?d A g? 沿 d0方向進行一維搜索 ， 得 01 0 000014141212???????? ? ? ?? ? ? ? ???? ? ? ? ??? ? ? ? ??x x d為一維搜索最佳步長 ， 應滿足 0?1 0 0 2( ) m i n ( ) m i n ( 40 20 3 )ff?? ? ? ?? ? ? ? ?x x d得 : 0 0 .2 5? ?1 2???????x, 2） 再按 DFP法構造點 x1處的搜尋方向 d1， 需計算 1121212 2 4 142 2xxxx?? ??? ?????? ??? ?????xg0 1 0 1 4 32 2 4??? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?g g g0 1 0 2 1 1 1 ? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ??? ? ? ? ? ?x x x代入校正公式 0 0 0 0 0 000 0 0 0 0[ ] [ ][ ] [ ]T TTT? ? ? ?? ? ?? ? ? ?x x A g g AAx g g A g? ?? ?? ?? ?131 3 4 4331 3 444? ? ? ???? ? ? ???? ? ? ??? ? ? ???? ? ? ???? ? ? ?= 1 0 0? ? ?A A A21 191 0 1 9 1211 25 500 1 12 16 19 415 2550 100??????? ? ? ? ? ?? ? ? ??? ? ? ? ? ???? ? ? ? ? ? ??????= 第二次搜尋方向為 1 1 18665????