機械優(yōu)化設(shè)計無約束優(yōu)化方法

機械優(yōu)化設(shè)計無約束優(yōu)化方法演示文稿現(xiàn)在是1頁\一共有38頁\編輯于星期一（優(yōu)選）機械優(yōu)化設(shè)計無約束優(yōu)化方法現(xiàn)在是2頁\一共有38頁\編輯于星期一

第1章所列舉的機械優(yōu)化設(shè)計問題，都是在一定的限制條件下追求某一指標為最小，它們都屬于約束優(yōu)化問題。工程問題大都如此。

為什么要研究無約束優(yōu)化問題?

（1）有些實際問題，其數(shù)學(xué)模型本身就是一個無約束優(yōu)化問題。（2）通過熟悉它的解法可以為研究約束優(yōu)化問題打下良好的基礎(chǔ)。（3）約束優(yōu)化問題的求解可以通過一系列無約束優(yōu)化方法來達到。所以無約束優(yōu)化問題的解法是優(yōu)化設(shè)計方法的基本組成部分，也是優(yōu)化方法的基礎(chǔ)?，F(xiàn)在是3頁\一共有38頁\編輯于星期一

（4）對于多維無約束問題來說，古典極值理論中令一階導(dǎo)數(shù)為零，但要求二階可微，且要判斷海賽矩陣為正定才能求得極小點，這種方法有理論意義，但無實用價值。和一維問題一樣，若多元函數(shù)F(X)不可微，亦無法求解。但古典極值理論是無約束優(yōu)化方法發(fā)展的基礎(chǔ)。現(xiàn)在是4頁\一共有38頁\編輯于星期一

目前已研究出很多種無約束優(yōu)化方法，它們的主要不同點在于構(gòu)造搜索方向上的差別。（1）間接法——要使用導(dǎo)數(shù)，如梯度法、（阻尼）牛頓法、變尺度法、共軛梯度法等。（2）直接法——不使用導(dǎo)數(shù)信息，如坐標輪換法、鮑威爾法、單純形法等。無約束優(yōu)化問題是：求n維設(shè)計變量使目標函數(shù)現(xiàn)在是5頁\一共有38頁\編輯于星期一搜索方向的構(gòu)成問題乃是無約束優(yōu)化方法的關(guān)鍵。

用直接法尋找極小點時，不必求函數(shù)的導(dǎo)數(shù)，只要計算目標函數(shù)值。這類方法較適用于解決變量個數(shù)較少的（n≤20）問題，一般情況下比間接法效率低。間接法除要計算目標函數(shù)值外，還要計算目標函數(shù)的梯度，有的還要計算其海賽矩陣?，F(xiàn)在是6頁\一共有38頁\編輯于星期一4-1梯度法

基本思想：函數(shù)的負梯度方向是函數(shù)值在該點下降最快的方向。將n維問題轉(zhuǎn)化為一系列沿負梯度方向用一維搜索方法尋優(yōu)的問題，利用負梯度作為搜索方向，故稱最速下降法或梯度法。

搜索方向s取該點的負梯度方向(最速下降方向)，使函數(shù)值在該點附近的范圍內(nèi)下降最快?，F(xiàn)在是7頁\一共有38頁\編輯于星期一

為了使目標函數(shù)值沿搜索方向能夠獲得最大的下降值，其步長因子應(yīng)取一維搜索的最佳步長。即有

根據(jù)一元函數(shù)極值的必要條件和多元復(fù)合函數(shù)求導(dǎo)公式，得現(xiàn)在是8頁\一共有38頁\編輯于星期一

在最速下降法中，相鄰兩個迭代點上的函數(shù)梯度相互垂直。而搜索方向就是負梯度方向，因此相鄰兩個搜索方向互相垂直。這就是說在迭代點向函數(shù)極小點靠近的過程，走的是曲折的路線。形成“之”字形的鋸齒現(xiàn)象，而且越接近極小點鋸齒越細。

圖4-2最速下降法的搜索路徑現(xiàn)在是9頁\一共有38頁\編輯于星期一現(xiàn)在是10頁\一共有38頁\編輯于星期一方法特點（1）初始點可任選，每次迭代計算量小，存儲量少，程序簡短。即使從一個不好的初始點出發(fā)，開始的幾步迭代，目標函數(shù)值下降很快，然后慢慢逼近局部極小點。（2）任意相鄰兩點的搜索方向是正交的，它的迭代路徑為繞道逼近極小點。當?shù)c接近極小點時，步長變得很小，越走越慢?，F(xiàn)在是11頁\一共有38頁\編輯于星期一sk現(xiàn)在是12頁\一共有38頁\編輯于星期一沿負梯度方向進行一維搜索，有為一維搜索最佳步長，應(yīng)滿足極值必要條件

例4－1求目標函數(shù)的極小點。解取初始點則初始點處函數(shù)值及梯度分別為現(xiàn)在是13頁\一共有38頁\編輯于星期一算出一維搜索最佳步長

第一次迭代設(shè)計點位置和函數(shù)值

繼續(xù)作下去，經(jīng)10次迭代后，得到最優(yōu)解

現(xiàn)在是14頁\一共有38頁\編輯于星期一

這個問題的目標函數(shù)的等值線為一簇橢圓,迭代點從走的是一段鋸齒形路線，見圖4-3。11圖4-3現(xiàn)在是15頁\一共有38頁\編輯于星期一將上例中目標函數(shù)引入變換其等值線由橢圓變成一簇同心圓。

仍從

即

出發(fā)進行最速下降法尋優(yōu)。此時：沿負梯度方向進行一維搜索：則函數(shù)f(X)變?yōu)椋簓1=x1,y2=5x2現(xiàn)在是16頁\一共有38頁\編輯于星期一β為一維搜索最佳步長，可由極值條件：由從而算得一步計算后設(shè)計點的位置及其目標函數(shù)：現(xiàn)在是17頁\一共有38頁\編輯于星期一經(jīng)變換后，只需一次迭代，就可找到最優(yōu)解。這是因為經(jīng)過尺度變換：等值線由橢圓變成圓。現(xiàn)在是18頁\一共有38頁\編輯于星期一梯度法的特點（1）理論明確，程序簡單，對初始點要求不嚴格。（2）對一般函數(shù)而言，梯度法的收斂速度并不快，因為最速下降方向僅僅是指某點的一個局部性質(zhì)。（3）梯度法相鄰兩次搜索方向的正交性，決定了迭代全過程的搜索路線呈鋸齒狀，在遠離極小點時逼近速度較快，而在接近極小點時逼近速度較慢。（4）梯度法的收斂速度與目標函數(shù)的性質(zhì)密切相關(guān)。對于等值線(面)為同心圓（球）的目標函數(shù)，一次搜索即可達到極小點?，F(xiàn)在是19頁\一共有38頁\編輯于星期一

前面介紹的許多優(yōu)化方法，除鮑威爾（Powell）法外，都需要計算目標函數(shù)的導(dǎo)數(shù)，而在實際工程的最優(yōu)化問題中，目標函數(shù)的導(dǎo)數(shù)往往很難求出或者根本無法求出。下面所介紹的方法只需要計算目標函數(shù)值，無需求其導(dǎo)數(shù)，因此計算比較簡單，其幾何概念也比較清晰，屬于直接法的無約束最優(yōu)化方法。這類方法適用于不知道目標函數(shù)的數(shù)學(xué)表達式而僅知其具體算法的情況。這也是直接法的一個優(yōu)點?！?-6其它方法（如坐標輪換法、單純形法）現(xiàn)在是20頁\一共有38頁\編輯于星期一坐標輪換法

坐標輪換法的基本思想：是將一個n維優(yōu)化問題轉(zhuǎn)化為依次沿n個坐標方向反復(fù)進行一維搜索問題。這種方法的實質(zhì)是把n維問題的求優(yōu)過程轉(zhuǎn)化為對每個變量逐次進行一維求優(yōu)的循環(huán)過程。每次一維搜索時，只允許n個變量的一次改動，其余(n-1)個變量固定不變。故坐標輪換法也常稱單變量法或變量交錯法。現(xiàn)在是21頁\一共有38頁\編輯于星期一坐標輪換法

此法的效能在很大程度上取決于目標函數(shù)的性質(zhì)?，F(xiàn)在是22頁\一共有38頁\編輯于星期一（1）計算量少，程序簡單，不需要求函數(shù)導(dǎo)數(shù)的直接探索目標函數(shù)最優(yōu)解的方法；（2）探索路線較長，問題的維數(shù)愈多求解的效率愈低。當維數(shù)n＞10時，則不應(yīng)采用此法。僅適用于n較少（n<10）的目標函數(shù)求優(yōu)；

（3）改變初始點重新迭代，可避免出現(xiàn)病態(tài)。方法特點現(xiàn)在是23頁\一共有38頁\編輯于星期一現(xiàn)在是24頁\一共有38頁\編輯于星期一步長加速法（Hook-Reeves算法）一、步長加速法原理步長加速法也稱之為離散步長的Hook-Reeves算法，是一種不使用導(dǎo)數(shù)的直接搜索算法，其算法過程可分成兩個基本階段：坐標循環(huán)試探及模矢加速搜索。見下圖，從初始探點Y0出發(fā)，依次沿n個坐標方向用固定步長△進行試探，尋找更好的點。而模矢加速搜索，就是沿模矢方向加大步長前進，以得到第k+1次迭代的出發(fā)點Y0，這樣就完成了一次迭代，然后再從新的Y0出發(fā)，進行下一輪坐標循環(huán)試探，如此重復(fù)進行，使目標值不斷減小?，F(xiàn)在是25頁\一共有38頁\編輯于星期一二、步長加速法算法設(shè)問題為X0為初始點，個坐標軸的單位方向向量，初始坐標循環(huán)試探的步長為△>0，模矢加速搜索的加速步長因子為a>1（通常取a=2），迭代終止準則為(為預(yù)先確定的正數(shù)）。現(xiàn)在是26頁\一共有38頁\編輯于星期一（1）（2）

（3）若（2）；否則，轉(zhuǎn)（4）否則轉(zhuǎn)（6）否則，令（6）否則，，轉(zhuǎn)（2）（5）（4）轉(zhuǎn)（5）；現(xiàn)在是27頁\一共有38頁\編輯于星期一現(xiàn)在是28頁\一共有38頁\編輯于星期一單純形方法一、基本思想單純形替換法也是一種不使用導(dǎo)數(shù)的求解無約束極小化問題的直接搜索方法，與前面幾種方法不同的是，單純形替換法不是利用搜索方向從一個點迭代到另一個更優(yōu)的點，而是從一個單純形迭代到另一個更優(yōu)的單純形?，F(xiàn)在是29頁\一共有38頁\編輯于星期一定義：單純形

n維空間中的恰好有n+1個頂點（極點）的有界的凸多面體稱之為一個單純形。根據(jù)定義，可知，一維空間中的單純形是線段，二維空間中的單純形是三角形，而三維空間中的單純形則是四面體。在單純形替換算法中，從一個單純形到另一個單純形的迭代主要通過反射、擴張、收縮和縮邊這4個操作來實現(xiàn)。下面以二維問題為例來對4種操作進行說明（參見下圖）?，F(xiàn)在是30頁\一共有38頁\編輯于星期一（1）反射——設(shè)除了最劣點X1以外的基余頂點的中心為X4，作X1關(guān)于點X4的對稱點X5，稱X5為X1的反射點。求反射點的過程稱之為反射。（2）擴張——在得到反射點X5之后，如果X5優(yōu)于原單純形的最劣點（即有），表明反射方向（X5—X1）是有利方向，反射成功。若進一步有，可沿反射方向前進適當?shù)木嚯x到點X6。X6稱之為擴張點，求擴張點的過程稱之為擴張。擴張之后，若擴張點X6優(yōu)于反射點X5，則擴張成功，以X6取代X1，得新單純形{X6,X2,X3}；否則，擴張失敗，舍棄擴張點，以反射X5點取代X1，得新單純形{X5,X2,X3}。設(shè)當前的單純形的頂點為X1，X2，X3，且有現(xiàn)在是31頁\一共有38頁\編輯于星期一如果出現(xiàn)。表示反射完全失敗，應(yīng)退回到介于X4與X1之間的某個點X8。（3）收縮——在得到反射點X5之后，如果有表示反射部分成功，方向（X5—X1）雖然是有利方向，但X5前進過遠，應(yīng)收縮到介于X4與X5之間的某個點X7。

上述兩種從反射點向X1方向后退的過程都稱之為收縮。如果收縮點優(yōu)于原來的最劣點X1，稱收縮成功，并以收縮點取代原最劣點，構(gòu)成新單純形{X7,X2,X3}或{X8,X2,X3}；否則，稱之為收縮失敗，舍棄收縮點?，F(xiàn)在是32頁\一共有38頁\編輯于星期一（4）縮邊——若收縮失敗，則應(yīng)壓縮當前單純形的邊長：令最優(yōu)點X3不動，而其余頂點向X3方向壓縮，使邊長縮短（通?？s短一半），以產(chǎn)生新單純形。如下圖所示，點X1壓縮到點X9，點X2壓縮到點X10，得新單純形{X9,X10,X3}，這一過程稱之為縮邊?，F(xiàn)在是33頁\一共有38頁\編輯于星期一二、單純形替換算法設(shè)初始點為X0，初始邊長h，ei為坐標軸方向的單位向量，預(yù)定正數(shù)（2）比較各項點Xi的函數(shù)值，挑出其中的最優(yōu)點，記為XL；最劣點，記XH；次差點，記為Xw；（3）求反射中心其中，a>0，通常取a=1；

（1）令；輸出XL，為原問題近似極小點；否則，轉(zhuǎn)（2）。構(gòu)造新單純形；（4）根據(jù)不同情況，分別進行擴張，收縮或縮邊，其中收縮因子（5）如果滿足現(xiàn)在是34頁\一共有38頁\編輯于星期一現(xiàn)在是35頁\一共有38頁\編輯于星期一現(xiàn)在是36頁\一共有38頁\編輯于星期一表1無約束優(yōu)化方法搜索方向之間的相互聯(lián)系——間接法搜索方向函數(shù)梯度的修正因子所用目標函數(shù)信息梯度法I（單位陣）一階導(dǎo)數(shù)（阻尼）牛頓法二階導(dǎo)數(shù)共軛梯度法一階導(dǎo)數(shù)變尺度法一階導(dǎo)數(shù)，使（