無約束優(yōu)化方法ppt課件

1、第四章 無約束優(yōu)化方法第一節(jié) 概述 第1章所列舉的機械優(yōu)化設(shè)計問題，都是在一定的限制條件下追求某一目的為最小，它們都屬于約束優(yōu)化問題。 約束優(yōu)化問題的求解轉(zhuǎn)化為一系列的無約束優(yōu)化問題實現(xiàn)的。 因此，無約束優(yōu)化問題的解法是優(yōu)化設(shè)計方法的根本組成部分，也是優(yōu)化方法的根底。 為什么要研討無約束優(yōu)化問題為什么要研討無約束優(yōu)化問題? 1有些實踐問題，其數(shù)學(xué)模型本身就是一個無約束有些實踐問題，其數(shù)學(xué)模型本身就是一個無約束優(yōu)化問題。優(yōu)化問題。 2經(jīng)過熟習(xí)它的解法可以為研討約束優(yōu)化問題打下經(jīng)過熟習(xí)它的解法可以為研討約束優(yōu)化問題打下良好的根底。良好的根底。 3約束優(yōu)化問題的求解可以經(jīng)過一系列無約束優(yōu)化約束優(yōu)化問

2、題的求解可以經(jīng)過一系列無約束優(yōu)化方法來到達。所以無約束優(yōu)化問題的解法是優(yōu)化設(shè)計方法來到達。所以無約束優(yōu)化問題的解法是優(yōu)化設(shè)計方法的根本組成部分，也是優(yōu)化方法的根底。方法的根本組成部分，也是優(yōu)化方法的根底。 4對于多維無約束問題來說，古典極值實際中令對于多維無約束問題來說，古典極值實際中令一階導(dǎo)數(shù)為零，但要求二階可微，且要判別海賽矩一階導(dǎo)數(shù)為零，但要求二階可微，且要判別海賽矩陣為正定才干求得極小點，這種方法有實際意義，陣為正定才干求得極小點，這種方法有實際意義，但無適用價值。和一維問題一樣，假設(shè)多元函數(shù)但無適用價值。和一維問題一樣，假設(shè)多元函數(shù)f(x)不可微，亦無法求解。但古典極值實際是無約束優(yōu)

3、不可微，亦無法求解。但古典極值實際是無約束優(yōu)化方法開展的根底?；椒ㄩ_展的根底。 目前已研討出很多種無約束優(yōu)化方法，它們的目前已研討出很多種無約束優(yōu)化方法，它們的主要不同點在于構(gòu)造搜索方向上的差別。主要不同點在于構(gòu)造搜索方向上的差別。 min( )nfRxx無約束優(yōu)化問題是：無約束優(yōu)化問題是：12Tnx xxx求求n n維設(shè)計變量維設(shè)計變量( )minfx使目的函數(shù)使目的函數(shù) 解析法數(shù)值法數(shù)學(xué)模型復(fù)雜時不便求解可以處置復(fù)雜函數(shù)及沒有數(shù)學(xué)表達式的優(yōu)化設(shè)計問題1kkkkxxa d搜索方向問題是無約束優(yōu)化方法的關(guān)鍵。各種無約束優(yōu)化方法的區(qū)別：確定搜索方向的方法不同。無約束優(yōu)化方法分類利用目的函數(shù)的一

4、階或二階導(dǎo)數(shù)利用目的函數(shù)值最速下降法、共軛梯度法、牛頓法坐標輪換法、鮑威爾等1(0,1,2,)kkkkskxx搜索方向的構(gòu)成問題乃是無約束優(yōu)化方法的關(guān)鍵。搜索方向的構(gòu)成問題乃是無約束優(yōu)化方法的關(guān)鍵。 用直接法尋覓極小點時，不用求函數(shù)的導(dǎo)數(shù)，只需計用直接法尋覓極小點時，不用求函數(shù)的導(dǎo)數(shù)，只需計算目的函數(shù)值。這類方法較適用于處理變量個數(shù)較少的算目的函數(shù)值。這類方法較適用于處理變量個數(shù)較少的n 20問題，普通情況下比間接法效率低。間接法除問題，普通情況下比間接法效率低。間接法除要計算目的函數(shù)值外，還要計算目的函數(shù)的梯度，有的要計算目的函數(shù)值外，還要計算目的函數(shù)的梯度，有的還要計算其海賽矩陣。還要計算

5、其海賽矩陣。 第二節(jié) 最速下降法優(yōu)化設(shè)計追求目的函數(shù)值最小，假設(shè)搜索方向取該點的負梯度方向，使函數(shù)值在該點附近的范圍內(nèi)下降最快。按此規(guī)律不斷走步，構(gòu)成以下迭代算法：1kkkkxxaf x以負梯度方向為搜索方向，所以稱最速下降法或梯度法。搜索方向確定為負梯度方向，還需確定步長因子ka即求一維搜索的最正確步長，既有 1minminkkkkkkkfxfxafxfxafx 0Tkkkkfxafxfx 10Tkkf xf x10Tkkdd由此可知，在最速下降法中，相鄰兩個迭代點上的函數(shù)梯度相互垂直。而搜索方向就是負梯度方向，因此相鄰兩個搜索方向相互垂直。 在最速下降法中，在最速下降法中，相鄰兩個迭代點上

6、的函相鄰兩個迭代點上的函數(shù)梯度相互垂直。而搜數(shù)梯度相互垂直。而搜索方向就是負梯度方向，索方向就是負梯度方向，因此相鄰兩個搜索方向因此相鄰兩個搜索方向相互垂直。這就是說在相互垂直。這就是說在迭代點向函數(shù)極小點接迭代點向函數(shù)極小點接近的過程，走的是曲折近的過程，走的是曲折的道路。構(gòu)成的道路。構(gòu)成“之字之字形的鋸齒景象，而且越形的鋸齒景象，而且越接近極小點鋸齒越細。接近極小點鋸齒越細。 圖圖4-2 最速下降法的搜索途徑最速下降法的搜索途徑方法特點方法特點1 1初始點可任選，每次迭代計算量小，初始點可任選，每次迭代計算量小，存儲量少，程序簡短。即使從一個不好的存儲量少，程序簡短。即使從一個不好的初始點

7、出發(fā)，開場的幾步迭代，目的函數(shù)初始點出發(fā)，開場的幾步迭代，目的函數(shù)值下降很快，然后漸漸逼近部分極小點。值下降很快，然后漸漸逼近部分極小點。2 2恣意相鄰兩點的搜索方向是正交的，恣意相鄰兩點的搜索方向是正交的，它的迭代途徑為繞道逼近極小點。當?shù)牡緩綖槔@道逼近極小點。當?shù)c接近極小點時，步長變得很小，越走越點接近極小點時，步長變得很小，越走越慢。慢。 00102()10424()50100 xfxfxxx沿負梯度方向進展一維搜索，有沿負梯度方向進展一維搜索，有01000024()2 100fxxx0為一維搜索最正確步長，應(yīng)滿足極值必要條為一維搜索最正確步長，應(yīng)滿足極值必要條件件 122

8、()min (24 )25(2 100 )min ( )f x例例4 41 1 求目的函數(shù)求目的函數(shù) 的極小點。的極小點。解解 取初始點取初始點那么初始點處函數(shù)值及梯度分別為那么初始點處函數(shù)值及梯度分別為02,2Tx2212( )25fxxx00( )8(24)5 000(2 100)0 算出一維搜索最正確步長算出一維搜索最正確步長 06260.020 030 7231 252第一次迭代設(shè)計點位置和函數(shù)值第一次迭代設(shè)計點位置和函數(shù)值 0120241.919 8772 1000.307178 5 10 x1()3.686164fx繼續(xù)作下去，經(jīng)繼續(xù)作下去，經(jīng)1010次迭代后，得到最優(yōu)解次迭代后，

9、得到最優(yōu)解 00Tx()0fx 這個問題的目的函數(shù)的等值線為一簇橢圓這個問題的目的函數(shù)的等值線為一簇橢圓, ,迭代點從迭代點從 走的是一段鋸齒形道路，見圖走的是一段鋸齒形道路，見圖4-34-3。0 x1 1圖圖4-3將上例中目的函數(shù)將上例中目的函數(shù) 引入變換引入變換2212( )25fxxx221212(,)y yyy其等值線由橢圓變成一簇同心圓。其等值線由橢圓變成一簇同心圓。 仍從仍從 即即 出發(fā)進展最速下降法尋優(yōu)。出發(fā)進展最速下降法尋優(yōu)。此時：此時：02,2Tx02,10Ty00102()10424()220yyyyy沿負梯度方向進展一維搜索：沿負梯度方向進展一維搜索：那么函數(shù)那么函數(shù)f(

10、X)f(X)變?yōu)椋鹤優(yōu)椋簓1=x1, y2=5x21000000()242410201020yyy為一維搜索最正確步長，可由極值條件：為一維搜索最正確步長，可由極值條件：10022()min ()min( )( )(24 )(1020 ) yyy0()0由由0260.552從而算得一步計算后設(shè)計點的位置及其目的函數(shù)：從而算得一步計算后設(shè)計點的位置及其目的函數(shù)：010124010200()0 yy經(jīng)變換后，只需一次迭代，就可找到最優(yōu)解。經(jīng)變換后，只需一次迭代，就可找到最優(yōu)解。這是由于經(jīng)過尺度變換：這是由于經(jīng)過尺度變換：11225yxyx等值線由橢圓變成圓。等值線由橢圓變成圓。梯度法的特點梯度法的

11、特點 1實際明確，程序簡單，對初始點要求不嚴厲。實際明確，程序簡單，對初始點要求不嚴厲。 2對普通函數(shù)而言，梯度法的收斂速度并不快，由對普通函數(shù)而言，梯度法的收斂速度并不快，由于最速下降方向僅僅是指某點的一個部分性質(zhì)。于最速下降方向僅僅是指某點的一個部分性質(zhì)。 3梯度法相鄰兩次搜索方向的正交性，決議了迭代梯度法相鄰兩次搜索方向的正交性，決議了迭代全過程的搜索道路呈鋸齒狀，在遠離極小點時逼近速度全過程的搜索道路呈鋸齒狀，在遠離極小點時逼近速度較快，而在接近極小點時逼近速度較慢。較快，而在接近極小點時逼近速度較慢。 4梯度法的收斂速度與目的函數(shù)的性質(zhì)親密相關(guān)。梯度法的收斂速度與目的函數(shù)的性質(zhì)親密相

12、關(guān)。對于等值線對于等值線(面面)為同心圓球的目的函數(shù)，一次搜索為同心圓球的目的函數(shù)，一次搜索即可到達極小點。即可到達極小點。第三節(jié) 牛頓型方法在第三章中，我們曾經(jīng)討論了一維搜索的牛頓方法。得出一維情況下的牛頓迭代公式1kkkkfxxxfx對于多元函數(shù)，在kx泰勒展開，得 f xx 212TTkkkkkkf xf xxxxxf xxx設(shè)1kx為函數(shù)的極小點，根據(jù)極值的必要條件10kx210kkkkf xf xxx112kkkkxxf xf x 這是多元函數(shù)求極值的牛頓法迭代公式。121()()(0,1,2,)kkkkffk xxxx 對于二次函數(shù)對于二次函數(shù) ，海賽矩陣，海賽矩陣H H是一個常矩

13、陣，其是一個常矩陣，其中各元素均為常數(shù)。因此，無論從任何點出發(fā)，中各元素均為常數(shù)。因此，無論從任何點出發(fā)，只需一步就可找到極小點。只需一步就可找到極小點。 例例4 42 2 求目的函數(shù)求目的函數(shù) 的極小點。的極小點。解解 取初始點取初始點2212( )25fxxx02,2Tx102010102402()()121000050ff xxxx00 x()0fx 從牛頓法迭代公式的推演中可以看到，迭代點的位置是從牛頓法迭代公式的推演中可以看到，迭代點的位置是按照極值條件確定的，其中并未含有沿下降方向搜索的概按照極值條件確定的，其中并未含有沿下降方向搜索的概念。因此對于非二次函數(shù)，假設(shè)采用上述牛頓迭代

14、公式，念。因此對于非二次函數(shù)，假設(shè)采用上述牛頓迭代公式，有時會使函數(shù)值上升有時會使函數(shù)值上升 。阻尼牛頓法阻尼牛頓法 121()()(0,1,2,)kkkkkkkksffkxxxxxk阻尼因子阻尼因子 ，沿牛頓方向進展一維搜索的最，沿牛頓方向進展一維搜索的最正確步長，由下式求得：正確步長，由下式求得： 1()()min()kkkkkkkffsfsxxx經(jīng)過一次迭代即求得極小點經(jīng)過一次迭代即求得極小點函數(shù)極小值函數(shù)極小值開始給定結(jié)束0,x21()()kkkff dxx1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k 阻尼牛頓法程序框圖方法特點方法特點 1 初始點應(yīng)選在初

15、始點應(yīng)選在X*附近，有一定難度；附近，有一定難度； 2 雖然每次迭代都不會是函數(shù)值上升，但不雖然每次迭代都不會是函數(shù)值上升，但不能保證每次下降能保證每次下降 ； 3 假設(shè)迭代點的海賽矩陣為奇特，那么無法假設(shè)迭代點的海賽矩陣為奇特，那么無法求逆矩陣，不能構(gòu)造牛頓法方向；求逆矩陣，不能構(gòu)造牛頓法方向； 4 不僅要計算梯度，還要求海賽矩陣及其逆不僅要計算梯度，還要求海賽矩陣及其逆矩陣，計算量和存儲量大。此外，對于二階不矩陣，計算量和存儲量大。此外，對于二階不可微的可微的F(X)也不適用。也不適用。 雖然阻尼牛頓法有上述缺陷，但在特定條雖然阻尼牛頓法有上述缺陷，但在特定條件下它具有收斂最快的優(yōu)點，并為

16、其他的算法件下它具有收斂最快的優(yōu)點，并為其他的算法提供了思緒和實際根據(jù)。提供了思緒和實際根據(jù)。1(0,1,2,)kkkkskxx1() (0,1,2,)kkkkafkxxx121()()(0,1,2,)kkkkffk xxxx121()()(0,1,2,)kkkkkffkxxxx普通迭代式：普通迭代式：梯度法：梯度法：牛頓法：牛頓法：阻尼牛頓法：阻尼牛頓法：梯度法與牛頓法：梯度法與牛頓法：1()kkkkkfxxAx第四節(jié) 共軛方向及共軛方向法為了抑制最速下降法的鋸齒景象，提高收斂速度，開展了一類共軛方向法。搜索方向是共軛方向。一、共軛方向的概念 12TTf xx Gxb xc共軛方向的概念是在

17、研討二次函數(shù)時引出的。首先思索二維情況假設(shè)按最速下降法，選擇負梯度方向為搜索方向，會產(chǎn)生鋸齒景象。為防止鋸齒的發(fā)生，取下一次的迭代搜索方向直接指向極小點，假設(shè)選定這樣的搜索方向，對于二元二次函數(shù)只需進展兩次直線搜索就可以求到極小點。1000 xxa d*111xxa d 1100Txff xdd 1d應(yīng)滿足什么條件？對于二次函數(shù) 在 處獲得極小點的必要條件 f x*x*0f xGxb*111111f xG xa dbGxbaGd 1110f xaGd 等式兩邊同乘 得0Td010TdGd 0d1d是對G的共軛方向。01()0TdGd 就是使就是使d1d1直指極小點直指極小點x x* * ， d

18、1 d1所必需滿足的條件所必需滿足的條件 。兩個向量兩個向量d0d0和和d1d1稱為稱為G G的共軛向量，或稱的共軛向量，或稱d0d0和和d1d1對對G G是共軛方向。是共軛方向。 二二. .共軛方向的性質(zhì)共軛方向的性質(zhì)性質(zhì)性質(zhì)1 1 假設(shè)非零向量系假設(shè)非零向量系d0,d1,d2,dm-1d0,d1,d2,dm-1是對是對G G共共軛，那么這軛，那么這m m個向量是線性無關(guān)的。個向量是線性無關(guān)的。性質(zhì)性質(zhì)2 2 在在n n維空間中相互共軛的非零向量的個數(shù)維空間中相互共軛的非零向量的個數(shù)不超越不超越n n。 性質(zhì)性質(zhì)3 3 從恣意初始點出發(fā)，依次沿從恣意初始點出發(fā)，依次沿n n個個G G的共軛方

19、的共軛方向向d0,d1, d2,d0,d1, d2,進展一維搜索，最多經(jīng)過進展一維搜索，最多經(jīng)過n n次迭代次迭代就可以找到的二次函數(shù)就可以找到的二次函數(shù)f(x)f(x)極小點。極小點。 021()( )0Tfdx d三、共軛方向法1、選定初始點 ，下降方向 和收斂精度，k=0。0 x0d2、沿 方向進展一維搜索，得kd1kkkkxxa d3、判別 能否滿足，假設(shè)滿足那么打印1kf x1kx否那么轉(zhuǎn)4。4、提供新的共軛方向 ，使 1kd10TjkdGd5、置 ，轉(zhuǎn)2。1kk第五節(jié) 共軛梯度法共軛梯度法是共軛方向法的一種，共軛向量有迭代點的負梯度構(gòu)造出來，所以稱共軛梯度法。 12TTf xx G

20、xb xc1kkkkxxa d1kkkkxxa dkkgGxb從點 出發(fā)，沿G某一共軛方向 作一維搜索,到達kxkd1kx11kkgGxb而在點 、 處的梯度分別為：kx1kx11kkkkkkggG xxa Gd10TjkdGd0TjkdGd 10TjkkdG gg得出共軛方向與梯度之間的關(guān)系。此式闡明沿方向kd進展一維搜索，其終點 與始點 的梯度值差1kxkx1kkgg與 的共軛方向 正交。kdjd3.3.共軛梯度法共軛梯度法 共軛梯度法是共軛方向法中的一種，該方法中共軛梯度法是共軛方向法中的一種，該方法中每一個共軛向量都是依賴于迭代點處的負梯度每一個共軛向量都是依賴于迭代點處的負梯度而構(gòu)造

21、出來。而構(gòu)造出來。 從從xkxk出發(fā)，沿負梯度方向作一維搜索出發(fā)，沿負梯度方向作一維搜索: :1(0,1,2,)kkkkkxxd()kkf dx設(shè)與設(shè)與dk共軛的下一個方向共軛的下一個方向dk+1由由dk和點和點xk+1的的負梯度的線形組合構(gòu)成，即：負梯度的線形組合構(gòu)成，即：11()kkkkf dxd21()( )0kTkfdx d共軛條件：共軛條件： 那么：那么：21()( )()0kTkkkfff xxxd解得：解得：212()()()()()()kTkkkkTkkffffffxxxxxx令令1( )2TfTxx Gxb xc為函數(shù)的泰勒二次展開式為函數(shù)的泰勒二次展開式()kkfxGxb那

22、那么么11()kkfxGxb上兩式相減，并代入上兩式相減，并代入1kkkkxxd1()()kkkkffGdxx1()()kkkkffGdxx將式將式11()kkkkf dxd與式與式兩邊相乘，并運用共軛條件兩邊相乘，并運用共軛條件得：得：11()()()()0kkkkkffff xxxx21112()()()()()()kkTkkkTkkffffffxxxxxx因此因此11()kkkkf dxd212()()kkkffxx1(0,1,2,)kkkkkxxd2212112( )242fxxxx xx，知初始點，知初始點1,1T1,1Tl解：解： 1第一次沿負梯度方向搜索第一次沿負梯度方向搜索l計

23、算初始點處的梯度計算初始點處的梯度0120212244()422xxfxxxx010000014141212 xxd為一維搜索最正確步長，應(yīng)滿足為一維搜索最正確步長，應(yīng)滿足1002()min()min(40203)ffxxdl迭代精度迭代精度 。 0.001得得:00.25120.5x2第二次迭代：第二次迭代：21200()50.2520()ffxx11()2fx11002()1.5f dxd21122220.51.50.5 1.5xxd代入目的函數(shù)代入目的函數(shù)22( )(22 )2(0.5 1.5 )2(22 )(0.5 1.5 )4(22 )( )f x 得得1因因2()0fx收斂。收斂。

24、( )0 由由22240,()8,()20ff xxx從而有：從而有：圖4-9 共軛梯度法的幾何闡明第六節(jié) 變尺度法(DFP法)1kkkkxxHf x變尺度法的根本思想：前面討論的梯度法和牛頓法，它們的迭代公式可以看作以下公式的特例。變尺度法是對牛頓法的修正，它不是計算二階導(dǎo)數(shù)的矩陣和它的逆矩陣，而是設(shè)法構(gòu)造一個對稱正定矩陣H來替代Hesse矩陣的逆矩陣。并在迭代過程中，使其逐漸逼近H-1 。由于對稱矩陣H在迭代過程中是不斷修正改動的，它對于一般尺度的梯度起到改動尺度的作用，因此H又稱變尺度矩陣。 DFP變尺度法首先有戴維頓變尺度法首先有戴維頓Davidon與與1959年提出，又于年提出，又于

25、1963年由弗萊徹年由弗萊徹Fletcher和鮑維爾加和鮑維爾加以開展和完善，成為現(xiàn)代公認的較好的算法之一。以開展和完善，成為現(xiàn)代公認的較好的算法之一。 DFP法是基于牛頓法的思想又作了重要改良。這法是基于牛頓法的思想又作了重要改良。這種算法僅用到梯度，不用計算海賽陣及其逆矩陣，但種算法僅用到梯度，不用計算海賽陣及其逆矩陣，但又能使搜索方向逐漸逼近牛頓方向，具有較快的收斂又能使搜索方向逐漸逼近牛頓方向，具有較快的收斂速度。速度。 根本思想根本思想 變量的尺度變換是放大或減少各個坐標。經(jīng)過變量的尺度變換是放大或減少各個坐標。經(jīng)過尺尺度變換可以把函數(shù)的偏心程度降到最低限制。度變換可以把函數(shù)的偏心程

26、度降到最低限制。 例如在用最速下降法求例如在用最速下降法求 的極小的極小2212( )25fxxx值時值時 ,需求進展需求進展10次迭代才干到達極小點次迭代才干到達極小點0,0Tx 如作變換如作變換 y1=x1, y2=5x2把把 的尺度放大的尺度放大5倍，那么目的函數(shù)等值線由一倍，那么目的函數(shù)等值線由一簇橢圓變成一簇同心圓。簇橢圓變成一簇同心圓。x2221212(,)y yyy 消除了函數(shù)的偏心，用最速下降法只需一次迭消除了函數(shù)的偏心，用最速下降法只需一次迭代即可求得極小點。代即可求得極小點。 梯度法構(gòu)造簡單，只用到一階偏導(dǎo)數(shù)，計算量小，梯度法構(gòu)造簡單，只用到一階偏導(dǎo)數(shù)，計算量小，初始點可任

27、選，且開場幾次迭代，目的函數(shù)值下降很初始點可任選，且開場幾次迭代，目的函數(shù)值下降很快；其主要缺陷是迭代點接近快；其主要缺陷是迭代點接近X*時，即使對二次正時，即使對二次正定函數(shù)收斂也非常慢。定函數(shù)收斂也非常慢。 牛頓法收斂很快，對于二次函數(shù)只需迭代一次便牛頓法收斂很快，對于二次函數(shù)只需迭代一次便到達最優(yōu)點，對非二次函數(shù)也能較快迭代到最優(yōu)點，到達最優(yōu)點，對非二次函數(shù)也能較快迭代到最優(yōu)點，但要計算二階偏導(dǎo)數(shù)矩陣及其逆陣，對維數(shù)較高的優(yōu)但要計算二階偏導(dǎo)數(shù)矩陣及其逆陣，對維數(shù)較高的優(yōu)化問題，其計算任務(wù)和存儲量都太大?；瘑栴}，其計算任務(wù)和存儲量都太大。能不能將兩種算法的優(yōu)點綜合起來，揚長避短？能不能將兩

28、種算法的優(yōu)點綜合起來，揚長避短？1()kkkkkfxxAxAk 是需求構(gòu)造是需求構(gòu)造nn的一個對稱方陣的一個對稱方陣 ，如如Ak=I, 那么得到梯度法那么得到梯度法 ；21()kkf Ax 那么得到阻尼牛頓法那么得到阻尼牛頓法 ；如如當矩陣當矩陣Ak Ak 不斷地迭代而能很好地逼近不斷地迭代而能很好地逼近 21()kfx時，就可以不再需求計算二階導(dǎo)數(shù)。時，就可以不再需求計算二階導(dǎo)數(shù)。 變尺度法的關(guān)鍵在于尺度矩陣變尺度法的關(guān)鍵在于尺度矩陣AkAk的產(chǎn)生的產(chǎn)生 。對于二次函數(shù)對于二次函數(shù):1( )2TTfxx Gxb xcxQx進展尺度變換進展尺度變換在新的坐標系中，函數(shù)在新的坐標系中，函數(shù)f(x

29、)的二次項變?yōu)椋旱亩雾椬優(yōu)椋?122TTTx Gxx Q GQx目的：減少二次項的偏心目的：減少二次項的偏心如如G是正定，那么總存在矩陣是正定，那么總存在矩陣Q，使得：，使得：TQ GQI 用矩陣用矩陣Q-1右乘等式兩邊，得：右乘等式兩邊，得：用矩陣用矩陣Q左乘等式兩邊，得：左乘等式兩邊，得：1TQ GQTQQ GI所以所以1TQQG上式闡明：二次函數(shù)矩陣上式闡明：二次函數(shù)矩陣G的逆陣，可以經(jīng)過尺度變換的逆陣，可以經(jīng)過尺度變換矩陣矩陣Q來求得。來求得。121()()(0,1,2,)kkkkkffkxxxx牛頓迭代公式：牛頓迭代公式：1()(0,1,2,)kkTkkQQfkxxx記：記：TAQ

30、Q搜索方向：搜索方向：1()(0,1,2,)kkksfk Ax迭代公式：迭代公式：1()(0,1,2,)kkkkkfkxxAxA A 稱為變尺度矩陣稱為變尺度矩陣2212( )25fxxx在例在例42中中122121222011( )2505022Txfxxx xxxx Gx20050G如取如取102105 2Q11002010221050101005 25 2TQ GQI求得：求得：1111000222111000505 25 2TGQQ三、變尺度法的普通步驟三、變尺度法的普通步驟DFP算法DFP算法DFP算法例題例題 4-5 第七節(jié) 坐標輪換法坐標輪換法是每次搜索只允許一個變量變化，其他變

31、量堅持不變，即沿坐標方向輪番進展搜索的尋優(yōu)方法。它把多變量的優(yōu)化問題輪番地轉(zhuǎn)化成單變量的優(yōu)化問題。因此又稱變量輪換法。 其根本原理是將一個多維的無約束最優(yōu)化問題轉(zhuǎn)化為一系列較低維的最優(yōu)化問題來求解，簡單地說，就是先將(n-1)個變量固定不動，只對第一個變量進展一維搜索得到最優(yōu)點x11。然后，又堅持(n-1)個變量不變，再對第二個變量進展一維搜索到x21等等。 圖412 坐標輪換法原理圖)0(2)0(1XX)0(2)1(1XX)1(2)1(1XX)2(2)2(1XX2. 搜索方向與步長確實定對于第k輪第i次的計算1kkkkiiiixxa d第k輪第I次的迭代方向，它輪番取n維坐標的單位向量。0.

32、1.0kiide 3.搜索步長確實定關(guān)于 值通常有以下幾種取法1加速步長法2最優(yōu)步長法 最優(yōu)步長法就是利用一維最優(yōu)搜索方法來完成每一次迭代，此時可以采用0.618方法或二次插值方法來計算。)( ki圖413 加速步長法的搜索道路圖414 最優(yōu)步長法的搜索道路4 . 坐標輪換法存在的問題圖415 坐標輪換法在各種不同情況下的效能a搜索有效；b搜索低效；c搜索無效第八節(jié) Powell法方向加速法 Powell法是利用共軛方向可以加速收斂的性質(zhì)所構(gòu)成的一種搜索算法。一、共軛方向的生成二、根本算法三、改良的算法在鮑維爾根本算法中，每一輪迭代都用連結(jié)始點和終點所產(chǎn)生出的搜索方向去交換原來向量組中的第一個

33、向量，而不論它的“好壞。改良的算法是：首先判別原向量組能否需求交換。如需求交換，在產(chǎn)生新的向量。第八節(jié) Powell法方向加速法 鮑威爾法是以共軛方向為根底的收斂較鮑威爾法是以共軛方向為根底的收斂較快的直接法之一，是一種非常有效的算法?？斓闹苯臃ㄖ?，是一種非常有效的算法。 1964年，鮑維爾提出這種算法，其根本思想年，鮑維爾提出這種算法，其根本思想是直接利用迭代點的目的函數(shù)值來構(gòu)造共是直接利用迭代點的目的函數(shù)值來構(gòu)造共軛方向，然后從任一初始點開場，逐次沿軛方向，然后從任一初始點開場，逐次沿共軛方向作一維搜索求極小點。并在以后共軛方向作一維搜索求極小點。并在以后的實際中進展了改良。的實際中進展

34、了改良。 1()2TfTxx G xbxc對函數(shù)：對函數(shù)：根本思想：在不用導(dǎo)數(shù)的前提下，在迭代中逐次構(gòu)造根本思想：在不用導(dǎo)數(shù)的前提下，在迭代中逐次構(gòu)造G G的共軛方向。的共軛方向。 1.1.共軛方向的生成共軛方向的生成jjkkkdd ddjgg gk+1xxk+1設(shè)設(shè)xk, xk+1xk, xk+1為從不同為從不同點出發(fā)，沿同一方向點出發(fā)，沿同一方向djdj進展一維搜索而到進展一維搜索而到的兩個極小點。的兩個極小點。 梯度和等值面相垂直的性質(zhì)梯度和等值面相垂直的性質(zhì), dj, dj和和 xk, xk+1 xk, xk+1兩點處的梯度兩點處的梯度gk,gk+1gk,gk+1之間存在關(guān)系之間存在關(guān)

35、系: :1()0,()0jTkjTkdgdg另一方面，對于上述二次函數(shù)，其另一方面，對于上述二次函數(shù)，其xk, xk+1xk, xk+1兩點處兩點處的梯度可表示為的梯度可表示為: :11,kkkkgGxbgGxb因此有因此有11() ()()()0jTkkjTkkdggdG xx1kkkdxx取取這闡明只需沿這闡明只需沿djdj方向分別對函作兩次一維搜索，方向分別對函作兩次一維搜索，得到兩個極小點得到兩個極小點xkxk和和xk+1 xk+1 ，那么這兩點的連線，那么這兩點的連線所給出的方向所給出的方向dkdk就是與就是與djdj一同對一同對G G共軛的方向。共軛的方向。2.2.根本算法根本算法

36、 二維情況描畫鮑威爾的根本算法二維情況描畫鮑威爾的根本算法: : 1 1任選一初始點任選一初始點x0 x0，再選兩個線性無關(guān)的再選兩個線性無關(guān)的向量，如坐標軸單位向量，如坐標軸單位向量向量e1=1,0Te1=1,0T和和e2=0,1Te2=0,1T作為初始作為初始搜索方向。搜索方向。2 2從從x0 x0出發(fā)，依次沿出發(fā)，依次沿e1e1， e1e1作一維搜索，作一維搜索，得得 點，兩點連線點，兩點連線得一新方向得一新方向d1d10012,x x1002dxxx1x2x0oe1e2d1d2x*102x10 x11x12x01xx1x2x0o oe1e2d1d2x*102x10 x11x12x01x

37、21120dxx沿沿d2d2作一維搜索得點作一維搜索得點x2 x2 。 即是二維問題的極即是二維問題的極小點小點x x* * 。方法的根本迭代格式包括共軛方向產(chǎn)生和方向交換兩方法的根本迭代格式包括共軛方向產(chǎn)生和方向交換兩主要步驟。主要步驟。用用 d1d1替代替代e1e1構(gòu)成兩個線性無關(guān)向量構(gòu)成兩個線性無關(guān)向量d1 ,e2 d1 ,e2 ，作，作為下一輪迭代的搜索方向。再為下一輪迭代的搜索方向。再 從出發(fā)，沿從出發(fā)，沿d1d1作一維搜索得點作一維搜索得點 ，作為下一輪迭代的初始點。，作為下一輪迭代的初始點。 02x10 x3 3從出發(fā)從出發(fā) ，依次，依次沿沿e2,d1 e2,d1 作一維搜索，作

38、一維搜索，得到點得到點 ，兩點連，兩點連線得一新方向線得一新方向: :1112,xx10 x 把二維情況的根本算法擴展到把二維情況的根本算法擴展到n n維，那么鮑威維，那么鮑威爾根本算法的要點是：爾根本算法的要點是： 在每一輪迭代中總有一個始點第一輪的始點在每一輪迭代中總有一個始點第一輪的始點是任選的初始點和是任選的初始點和n n個線性獨立的搜索方向。從個線性獨立的搜索方向。從始點出發(fā)依次沿始點出發(fā)依次沿n n個方向作一維搜索得一終點，由個方向作一維搜索得一終點，由始點和終點決議了一個新的搜索方向。始點和終點決議了一個新的搜索方向。 用這個方向交換原來用這個方向交換原來n n個方向中的一個，于

39、是個方向中的一個，于是構(gòu)成新的搜索方向組。交換的原那么是去掉原方構(gòu)成新的搜索方向組。交換的原那么是去掉原方向組的第一個方向而將新方向排在原方向的最后。向組的第一個方向而將新方向排在原方向的最后。此外規(guī)定，從這一輪的搜索終點出發(fā)沿新的搜索此外規(guī)定，從這一輪的搜索終點出發(fā)沿新的搜索方向作一維搜索而得到的極小點，作為下一輪迭方向作一維搜索而得到的極小點，作為下一輪迭代的始點。這樣就構(gòu)成算法的循環(huán)。代的始點。這樣就構(gòu)成算法的循環(huán)。 2x3x1xo0X1e2e3e3 3假設(shè)目的函數(shù)為正定二次函數(shù)，假設(shè)目的函數(shù)為正定二次函數(shù)，n n輪終了后即可到輪終了后即可到達最優(yōu)點。達最優(yōu)點。2 2每輪迭代產(chǎn)生一個新方

40、向取代原來的第一方向，每輪迭代產(chǎn)生一個新方向取代原來的第一方向，n n輪迭代后可產(chǎn)生輪迭代后可產(chǎn)生n n個彼此共軛的方向；個彼此共軛的方向；nX1 1開場采用坐標軸方向；開場采用坐標軸方向；PowellPowell根本算法根本算法 上述根本算法僅具有實際意義 。 由于在迭代中的由于在迭代中的n n個搜索方向有時會變個搜索方向有時會變成線性相關(guān)而不能構(gòu)成共軛方向。這時組不成線性相關(guān)而不能構(gòu)成共軛方向。這時組不成成n n維空間，能夠求不到極小點，所以上述維空間，能夠求不到極小點，所以上述根本算法有待改良。根本算法有待改良。 3.3.改良的算法改良的算法 在鮑威爾根本算法中，每一輪迭代都用連結(jié)始點和

41、終在鮑威爾根本算法中，每一輪迭代都用連結(jié)始點和終點所產(chǎn)生出的搜索方向去交換原向量組中的第一個向量，點所產(chǎn)生出的搜索方向去交換原向量組中的第一個向量，而不論它的而不論它的“好壞，這是產(chǎn)生向量組線性相關(guān)的緣由所在。好壞，這是產(chǎn)生向量組線性相關(guān)的緣由所在。 在改良的算法中首先判別原向量組能否需求交換。假在改良的算法中首先判別原向量組能否需求交換。假設(shè)需求交換，還要進一步判別原向量組中哪個向量最壞，設(shè)需求交換，還要進一步判別原向量組中哪個向量最壞，然后再用新產(chǎn)生的向量交換這個最壞的向量，以保證逐次然后再用新產(chǎn)生的向量交換這個最壞的向量，以保證逐次生成共軛方向。生成共軛方向。 為此，要處理兩個關(guān)鍵問題：

42、為此，要處理兩個關(guān)鍵問題： 1dk1能否較好？能否應(yīng)該進入新的方向能否較好？能否應(yīng)該進入新的方向組？即方向組能否進展更新？組？即方向組能否進展更新？l2假設(shè)應(yīng)該更新方向組，假設(shè)應(yīng)該更新方向組， dk1不一定交換不一定交換方向方向 ，而是有選擇地交換某一方向，而是有選擇地交換某一方向 。1kdkmd令在令在k次循環(huán)中次循環(huán)中00231()()()kknknFfFfFfxxx01,kkknnx x x100()2kkkkkknnnnxxxxxx分別稱為一輪迭代的始點、終點和反射點分別稱為一輪迭代的始點、終點和反射點 。 那么在循環(huán)中函數(shù)下降最多的第那么在循環(huán)中函數(shù)下降最多的第m次迭代是次迭代是1(

43、1,2, )iiiffin ()(0,1,2, )kiiffinx記：記：11maxmimmi nff 相應(yīng)的方向為相應(yīng)的方向為 。kmd為了構(gòu)成共軛性好的方向組，須遵照以下準為了構(gòu)成共軛性好的方向組，須遵照以下準那么：那么：在在k次循環(huán)中，假設(shè)滿足條件：次循環(huán)中，假設(shè)滿足條件：30FF和和202302(2)()mFFFFF2030.5()mFF那么選用新方向那么選用新方向dk，并在第，并在第k+1迭代中用迭代中用dk交換對應(yīng)交換對應(yīng)于于 的方向的方向 。否那么，依然用原方向組進展第。否那么，依然用原方向組進展第k+1迭代。迭代。kmdm002,nFfFf因此因此 這樣反復(fù)迭代的結(jié)果，后面加進

44、去的向這樣反復(fù)迭代的結(jié)果，后面加進去的向量都彼此對量都彼此對G G共軛，經(jīng)共軛，經(jīng)n n輪迭代即可得到一個輪迭代即可得到一個由由n n個共軛方向所組成的方向組。對于二次個共軛方向所組成的方向組。對于二次函次，最多函次，最多n n次就可找到極小點，而對普通次就可找到極小點，而對普通函數(shù)，往往要超越函數(shù)，往往要超越n n次才干找到極小點這次才干找到極小點這里里“n n表示設(shè)計空間的維數(shù)。表示設(shè)計空間的維數(shù)。 例例4-5 4-5 用改良的鮑威爾法求目的函數(shù)用改良的鮑威爾法求目的函數(shù)2212112( )242fxxxx xx解：解：1 1第第1 1輪迭代計算輪迭代計算， 0011 x0000()3Ff

45、f x沿沿e1e1方向進展一維搜索方向進展一維搜索0201min()43fxe12得得00101 11132101 xxe011()7ff x0.001。的最優(yōu)解。知初始點的最優(yōu)解。知初始點1,1T1,1T，迭代精度，迭代精度以以 為起點，沿第二坐標軸方向為起點，沿第二坐標軸方向 e2 進展一維進展一維搜索搜索01x0212min()227fxe20.5得得0021213030.5111.5 xxe022()7.5ff x確定此輪中的最大下降量及其相應(yīng)方向確定此輪中的最大下降量及其相應(yīng)方向 0010101()()4ffff xx0021212()()0.5ffff xx12max,4m 反射點

46、及其函數(shù)值反射點及其函數(shù)值000320315221.512 xxx033()7Ff x檢驗檢驗PowellPowell條件條件202302(2)()1.25mFFFFF2030.5()32mFF3073FF 由于滿足由于滿足PowellPowell條件，那么淘汰函數(shù)值下降量條件，那么淘汰函數(shù)值下降量最大的方向最大的方向e1e1，下一輪的根本方向組為，下一輪的根本方向組為e2e2， 。03d構(gòu)成新的方向構(gòu)成新的方向 0003203121.510.5 dxx沿沿 方向一維搜索得極小點和極小值方向一維搜索得極小點和極小值03d13.81.7x1()7.9f x，此點為下輪迭代初始點。此點為下輪迭代初

47、始點。 按點距準那么檢驗終止條件按點距準那么檢驗終止條件 11220(3.81)(1.71)2.886xx需進展第二輪迭代機算。需進展第二輪迭代機算。 2 2第第2 2輪迭代計算輪迭代計算此 輪 根 本 方 向 組 為此 輪 根 本 方 向 組 為 e 2e 2 ， ， 分 別 相 當， 分 別 相 當于于 ， ，起始點為，起始點為 。03d11d12d10 x1x沿沿e2e2方向進展一維搜索得方向進展一維搜索得 113.81.9x111()7.98ff x以以 為起點沿為起點沿 方向一維搜索得方向一維搜索得11x03d123.961.9x122()7.996ff x確定此輪中函數(shù)值最大下降量

48、及其相應(yīng)方向確定此輪中函數(shù)值最大下降量及其相應(yīng)方向10.08 20.016 12max,0.08m 反射點及其函數(shù)值反射點及其函數(shù)值1113203.963.84.12221.941.72.18xxx133()7.964Ff x檢驗檢驗PowellPowell條件，淘汰函數(shù)值下降量最大的條件，淘汰函數(shù)值下降量最大的方向方向e2e2，下一輪的根本方向組應(yīng)為，下一輪的根本方向組應(yīng)為 ， 。 03d13d構(gòu)成新的方向構(gòu)成新的方向1113203.963.80.161.941.70.24dxx沿沿 方向進展一維搜索得方向進展一維搜索得13d242 x2()8f x 檢驗終止條件檢驗終止條件 22220(4

49、3.8)(21.7)0.36xx3 3第第3 3輪迭代計算輪迭代計算此輪根本方向組為此輪根本方向組為 ， ，起始點為，起始點為 ，先后沿先后沿 ， 方向，進展一維搜索，得方向，進展一維搜索，得03d13d20 x2x03d13d2242 x2142 x，22200 xx*42 x*()8f x故最優(yōu)解故最優(yōu)解檢驗終止條件檢驗終止條件 實踐上，前兩輪迭代的實踐上，前兩輪迭代的 ， 為共軛方為共軛方向，由于本例目的函數(shù)是二次函數(shù)，按共軛方向向，由于本例目的函數(shù)是二次函數(shù)，按共軛方向的二次收斂性，故前兩輪的結(jié)果就是問題的最優(yōu)的二次收斂性，故前兩輪的結(jié)果就是問題的最優(yōu)解，但每一輪迭代都需求進展解，但每

50、一輪迭代都需求進展n+1n+1次迭代。次迭代。 13d23d第九節(jié)第九節(jié) 單純形方法單純形方法根本思想根本思想 單純形交換法也是一種不運用導(dǎo)數(shù)的求解無單純形交換法也是一種不運用導(dǎo)數(shù)的求解無約束極小化問題的直接搜索方法，與前面幾種方約束極小化問題的直接搜索方法，與前面幾種方法不同的是，單純形交換法不是利用搜索方向從法不同的是，單純形交換法不是利用搜索方向從一個點迭代到另一個更優(yōu)的點，而是從一個單純一個點迭代到另一個更優(yōu)的點，而是從一個單純形迭代到另一個更優(yōu)的單純形。形迭代到另一個更優(yōu)的單純形。定義：單純形定義：單純形 n維空間中的恰好有維空間中的恰好有n+1個頂點極點的有界的個頂點極點的有界的凸

51、多面體稱之為一個單純形。凸多面體稱之為一個單純形。 根據(jù)定義，可知，一維空間中的單純形是線段，根據(jù)定義，可知，一維空間中的單純形是線段，二維空間中的單純形是三角形，而三維空間中的單純二維空間中的單純形是三角形，而三維空間中的單純形那么是四面體。形那么是四面體。 在單純形交換算法中，從一個單純形到另一個單在單純形交換算法中，從一個單純形到另一個單純形的迭代主要經(jīng)過反射、擴張、收縮和縮邊這純形的迭代主要經(jīng)過反射、擴張、收縮和縮邊這4個個操作來實現(xiàn)。下面以二維問題為例來對操作來實現(xiàn)。下面以二維問題為例來對4種操作進展種操作進展闡明參見以下圖。闡明參見以下圖。1 1反射反射設(shè)除了最劣點設(shè)除了最劣點X1

52、X1以外的基余頂點的中心為以外的基余頂點的中心為X4X4，作作X1X1關(guān)于點關(guān)于點X4X4的對稱點的對稱點X5X5，稱，稱X5X5為為X1X1的反射點。求反射點的過的反射點。求反射點的過程稱之為反射。程稱之為反射。)()()(321XfXfXf2 2擴張擴張在得到反射點在得到反射點X5X5之后，假設(shè)之后，假設(shè)X5X5優(yōu)于原單純形的最劣優(yōu)于原單純形的最劣點即有點即有 ，闡明反射方向，闡明反射方向X5X1X5X1是有利方是有利方向，反射勝利。假設(shè)進一步有向，反射勝利。假設(shè)進一步有 ，可沿反射方向前，可沿反射方向前進適當?shù)拈g隔到點進適當?shù)拈g隔到點X6X6。X6X6稱之為擴張點，求擴張點的過程稱之為稱之為擴張點，求擴張點的過程稱之為擴張。擴張之后，假設(shè)擴張點擴張。擴張之后，假設(shè)擴張點X6X6優(yōu)于反射點優(yōu)于反射點X5X5，那么擴張勝利，那么擴張勝利，以以X6X6取代取代X1X1，得新單純形，得新單純形X6,X2,X3X6,X2,X3；否那么，擴張失敗，舍棄；否那么，擴張失敗，舍棄擴張點，以反射擴張點，以反射X5X5點取代點取代X1X1，得新單純形，得新單純形X5,X2,X3X5,X2,X3。)()(15XfXf)()(25XfXf設(shè)當前的單純形的頂點為設(shè)當前的單純形的頂點為X1X1，X2X2，X3X3，且有，且有)()()(251XfXfXf假設(shè)出現(xiàn)假設(shè)出現(xiàn) 。表示反射完全失敗，應(yīng)退回到介