機(jī)械優(yōu)化設(shè)計(jì)無(wú)約束優(yōu)化方法-文庫(kù)吧
2024-12-24 14:43 本頁(yè)面
【正文】 1( ) ( ) m i n ( )k k k k kkkf f s f s???? ? ? ? ?x x x經(jīng)過一次迭代即求得極小點(diǎn) 函數(shù)極小值 開始給定結(jié)束0, ?x21[ ( ) ] ( )k k kff?? ? ? ?d x x1: m i n ( )k k kkkkkf????????x x dxd1kk????xx*1 k ??xx否是1kk??0k ? 阻尼牛頓法程序框圖 方法特點(diǎn) （ 1） 初始點(diǎn)應(yīng)選在 X*附近，有一定難度； （ 2） 若迭代點(diǎn)的海賽矩陣為奇異，則無(wú)法求逆矩陣，不能構(gòu)造牛頓法方向； （ 3） 不僅要計(jì)算梯度，還要求海賽矩陣及其逆矩陣，計(jì)算量和存儲(chǔ)量大。此外，對(duì)于二階不可微的 F(X)也不適用。 雖然阻尼牛頓法有上述缺點(diǎn)，但在特定條件下它具有收斂最快的優(yōu)點(diǎn)，并為其他的算法提供了思路和理論依據(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)代公認(rèn)的較好的算法之一。 DFP法是基于牛頓法的思想又作了重要改進(jìn)。這種算法僅用到梯度，不必計(jì)算海賽矩陣及其逆矩陣，但又能使搜索方向逐漸逼近牛頓方向，具有較快的收斂速度。 1. 基本思想 變量的尺度變換是放大或縮小各個(gè)坐標(biāo)。通過尺 度變換可以把函數(shù)的偏心程度降到最低限度。 例如在用最速下降法求 的極小 2212( ) 2 5f x x??x值時(shí) ,需要進(jìn)行 10次迭代才能達(dá)到極小點(diǎn) [0 , 0 ]Tx ? 如作變換 y1=x1, y2=5x2 把 的尺度放大 5倍，則目標(biāo)函數(shù)等值線由一簇橢圓變成一簇同心圓。 x2 221 2 1 2( , )y y y y? ?? 消除了函數(shù)的偏心，用最速下降法只需一次迭代即可求得極小點(diǎn)。 梯度法構(gòu)造簡(jiǎn)單，只用到一階偏導(dǎo)數(shù)，計(jì)算量小，初始點(diǎn)可任選，且開始幾次迭代，目標(biāo)函數(shù)值下降很快；其主要缺點(diǎn)是迭代點(diǎn)接近 X*時(shí)，即使對(duì)二次正定函數(shù)收斂也非常慢。 牛頓法收斂很快，對(duì)于二次函數(shù)只需迭代一次便達(dá)到最優(yōu)點(diǎn)，對(duì)非二次函數(shù)也能較快迭代到最優(yōu)點(diǎn)，但要計(jì)算二階偏導(dǎo)數(shù)矩陣及其逆陣，對(duì)維數(shù)較高的優(yōu)化問題，其計(jì)算工作和存儲(chǔ)量都太大。 能不能將兩種算法的優(yōu)點(diǎn)綜合起來(lái)，揚(yáng)長(zhǎng)避短？ 1 ()k k k kk f?? ? ? ?x x A xAk 是需要構(gòu)造 n n的一個(gè)對(duì)稱方陣 ， 如 Ak=I, 則得到梯度法 ； 21[ ( ) ]kkf ???Ax 則得到阻尼牛頓法 ； 如 當(dāng)矩陣 Ak 不斷地迭代而能很好地逼近 21[ ( ) ]kf ?? x時(shí)，就可以不再需要計(jì)算二階導(dǎo)數(shù)。 變尺度法的關(guān)鍵在于尺度矩陣 Ak的產(chǎn)生 。 對(duì)于二次函數(shù) : 1()2TTf ? ? ?x x G x b x c?x Q x進(jìn)行尺度變換 在新的坐標(biāo)系中，函數(shù) f(x)的二次項(xiàng)變?yōu)椋? 1122T T T?x G x x Q G Q x目的：減少二次項(xiàng)的偏心 如 G是正定，則總存在矩陣 Q，使得： T ?Q G Q I 用矩陣 Q1右乘等式兩邊，得： 用矩陣 Q左乘等式兩邊，得： 1T ??Q G QT ?Q Q G I所以 1T ??Q Q G上式說明：二次函數(shù)矩陣 G的逆陣，可以通過尺度變換矩陣 Q來(lái)求得。 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. 構(gòu)造尺度矩陣 Ak 從初始矩陣 A0=I(單位矩陣 )開始，通過對(duì)公式 1k k k? ? ? ?A A A因此，一旦達(dá)到最優(yōu)點(diǎn)附近，就可望達(dá)到牛頓法的收斂速度 。 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算法由于舍入誤差和一維搜索不精確，有可能導(dǎo)致構(gòu)造矩陣的正定性遭到破壞，以至算法不穩(wěn)定。 BFGS算法對(duì)于維數(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開始給定結(jié)束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）取初始點(diǎn) ，為了按 DFP法構(gòu)造第一次搜尋方向 d0，需計(jì)算初始點(diǎn)處的梯度 0 [1 1]T?x01200212 2 4 4()42 2xxfxx?? ??? ??? ? ? ??? ??? ????xgx取初始變尺度矩陣為單位矩陣 A0=I，則第一次搜尋方向?yàn)? 0 0 0 1 0 4 40 1 2 2?? ? ? ? ? ?? ? ? ? ?? ? ? ? ? ??? ? ? ? ? ?d A g? 沿 d0方向進(jìn)行一維搜索 ， 得 01 0 000014141212???????? ? ? ?? ? ? ? ???? ? ? ? ??? ? ? ? ??x x d為一維搜索最佳步長(zhǎng) ， 應(yīng)滿足 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法構(gòu)造點(diǎn) x1處的搜尋方向 d1， 需計(jì)算 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??????? ? ? ? ? ?? ? ? ??? ? ? ? ? ???? ? ? ? ? ? ??????= 第二次搜尋方向?yàn)? 1 1 18665????
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1