第三章一維搜索方法

1、第三章 一維搜索方法 第一節(jié) 概 述 第二節(jié) 搜索區(qū)間的確定和區(qū) 間消去法原理 第三節(jié) 一維搜索的試探方法 第四節(jié) 一維搜索的插值方法第一節(jié) 概 述1kkkkxxa d采用數(shù)學(xué)規(guī)劃法求函數(shù)極值點的迭代計算：K+1次迭代的搜索方向搜索的最佳步長因子當(dāng)搜索方向 給定，求最佳步長kakd就是求一元函數(shù)的極值。1kkkkkf xf xa da即在第K次迭代時，從已知點 X(k)出發(fā)，沿給定方向求最優(yōu)步長因子(k)，使 f (X(k) + akdk)達到最小值的過程，稱為一維搜索，它是優(yōu)化搜索方法的基礎(chǔ)。 12TTf xadf xadf xadG ad上式求的極值，即求導(dǎo)數(shù)為零。 212TTf xdf

2、xd Gd *0TTdf xd Gd則 *TTdfxd Gd 從上式看，需要求導(dǎo)進行計算，對于函數(shù)關(guān)系復(fù)雜的，解析法十分不便。求解一元函數(shù) 的極小點a*a1、解析法 把 f(X(k) + d(k) ) 沿d(k) 方向泰勒展開,取二次近似： 數(shù)值法基本思路：確定 的搜索區(qū)間，在不斷縮小區(qū)間，最終獲得近似值。*2、數(shù)值法直接法應(yīng)用序列消去原理： 進退法、黃金分割法近似法利用多項式函數(shù)逼近（曲線擬合）原理： 二次插值法、 三次插值法步驟： 進退法找單谷區(qū)間； 0.618法或插值法在單谷區(qū)間找最優(yōu)點。單峰區(qū)間單峰區(qū)間（高低高）（高低高） 在區(qū)間在區(qū)間 aa，b b 內(nèi)，函數(shù)只內(nèi)，函數(shù)只有一個峰值，則

3、此區(qū)間為單峰有一個峰值，則此區(qū)間為單峰區(qū)間。單峰區(qū)間內(nèi)，一定存在區(qū)間。單峰區(qū)間內(nèi)，一定存在一點一點* *，當(dāng)任意一點，當(dāng)任意一點2 2* *時，時，f(f(2 2) )f(f(* *) )，當(dāng)當(dāng)2 2*時時，仍有仍有f (f (2 2 ) ) f(f(* *) ) ，則，則* *是是最優(yōu)點，也即為最優(yōu)步長因子最優(yōu)點，也即為最優(yōu)步長因子(k)(k)。第二節(jié) 搜索區(qū)間的確定和區(qū)間消去法原理一、確定搜索區(qū)間的外推法圖3-1 具有單谷性的函數(shù)22說明：說明：l 單峰區(qū)間內(nèi)，函數(shù)可以有不可微點，也可以是不連續(xù)單峰區(qū)間內(nèi)，函數(shù)可以有不可微點，也可以是不連續(xù) 函數(shù)；函數(shù)；0f (x)13f (x)031l

4、確定的搜索區(qū)間必定是一個含有最優(yōu)點確定的搜索區(qū)間必定是一個含有最優(yōu)點* *的單峰區(qū)間的單峰區(qū)間。.進退法的基本思路：進退法的基本思路： 由單峰函數(shù)的性質(zhì)可知，在極小點*左邊函數(shù)值應(yīng)嚴格下降，而在極小點右邊函數(shù)值應(yīng)嚴格上升，因此可以從某一個給定初始點1出發(fā)，以初始步長h0沿著目標值的下降方向，逐步前進或后退，直至找到相繼的3個試點的函數(shù)值按“大-小-大”變化為止。;,)2()(2)(1211200121ffffhhh并并計計算算函函數(shù)數(shù)值值，、得得到到兩兩試試點點令令 3 . 進退法的步驟：進退法的步驟：（1 1）給定初始點）給定初始點0 0和初始步長和初始步長h h0 0；（3 3）比較）比較

5、f1f1與與f2,f2,存在兩種情況：存在兩種情況：32)(32321,) 13ffffhff與與比比較較計計算算取取第第三三個個點點則則作作前前進進運運算算若若進,3323121ff大大”，搜搜索索區(qū)區(qū)間間為為小小值值滿滿足足“大大并并且且函函數(shù)數(shù)、則則找找到到三三個個試試點點若若,2,3123322132bahhhff大”，搜索區(qū)間小“大直到找到函數(shù)值滿足、則步長加倍，即令若2311f2f3f21 32 h230h0h02h進.,)232)(3232211213ffffhffhhff與比較對調(diào)后的并計算函數(shù)值對調(diào)，并取第三試點與將則作后退運算，令若退；，則搜索區(qū)間若,1332baff,2,

6、133223322132baffhhhff大”搜索區(qū)間小直到找到“大與計算、退運算，即令則步長加倍，繼續(xù)作后若21211f2f3f21 32 h230h0h02h退231f2f3f總結(jié)進退法總結(jié)進退法：給定初始值及初始步長向前試探，如果函數(shù)：給定初始值及初始步長向前試探，如果函數(shù)值上升，則步長變號，即改變試探方向。如果函數(shù)值下降，值上升，則步長變號，即改變試探方向。如果函數(shù)值下降，則不改變試探方向，并將步長加倍，最后找到函數(shù)值則不改變試探方向，并將步長加倍，最后找到函數(shù)值“高高- -低低- -高高”。圖3-2 正向搜索的外推法圖3-3 反向搜索的外推法三、區(qū)間消去法原理搜索區(qū)間（a, b）確定

7、后，采用區(qū)間消去法逐步縮短區(qū)間，從而找到極小點的近似值，方法是在區(qū)間內(nèi)任取兩點a1,b1，假設(shè)a1=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#includefloat f(float x)float y;y=x*x*x/3-x*x+1;return(y); void main()float a,b,x;printf(Enter two numbers:);scanf(%f,%f,&a,&b

8、);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ù)逼近法。一、牛頓法（切線法） 20000012ffff yf一維搜索函數(shù)，假定一給出極小點的一個較好的近似點0，因為一個連續(xù)可微的函數(shù)在極小點附近與一個二次函數(shù)很接近，因此，在 點附近用一個二次函數(shù) 逼近。0 10 求二次函數(shù) 的極小點作為 f極小點的新近

9、似點1即0000ff0100ff依次繼續(xù)下去，可得牛頓法迭代公式：1kkkkff0,1,2,.k 牛頓法的幾何解釋：圖3-9 一維搜索的切線法牛頓法的計算步驟：給定初始點 ，控制誤差 ，并令k=0。01）計算kfkf2）求1kkkkff3)若1kkaa則求得近似解*1kaa，停止計算，否則作4。4）令1kk轉(zhuǎn)1。優(yōu)點：收斂速度快。缺點：每一點都要進行二階導(dǎo)數(shù)，工作量大；要求初始點離極小點不太遠，否則有可能使極小化發(fā)散或收斂到非極小點。二、二次插值（拋物線法）利用123 yf a在單谷區(qū)間中 的函數(shù)值123fff，作出如下的二次插值多項式 2012Paaa它應(yīng)滿足條件210112111Paaayf（1）220122222Paaayf230132333Paaayf從極值的必要條件求得1220ppPaa12/2paa （2）（3）要求出系數(shù) 和 ，聯(lián)立方程組（1）、（2）、（3）。1a2a2212322323a aaaaayy2211221212a aaaaayy2222222313121231122331aayaayaayaaaaaaa2313121232122331aa