無(wú)約束條件下多變量函數(shù)尋優(yōu)方法ppt課件

1、5-1 5-1 梯度法梯度法5-2 5-2 牛頓法牛頓法5-3 5-3 坐標(biāo)輪換法坐標(biāo)輪換法5-4 5-4 單純形方法單純形方法 1工程問(wèn)題大都為有約束優(yōu)化問(wèn)題。為什么要研討無(wú)約束優(yōu)化問(wèn)題? 1有些實(shí)踐問(wèn)題，其數(shù)學(xué)模型本身就是一個(gè)無(wú)約束優(yōu)化問(wèn)題。 2經(jīng)過(guò)熟習(xí)它的解法可以為研討約束優(yōu)化問(wèn)題打下良好的根底。 3約束優(yōu)化問(wèn)題的求解可以經(jīng)過(guò)一系列無(wú)約束優(yōu)化方法來(lái)到達(dá)。所以無(wú)約束優(yōu)化問(wèn)題的解法是優(yōu)化設(shè)計(jì)方法的根本組成部分，也是優(yōu)化方法的根底。2 目前已研討出很多種無(wú)約束優(yōu)化方法，它們的主要不同點(diǎn)在于構(gòu)造搜索方向上的差別。 min( )nfRxx1間接法要運(yùn)用導(dǎo)數(shù)，如梯度法、阻尼牛頓法、變尺度法、共軛梯度

2、法等。2直接法不運(yùn)用導(dǎo)數(shù)信息，如坐標(biāo)輪換法、鮑威爾法單純形法等。無(wú)約束優(yōu)化問(wèn)題是：無(wú)約束優(yōu)化問(wèn)題是：12Tnx xxx求求n n維設(shè)計(jì)變量維設(shè)計(jì)變量( )minfx使目的函數(shù)使目的函數(shù) 31(0,1,2,)kkkkskxx搜索方向的構(gòu)成問(wèn)題乃是無(wú)約束優(yōu)化方法的關(guān)鍵。搜索方向的構(gòu)成問(wèn)題乃是無(wú)約束優(yōu)化方法的關(guān)鍵。 用直接法尋覓極小點(diǎn)時(shí)，不用求函數(shù)的導(dǎo)數(shù)，只需計(jì)算目的函數(shù)值。這類方法較適用于處理變量個(gè)數(shù)較少的n 20問(wèn)題，普通情況下比間接法效率低。間接法除要計(jì)算目的函數(shù)值外，還要計(jì)算目的函數(shù)的梯度，有的還要計(jì)算其海賽矩陣。 41(0,1,2,)kkkkskxx1() (0,1,2,)kkkkafkx

3、xx 根本思想：函數(shù)的負(fù)梯度方向是函數(shù)值在該點(diǎn)根本思想：函數(shù)的負(fù)梯度方向是函數(shù)值在該點(diǎn)下降最快的方向。將下降最快的方向。將n n維問(wèn)題轉(zhuǎn)化為一系列沿負(fù)梯度維問(wèn)題轉(zhuǎn)化為一系列沿負(fù)梯度方向用一維搜索方法尋優(yōu)的問(wèn)題，利用負(fù)梯度作為方向用一維搜索方法尋優(yōu)的問(wèn)題，利用負(fù)梯度作為搜索方向，故稱最速下降法或梯度法。搜索方向，故稱最速下降法或梯度法。 ( )fx 搜索方向搜索方向s s取該點(diǎn)的負(fù)梯度方向取該點(diǎn)的負(fù)梯度方向 ( (最速下降方最速下降方向向) ) ，使函數(shù)值在該點(diǎn)附近的范圍內(nèi)下降最快，使函數(shù)值在該點(diǎn)附近的范圍內(nèi)下降最快 。5 為了使目的函數(shù)值沿搜索方向?yàn)榱耸鼓康暮瘮?shù)值沿搜索方向 可以獲可以獲得最大

4、的下降值，其步長(zhǎng)因子得最大的下降值，其步長(zhǎng)因子 應(yīng)取一維搜索的最應(yīng)取一維搜索的最正確步長(zhǎng)。即有正確步長(zhǎng)。即有()kf xk1()()min ()min ( )kkkkkkaaffaffa f xxxxx根據(jù)一元函數(shù)極值的必要條件和多元復(fù)合函數(shù)求導(dǎo)公式，得根據(jù)一元函數(shù)極值的必要條件和多元復(fù)合函數(shù)求導(dǎo)公式，得 ( )()()0Tkkkkfff xxx1()()0kTkffxx1()0kTkss6 在最速下降法中，在最速下降法中，相鄰兩個(gè)迭代點(diǎn)上的函相鄰兩個(gè)迭代點(diǎn)上的函數(shù)梯度相互垂直。而搜數(shù)梯度相互垂直。而搜索方向就是負(fù)梯度方向，索方向就是負(fù)梯度方向，因此相鄰兩個(gè)搜索方向因此相鄰兩個(gè)搜索方向相互垂直

5、。這就是說(shuō)在相互垂直。這就是說(shuō)在迭代點(diǎn)向函數(shù)極小點(diǎn)接迭代點(diǎn)向函數(shù)極小點(diǎn)接近的過(guò)程，走的是曲折近的過(guò)程，走的是曲折的道路。構(gòu)成的道路。構(gòu)成“之字之字形的鋸齒景象，而且越形的鋸齒景象，而且越接近極小點(diǎn)鋸齒越細(xì)。接近極小點(diǎn)鋸齒越細(xì)。 圖圖5-2 5-2 最速下降法的搜索途徑最速下降法的搜索途徑78方法特點(diǎn)方法特點(diǎn)1 1初始點(diǎn)可任選，每次迭代計(jì)算量小，初始點(diǎn)可任選，每次迭代計(jì)算量小，存儲(chǔ)量少，程序簡(jiǎn)短。即使從一個(gè)不好的存儲(chǔ)量少，程序簡(jiǎn)短。即使從一個(gè)不好的初始點(diǎn)出發(fā)，開(kāi)場(chǎng)的幾步迭代，目的函數(shù)初始點(diǎn)出發(fā)，開(kāi)場(chǎng)的幾步迭代，目的函數(shù)值下降很快，然后漸漸逼近部分極小點(diǎn)。值下降很快，然后漸漸逼近部分極小點(diǎn)。 2

6、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)變得很小，越走越慢。慢。 9程序程序編寫(xiě)編寫(xiě)1000102()10424()50100 xfxfxxx沿負(fù)梯度方向進(jìn)展一維搜索，有沿負(fù)梯度方向進(jìn)展一維搜索，有01000024()2 100fxxx0為一維搜索最正確步長(zhǎng)，應(yīng)滿足極值必要條為一維搜索最正確步長(zhǎng)，應(yīng)滿足極值必要條件件 122()min (24 )25(2 100 )min ( )f x例例5 51 1 求目的函數(shù)求目的函數(shù) 的極小點(diǎn)。的極小點(diǎn)

7、。解解 取初始點(diǎn)取初始點(diǎn)那么初始點(diǎn)處函數(shù)值及梯度分別為那么初始點(diǎn)處函數(shù)值及梯度分別為02,2Tx2212( )25fxxx1100( )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)解次迭代后，得到最優(yōu)解 00Tx()0fx12 這個(gè)問(wèn)題的目的函數(shù)的等值線為一簇橢圓這個(gè)問(wèn)題的目的函數(shù)的等值線為一簇橢圓, ,迭

8、代點(diǎn)從迭代點(diǎn)從 走的是一段鋸齒形道路，見(jiàn)圖走的是一段鋸齒形道路，見(jiàn)圖 。0 x13將上例中目的函數(shù)將上例中目的函數(shù) 引入變換引入變換2212( )25fxxx221212(,)y yyy其等值線由橢圓變成一簇同心圓。其等值線由橢圓變成一簇同心圓。 仍從仍從 即即 出發(fā)進(jìn)展最速下降法尋優(yōu)。此時(shí)：出發(fā)進(jìn)展最速下降法尋優(yōu)。此時(shí)：02,2Tx02,10Ty00102()10424()220yyyyy沿負(fù)梯度方向進(jìn)展一維搜索：沿負(fù)梯度方向進(jìn)展一維搜索：那么函數(shù)那么函數(shù)f(X)f(X)變?yōu)椋鹤優(yōu)椋簓1=x1, y2=5x2y1=x1, y2=5x2141000000()242410201020yyy 0

9、0為一維搜索最正確步長(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ù)：15010124010200()0 yy經(jīng)變換后，只需一次迭代，就可找到最優(yōu)解。經(jīng)變換后，只需一次迭代，就可找到最優(yōu)解。這是由于經(jīng)過(guò)尺度變換：這是由于經(jīng)過(guò)尺度變換：11225yxyx等值線由橢圓變成圓。等值線由橢圓變成圓。161 1實(shí)際明確，程序簡(jiǎn)單，對(duì)初始點(diǎn)要求不嚴(yán)厲。實(shí)際明確，程序簡(jiǎn)單，對(duì)初始點(diǎn)要求不嚴(yán)厲。2 2對(duì)普通函數(shù)而言，

10、梯度法的收斂速度并不快，由對(duì)普通函數(shù)而言，梯度法的收斂速度并不快，由于最速下降方向僅僅是指某點(diǎn)的一個(gè)部分性質(zhì)。于最速下降方向僅僅是指某點(diǎn)的一個(gè)部分性質(zhì)。3 3梯度法相鄰兩次搜索方向的正交性，決議了迭代梯度法相鄰兩次搜索方向的正交性，決議了迭代全過(guò)程的搜索道路呈鋸齒狀，在遠(yuǎn)離極小點(diǎn)時(shí)逼近速度全過(guò)程的搜索道路呈鋸齒狀，在遠(yuǎn)離極小點(diǎn)時(shí)逼近速度較快，而在接近極小點(diǎn)時(shí)逼近速度較慢。較快，而在接近極小點(diǎn)時(shí)逼近速度較慢。4 4梯度法的收斂速度與目的函數(shù)的性質(zhì)親密相關(guān)。梯度法的收斂速度與目的函數(shù)的性質(zhì)親密相關(guān)。對(duì)于等值線對(duì)于等值線( (面面) )為同心圓球的目的函數(shù)，一次搜索為同心圓球的目的函數(shù)，一次搜索即可

11、到達(dá)極小點(diǎn)。即可到達(dá)極小點(diǎn)。172( )( )()() ()1()()()2kkTkkTkkffffxxxxxxxxxxx設(shè)設(shè) 為為 的極小點(diǎn)的極小點(diǎn) 1kx( )x1()0kx( )x( )x( )f x1kx( )f x21()()()0kkkkffxxxx18這就是多元函數(shù)求極值的牛頓法迭代公式。這就是多元函數(shù)求極值的牛頓法迭代公式。 對(duì)于二次函數(shù)對(duì)于二次函數(shù) ，海賽矩陣，海賽矩陣 H H 是一個(gè)常矩陣，是一個(gè)常矩陣，其中各元素均為常數(shù)。因此，無(wú)論從任何點(diǎn)出發(fā)，其中各元素均為常數(shù)。因此，無(wú)論從任何點(diǎn)出發(fā)，只需一步就可找到極小點(diǎn)。只需一步就可找到極小點(diǎn)。 例例5 52 2 求目的函數(shù)求目的

12、函數(shù) 的極小點(diǎn)。的極小點(diǎn)。解：取初始點(diǎn)解：取初始點(diǎn)2212( )25fxxx02,2Tx102010102402()()121000050ff xxxx121()()(0,1,2,)kkkkffk xxxx1900 x()0fx 從牛頓法迭代公式的推演中可以看到，迭代點(diǎn)的位置是按照極值條件確定從牛頓法迭代公式的推演中可以看到，迭代點(diǎn)的位置是按照極值條件確定的，其中并未含有沿下降方向搜索的概念。因此對(duì)于非二次函數(shù)，假設(shè)采用上的，其中并未含有沿下降方向搜索的概念。因此對(duì)于非二次函數(shù)，假設(shè)采用上述牛頓迭代公式，有時(shí)會(huì)使函數(shù)值上升述牛頓迭代公式，有時(shí)會(huì)使函數(shù)值上升 。阻尼牛頓法阻尼牛頓法 121()(

13、)(0,1,2,)kkkkkkkksffkxxxxxk阻尼因子阻尼因子 ，沿牛頓方向進(jìn)展一維搜索的最，沿牛頓方向進(jìn)展一維搜索的最正確步長(zhǎng)，由下式求得：正確步長(zhǎng)，由下式求得： 1()()min()kkkkkkkffsfsxxx經(jīng)過(guò)一次迭代即求得極小點(diǎn)經(jīng)過(guò)一次迭代即求得極小點(diǎn)函數(shù)極小值函數(shù)極小值20開(kāi)始給定結(jié)束0,x21()()kkkff dxx1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k 阻尼牛頓法程序框圖21方法特點(diǎn)方法特點(diǎn) 1 1 初始點(diǎn)應(yīng)選在初始點(diǎn)應(yīng)選在X X* *附近，有一定難度；附近，有一定難度； 2 2 不僅要計(jì)算梯度，還要求海賽矩陣及其逆矩陣，不僅要計(jì)

14、算梯度，還要求海賽矩陣及其逆矩陣，計(jì)算量和存儲(chǔ)量大。此外，對(duì)于二階不可微的計(jì)算量和存儲(chǔ)量大。此外，對(duì)于二階不可微的F(X)F(X)也不也不適用。適用。 雖然阻尼牛頓法有上述缺陷，但在特定條件下它雖然阻尼牛頓法有上述缺陷，但在特定條件下它具有收斂最快的優(yōu)點(diǎn)，并為其他的算法提供了思緒和實(shí)具有收斂最快的優(yōu)點(diǎn)，并為其他的算法提供了思緒和實(shí)際根據(jù)。際根據(jù)。221(0,1,2,)kkkkskxx1() (0,1,2,)kkkkafkxxx121()()(0,1,2,)kkkkffk xxxx121()()(0,1,2,)kkkkkffkxxxx普通迭代式：普通迭代式：梯度法：梯度法：牛頓法：牛頓法：阻尼牛

15、頓法：阻尼牛頓法：梯度法與牛頓法：梯度法與牛頓法：1()kkkkkfxxAx23 前面引見(jiàn)的優(yōu)化方法，都需求計(jì)算目的函數(shù)的前面引見(jiàn)的優(yōu)化方法，都需求計(jì)算目的函數(shù)的導(dǎo)數(shù)，而在實(shí)踐工程的最優(yōu)化問(wèn)題中，目的函數(shù)的導(dǎo)導(dǎo)數(shù)，而在實(shí)踐工程的最優(yōu)化問(wèn)題中，目的函數(shù)的導(dǎo)數(shù)往往很難求出或者根本無(wú)法求出。下面所引見(jiàn)的方數(shù)往往很難求出或者根本無(wú)法求出。下面所引見(jiàn)的方法只需求計(jì)算目的函數(shù)值，無(wú)需求其導(dǎo)數(shù)，因此計(jì)算法只需求計(jì)算目的函數(shù)值，無(wú)需求其導(dǎo)數(shù)，因此計(jì)算比較簡(jiǎn)單，其幾何概念也比較明晰，屬于直接法的無(wú)比較簡(jiǎn)單，其幾何概念也比較明晰，屬于直接法的無(wú)約束最優(yōu)化方法。這類方法適用于不知道目的函數(shù)的約束最優(yōu)化方法。這類方法

16、適用于不知道目的函數(shù)的數(shù)學(xué)表達(dá)式而僅知其詳細(xì)算法的情況。這也是直接法數(shù)學(xué)表達(dá)式而僅知其詳細(xì)算法的情況。這也是直接法的一個(gè)優(yōu)點(diǎn)。的一個(gè)優(yōu)點(diǎn)。2425 此法的效能在很大程度上取決于目的函數(shù)的性質(zhì)。此法的效能在很大程度上取決于目的函數(shù)的性質(zhì)。 261 1計(jì)算量少，程序簡(jiǎn)單，不需求求函數(shù)導(dǎo)數(shù)的直接計(jì)算量少，程序簡(jiǎn)單，不需求求函數(shù)導(dǎo)數(shù)的直接探求目的函數(shù)最優(yōu)解的方法；探求目的函數(shù)最優(yōu)解的方法；2 2探求道路較長(zhǎng)，問(wèn)題的維數(shù)愈多求解的效率愈低。探求道路較長(zhǎng)，問(wèn)題的維數(shù)愈多求解的效率愈低。當(dāng)維數(shù)當(dāng)維數(shù)n n1010時(shí)，那么不應(yīng)采用此法。僅適用于時(shí)，那么不應(yīng)采用此法。僅適用于n n較少較少n 10n 10的目的

17、函數(shù)求優(yōu)；的目的函數(shù)求優(yōu)； 3 3改動(dòng)初始點(diǎn)重新迭代，可防止出現(xiàn)病態(tài)。改動(dòng)初始點(diǎn)重新迭代，可防止出現(xiàn)病態(tài)。 2728一、根本思想一、根本思想 單純形交換法也是一種不運(yùn)用導(dǎo)數(shù)的求解單純形交換法也是一種不運(yùn)用導(dǎo)數(shù)的求解無(wú)約束極小化問(wèn)題的直接搜索方法，與前面幾種無(wú)約束極小化問(wèn)題的直接搜索方法，與前面幾種方法不同的是，單純形交換法不是利用搜索方向方法不同的是，單純形交換法不是利用搜索方向從一個(gè)點(diǎn)迭代到另一個(gè)更優(yōu)的點(diǎn)，而是從一個(gè)單從一個(gè)點(diǎn)迭代到另一個(gè)更優(yōu)的點(diǎn)，而是從一個(gè)單純形迭代到另一個(gè)更優(yōu)的單純形。純形迭代到另一個(gè)更優(yōu)的單純形。29定義：?jiǎn)渭冃味x：?jiǎn)渭冃?n n 維空間中的恰好有維空間中的恰好有n+

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

19、參見(jiàn)以下圖。301 1反射反射設(shè)除了最劣點(diǎn)設(shè)除了最劣點(diǎn)X1X1以外的基余頂點(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)的過(guò)的反射點(diǎn)。求反射點(diǎn)的過(guò)程稱之為反射。程稱之為反射。)()()(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隔

20、到點(diǎn)X6X6。X6X6稱之為擴(kuò)張點(diǎn)，求擴(kuò)張點(diǎn)的過(guò)程稱之為稱之為擴(kuò)張點(diǎn)，求擴(kuò)張點(diǎn)的過(guò)程稱之為擴(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，且有，且有31)()()(251XfXfXf假設(shè)出現(xiàn)假設(shè)出