第三章 一維搜索方法

第三章

一維搜索方法

第一節(jié)

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

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

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

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

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

在區(qū)間[a，b

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

3.進退法的步驟：（1）給定初始點α0和初始步長h0；（3）比較f1與f2,存在兩種情況：進①②進①②退①②退總結(jié)進退法：給定初始值及初始步長向前試探，如果函數(shù)值上升，則步長變號，即改變試探方向。如果函數(shù)值下降，則不改變試探方向，并將步長加倍，最后找到函數(shù)值“高-低-高”。圖3-2正向搜索的外推法圖3-3反向搜索的外推法三、區(qū)間消去法原理搜索區(qū)間（a,b）確定后，采用區(qū)間消去法逐步縮短區(qū)間，從而找到極小點的近似值，方法是在區(qū)間內(nèi)任取兩點a1,b1，假設(shè)a1<b1，計算其函數(shù)值。分以下三種情況：函數(shù)為單谷，極小點必在區(qū)間（a,b1）內(nèi)。函數(shù)為單谷，極小點必在區(qū)間（a1,b）內(nèi)。函數(shù)為單谷，極小點必在區(qū)間（a1,b1）內(nèi)。為了避免多計算函數(shù)值，將第三種情況合并到前兩種情況中。三、一維搜索方法的分類從前面的分析可知，每次縮短區(qū)間，只需要在區(qū)間內(nèi)在插入一點并計算其函數(shù)值。而插入點的位置，可以由不同的方法來確定。就形成了不同的一維搜索方法。一維搜索方法分類試探法插值法黃金分割法二次插值法第三節(jié)一維搜索的試探法最常用的一維搜索試探法是黃金分割法，又稱0.618法。對目標(biāo)函數(shù)的要求：單谷、可以不連續(xù)。原理：區(qū)間消去法，使搜索區(qū)間無限縮小，從而得到極小點的近似解。特殊之處是要求插入點a1、a2的位置相對于區(qū)間[a,b]兩端點具有對稱性，即：除對稱要求外，黃金分割法還要求在保留下來的區(qū)間再插入一點所形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布。2所謂的“黃金分割”是指將一線段分成兩段的方法，使整段長與較長段的長度比值等于較長段與較短段的比值，即黃金分割法的搜索過程：1）給出初始搜索區(qū)間（a,b）及收斂精度ξ，將λ賦以0.618。2）計算區(qū)間分割點α1和α2，并計算其對應(yīng)的函數(shù)值。3）根據(jù)區(qū)間消去法原理縮短區(qū)間。注意：為了能用原來的坐標(biāo)點計算公式，須進行區(qū)間名稱得代換，并在保留區(qū)間中計算一個新的分割點及其函數(shù)值。4）檢查區(qū)間是否滿足迭代準(zhǔn)則，如不滿足返2）。5）如果條件滿足，則取最后兩點的平均值作為極小點的近似解。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ù)的極小點的位置，雖然沒有函數(shù)表達式，但能夠給出若干試驗點處的函數(shù)值。我們可以根據(jù)這些點處的函數(shù)值，利用插值的方法建立函數(shù)的近似表達式，進而求處函數(shù)的極小點，作為原來函數(shù)的極小點的近似值。這種方法稱作插值法，也稱函數(shù)逼近法。一、牛頓法（切線法）一維搜索函數(shù)，假定一給出極小點的一個較好的近似點，因為一個連續(xù)可微的函數(shù)在極小點附近與一個二次函數(shù)很接近，因此，在點附近用一個二次函數(shù)逼近。求二次函數(shù)的極小點作為極小點的新近似點即依次繼續(xù)下去，可得牛頓法迭代公式：牛頓法的幾何解釋：圖3-9一維搜索的切線法牛頓法的計算步驟：給定初始點，控制誤差，并令k=0。1）計算2）求3)若則求得近似解，停止計算，否則作4。4）令轉(zhuǎn)1。優(yōu)點：收斂速度快。缺點：每一點都要進行二階導(dǎo)數(shù)，工作量大；要求初始點離極小點不太遠，否則有可能使極小化發(fā)散或收斂到非極小點。二、二次插值（拋物線法）利用在單谷區(qū)間