1、第三章無約束優化法概述梯度法牛頓法共軛梯度法坐標輪換法鮑威爾法概述無約束優化問題的一般形式：求設計變量Xx,x,.xT12n使目標函數F（x）min，對X沒有任何約束條件。工程實際問題中，無約束結構優化問題很少，多數是有約束條件的。學習無約束結構優化原因：1）工程也有少量無約束結構優化問題，其數學模型就是無約束優化問題，除了在非常接近最小點的情況下，可以按無約束問題處理；2）為研究約束優化問題打下基礎；3）約束優化問題可以通過一系列無約束方法達到。無約束優化問題的求解，可以直接應用函數極值問題的求解方程：F0的問題，即求X，使其滿足：00X2n個方程組，一般為非線性的，很難用解析方法求解，一般

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

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

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

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

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

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

8、一般目標函數f(X)具有一、二階偏導數，此時，在Xk處做泰勒展開并取值二次項，得：1f(X)(X)f(Xk)時(Xk)t(XXk)(XXk)T2f(Xk)t(XXk)2其中H(Xk)2fXk為f(X)在Xk的海森矩陣，是對稱方陣。求f(X)的極小問題轉換為(X)的極小值問題。令(X)0，即：f(Xk)H(Xk(XXk)0若H(Xk)為正定，解得：XXkH(Xk).(Xk)由于Xk在極小點附近，X乍為f(x)極小點的下一個近似點XkXkH(Xk).(Xk)其中：搜索方向Sk叫(Xk).(Xk)步長恒為1。例題：用牛頓法求解問題minf(X)4x2x2,12其中，x)t.取初始點(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,迭代結束，得X為問題的最優解。以上例子說明，牛頓法比最速下降法收斂快有定理可以證明，當初始點X0靠近極小點X國寸，牛頓法的收斂速度是很快的。但是，當X0遠離X!時，牛頓法可能不收斂，甚至連下降性也保證不了。其原因是：迭代點Xk不一定是目標函數f在搜索方向k上的極小點僅是)在牛頓方向上的極小點。習題三：用牛頓法求目標函數F(X)X225%2的極小點和極小值。取初始點X02,2/習題四：:用牛頓法求F(X)10%2X24X2的最優解，取

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

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

12、梯度方向為搜索方向，會產生鋸齒現象；為避免鋸齒的發生，取下一次的迭代搜索方向直接指向極小點，如果選定這樣的搜索方向，對于二元二次函數只需進行兩次直線搜索就可以求到極小點。初選初始點X0沿某個下降方向S0做一維I0是沿S0方向搜索的最佳步長，即在點X1處的函數F(X)沿方向S0的方向導數為零?？紤]到點X1處方向導數與梯度之間的關系，有：毛F1S00S0為避免鋸齒現象，下一次迭代搜索方向S1指向極小點XXX11S1其中1為方向S1的最佳步長。這樣的S1滿足什么條件？對于二次函數F(X)在X處取得極小點的必要條件：F*!HX*B0(F1.HX1B)即：FX*!H(X1-iS1)BHX1B11HS1f

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

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

15、雙Jg）與Sk的共軛方向SJ正交。如下圖所示。坐標輪換法以上方法都要計算目標函數的偏導數，屬于間接法。大量的工程問題目標函數往往很復雜，有的沒有明顯的解析表達式，其導數難以獲得或根本不存在，間接法無法使用，只能借助直接法。坐標輪換法是每次搜索只允許一個變量變化，其余變量保持不變，即沿坐標方向輪流進行搜索的尋優方法。它把多變量的優化問題輪流地轉化成單變量的優化問題。又稱變量輪換法，也稱降維法。其基本原理是將一個多維的無約束最優化問題轉化為一系列較低維的最優化問題來求解，簡單地說，就是先將nH個變量固定不動，只對第一個變量進行一維搜索得到最優點X1，然后，又保持n個變量1不變，再對第二個變量進行一

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

17、函數F(X)%2%2%10%4%60的無約束最優解。121212取初始點X00,0嘰迭代精度0.1。解：第一輪：沿S：即1方向進行一維搜索，取X0X0，因為X11X0-1S110卜1訪需dF(XdF(X1)d12BH001minF(X1)2H10H60111得：15x1以X1以X1為起點，沿e2方向進行一維搜索,因為X2-X尸2S2噌卜2i準i2minF(X1)2525B504B602935222222dF(X1)2B90d22”_5得：4.5X1.2.檢測：|x2xi|J524.526.7進行第二輪。精確解：x8,x6,F8。12min習題六:用坐標輪換法求函數F(X)2x23x28x10的

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