34結(jié)構(gòu)優(yōu)化算法基礎之無約束優(yōu)化方法

1、3.4 無約束優(yōu)化方法3.4.1 概述大多數(shù)實際問題是約束優(yōu)化問題。約束優(yōu)化問題的求解轉(zhuǎn)化為一系列的無約束優(yōu)化問題實現(xiàn)。因此，無約束優(yōu)化問題的解法是優(yōu)化設計方法的基本組成部分，也是優(yōu)化方法的基礎。*0f x無約束優(yōu)化問題的極值條件解析法數(shù)值法數(shù)學模型復雜時不便求解可以處理復雜函數(shù)及沒有數(shù)學表達式的優(yōu)化設計問題1kkkkxxa d搜索方向問題是無約束優(yōu)化方法的關(guān)鍵。各種無約束優(yōu)化方法的區(qū)別：確定搜索方向的方法不同。無約束優(yōu)化方法分類利用目標函數(shù)的一階或二階導數(shù)利用目標函數(shù)值（最速下降法、共軛梯度法、牛頓法）（坐標輪換法、鮑威爾等）3.4.2 最速下降法優(yōu)化設計追求目標函數(shù)值最小，若搜索方向取該點

2、的負梯度方向，使函數(shù)值在該點附近的范圍內(nèi)下降最快。按此規(guī)律不斷走步，形成以下迭代算法：1kkkkxxaf x以負梯度方向為搜索方向，所以稱最速下降法最速下降法或梯度法梯度法。搜索方向確定為負梯度方向，還需確定步長因子ka即求一維搜索的最佳步長，既有 1minminkkkkkkkf xfxaf xfxaf x 0tkkkkfxaf xf x 10tkkf xf x10tkkdd由此可知，在最速下降法中，相鄰兩個迭代點上的相鄰兩個迭代點上的函數(shù)梯度相互垂直函數(shù)梯度相互垂直。而搜索方向就是負梯度方向，因此相鄰兩個搜索方向互相垂直。例4-1 求目標函數(shù) 221225f xxx的極小點。3.4.3 牛頓

3、型方法前面討論了一維搜索的牛頓方法。得出一維情況下的牛頓迭代公式1kkkkfxxxfx對于多元函數(shù)，在kx泰勒展開，得 f xx 212ttkkkkkkf xf xxxxxf xxx設1kx為函數(shù)的極小點，根據(jù)極值的必要條件10kx210kkkkf xf xxx112kkkkxxf xf x 這是多元函數(shù)求極值的牛頓法迭代公式。例4-2 用牛頓法求 221225f xxx的極小值。對牛頓法進行改進，提出“阻尼牛頓法”112kkkkkxxf xf x1minkkkkkkf xfxa dfxad3.4.4 共軛方向及共軛方向法為了克服最速下降法的鋸齒現(xiàn)象，提高收斂速度，發(fā)展了一類共軛方向法。搜索方

4、向是共軛方向。一、共軛方向的概念 12ttf xx gxb xc共軛方向的概念是在研究二次函數(shù)時引出的。首先考慮二維情況如果按最速下降法，選擇負梯度方向為搜索方向，會產(chǎn)生鋸齒現(xiàn)象。為避免鋸齒的發(fā)生，取下一次的迭代搜索方向直接指向極小點，如果選定這樣的搜索方向，對于二元二次函數(shù)只需進行兩次直線搜索就可以求到極小點。1000 xxa d*111xxa d 1100txff xdd 1d應滿足什么條件？對于二次函數(shù) 在 處取得極小點的必要條件 f x*x*0f xgxb*111111f xg xa dbgxbagd 1110f xagd 等式兩邊同乘 得0td010tdgd 0d1d是對g的共軛方向

5、的共軛方向。三、共軛方向法1、選定初始點 ，下降方向 和收斂精度，k=0。0 x0d2、沿 方向進行一維搜索，得kd1kkkkxxa d3、判斷 是否滿足，若滿足則打印1kf x1kx否則轉(zhuǎn)4。4、提供新的共軛方向 ，使 1kd10tjkdgd5、置 ，轉(zhuǎn)2。1kk3.4.5 共軛梯度法共軛梯度法是共軛方向法的一種，共軛向量由迭代點的負梯度構(gòu)造出來，所以稱共軛梯度法。 12ttf xx gxb xc1kkkkxxa d1kkkkxxa dkkggxb從點 出發(fā)，沿g某一共軛方向 作一維搜索，到達kxkd1kx11kkggxb而在點 、 處的梯度分別為：kx1kx11kkkkkkggg xxa

6、gd0tjkdgd 10tjkkdg gg得出共軛方向與梯度之間的關(guān)系。此式表明沿方向kd進行一維搜索，其終點 與始點 的梯度值差1kxkx1kkgg與 的共軛方向 正交。kdjd若dj和dk對g是共軛的，則 圖4-9 共軛梯度法的幾何說明3.4.6 變尺度法1kkkkxxhf x變尺度法的基本思想：前面討論的梯度法和牛頓法，它們的迭代公式可以看作下列公式的特例。變尺度法是對牛頓法的修正，它不是計算二階導數(shù)的矩陣和它的逆矩陣，而是設法構(gòu)造一個對稱正定矩陣h來代替hessian矩陣的逆矩陣。并在迭代過程中，使其逐漸逼近h-1 。由于對稱矩陣h在迭代過程中是不斷修正改變的，它對于一般尺度的梯度起到

7、改變尺度的作用，因此h又稱變尺度矩陣。一、尺度矩陣的概念變量的尺度變換是放大或縮小各個坐標。通過尺度變換可以把函數(shù)的偏心程度降低到最低限度。對于一般二次函數(shù) 12ttf xx gxb xc如果進行尺度變換xqx則在新的坐標系中，函數(shù)的二次項變?yōu)?122tttx gxx q gqx選擇這樣變換的目的：降低二次項的偏心程度。若矩陣g是正定的，則總存在矩陣q使tq gqi使得函數(shù)偏心度變?yōu)榱恪Ｓ胵-1 右乘等式兩邊，得1tq gq再用q左乘等式兩邊，得tqq gi所以1tqqg說明二次函數(shù)矩陣g的逆矩陣，可以通過尺度變換矩陣q求得。這樣，牛頓法迭代過程中的牛頓方向可寫成：1kktkdgf xqqf

8、x 1kkktkxxqqf x三、變尺度法的一般步驟3.4.7 坐標輪換法坐標輪換法是每次搜索只允許一個變量變化，其余變量保持不變，即沿坐標方向輪流進行搜索的尋優(yōu)方法。它把多變量的優(yōu)化問題輪流地轉(zhuǎn)化成單變量的優(yōu)化問題。因此又稱變量輪換法變量輪換法。 其基本原理是將一個多維的無約束最優(yōu)化問題轉(zhuǎn)化為一系列較低維的最優(yōu)化問題來求解，簡單地說，就是先將(n-1)個變量固定不動，只對第一個變量進行一維搜索得到最優(yōu)點x1（1）。然后，又保持(n-1)個變量不變，再對第二個變量進行一維搜索到x2（1）等等。 坐標輪換法原理圖（坐標輪換法原理圖（動畫演示動畫演示）)0(2)0(1xx)0(2)1(1xx)1(

9、2)1(1xx)2(2)2(1xx2. 搜索方向與步長的確定（1）搜索方向的確定）搜索方向的確定對于第k輪第i次的計算1kkkkiiiixxa d第k輪第i次的迭代方向，它輪流取n維坐標的單位向量。0.1.0kiide 3.搜索步長的確定關(guān)于關(guān)于 值通常有以下幾種取法值通常有以下幾種取法（1）加速步長法）加速步長法（2）最優(yōu)步長法）最優(yōu)步長法 最優(yōu)步長法就是利用一維最優(yōu)搜索方法來完成最優(yōu)步長法就是利用一維最優(yōu)搜索方法來完成每一次迭代，即每一次迭代，即此時可以采用此時可以采用0.618方法或二次插值方法來計算方法或二次插值方法來計算 的值。的值。)( ki加速步長法的搜索路線圖圖414 最優(yōu)步長法的搜索路線最優(yōu)步長法的搜索路線4 . 坐標輪換法存在的問題圖圖415 坐標輪換法在各種不同情況下的效能坐標輪換法在各種不同情況下的效能（a）搜索有效；（）搜索有效；（b）搜索低效；（）搜索低效；（c）搜索無效）搜索無效3.4.8 powell法（方向加速法） powell法是利用共軛方向可以加速收斂的性質(zhì)所法是利用共軛