第三章-一維搜索方法PPT課件

1、第三章一維搜索方法,第一節(jié) 一維搜索的概念 第二節(jié) 搜索區(qū)間的確定與區(qū)間消去法原理 第三節(jié) 一維搜索的試探方法黃金分割法 第四節(jié) 一維搜索的插值方法,第一節(jié) 一維搜索的概念,當(dāng)采用數(shù)學(xué)規(guī)劃法尋求多元函數(shù)的極值點時，一般要進行 一系列如下格式的迭代計算,當(dāng)方向,給定，求最佳步長,就是求一元函數(shù),的極值問題。這一過程被稱為一維搜索,一維搜索是優(yōu)化搜索方法的基礎(chǔ),f (x (k+1) ) = min. f (x (k) + S (k) ) = f (x (k) + (k) S ( k),求解一元函數(shù) 的極小點,可用解析法,上式求的極值，即求導(dǎo)數(shù)為零,則,數(shù)值解法基本思路,先確定 所在的搜索區(qū)間，然后

2、根據(jù)區(qū)間消去法原理不斷縮小此區(qū)間，從而獲得 的數(shù)值近似解,解析解法對于函數(shù)關(guān)系復(fù)雜、求導(dǎo)困難等情況難以實現(xiàn)。在實際優(yōu)化設(shè)計中，數(shù)值解法的應(yīng)用更為有效，且適合計算機的運算特點,一維搜索也稱直線搜索。這種方法不僅對于解決一維最優(yōu)化問題具有實際意義，而且也是求解多維最優(yōu)化問題的重要支柱,一維搜索一般分為兩大步驟： (1)確定初始搜索區(qū)間a，b，該區(qū)間應(yīng)是包括一維函數(shù)極小點在內(nèi)的單谷區(qū)間。 (2)在單谷區(qū)間a,b內(nèi)通過縮小區(qū)間尋找極小點,第二節(jié) 搜索區(qū)間的確定與區(qū)間消去法原理,1、確定搜索區(qū)間的外推法,1）單谷（峰）區(qū)間,在給定區(qū)間內(nèi)僅有一個谷值（或有唯一的極小點）的函數(shù)稱為單谷函數(shù)，其區(qū)間稱為單谷區(qū)

3、間,函數(shù)值：“大小大,圖形：“高低高,單谷區(qū)間中一定能求得一個極小點,說明：單谷區(qū)間內(nèi)，函數(shù)可以有不可微點，也可以是不連續(xù)函數(shù),2）外推方法,基本思想：對 任選一個初始點 及初始步長 ，通過比較這兩點函數(shù)值的大小，確定第三點位置，比較這三點的函數(shù)值大小，確定是否為“高低高”形態(tài),步驟,1）選定初始點a1，初始步長h=h0，計算y1=f(a1)和y2=f(a1+h,2）比較y1和y2,a）如果y1y2，向右前進，加大步長h=2h0，轉(zhuǎn)（3）向前； b）如果y1y2，向左后退， h=-2h0，將a1和a2,y1和y2的值互換。轉(zhuǎn)（3）向后探測； c）如果y1=y2，極小點在a1和a1+h之間,3）

4、產(chǎn)生新的探測點a3=a2+h，y3=f(a3,4）比較函數(shù)值y2和y3,a）如果y2y3 ，加大步長h=2h，a1=a2,a2=a3,轉(zhuǎn)（3）繼續(xù)探測； b）如果y2y3，則初始區(qū)間得到： a=mina1,a3,b=maxa1,a3，函數(shù)最小值所在區(qū)間為a,b,前進搜索步驟表,后退搜索步驟表,3）搜索區(qū)間外推法程序框圖,是,否,是,是,否,練習(xí) 確定 的初始搜索區(qū)間,得區(qū)間,得區(qū)間,2）取,解：1）取,2、區(qū)間消去法原理,基本思想,3、一維搜索方法分類,根據(jù)插入點位置的確定方法，可以把一維搜索法分成兩大類,試探法：即按照某種規(guī)律來確定區(qū)間內(nèi)插入點的位置，如黃金分割法，裴波納契法等。 裴波納契數(shù)

5、列：1、1、2、3、5、8、13、21、34、55、89、144,插值法（函數(shù)逼近法）：通過構(gòu)造插值函數(shù)來逼近原函數(shù)，用插值函數(shù)的極小點作為區(qū)間的插入點，如二次插值法，三次插值法等,第三節(jié)一維搜索的試探方法,1、前提,函數(shù)在區(qū)間 上是單谷函數(shù),2、點的插入原則,1）要求插入點 的位置相對于區(qū)間,兩端點具有對稱性,2）要求保留下來的區(qū)間內(nèi)再插入一點所形成的新三段具有相同的比例分布,3、點位置的確定方法,結(jié)論：所謂黃金分割是指將一線段分成兩段的方法，使整段長與較長段的長度比值等于較長段與較短段長度的比值即,兩內(nèi)分點值,4、黃金分割法的搜索過程,1）給出初始搜索區(qū)間 及收斂精度 ，將 賦以,2）按坐

6、標(biāo)點計算公式計算 并計算其對應(yīng)的函數(shù)值,3）根據(jù)區(qū)間消去法原理縮短搜索區(qū)間。為了能用原來的坐標(biāo)點計算公式，進行區(qū)間名稱的代換，并在保留區(qū)間中計算一個新的試驗點及其函數(shù)值。 （4）檢查區(qū)間是否縮短到足夠小和函數(shù)值收斂到足夠近，如果條件不滿足返回到步驟（2）。 （5）如果條件滿足，則取最后兩試驗點的平均值作為極小點的數(shù)值近似解,縮短區(qū)間的總次數(shù)（迭代次數(shù),5、黃金分割法程序框圖,給定,也可采用迭代次數(shù)是否大于或等于 k 作終止準(zhǔn)則,6、舉例,對函數(shù),當(dāng)給定搜索區(qū)間,時，試用黃金分割法求極小點,四、一維搜索的插值方法,在某一確定的區(qū)間內(nèi)尋求函數(shù)的極小點位置，雖然沒有函數(shù)表達式，但能夠給出若干點處的函

7、數(shù)值?？梢愿鶕?jù)這些點處的函數(shù)值，利用插值方法建立函數(shù)的某種近似表達式，進而求出函數(shù)的極小點，并用它作為原來函數(shù)極小點的最小值，這種方法稱作插值方法，又叫函數(shù)逼近法,試探法（如黃金分割法）與插值法的比較,相同點：兩種方法都是利用區(qū)間消去法原理將初始搜索區(qū)間不斷縮短，求得極小值的數(shù)值近似解,試探法：試驗點是按照某種個特定的規(guī)律確定；不考慮函數(shù)值的分布,不同點：表現(xiàn)在試驗點（插入點）位置的確定方法不同,插值法：試驗點是按照函數(shù)值近似分布的極小點確定；利用了函數(shù)值本身及其導(dǎo)數(shù)信息,1、牛頓法（切線法,對于一維搜索函數(shù) ，假定已經(jīng)給出極小點的一個較好的近似點 ，在 點附近用一個二次函數(shù) 來逼近函數(shù),然后

8、以該二次函數(shù) 的極小點作為 極小點的一個新的近似點 。根據(jù)極值必要條件,牛頓法的幾何解釋,在上圖中，在 處用一拋物線 代替曲線 ，相當(dāng)于用一斜線 代替 。這樣各個近似點是通過對 作切線求得與 軸的交點找到，故牛頓法又稱為切線法,牛頓法的計算步驟,例題,給定,試用,牛頓法求其極小點,解：1）給定初始點,控制誤差,2,3,4,重復(fù)上邊的過程，進行迭代，直到,為止。可得到計算結(jié)果如下表,優(yōu)點：收斂速度快,缺點：每一點都要進行二階導(dǎo)數(shù)，工作量大,當(dāng)用數(shù)值微分代替二階導(dǎo)數(shù)，由于舍入誤差會影響迭代速度； 要求初始點離極小點不太遠(yuǎn)，否則有可能使極小化發(fā)散或收斂到非極小點,牛頓法的特點,二次插值法（拋物線法,基本思想：利用目標(biāo)函數(shù)在不同3點的函數(shù)值構(gòu)成一個與原函數(shù) 相近似的二次多項式 ，以函數(shù) 的極值點 （即