第三章 一維搜索方法

第三章

一維搜索方法

第一節(jié)

概述第二節(jié)搜索區(qū)間的確定和區(qū)間消去法原理第三節(jié)一維搜索的試探方法第四節(jié)一維搜索的插值方法第一節(jié)概述采用數(shù)學(xué)規(guī)劃法求函數(shù)極值點(diǎn)的迭代計(jì)算：K+1次迭代的搜索方向搜索的最佳步長(zhǎng)因子當(dāng)搜索方向給定，求最佳步長(zhǎng)就是求一元函數(shù)的極值。即在第K次迭代時(shí)，從已知點(diǎn)X(k)出發(fā)，沿給定方向求最優(yōu)步長(zhǎng)因子α(k)，使f(X(k)+akdk)達(dá)到最小值的過(guò)程，稱為一維搜索，它是優(yōu)化搜索方法的基礎(chǔ)。上式求α的極值，即求α導(dǎo)數(shù)為零。則從上式看，需要求導(dǎo)進(jìn)行計(jì)算，對(duì)于函數(shù)關(guān)系復(fù)雜的，解析法十分不便。求解一元函數(shù)的極小點(diǎn)1、解析法

把f(X(k)+αd(k))沿d(k)方向泰勒展開(kāi),取二次近似：數(shù)值法基本思路：確定的搜索區(qū)間，在不斷縮小區(qū)間，最終獲得近似值。2、數(shù)值法直接法——應(yīng)用序列消去原理：

進(jìn)退法、黃金分割法近似法——利用多項(xiàng)式函數(shù)逼近（曲線擬合）原理：

二次插值法、三次插值法步驟：①進(jìn)退法找單谷區(qū)間；②

0.618法或插值法在單谷區(qū)間找最優(yōu)點(diǎn)。單峰區(qū)間（高－低－高）

在區(qū)間[a，b

]內(nèi)，函數(shù)只有一個(gè)峰值，則此區(qū)間為單峰區(qū)間。單峰區(qū)間內(nèi)，一定存在一點(diǎn)α*，當(dāng)任意一點(diǎn)α2＞α*時(shí)，f(α2)＞f(α*)，當(dāng)α2＜α*時(shí)，仍有f(α2)＞f(α*)，則α*是最優(yōu)點(diǎn)，也即為最優(yōu)步長(zhǎng)因子α(k)。第二節(jié)搜索區(qū)間的確定和區(qū)間消去法原理一、確定搜索區(qū)間的外推法圖3-1具有單谷性的函數(shù)α2α2說(shuō)明：?jiǎn)畏鍏^(qū)間內(nèi)，函數(shù)可以有不可微點(diǎn)，也可以是不連續(xù)函數(shù)；α0f(x)α1α3αf(x)0α3α1確定的搜索區(qū)間必定是一個(gè)含有最優(yōu)點(diǎn)α*的單峰區(qū)間。２.進(jìn)退法的基本思路：由單峰函數(shù)的性質(zhì)可知，在極小點(diǎn)α*左邊函數(shù)值應(yīng)嚴(yán)格下降，而在極小點(diǎn)右邊函數(shù)值應(yīng)嚴(yán)格上升，因此可以從某一個(gè)給定初始點(diǎn)α1出發(fā)，以初始步長(zhǎng)h0沿著目標(biāo)值的下降方向，逐步前進(jìn)或后退，直至找到相繼的3個(gè)試點(diǎn)的函數(shù)值按“大-小-大”變化為止。

3.進(jìn)退法的步驟：（1）給定初始點(diǎn)α0和初始步長(zhǎng)h0；（3）比較f1與f2,存在兩種情況：進(jìn)①②進(jìn)①②退①②退總結(jié)進(jìn)退法：給定初始值及初始步長(zhǎng)向前試探，如果函數(shù)值上升，則步長(zhǎng)變號(hào)，即改變?cè)囂椒较?。如果函?shù)值下降，則不改變?cè)囂椒较?，并將步長(zhǎng)加倍，最后找到函數(shù)值“高-低-高”。圖3-2正向搜索的外推法圖3-3反向搜索的外推法三、區(qū)間消去法原理搜索區(qū)間（a,b）確定后，采用區(qū)間消去法逐步縮短區(qū)間，從而找到極小點(diǎn)的近似值，方法是在區(qū)間內(nèi)任取兩點(diǎn)a1,b1，假設(shè)a1<b1，計(jì)算其函數(shù)值。分以下三種情況：函數(shù)為單谷，極小點(diǎn)必在區(qū)間（a,b1）內(nèi)。函數(shù)為單谷，極小點(diǎn)必在區(qū)間（a1,b）內(nèi)。函數(shù)為單谷，極小點(diǎn)必在區(qū)間（a1,b1）內(nèi)。為了避免多計(jì)算函數(shù)值，將第三種情況合并到前兩種情況中。三、一維搜索方法的分類(lèi)從前面的分析可知，每次縮短區(qū)間，只需要在區(qū)間內(nèi)在插入一點(diǎn)并計(jì)算其函數(shù)值。而插入點(diǎn)的位置，可以由不同的方法來(lái)確定。就形成了不同的一維搜索方法。一維搜索方法分類(lèi)試探法插值法黃金分割法二次插值法第三節(jié)一維搜索的試探法最常用的一維搜索試探法是黃金分割法，又稱0.618法。對(duì)目標(biāo)函數(shù)的要求：?jiǎn)喂?、可以不連續(xù)。原理：區(qū)間消去法，使搜索區(qū)間無(wú)限縮小，從而得到極小點(diǎn)的近似解。特殊之處是要求插入點(diǎn)a1、a2的位置相對(duì)于區(qū)間[a,b]兩端點(diǎn)具有對(duì)稱性，即：除對(duì)稱要求外，黃金分割法還要求在保留下來(lái)的區(qū)間再插入一點(diǎn)所形成的區(qū)間新三段，與原來(lái)區(qū)間的三段具有相同的比例分布。2所謂的“黃金分割”是指將一線段分成兩段的方法，使整段長(zhǎng)與較長(zhǎng)段的長(zhǎng)度比值等于較長(zhǎng)段與較短段的比值，即黃金分割法的搜索過(guò)程：1）給出初始搜索區(qū)間（a,b）及收斂精度ξ，將λ賦以0.618。2）計(jì)算區(qū)間分割點(diǎn)α1和α2，并計(jì)算其對(duì)應(yīng)的函數(shù)值。3）根據(jù)區(qū)間消去法原理縮短區(qū)間。注意：為了能用原來(lái)的坐標(biāo)點(diǎn)計(jì)算公式，須進(jìn)行區(qū)間名稱得代換，并在保留區(qū)間中計(jì)算一個(gè)新的分割點(diǎn)及其函數(shù)值。4）檢查區(qū)間是否滿足迭代準(zhǔn)則，如不滿足返2）。5）如果條件滿足，則取最后兩點(diǎn)的平均值作為極小點(diǎn)的近似解。floatgolden(float

a,floatb){floatx,x1,x2,B=0.618,e=0.00001;x1=b-B*(b-a);x2=a+B*(b-a);do{if(f(x1)>=f(x2)){a=x1;x1=x2;x2=a+B*(b-a);}else{b=x2;x2=x1;x1=b-B*(b-a);}}while(fabs(x1-x2)>=e);x=(x1+x2)/2;return(x);}#include<stdio.h>#include<math.h>floatf(floatx){floaty;y=x*x*x/3-x*x+1;return(y);}voidmain(){floata,b,x;printf("Entertwonumbers:");scanf("%f,%f",&a,&b);x=golden(a,b);printf("x=%f,f(x)",x,f(x));}第四節(jié)一維搜索的插值方法假定要在某一區(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ù)逼近法。一、牛頓法（切線法）一維搜索函數(shù)，假定一給出極小點(diǎn)的一個(gè)較好的近似點(diǎn)，因?yàn)橐粋€(gè)連續(xù)可微的函數(shù)在極小點(diǎn)附近與一個(gè)二次函數(shù)很接近，因此，在點(diǎn)附近用一個(gè)二次函數(shù)逼近。求二次函數(shù)的極小點(diǎn)作為極小點(diǎn)的新近似點(diǎn)即依次繼續(xù)下去，可得牛頓法迭代公式：牛頓法的幾何解釋?zhuān)簣D3-9一維搜索的切線法牛頓法的計(jì)算步驟：給定初始點(diǎn)，控制誤差，并令k=0。1）計(jì)算2）求3)若則求得近似解，停止計(jì)算，否則作4。4）令轉(zhuǎn)1。優(yōu)點(diǎn)：收斂速度快。缺點(diǎn)：每一點(diǎn)都要進(jìn)行二階導(dǎo)數(shù)，工作量大；要求初始點(diǎn)離極小點(diǎn)不太遠(yuǎn)，否則有可能使極小化發(fā)散或收斂到非極小點(diǎn)。二、二次插值（拋物線法）利用在單谷區(qū)間