四章無(wú)約束優(yōu)化方法ppt課件

1、第四章無(wú)約束優(yōu)化方法第一節(jié) 概述從第一章列舉的機(jī)械設(shè)計(jì)問(wèn)題，大多數(shù)實(shí)踐問(wèn)題是約束優(yōu)化問(wèn)題。約束優(yōu)化問(wèn)題的求解轉(zhuǎn)化為一系列的無(wú)約束優(yōu)化問(wèn)題實(shí)現(xiàn)的。因此，無(wú)約束優(yōu)化問(wèn)題的解法是優(yōu)化設(shè)計(jì)方法的根本組成部分，也是優(yōu)化方法的根底。*0f x無(wú)約束優(yōu)化問(wèn)題的極值條件解析法數(shù)值法數(shù)學(xué)模型復(fù)雜時(shí)不便求解可以處置復(fù)雜函數(shù)及沒(méi)有數(shù)學(xué)表達(dá)式的優(yōu)化設(shè)計(jì)問(wèn)題1kkkkxxa d搜索方向問(wèn)題是無(wú)約束優(yōu)化方法的關(guān)鍵。各種無(wú)約束優(yōu)化方法的區(qū)別：確定搜索方向的方法不同。無(wú)約束優(yōu)化方法分類利用目的函數(shù)的一階或二階導(dǎo)數(shù)利用目的函數(shù)值最速下降法、共軛梯度法、牛頓法坐標(biāo)輪換法、鮑威爾等第二節(jié) 最速下降法優(yōu)化設(shè)計(jì)追求目的函數(shù)值最小，假設(shè)

2、搜索方向取該點(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è)搜索方向相互垂直。例4-1 求目的函數(shù) 221225f xxx的極小點(diǎn)。第三節(jié)牛頓型方法在第三章中，我們?cè)?jīng)討論了一維搜索的牛頓方法

3、。得出一維情況下的牛頓迭代公式1kkkkfxxxfx對(duì)于多元函數(shù)，在kx泰勒展開，得 f xx 212TTkkkkkkf xf xxxxxf xxx設(shè)1kx為函數(shù)的極小點(diǎn)，根據(jù)極值的必要條件10kx210kkkkf xf xxx112kkkkxxf xf x 這是多元函數(shù)求極值的牛頓法迭代公式。例4-2 用牛頓法求 221225f xxx的極小值。對(duì)牛頓法進(jìn)展改良，提出“阻尼牛頓法112kkkkkxxf xf x1minkkkkkkf xfxa dfxad第四節(jié)共軛方向及共軛方向法為了抑制最速下降法的鋸齒景象，提高收斂速度，開展了一類共軛方向法。搜索方向是共軛方向。一、共軛方向的概念 12TT

4、f xx Gxb xc共軛方向的概念是在研討二次函數(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的共軛方向。三、共軛方向法1、選定初始點(diǎn) ，下降方向

5、 和收斂精度，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)造出來(lái)，所以稱共軛梯度法。 12TTf xx Gxb xc1kkkkxxa d1kkkkxxa dkkgGxb從點(diǎn) 出發(fā)，沿G某一共軛方向 作一維搜索,到達(dá)kxkd1kx11kkgGxb而在點(diǎn) 、 處的梯度分別為：kx1kx11kkkkkkggG xxa Gd10TjkdGd0TjkdGd 10Tjkkd

6、G gg得出共軛方向與梯度之間的關(guān)系。此式闡明沿方向kd進(jìn)展一維搜索，其終點(diǎn) 與始點(diǎn) 的梯度值差1kxkx1kkgg與 的共軛方向 正交。kdjd圖4-9 共軛梯度法的幾何闡明第六節(jié)變尺度法1kkkkxxHf x變尺度法的根本思想：前面討論的梯度法和牛頓法，它們的迭代公式可以看作以下公式的特例。變尺度法是對(duì)牛頓法的修正，它不是計(jì)算二階導(dǎo)數(shù)的矩陣和它的逆矩陣，而是設(shè)法構(gòu)造一個(gè)對(duì)稱正定矩陣H來(lái)替代Hesse矩陣的逆矩陣。并在迭代過(guò)程中，使其逐漸逼近H-1 。由于對(duì)稱矩陣H在迭代過(guò)程中是不斷修正改動(dòng)的，它對(duì)于一般尺度的梯度起到改動(dòng)尺度的作用，因此H又稱變尺度矩陣。一、尺度矩陣的概念變量的尺度變換是放

7、大或減少各個(gè)坐標(biāo)。經(jīng)過(guò)尺度變換可以把函數(shù)的偏心程度降低到最低限制。對(duì)于普通二次函數(shù) 12TTf xx Gxb xc假設(shè)進(jìn)展尺度變換xQx那么在新的坐標(biāo)系中，函數(shù)的二次項(xiàng)變?yōu)?122TTTx Gxx Q GQx選擇這樣變換的目的：降低二次項(xiàng)的偏心程度。假設(shè)矩陣G是正定的，那么總存在矩陣Q使TQ GQI使得函數(shù)偏心度變?yōu)榱?。用Q-1 右乘等式兩邊，得1TQ GQ再用Q左乘等式兩邊，得TQQ GI所以1TQQG闡明二次函數(shù)矩陣G的逆矩陣，可以經(jīng)過(guò)尺度變換矩陣Q求得。這樣，牛頓法迭代過(guò)程中的牛頓方向可寫成：1kkTkdGf xQQf x 1kkkTkxxQQf x三、變尺度法的普通步驟第七節(jié) 坐標(biāo)輪換

8、法坐標(biāo)輪換法是每次搜索只允許一個(gè)變量變化，其他變量堅(jiān)持不變，即沿坐標(biāo)方向輪番進(jìn)展搜索的尋優(yōu)方法。它把多變量的優(yōu)化問(wèn)題輪番地轉(zhuǎn)化成單變量的優(yōu)化問(wèn)題。因此又稱變量輪換法。 其根本原理是將一個(gè)多維的無(wú)約束最優(yōu)化問(wèn)題轉(zhuǎn)化為一系列較低維的最優(yōu)化問(wèn)題來(lái)求解，簡(jiǎn)單地說(shuō)，就是先將(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)輪換法原理圖動(dòng)畫演示)0(2)0(1XX)0(2)1(1XX)1(2)1(1XX)2(2)2(1XX2. 搜索方向與步長(zhǎng)確實(shí)定1搜索方向確實(shí)定對(duì)于第k輪第i次的計(jì)算1kkkkiiiixxa d第k輪第I次的迭代方向，它輪番取n維坐標(biāo)的單位向量。0.1.0kiide 3.搜索步長(zhǎng)確實(shí)定關(guān)于 值通常有以下幾種取法1加速步長(zhǎng)法2最優(yōu)步長(zhǎng)法 最優(yōu)步長(zhǎng)法就是利用一維最優(yōu)搜索方法來(lái)完成每一次迭代，即此時(shí)可以采用0.618方法或二次插值方法來(lái)計(jì)算 的值。)( ki圖413 加速步長(zhǎng)法的搜索道路圖414 最優(yōu)步長(zhǎng)法的搜索道路4 . 坐標(biāo)輪換法存在的問(wèn)題圖415 坐標(biāo)輪換法在各種不同情況下的效能a搜索有效；b搜索低效；c搜索無(wú)效第八節(jié) Powell法方向加速法 Powell法是利用共