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)化方法的基礎(chǔ)。無(wú)約束優(yōu)化問(wèn)題的極值條件解析法(間接解法)數(shù)值法(直接解法)數(shù)學(xué)模型復(fù)雜時(shí)不便求解可以處理復(fù)雜函數(shù)及沒有數(shù)學(xué)表達(dá)式的優(yōu)化設(shè)計(jì)問(wèn)題搜索方向問(wèn)題是無(wú)約束優(yōu)化方法的關(guān)鍵。各種無(wú)約束優(yōu)化方法的區(qū)別：確定搜索方向的方法不同。無(wú)約束優(yōu)化方法分類利用目標(biāo)函數(shù)的一階或二階導(dǎo)數(shù)利用目標(biāo)函數(shù)值（最速下降法、共軛梯度法、牛頓法）（坐標(biāo)輪換法、鮑威爾法等）第二節(jié) 最速下降法優(yōu)化設(shè)計(jì)追求目標(biāo)函數(shù)值最小

2、，若搜索方向取該點(diǎn)的負(fù)梯度方向，使函數(shù)值在該點(diǎn)附近的范圍內(nèi)下降最快。按此規(guī)律不斷走步，形成以下迭代算法：以負(fù)梯度方向?yàn)樗阉鞣较?，所以稱最速下降法或梯度法。搜索方向確定為負(fù)梯度方向，還需確定步長(zhǎng)因子即求一維搜索的最佳步長(zhǎng)，既有例4-1 求目標(biāo)函數(shù)的極小點(diǎn)。作業(yè)第四章 習(xí)題4-3設(shè)目標(biāo)函數(shù)為 ，試用最速下降法求其最優(yōu)解。第三節(jié)牛頓型方法在第三章中，我們已經(jīng)討論了一維搜索的牛頓方法。得出一維情況下的牛頓迭代公式第三節(jié)牛頓型方法對(duì)于多元函數(shù)，在泰勒展開，得設(shè)為函數(shù)的極小點(diǎn)，根據(jù)極值的必要條件這就是多元函數(shù)求極值的牛頓法迭代公式。4.3.2 阻尼牛頓法牛頓法的缺陷是，在確定極值點(diǎn)的過(guò)程中，并不含有沿下降

3、方向搜索的概念。因此對(duì)于非二次型函數(shù)，在迭代過(guò)程中，可能出現(xiàn)的現(xiàn)象。為此人們提出了所謂的阻尼牛頓法。作為一個(gè)搜索方向，則阻尼牛頓法采用下述迭代公式:是沿牛頓方向進(jìn)行一維搜索的最佳步長(zhǎng),稱為阻尼因子。其中令通過(guò)下式求得這樣就能保證阻尼牛頓法程序框圖第四節(jié)共軛方向及共軛方向法為了克服最速下降法的鋸齒現(xiàn)象，提高收斂速度，發(fā)展了一類共軛方向法。搜索方向是共軛方向。一、共軛方向的概念共軛方向的概念是在研究二次函數(shù)時(shí)引出的。首先考慮二維情況1 共軛方向定義1：設(shè)G為 階實(shí)對(duì)稱正定矩陣，而 為在n維歐氏空間中的兩個(gè)非零向量，如果滿足式： 則稱向量 關(guān)于實(shí)對(duì)稱正定矩陣G 是共軛的，或簡(jiǎn)稱 與 關(guān)于G 共軛如果

4、按最速下降法，選擇負(fù)梯度方向?yàn)樗阉鞣较颍瑫?huì)產(chǎn)生鋸齒現(xiàn)象。為避免鋸齒的發(fā)生，取下一次的迭代搜索方向直接指向極小點(diǎn)，如果選定這樣的搜索方向，對(duì)于二元二次函數(shù)只需進(jìn)行兩次直線搜索就可以求到極小點(diǎn)。應(yīng)滿足什么條件？對(duì)于二次函數(shù) 在 處取得極小點(diǎn)的必要條件等式兩邊同乘 得是對(duì)G的共軛方向。三、共軛方向法1、選定初始點(diǎn) ，下降方向 和收斂精度，k=0。2、沿 方向進(jìn)行一維搜索，得3、判斷 是否滿足，若滿足則打印否則轉(zhuǎn)4。4、提供新的共軛方向 ，使 5、置 ，轉(zhuǎn)2。第五節(jié) 共軛梯度法共軛梯度法是共軛方向法的一種，共軛向量有迭代點(diǎn)的負(fù)梯度構(gòu)造出來(lái)，所以稱共軛梯度法。從點(diǎn) 出發(fā)，沿G某一共軛方向 作一維搜索,到

5、達(dá)而在點(diǎn) 、 處的梯度分別為：得出共軛方向與梯度之間的關(guān)系。此式表明沿方向進(jìn)行一維搜索，其終點(diǎn) 與始點(diǎn) 的梯度值差與 的共軛方向 正交。第六節(jié) 坐標(biāo)輪換法坐標(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ō)，就是先將(n-1)個(gè)變量固定不動(dòng)，只對(duì)第一個(gè)變量進(jìn)行一維搜索得到最優(yōu)點(diǎn)x1（1）。然后，又保持(n-1)個(gè)變量不變，再對(duì)第二個(gè)變量進(jìn)行一維搜索到x2（1）等等。 4.6.1 坐標(biāo)輪換法的搜索

6、過(guò)程及方向向量取法下面以二元函數(shù)為例 2. 搜索方向與步長(zhǎng)的確定（1）搜索方向的確定對(duì)于第k輪第i次的計(jì)算第k輪第I次的迭代方向，它輪流取n維坐標(biāo)的單位向量。3.搜索步長(zhǎng)的確定關(guān)于 值通常有以下幾種取法（1）加速步長(zhǎng)法（2）最優(yōu)步長(zhǎng)法 最優(yōu)步長(zhǎng)法就是利用一維最優(yōu)搜索方法來(lái)完成每一次迭代，即此時(shí)可以采用0.618方法或二次插值方法來(lái)計(jì)算 的值。圖4-9 坐標(biāo)輪換法的程序框圖4 . 坐標(biāo)輪換法存在的問(wèn)題圖415 坐標(biāo)輪換法在各種不同情況下的效能（a）搜索有效；（b）搜索低效；（c）搜索無(wú)效第七節(jié) 鮑威爾法Powell一、共軛方向的生成直接利用函數(shù)值來(lái)構(gòu)造共軛方向的一種共軛方向法?；舅枷耄涸诓挥们?/p>

7、導(dǎo)數(shù)的前提下，在迭代中逐次構(gòu)造Hessian 矩陣G的共軛方向。4.7.2 鮑威爾法的基本算法二、基本算法三、改進(jìn)的算法在鮑維爾基本算法中，每一輪迭代都用連結(jié)始點(diǎn)和終點(diǎn)所產(chǎn)生出的搜索方向去替換原來(lái)向量組中的第一個(gè)向量，而不管它的“好壞”。改進(jìn)的算法是：首先判斷原向量組是否需要替換。如需要替換，在產(chǎn)生新的向量。單純形法:通過(guò)計(jì)算單純形頂點(diǎn)的函數(shù)值并加以比較，找到一個(gè)較好的點(diǎn)組成新的單純形。不斷地向極小點(diǎn)靠近。屬于直接尋優(yōu)方法類，僅需要目標(biāo)函數(shù)值信息。第八節(jié) 單純形法4.8.1單純形法基本原理單純形是指在n維空間中具有n+1個(gè)頂點(diǎn)的多面體。 以二元函數(shù)為例 設(shè)，最好點(diǎn)，最差點(diǎn)， 次壞點(diǎn) 點(diǎn)稱作點(diǎn)的

8、相對(duì)于點(diǎn)的反射點(diǎn) 以上說(shuō)明，可以通過(guò)反射、擴(kuò)張、收縮、縮邊方式得到一個(gè)新的單純型，其中至少有一個(gè)頂點(diǎn)的函數(shù)值比原單純形要小。單純形法的計(jì)算步驟以二元函數(shù)為例 以二元函數(shù) 為例第九節(jié)變尺度法變尺度法的基本思想：前面討論的梯度法和牛頓法，它們的迭代公式可以看作下列公式的特例。變尺度法是對(duì)牛頓法的修正，它不是計(jì)算二階導(dǎo)數(shù)的矩陣和它的逆矩陣，而是設(shè)法構(gòu)造一個(gè)對(duì)稱正定矩陣H來(lái)代替Hesse矩陣的逆矩陣。并在迭代過(guò)程中，使其逐漸逼近H-1 。由于對(duì)稱矩陣H在迭代過(guò)程中是不斷修正改變的，它對(duì)于一般尺度的梯度起到改變尺度的作用，因此H又稱變尺度矩陣。一、尺度矩陣的概念變量的尺度變換是放大或縮小各個(gè)坐標(biāo)。通過(guò)尺度變換可以把函數(shù)的偏心程度降低到最低限度。對(duì)于一般二次函數(shù)如果進(jìn)行尺度變換則在新的坐標(biāo)系中，函數(shù)的二次項(xiàng)變?yōu)檫x擇這樣變換的目的：降低二次項(xiàng)的偏心程度。若矩陣G是正定的，則總存在矩陣Q使使得函數(shù)偏心度變?yōu)榱?。用Q-1 右乘等式兩邊，得再用Q左乘等式兩邊，得所以說(shuō)明二次函數(shù)矩陣G的逆矩陣，可以通過(guò)尺度變換矩陣Q求得。這樣，牛頓法迭代過(guò)程中的牛頓方向可寫成：三、變尺度法的一般步驟解析法(間接解法)數(shù)值法(直接解法)數(shù)學(xué)模型復(fù)雜時(shí)