無(wú)約束優(yōu)化計(jì)算方法

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

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

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

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

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

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

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

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

a（k）——第k步迭代計(jì)算的步長(zhǎng)；

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

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

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

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

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

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

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

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

:的極值問(wèn)題，這一過(guò)程被稱為一維搜索.

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

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

得：

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

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

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

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

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

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

圖(b)．f(x1)>f(x2)，說(shuō)明x*<x1，需改變步長(zhǎng)符號(hào)，得點(diǎn)x3=x2-h。

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

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

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

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

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

和x2

，并計(jì)算f(x1)和f(x2)。可能有三種情況：第十七頁(yè)，共一百零三頁(yè)，編輯于2023年，星期日

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

對(duì)稱的點(diǎn)x2

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

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

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

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

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

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

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

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

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

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

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

給定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ù)向前探測(cè)。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第三十頁(yè)，共一百零三頁(yè)，編輯于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]因?yàn)閎-a=1.236-0.472=0.764>0.2,應(yīng)繼續(xù)縮小區(qū)間。第三十一頁(yè)，共一百零三頁(yè)，編輯于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]因?yàn)閎-a=0.944-0.472=0.472>0.2,應(yīng)繼續(xù)縮小區(qū)間。第三十二頁(yè)，共一百零三頁(yè)，編輯于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]因?yàn)閎-a=0.764-0.472=0.292>0.2,應(yīng)繼續(xù)縮小區(qū)間。第三十三頁(yè)，共一百零三頁(yè)，編輯于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]因?yàn)閎-a=0.764-0.584=0.18<0.2,停止迭代。極小點(diǎn)與極小值：x*=0.5X(0.584+0.764)=0.674,f(x*)=0.222第三十四頁(yè)，共一百零三頁(yè)，編輯于2023年，星期日思考題：

試用黃金分割法求

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

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

解

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

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

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

鮑威爾方法

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

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

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

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

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

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

。即是二維問(wèn)題的極小點(diǎn)x*

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

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

，作為下一輪迭代的搜索方向。再?gòu)某霭l(fā)，沿d1作一維搜索得點(diǎn)，作為下一輪迭代的初始點(diǎn)。

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

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

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

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

因?yàn)樵诘械膎個(gè)搜索方向有時(shí)會(huì)變成線性相關(guān)而不能形成共軛方向。這時(shí)組不成n維空間，可能求不到極小點(diǎn)，所以上述基本算法有待改進(jìn)。

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

n維空間中的恰好有n+1個(gè)頂點(diǎn)（極點(diǎn)）的有界的凸多面體稱之為一個(gè)單純形。根據(jù)定義，可知，一維空間中的單純形是線段，二維空間中的單純形是三角形，而三維空間中的單純形則是四面體。在單純形替換算法中，從一個(gè)單純形到另一個(gè)單純形的迭代主要通過(guò)反射、擴(kuò)張、收縮和縮邊這4個(gè)操作來(lái)實(shí)現(xiàn)。下面以二維問(wèn)題為例來(lái)對(duì)4種操作進(jìn)行說(shuō)明（參見(jiàn)下圖）。第六十九頁(yè)，共一百零三頁(yè)，編輯于2023年，星期日第七十頁(yè)，共一百零三頁(yè)，編輯于2023年，星期日第七十一頁(yè)，共一百零三頁(yè)，編輯于2023年，星期日第七十二頁(yè)，共一百零三頁(yè)，編輯于2023年，星期日（1）反射——設(shè)除了最劣點(diǎn)X1以外的基余頂點(diǎn)的中心為X4，作X1關(guān)于點(diǎn)X4的對(duì)稱點(diǎn)X5，稱X5為X1的反射點(diǎn)。求反射點(diǎn)的過(guò)程稱之為反射。（2）擴(kuò)張——在得到反射點(diǎn)X5之后，如果X5優(yōu)于原單純形的最劣點(diǎn)（即有），表明反射方向（X5—X1）是有利方向，反射成功。若進(jìn)一步有，可沿反射方向前進(jìn)適當(dāng)?shù)木嚯x到點(diǎn)X6。X6稱之為擴(kuò)張點(diǎn)，求擴(kuò)張點(diǎn)的過(guò)程稱之為擴(kuò)張。擴(kuò)張之后，若擴(kuò)張點(diǎn)X6優(yōu)于反射點(diǎn)X5，則擴(kuò)張成功，以X6取代X1，得新單純形{X6,X2,X3}；否則，擴(kuò)張失敗，舍棄擴(kuò)張點(diǎn)，以反射X5點(diǎn)取代X1，得新單純形{X5,X2,X3}。設(shè)當(dāng)前的單純形的頂點(diǎn)為X1，X2，X3，且有第七十三頁(yè)，共一百零三頁(yè)，編輯于2023年，星期日如果出現(xiàn)。表示反射完全失敗，應(yīng)退回到介于X4與X1之間的某個(gè)點(diǎn)X8。（3）收縮——在得到反射點(diǎn)X5之后，如果有表示反射部分成功，方向（X5—X1）雖然是有利方向，但X5前進(jìn)過(guò)遠(yuǎn)，應(yīng)收縮到介于X4與X5之間的某個(gè)點(diǎn)X7。上述兩種從反射點(diǎn)向X1方向后退的過(guò)程都稱之為收縮。如果收縮點(diǎn)優(yōu)于原來(lái)的最劣點(diǎn)X1，稱收縮成功，并以收縮點(diǎn)取代原最劣點(diǎn)，構(gòu)成新單純形{X7,X2,X3}或{X8,X2,X3}；否則，稱之為收縮失敗，舍棄收縮點(diǎn)。第七十四頁(yè)，共一百零三頁(yè)，編輯于2023年，星期日（4）縮邊——若收縮失敗，則應(yīng)壓縮當(dāng)前單純形的邊長(zhǎng)：令最優(yōu)點(diǎn)X3不動(dòng)，而其余頂點(diǎn)向X3方向壓縮，使邊長(zhǎng)縮短（通?？s短一半），以產(chǎn)生新單純形。如下圖所示，點(diǎn)X1壓縮到點(diǎn)X9，點(diǎn)X2壓縮到點(diǎn)X10，得新單純形{X9,X10,X3}，這一過(guò)程稱之為縮邊。第七十五頁(yè)，共一百零三頁(yè)，編輯于2023年，星期日二、單純形替換算法設(shè)初始點(diǎn)為X0，初始邊長(zhǎng)h，ei為坐標(biāo)軸方向的單位向量，預(yù)定正數(shù)（2）比較各項(xiàng)點(diǎn)Xi的函數(shù)值，挑出其中的最優(yōu)點(diǎn)，記為XL；最劣點(diǎn)，記XH；次差點(diǎn)，記為Xw；（3）求反射中心其中，a>0，通常取a=1；

（1）令；輸出XL，為原問(wèn)題近似極小點(diǎn)；否則，轉(zhuǎn)（2）。構(gòu)造新單純形；（4）根據(jù)不同情況，分別進(jìn)行擴(kuò)張，收縮或縮邊，其中收縮因子（5）如果滿足第七十六頁(yè)，共一百零三頁(yè)，編輯于2023年，星期日第七十七頁(yè)，共一百零三頁(yè)，編輯于2023年，星期日1、坐標(biāo)輪換法計(jì)算效率較低適合維數(shù)較低，目標(biāo)函數(shù)無(wú)導(dǎo)數(shù)或?qū)?shù)較難求得2、Powell法具有二次收斂性，收斂速度較快，可靠性高，被認(rèn)為是直接法中最有效的方法之一3、單純形法思路清楚，收斂慢無(wú)約束優(yōu)化方法——直接法總結(jié)第七十八頁(yè)，共一百零三頁(yè)，編輯于2023年，星期日4.4梯度法

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

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

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

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

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

第一次迭代設(shè)計(jì)點(diǎn)位置和函數(shù)值

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

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

仍從

即

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