無(wú)約束優(yōu)化法

1、第三章無(wú)約束優(yōu)化法概述梯度法牛頓法共軛梯度法坐標(biāo)輪換法鮑威爾法概述無(wú)約束優(yōu)化問(wèn)題的一般形式：求設(shè)計(jì)變量Xx,x,.xT12n使目標(biāo)函數(shù)F（x）min，對(duì)X沒(méi)有任何約束條件。工程實(shí)際問(wèn)題中，無(wú)約束結(jié)構(gòu)優(yōu)化問(wèn)題很少，多數(shù)是有約束條件的。學(xué)習(xí)無(wú)約束結(jié)構(gòu)優(yōu)化原因：1）工程也有少量無(wú)約束結(jié)構(gòu)優(yōu)化問(wèn)題，其數(shù)學(xué)模型就是無(wú)約束優(yōu)化問(wèn)題，除了在非常接近最小點(diǎn)的情況下，可以按無(wú)約束問(wèn)題處理；2）為研究約束優(yōu)化問(wèn)題打下基礎(chǔ)；3）約束優(yōu)化問(wèn)題可以通過(guò)一系列無(wú)約束方法達(dá)到。無(wú)約束優(yōu)化問(wèn)題的求解，可以直接應(yīng)用函數(shù)極值問(wèn)題的求解方程：F0的問(wèn)題，即求X，使其滿足：00X2n個(gè)方程組，一般為非線性的，很難用解析方法求解，一般

2、采用數(shù)值方法。與其用數(shù)值方法求解非線性方程組，倒不如用數(shù)值方法直接求解無(wú)約束極值問(wèn)題。數(shù)值方法最常用的就是搜索法，其基本思想：從給定的初始點(diǎn)x0出發(fā)，按照一定原則尋找搜索方向S0，沿方向S0進(jìn)行搜索，確定最佳步長(zhǎng)0，使得函數(shù)沿方向S0下降最快，依次形成迭代公式:XkXkkSkk0,1,2,.各種無(wú)約束優(yōu)化方法的區(qū)別在于確定搜索方向Sk的方法，這是無(wú)約束優(yōu)化方法的關(guān)鍵。根據(jù)構(gòu)成搜索方向所使用的信息不同分為：間接法利用目標(biāo)函數(shù)的一階或二階導(dǎo)數(shù)，如梯度法（最速下降法）、牛頓法、共軛梯度法和變尺度法；直接法直接利用目標(biāo)函數(shù)，如坐標(biāo)輪換法、鮑威爾法和單形替換法。梯度法最早由1847年柯西提出，是無(wú)約束優(yōu)

3、化的基本方法。其基本思想：取目標(biāo)函數(shù)的負(fù)梯度方向作為迭代的搜索方向，必使函數(shù)值下降的速度最快。設(shè)在第k次迭代中取得迭代點(diǎn)*從該點(diǎn)出發(fā)，取負(fù)梯度方向：SkF(Xk)為搜索方向，式中：.(Xk)*(Xk)*(Xk)TOC o 1-5 h z HYPERLINK l bookmark18 F(Xk),，.xxx12n第k1次得到的新點(diǎn)：XkXkkF(Xk)一般步長(zhǎng)k1常采用沿負(fù)梯度方向做一維搜索：F(Xk)minF(XkkSk)算法特點(diǎn)：初始階段改進(jìn)較快，最優(yōu)解附近改進(jìn)較慢。具體迭代步驟：.選擇初始點(diǎn)X0及迭代精度0，令迭代次數(shù)k0；.計(jì)算點(diǎn)Xk的梯度F(Xk)及梯度的模F(Xk)|，并令SkF(X

4、k).判斷是否滿足收斂精度眄F(Xk)|一般情況下，若|F(Xk)|，則Xk為近似最優(yōu)點(diǎn)，F(xiàn)(Xk)為近似最優(yōu)值，可以輸出最優(yōu)解XXk，F(xiàn)(X)F(Xk)，否則進(jìn)行4.從點(diǎn)Xk出發(fā)，沿負(fù)梯度方向求最優(yōu)步長(zhǎng)，及沿Sk進(jìn)行一維搜索，求得使函數(shù)下降最多的步長(zhǎng)因子kminF(Xk1kSk)min().確定新的近似點(diǎn)X0,此點(diǎn)也就是下次迭代的出發(fā)點(diǎn)XkXkkSk令kkH，轉(zhuǎn)入2步。例題：用最速下降法求解問(wèn)題minf(X)4x2x2,12其中,，)t.取初始點(diǎn)(i,ir,允許誤差0.1.120解：f在點(diǎn)X(,x)T處的梯度,(X)(8x,2x)T.12i2第一次迭代：令搜索方向(X)(IB,IE)t,00

5、|11%：6442v17故從點(diǎn)出發(fā)沿作一維搜索，代入目標(biāo)函數(shù)并求其最小值00f+令即最佳步長(zhǎng)因子00得0.i30769XO0.13.769(*,IE)t(D.046152,0.738462)t第二次迭代：令搜索方向(X)(0.369216,1.476924)t,1|:|2.183051.522375從點(diǎn)出發(fā)沿作一維搜索，11X(0.101537,0.147682)T第三次迭代：令搜索方向(X)(0.369216,1.476924)t,22|0.7470560.864329從點(diǎn)出發(fā)沿作一維搜索，22X(0.009747,0.107217)T3第四次迭代：令搜索方向(X)(0.077976,BQ.

6、214434)t,33|0.0520620.228171從點(diǎn)出發(fā)沿作一維搜索，33X(0.019126,0.027816)T4第五次迭代：令搜索方向(X)(D.153008,ID.055632)t,4411|40.0265060.162807從點(diǎn)出發(fā)沿作一維搜索，44X(0.001835,0.020195)T5此時(shí),|.(X5)|0.001847滿足精度要求，故得問(wèn)題的最優(yōu)解為X(0.001835,0.020195)T5實(shí)際上，原問(wèn)題的最優(yōu)解為(0,0)t梯度法的特點(diǎn)：理論明確，方法簡(jiǎn)單，概念清楚，計(jì)算不量小，對(duì)初始點(diǎn)沒(méi)有嚴(yán)格要求。相鄰兩次迭代的梯度方向是相互正交的，搜索線路呈直角鋸齒形，越靠

7、近極小點(diǎn)，搜索密度越大，收斂越慢。迭代次數(shù)與目標(biāo)函數(shù)等值線的形狀有關(guān)，目標(biāo)函數(shù)若為橢圓族越扁，迭代次數(shù)越多，搜索到最優(yōu)點(diǎn)的難度越大。所謂最速下降方向f(X)僅僅反出對(duì)局部來(lái)說(shuō)是最速的下降方向，及但對(duì)整體：形的，當(dāng)?shù)c(diǎn)越靠近X,其搜索步長(zhǎng)形的，當(dāng)?shù)c(diǎn)越靠近X,其搜索步長(zhǎng)q95,心,乂越慢。：試用梯度法求目標(biāo)函數(shù)F(X)(%1)2(X1)2的極小值，設(shè)初始點(diǎn)X00,8,0.01o習(xí)題二,試用梯度法求目標(biāo)函數(shù)F(X)x225x2的最優(yōu)解。初始點(diǎn)X02,2t,迭代精度0.05。牛頓法牛頓法的基本思想就是利用二次函數(shù)來(lái)代替原目標(biāo)函數(shù),以二次函數(shù)的極小點(diǎn)作為原目標(biāo)函數(shù)的極小點(diǎn)的近似,并逐步逼近該點(diǎn)。設(shè)

8、一般目標(biāo)函數(shù)f(X)具有一、二階偏導(dǎo)數(shù)，此時(shí)，在Xk處做泰勒展開(kāi)并取值二次項(xiàng)，得：1f(X)(X)f(Xk)時(shí)(Xk)t(XXk)(XXk)T2f(Xk)t(XXk)2其中H(Xk)2fXk為f(X)在Xk的海森矩陣，是對(duì)稱方陣。求f(X)的極小問(wèn)題轉(zhuǎn)換為(X)的極小值問(wèn)題。令(X)0，即：f(Xk)H(Xk(XXk)0若H(Xk)為正定，解得：XXkH(Xk).(Xk)由于Xk在極小點(diǎn)附近，X乍為f(x)極小點(diǎn)的下一個(gè)近似點(diǎn)XkXkH(Xk).(Xk)其中：搜索方向Sk叫(Xk).(Xk)步長(zhǎng)恒為1。例題：用牛頓法求解問(wèn)題minf(X)4x2x2,12其中，x)t.取初始點(diǎn)(1,1T,允許誤

9、差0.1.解：120解：f(X0)2T，2于(X0)故。.2。.2f(X0怖叫(X0)XXS(1,1)T(1,1)T(0,0)Ti00由于IIf(X1)|00.1,迭代結(jié)束，得X為問(wèn)題的最優(yōu)解。以上例子說(shuō)明，牛頓法比最速下降法收斂快有定理可以證明，當(dāng)初始點(diǎn)X0靠近極小點(diǎn)X國(guó)寸，牛頓法的收斂速度是很快的。但是，當(dāng)X0遠(yuǎn)離X!時(shí)，牛頓法可能不收斂，甚至連下降性也保證不了。其原因是：迭代點(diǎn)Xk不一定是目標(biāo)函數(shù)f在搜索方向k上的極小點(diǎn)僅是)在牛頓方向上的極小點(diǎn)。習(xí)題三：用牛頓法求目標(biāo)函數(shù)F(X)X225%2的極小點(diǎn)和極小值。取初始點(diǎn)X02,2/習(xí)題四：:用牛頓法求F(X)10%2X24X2的最優(yōu)解，取

10、初始點(diǎn)X02,5t,迭代122精度0.01。修正牛頓法為了彌補(bǔ)牛頓法的上述缺陷，人們把牛頓法作了如下修正：由Xk求Xk時(shí)，不直接用迭代公式XkXk2f(Xk)HBf(Xk)，因?yàn)檫@個(gè)公式已經(jīng)把步長(zhǎng)限定為1。而是沿著牛頓方向k進(jìn)行一維搜索。這樣就是所謂的阻尼牛頓法，也稱為修正牛頓法。阻尼牛頓法一般步驟：選取初始數(shù)據(jù)。選取初始點(diǎn)X0,給定允許誤差0,令k0檢驗(yàn)是否滿足終止準(zhǔn)則。計(jì)算(Xk),若|(Xk)|迭代終止，Xk為問(wèn)題的近似最優(yōu)解；否則，轉(zhuǎn)Step3.構(gòu)造牛頓方向。計(jì)算.2f(Xk)，取2f(Xk)(Xk)進(jìn)行一維搜索。求k和Xk，使得f(Xkk)minf(Xk-)0Xk1XkkSk令X:X

11、k-l,返回step2牛頓法特點(diǎn)如果f(%)是對(duì)稱正定矩陣A的二次函數(shù)，則用牛頓法經(jīng)過(guò)一次迭代，就可達(dá)到最優(yōu)點(diǎn),如不是二次函數(shù),則牛頓法不能一步達(dá)到極值點(diǎn),但由于這種函數(shù)在極值點(diǎn)附近和二次函數(shù)很近似,因此牛頓法的收斂速度還是很快的。牛頓法的收斂速度雖然較快,但要求海森矩陣要可逆,要計(jì)算二階導(dǎo)數(shù)和逆矩陣,就加大了計(jì)算機(jī)計(jì)算量和存儲(chǔ)量。習(xí)題五：用阻尼牛頓法求函數(shù)F(X)4(%1)22(%Hl)2%10的最優(yōu)解，取初1212始點(diǎn)X00,0t,迭代精度0.001。共軛方向法和共軛梯度法共軛方向概念共軛方向的概念是在研究二次函數(shù)FX.2XtHXBtXC過(guò)程中引出的?？紤]二維情形，如果按最速下降法，選擇負(fù)

12、梯度方向?yàn)樗阉鞣较颍瑫?huì)產(chǎn)生鋸齒現(xiàn)象；為避免鋸齒的發(fā)生，取下一次的迭代搜索方向直接指向極小點(diǎn)，如果選定這樣的搜索方向，對(duì)于二元二次函數(shù)只需進(jìn)行兩次直線搜索就可以求到極小點(diǎn)。初選初始點(diǎn)X0沿某個(gè)下降方向S0做一維I0是沿S0方向搜索的最佳步長(zhǎng)，即在點(diǎn)X1處的函數(shù)F(X)沿方向S0的方向?qū)?shù)為零。考慮到點(diǎn)X1處方向?qū)?shù)與梯度之間的關(guān)系，有：毛F1S00S0為避免鋸齒現(xiàn)象，下一次迭代搜索方向S1指向極小點(diǎn)XXX11S1其中1為方向S1的最佳步長(zhǎng)。這樣的S1滿足什么條件？對(duì)于二次函數(shù)F(X)在X處取得極小點(diǎn)的必要條件：F*!HX*B0(F1.HX1B)即：FX*!H(X1-iS1)BHX1B11HS1f

13、1*!1HS10上式兩邊左乘.0.得：S0THS10滿足上式的兩個(gè)量S0和S1稱為H的共軛向量，或稱S0和S1對(duì)H是共軛方向。G是nxn對(duì)稱正定矩陣，方向向量di,d2,d.的.如果:dTGd0ijij稱方向向量di,d2,dm關(guān)于G的共軛方向共軛方向性質(zhì)：1)S0,S1,。關(guān)于G共軛，這些向量是線性無(wú)關(guān)的；2)在N維空間中相互共軛的向量個(gè)數(shù)不超過(guò)N個(gè)；3)若G是單位矩陣，則S0，S1，。相互垂直正交；共軛方向法步驟：.選定初始點(diǎn)X0，下降方向S0和收斂精度，迭代次數(shù)k0；.沿Sk方向進(jìn)行一維搜索，得Xk.Xk-kSk；.判斷F(Xk)是否滿足，若滿足則打印輸出；否則轉(zhuǎn)4。.提供新的共軛方向S

14、k，使SjTHSk0，j0,1,2,.k.kkH，轉(zhuǎn)2。共軛梯度法共軛梯度法是共軛方向法的一種，共軛向量有迭代點(diǎn)的負(fù)梯度構(gòu)造出來(lái)，所以稱共軛梯度法。該法于1964年由弗里茨和里烏斯兩人提出。首先研究共軛方向與梯度之間關(guān)系：FX-XtHXBtXC2從點(diǎn)Xk出發(fā)，沿H的某一共軛方向Sk做一維搜索，到達(dá)Xk點(diǎn)即：XkXkkSk在點(diǎn)Xk，Xk處的梯度g，g為kkgHXkB，gHXkBkk有：ggH(XkXk)kHSkkk若Sj,Sk對(duì)H是共軛的，有：.j.HSk0(SkBigk代入上式得：Sj(SkBigkkk得出共軛方向與梯度之間的關(guān)系。此式表明沿方向Sk進(jìn)行一維搜索，其終點(diǎn)Xk和始點(diǎn)Xk的梯度之差

15、雙Jg）與Sk的共軛方向SJ正交。如下圖所示。坐標(biāo)輪換法以上方法都要計(jì)算目標(biāo)函數(shù)的偏導(dǎo)數(shù)，屬于間接法。大量的工程問(wèn)題目標(biāo)函數(shù)往往很復(fù)雜，有的沒(méi)有明顯的解析表達(dá)式，其導(dǎo)數(shù)難以獲得或根本不存在，間接法無(wú)法使用，只能借助直接法。坐標(biāo)輪換法是每次搜索只允許一個(gè)變量變化，其余變量保持不變，即沿坐標(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ō)，就是先將nH個(gè)變量固定不動(dòng)，只對(duì)第一個(gè)變量進(jìn)行一維搜索得到最優(yōu)點(diǎn)X1，然后，又保持n個(gè)變量1不變，再對(duì)第二個(gè)變量進(jìn)行一

16、維搜索到X1等等，直到所有變量進(jìn)行后完成一輪，再進(jìn)行下2一輪的變換，把N維優(yōu)化問(wèn)題轉(zhuǎn)化為一系列一維優(yōu)化問(wèn)題。X的右上角表示迭代的輪數(shù)，右下角表示該輪中的兩個(gè)迭代點(diǎn)。搜索方向與步長(zhǎng)的確定對(duì)于第k輪第i次的計(jì)算：XkXkkSki1,2,n.iiii其中Xk第k輪第iH次迭代起始點(diǎn)；iSk第k輪第i次搜索方向，它輪換取n維坐標(biāo)的單位向量，iSke010嘰其中第i分量為1,其余為0.iik第k輪第i次迭代步長(zhǎng)因子。i步長(zhǎng)可正可負(fù),一般采用最優(yōu)步長(zhǎng)法,就是沿坐標(biāo)軸方向搜索中,利用黃金分割法等確定沿該方向上的具有最小目標(biāo)函數(shù)的步長(zhǎng),即：F(XkkSk)minF(XkSk)i*iiii例題：坐標(biāo)輪換法求目標(biāo)

17、函數(shù)F(X)%2%2%10%4%60的無(wú)約束最優(yōu)解。121212取初始點(diǎn)X00,0嘰迭代精度0.1。解：第一輪：沿S：即1方向進(jìn)行一維搜索，取X0X0，因?yàn)閄11X0-1S110卜1訪需dF(XdF(X1)d12BH001minF(X1)2H10H60111得：15x1以X1以X1為起點(diǎn)，沿e2方向進(jìn)行一維搜索,因?yàn)閄2-X尸2S2噌卜2i準(zhǔn)i2minF(X1)2525B504B602935222222dF(X1)2B90d22”_5得：4.5X1.2.檢測(cè)：|x2xi|J524.526.7進(jìn)行第二輪。精確解：x8,x6,F8。12min習(xí)題六:用坐標(biāo)輪換法求函數(shù)F(X)2x23x28x10的

18、無(wú)約束最優(yōu)解，取初始點(diǎn)X01,2t，迭代精度0.01。坐標(biāo)輪換法的問(wèn)題W11a)當(dāng)函數(shù)白睛叫UW11a)當(dāng)函數(shù)白睛叫U長(zhǎng)短軸平伊則網(wǎng)b)當(dāng)函數(shù)的返次其長(zhǎng)短軸與強(qiáng)解Mc)當(dāng)函國(guó)恒愈1長(zhǎng)沼軸h”屣余運(yùn)!用其陸芳去。找才刎修6)鮑威爾法Powell法是利用共軛方向可以加速收斂的性質(zhì)所形成的一種搜索算法，又稱方向加速法。共軛方向的生成9攵斂快，多次搜索方臺(tái)華1,血任回坐標(biāo)士聞都無(wú)法使函數(shù)下降，改71抻占0/卜/1設(shè)Xk、Xk從不同點(diǎn)出發(fā)，沿同一方向Sj進(jìn)行一維搜索得到兩個(gè)極小點(diǎn)，根據(jù)梯度與等值面垂直性質(zhì)，Sj與Xk、Xk兩點(diǎn)的梯度ggk存在以下關(guān)系:0k同時(shí)：由二維推廣至N維，鮑威爾算法就是在每輪開(kāi)始點(diǎn)和終止點(diǎn)決定新的搜索方向，把這個(gè)新方向替換原來(lái)N