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

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

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

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

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

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

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

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

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