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

無約束優(yōu)化計算方法第一頁，共一百零三頁，編輯于2023年，星期日

求解優(yōu)化問題的基本解法有：

解析法數(shù)值解法解析法：即利用數(shù)學(xué)分析(微分、變分等）的方法，根據(jù)函數(shù)（泛函）極值的必要條件和充分條件求出其最優(yōu)解析解的求解方法。在目標(biāo)函數(shù)比較簡單時，求解還可以。

局限性：工程優(yōu)化問題的目標(biāo)函數(shù)和約束條件往往比較復(fù)雜，有時甚至還無法用數(shù)學(xué)方程描述，在這種情況下應(yīng)用數(shù)學(xué)分析方法就會帶來麻煩。4.1引言第二頁，共一百零三頁，編輯于2023年，星期日

數(shù)值迭代法的基本思路：是進行反復(fù)的數(shù)值計算，尋求目標(biāo)函數(shù)值不斷下降的可行計算點，直到最后獲得足夠精度的最優(yōu)點。這種方法的求優(yōu)過程大致可歸納為以下步驟：

1）首先初選一個盡可能靠近最小點的初始點X（0），從X（0）出發(fā)按照一定的原則尋找可行方向和初始步長，向前跨出一步達到X（1）點；

2）得到新點X（1）后再選擇一個新的使函數(shù)值迅速下降的方向及適當(dāng)?shù)牟介L，從X（1）點出發(fā)再跨出一步，達到X（2）點，并依此類推，一步一步地向前探索并重復(fù)數(shù)值計算，最終達到目標(biāo)函數(shù)的最優(yōu)點。數(shù)值解法求解步驟第三頁，共一百零三頁，編輯于2023年，星期日在中間過程中每一步的迭代形式為：

上式中：X（k）——第k步迭代計算所得到的點，稱第k步迭代點，亦為第k步設(shè)計方案；

a（k）——第k步迭代計算的步長；

S（k）——第k步迭代計算的探索方向。迭代計算機逐步逼近最優(yōu)點過程示意圖用迭代法逐步逼近最優(yōu)點的探索過程如圖所示。第四頁，共一百零三頁，編輯于2023年，星期日

運用迭代法，每次迭代所得新的點的目標(biāo)函數(shù)都應(yīng)滿足函數(shù)值下降的要求：（1）選擇搜索方向（2）確定步長因子（3）給定收斂準(zhǔn)則迭代法要解決的問題：第五頁，共一百零三頁，編輯于2023年，星期日終止準(zhǔn)則準(zhǔn)則1-點距準(zhǔn)則準(zhǔn)則2-下降準(zhǔn)則：

準(zhǔn)則3-梯度準(zhǔn)則

第六頁，共一百零三頁，編輯于2023年，星期日往往采用兩個準(zhǔn)則來判別（1）f(x)在x*附近比較平坦

第七頁，共一百零三頁，編輯于2023年，星期日往往采用兩個準(zhǔn)則來判別（2）

f(x)在X*附近比較陡峭

結(jié)論：由于不知道函數(shù)的具體形態(tài)，有時用兩個準(zhǔn)則判斷更可靠??！第八頁，共一百零三頁，編輯于2023年，星期日

當(dāng)采用數(shù)學(xué)規(guī)劃法尋求多元函數(shù)的極值點時，一般要進行一系列如下格式的迭代計算:當(dāng)方向給定，求最佳步長就是求一元函數(shù)

:的極值問題，這一過程被稱為一維搜索.

第九頁，共一百零三頁，編輯于2023年，星期日第十頁，共一百零三頁，編輯于2023年，星期日一維搜索的最優(yōu)化方法-分析法例

已知極小值在區(qū)間內(nèi)，若從點出發(fā)，根據(jù)迭代公式：取第十一頁，共一百零三頁，編輯于2023年，星期日將代入得：令

得：

將（3-3）代入（3-2）得：

因為滿足準(zhǔn)則3所以=0（3-3）（3-2）第十二頁，共一百零三頁，編輯于2023年，星期日由舉例可知，一維搜索方法解析法利用一維函數(shù)的極值條件：一維搜索方法數(shù)值解法分類

一維搜索也稱直線搜索。這種方法不僅對于解決一維最優(yōu)化本身具有實際意義，而且也是解多維最優(yōu)化問題的重要支柱。第十三頁，共一百零三頁，編輯于2023年，星期日4.2.1進退法（確定搜索區(qū)間）

進退法也稱外推法，是一種通過比較函數(shù)值大小來確定單峰區(qū)間的方法。任意給定初始點X1和步長h，算出f(x1)和

x2=x1+h點的f(x2)函數(shù)值。

圖(a)．f(x1)>f(x2)，說明x*>x1，將步長增加一倍，取x3=x2+2h；

圖(b)．f(x1)>f(x2)，說明x*<x1，需改變步長符號，得點x3=x2-h。

以此類推，即每跨一步為前一次步長的2倍，直至函數(shù)值增加為止。4.2單變量優(yōu)化計算方法第十四頁，共一百零三頁，編輯于2023年，星期日在搜索區(qū)間內(nèi)[a,b]適當(dāng)插入兩點，將區(qū)間分成三段；4.2.2黃金分割法黃金分割法適用于[a,b]區(qū)間上的任何單谷函數(shù)求極小值問題。對函數(shù)除要求“單谷”外不作其他要求，甚至可以不連續(xù)。因此，這種方法的適應(yīng)面相當(dāng)廣。黃金分割法也是建立在區(qū)間消去法原理基礎(chǔ)上的試探方法。

利用區(qū)間消去法，使搜索區(qū)間縮小，通過迭代計算，使搜索區(qū)間無限縮小，從而得到極小點的數(shù)值近似解。第十五頁，共一百零三頁，編輯于2023年，星期日黃金分割法要求在保留下來的區(qū)間內(nèi)再插入一點所形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布。將區(qū)間分成三段第十六頁，共一百零三頁，編輯于2023年，星期日

黃金分割法也稱0.618法，是通過對黃金分割點函數(shù)值的計算和比較，將初始區(qū)間逐次進行縮小，直到滿足給定的精度要求，即求得一維極小點的近似解x*。1）

區(qū)間縮小的基本思路

已知f(x)的單峰區(qū)間[a,b]。為了縮小區(qū)間，在[a,b]內(nèi)按一定規(guī)則對稱地取2個內(nèi)部點x1

和x2

，并計算f(x1)和f(x2)?？赡苡腥N情況：第十七頁，共一百零三頁，編輯于2023年，星期日

圖(a)．經(jīng)過一次函數(shù)比較，區(qū)間縮小一次。在新的區(qū)間內(nèi)，保留一個好點x1和f(x1)，下一次只需再按一定規(guī)則，在新區(qū)間內(nèi)找另一個與x1

對稱的點x2

，計算f(x2)，與f(x1)比較。如此反復(fù)。

圖(b)．淘汰[a,x1],得新區(qū)間[a,b],此時：a=x1，x1=x2,x2為x1對稱點，b=b。

圖(c)．可歸納入上面任一種情況處理。2）取點規(guī)則黃金分割法的均勻縮短率為0.618，即每經(jīng)過一次函數(shù)值比較，都是淘汰本次區(qū)間的0.382倍。根據(jù)上式，黃金分割法的取點規(guī)則是第十八頁，共一百零三頁，編輯于2023年，星期日3）收斂準(zhǔn)則

由于實際問題的需要和函數(shù)形態(tài)的不同，常常需要不同的收斂準(zhǔn)則確定最優(yōu)點。對于直接法，有以下幾種收斂準(zhǔn)則：

（1）．區(qū)間絕對精度

（2）．區(qū)間相對精度

（3）．函數(shù)值絕對精度；

（4）．函數(shù)值相對精度4）

黃金分割法特點（1）不必要求f(x)可微，只要利用函數(shù)值大小的比較，即可很快地找到x*；（2）除了第一次縮小區(qū)間要計算兩個點及其函數(shù)值以外，其余每次只要計算一個點及其函數(shù)值；（3）可靠性好。

第十九頁，共一百零三頁，編輯于2023年，星期日5）

黃金分割法前提條件x1、x2在區(qū)間中的位置相對于邊界來說是對稱的在舍去一段后,留在新區(qū)間的那個點仍處于新區(qū)間內(nèi)兩個計算點之一的位置；在縮小區(qū)間時,λ的值為一不變的常數(shù)。第二十頁，共一百零三頁，編輯于2023年，星期日演示過程1第二十一頁，共一百零三頁，編輯于2023年，星期日演示過程2第二十二頁，共一百零三頁，編輯于2023年，星期日黃金分割法計算框圖第二十三頁，共一百零三頁，編輯于2023年，星期日黃金分割法的搜索過程：1）給出初始搜索區(qū)間及收斂精度，將賦以0.618。2）按坐標(biāo)點計算公式計算,；并計算其對應(yīng)的函數(shù)值。3）根據(jù)區(qū)間消去法原理縮短搜索區(qū)間。為了能用原來的坐標(biāo)點計算公式，需進行區(qū)間名稱的代換，并在保留區(qū)間中計算一個新的試驗點及其函數(shù)值。如果，則新區(qū)間＝ 令記N0=0；如果，則新區(qū)間＝，令，記N0=1；第二十四頁，共一百零三頁，編輯于2023年，星期日4）檢查區(qū)間是否縮短到足夠小和函數(shù)值收斂到足夠精度，如果收斂條件滿足，則取最后兩試驗點的平均值作為極小點的數(shù)值近似解。如果條件不滿足則轉(zhuǎn)向步驟5）。如N0=0，則取如N0=1，則取5）產(chǎn)生新的插入點：轉(zhuǎn)向3）進行新的區(qū)間縮小。第二十五頁，共一百零三頁，編輯于2023年，星期日第二十六頁，共一百零三頁，編輯于2023年，星期日第二十七頁，共一百零三頁，編輯于2023年，星期日第二十八頁，共一百零三頁，編輯于2023年，星期日第二十九頁，共一百零三頁，編輯于2023年，星期日例:用黃金分割法求函數(shù)f(x)=3x3-4x+2的極小點

給定x0=0,h=1,ε=0.2。解：1）確定初始區(qū)間x1=x0=0,f1=f(x1)=2x2=x0+h=0+1=1,f2=f(x2)=1由于f1>f2,應(yīng)在原方向繼續(xù)向前探測。x3=x2+h=1+1=2,f3=f(x3)=18由于f2<f3,可知初始區(qū)間已經(jīng)找到，即[a,b]=[x1,x2]=[0,2]2）用黃金分割法縮小區(qū)間第一次縮小區(qū)間：

x1=0+0.382X(2-0)=0.764,f1=0.282x2=0+0.618X(2-0)=1.236,f2=2.72f1<f2,新區(qū)間[a,b]=[a,x2]=[0,1.236],b-a>0.2第三十頁，共一百零三頁，編輯于2023年，星期日第二次縮小區(qū)間：令x2=x1=0.764,f2=f1=0.282

x1=0+0.382X(1.236-0)=0.472,f1=0.317由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.472,1.236]因為b-a=1.236-0.472=0.764>0.2,應(yīng)繼續(xù)縮小區(qū)間。第三十一頁，共一百零三頁，編輯于2023年，星期日第三次縮小區(qū)間：令x1=x2=0.764,f1=f2=0.282

x2=0.472+0.618X(1.236-0.472)=0.944,f2=0.747由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0.472,0.944]因為b-a=0.944-0.472=0.472>0.2,應(yīng)繼續(xù)縮小區(qū)間。第三十二頁，共一百零三頁，編輯于2023年，星期日

第四次縮小區(qū)間：令x2=x1=0.764,f2=f1=0.282

x1=0.472+0.382X(0.944-0.472)=0.652,f1=0.223由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0.472,0.764]因為b-a=0.764-0.472=0.292>0.2,應(yīng)繼續(xù)縮小區(qū)間。第三十三頁，共一百零三頁，編輯于2023年，星期日第五次縮小區(qū)間：令x2=x1=0.652,f2=f1=0.223

x1=0.472+0.382X(0.764-0.472)=0.584,f1=0.262由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.584,0.764]因為b-a=0.764-0.584=0.18<0.2,停止迭代。極小點與極小值：x*=0.5X(0.584+0.764)=0.674,f(x*)=0.222第三十四頁，共一百零三頁，編輯于2023年，星期日思考題：

試用黃金分割法求

近似極小點及極小值。已知[a,b]=[0,2]，ε=0.01（只要求進行2輪迭代，判斷是否收斂）。第三十五頁，共一百零三頁，編輯于2023年，星期日一維搜索的插值方法假定我們的問題是在某一確定區(qū)間內(nèi)尋求函數(shù)的極小點位置，雖然沒有函數(shù)表達式，但能夠給出若干試驗點處的函數(shù)值。我們可以根據(jù)這些點處的函數(shù)值，利用插值方法建立函數(shù)的某種近似表達式，進而求出函數(shù)的極小點，并用它作為原來函數(shù)極小點的近似值。這種方法稱作插值方法，又稱作函數(shù)迫近法。第三十六頁，共一百零三頁，編輯于2023年，星期日第三十七頁，共一百零三頁，編輯于2023年，星期日二次插值法（拋物線法）二次插值的基本思想是利用目標(biāo)函數(shù)在不同3點的函數(shù)值構(gòu)成一個與原函數(shù)f(x)相近似的二次多項式p(x)，以函數(shù)p(x)的極值點(即p’(x*p)=0的根)作為目標(biāo)函數(shù)f(x)的近似極值點。

x23p2p1f3x*1xf(x)p(x)xx1p3f2fp第三十八頁，共一百零三頁，編輯于2023年，星期日第三十九頁，共一百零三頁，編輯于2023年，星期日第四十頁，共一百零三頁，編輯于2023年，星期日第四十一頁，共一百零三頁，編輯于2023年，星期日例1用二次插值法求函數(shù)f(x)=3x3-4x+2的極小點，給定x0=0,ε=0.2。

解

1）確定初始區(qū)間初始區(qū)間[a,b]=[0,2],中間點x2=1。2）用二次插值法逼近極小點相鄰三點的函數(shù)值:x1=0,x2=1,x3=2;f1=2,f2=1,f3=18.代入公式：xp*＝0.555,fp=0.292第四十二頁，共一百零三頁，編輯于2023年，星期日在新區(qū)間，相鄰三點的函數(shù)值:x1=0,x2=0.555,x3=1;f1=2,f2=0.292,f3=1.xp*＝0.607,fp=0.243

由于fp<f2,xp>x2,新區(qū)間[a,b]=[x2,b]=[0.555,1]|x2-xp*|=|0.555-0.607|=0.052<0.2,迭代終止。

xp*＝0.607,f*=0.243由于fp<f2,xp*

<x2,新區(qū)間[a,b]=[a,x2]=[0,1]|x2-xp*

|=1-0.555=0.445>0.2,應(yīng)繼續(xù)迭代。第四十三頁，共一百零三頁，編輯于2023年，星期日第四十四頁，共一百零三頁，編輯于2023年，星期日第四十五頁，共一百零三頁，編輯于2023年，星期日第四十六頁，共一百零三頁，編輯于2023年，星期日

坐標(biāo)輪換法是每次搜索只允許一個變量變化，其余變量保持不變，即沿坐標(biāo)方向輪流進行搜索的尋憂方法。它把多變量的優(yōu)化問題輪流地轉(zhuǎn)化成單變量(其余變量視為常量)的優(yōu)化問題，因此又稱這種方法為變量輪換法。在搜索過程中可以不需要目標(biāo)函數(shù)的導(dǎo)數(shù)，只需目標(biāo)函數(shù)值信息。這比前面所討論的利用目標(biāo)函數(shù)導(dǎo)數(shù)信息建立搜索方向的方法要簡單得多。4.3.1坐標(biāo)輪換法4.3多變量優(yōu)化計算的非梯度方法第四十七頁，共一百零三頁，編輯于2023年，星期日第四十八頁，共一百零三頁，編輯于2023年，星期日第四十九頁，共一百零三頁，編輯于2023年，星期日第五十頁，共一百零三頁，編輯于2023年，星期日（1）計算量少，程序簡單，不需要求函數(shù)導(dǎo)數(shù)的直接探索目標(biāo)函數(shù)最優(yōu)解的方法；（2）探索路線較長，問題的維數(shù)愈多求解的效率愈低。當(dāng)維數(shù)n＞10時，則不應(yīng)采用此法。僅適用于n較少（n<10）的目標(biāo)函數(shù)求優(yōu)；

（3）改變初始點重新迭代，可避免出現(xiàn)病態(tài)。方法特點第五十一頁，共一百零三頁，編輯于2023年，星期日

鮑威爾方法

鮑威爾法是以共軛方向為基礎(chǔ)的收斂較快的直接法之一，是一種十分有效的算法。1964年，鮑維爾提出這種算法，其基本思想是直接利用迭代點的目標(biāo)函數(shù)值來構(gòu)造共軛方向，然后從任一初始點開始，逐次沿共軛方向作一維搜索求極小點。并在以后的實踐中進行了改進。

第五十二頁，共一百零三頁，編輯于2023年，星期日對函數(shù)：基本思想：在不用導(dǎo)數(shù)的前提下，在迭代中逐次構(gòu)造G的共軛方向。

1.共軛方向的生成jjkkkdddjggk+1xxk+1設(shè)xk,xk+1為從不同點出發(fā)，沿同一方向dj進行一維搜索而到的兩個極小點。

第五十三頁，共一百零三頁，編輯于2023年，星期日梯度和等值面相垂直的性質(zhì),dj和xk,xk+1兩點處的梯度gk,gk+1之間存在關(guān)系:另一方面，對于上述二次函數(shù)，其xk,xk+1兩點處的梯度可表示為:因而有取這說明只要沿dj方向分別對函數(shù)作兩次一維搜索，得到兩個極小點xk和xk+1

，那么這兩點的連線所給出的方向dk就是與dj一起對G共軛的方向。第五十四頁，共一百零三頁，編輯于2023年，星期日2.基本算法二維情況描述鮑威爾的基本算法:

1）任選一初始點x0，再選兩個線性無關(guān)的向量，如坐標(biāo)軸單位向量e1=[1,0]T和e2=[0,1]T作為初始搜索方向。2）從x0出發(fā)，順次沿e1，e1作一維搜索，得點，兩點連線得一新方向d1第五十五頁，共一百零三頁，編輯于2023年，星期日沿d2作一維搜索得點x2

。即是二維問題的極小點x*

。方法的基本迭代格式包括共軛方向產(chǎn)生和方向替換兩主要步驟。用

d1代替e1形成兩個線性無關(guān)向量d1,e2

，作為下一輪迭代的搜索方向。再從出發(fā)，沿d1作一維搜索得點，作為下一輪迭代的初始點。

3）從出發(fā)，順次沿e2,d1

作一維搜索，得到點，兩點連線得一新方向:第五十六頁，共一百零三頁，編輯于2023年，星期日

把二維情況的基本算法擴展到n維，則鮑威爾基本算法的要點是：在每一輪迭代中總有一個始點（第一輪的始點是任選的初始點）和n個線性獨立的搜索方向。從始點出發(fā)順次沿n個方向作一維搜索得一終點，由始點和終點決定了一個新的搜索方向。用這個方向替換原來n個方向中的一個，于是形成新的搜索方向組。替換的原則是去掉原方向組的第一個方向而將新方向排在原方向的最后。此外規(guī)定，從這一輪的搜索終點出發(fā)沿新的搜索方向作一維搜索而得到的極小點，作為下一輪迭代的始點。這樣就形成算法的循環(huán)。

第五十七頁，共一百零三頁，編輯于2023年，星期日

因為在迭代中的n個搜索方向有時會變成線性相關(guān)而不能形成共軛方向。這時組不成n維空間，可能求不到極小點，所以上述基本算法有待改進。

第五十八頁，共一百零三頁，編輯于2023年，星期日第五十九頁，共一百零三頁，編輯于2023年，星期日第六十頁，共一百零三頁，編輯于2023年，星期日第六十一頁，共一百零三頁，編輯于2023年，星期日第六十二頁，共一百零三頁，編輯于2023年，星期日第六十三頁，共一百零三頁，編輯于2023年，星期日第六十四頁，共一百零三頁，編輯于2023年，星期日第六十五頁，共一百零三頁，編輯于2023年，星期日第六十六頁，共一百零三頁，編輯于2023年，星期日鮑威爾方法是鮑威爾于1964年提出的，以后又經(jīng)過他本人的改進。該法是一種有效的共軛方向法，它可以在有限步內(nèi)找到二次函數(shù)的極小點。對于非二次函數(shù)只要具有連續(xù)二階導(dǎo)數(shù)，用這種方法也是有效的。第六十七頁，共一百零三頁，編輯于2023年，星期日單純形方法一、基本思想單純形替換法也是一種不使用導(dǎo)數(shù)的求解無約束極小化問題的直接搜索方法，與前面幾種方法不同的是，單純形替換法不是利用搜索方向從一個點迭代到另一個更優(yōu)的點，而是從一個單純形迭代到另一個更優(yōu)的單純形。第六十八頁，共一百零三頁，編輯于2023年，星期日定義：單純形

n維空間中的恰好有n+1個頂點（極點）的有界的凸多面體稱之為一個單純形。根據(jù)定義，可知，一維空間中的單純形是線段，二維空間中的單純形是三角形，而三維空間中的單純形則是四面體。在單純形替換算法中，從一個單純形到另一個單純形的迭代主要通過反射、擴張、收縮和縮邊這4個操作來實現(xiàn)。下面以二維問題為例來對4種操作進行說明（參見下圖）。第六十九頁，共一百零三頁，編輯于2023年，星期日第七十頁，共一百零三頁，編輯于2023年，星期日第七十一頁，共一百零三頁，編輯于2023年，星期日第七十二頁，共一百零三頁，編輯于2023年，星期日（1）反射——設(shè)除了最劣點X1以外的基余頂點的中心為X4，作X1關(guān)于點X4的對稱點X5，稱X5為X1的反射點。求反射點的過程稱之為反射。（2）擴張——在得到反射點X5之后，如果X5優(yōu)于原單純形的最劣點（即有），表明反射方向（X5—X1）是有利方向，反射成功。若進一步有，可沿反射方向前進適當(dāng)?shù)木嚯x到點X6。X6稱之為擴張點，求擴張點的過程稱之為擴張。擴張之后，若擴張點X6優(yōu)于反射點X5，則擴張成功，以X6取代X1，得新單純形{X6,X2,X3}；否則，擴張失敗，舍棄擴張點，以反射X5點取代X1，得新單純形{X5,X2,X3}。設(shè)當(dāng)前的單純形的頂點為X1，X2，X3，且有第七十三頁，共一百零三頁，編輯于2023年，星期日如果出現(xiàn)。表示反射完全失敗，應(yīng)退回到介于X4與X1之間的某個點X8。（3）收縮——在得到反射點X5之后，如果有表示反射部分成功，方向（X5—X1）雖然是有利方向，但X5前進過遠(yuǎn)，應(yīng)收縮到介于X4與X5之間的某個點X7。上述兩種從反射點向X1方向后退的過程都稱之為收縮。如果收縮點優(yōu)于原來的最劣點X1，稱收縮成功，并以收縮點取代原最劣點，構(gòu)成新單純形{X7,X2,X3}或{X8,X2,X3}；否則，稱之為收縮失敗，舍棄收縮點。第七十四頁，共一百零三頁，編輯于2023年，星期日（4）縮邊——若收縮失敗，則應(yīng)壓縮當(dāng)前單純形的邊長：令最優(yōu)點X3不動，而其余頂點向X3方向壓縮，使邊長縮短（通?？s短一半），以產(chǎn)生新單純形。如下圖所示，點X1壓縮到點X9，點X2壓縮到點X10，得新單純形{X9,X10,X3}，這一過程稱之為縮邊。第七十五頁，共一百零三頁，編輯于2023年，星期日二、單純形替換算法設(shè)初始點為X0，初始邊長h，ei為坐標(biāo)軸方向的單位向量，預(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）如果滿足第七十六頁，共一百零三頁，編輯于2023年，星期日第七十七頁，共一百零三頁，編輯于2023年，星期日1、坐標(biāo)輪換法計算效率較低適合維數(shù)較低，目標(biāo)函數(shù)無導(dǎo)數(shù)或?qū)?shù)較難求得2、Powell法具有二次收斂性，收斂速度較快，可靠性高，被認(rèn)為是直接法中最有效的方法之一3、單純形法思路清楚，收斂慢無約束優(yōu)化方法——直接法總結(jié)第七十八頁，共一百零三頁，編輯于2023年，星期日4.4梯度法

基本思想：函數(shù)的負(fù)梯度方向是函數(shù)值在該點下降最快的方向。將n維問題轉(zhuǎn)化為一系列沿負(fù)梯度方向用一維搜索方法尋優(yōu)的問題，利用負(fù)梯度作為搜索方向，故稱最速下降法或梯度法。搜索方向s取該點的負(fù)梯度方向(最速下降方向)，使函數(shù)值在該點附近的范圍內(nèi)下降最快。第七十九頁，共一百零三頁，編輯于2023年，星期日為了使目標(biāo)函數(shù)值沿搜索方向能夠獲得最大的下降值，其步長因子應(yīng)取一維搜索的最佳步長。即有

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

第八十頁，共一百零三頁，編輯于2023年，星期日在最速下降法中，相鄰兩個迭代點上的函數(shù)梯度相互垂直。而搜索方向就是負(fù)梯度方向，因此相鄰兩個搜索方向互相垂直。這就是說在迭代點向函數(shù)極小點靠近的過程，走的是曲折的路線。形成“之”字形的鋸齒現(xiàn)象，而且越接近極小點鋸齒越細(xì)。

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

例4－1求目標(biāo)函數(shù)的極小點。解取初始點則初始點處函數(shù)值及梯度分別為第八十四頁，共一百零三頁，編輯于2023年，星期日算出一維搜索最佳步長

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

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

第八十五頁，共一百零三頁，編輯于2023年，星期日這個問題的目標(biāo)函數(shù)的等值線為一簇橢圓,迭代點從走的是一段鋸齒形路線，見圖。第八十六頁，共一百零三頁，編輯于2023年，星期日將上例中目標(biāo)函數(shù)引入變換其等值線由橢圓變成一簇同心圓。

仍從

即

出發(fā)進行最速下降法尋優(yōu)。此時：沿負(fù)梯度方向進行一維搜索：則函數(shù)f(X)變?yōu)椋簓1=x1,y2=5x2第八十七頁，共一百零三頁，編輯于2023年，星期日β為一維搜索最佳步長，可由極值條件：由從而算得一步計算后設(shè)計點的位置及其目標(biāo)函數(shù)：第八十八頁，共一百零三頁，編輯于2023年，星期日經(jīng)變換后，只需一次迭代，就可找到最優(yōu)解。這是因為經(jīng)過尺度變換：等值線由橢圓變成圓。第八十九頁，共一百零三頁，編輯于2023年，星期日共軛梯度法共軛梯度法中每一個共軛向量都是依賴于迭代點處的負(fù)梯度而構(gòu)造出來。從x(k)出發(fā)，沿負(fù)梯度方向作一維搜索:設(shè)與sk共軛的下一個方向sk+1由sk和點xk+1的負(fù)梯度的線形組合構(gòu)成，即：共軛條件：第九十頁，共一百零三頁，編輯于2023年，星期日則：解得：令為函數(shù)的泰勒二次展開式則上兩式相減，并代入第九十一頁，共一百零三頁，編輯于2023年，星期日將式與式轉(zhuǎn)置兩邊相乘，應(yīng)用共軛條件得：因此第九十二頁，共一百零三頁，編輯于2023年，星期日第九十三頁，共一百零三頁，編輯于2023年，星期日，已知初始點[1,1]T例