無約束優(yōu)化方法

無約束優(yōu)化方法第1頁/共69頁解析法(間接解法)數(shù)值法(直接解法)數(shù)學模型復雜時不便求解可以處理復雜函數(shù)及沒有數(shù)學表達式的優(yōu)化設(shè)計問題搜索方向問題是無約束優(yōu)化方法的關(guān)鍵。各種無約束優(yōu)化方法的區(qū)別：確定搜索方向的方法不同。無約束優(yōu)化方法分類利用目標函數(shù)的一階或二階導數(shù)利用目標函數(shù)值（最速下降法、共軛梯度法、牛頓法）（坐標輪換法、鮑威爾法等）第2頁/共69頁第3頁/共69頁第二節(jié)最速下降法優(yōu)化設(shè)計追求目標函數(shù)值最小，若搜索方向取該點的負梯度方向，使函數(shù)值在該點附近的范圍內(nèi)下降最快。按此規(guī)律不斷走步，形成以下迭代算法：以負梯度方向為搜索方向，所以稱最速下降法或梯度法。搜索方向確定為負梯度方向，還需確定步長因子即求一維搜索的最佳步長，既有第4頁/共69頁由此可知，在最速下降法中，相鄰兩個迭代點上的函數(shù)梯度相互垂直。而搜索方向就是負梯度方向，因此相鄰兩個搜索方向互相垂直。第5頁/共69頁第6頁/共69頁例4-1求目標函數(shù)的極小點。第7頁/共69頁第8頁/共69頁作業(yè)第四章習題4-3設(shè)目標函數(shù)為，試用最速下降法求其最優(yōu)解。第9頁/共69頁第三節(jié)牛頓型方法在第三章中，我們已經(jīng)討論了一維搜索的牛頓方法。得出一維情況下的牛頓迭代公式第10頁/共69頁第三節(jié)牛頓型方法對于多元函數(shù)，在泰勒展開，得設(shè)為函數(shù)的極小點，根據(jù)極值的必要條件這就是多元函數(shù)求極值的牛頓法迭代公式。第11頁/共69頁4.3.2阻尼牛頓法牛頓法的缺陷是，在確定極值點的過程中，并不含有沿下降方向搜索的概念。因此對于非二次型函數(shù)，在迭代過程中，可能出現(xiàn)的現(xiàn)象。為此人們提出了所謂的阻尼牛頓法。第12頁/共69頁作為一個搜索方向，則阻尼牛頓法采用下述迭代公式:是沿牛頓方向進行一維搜索的最佳步長,稱為阻尼因子。。其中令通過下式求得這樣就能保證第13頁/共69頁阻尼牛頓法程序框圖第14頁/共69頁以上介紹的最速下降法及牛頓法或者阻尼牛頓法，屬于經(jīng)典的數(shù)學方法。

顯然在這些方法中要用到某點函數(shù)的一階梯度，二階梯度等信息，同時對牛頓法還要用到逆矩陣的計算等。當變量維數(shù)較高時，計算工作量相當大，影響計算速度。

理論上，牛頓法的收斂速度高于最速下降法。從以上二種經(jīng)典方法中，人們不斷努力，發(fā)掘，提出了不同的改進方法。第15頁/共69頁第四節(jié)共軛方向及共軛方向法為了克服最速下降法的鋸齒現(xiàn)象，提高收斂速度，發(fā)展了一類共軛方向法。搜索方向是共軛方向。一、共軛方向的概念共軛方向的概念是在研究二次函數(shù)時引出的。首先考慮二維情況第16頁/共69頁1共軛方向定義1：設(shè)G為

階實對稱正定矩陣，而

為在n維歐氏空間中的兩個非零向量，如果滿足式：

則稱向量

關(guān)于實對稱正定矩陣G是共軛的，或簡稱

與

關(guān)于G共軛第17頁/共69頁第18頁/共69頁第19頁/共69頁第20頁/共69頁如果按最速下降法，選擇負梯度方向為搜索方向，會產(chǎn)生鋸齒現(xiàn)象。為避免鋸齒的發(fā)生，取下一次的迭代搜索方向直接指向極小點，如果選定這樣的搜索方向，對于二元二次函數(shù)只需進行兩次直線搜索就可以求到極小點。第21頁/共69頁應滿足什么條件？對于二次函數(shù)在處取得極小點的必要條件等式兩邊同乘得是對G的共軛方向。第22頁/共69頁三、共軛方向法1、選定初始點，下降方向和收斂精度ε，k=0。2、沿方向進行一維搜索，得3、判斷是否滿足，若滿足則打印否則轉(zhuǎn)4。4、提供新的共軛方向，使5、置，轉(zhuǎn)2。第23頁/共69頁第24頁/共69頁共軛方向法程序框圖第25頁/共69頁第五節(jié)共軛梯度法共軛梯度法是共軛方向法的一種，共軛向量有迭代點的負梯度構(gòu)造出來，所以稱共軛梯度法。從點出發(fā)，沿G某一共軛方向作一維搜索,到達而在點、處的梯度分別為：第26頁/共69頁得出共軛方向與梯度之間的關(guān)系。此式表明沿方向進行一維搜索，其終點與始點的梯度值差與的共軛方向正交。第27頁/共69頁圖4-9共軛梯度法的幾何說明第28頁/共69頁第29頁/共69頁第六節(jié)坐標輪換法坐標輪換法是每次搜索只允許一個變量變化，其余變量保持不變，即沿坐標軸方向輪流進行搜索的尋優(yōu)方法。它把多變量的優(yōu)化問題輪流地轉(zhuǎn)化成單變量的優(yōu)化問題。因此又稱變量輪換法。

其基本原理是將一個多維的無約束最優(yōu)化問題轉(zhuǎn)化為一系列較低維的最優(yōu)化問題來求解，簡單地說，就是先將(n-1)個變量固定不動，只對第一個變量進行一維搜索得到最優(yōu)點x1（1）。然后，又保持(n-1)個變量不變，再對第二個變量進行一維搜索到x2（1）等等。第30頁/共69頁4.6.1坐標輪換法的搜索過程及方向向量取法下面以二元函數(shù)為例

第31頁/共69頁第32頁/共69頁2.搜索方向與步長的確定（1）搜索方向的確定對于第k輪第i次的計算第k輪第I次的迭代方向，它輪流取n維坐標的單位向量。第33頁/共69頁3.搜索步長的確定關(guān)于值通常有以下幾種取法（1）加速步長法（2）最優(yōu)步長法最優(yōu)步長法就是利用一維最優(yōu)搜索方法來完成每一次迭代，即此時可以采用0.618方法或二次插值方法來計算的值。第34頁/共69頁圖4-9坐標輪換法的程序框圖第35頁/共69頁4.坐標輪換法存在的問題圖4－15坐標輪換法在各種不同情況下的效能（a）搜索有效；（b）搜索低效；（c）搜索無效第36頁/共69頁第七節(jié)鮑威爾法Powell一、共軛方向的生成直接利用函數(shù)值來構(gòu)造共軛方向的一種共軛方向法?；舅枷耄涸诓挥们髮?shù)的前提下，在迭代中逐次構(gòu)造Hessian矩陣G的共軛方向。第37頁/共69頁第38頁/共69頁第39頁/共69頁第40頁/共69頁4.7.2鮑威爾法的基本算法第41頁/共69頁二、基本算法第42頁/共69頁三、改進的算法在鮑維爾基本算法中，每一輪迭代都用連結(jié)始點和終點所產(chǎn)生出的搜索方向去替換原來向量組中的第一個向量，而不管它的“好壞”。改進的算法是：首先判斷原向量組是否需要替換。如需要替換，在產(chǎn)生新的向量。第43頁/共69頁第44頁/共69頁單純形法:通過計算單純形頂點的函數(shù)值并加以比較，找到一個較好的點組成新的單純形。不斷地向極小點靠近。屬于直接尋優(yōu)方法類，僅需要目標函數(shù)值信息。第八節(jié)單純形法第45頁/共69頁4.8.1單純形法基本原理單純形是指在n維空間中具有n+1個頂點的多面體。以二元函數(shù)為例

設(shè)，最好點，最差點，

次壞點

點稱作點的相對于點的反射點

第46頁/共69頁第47頁/共69頁第48頁/共69頁以上說明，可以通過反射、擴張、收縮、縮邊方式得到一個新的單純型，其中至少有一個頂點的函數(shù)值比原單純形要小。單純形法的計算步驟以二元函數(shù)為例

以二元函數(shù)為例第49頁/共69頁第50頁/共69頁第51頁/共69頁第52頁/共69頁第53頁/共69頁第九節(jié)變尺度法變尺度法的基本思想：前面討論的梯度法和牛頓法，它們的迭代公式可以看作下列公式的特例。變尺度法是對牛頓法的修正，它不是計算二階導數(shù)的矩陣和它的逆矩陣，而是設(shè)法構(gòu)造一個對稱正定矩陣H來代替Hesse矩陣的逆矩陣。并在迭代過程中，使其逐漸逼近H-1

。由于對稱矩陣H在迭代過程中是不斷修正改變的，它對于一般尺度的梯度起到改變尺度的作用，因此H又稱變尺度矩陣。第54頁/共69頁一、尺度矩陣的概念變量的尺度變換是放大或縮小各個坐標。通過尺度變換可以把函數(shù)的偏心程度降低到最低限度。對于一般二次函數(shù)如果進行尺度變換第55頁/共69頁則在新的坐標系中，函數(shù)的二次項變?yōu)檫x擇這樣變換的目的：降低二次項的偏心程度。若矩陣G是正定的，則總存在矩陣Q使使得函數(shù)偏心度變?yōu)榱?。用Q-1

右乘等式兩邊，得再用Q左乘等式兩邊，得所以第56頁/共69頁說明二次函數(shù)矩陣G的逆矩陣，可以通過尺度變換矩陣Q求得。這樣，牛頓法迭代過程中的牛頓方向可寫成：三、變尺度法的一般步驟第57頁/共69頁第58頁/共69頁解析法(間接解法)數(shù)值法(直接解法)數(shù)學模型復雜時不便求解可以處理復雜函數(shù)及沒有數(shù)學表達式的優(yōu)化設(shè)計問題搜索方向問題是無約束優(yōu)化方法的關(guān)鍵。各種無約束優(yōu)化方法的區(qū)別：確定搜索方向的方法不同。無約束優(yōu)化方法分類利用目標函數(shù)的一階或二階導數(shù)利