第四章無約束優化方法

§4-1最速下降法（梯度法）§4-2*牛頓類方法§4-3*變尺度法§4-4*共軛方向法

§4-5*鮑威爾方法§4-6其它方法（如坐標輪換法、單純形法）現在是1頁\一共有39頁\編輯于星期一

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

為什么要研究無約束優化問題?（1）有些實際問題，其數學模型本身就是一個無約束優化問題。（2）通過熟悉它的解法可以為研究約束優化問題打下良好的基礎。（3）約束優化問題的求解可以通過一系列無約束優化方法來達到。所以無約束優化問題的解法是優化設計方法的基本組成部分，也是優化方法的基礎。現在是2頁\一共有39頁\編輯于星期一（4）對于多維無約束問題來說，古典極值理論中令一階導數為零，但要求二階可微，且要判斷海賽矩陣為正定才能求得極小點，這種方法有理論意義，但無實用價值。和一維問題一樣，若多元函數F(X)不可微，亦無法求解。但古典極值理論是無約束優化方法發展的基礎?，F在是3頁\一共有39頁\編輯于星期一目前已研究出很多種無約束優化方法，它們的主要不同點在于構造搜索方向上的差別。（1）間接法——要使用導數，如梯度法、（阻尼）牛頓法、變尺度法、共軛梯度法等。（2）直接法——不使用導數信息，如坐標輪換法、鮑威爾法、單純形法等。無約束優化問題是：求n維設計變量使目標函數現在是4頁\一共有39頁\編輯于星期一搜索方向的構成問題乃是無約束優化方法的關鍵。用直接法尋找極小點時，不必求函數的導數，只要計算目標函數值。這類方法較適用于解決變量個數較少的（n≤20）問題，一般情況下比間接法效率低。間接法除要計算目標函數值外，還要計算目標函數的梯度，有的還要計算其海賽矩陣。現在是5頁\一共有39頁\編輯于星期一4-1梯度法

基本思想：函數的負梯度方向是函數值在該點下降最快的方向。將n維問題轉化為一系列沿負梯度方向用一維搜索方法尋優的問題，利用負梯度作為搜索方向，故稱最速下降法或梯度法。搜索方向s取該點的負梯度方向(最速下降方向)，使函數值在該點附近的范圍內下降最快?，F在是6頁\一共有39頁\編輯于星期一為了使目標函數值沿搜索方向能夠獲得最大的下降值，其步長因子應取一維搜索的最佳步長。即有

根據一元函數極值的必要條件和多元復合函數求導公式，得現在是7頁\一共有39頁\編輯于星期一在最速下降法中，相鄰兩個迭代點上的函數梯度相互垂直。而搜索方向就是負梯度方向，因此相鄰兩個搜索方向互相垂直。這就是說在迭代點向函數極小點靠近的過程，走的是曲折的路線。形成“之”字形的鋸齒現象，而且越接近極小點鋸齒越細。

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

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

第一次迭代設計點位置和函數值

繼續作下去，經10次迭代后，得到最優解

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

仍從

即

出發進行最速下降法尋優。此時：沿負梯度方向進行一維搜索：則函數f(X)變為：y1=x1,y2=5x2現在是15頁\一共有39頁\編輯于星期一β為一維搜索最佳步長，可由極值條件：由從而算得一步計算后設計點的位置及其目標函數：現在是16頁\一共有39頁\編輯于星期一經變換后，只需一次迭代，就可找到最優解。這是因為經過尺度變換：等值線由橢圓變成圓。現在是17頁\一共有39頁\編輯于星期一梯度法的特點（1）理論明確，程序簡單，對初始點要求不嚴格。（2）對一般函數而言，梯度法的收斂速度并不快，因為最速下降方向僅僅是指某點的一個局部性質。（3）梯度法相鄰兩次搜索方向的正交性，決定了迭代全過程的搜索路線呈鋸齒狀，在遠離極小點時逼近速度較快，而在接近極小點時逼近速度較慢。（4）梯度法的收斂速度與目標函數的性質密切相關。對于等值線(面)為同心圓（球）的目標函數，一次搜索即可達到極小點。現在是18頁\一共有39頁\編輯于星期一前面介紹的許多優化方法，除鮑威爾（Powell）法外，都需要計算目標函數的導數，而在實際工程的最優化問題中，目標函數的導數往往很難求出或者根本無法求出。下面所介紹的方法只需要計算目標函數值，無需求其導數，因此計算比較簡單，其幾何概念也比較清晰，屬于直接法的無約束最優化方法。這類方法適用于不知道目標函數的數學表達式而僅知其具體算法的情況。這也是直接法的一個優點?！?-6其它方法（如坐標輪換法、單純形法）現在是19頁\一共有39頁\編輯于星期一坐標輪換法

坐標輪換法的基本思想：是將一個n維優化問題轉化為依次沿n個坐標方向反復進行一維搜索問題。這種方法的實質是把n維問題的求優過程轉化為對每個變量逐次進行一維求優的循環過程。每次一維搜索時，只允許n個變量的一次改動，其余(n-1)個變量固定不變。故坐標輪換法也常稱單變量法或變量交錯法?，F在是20頁\一共有39頁\編輯于星期一坐標輪換法此法的效能在很大程度上取決于目標函數的性質?，F在是21頁\一共有39頁\編輯于星期一（1）計算量少，程序簡單，不需要求函數導數的直接探索目標函數最優解的方法；（2）探索路線較長，問題的維數愈多求解的效率愈低。當維數n＞10時，則不應采用此法。僅適用于n較少（n<10）的目標函數求優；

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

（3）若（2）；否則，轉（4）否則轉（6）否則，令（6）否則，，轉（2）（5）（4）轉（5）；現在是26頁\一共有39頁\編輯于星期一現在是27頁\一共有39頁\編輯于星期一單純形方法一、基本思想單純形替換法也是一種不使用導數的求解無約束極小化問題的直接搜索方法，與前面幾種方法不同的是，單純形替換法不是利用搜索方向從一個點迭代到另一個更優的點，而是從一個單純形迭代到另一個更優的單純形。現在是28頁\一共有39頁\編輯于星期一定義：單純形n維空間中的恰好有n+1個頂點（極點）的有界的凸多面體稱之為一個單純形。根據定義，可知，一維空間中的單純形是線段，二維空間中的單純形是三角形，而三維空間中的單純形則是四面體。在單純形替換算法中，從一個單純形到另一個單純形的迭代主要通過反射、擴張、收縮和縮邊這4個操作來實現。下面以二維問題為例來對4種操作進行說明（參見下圖）。現在是29頁\一共有39頁\編輯于星期一（1）反射——設除了最劣點X1以外的基余頂點的中心為X4，作X1關于點X4的對稱點X5，稱X5為X1的反射點。求反射點的過程稱之為反射。（2）擴張——在得到反射點X5之后，如果X5優于原單純形的最劣點（即有），表明反射方向（X5—X1）是有利方向，反射成功。若進一步有，可沿反射方向前進適當的距離到點X6。X6稱之為擴張點，求擴張點的過程稱之為擴張。擴張之后，若擴張點X6優于反射點X5，則擴張成功，以X6取代X1，得新單純形{X6,X2,X3}；否則，擴張失敗，舍棄擴張點，以反射X5點取代X1，得新單純形{X5,X2,X3}。設當前的單純形的頂點為X1，X2，X3，且有現在是30頁\一共有39頁\編輯于星期一如果出現。表示反射完全失敗，應退回到介于X4與X1之間的某個點X8。（3）收縮——在得到反射點X5之后，如果有表示反射部分成功，方向（X5—X1）雖然是有利方向，但X5前進過遠，應收縮到介于X4與X5之間的某個點X7。上述兩種從反射點向X1方向后退的過程都稱之為收縮。如果收縮點優于原來的最劣點X1，稱收縮成功，并以收縮點取代原最劣點，構成新單純形{X7,X2,X3}或{X8,X2,X3}；否則，稱之為收縮失敗，舍棄收縮點?，F在是31頁\一共有39頁\編輯于星期一（4）縮邊——若收縮失敗，則應壓縮當前單純形的邊長：令最優點X3不動，而其余頂點向X3方向壓縮，使邊長縮短（通常縮短一半），以產生新單純形。如下圖所示，點X1壓縮到點X9，點X2壓縮到點X10，得新單純形{X9,X10,X3}，這一過程稱之為縮邊?，F在是32頁\一共有39頁\編輯于星期一二、單純形替換算法設初始點為X0，初始邊長h，ei為坐標軸方向的單位向量，預定正數（2）比較各項點Xi的函數值，挑出其中的最優點，記為XL；最劣點，記XH；次差點，記為Xw；（3）求反射中心其中，a>0，通常取a=1；

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

——間接法總結1、梯度法方向負梯度用到一階導數適合于精度不高或用于復雜函數尋找一個好的初始點2、牛頓法用到一階導數和海色矩陣，具有二次收斂性要求海色矩陣奇異，且維數不宜太高3、共軛梯度法用到一階導數，具有二次收斂性4、變尺度法收斂快，效果好，被認為是目前最有效的無約束優化方法。適用于維數較高，具有一階偏導數的目標函數

現在是37頁\一共有39頁\編輯于星期一1、坐標輪換法計算效率較低適合維數較低，目標函數無導數或導數較難求得2、步長加速法同坐標輪換法