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

1、第四章 無約束優(yōu)化方法第一節(jié) 概述 第1章所列舉的機(jī)械優(yōu)化設(shè)計(jì)問題，都是在一定的限制條件下追求某一目的為最小，它們都屬于約束優(yōu)化問題。 約束優(yōu)化問題的求解轉(zhuǎn)化為一系列的無約束優(yōu)化問題實(shí)現(xiàn)的。 因此，無約束優(yōu)化問題的解法是優(yōu)化設(shè)計(jì)方法的根本組成部分，也是優(yōu)化方法的根底。 為什么要研討無約束優(yōu)化問題為什么要研討無約束優(yōu)化問題? 1有些實(shí)踐問題，其數(shù)學(xué)模型本身就是一個(gè)無約束有些實(shí)踐問題，其數(shù)學(xué)模型本身就是一個(gè)無約束優(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)化方法來到達(dá)。所以無約束優(yōu)化問題的解法是優(yōu)化設(shè)計(jì)方法來到達(dá)。所以無約束優(yōu)化問題的解法是優(yōu)化設(shè)計(jì)方法的根本組成部分，也是優(yōu)化方法的根底。方法的根本組成部分，也是優(yōu)化方法的根底。 4對(duì)于多維無約束問題來說，古典極值實(shí)際中令對(duì)于多維無約束問題來說，古典極值實(shí)際中令一階導(dǎo)數(shù)為零，但要求二階可微，且要判別海賽矩一階導(dǎo)數(shù)為零，但要求二階可微，且要判別海賽矩陣為正定才干求得極小點(diǎn)，這種方法有實(shí)際意義，陣為正定才干求得極小點(diǎn)，這種方法有實(shí)際意義，但無適用價(jià)值。和一維問題一樣，假設(shè)多元函數(shù)但無適用價(jià)值。和一維問題一樣，假設(shè)多元函數(shù)f(x)不可微，亦無法求解。但古典極值實(shí)際是無約束優(yōu)

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

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

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

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

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

8、()min (24 )25(2 100 )min ( )f x例例4 41 1 求目的函數(shù)求目的函數(shù) 的極小點(diǎn)。的極小點(diǎn)。解解 取初始點(diǎn)取初始點(diǎn)那么初始點(diǎn)處函數(shù)值及梯度分別為那么初始點(diǎn)處函數(shù)值及梯度分別為02,2Tx2212( )25fxxx00( )8(24)5 000(2 100)0 算出一維搜索最正確步長(zhǎng)算出一維搜索最正確步長(zhǎng) 06260.020 030 7231 252第一次迭代設(shè)計(jì)點(diǎn)位置和函數(shù)值第一次迭代設(shè)計(jì)點(diǎn)位置和函數(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 這個(gè)問題的目的函數(shù)的等值線為一簇橢圓這個(gè)問題的目的函數(shù)的等值線為一簇橢圓, ,迭代點(diǎn)從迭代點(diǎn)從 走的是一段鋸齒形道路，見圖走的是一段鋸齒形道路，見圖4-34-3。0 x1 1圖圖4-3將上例中目的函數(shù)將上例中目的函數(shù) 引入變換引入變換2212( )25fxxx221212(,)y yyy其等值線由橢圓變成一簇同心圓。其等值線由橢圓變成一簇同心圓。 仍從仍從 即即 出發(fā)進(jìn)展最速下降法尋優(yōu)。出發(fā)進(jìn)展最速下降法尋優(yōu)。此時(shí)：此時(shí)：02,2Tx02,10Ty00102()10424()220yyyyy沿負(fù)梯度方向進(jìn)展一維搜索：沿負(fù)梯度方向進(jìn)展一維搜索：那么函數(shù)那么函數(shù)f(

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

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

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

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

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

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

16、其他的算法件下它具有收斂最快的優(yōu)點(diǎn)，并為其他的算法提供了思緒和實(shí)際根據(jù)。提供了思緒和實(shí)際根據(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í)引出的。首先思索二維情況假設(shè)按最速下降法，選擇負(fù)梯度方向?yàn)樗阉鞣较颍瑫?huì)產(chǎn)生鋸齒景象。為防止鋸齒的發(fā)生，取下一次的迭代搜索方向直接指向極小點(diǎn)，假設(shè)選定這樣的搜索方向，對(duì)于二元二次函數(shù)只需進(jìn)展兩次直線搜索就可以求到極小點(diǎn)。1000 xxa d*111xxa d 1100Txff xdd 1d應(yīng)滿足什么條件？對(duì)于二次函數(shù) 在 處獲得極小點(diǎn)的必要條件 f x*x*0f xGxb*111111f xG xa dbGxbaGd 1110f xaGd 等式兩邊同乘 得0Td010TdGd 0d1d是對(duì)G的共軛方向。01()0TdGd 就是使就是使d1d1直指極小點(diǎn)直指極小點(diǎn)x x* * ， d

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

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

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

21、出來。而構(gòu)造出來。 從從xkxk出發(fā)，沿負(fù)梯度方向作一維搜索出發(fā)，沿負(fù)梯度方向作一維搜索: :1(0,1,2,)kkkkkxxd()kkf dx設(shè)與設(shè)與dk共軛的下一個(gè)方向共軛的下一個(gè)方向dk+1由由dk和點(diǎn)和點(diǎn)xk+1的的負(fù)梯度的線形組合構(gòu)成，即：負(fù)梯度的線形組合構(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與式與式兩邊相乘，并運(yùn)用共軛條件兩邊相乘，并運(yùn)用共軛條件得：得：11()()()()0kkkkkffff xxxx21112()()()()()()kkTkkkTkkffffffxxxxxx因此因此11()kkkkf dxd212()()kkkffxx1(0,1,2,)kkkkkxxd2212112( )242fxxxx xx，知初始點(diǎn)，知初始點(diǎn)1,1T1,1Tl解：解： 1第一次沿負(fù)梯度方向搜索第一次沿負(fù)梯度方向搜索l計(jì)

23、算初始點(diǎn)處的梯度計(jì)算初始點(diǎn)處的梯度0120212244()422xxfxxxx010000014141212 xxd為一維搜索最正確步長(zhǎng)，應(yīng)滿足為一維搜索最正確步長(zhǎ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變尺度法的根本思想：前面討論的梯度法和牛頓法，它們的迭代公式可以看作以下公式的特例。變尺度法是對(duì)牛頓法的修正，它不是計(jì)算二階導(dǎo)數(shù)的矩陣和它的逆矩陣，而是設(shè)法構(gòu)造一個(gè)對(duì)稱正定矩陣H來替代Hesse矩陣的逆矩陣。并在迭代過程中，使其逐漸逼近H-1 。由于對(duì)稱矩陣H在迭代過程中是不斷修正改動(dòng)的，它對(duì)于一般尺度的梯度起到改動(dòng)尺度的作用，因此H又稱變尺度矩陣。 DFP變尺度法首先有戴維頓變尺度法首先有戴維頓Davidon與與1959年提出，又于年提出，又于

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

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

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

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

29、)的二次項(xiàng)變?yōu)椋旱亩雾?xiàng)變?yōu)椋?122TTTx Gxx Q GQx目的：減少二次項(xiàng)的偏心目的：減少二次項(xiàng)的偏心如如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é) 坐標(biāo)輪換法坐標(biāo)輪換法是每次搜索只允許一個(gè)變量變化，其他變

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

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

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

34、了改良。 1()2TfTxx G xbxc對(duì)函數(shù)：對(duì)函數(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為從不同為從不同點(diǎn)出發(fā)，沿同一方向點(diǎn)出發(fā)，沿同一方向djdj進(jìn)展一維搜索而到進(jìn)展一維搜索而到的兩個(gè)極小點(diǎn)。的兩個(gè)極小點(diǎn)。 梯度和等值面相垂直的性質(zhì)梯度和等值面相垂直的性質(zhì), dj, dj和和 xk, xk+1 xk, xk+1兩點(diǎn)處的梯度兩點(diǎn)處的梯度gk,gk+1gk,gk+1之間存在關(guān)系之間存在關(guān)

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

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

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

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

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

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

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

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

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

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

45、f x沿沿e1e1方向進(jìn)展一維搜索方向進(jìn)展一維搜索0201min()43fxe12得得00101 11132101 xxe011()7ff x0.001。的最優(yōu)解。知初始點(diǎn)的最優(yōu)解。知初始點(diǎn)1,1T1,1T，迭代精度，迭代精度以以 為起點(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 x確定此輪中的最大下降量及其相應(yīng)方向確定此輪中的最大下降量及其相應(yīng)方向 0010101()()4ffff xx0021212()()0.5ffff xx12max,4m 反射點(diǎn)

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

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

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

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

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

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

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