一維搜索方法和區(qū)間消去法原理

1、一維搜索方法和區(qū)間消去法原理 第三章 一維搜索方法 3.3 一維搜索的試探法 3.1 搜索區(qū)間的確定 3.2 區(qū)間消去法原理 3.4 一維搜索的插值法 一維搜索方法和區(qū)間消去法原理 求解求解最優(yōu)解的過(guò)程，稱(chēng)為最優(yōu)解的過(guò)程，稱(chēng)為( (一維一維 搜索搜索) )，所使用的方法稱(chēng)為，所使用的方法稱(chēng)為。 )(Xf 由前由前可知，求某目標(biāo)函數(shù)的最優(yōu)值時(shí)，迭代過(guò)可知，求某目標(biāo)函數(shù)的最優(yōu)值時(shí)，迭代過(guò) 程每一步的格式都是從某一定點(diǎn)程每一步的格式都是從某一定點(diǎn) 出發(fā)，沿著某一使目出發(fā)，沿著某一使目 標(biāo)函數(shù)下降的規(guī)定方向標(biāo)函數(shù)下降的規(guī)定方向 搜索，以找出此方向的極小點(diǎn)搜索，以找出此方向的極小點(diǎn) 。這一過(guò)程是各種最優(yōu)

2、化方法的一種。這一過(guò)程是各種最優(yōu)化方法的一種。 )(k S )1( k X )(k X 一般一般： 首先確定一個(gè)包含函數(shù)極小點(diǎn)的初始區(qū)間，即確定首先確定一個(gè)包含函數(shù)極小點(diǎn)的初始區(qū)間，即確定 函數(shù)的搜索區(qū)間，該區(qū)間必須是單峰區(qū)間；函數(shù)的搜索區(qū)間，該區(qū)間必須是單峰區(qū)間； 然后采用縮小區(qū)間或插值逼近的方法得到最優(yōu)步長(zhǎng)，然后采用縮小區(qū)間或插值逼近的方法得到最優(yōu)步長(zhǎng)， 最終求出該搜索區(qū)間內(nèi)的一維極小點(diǎn)。最終求出該搜索區(qū)間內(nèi)的一維極小點(diǎn)。 3.1 3.1 搜索區(qū)間的確定搜索區(qū)間的確定 一維搜索方法和區(qū)間消去法原理 根據(jù)函數(shù)的變化情況，可將根據(jù)函數(shù)的變化情況，可將分為單峰區(qū)間和多峰區(qū)間。分為單峰區(qū)間和多峰區(qū)

3、間。 所謂所謂，就是在該區(qū)間內(nèi)的函數(shù)變化只有一個(gè)峰值，就是在該區(qū)間內(nèi)的函數(shù)變化只有一個(gè)峰值， 即函數(shù)的極小值。即函數(shù)的極小值。 即在即在內(nèi)的內(nèi)的的左側(cè)：函數(shù)呈的左側(cè)：函數(shù)呈， 而在而在內(nèi)的極小值點(diǎn)內(nèi)的極小值點(diǎn)X* 的右側(cè)：函數(shù)呈上升趨勢(shì)。的右側(cè)：函數(shù)呈上升趨勢(shì)。 也就是說(shuō)，也就是說(shuō)，的函數(shù)值呈的函數(shù)值呈的變化特征的變化特征。 3.1 3.1 搜索區(qū)間的確定搜索區(qū)間的確定 O f (a) b x* x a 一維搜索方法和區(qū)間消去法原理 目前在一維優(yōu)化搜索中確定單峰區(qū)間常用的方法目前在一維優(yōu)化搜索中確定單峰區(qū)間常用的方法 是進(jìn)退試算法。是進(jìn)退試算法。 為：為： 1)1) 按照一定的規(guī)律給出若干試算

4、點(diǎn)，按照一定的規(guī)律給出若干試算點(diǎn)， 2)2) 依次比較各試算點(diǎn)的函數(shù)值的大小，依次比較各試算點(diǎn)的函數(shù)值的大小， 3) 3) 直到找到相鄰三點(diǎn)函數(shù)值按直到找到相鄰三點(diǎn)函數(shù)值按“高高- -低低- -高高” 變化的單峰區(qū)間為止變化的單峰區(qū)間為止 3.1 3.1 搜索區(qū)間的確定搜索區(qū)間的確定 一維搜索方法和區(qū)間消去法原理 進(jìn)退試算法的進(jìn)退試算法的如下：如下： (2)將將0及及0+h 代入目標(biāo)函數(shù)代入目標(biāo)函數(shù) f(x) 進(jìn)行計(jì)算并比較大小進(jìn)行計(jì)算并比較大小 (1)給定初始點(diǎn)給定初始點(diǎn)0和初始步長(zhǎng)和初始步長(zhǎng)h 3.1 3.1 搜索區(qū)間的確定搜索區(qū)間的確定 一維搜索方法和區(qū)間消去法原理 若若 ，則所計(jì)算的相

5、鄰三點(diǎn)，則所計(jì)算的相鄰三點(diǎn) 的函數(shù)值已具的函數(shù)值已具“高高-低低-高高”特征，這時(shí)可確定特征，這時(shí)可確定 搜索區(qū)間搜索區(qū)間 (3)若若 ，則表明極小點(diǎn)在試算點(diǎn)，則表明極小點(diǎn)在試算點(diǎn) 的右側(cè)，需做前進(jìn)試算。的右側(cè)，需做前進(jìn)試算。 00 ()()ffh 00 ()(3 )fhfh 00 , 3abh 否則，將步長(zhǎng)再加倍，并重復(fù)上述運(yùn)算。否則，將步長(zhǎng)再加倍，并重復(fù)上述運(yùn)算。 3.1 3.1 搜索區(qū)間的確定搜索區(qū)間的確定 在做前進(jìn)運(yùn)算時(shí)，為加速計(jì)算，可將步長(zhǎng)在做前進(jìn)運(yùn)算時(shí)，為加速計(jì)算，可將步長(zhǎng)h 增加增加2倍，并取計(jì)算新點(diǎn)為倍，并取計(jì)算新點(diǎn)為0+h+2h=0+3h 一維搜索方法和區(qū)間消去法原理 (4)

6、若若 ，則表明極小點(diǎn)在試算點(diǎn)，則表明極小點(diǎn)在試算點(diǎn) 的左側(cè)，需做后退試算。的左側(cè)，需做后退試算。 在做后退運(yùn)算時(shí)，應(yīng)將步長(zhǎng)變?yōu)樵谧龊笸诉\(yùn)算時(shí)，應(yīng)將步長(zhǎng)變?yōu)?h ，并從，并從 點(diǎn)出點(diǎn)出 發(fā)，得到后退點(diǎn)為發(fā)，得到后退點(diǎn)為 若若 ，則搜索區(qū)間可取為，則搜索區(qū)間可取為 00 ()()ffh 00 ()()fhf 00 , ahbh 0 0 h 否則，將步長(zhǎng)加倍，繼續(xù)后退，重復(fù)上述步否則，將步長(zhǎng)加倍，繼續(xù)后退，重復(fù)上述步 驟，直到滿足單峰區(qū)間條件為止。驟，直到滿足單峰區(qū)間條件為止。 3.1 3.1 搜索區(qū)間的確定搜索區(qū)間的確定 一維搜索方法和區(qū)間消去法原理 f(b1)f(a1) f(b1) f(a1)f

7、(b1) a f(a1) 搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間， 找到極小點(diǎn)的數(shù)值近似解。找到極小點(diǎn)的數(shù)值近似解。 假定在搜索區(qū)間內(nèi)假定在搜索區(qū)間內(nèi)a,b 任取兩點(diǎn)任取兩點(diǎn)a1、b1,且且a1f2 f1f2 f1=f2 f(x) f(x) f(x) 一維搜索方法和區(qū)間消去法原理 f(a1) f(b1) f(a1) f(b1) f(a1) f(b1) a1 a1 a1b1 ba a b a b b1 b1 (1)f1f2, 新區(qū)間為新區(qū)間為a1,b; (3)如如f1=f2, 新區(qū)間為新區(qū)間為a1,b1 12 ff 1 , a b 對(duì)于

8、上述縮短后的新區(qū)間，可在其內(nèi)再取一個(gè)新點(diǎn)，然后對(duì)于上述縮短后的新區(qū)間，可在其內(nèi)再取一個(gè)新點(diǎn)，然后 將此點(diǎn)和該區(qū)間內(nèi)剩下的那一點(diǎn)進(jìn)行函數(shù)值大小的比較，將此點(diǎn)和該區(qū)間內(nèi)剩下的那一點(diǎn)進(jìn)行函數(shù)值大小的比較， 以再次按照上述方法，進(jìn)一步縮短區(qū)間，這樣不斷進(jìn)行下以再次按照上述方法，進(jìn)一步縮短區(qū)間，這樣不斷進(jìn)行下 去，直到所保留的區(qū)間縮小到給定的誤差范圍內(nèi)，而得到去，直到所保留的區(qū)間縮小到給定的誤差范圍內(nèi)，而得到 近似最優(yōu)解。近似最優(yōu)解。 新區(qū)間為新區(qū)間為 一維搜索方法和區(qū)間消去法原理 111 222 (1)(),( ) (),() aabaff a aabaff a ab a2a1 a2a a1 f(a1

9、) f(a2) f(a2) f(a1) b 一、適用范圍一、適用范圍 適用于適用于a,b區(qū)間上的任何單谷函數(shù)求極小值問(wèn)題。對(duì)區(qū)間上的任何單谷函數(shù)求極小值問(wèn)題。對(duì) 函數(shù)除要求函數(shù)除要求“單谷單谷”外不作其他要求，甚至可以不連外不作其他要求，甚至可以不連 續(xù)。適應(yīng)面相當(dāng)廣。基本原理為區(qū)間消去法續(xù)。適應(yīng)面相當(dāng)廣。基本原理為區(qū)間消去法 3.3 3.3 黃金分割法黃金分割法 黃金分割法插入兩點(diǎn)：黃金分割法插入兩點(diǎn)： 一維搜索方法和區(qū)間消去法原理 ab 2 1 1 1 a 2 1 3 (1) 2 2 1 51 0.618 2 3.3 3.3 黃金分割法黃金分割法 一維搜索方法和區(qū)間消去法原理 ab 黃金分

10、割法程序框圖黃金分割法程序框圖 開(kāi)開(kāi) 始始 輸入輸入a, b, , 1 2 0.382() 0.618() xaba xaba 12 ( )()f xf x 22121 111 , 0.382(),( ) bx xx ff xabaff x 11212 222 , 0.618(),() ax xxff xabaff x * 0.5(),()xabff x 結(jié)結(jié) 束束 一維搜索方法和區(qū)間消去法原理 例例 3-1 用黃金分割法求函數(shù)用黃金分割法求函數(shù)f(x)=3x3-4x+2的極小點(diǎn)，的極小點(diǎn)， 初始點(diǎn)初始點(diǎn) x0=0, 步長(zhǎng)步長(zhǎng)h=1,精度精度 =0.2。 解：解： 1）確定初始區(qū)間）確定初始區(qū)

11、間 x1=x0=0, f1=f(x1)=2 x2=x0+h=0+1=1 f2=f(x2)=1 由于由于f1f2, 應(yīng)繼續(xù)向前探測(cè)應(yīng)繼續(xù)向前探測(cè) x3= x0+2h=0+2=2 f3=f(x3)=18 由于由于f2f3,可知初始區(qū)間已經(jīng)找到，即可知初始區(qū)間已經(jīng)找到，即 a,b=x1,x3=0,2 3.3 3.3 黃金分割法黃金分割法 一維搜索方法和區(qū)間消去法原理 2）用黃金分割法縮小區(qū)間）用黃金分割法縮小區(qū)間 第一次縮小區(qū)間：第一次縮小區(qū)間： x1=0+0.382(2-0)=0.764, f1=0.282 x2=0+0.618(2-0)=1.236, f2=2.72 由于由于f10.2,應(yīng)繼續(xù)縮

12、小區(qū)間應(yīng)繼續(xù)縮小區(qū)間 3.3 3.3 黃金分割法黃金分割法 第二次縮小區(qū)間：第二次縮小區(qū)間： 令令 x2=x1=0.764, f2=f1=0.282 x1=0+0.382 (1.236-0)=0.472, f1=0.317 由于由于f1f2, 故新區(qū)間故新區(qū)間a,b=x1,b=0.472, 1.236 由于由于 b-a=1.236-0.472=0.7640.2, 應(yīng)繼續(xù)縮小區(qū)間應(yīng)繼續(xù)縮小區(qū)間 一維搜索方法和區(qū)間消去法原理 第三次縮小區(qū)間：第三次縮小區(qū)間： 令令 x1=x2=0.764, f1=f2=0.282 x2=0.472+0.618 (1.236-0.472)=0.944, f2=0.7

13、47 由于由于f10.2, 應(yīng)繼續(xù)縮小區(qū)間。應(yīng)繼續(xù)縮小區(qū)間。 3.3 3.3 黃金分割法黃金分割法 第四次縮小區(qū)間：第四次縮小區(qū)間： 令令 x2=x1=0.764, f2=f1=0.282 x1=0.472+0.382 (0.944-0.472)=0.652, f1=0.223 由于由于f10.2, 應(yīng)繼續(xù)縮小區(qū)間。應(yīng)繼續(xù)縮小區(qū)間。 一維搜索方法和區(qū)間消去法原理 第五次縮小區(qū)間：第五次縮小區(qū)間： 令令 x2=x1=0.652, f2=f1=0.223 x1=0.472+0.382 (0.764-0.472)=0.584, f1=0.262 由于由于f1f2, 故新區(qū)間故新區(qū)間a,b=x1,b=

14、0.584, 0.764 因?yàn)橐驗(yàn)?b-a=0.764-0.584=0.180.2, 停止迭代。停止迭代。 黃金分割法求的的極小點(diǎn)與極小值：黃金分割法求的的極小點(diǎn)與極小值： x=0.5 (0.584+0.764)=0.674, f(x)=0.222 3.3 3.3 黃金分割法黃金分割法 求導(dǎo)運(yùn)算求的極小點(diǎn)與極小值：求導(dǎo)運(yùn)算求的極小點(diǎn)與極小值： x=0.667, f(x)=0.222 一維搜索方法和區(qū)間消去法原理 一、牛頓法一、牛頓法 3.4 3.4 插值方法插值方法 利用一點(diǎn)的函數(shù)值、利用一點(diǎn)的函數(shù)值、 一階導(dǎo)數(shù)以及二階一階導(dǎo)數(shù)以及二階 導(dǎo)數(shù)構(gòu)造二次多項(xiàng)導(dǎo)數(shù)構(gòu)造二次多項(xiàng) 式。用構(gòu)造的二次式。用

15、構(gòu)造的二次 多項(xiàng)式的極小點(diǎn)作多項(xiàng)式的極小點(diǎn)作 為原函數(shù)極小點(diǎn)的為原函數(shù)極小點(diǎn)的 近似。近似。 一維搜索方法和區(qū)間消去法原理 一、牛頓法一、牛頓法 設(shè)設(shè)f(a)為一個(gè)連續(xù)可微的函數(shù)，則在點(diǎn)為一個(gè)連續(xù)可微的函數(shù)，則在點(diǎn)a0附近附近 進(jìn)行泰勒展開(kāi)并保留到二次項(xiàng)：進(jìn)行泰勒展開(kāi)并保留到二次項(xiàng)： 2 00000 1 ( )( )()()()()() 2 f aaf afaaafaaa 1 ()0a 用二次函數(shù)用二次函數(shù)(a)的極小點(diǎn)的極小點(diǎn)a1 作為作為f(a)極小點(diǎn)的一個(gè)近似極小點(diǎn)的一個(gè)近似 點(diǎn)。根據(jù)極值必要條件點(diǎn)。根據(jù)極值必要條件: 3.4 3.4 插值方法插值方法 一維搜索方法和區(qū)間消去法原理 00

16、10 ()()()0fafaaa 即即 0 10 0 () () fa aa fa 依此類(lèi)推可得牛頓迭代公式：依此類(lèi)推可得牛頓迭代公式： 1 () () k kk k fa aa fa 一、牛頓法一、牛頓法 3.4 3.4 插值方法插值方法 一維搜索方法和區(qū)間消去法原理 在在a0處用一拋物線處用一拋物線 (a)代替曲線代替曲線f(a)， 相當(dāng)于用一斜直線相當(dāng)于用一斜直線 (a)代替曲線代替曲線f(a) 。這樣各個(gè)近似點(diǎn)。這樣各個(gè)近似點(diǎn) 是通過(guò)對(duì)作是通過(guò)對(duì)作f(a)切切 線求得與軸的交點(diǎn)線求得與軸的交點(diǎn) 找到的，所以，有找到的，所以，有 時(shí)，牛頓法又稱(chēng)作時(shí)，牛頓法又稱(chēng)作 切線法。切線法。 一維搜

17、索方法和區(qū)間消去法原理 1kk aa 牛頓法牛頓法 開(kāi)開(kāi) 始始 計(jì)算計(jì)算 ， * 1k aa 給定初始點(diǎn)給定初始點(diǎn) ，誤差，誤差 , 令令k=0 0 a ( ),( ) kk ff 計(jì)算計(jì)算 ， 1 () () k kk k fa aa fa 1kk 結(jié)結(jié) 束束 一維搜索方法和區(qū)間消去法原理 數(shù)值數(shù)值 k 0 1 2 3 4 3 5.1667 4.33474 4.03960 4.00066 -52 153.35183 32.30199 3.38299 0.00551 24 184.33332 109.44586 86.86992 84.04720 5.1667 4.33474 4.03960

18、4.00066 4.00059 2.1667 0.83196 0.29514 0.03894 0.00007 41664 234 xxxxxF k x k x F k x F 給定初始點(diǎn)給定初始點(diǎn)x0=3，=0.001，計(jì)算公式：，計(jì)算公式： 1 () () k kk k F x xx Fx 122412 2 xxxF函數(shù)的二階導(dǎo)數(shù)：函數(shù)的二階導(dǎo)數(shù)： 1612124 23 xxxxF解：解： 函數(shù)的一階導(dǎo)數(shù)：函數(shù)的一階導(dǎo)數(shù)： 3.4 3.4 插值方法插值方法 1k x 一維搜索方法和區(qū)間消去法原理 優(yōu)點(diǎn)：優(yōu)點(diǎn)：1）收斂速度快。）收斂速度快。 缺點(diǎn)：缺點(diǎn)：1）要計(jì)算函數(shù)的一階和二階導(dǎo)數(shù)，增加每次

19、）要計(jì)算函數(shù)的一階和二階導(dǎo)數(shù)，增加每次 迭代的工作量。迭代的工作量。 2）數(shù)值微分計(jì)算函數(shù)二階導(dǎo)數(shù)，舍入誤差將）數(shù)值微分計(jì)算函數(shù)二階導(dǎo)數(shù)，舍入誤差將 嚴(yán)重影響牛頓法的收斂速度，嚴(yán)重影響牛頓法的收斂速度， f (x)的值越的值越 小問(wèn)題越嚴(yán)重。小問(wèn)題越嚴(yán)重。 3）牛頓法要求初始點(diǎn)離極小點(diǎn)不太遠(yuǎn)，否則）牛頓法要求初始點(diǎn)離極小點(diǎn)不太遠(yuǎn)，否則 可能使極小化序列發(fā)散或收斂到非極小點(diǎn)?？赡苁箻O小化序列發(fā)散或收斂到非極小點(diǎn)。 一、牛頓法一、牛頓法 3.4 3.4 插值方法插值方法 一維搜索方法和區(qū)間消去法原理 二、二次插值法（二、二次插值法（） a1a f(a) 2 a 3 a 1 f f2 3 f a*

20、在給定的單峰區(qū)間中，利用目標(biāo)函數(shù)上的三個(gè)點(diǎn)來(lái)構(gòu)在給定的單峰區(qū)間中，利用目標(biāo)函數(shù)上的三個(gè)點(diǎn)來(lái)構(gòu) 造一個(gè)二次插值函數(shù)，以近似地表達(dá)原目標(biāo)函數(shù)，并造一個(gè)二次插值函數(shù)，以近似地表達(dá)原目標(biāo)函數(shù)，并 求這個(gè)插值函數(shù)的極小點(diǎn)近似作為原目標(biāo)函數(shù)的極小點(diǎn)。求這個(gè)插值函數(shù)的極小點(diǎn)近似作為原目標(biāo)函數(shù)的極小點(diǎn)。 ( )f a ap 3.4 3.4 插值方法插值方法 2 ( )=ABCp a B =- 2C p a 一維搜索方法和區(qū)間消去法原理 y 0 a ap1 a1 a2 ap a3 a y 0 a* y1 y2 yp y3 a1 a2 apa* y1 y2 yp yp1 一維搜索方法和區(qū)間消去法原理 apap1

21、a1a2ap a3 a y 0 a* y1 y2 yp y3 a2a3 a y 0 a* y2 yp y3 yp1 一維搜索方法和區(qū)間消去法原理 2 1111 2 2222 2 3333 p()ABC p()ABC p()ABC f f f 構(gòu)造的構(gòu)造的上的三個(gè)點(diǎn)上的三個(gè)點(diǎn): : 解得系數(shù)解得系數(shù) 222222 231312123 122331 231312123 122331 ()()() ()()() ()()() ()()() fff B fff C 222222 231312123 231312123 1 ()()() 22 ()()() p Bfff Cfff 二、二次插值法（二、二次插值法（） 3.4 3.4 插值方法插值方法 一維搜索方法和區(qū)間消去法原理 2p yy 二次插值法二次插值法 開(kāi)開(kāi) 始始 計(jì)算計(jì)算 ， * 2 min, p yyy 給定給定 , 123123 a a a y y y , pp y 縮短區(qū)間縮短區(qū)間 名稱(chēng)置換名稱(chēng)置換 結(jié)結(jié) 束束 一維搜索方法和區(qū)間消去法原理 a1a2ap a3 a y 0 a* y1 y2 yp y3 a1a2apa3 a 0 a* y y1 y2 yp y3 * 2 min, p yy y 一維搜索方法和區(qū)間消去法原理 二次插值法程序編制換名方法二次插值法程序編制換名方法(1)(1) 1)