lxt第4章無(wú)約束優(yōu)化方法2

1、軋機(jī)CAD/CAM/CAE研究室第四章第四章 無(wú)約束優(yōu)化方法無(wú)約束優(yōu)化方法1) 1) 坐標(biāo)輪換法坐標(biāo)輪換法; ;2) 2) 鮑威爾法鮑威爾法; ;3) 3) 梯度法梯度法; ;4) 4) 共軛梯度法共軛梯度法; ;5) 5) 牛頓法牛頓法; ;6) DFP6) DFP變尺度法變尺度法. .軋機(jī)CAD/CAM/CAE研究室4-1 概述概述 對(duì)于一個(gè)對(duì)于一個(gè)n n維目標(biāo)函數(shù)，如果在沒(méi)有任何維目標(biāo)函數(shù)，如果在沒(méi)有任何限制條件下尋求它的極小點(diǎn)，稱(chēng)無(wú)約束極限制條件下尋求它的極小點(diǎn)，稱(chēng)無(wú)約束極小化問(wèn)題或無(wú)約束優(yōu)化問(wèn)題。數(shù)學(xué)上表達(dá)小化問(wèn)題或無(wú)約束優(yōu)化問(wèn)題。數(shù)學(xué)上表達(dá)為為: : Min F(X)XRn軋機(jī)CA

2、D/CAM/CAE研究室一）研究無(wú)約束優(yōu)化方法的意義一）研究無(wú)約束優(yōu)化方法的意義 一類(lèi)有約束優(yōu)化方法，往往能轉(zhuǎn)化成無(wú)約束問(wèn)題，一類(lèi)有約束優(yōu)化方法，往往能轉(zhuǎn)化成無(wú)約束問(wèn)題，易于采用無(wú)約束優(yōu)化方法求解易于采用無(wú)約束優(yōu)化方法求解; ; 有些問(wèn)題可先作無(wú)約束問(wèn)題求解，然后采用有約有些問(wèn)題可先作無(wú)約束問(wèn)題求解，然后采用有約束方法求出最優(yōu)解。束方法求出最優(yōu)解。 軋機(jī)CAD/CAM/CAE研究室二）解法分類(lèi)二）解法分類(lèi)無(wú)約束優(yōu)化方法無(wú)約束優(yōu)化方法 間接法間接法（解析法）（解析法）直接法直接法 梯度法梯度法 牛頓法牛頓法DFP變尺度法變尺度法 坐標(biāo)輪換法坐標(biāo)輪換法 鮑威爾法鮑威爾法確定搜索方向時(shí)用到一確定搜索

3、方向時(shí)用到一階或（和）二階導(dǎo)數(shù)的階或（和）二階導(dǎo)數(shù)的方法。方法。其搜索方向直接其搜索方向直接取定或由計(jì)算目取定或由計(jì)算目標(biāo)函數(shù)值所得的標(biāo)函數(shù)值所得的信息來(lái)確定；信息來(lái)確定；軋機(jī)CAD/CAM/CAE研究室4-2 坐標(biāo)輪換法 一、一、方法概述方法概述 坐標(biāo)輪換法的基本構(gòu)思是坐標(biāo)輪換法的基本構(gòu)思是將一個(gè)將一個(gè) n n 維優(yōu)化問(wèn)題轉(zhuǎn)化為維優(yōu)化問(wèn)題轉(zhuǎn)化為依次沿依次沿 n n 個(gè)坐標(biāo)方向反復(fù)進(jìn)個(gè)坐標(biāo)方向反復(fù)進(jìn)行一維搜索問(wèn)題。這種方法的行一維搜索問(wèn)題。這種方法的實(shí)質(zhì)是把實(shí)質(zhì)是把n n維問(wèn)題的求優(yōu)過(guò)程維問(wèn)題的求優(yōu)過(guò)程轉(zhuǎn)化為對(duì)每個(gè)變量逐次進(jìn)行一轉(zhuǎn)化為對(duì)每個(gè)變量逐次進(jìn)行一維求優(yōu)的循環(huán)過(guò)程。維求優(yōu)的循環(huán)過(guò)程。 軋

4、機(jī)CAD/CAM/CAE研究室二、迭代過(guò)程二、迭代過(guò)程 任選初始點(diǎn)任選初始點(diǎn) 搜索方向搜索方向以以X X(0)(0)為初始點(diǎn)，沿為初始點(diǎn)，沿e e1 1作正向試探性移步，步長(zhǎng)作正向試探性移步，步長(zhǎng)0 0 若試探成功，沿此方向一維搜索；否則，沿坐標(biāo)的負(fù)若試探成功，沿此方向一維搜索；否則，沿坐標(biāo)的負(fù)方向試探。若正負(fù)方向試探均失敗，則轉(zhuǎn)入下一步。方向試探。若正負(fù)方向試探均失敗，則轉(zhuǎn)入下一步。TnTTTieeeS1 , 0 , 0 , 00 , 0 , 1 , 00 , 0 , 0 , 121TnxxxX)0()0(2)0(1)0(, 沿沿e e2 2方向進(jìn)行一維搜索。以此類(lèi)推，進(jìn)行完一輪一維搜索后得

5、方向進(jìn)行一維搜索。以此類(lèi)推，進(jìn)行完一輪一維搜索后得 以以 作為第二輪的初始點(diǎn)，重復(fù)步驟前作為第二輪的初始點(diǎn)，重復(fù)步驟前2 2步，得第二輪搜索的終點(diǎn)步，得第二輪搜索的終點(diǎn) ，相繼進(jìn)行第三、第四輪等的搜索。，相繼進(jìn)行第三、第四輪等的搜索。 如果從某輪的起始點(diǎn)出發(fā)，沿各個(gè)坐標(biāo)軸的正負(fù)方向試探均失敗，則如果從某輪的起始點(diǎn)出發(fā)，沿各個(gè)坐標(biāo)軸的正負(fù)方向試探均失敗，則縮短初始試探步長(zhǎng)。當(dāng)初始步長(zhǎng)縮得足夠小，滿(mǎn)足精度時(shí)，迭代終止。縮短初始試探步長(zhǎng)。當(dāng)初始步長(zhǎng)縮得足夠小，滿(mǎn)足精度時(shí)，迭代終止。 )1(nx)1(nx)2(nx軋機(jī)CAD/CAM/CAE研究室 二、迭代過(guò)程二、迭代過(guò)程軋機(jī)CAD/CAM/CAE研究

6、室三、坐標(biāo)輪換法流程圖三、坐標(biāo)輪換法流程圖從從 出發(fā)沿出發(fā)沿 方向進(jìn)行一維搜索得方向進(jìn)行一維搜索得 ：1iXieiiiiieXX1)(iXFF 1ini 給給定定,0nX0XXn1iiFFXXn結(jié)束結(jié)束10kkXXn1k是否否是軋機(jī)CAD/CAM/CAE研究室四、算法特點(diǎn)四、算法特點(diǎn) 如如:(:(1)1)等值線(xiàn)為橢圓等值線(xiàn)為橢圓, ,且長(zhǎng)短軸分別平行于坐標(biāo)軸時(shí)且長(zhǎng)短軸分別平行于坐標(biāo)軸時(shí)-高效高效1x2xo(2(2) )等值線(xiàn)為如圖脊線(xiàn)時(shí)等值線(xiàn)為如圖脊線(xiàn)時(shí)-無(wú)效無(wú)效1x2xo(3(3) )一般情況一般情況-低效低效1 1）編程簡(jiǎn)單，容易掌握；）編程簡(jiǎn)單，容易掌握；2 2）收斂速度通常較低（）收斂

7、速度通常較低（其有效性取決于目標(biāo)其有效性取決于目標(biāo)函數(shù)的性態(tài)函數(shù)的性態(tài)），僅適于低維的情況），僅適于低維的情況(n10)(n10)。軋機(jī)CAD/CAM/CAE研究室4-3 鮑威爾法鮑威爾法 設(shè)設(shè)A A為為n n階對(duì)稱(chēng)正定矩陣，若有兩個(gè)階對(duì)稱(chēng)正定矩陣，若有兩個(gè)n n維矢量維矢量S1S1和和S2 S2 ，滿(mǎn)足：滿(mǎn)足： 鮑威爾法是以共軛方向?yàn)榛A(chǔ)的收斂較快的直接法之一。鮑威爾法是以共軛方向?yàn)榛A(chǔ)的收斂較快的直接法之一。 共軛方向法的概念共軛方向法的概念則稱(chēng)矢量則稱(chēng)矢量S1S1和和S2S2對(duì)矩陣對(duì)矩陣A A共軛。共軛。共軛矢量的方向稱(chēng)共軛矢量的方向稱(chēng)共軛方向共軛方向。軋機(jī)CAD/CAM/CAE研究室鮑

8、威爾法 共軛方向與函數(shù)極小點(diǎn)的關(guān)系共軛方向與函數(shù)極小點(diǎn)的關(guān)系 設(shè)有一般二維二次正定函數(shù)設(shè)有一般二維二次正定函數(shù) 同心橢圓族。從同心橢圓族。從出發(fā)，沿出發(fā)，沿S S1 1方向作一維搜索，得最優(yōu)點(diǎn)方向作一維搜索，得最優(yōu)點(diǎn)X X1 1 （與橢圓相切）；再?gòu)牧硪怀跏键c(diǎn)（與橢圓相切）；再?gòu)牧硪怀跏键c(diǎn) 出發(fā)，沿出發(fā)，沿S S1 1方向作一維搜索，方向作一維搜索，連線(xiàn)的方向?yàn)檫B線(xiàn)的方向?yàn)镾 S2 2，則，則S S2 2必過(guò)橢圓族的中心，即必過(guò)橢圓族的中心，即X X* *，且，且S S1 1和和S S2 2必與必與A A正交。正交。 其等值線(xiàn)是其等值線(xiàn)是沿沿S S1 1方向作一維搜索，得最優(yōu)點(diǎn)方向作一維搜索，

9、得最優(yōu)點(diǎn)X X2 2 （也與橢圓相切）。設(shè)（也與橢圓相切）。設(shè)X X1 1與與 X X2 2 軋機(jī)CAD/CAM/CAE研究室4-2 Powell4-2 Powell法法2x3x1xo0X1e2e3e3 3）若目標(biāo)函數(shù)為正定二次函數(shù)，）若目標(biāo)函數(shù)為正定二次函數(shù)，n n輪結(jié)束后即可到達(dá)輪結(jié)束后即可到達(dá)最優(yōu)點(diǎn)。最優(yōu)點(diǎn)。2 2）每輪迭代產(chǎn)生一個(gè)新方向取代原來(lái)的第一方向，）每輪迭代產(chǎn)生一個(gè)新方向取代原來(lái)的第一方向，n n輪迭代后可產(chǎn)生輪迭代后可產(chǎn)生n n個(gè)彼此共軛的方向個(gè)彼此共軛的方向；nX1 1）開(kāi)始采用坐標(biāo)軸方向）開(kāi)始采用坐標(biāo)軸方向；一）一）PowellPowell基本算法基本算法共軛方向法共軛方

10、向法軋機(jī)CAD/CAM/CAE研究室迭代過(guò)程軋機(jī)CAD/CAM/CAE研究室二）二）PowellPowell法法（ PowellPowell修正算法）修正算法）2x3x1xo0X2e3e1X 應(yīng)用應(yīng)用 PowellPowell基本算法時(shí)，若有一次搜索的最優(yōu)步長(zhǎng)為基本算法時(shí)，若有一次搜索的最優(yōu)步長(zhǎng)為0 0，且該方向被換掉，則該算法失效。且該方向被換掉，則該算法失效。1 1）問(wèn)題的提出）問(wèn)題的提出軋機(jī)CAD/CAM/CAE研究室 2)Powell 2)Powell對(duì)基本算法的改進(jìn)對(duì)基本算法的改進(jìn) 在獲得新方向構(gòu)成新方向組時(shí)在獲得新方向構(gòu)成新方向組時(shí), ,不是不是輪換地去掉原來(lái)的方向輪換地去掉原來(lái)的

11、方向, ,而是經(jīng)判別后而是經(jīng)判別后, ,在在n+1n+1個(gè)方向中留下最接近共軛的個(gè)方向中留下最接近共軛的n n個(gè)方個(gè)方向向. . * * 根據(jù)根據(jù)PowellPowell條件判定是否需換方向；條件判定是否需換方向；如需換向，則換掉函數(shù)值下降量最大的方向如需換向，則換掉函數(shù)值下降量最大的方向. .軋機(jī)CAD/CAM/CAE研究室三）三）PowellPowell條件條件),()(01kXFF )(0)()(12kknknXXX),()(2knXFF )()(13knXFF),()(max,.,.2, 1)()(1nmikikiXFXF)()()()(1kmkmXFXF23122132113)(21

12、)(2(FFFFFFFFF如下述兩不等式如下述兩不等式同時(shí)成立則需換向，否則仍取原方向組。同時(shí)成立則需換向，否則仍取原方向組。 計(jì)算計(jì)算: : （映射計(jì)算）（映射計(jì)算）)(1knX)(knX)(1kX)(0kXPQ大的方向的標(biāo)號(hào)為目標(biāo)函數(shù)值下降量最式中 m,軋機(jī)CAD/CAM/CAE研究室四）更換方向的步驟四）更換方向的步驟nmmiiiSS,.,1,1,)(0)(1kknnXXS3 3）更換方向：）更換方向：2 2）構(gòu)造新方向：）構(gòu)造新方向：1 1）找出該輪迭代中目標(biāo)函數(shù)值下降量最大的）找出該輪迭代中目標(biāo)函數(shù)值下降量最大的方向方向（假定其標(biāo)號(hào)為假定其標(biāo)號(hào)為m m）；軋機(jī)CAD/CAM/CAE研

13、究室迭代步驟軋機(jī)CAD/CAM/CAE研究室軋機(jī)CAD/CAM/CAE研究室軋機(jī)CAD/CAM/CAE研究室4-4 4-4 梯度法梯度法一）梯度方向一）梯度方向* *可取最優(yōu)步長(zhǎng)或下降步長(zhǎng)可取最優(yōu)步長(zhǎng)或下降步長(zhǎng)二）基本思想二）基本思想 梯度方向是目標(biāo)函數(shù)上升最快的方梯度方向是目標(biāo)函數(shù)上升最快的方向，負(fù)梯度方向則是最速下降方向；向，負(fù)梯度方向則是最速下降方向；)()()()() 1(kkkkXFXX2 2）迭代公式迭代公式1 1）沿沿負(fù)梯度方向搜索負(fù)梯度方向搜索：)()()()(kkkgXFS kg三）終止判別條件三）終止判別條件軋機(jī)CAD/CAM/CAE研究室給定給定 X0 ，K=0 ，X（K

14、）=X0K=K+1X(k)=XX*= X（K）F*=F（X*）結(jié)結(jié) 束束NY計(jì)算計(jì)算)()(,kkgg)(kg 從從 出發(fā)出發(fā)，沿沿 搜索得搜索得)(kX)(kg)()()(kkkgXX* * “ “最速下降性最速下降性”只只是迭代點(diǎn)鄰域的局部是迭代點(diǎn)鄰域的局部性質(zhì)。從全局看，并性質(zhì)。從全局看，并非最速下降方向。非最速下降方向。四四. .迭代步驟迭代步驟軋機(jī)CAD/CAM/CAE研究室梯度法特點(diǎn)：梯度法每次迭代都是沿迭代點(diǎn)函數(shù)值下降最快的方向搜索，因梯度法每次迭代都是沿迭代點(diǎn)函數(shù)值下降最快的方向搜索，因而梯度法而梯度法又稱(chēng)最速下降法又稱(chēng)最速下降法。這種方法搜索路線(xiàn)常常很曲折，收斂速度較慢。對(duì)于

15、等值線(xiàn)為這種方法搜索路線(xiàn)常常很曲折，收斂速度較慢。對(duì)于等值線(xiàn)為圓的優(yōu)化問(wèn)題，梯度法一次迭代就可以達(dá)到極小點(diǎn)；當(dāng)?shù)戎稻€(xiàn)圓的優(yōu)化問(wèn)題，梯度法一次迭代就可以達(dá)到極小點(diǎn)；當(dāng)?shù)戎稻€(xiàn)不是圓，負(fù)梯度方向不再指向圓心，迭代次數(shù)增加，偏心越嚴(yán)不是圓，負(fù)梯度方向不再指向圓心，迭代次數(shù)增加，偏心越嚴(yán)重，迭代次數(shù)越多，形成重，迭代次數(shù)越多，形成鋸齒現(xiàn)象鋸齒現(xiàn)象。且在搜索開(kāi)始時(shí)步長(zhǎng)越大，。且在搜索開(kāi)始時(shí)步長(zhǎng)越大，愈接近極小點(diǎn)步長(zhǎng)愈小，最后收斂的速度極其緩慢。愈接近極小點(diǎn)步長(zhǎng)愈小，最后收斂的速度極其緩慢。因此，對(duì)于比較復(fù)雜的優(yōu)化問(wèn)題，梯度法不具有實(shí)用價(jià)值。但因此，對(duì)于比較復(fù)雜的優(yōu)化問(wèn)題，梯度法不具有實(shí)用價(jià)值。但由于梯度法

16、在迭代開(kāi)始時(shí)函數(shù)值下降得較快，由于梯度法在迭代開(kāi)始時(shí)函數(shù)值下降得較快，因此常用于其他因此常用于其他方法中作初始迭代法。方法中作初始迭代法。梯度法的優(yōu)點(diǎn)是迭代過(guò)程簡(jiǎn)單，對(duì)初始點(diǎn)要求不高，雖要計(jì)算梯度法的優(yōu)點(diǎn)是迭代過(guò)程簡(jiǎn)單，對(duì)初始點(diǎn)要求不高，雖要計(jì)算導(dǎo)數(shù)，但只要求一階偏導(dǎo)，存儲(chǔ)單元較少。導(dǎo)數(shù)，但只要求一階偏導(dǎo)，存儲(chǔ)單元較少。軋機(jī)CAD/CAM/CAE研究室4-5 4-5 共軛梯度法共軛梯度法) 1 (1)2()2()(SXFS第二方向：第二方向：)()1()1(XFS第一方向：第一方向：二二. .共軛方向的構(gòu)成共軛方向的構(gòu)成* *利于突破函數(shù)的非二次性利于突破函數(shù)的非二次性; ;每輪搜索方向?yàn)橐唤M

17、共軛方向每輪搜索方向?yàn)橐唤M共軛方向, , 但第一方向?yàn)樨?fù)梯度方向但第一方向?yàn)樨?fù)梯度方向. .一一. .基本思路基本思路)1()1()1()2(SXX* 可表示為兩個(gè)負(fù)梯度方向的線(xiàn)性組合可表示為兩個(gè)負(fù)梯度方向的線(xiàn)性組合。)2(S) 1 (X)2(S)2(X) 1 (S)()2(XF軋機(jī)CAD/CAM/CAE研究室2)(2)1()()(kkkXFXF)() 1() 1()(kkkkSXFS，以后新方向均按下述迭代公式產(chǎn)生以后新方向均按下述迭代公式產(chǎn)生：2)1(2)2()1()1()2()1()1()1()2()2(1)()()()()()()()(XFXFXFXFXFXFXFXFTT因而因而，0)

18、 1 ()2(ASST因?yàn)橐驗(yàn)椋ˋ A是二次函數(shù)的是二次函數(shù)的Hessian Hessian 矩陣矩陣）CXBAXXXFTT21)(BAXXF)(二次函數(shù)二次函數(shù)其梯度為其梯度為故有故有0)() 1 (1) 1 (1)2(ASSXFT)1()1()1()2(1)(ASSASXFTT)1()1()1()2(SXX)1()1()1()2()1()2()()()(ASXXAXFXF故有故有又又0)()2() 1 (XFST（正交正交） 劉 惟 信 用 數(shù)劉 惟 信 用 數(shù)學(xué)歸納法對(duì)此法學(xué)歸納法對(duì)此法的共軛性作出過(guò)的共軛性作出過(guò)證明。證明。軋機(jī)CAD/CAM/CAE研究室K n給定給定X0, n, K

19、=1, X(K)=X0S(K)= -F(X(K)從從X(K)始始，沿沿S(K)進(jìn)行一維搜索得進(jìn)行一維搜索得X(K+1)K=K+1是是是是否否否否計(jì)算計(jì)算)(),()1()1( KKXFXF )() 1(KXF結(jié)結(jié) 束束)()1()1( KKXFFXX) 1(0KXX)() 1() 1(2)() 1()()()(KKKKKKKSXFSXFXF重置負(fù)梯度方向重置負(fù)梯度方向三三. .迭代步驟迭代步驟軋機(jī)CAD/CAM/CAE研究室四四. .共軛梯度法的特點(diǎn)共軛梯度法的特點(diǎn)1.1.為共軛方向法為共軛方向法, ,具有二次收斂性具有二次收斂性; ;2.2.算法簡(jiǎn)單算法簡(jiǎn)單, ,編程容易編程容易, ,存儲(chǔ)量

20、小存儲(chǔ)量小; ;3.3.需用到一階導(dǎo)數(shù)需用到一階導(dǎo)數(shù). .軋機(jī)CAD/CAM/CAE研究室4-6 4-6 牛頓法牛頓法* * 鮑威爾法需迭代鮑威爾法需迭代 (n+1)n (n+1)n 次才能到達(dá)二次函數(shù)的極小點(diǎn)；共軛梯度法次才能到達(dá)二次函數(shù)的極小點(diǎn)；共軛梯度法則需迭代則需迭代n n次，能否更快到達(dá)二次函數(shù)的極小點(diǎn)？次，能否更快到達(dá)二次函數(shù)的極小點(diǎn)？一一. . 原始牛頓法原始牛頓法一）基本思路一）基本思路 牛頓法是梯度法的進(jìn)一步發(fā)展，其基本思想是在求牛頓法是梯度法的進(jìn)一步發(fā)展，其基本思想是在求目標(biāo)函數(shù)目標(biāo)函數(shù)f(X)f(X)的極小值時(shí)，先將的極小值時(shí)，先將f(X)f(X)在點(diǎn)在點(diǎn)X Xk k附近

21、作泰勒附近作泰勒展開(kāi)，取其二次近似函數(shù)式，然后求出這個(gè)二次函數(shù)的展開(kāi)，取其二次近似函數(shù)式，然后求出這個(gè)二次函數(shù)的極小點(diǎn)，并以該極小點(diǎn)作為原目標(biāo)函數(shù)的近似極小點(diǎn)；極小點(diǎn)，并以該極小點(diǎn)作為原目標(biāo)函數(shù)的近似極小點(diǎn)；若此值不滿(mǎn)足精度要求，則以此近似極小點(diǎn)作為下一次若此值不滿(mǎn)足精度要求，則以此近似極小點(diǎn)作為下一次迭代的初始點(diǎn)，繼續(xù)以上過(guò)程，迭代下去，直至所求出迭代的初始點(diǎn)，繼續(xù)以上過(guò)程，迭代下去，直至所求出的近似極小點(diǎn)滿(mǎn)足精度要求為止。的近似極小點(diǎn)滿(mǎn)足精度要求為止。軋機(jī)CAD/CAM/CAE研究室kkkkgHXXX1)()1(0)()(*kkkXXHg（牛頓方向牛頓方向）kkkgHS1)(1）迭代方向迭

22、代方向：*二）原始牛頓法的迭代公式二）原始牛頓法的迭代公式原函數(shù)原函數(shù):)(XF)()()()(21)()(kkTkkTkkXHXXgXFX近似二次函數(shù)近似二次函數(shù):0)()(kkkXHgX令令1)(k2）步長(zhǎng)因子步長(zhǎng)因子：CXBAXXXFTT21)(BAXXF)(軋機(jī)CAD/CAM/CAE研究室二）阻尼牛頓法二）阻尼牛頓法)()()(1)()()()1(kkkkkXfXHXX* *具有二次收斂性，但用到二階導(dǎo)數(shù)矩陣求逆具有二次收斂性，但用到二階導(dǎo)數(shù)矩陣求逆仍取牛頓方向，但改用最優(yōu)步長(zhǎng)因子：仍取牛頓方向，但改用最優(yōu)步長(zhǎng)因子： 因因F(XF(X）不一定是二次函數(shù)，基本牛頓法的步長(zhǎng)因）不一定是二次

23、函數(shù)，基本牛頓法的步長(zhǎng)因子恒為子恒為1 1，有時(shí)會(huì)導(dǎo)致迭代發(fā)散而失效。，有時(shí)會(huì)導(dǎo)致迭代發(fā)散而失效。1. 1. 問(wèn)題的提出問(wèn)題的提出2. 2. 改進(jìn)方法改進(jìn)方法在在H Hk k正定時(shí)可保證收斂性。正定時(shí)可保證收斂性。 軋機(jī)CAD/CAM/CAE研究室K=0 ，X（K）=X0K=K+1NX*= X（K）F*=F（X*）結(jié)結(jié) 束束Y3.3.阻尼牛頓法的迭代步驟阻尼牛頓法的迭代步驟kg計(jì)算計(jì)算kkgg ,計(jì)算計(jì)算 ，KKKgHS1)(1 KH由由 出發(fā)出發(fā)，沿沿 方向搜索得方向搜索得 )()()()1(KKKKSXX)(KX)(KS給定給定 X0 ，軋機(jī)CAD/CAM/CAE研究室 牛頓法的特點(diǎn)牛頓法

24、的特點(diǎn) 牛頓法不僅利用了函數(shù)的一階導(dǎo)數(shù)信息，還利牛頓法不僅利用了函數(shù)的一階導(dǎo)數(shù)信息，還利用了函數(shù)的二階導(dǎo)數(shù)信息，故其收斂速度較梯度用了函數(shù)的二階導(dǎo)數(shù)信息，故其收斂速度較梯度法快很多。但是牛頓法要計(jì)算黑塞矩陣及其逆矩法快很多。但是牛頓法要計(jì)算黑塞矩陣及其逆矩陣，計(jì)算量?jī)?chǔ)存量較大，且都以維數(shù)陣，計(jì)算量?jī)?chǔ)存量較大，且都以維數(shù)n2比例增加，比例增加，維數(shù)高時(shí)這個(gè)問(wèn)題更加突出。此外，若黑塞矩陣維數(shù)高時(shí)這個(gè)問(wèn)題更加突出。此外，若黑塞矩陣是奇異時(shí)，其逆矩陣不存在，這種方法就根本不是奇異時(shí)，其逆矩陣不存在，這種方法就根本不能應(yīng)用能應(yīng)用軋機(jī)CAD/CAM/CAE研究室4-7 DFP4-7 DFP變尺度法變尺度法

25、)()()()() 1(kkkkXFEXX)()()(1)()()() 1(kkkkkXFXHXX能否克服各自的缺點(diǎn)，綜合發(fā)揮其優(yōu)點(diǎn)？能否克服各自的缺點(diǎn)，綜合發(fā)揮其優(yōu)點(diǎn)？2 2）阻尼牛頓法）阻尼牛頓法1 1）梯度法）梯度法一）問(wèn)題的提出一）問(wèn)題的提出由由Davidan、Fletcher、Powell共同提出。共同提出。* * 簡(jiǎn)單，開(kāi)始時(shí)目標(biāo)函數(shù)值下降較快，但越來(lái)越慢。簡(jiǎn)單，開(kāi)始時(shí)目標(biāo)函數(shù)值下降較快，但越來(lái)越慢。* * 目標(biāo)函數(shù)值在最優(yōu)點(diǎn)附近時(shí)收斂快，但要用到二目標(biāo)函數(shù)值在最優(yōu)點(diǎn)附近時(shí)收斂快，但要用到二階導(dǎo)數(shù)和矩陣求逆。階導(dǎo)數(shù)和矩陣求逆。軋機(jī)CAD/CAM/CAE研究室二）基本思路二）基本思路

26、)()()()() 1(kkkkkXFAXX1kkHA2 2）迭代終了迭代終了， 具有二階收斂性具有二階收斂性。EAkk , 0* *1 1）當(dāng)當(dāng) 和梯度法一樣，便于突破函數(shù)的非二次性和梯度法一樣，便于突破函數(shù)的非二次性；式中，式中，1.1.A Ak k 構(gòu)造矩陣構(gòu)造矩陣（在迭代中產(chǎn)生，不用求導(dǎo)和作矩陣求逆）（在迭代中產(chǎn)生，不用求導(dǎo)和作矩陣求逆）迭代公式：迭代公式：)()()()() 1(kkkkXFEXX)()()(1)()()() 1(kkkkkXFXHXX)()()(kkkXFAS-擬牛頓方向擬牛頓方向2.軋機(jī)CAD/CAM/CAE研究室三）構(gòu)造矩陣應(yīng)滿(mǎn)足的條件三）構(gòu)造矩陣應(yīng)滿(mǎn)足的條件k

27、A1） 應(yīng)為正定對(duì)稱(chēng)矩陣；應(yīng)為正定對(duì)稱(chēng)矩陣；kA(1) 應(yīng)為對(duì)稱(chēng)矩陣應(yīng)為對(duì)稱(chēng)矩陣；E E和和 均為對(duì)稱(chēng)矩陣均為對(duì)稱(chēng)矩陣1KHkA(2) 應(yīng)為正定矩陣應(yīng)為正定矩陣；因?yàn)橐驗(yàn)?應(yīng)使應(yīng)使 為函數(shù)下降方向?yàn)楹瘮?shù)下降方向,即即 與與 的夾角應(yīng)小于的夾角應(yīng)小于900:kA)(kS)(kSkg0)(kTkSg0kkTkgAg0kkTkgAg二次型正定二次型正定軋機(jī)CAD/CAM/CAE研究室kA1kH2） 能逼近能逼近以近似二次函數(shù)的梯度作為下一迭代點(diǎn)處的梯度以近似二次函數(shù)的梯度作為下一迭代點(diǎn)處的梯度: :)()()()(21)()(kkTkkTkkXHXXgXFX其梯度其梯度)(kkkXHgg)(1kkkkXHggkkkkkkgH