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

無約束優(yōu)化方法第1頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法，

（4）對于多維無約束問題來說，古典極值理論中令一階導(dǎo)數(shù)為零，但要求二階可微，且要判斷海賽矩陣為正定才能求得極小點，這種方法有理論意義，但無實用價值。和一維問題一樣，若多元函數(shù)F(X)不可微，亦無法求解。但古典極值理論是無約束優(yōu)化方法發(fā)展的基礎(chǔ)。第2頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第一節(jié)概述，

對于無約束優(yōu)化問題的求解，可以直接應(yīng)用第二章的極值條件來確定極值點位置。這就是把求函數(shù)極值的問題變成求解方程無約束優(yōu)化問題是：求n維設(shè)計變量使目標函數(shù)

這是一個含有n個未知量，n個方程的方程組，并且一般是非線性的。對于非線性方程組，一般是很難用解析方法求解的，需要采用數(shù)值計算方法逐步求出非線性聯(lián)立方程組的解。第3頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第一節(jié)概述，數(shù)值解法：是從給定的初始點x0出發(fā)，沿某一搜索方向d0進行搜索。確定最佳步長α，使函數(shù)值沿d0方向下降最大。依此方式按下述公式不斷進行，形成迭代的下降算法。1）選擇迭代方向即探索方向；2）在確定的方向上選擇適當步長邁步進行探索。

各種無約束優(yōu)化方法的區(qū)別就在于確定其搜索方向dk的方法不同。所以搜索方向的構(gòu)成問題是無約束優(yōu)化方法的關(guān)鍵。第4頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第一節(jié)概述，第5頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第一節(jié)概述，無約束優(yōu)化方法可以分成兩類：一類是利用目標函數(shù)的一階或二階導(dǎo)數(shù)的無約束優(yōu)化方法（如最速下降法、共軛梯度法、牛頓法及變尺度法）；另一類只利用目標函數(shù)的無約束優(yōu)化方法（如坐標輪換法、單形替換法及鮑威爾法等）。第6頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第二節(jié)最速下降法，最速下降法的迭代公式定義：最速下降法就是采用使目標函數(shù)值下降得最快的負梯度方向作為探索方向，來求目標函數(shù)的極小值的方法，又稱為梯度法。第7頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第二節(jié)最速下降法，

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

根據(jù)一元函數(shù)極值的必要條件和多元復(fù)合函數(shù)求導(dǎo)公式，得

第8頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第二節(jié)最速下降法，

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

圖4-2最速下降法的搜索路徑第9頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第二節(jié)最速下降法，最速下降法的迭代步驟：第10頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第二節(jié)最速下降法，第11頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法，沿負梯度方向進行一維搜索，有為一維搜索最佳步長，應(yīng)滿足極值必要條件

解取初始點則初始點處函數(shù)值及梯度分別為第12頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法，算出一維搜索最佳步長

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

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

第13頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法，

這個問題的目標函數(shù)的等值線為一簇橢圓,迭代點從走的是一段鋸齒形路線，見圖4-3。第14頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法，將上例中目標函數(shù)引入變換其等值線由橢圓變成一簇同心圓。

仍從即出發(fā)進行最速下降法尋優(yōu)。此時：沿負梯度方向進行一維搜索：則函數(shù)f(X)變?yōu)椋簓1=x1,y2=5x2第15頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法，β為一維搜索最佳步長，可由極值條件：由從而算得第一次走步后設(shè)計點的位置及其相應(yīng)的目標函數(shù)：第16頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法，經(jīng)變換后，只需一次迭代，就可找到最優(yōu)解。這是因為經(jīng)過尺度變換：等值線由橢圓變成圓。第17頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第二節(jié)最速下降法，最速下降法的特點：

1）對初始搜索點無嚴格要求；

2）收斂速度不快；

3）相鄰兩次迭代搜索方向互相垂直，在遠離極值點處收斂快，在靠近極值點處收斂慢；

4）收斂速度與目標函數(shù)值的性質(zhì)有關(guān)，對等值線是同心圓的目標函數(shù)來說，經(jīng)過一次迭代就可以達到極值點。第18頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第三節(jié)牛頓型法，牛頓型法的基本思想：利用二次曲線來逐點近似原目標函數(shù)，以二次曲線的極小點來近似原目標函數(shù)的極小點并逐漸逼近該點。

基本牛頓法的迭代公式：第19頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第三節(jié)牛頓型法，基本牛頓法的迭代公式：第20頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第三節(jié)牛頓型法，基本牛頓法的迭代公式：阻尼牛頓法的迭代公式：第21頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法

第三節(jié)牛頓型法，阻尼牛頓法的迭代步驟：第22頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第三節(jié)牛頓型法，阻尼牛頓法的迭代公式：第23頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第四節(jié)共軛方向及共軛方向法，

在下一次迭代時，選擇搜索方d1指向極小點x*，共軛方向以二元函數(shù)為例：我們?nèi)我膺x擇一個初始點x0點，沿著某個下降方向d0作一維搜索第24頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第四節(jié)共軛方向及共軛方向法，共軛方向正交第25頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第四節(jié)共軛方向及共軛方向法，共軛方向的性質(zhì)第26頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第四節(jié)共軛方向及共軛方向法，共軛方向法的步驟第27頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第四節(jié)共軛方向及共軛方向法，共軛方向的形成格拉姆-斯密特向量系共軛化的方法

n個線性無關(guān)的向量系vi（i=0,1，…，n-1）一組獨立向量dr（r=0,1，…，n-1）

第28頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第四節(jié)共軛方向及共軛方向法，第29頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第五節(jié)共軛梯度法，共軛梯度法：先沿最速下降方向(負梯度方向)探索第一步，然后沿與該負梯度方向相共軛的方向進行探索。第30頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第五節(jié)共軛梯度法，共軛方向與梯度之間的關(guān)系：

它表示沿著方向dk做一維搜索，它的終點xk+1與始點xk的梯度之差與dk的共軛方向dj正交。第31頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第五節(jié)共軛梯度法，共軛梯度法遞推公式：第32頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第五節(jié)共軛梯度法，共軛梯度法步驟：第33頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第五節(jié)共軛梯度法，共軛梯度法步驟：第34頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第五節(jié)共軛梯度法，共軛梯度法第35頁，共57頁，2023年，2月20日，星期五

設(shè)法構(gòu)造出一個對稱正定矩陣來代替，并在迭代過程中使逐漸逼近

,那么就簡化了牛頓法的計算，并且保持了牛頓法收斂快的優(yōu)點。第四章無約束優(yōu)化方法第六節(jié)變尺度法（擬牛頓法），變尺度法的基本思想：牛頓方向：變尺度法的迭代公式：尺度矩陣第36頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第六節(jié)變尺度法（擬牛頓法），尺度矩陣G正定牛頓迭代公式：目的：目標函數(shù)的偏心率減小到零。第37頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第六節(jié)變尺度法（擬牛頓法），變尺度矩陣的建立：變尺度法的迭代公式：搜索方向：尺度矩陣應(yīng)具備的條件：1）為正定對稱矩陣；2）具有簡單的迭代形式:3）滿足擬牛頓條件：令則第38頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第六節(jié)變尺度法（擬牛頓法），變尺度法的一般步驟：第39頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第六節(jié)變尺度法（擬牛頓法），變尺度法的流程圖：第40頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第六節(jié)變尺度法（擬牛頓法），DFP算法：DFP算法的校正公式第41頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第六節(jié)變尺度法（擬牛頓法），DFP算法：第42頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第七節(jié)坐標輪換法，基本思想：每次僅對多元函數(shù)的一個變量沿其坐標軸進行一維探索，其余各變量均固定不動，并依次輪換進行一維探索的坐標軸，完成第一輪探索后再重新進行第二輪探索，直到找到目標函數(shù)在全域上的最小點為止。目的：將一個多維的無約束最優(yōu)化問題，轉(zhuǎn)化為一系列的一維問題來求解。第43頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第七節(jié)坐標輪換法，二維問題第44頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第七節(jié)坐標輪換法，第k輪迭代公式：包括正負第45頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第七節(jié)坐標輪換法，步長α的幾種取法：隨機選擇方法加速步長法最優(yōu)步長法（一維搜索方法，如：黃金分割法、二次插值法，來確定最優(yōu)步長）第46頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第七節(jié)坐標輪換法，加速步長法：第47頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第七節(jié)坐標輪換法，坐標輪換法的流程圖第48頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第七節(jié)坐標輪換法，坐標輪換法的特點：

計算簡單、概念清楚、易于掌握；但搜索路線較長（需要經(jīng)過多次曲折迂回的路徑才能達到極值點），計算率較低，特別是當維數(shù)很高時很費時，所以坐標輪換法只能用于低維（n<10）的優(yōu)化問題求解。此外，坐標輪換法的效率在很大程度上取決于目標函數(shù)的性態(tài)，也就是等值線的形態(tài)與坐標軸的關(guān)系。第49頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第八節(jié)鮑威爾法，鮑威爾法的基本思想：

直接利用迭代點的目標函數(shù)值來構(gòu)造共軛方向，然后再從任一初始點出發(fā)，逐次的共軛方向作一維搜索求極值點。第50頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第八節(jié)鮑威爾法，共軛方向的生成：結(jié)論：從不同的兩點出發(fā)，沿同一方向進行兩次一維搜索，所得兩個極小點的連線方向便是原方向共軛的另一方向。第51頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第八節(jié)鮑威爾法，共軛方向的生成：二維情況：任意點出發(fā)沿著x1軸方向和AB方向搜索，即可得到極小點。第52頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第八節(jié)鮑威爾法，基本POWELL法（二維）：第53頁，共57頁，2023年，2月20日，星期五第四章無約束優(yōu)化方法第八節(jié)鮑威爾法基本POWELL法（n維）：1）從初始點出發(fā)，首先沿著n個坐標軸方向進行一維搜索，得到一個終點；2）由初始點和終點連線形成一個新方向，該方向排在原方向組的最后，去掉原方向組的的第一個方向，形成新的方向組；3）從上一輪的搜索終