第三章一維搜索方法ppt課件

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

2、是各種最優(yōu)化方法的一種基本過程。這一過程是各種最優(yōu)化方法的一種基本過程。)(kS)1( kX)(kX3.1 3.1 搜索區(qū)間的確定搜索區(qū)間的確定根據(jù)函數(shù)的變化情況，可將區(qū)間分為單峰區(qū)間和多峰區(qū)間。根據(jù)函數(shù)的變化情況，可將區(qū)間分為單峰區(qū)間和多峰區(qū)間。所謂單峰區(qū)間，就是在該區(qū)間內(nèi)的函數(shù)變化只有一個峰值，所謂單峰區(qū)間，就是在該區(qū)間內(nèi)的函數(shù)變化只有一個峰值，即函數(shù)的極小值。即函數(shù)的極小值。即在單峰區(qū)間內(nèi)的極小值點即在單峰區(qū)間內(nèi)的極小值點X* 的左側(cè)：函數(shù)呈下降趨勢，的左側(cè)：函數(shù)呈下降趨勢，而在單峰區(qū)間內(nèi)的極小值點而在單峰區(qū)間內(nèi)的極小值點X* 的右側(cè)：函數(shù)呈上升趨勢。的右側(cè)：函數(shù)呈上升趨勢。也就是說，單

3、峰區(qū)間的函數(shù)值呈也就是說，單峰區(qū)間的函數(shù)值呈“高高-低低-高高的變化特征。的變化特征。3.1 3.1 搜索區(qū)間的確定搜索區(qū)間的確定O f (a) b x* x a 目前在一維優(yōu)化搜索中確定單峰區(qū)間常用的方法是進(jìn)退試算法。 進(jìn)退試算法的基本思想為： 1) 按照一定的規(guī)律給出若干試算點， 2) 依次比較各試算點的函數(shù)值的大小， 3) 直到找到相鄰三點函數(shù)值按“高-低-高” 變化的單峰區(qū)間為止3.1 3.1 搜索區(qū)間的確定搜索區(qū)間的確定進(jìn)退試算法的運算步驟如下：(2)將將0及及0+h 代入目標(biāo)函數(shù)代入目標(biāo)函數(shù) f(x) 進(jìn)行計算并比較大小進(jìn)行計算并比較大小(1)給定初始點給定初始點0和初始步長和初始

4、步長h3.1 3.1 搜索區(qū)間的確定搜索區(qū)間的確定 假設(shè)假設(shè) ，則所計算的相鄰三，則所計算的相鄰三點點 的函數(shù)值已具的函數(shù)值已具“高高-低低-高高特征，這時可確定特征，這時可確定 搜索區(qū)間搜索區(qū)間(3)假設(shè) ，則表明極小點在試算點 的右側(cè)，需做前進(jìn)試算。00()()ffh00()(3 )fhfh00, 3abh否則，將步長再加倍，并重復(fù)上述運算。否則，將步長再加倍，并重復(fù)上述運算。3.1 3.1 搜索區(qū)間的確定搜索區(qū)間的確定 在做前進(jìn)運算時，為加速計算，可將步長在做前進(jìn)運算時，為加速計算，可將步長h 增加增加2倍，并取計算新點為倍，并取計算新點為0+h+2h=0+3h(4)假設(shè) ，則表明極小點

5、在試算點 的左側(cè)，需做后退試算。 在做后退運算時，應(yīng)將步長變?yōu)?h ，并從 點出 發(fā)，得到后退點為 假設(shè) ，則搜索區(qū)間可取為00()()ffh00()()fhf00, ahbh00h否則，將步長加倍，繼續(xù)后退，重復(fù)上述步否則，將步長加倍，繼續(xù)后退，重復(fù)上述步驟，直到滿足單峰區(qū)間條件為止。驟，直到滿足單峰區(qū)間條件為止。3.1 3.1 搜索區(qū)間的確定搜索區(qū)間的確定f(b1)f(a1)f(b1)f(a1)f(b1)af(a1) 搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，找到極小點的數(shù)值近似解。找到極小點的數(shù)值近似解。 假定在搜索區(qū)間內(nèi)假定在搜

6、索區(qū)間內(nèi)a,b 任取兩點任取兩點a1、b1,且且a1f2 f1f2 f1=f2 f(x) f(x) f(x) f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1b1baabab b1 b1(1)f1f2, 新區(qū)間為新區(qū)間為a1,b;(3)如如f1=f2, 新區(qū)間為新區(qū)間為a1,b112ff1 , a b對于上述縮短后的新區(qū)間，可在其內(nèi)再取一個新點，然后對于上述縮短后的新區(qū)間，可在其內(nèi)再取一個新點，然后將此點和該區(qū)間內(nèi)剩下的那一點進(jìn)行函數(shù)值大小的比較，將此點和該區(qū)間內(nèi)剩下的那一點進(jìn)行函數(shù)值大小的比較，以再次按照上述方法，進(jìn)一步縮短區(qū)間，這樣不斷進(jìn)行下以再次按照上述方法，進(jìn)

7、一步縮短區(qū)間，這樣不斷進(jìn)行下去，直到所保留的區(qū)間縮小到給定的誤差范圍內(nèi)，而得到去，直到所保留的區(qū)間縮小到給定的誤差范圍內(nèi)，而得到近似最優(yōu)解。近似最優(yōu)解。新區(qū)間為新區(qū)間為111222(1)(),( )(),()aabaff aaabaff aab a2a1 a2a a1f(a1)f(a2)f(a2)f(a1)b一、適用范圍一、適用范圍 適用于適用于a,ba,b區(qū)間上的任何單谷函數(shù)求極小值區(qū)間上的任何單谷函數(shù)求極小值問題。對函數(shù)除要求問題。對函數(shù)除要求“單谷外不作其他要求單谷外不作其他要求，甚至可以不連續(xù)。適應(yīng)面相當(dāng)廣。基本原理，甚至可以不連續(xù)。適應(yīng)面相當(dāng)廣?；驹頌閰^(qū)間消去法為區(qū)間消去法3.3

8、 3.3 黃金分割法黃金分割法黃金分割法插入兩點：黃金分割法插入兩點：ab2111a213(1)221510.61823.3 3.3 黃金分割法黃金分割法ab黃金分割法程序框圖黃金分割法程序框圖 開開 始始輸入輸入a, b, , 120.382()0.618()xabaxaba12( )()f xf x22121111,0.382(),( )bx xx ffxabaff x11212222,0.618(),()ax xxffxabaff x*0.5(),()xabff x結(jié)結(jié) 束束例例 3-1 用黃金分割法求函數(shù)用黃金分割法求函數(shù)f(x)=3x3-4x+2的極小點，的極小點， 初始點初始點 x

9、0=0, 步長步長h=1,精度精度 =0.2。解：解：1確定初始區(qū)間確定初始區(qū)間 x1=x0=0, f1=f(x1)=2 x2=x0+h=0+1=1 f2=f(x2)=1 由于由于f1f2, 應(yīng)繼續(xù)向前探測應(yīng)繼續(xù)向前探測 x3= x0+2h=0+2=2 f3=f(x3)=18 由于由于f2f3,可知初始區(qū)間已經(jīng)找到，即可知初始區(qū)間已經(jīng)找到，即 a,b=x1,x3=0,23.3 3.3 黃金分割法黃金分割法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

10、=2.72 由于由于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+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ū)間： 令令 x1=x2=0.764, f1=f2=0.282 x2=0.472+0.618 (1.236-0.472)=0.944, f2=

11、0.747 由于由于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ū)間：令令 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=0.584, 0.764因為因為

12、b-a=0.764-0.584=0.180.2, 停止迭代。停止迭代。黃金分割法求的的極小點與極小值：黃金分割法求的的極小點與極小值： x=0.5 (0.584+0.764)=0.674, f(x)=0.2223.3 3.3 黃金分割法黃金分割法求導(dǎo)運算求的極小點與極小值：求導(dǎo)運算求的極小點與極小值： x=0.667, f(x)=0.222一、牛頓法一、牛頓法3.4 3.4 插值方法插值方法利用一點的函數(shù)值、利用一點的函數(shù)值、一階導(dǎo)數(shù)以及二階一階導(dǎo)數(shù)以及二階導(dǎo)數(shù)構(gòu)造二次多項導(dǎo)數(shù)構(gòu)造二次多項式。用構(gòu)造的二次式。用構(gòu)造的二次多項式的極小點作多項式的極小點作為原函數(shù)極小點的為原函數(shù)極小點的近似。近似

13、。一、牛頓法一、牛頓法設(shè)設(shè)f(a)為一個連續(xù)可微的函數(shù)，則在點為一個連續(xù)可微的函數(shù)，則在點a0附附近進(jìn)行泰勒展開并保留到二次項：近進(jìn)行泰勒展開并保留到二次項：2000001( )( )()()()()()2f aaf afaaafaaa1()0a用二次函數(shù)用二次函數(shù)(a)的極小點的極小點a1作為作為f(a)極小點的一個近似極小點的一個近似點。根據(jù)極值必要條件點。根據(jù)極值必要條件:3.4 3.4 插值方法插值方法0010()()()0fafaaa即即0100()()faaafa依此類推可得牛頓迭代公式：依此類推可得牛頓迭代公式：1()()kkkkfaaafa一、牛頓法一、牛頓法3.4 3.4 插

14、值方法插值方法在在a0處用一拋物線處用一拋物線(a)代替曲線代替曲線f(a)，相當(dāng)于用一斜直線相當(dāng)于用一斜直線 ( a ) 代 替 曲 線代 替 曲 線f(a) 。這樣各個。這樣各個近似點是通過對作近似點是通過對作f(a)切線求得與軸切線求得與軸的交點找到的，所的交點找到的，所以，有時，牛頓法以，有時，牛頓法又稱作切線法。又稱作切線法。1kkaa牛頓法程序框圖牛頓法程序框圖 開開 始始計算計算 ，*1kaa給定初始點給定初始點 ，誤差，誤差 ,令令k=00a( ),( )kkff計算計算 ，1()()kkkkfaaafa1kk結(jié)結(jié) 束束數(shù)值數(shù)值 k 0 1 2 3 4 3 5.1667 4.3

15、3474 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 4.00066 4.00059 2.1667 0.83196 0.29514 0.03894 0.00007 41664234xxxxxFkxkxFkxF 給定初始點給定初始點x0=3，=0.001，計算公式：，計算公式：1()()kkkkF xxxFx 1224122 xxxF函數(shù)的二階導(dǎo)數(shù)：函數(shù)的二階導(dǎo)數(shù)： 161212423xxxxF解：解：

16、函數(shù)的一階導(dǎo)數(shù)：函數(shù)的一階導(dǎo)數(shù)：3.4 3.4 插值方法插值方法1kx 優(yōu)點：優(yōu)點：1收斂速度快。收斂速度快。 缺點：缺點：1要計算函數(shù)的一階和二階導(dǎo)數(shù)，增加每次要計算函數(shù)的一階和二階導(dǎo)數(shù)，增加每次 迭代的工作量。迭代的工作量。 2數(shù)值微分計算函數(shù)二階導(dǎo)數(shù)，舍入誤差將數(shù)值微分計算函數(shù)二階導(dǎo)數(shù)，舍入誤差將 嚴(yán)重影響牛頓法的收斂速度，嚴(yán)重影響牛頓法的收斂速度， f (x)的值越的值越 小問題越嚴(yán)重。小問題越嚴(yán)重。 3牛頓法要求初始點離極小點不太遠(yuǎn)，否則牛頓法要求初始點離極小點不太遠(yuǎn)，否則 可能使極小化序列發(fā)散或收斂到非極小點。可能使極小化序列發(fā)散或收斂到非極小點。一、牛頓法一、牛頓法3.4 3.4

17、 插值方法插值方法二、二次插值法拋物線法）二、二次插值法拋物線法）a1af(a)2a3a1ff23fa*在給定的單峰區(qū)間中，利用目標(biāo)函數(shù)上的三個點來構(gòu)造一個二次插值函數(shù)，以近似地表達(dá)原目標(biāo)函數(shù)，并求這個插值函數(shù)的極小點近似作為原目標(biāo)函數(shù)的極小點。( )f aap3.4 3.4 插值方法插值方法2( )=ABCp aB=-2Cpay0aap1a1a2apa3ay0a*y1y2ypy3a1a2apa*y1y2ypyp1apap1a1a2apa3ay0a*y1y2ypy3a2a3ay0a*y2ypy3yp1211112222223333p()ABCp()ABCp()ABCfff構(gòu)造的二次插值函數(shù)曲線

18、通過原函數(shù)上的三個點構(gòu)造的二次插值函數(shù)曲線通過原函數(shù)上的三個點: : 解得系數(shù)解得系數(shù)222222231312123122331231312123122331()()()()()()()()()()()()fffBfffC 2222222313121232313121231 ()()()22 ()()()pBfffCfff 二、二次插值法拋物線法）二、二次插值法拋物線法）3.4 3.4 插值方法插值方法2pyy二次插值法程序框圖二次插值法程序框圖 開開 始始計算計算 ，*2min,pyyy給定給定 ,123123a a a y y y ,ppy縮短區(qū)間縮短區(qū)間名稱置換名稱置換結(jié)結(jié) 束束a1a2apa3ay0a*y1y2ypy3a1a2 apa3a0a*yy1y2ypy3*2min,pyyy二次插值法程序編制換名方法二次插值法程序編制換名方法(1)(1)1) a2ap y2yp y2ap y2 yp y2yp（1 1二次插值法只要求二次插值法只要求f(x)f(x)連續(xù)，不要求其