1、主講人：魏良慶主講人：魏良慶1 1、PowellPowell法的應(yīng)用計(jì)算法的應(yīng)用計(jì)算2 2、梯度法的應(yīng)用計(jì)算、梯度法的應(yīng)用計(jì)算3 3、共軛梯度法的應(yīng)用計(jì)算、共軛梯度法的應(yīng)用計(jì)算4 4、變尺度法的應(yīng)用計(jì)算、變尺度法的應(yīng)用計(jì)算2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 l共軛與共軛方向的概念共軛與共軛方向的概念l共軛方向的形成共軛方向的形成l常用的無(wú)約束優(yōu)化設(shè)計(jì)方法的基本步常用的無(wú)約束優(yōu)化設(shè)計(jì)方法的基本步驟與幾何解釋驟與幾何解釋2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 l第第2 2章第一節(jié)所列舉的機(jī)械優(yōu)化設(shè)計(jì)問(wèn)題，章第一節(jié)所列舉的機(jī)械優(yōu)化設(shè)計(jì)問(wèn)題，都是在一定的限制條件下追求某

2、一指標(biāo)為都是在一定的限制條件下追求某一指標(biāo)為最小，它們都屬于多維約束優(yōu)化問(wèn)題。工最小，它們都屬于多維約束優(yōu)化問(wèn)題。工程問(wèn)題大都如此。程問(wèn)題大都如此。 為什么要研究多維無(wú)約束優(yōu)化問(wèn)題為什么要研究多維無(wú)約束優(yōu)化問(wèn)題? 2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 (1) (1)有些實(shí)際問(wèn)題，其數(shù)學(xué)模型本身就是一個(gè)多有些實(shí)際問(wèn)題，其數(shù)學(xué)模型本身就是一個(gè)多維無(wú)約束優(yōu)化問(wèn)題。維無(wú)約束優(yōu)化問(wèn)題。 (2)(2)通過(guò)熟悉它的解法可以為研究多維約束優(yōu)化通過(guò)熟悉它的解法可以為研究多維約束優(yōu)化問(wèn)題打下良好的基礎(chǔ)。問(wèn)題打下良好的基礎(chǔ)。 (3)(3)多維約束優(yōu)化問(wèn)題的求解可以通過(guò)一系列多多維約束優(yōu)化問(wèn)題的求解可

3、以通過(guò)一系列多維無(wú)約束優(yōu)化方法來(lái)達(dá)到。維無(wú)約束優(yōu)化方法來(lái)達(dá)到。所以多維無(wú)約束優(yōu)化所以多維無(wú)約束優(yōu)化問(wèn)題的解法是優(yōu)化設(shè)計(jì)方法的基本組成部分，也問(wèn)題的解法是優(yōu)化設(shè)計(jì)方法的基本組成部分，也是優(yōu)化方法的基礎(chǔ)。是優(yōu)化方法的基礎(chǔ)。2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 多維無(wú)約束優(yōu)化問(wèn)題是：多維無(wú)約束優(yōu)化問(wèn)題是：求求n n維設(shè)計(jì)變量維設(shè)計(jì)變量使目標(biāo)函數(shù)：使目標(biāo)函數(shù)： 12Tnx xxx( )minfxmin( )nfRxx各種多維無(wú)約束優(yōu)化解法的區(qū)別：各種多維無(wú)約束優(yōu)化解法的區(qū)別：搜索方向的不同搜索方向的不同2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 分類(lèi)：分類(lèi)：（1 1）直接解法

4、）直接解法-不使用導(dǎo)數(shù)信息，如不使用導(dǎo)數(shù)信息，如坐標(biāo)輪換坐標(biāo)輪換 法、法、PowellPowell法、隨機(jī)搜索法、單純形法法、隨機(jī)搜索法、單純形法等等（2 2）間接解法）間接解法( (解析法解析法) )-要使用導(dǎo)數(shù)，要使用導(dǎo)數(shù)，二階有二階有 梯度法、共軛梯度法、二階以上用牛頓法梯度法、共軛梯度法、二階以上用牛頓法1(0,1,2,)kkkkSkxx搜索方向的構(gòu)成問(wèn)題是多維無(wú)約束優(yōu)化方法的關(guān)鍵搜索方向的構(gòu)成問(wèn)題是多維無(wú)約束優(yōu)化方法的關(guān)鍵2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 從選定的某初始點(diǎn)從選定的某初始點(diǎn)x x(k(k) )出發(fā)，沿著以一出發(fā)，沿著以一定規(guī)律產(chǎn)生的搜索方向定規(guī)律產(chǎn)生

5、的搜索方向S S(k(k) )，取適當(dāng)?shù)牟介L(zhǎng)，取適當(dāng)?shù)牟介L(zhǎng)a a(k(k) ), ,逐次搜尋函數(shù)值下降的新迭代點(diǎn)逐次搜尋函數(shù)值下降的新迭代點(diǎn)x x(k+1)(k+1), ,使之逐步通近最優(yōu)點(diǎn)使之逐步通近最優(yōu)點(diǎn)x x* *。 2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 可以把可以把初始點(diǎn)初始點(diǎn)x x(k(k) )、搜索方向搜索方向S S(k(k) )、迭代步長(zhǎng)迭代步長(zhǎng)a a(k(k) )稱(chēng)為優(yōu)化方法算法的三要素。其中以稱(chēng)為優(yōu)化方法算法的三要素。其中以搜索方向搜索方向S S(k(k) )更為突出和重要更為突出和重要，它從根本上決定一個(gè)算法的，它從根本上決定一個(gè)算法的成敗、收斂速率的快慢等

6、。成敗、收斂速率的快慢等。 一個(gè)算法的搜索方向成為該優(yōu)化方法的基本一個(gè)算法的搜索方向成為該優(yōu)化方法的基本標(biāo)志，標(biāo)志，分析、確定搜索方向分析、確定搜索方向S S(k(k) )是研究?jī)?yōu)化方法的是研究?jī)?yōu)化方法的最根本的任務(wù)之一最根本的任務(wù)之一。2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 函數(shù)的函數(shù)的負(fù)梯度方向負(fù)梯度方向是函數(shù)值下降最快的方向是函數(shù)值下降最快的方向搜索方向搜索方向S S取該點(diǎn)的負(fù)梯度方向取該點(diǎn)的負(fù)梯度方向 ( (最速下降最速下降方向方向) )，使函數(shù)值在該點(diǎn)附近的范圍內(nèi)下降最快。，使函數(shù)值在該點(diǎn)附近的范圍內(nèi)下降最快。( )fx1(0,1,2,)kkkkSkxx1() (0,1

7、,2, )kkkka fk xxx2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 為了使目標(biāo)函數(shù)值沿搜索方向?yàn)榱耸鼓繕?biāo)函數(shù)值沿搜索方向 能夠能夠獲得最大的下降值，其步長(zhǎng)因子獲得最大的下降值，其步長(zhǎng)因子 應(yīng)取一應(yīng)取一維搜索的最佳步長(zhǎng)。即有維搜索的最佳步長(zhǎng)。即有()kfxk1()() min ()min ( )kkkkkkaaffa ffa f xxxxx2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 l根據(jù)一元函數(shù)極值的必要條件和多元復(fù)根據(jù)一元函數(shù)極值的必要條件和多元復(fù)合函數(shù)求導(dǎo)公式，得合函數(shù)求導(dǎo)公式，得 ( )()()0Tkkkkfff xxx1()()0kTkffxx1()0kT

8、kSS2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 在最速下降在最速下降( (梯度梯度) )法中，相鄰兩個(gè)迭代點(diǎn)上法中，相鄰兩個(gè)迭代點(diǎn)上的函數(shù)梯度的函數(shù)梯度相互垂直相互垂直。而搜索方向就是負(fù)梯度方。而搜索方向就是負(fù)梯度方向，因此向，因此相鄰兩個(gè)搜索方向互相垂直相鄰兩個(gè)搜索方向互相垂直。這就是說(shuō)。這就是說(shuō)在迭代點(diǎn)向函數(shù)極小點(diǎn)靠近的過(guò)程，走的是曲折在迭代點(diǎn)向函數(shù)極小點(diǎn)靠近的過(guò)程，走的是曲折的路線。形成的路線。形成“之之”字形的鋸齒現(xiàn)象，而且字形的鋸齒現(xiàn)象，而且越接越接近極小點(diǎn)鋸齒越細(xì)。近極小點(diǎn)鋸齒越細(xì)。 2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 開(kāi)始給定結(jié)束0,x()kkf d

9、x1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k 2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 例例2.4-1 2.4-1 求目標(biāo)函數(shù)求目標(biāo)函數(shù) 的極小點(diǎn)。的極小點(diǎn)。初始點(diǎn)初始點(diǎn)解：初始點(diǎn)處函數(shù)值及梯度分別為解：初始點(diǎn)處函數(shù)值及梯度分別為02,2Tx00102()10424()50100 xfxfxxx2212( )25fxxx2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 沿負(fù)梯度方向進(jìn)行一維搜索，有沿負(fù)梯度方向進(jìn)行一維搜索，有0100002 4()2 100fxxx0為一維搜索最佳步長(zhǎng)，應(yīng)滿(mǎn)足極值必要條件為一維搜索最佳步長(zhǎng)，應(yīng)滿(mǎn)足極值必要條件 12

10、2( )min (2 4 )25(2 100 )min ( )f x2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 00( )8(2 4) 5000(2 100)0 算出一維搜索最佳步長(zhǎng)算出一維搜索最佳步長(zhǎng) 06260.020 030 7231252第一次迭代設(shè)計(jì)點(diǎn)位置和函數(shù)值第一次迭代設(shè)計(jì)點(diǎn)位置和函數(shù)值 01202 41.9198772 1000.307178 5 10 x1( ) 3.686164fx繼續(xù)作下去，經(jīng)繼續(xù)作下去，經(jīng)1010次迭代后，得到最優(yōu)解次迭代后，得到最優(yōu)解 0 0Tx()0fx2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 這一問(wèn)題的目標(biāo)函數(shù)這一問(wèn)題的目標(biāo)函

11、數(shù)f f( (x x) )的等值線為一簇橢圓。的等值線為一簇橢圓。將上例中目標(biāo)函數(shù)將上例中目標(biāo)函數(shù) 引入變換引入變換 y1=x1,y2=5x2則函數(shù)則函數(shù)f(x)f(x)變?yōu)椋鹤優(yōu)椋?212( )25fxxx221212(,)y yyy其等值線由橢圓變成一簇同心圓。其等值線由橢圓變成一簇同心圓。2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 仍從仍從 即即 出發(fā)進(jìn)行最速下降法出發(fā)進(jìn)行最速下降法尋優(yōu)。此時(shí)：尋優(yōu)。此時(shí)：02,2Tx02,10Ty00102()10424()220yyyyy沿負(fù)梯度方向進(jìn)行一維搜索沿負(fù)梯度方向進(jìn)行一維搜索：1000000()2 42410 201020 yyy

12、2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 為一維搜索最佳步長(zhǎng)，可由極值條件：為一維搜索最佳步長(zhǎng)，可由極值條件：10022()min ()min( )( )(24 )(1020 ) yyy0()0由由0260.552從而算得一步計(jì)算后設(shè)計(jì)點(diǎn)的位置及其目標(biāo)函數(shù)：從而算得一步計(jì)算后設(shè)計(jì)點(diǎn)的位置及其目標(biāo)函數(shù)：2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 010124010200()0 yy經(jīng)變換后，只需一次迭代，就可找到最優(yōu)解。經(jīng)變換后，只需一次迭代，就可找到最優(yōu)解。這是因?yàn)榻?jīng)過(guò)尺度變換：這是因?yàn)榻?jīng)過(guò)尺度變換：11225yxyx等值線由橢圓變成圓。等值線由橢圓變成圓。1 12.4

13、2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 （1）理論明確，程序簡(jiǎn)單，理論明確，程序簡(jiǎn)單，對(duì)初始點(diǎn)要求不嚴(yán)格。對(duì)初始點(diǎn)要求不嚴(yán)格。（2）對(duì)一般函數(shù)而言，收對(duì)一般函數(shù)而言，收斂速度并不快，因?yàn)樽钏贁克俣炔⒉豢欤驗(yàn)樽钏傧陆捣较騼H是指某點(diǎn)的一下降方向僅是指某點(diǎn)的一個(gè)個(gè)局部局部性質(zhì)。性質(zhì)。2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 （4）梯度法的收斂速度與目標(biāo)函數(shù)的性質(zhì)密切相梯度法的收斂速度與目標(biāo)函數(shù)的性質(zhì)密切相關(guān)。對(duì)于關(guān)。對(duì)于等值線等值線( (面面) )為同心圓（球）的目標(biāo)函數(shù)，為同心圓（球）的目標(biāo)函數(shù)，一次搜索即可達(dá)到極小點(diǎn)。一次搜索即可達(dá)到極小點(diǎn)。（3）相鄰兩次搜索方向的正交性決定

14、了迭代過(guò)程相鄰兩次搜索方向的正交性決定了迭代過(guò)程的的路線呈鋸齒狀路線呈鋸齒狀，在，在遠(yuǎn)離極小點(diǎn)時(shí)逼近速度較快，遠(yuǎn)離極小點(diǎn)時(shí)逼近速度較快，而在接近極小點(diǎn)時(shí)逼近速度較慢。而在接近極小點(diǎn)時(shí)逼近速度較慢。2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 設(shè)設(shè)G G為為n nn n階階實(shí)對(duì)稱(chēng)正定矩陣實(shí)對(duì)稱(chēng)正定矩陣，如果有兩個(gè)，如果有兩個(gè)n n維維向量向量S S0 0和和S S1 1滿(mǎn)足滿(mǎn)足 ，則稱(chēng)向量，則稱(chēng)向量S S0 0與與S S1 1 關(guān)于矩陣關(guān)于矩陣G G共軛共軛。01()0TSS G2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 01()0TSS G當(dāng)當(dāng)G為單位矩陣時(shí)為單位矩陣時(shí)，01

15、()0TSS 假設(shè)目標(biāo)函數(shù)假設(shè)目標(biāo)函數(shù)f(x)在極值點(diǎn)附近的二次近似函數(shù)為在極值點(diǎn)附近的二次近似函數(shù)為1( )2TfTxx Gxb xc對(duì)二維情況對(duì)二維情況任選取初始點(diǎn)任選取初始點(diǎn)x0沿某個(gè)下降方向沿某個(gè)下降方向S0作一維搜索，得作一維搜索，得x11000Sxx2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 因?yàn)橐驗(yàn)?是沿是沿S0方向搜索的最佳步長(zhǎng)，即在方向搜索的最佳步長(zhǎng)，即在點(diǎn)點(diǎn)x1處函數(shù)處函數(shù)f（x）沿方向沿方向S0的方向?qū)?shù)為零的方向?qū)?shù)為零?？紤]到點(diǎn)?？紤]到點(diǎn)x1處方向?qū)?shù)與梯度之間的關(guān)系，故有處方向?qū)?shù)與梯度之間的關(guān)系，故有01100()0TffSS xx如果按最速下降法，選擇

16、負(fù)梯度方向如果按最速下降法，選擇負(fù)梯度方向 為搜為搜索方向，則將發(fā)生索方向，則將發(fā)生鋸齒鋸齒現(xiàn)象現(xiàn)象 。1( )f x2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 0S0 x0 x1x*1 11S11()fx0取下一次的迭代搜索方向取下一次的迭代搜索方向S1直指極小點(diǎn)直指極小點(diǎn)x* S12.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 l如果能夠選定這樣的搜索方向，那么對(duì)于二元如果能夠選定這樣的搜索方向，那么對(duì)于二元二次函數(shù)二次函數(shù)只需順次進(jìn)行只需順次進(jìn)行S0、S1兩次直線搜索就兩次直線搜索就可以求到極小點(diǎn)可以求到極小點(diǎn)x*，即

17、有，即有111Sxx那么這樣的那么這樣的S1方向應(yīng)該滿(mǎn)足什么條件呢方向應(yīng)該滿(mǎn)足什么條件呢 ? ?01()0TSS G2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 對(duì)于前述的二次函數(shù)對(duì)于前述的二次函數(shù): :有有11( )fxGxb1( )2TfTxx Gxb xc當(dāng)當(dāng) 時(shí)時(shí) 。1xx10 x* *是是f( (x) )極小點(diǎn)，極小點(diǎn)，應(yīng)滿(mǎn)足極值必要條件，故有應(yīng)滿(mǎn)足極值必要條件，故有( )0f xG x b1111111( )()( )fSfxSb xG xbxG0將等式兩邊同時(shí)左乘將等式兩邊同時(shí)左乘 得：得：0()TS01()0TSS G2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法

18、 01()0TSS G就是使就是使S1直指極小點(diǎn)直指極小點(diǎn)x*，S S1 1所必須滿(mǎn)足的條件。所必須滿(mǎn)足的條件。兩個(gè)向量?jī)蓚€(gè)向量S S0 0和和S S1 1稱(chēng)為稱(chēng)為G的共軛向量，或稱(chēng)的共軛向量，或稱(chēng)SO和和S S1 1對(duì)對(duì)G是共軛方向。是共軛方向。 021()( )0TSfSx2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 性質(zhì)性質(zhì)1 1 若非零向量系若非零向量系S0, ,S1, ,S2,Sm-1是是對(duì)對(duì)G共軛共軛，則這則這m個(gè)向量是線性無(wú)關(guān)個(gè)向量是線性無(wú)關(guān)的的。性質(zhì)性質(zhì)2 2 在在n維空間中維空間中互相共軛的非零向量的個(gè)數(shù)互相共軛的非零向量的個(gè)數(shù)不超過(guò)不超過(guò)n。 性質(zhì)性質(zhì)3 3 從任意

19、初始點(diǎn)出發(fā)，順次沿從任意初始點(diǎn)出發(fā)，順次沿n個(gè)個(gè)G的共軛方的共軛方向向S0, ,S1, , S2,進(jìn)行一維搜索，進(jìn)行一維搜索，最多經(jīng)過(guò)最多經(jīng)過(guò)n次迭代次迭代就可以找到的就可以找到的二次二次函數(shù)函數(shù)f( (x) )極小點(diǎn)。極小點(diǎn)。 2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 開(kāi)始給定結(jié)束00,xd1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k 提供新的共軛方向關(guān)鍵：新的共關(guān)鍵：新的共軛方向軛方向確定確定2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 l共軛梯度法是共軛方向法中的一種共軛梯度法是共軛方向法中的一種，該方法中，該方法中每一個(gè)共軛向量都是每一

20、個(gè)共軛向量都是依賴(lài)于迭代點(diǎn)處的負(fù)梯度依賴(lài)于迭代點(diǎn)處的負(fù)梯度而構(gòu)造出來(lái)而構(gòu)造出來(lái)。l從從xk出發(fā)，沿負(fù)梯度方向作一維搜索出發(fā)，沿負(fù)梯度方向作一維搜索: :2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 1(0,1,2, )kkkkSkxx()kkSf x設(shè)與設(shè)與Sk共共軛的下一個(gè)方向軛的下一個(gè)方向Sk+1由由Sk和點(diǎn)和點(diǎn)xk+1的負(fù)的負(fù)梯度的線形組合構(gòu)成，即：梯度的線形組合構(gòu)成，即：11()kkkkSfS x21()( )0kTkSfSx共軛條件：共軛條件：2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 則：則：21()( )() 0kTkkkfffSxxx解得：解得：212()()

21、()()()()kTkkkkTkkffffffxxxxxx2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 ()kkfxGxb則則11()kkfxGxb上兩式相減，并代入上兩式相減，并代入1kkkkSxx1()()kkkkSff Gxx令令1( )2TfTxx Gxb xc為函數(shù)的泰勒二次展開(kāi)式為函數(shù)的泰勒二次展開(kāi)式2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 11()kkkkSfSx1()()kkkkSffGxx將式將式與式與式兩邊相乘，并應(yīng)用兩邊相乘，并應(yīng)用共軛條件共軛條件得：得：11()()()()0kkkkkffffxxxx21112()()()()()()kkTkkkTk

22、kffffffxxxxxx2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 因此因此11()kkkkSfS x212()()kkkffxx1(0,1,2,)kkkkSkxx2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 迭代精度迭代精度 。 2212112( )242fxxxxxx ，已知初始點(diǎn)已知初始點(diǎn)1,11,1T T解：解：1 1）第一次沿負(fù)梯度方向搜尋）第一次沿負(fù)梯度方向搜尋計(jì)算初始點(diǎn)處的梯度計(jì)算初始點(diǎn)處的梯度0120212244( )422xxfxxxx0.0012.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 01

23、20212244()422xxfxxxx01000001 4141 212S xx為一維搜索最佳步長(zhǎng)，應(yīng)滿(mǎn)足為一維搜索最佳步長(zhǎng)，應(yīng)滿(mǎn)足1002()min()min(40203)ffSxx2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 得:00.25120.5x2 2）第二次迭代：）第二次迭代：21200()50.2520()ffxx11()2fx11002()1.5SfS x2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 得:211222 20.51.50.5 1.5Sxx代入目標(biāo)函數(shù)代入目標(biāo)函數(shù)22( ) (2 2 )2(0.5 1.5 )2(2 2 )(0.5 1.5 ) 4(

24、2 2 )( )f x 2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 ( )0 得得122240,( )8,( )20ff xxx因因2()0fx收斂。收斂。由由從而有：從而有：2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 共軛梯度法特點(diǎn)共軛梯度法特點(diǎn)1 1）每步迭代只需存儲(chǔ)若干向量（適用于大）每步迭代只需存儲(chǔ)若干向量（適用于大規(guī)模問(wèn)題）；規(guī)模問(wèn)題）；2 2）有二次終結(jié)性（對(duì)于正定二次函數(shù)，至）有二次終結(jié)性（對(duì)于正定二次函數(shù)，至多多n n次迭代可達(dá)次迭代可達(dá)opt.opt.） 2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 1 1、梯度法：、梯度法：搜索方向?yàn)槟繕?biāo)函數(shù)負(fù)梯

25、度方向，搜索方向?yàn)槟繕?biāo)函數(shù)負(fù)梯度方向，計(jì)算速度開(kāi)始搜索下降快，愈接近極值點(diǎn)下降愈計(jì)算速度開(kāi)始搜索下降快，愈接近極值點(diǎn)下降愈慢。對(duì)初始點(diǎn)的選擇要求不高，適合與其它方法慢。對(duì)初始點(diǎn)的選擇要求不高，適合與其它方法結(jié)合使用。結(jié)合使用。2 2、共軛梯度法：、共軛梯度法：第一步搜索沿負(fù)梯度方向，然第一步搜索沿負(fù)梯度方向，然后沿負(fù)梯度的共軛方向搜索。后沿負(fù)梯度的共軛方向搜索。計(jì)算效率優(yōu)于梯度計(jì)算效率優(yōu)于梯度法。法。對(duì)初始點(diǎn)沒(méi)有特殊的要求，不需要計(jì)算二階對(duì)初始點(diǎn)沒(méi)有特殊的要求，不需要計(jì)算二階偏導(dǎo)數(shù)矩陣及其逆矩陣，計(jì)算量與梯度法相當(dāng)。偏導(dǎo)數(shù)矩陣及其逆矩陣，計(jì)算量與梯度法相當(dāng)。適用于各種大規(guī)模的問(wèn)題適用于各種大規(guī)

26、模的問(wèn)題。2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 鮑威爾（鮑威爾（PowellPowell）法是）法是直接利用函數(shù)值來(lái)構(gòu)造共直接利用函數(shù)值來(lái)構(gòu)造共軛方向的一種方法軛方向的一種方法 1( )2TfTxx Gxb xc對(duì)函數(shù)：對(duì)函數(shù)：基本思想：基本思想：在不用導(dǎo)數(shù)的前提下，在迭代中逐在不用導(dǎo)數(shù)的前提下，在迭代中逐次構(gòu)造次構(gòu)造G的共軛方向的共軛方向2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 jjk kkkSd dgg gk+1k+1xxk+1設(shè)設(shè)xk, xk+1為從不同點(diǎn)出發(fā)，沿同一方向?yàn)閺牟煌c(diǎn)出發(fā)，沿同一方向Sj進(jìn)行一維進(jìn)行一維搜索而得到的兩個(gè)極小點(diǎn)。搜索而得到的兩個(gè)極小

27、點(diǎn)。 jS2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 根據(jù)梯度和等值面相垂直的性質(zhì)，根據(jù)梯度和等值面相垂直的性質(zhì)，Sj和和xk, ,xk+1兩兩點(diǎn)處的梯度點(diǎn)處的梯度gk，gk+1之間存在關(guān)系之間存在關(guān)系: :1()0,()0jTkjTkSSgg另一方面，對(duì)于上述二次函數(shù)，其另一方面，對(duì)于上述二次函數(shù)，其xk，xk+1兩點(diǎn)處兩點(diǎn)處的梯度可表示為的梯度可表示為: :11,kkkkgGxbgGxb2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 因而有因而有11() ()()()0j Tkkj TkkSSggG xx1kkkSxx取取這說(shuō)明只要沿這說(shuō)明只要沿Sj方向分別對(duì)函作兩次一維搜

28、索，方向分別對(duì)函作兩次一維搜索，得到兩個(gè)極小點(diǎn)得到兩個(gè)極小點(diǎn)xk和和xk+1，那么這兩點(diǎn)的，那么這兩點(diǎn)的連線所連線所給出的方向給出的方向Sk就是與就是與Sj一起一起對(duì)對(duì)G共軛共軛的方向。的方向。2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 1 1）任選一初始點(diǎn)）任選一初始點(diǎn)x0，再，再選兩個(gè)線性無(wú)關(guān)的向量，選兩個(gè)線性無(wú)關(guān)的向量，如 坐 標(biāo) 軸 單 位 向 量如 坐 標(biāo) 軸 單 位 向 量e1=1,0T和和e2=0,1T作為作為初始搜索方向。初始搜索方向。2 2）從）從x0出發(fā)，順次沿出發(fā)，順次沿e1，e2作一維搜索，得作一維搜索，得 點(diǎn)，兩點(diǎn)連線點(diǎn)，兩點(diǎn)連線得一新方向得一新方向S100

29、12,xxx1x2x0o oe1e2d1d2x*102x10 x11x12x01x11002S xx2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 用用S1代替代替e1形成兩個(gè)線形成兩個(gè)線性無(wú)關(guān)向量性無(wú)關(guān)向量S1, e2 ，作，作為下一輪迭代的搜索方為下一輪迭代的搜索方向。再?gòu)南颉Ｔ購(gòu)?出發(fā)，沿出發(fā)，沿S S1 1作一維搜索得點(diǎn)作一維搜索得點(diǎn) ，作為下一輪迭代的初始作為下一輪迭代的初始點(diǎn)。點(diǎn)。 02x10 xx1x2x0o oe1e2d1d2x*102x10 x11x12x01x2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 x1x2x0o oe1e2d1d2x*102x10 x1

30、1x12x01x3 3）從出發(fā)）從出發(fā) ，順次，順次沿沿e2,S1作一維搜索，作一維搜索，得到點(diǎn)得到點(diǎn) ，兩點(diǎn)，兩點(diǎn)連線得一新方向連線得一新方向: :1112,x x21120S xx10 x2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 沿沿S S2 2作一維搜索得點(diǎn)作一維搜索得點(diǎn)x2 即是二維問(wèn)題的極即是二維問(wèn)題的極小點(diǎn)小點(diǎn)x* 方法的基本迭代格式方法的基本迭代格式包括包括共共軛方向產(chǎn)生和軛方向產(chǎn)生和方向替換兩主要步驟。方向替換兩主要步驟。x1x2x0o oe1e2d1d2x*102x10 x11x12x01x2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 把二維情況的基本算法

31、擴(kuò)展到把二維情況的基本算法擴(kuò)展到n維，則鮑維，則鮑威爾基本算法的要點(diǎn)是：威爾基本算法的要點(diǎn)是： 在每一輪迭代中總有一個(gè)始點(diǎn)（第一輪的在每一輪迭代中總有一個(gè)始點(diǎn)（第一輪的始點(diǎn)是任選的初始點(diǎn)）和始點(diǎn)是任選的初始點(diǎn)）和n個(gè)線性獨(dú)立的搜索個(gè)線性獨(dú)立的搜索方向。從始點(diǎn)出發(fā)順次沿方向。從始點(diǎn)出發(fā)順次沿n個(gè)方向作一維搜索個(gè)方向作一維搜索得一終點(diǎn)，由得一終點(diǎn)，由始點(diǎn)和終點(diǎn)決定了一個(gè)新的搜索始點(diǎn)和終點(diǎn)決定了一個(gè)新的搜索方向。方向。 2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 l用這個(gè)方向替換原來(lái)用這個(gè)方向替換原來(lái)n n個(gè)方向中的一個(gè)，于是個(gè)方向中的一個(gè)，于是形成新的搜索方向組。替換的原則是形成新的搜索

32、方向組。替換的原則是去掉原方去掉原方向組的第一個(gè)方向而將新方向排在原方向的最向組的第一個(gè)方向而將新方向排在原方向的最后。后。此外規(guī)定，從這一輪的搜索終點(diǎn)出發(fā)沿新此外規(guī)定，從這一輪的搜索終點(diǎn)出發(fā)沿新的搜索方向作一維搜索而得到的極小點(diǎn)，作為的搜索方向作一維搜索而得到的極小點(diǎn)，作為下一輪迭代的始點(diǎn)。這樣就形成算法的循環(huán)。下一輪迭代的始點(diǎn)。這樣就形成算法的循環(huán)。 上述基本算法僅具有理論意義上述基本算法僅具有理論意義 。2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 因?yàn)樵诘械囊驗(yàn)樵诘械膎個(gè)搜索方向有時(shí)會(huì)變成線個(gè)搜索方向有時(shí)會(huì)變成線性相關(guān)而不能形成共軛方向的情況性相關(guān)而不能形成共軛方向的情

33、況。從而。從而導(dǎo)致可能求不到極小點(diǎn)，所以上述基本算導(dǎo)致可能求不到極小點(diǎn)，所以上述基本算法有待改進(jìn)。法有待改進(jìn)。 2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 在鮑威爾基本算法中，每一輪迭代都用連結(jié)始點(diǎn)在鮑威爾基本算法中，每一輪迭代都用連結(jié)始點(diǎn)和終點(diǎn)所產(chǎn)生出的搜索方向去替換原向量組中的和終點(diǎn)所產(chǎn)生出的搜索方向去替換原向量組中的第一個(gè)向量，而不管它的第一個(gè)向量，而不管它的“好壞好壞”，這是產(chǎn)生向，這是產(chǎn)生向量組線性相關(guān)的原因所在。量組線性相關(guān)的原因所在。 2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 在改進(jìn)的算法中在改進(jìn)的算法中首先判斷原向量組是否需要替首先判斷原向量組是否需要替換

34、。換。如果需要替換，還要如果需要替換，還要進(jìn)一步判斷原向量組進(jìn)一步判斷原向量組中哪個(gè)向量最壞，中哪個(gè)向量最壞，然后然后再用新產(chǎn)生的向量替換再用新產(chǎn)生的向量替換這個(gè)最壞的向量，這個(gè)最壞的向量，以保證逐次生成共軛方向。以保證逐次生成共軛方向。2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 l為此，要解決兩個(gè)關(guān)鍵問(wèn)題為此，要解決兩個(gè)關(guān)鍵問(wèn)題： （1）Sk1是否較好？是否應(yīng)該進(jìn)入新的方向組？是否較好？是否應(yīng)該進(jìn)入新的方向組？即方向組是否進(jìn)行更新？即方向組是否進(jìn)行更新？ （2 2）如果應(yīng)該更新方向組，）如果應(yīng)該更新方向組， Sk1不一定替換方不一定替換方向向 ，而是有選擇地替換某一方向而是有選擇地

35、替換某一方向 。1kSkmS2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 令在令在k次循環(huán)中次循環(huán)中00231()()()kknknFfFfFfxxx01,kkknnx x x100()2kkkkkknnnnxxxxxx（）分別稱(chēng)為一輪迭代的分別稱(chēng)為一輪迭代的始點(diǎn)、終點(diǎn)和反射點(diǎn)始點(diǎn)、終點(diǎn)和反射點(diǎn)。2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 則在循環(huán)中函數(shù)下降最多的第則在循環(huán)中函數(shù)下降最多的第m次迭代是次迭代是() (0,1,2, )kiiffinx1(1,2, )iiiffin 記記：11maxmimmi nff 相應(yīng)的方向?yàn)橄鄳?yīng)的方向?yàn)?。kmS002,nFfFf因此因此2

36、.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 為了構(gòu)成共為了構(gòu)成共軛性好的方向組，須遵循下列準(zhǔn)則：軛性好的方向組，須遵循下列準(zhǔn)則：在在k次循環(huán)中，若次循環(huán)中，若滿(mǎn)足條件滿(mǎn)足條件：30FF202302(2)()mFFF FF2030.5()mFF則選用新方向則選用新方向Sk，并在第并在第k+1迭代中用迭代中用Sk替換對(duì)應(yīng)于替換對(duì)應(yīng)于 的方向的方向 。否則，仍然用原方向組進(jìn)行第。否則，仍然用原方向組進(jìn)行第k+1迭代。迭代。mkmS2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 這樣重復(fù)迭代的結(jié)果，后面加進(jìn)去的向量都彼此對(duì)這樣重復(fù)迭代的結(jié)果，后面加進(jìn)去的向量都彼此對(duì)G共軛，共軛，經(jīng)經(jīng)n輪

37、迭代即可得到一個(gè)由輪迭代即可得到一個(gè)由n個(gè)共軛方向所組成的方向組。對(duì)個(gè)共軛方向所組成的方向組。對(duì)于于n次函次，最多次函次，最多n次就可找到極小點(diǎn)，而對(duì)一般函數(shù)，往往次就可找到極小點(diǎn)，而對(duì)一般函數(shù)，往往要超過(guò)要超過(guò)n n次才能找到極小點(diǎn)（這里次才能找到極小點(diǎn)（這里“n”表示設(shè)計(jì)空間的維表示設(shè)計(jì)空間的維數(shù)）。數(shù)）。 2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 例例2.4-5 2.4-5 用改進(jìn)的鮑威爾法求目標(biāo)函數(shù)用改進(jìn)的鮑威爾法求目標(biāo)函數(shù)的最優(yōu)解。已知初始點(diǎn)的最優(yōu)解。已知初始點(diǎn)1,1T，迭代精度，迭代精度221211 2( )242fxxxxxx0.001解：（解：（1 1）第）第1 1

38、輪迭代計(jì)算輪迭代計(jì)算0011 x0000()3Fff x2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 沿沿e1方向進(jìn)行一維搜索方向進(jìn)行一維搜索0201min()43fxe12得得00101 11132101 xxe011( )7ffx2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 以以 為起點(diǎn)，沿第二坐標(biāo)軸方向?yàn)槠瘘c(diǎn)，沿第二坐標(biāo)軸方向e2進(jìn)行一維搜索進(jìn)行一維搜索01x0212min ()227fxe20.5得得0021213030.5111.5 xxe022()7.5ff x2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 確定此輪中的最大下降量及其相應(yīng)方向確定此輪中的最大下

39、降量及其相應(yīng)方向0010101()()4ffff xx0021212()()0.5ffff xx12max,4m 2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 反射點(diǎn)及其函數(shù)值反射點(diǎn)及其函數(shù)值000320315221.512 xxx033( )7Ffx檢驗(yàn)檢驗(yàn)PowellPowell條件條件202302(2)()1.25mFFF FF2030.5()32mFF2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 l由于滿(mǎn)足由于滿(mǎn)足PowellPowell條件，則淘汰函數(shù)值下降量最條件，則淘汰函數(shù)值下降量最大的方向大的方向e1，下一輪的基本方向組為下一輪的基本方向組為e2， 。03S構(gòu)成

40、新的方向構(gòu)成新的方向 0003203121.510.5S xx2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 沿沿 方向一維搜索得極小點(diǎn)和極小值方向一維搜索得極小點(diǎn)和極小值03S13.81.7x1()7.9f x此點(diǎn)為下輪迭代初始點(diǎn)。此點(diǎn)為下輪迭代初始點(diǎn)。 按點(diǎn)距準(zhǔn)則檢驗(yàn)終止條件按點(diǎn)距準(zhǔn)則檢驗(yàn)終止條件 11220(3.8 1)(1.7 1)2.886xx需進(jìn)行第二輪迭代計(jì)算。需進(jìn)行第二輪迭代計(jì)算。2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 （2 2）第）第2 2輪迭代計(jì)算輪迭代計(jì)算此輪基本方向組為此輪基本方向組為e2， ，分別相當(dāng)于分別相當(dāng)于 ， ，起始點(diǎn)為起始點(diǎn)為 = 03S

41、11S12S10 x1x沿沿e2方向進(jìn)行一維搜索得方向進(jìn)行一維搜索得 113.81.9x11()7.98f x2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 以以 為起點(diǎn)沿為起點(diǎn)沿 方向一維搜索得方向一維搜索得11x03S123.961.9x122()7.996ffx確定此輪中函數(shù)值最大下降量及其相應(yīng)方向確定此輪中函數(shù)值最大下降量及其相應(yīng)方向10.08 20.016 12max,0.08m 2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 l反射點(diǎn)及其函數(shù)值反射點(diǎn)及其函數(shù)值1113203.963.84.12221.941.72.18 xxx133()7.964Ff x檢驗(yàn)檢驗(yàn)Powe

42、llPowell條件，淘汰函數(shù)值下降量最大的方向條件，淘汰函數(shù)值下降量最大的方向e2，下一輪的基本方向組應(yīng)為下一輪的基本方向組應(yīng)為 ， 。 03S13S2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 構(gòu)成新的方向構(gòu)成新的方向1113203.963.80.161.941.70.24Sxx沿沿 方向進(jìn)行一維搜索得方向進(jìn)行一維搜索得13S242 x2()8f x2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 檢驗(yàn)終止條件檢驗(yàn)終止條件 22220(4 3.8)(2 1.7)0.36xx（3 3）第）第3 3輪迭代計(jì)算輪迭代計(jì)算此輪基本方向組為此輪基本方向組為 ， ，起始點(diǎn)為起始點(diǎn)為 ，先先

43、后沿后沿 ， 方向方向，進(jìn)行一維搜索，得進(jìn)行一維搜索，得03S13S20 x2x03S13S2142 x2242 x2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 檢驗(yàn)終止條件檢驗(yàn)終止條件 故最優(yōu)解故最優(yōu)解 22200 xx*42 x*()8f x2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 實(shí)際上，前兩輪迭代的實(shí)際上，前兩輪迭代的 ， 為共軛方向，由于本例目為共軛方向，由于本例目標(biāo)函數(shù)是二次函數(shù)，按共軛方向的二次收斂性，故前兩標(biāo)函數(shù)是二次函數(shù)，按共軛方向的二次收斂性，故前兩輪的結(jié)果就是問(wèn)題的最優(yōu)解，但每一輪迭代都需要進(jìn)行輪的結(jié)果就是問(wèn)題的最優(yōu)解，但每一輪迭代都需要進(jìn)行n n+1

44、+1次迭代。次迭代。13S23S2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 補(bǔ)充知識(shí)：補(bǔ)充知識(shí)：牛頓法牛頓法( )x( )x( )f x1kx( )f x2( )( )()() ()1()()()2kkTkkTkkffffxxxxxxxxxxx設(shè)設(shè) 為為 的極小點(diǎn)的極小點(diǎn) 1kx( )x1() 0kx21()()()0kkkkffxxxx2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 121()() (0,1,2, )kkkkffk xxxx這就是多元函數(shù)求極值的這就是多元函數(shù)求極值的牛頓法迭代公式牛頓法迭代公式。 對(duì)于二次函數(shù)，海賽矩陣是一個(gè)常矩陣，其中對(duì)于二次函數(shù)，海賽矩陣

45、是一個(gè)常矩陣，其中各元素均為常數(shù)。因此，無(wú)論從任何點(diǎn)出發(fā)，只各元素均為常數(shù)。因此，無(wú)論從任何點(diǎn)出發(fā)，只需一步就可找到極小點(diǎn)。需一步就可找到極小點(diǎn)。2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 例例2 24 4 求目標(biāo)函數(shù)求目標(biāo)函數(shù) 的極小點(diǎn)的極小點(diǎn)。初始點(diǎn)初始點(diǎn)2212( )25fxxx02,2Tx102010102402( )( )121000050ff xxxx經(jīng)過(guò)一次迭代即求得極小點(diǎn)經(jīng)過(guò)一次迭代即求得極小點(diǎn) ，函數(shù)極小值函數(shù)極小值 。00 x()0fx2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 開(kāi)始給定結(jié)束0,x21()()kkkff dxx1:min()kkkkkkk

46、fxxdxd1kkxx*1kxx否是1kk0k 2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 l 牛頓法的主要缺點(diǎn)牛頓法的主要缺點(diǎn)是每次迭代都要計(jì)是每次迭代都要計(jì)算函數(shù)的二階導(dǎo)數(shù)矩陣，并對(duì)該矩陣求逆。算函數(shù)的二階導(dǎo)數(shù)矩陣，并對(duì)該矩陣求逆。這樣工作量很大。特別是矩陣求逆，當(dāng)維這樣工作量很大。特別是矩陣求逆，當(dāng)維數(shù)高時(shí)工作量更大數(shù)高時(shí)工作量更大 。 2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 變尺度法是在牛頓法的思想上進(jìn)行了重大改進(jìn)變尺度法是在牛頓法的思想上進(jìn)行了重大改進(jìn)的一類(lèi)方法。的一類(lèi)方法。 1.1.基本思想基本思想 變量的尺度變換是放大或縮小各個(gè)坐標(biāo)。通過(guò)變量的尺度變換是放

47、大或縮小各個(gè)坐標(biāo)。通過(guò)尺度變換可以把函數(shù)的偏心程度降到最低限度。尺度變換可以把函數(shù)的偏心程度降到最低限度。 2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 把把 的尺度放大的尺度放大5 5倍，則目標(biāo)函數(shù)等值線由一簇倍，則目標(biāo)函數(shù)等值線由一簇橢圓變成一簇同心圓。橢圓變成一簇同心圓。例如在用最速下降法求例如在用最速下降法求 的極小的極小2212( )25fxxx值時(shí)值時(shí), ,需要進(jìn)行需要進(jìn)行1010次迭代才能達(dá)到極小點(diǎn)次迭代才能達(dá)到極小點(diǎn)0,0Tx如作變換如作變換 y1=x1, y2=5x2x2221212(,)y yyy消除了函數(shù)的偏心，用最速下降法只需一次迭代即消除了函數(shù)的偏心，用最速下

48、降法只需一次迭代即可求得極小點(diǎn)?？汕蟮脴O小點(diǎn)。2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 Ak 是需要構(gòu)造是需要構(gòu)造nn的一個(gè)對(duì)稱(chēng)方陣，稱(chēng)為的一個(gè)對(duì)稱(chēng)方陣，稱(chēng)為變尺度矩陣變尺度矩陣如如Ak=I, 則得到梯度法則得到梯度法 ；21()kkf Ax 則得到阻尼牛頓法則得到阻尼牛頓法 ；如如迭代方向：迭代方向：1()(0,1,2, )kkkSfkAx迭代公式：迭代公式：1()(0,1,2, )kkkkkfkxxAx變尺度法的關(guān)鍵在于尺度矩陣變尺度法的關(guān)鍵在于尺度矩陣A Ak k的產(chǎn)生。的產(chǎn)生。2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 從初始矩陣從初始矩陣A0=I( (單位矩陣單

49、位矩陣) )開(kāi)始，通過(guò)對(duì)公式開(kāi)始，通過(guò)對(duì)公式 1kkkAAA中修正矩陣中修正矩陣 的不斷修正，在迭代中逐步逼近于的不斷修正，在迭代中逐步逼近于 kA1()kGx因此，一旦達(dá)到最優(yōu)點(diǎn)附近，就可望達(dá)到牛頓法的因此，一旦達(dá)到最優(yōu)點(diǎn)附近，就可望達(dá)到牛頓法的收斂速度收斂速度。2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 1 1）DFPDFP法（法（DavidonDavidon-Fletcher-Powell)-Fletcher-Powell)TkkkkkTkkkTkkTkkxxAggAAxggAg111()( )kkkkkkkkff gggxxxxx式中式中2.4 2.4 多維無(wú)約束優(yōu)化方法多維

50、無(wú)約束優(yōu)化方法 DFPDFP算法由于舍入誤差和一維搜索不精確，有可能算法由于舍入誤差和一維搜索不精確，有可能導(dǎo)致構(gòu)造矩陣的正定性遭到破壞，以至算法不穩(wěn)定。導(dǎo)致構(gòu)造矩陣的正定性遭到破壞，以至算法不穩(wěn)定。BFGSBFGS算法對(duì)于維數(shù)較高問(wèn)題具有更好的穩(wěn)定性。算法對(duì)于維數(shù)較高問(wèn)題具有更好的穩(wěn)定性。 1 kk Tk Tkkkkk Tk Tkk TkkkkTkk TxxgAgAxxxgxgAgxxgA2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 開(kāi)始給定結(jié)束0,x000()f gxAI1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kkkn11111()kkkkkkkkf gx

51、gggxxx11kkk AAA01kxx0k kkk dA g是否2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 l解：解： 1）取初始點(diǎn)取初始點(diǎn) ，為了按為了按DFPDFP法構(gòu)法構(gòu)造第一次搜尋方向造第一次搜尋方向S0，需計(jì)算初始點(diǎn)處的梯度，需計(jì)算初始點(diǎn)處的梯度221212112( ,)242f x xxxxxx01 1Tx01200212244( )422xxfxx xgx2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 取初始變尺度矩陣為單位矩陣取初始變尺度矩陣為單位矩陣A0=I，則第一，則第一次搜尋方向?yàn)榇嗡褜し较驗(yàn)?00010440122S A g2.4 2.4 多維無(wú)約束優(yōu)化方法多維無(wú)約束優(yōu)化方法 沿沿S0方向進(jìn)行一維搜索，得