最優(yōu)化_第3章 一維搜索方法

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

2、 首先首先確定確定一個(gè)包含函數(shù)極小點(diǎn)的一個(gè)包含函數(shù)極小點(diǎn)的初始區(qū)間初始區(qū)間，即，即確定確定 函數(shù)的搜索區(qū)間，該區(qū)間必須是函數(shù)的搜索區(qū)間，該區(qū)間必須是單峰區(qū)間單峰區(qū)間； 然后采用縮小區(qū)間或插值逼近的方法然后采用縮小區(qū)間或插值逼近的方法得到得到最優(yōu)步長(zhǎng)最優(yōu)步長(zhǎng)， 最終求出該搜索區(qū)間內(nèi)的最終求出該搜索區(qū)間內(nèi)的一維極小點(diǎn)一維極小點(diǎn)。3.1 3.1 搜索區(qū)間的確定搜索區(qū)間的確定根據(jù)函數(shù)的變化情況，可將根據(jù)函數(shù)的變化情況，可將分為分為單峰區(qū)間單峰區(qū)間和和多峰區(qū)間多峰區(qū)間。所謂所謂，就是在該區(qū)間內(nèi)的函數(shù)變化只有一個(gè)峰值，就是在該區(qū)間內(nèi)的函數(shù)變化只有一個(gè)峰值，即函數(shù)的極小值。即函數(shù)的極小值。即在即在內(nèi)的內(nèi)的的

3、的左側(cè)左側(cè)：函數(shù)呈：函數(shù)呈，而在而在內(nèi)的內(nèi)的極小值點(diǎn)極小值點(diǎn)X* 的的右側(cè)右側(cè)：函數(shù)呈：函數(shù)呈上升趨勢(shì)上升趨勢(shì)。也就是說(shuō)，也就是說(shuō)，的函數(shù)值呈的函數(shù)值呈的變化特征的變化特征。3.1 3.1 搜索區(qū)間的確定搜索區(qū)間的確定x*abx0f(x)目前在一維優(yōu)化搜索中確定目前在一維優(yōu)化搜索中確定單峰區(qū)間單峰區(qū)間常用的方法常用的方法是是進(jìn)退試算法進(jìn)退試算法。 為：為： 1)1) 按照一定的規(guī)律給出按照一定的規(guī)律給出若干試算點(diǎn)若干試算點(diǎn)， 2)2) 依次比較各依次比較各試算點(diǎn)的函數(shù)值試算點(diǎn)的函數(shù)值的大小，的大小， 3) 3) 直到找到直到找到相鄰三點(diǎn)相鄰三點(diǎn)函數(shù)值按函數(shù)值按“高高- -低低- -高高” 變化

4、的變化的單峰區(qū)間單峰區(qū)間為止為止3.1 3.1 搜索區(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)h3.1 3.1 搜索區(qū)間的確定搜索區(qū)間的確定f(x)x0aba0f(a0)a0+hf(a0+h)a0+3hf(a0+3h)f(x)x0aba0-hf(a0-h)a0f(a0)a0+hf(a0+h) 若若f(0+h) f(0+3h) ，則所計(jì)算的相鄰三點(diǎn)，則所計(jì)算的相鄰三點(diǎn) 的函數(shù)值已具的函數(shù)值已具“高高-低低-高高”特征，這時(shí)可確定特征，這

5、時(shí)可確定 搜索區(qū)間搜索區(qū)間(3)若若f(0 ) f(0+h)，則表明極小點(diǎn)在試算點(diǎn)，則表明極小點(diǎn)在試算點(diǎn) 的右側(cè)，需做的右側(cè)，需做前進(jìn)試算前進(jìn)試算。00, 3abh否則，將步長(zhǎng)再加倍，并重復(fù)上述運(yùn)算。否則，將步長(zhǎng)再加倍，并重復(fù)上述運(yùn)算。3.1 3.1 搜索區(qū)間的確定搜索區(qū)間的確定 在做在做前進(jìn)運(yùn)算前進(jìn)運(yùn)算時(shí)，為加速計(jì)算，可將步長(zhǎng)時(shí)，為加速計(jì)算，可將步長(zhǎng)h 增加增加2倍，并取計(jì)算新點(diǎn)為倍，并取計(jì)算新點(diǎn)為0+h+2h=0+3h(4)若若 f(0) f(0) ，則，則搜索區(qū)間搜索區(qū)間可取為可取為00, ahbh否則，將步長(zhǎng)加倍，繼續(xù)后退，重復(fù)否則，將步長(zhǎng)加倍，繼續(xù)后退，重復(fù)上述步上述步驟驟，直到滿足

6、，直到滿足單峰區(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ū)間，找到極小點(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) (1)f1f2, 新區(qū)間為新區(qū)間為a1,b(3)f1=f2, 新區(qū)間為新區(qū)間為a1,b1對(duì)于上述對(duì)于上述縮短后的新區(qū)間縮短后的新區(qū)間，可在其內(nèi)再取一個(gè)，可在其內(nèi)再取

7、一個(gè)新點(diǎn)新點(diǎn)，然后，然后將此點(diǎn)和該區(qū)間內(nèi)剩下的那一點(diǎn)進(jìn)行函數(shù)值大小的比較，將此點(diǎn)和該區(qū)間內(nèi)剩下的那一點(diǎn)進(jìn)行函數(shù)值大小的比較，以再次按照以再次按照上述方法上述方法，進(jìn)一步，進(jìn)一步縮短區(qū)間縮短區(qū)間，這樣不斷進(jìn)行下，這樣不斷進(jìn)行下去，直到去，直到所保留的區(qū)間所保留的區(qū)間縮小到給定的誤差范圍內(nèi)，而得到縮小到給定的誤差范圍內(nèi)，而得到近似最優(yōu)解近似最優(yōu)解。12ff新區(qū)間為新區(qū)間為a1, bf(b1)af(a1) a1 b1bf(b1)f(a1)a1ab b1f(b1)f(a1)a1bab1111222(1)(),( )(),()aabaff aaabaff a一、適用范圍一、適用范圍 適用于適用于a, b

8、區(qū)間上的任何區(qū)間上的任何單谷函數(shù)單谷函數(shù)求極小值問(wèn)題。對(duì)求極小值問(wèn)題。對(duì)函數(shù)除要求函數(shù)除要求“單峰單峰”外不作其他要求，甚至可以外不作其他要求，甚至可以不連不連續(xù)續(xù)。適應(yīng)面相當(dāng)廣?；驹頌?。適應(yīng)面相當(dāng)廣?；驹頌閰^(qū)間消去法區(qū)間消去法3.3 3.3 黃金分割法黃金分割法黃金分割法插入兩點(diǎn)：黃金分割法插入兩點(diǎn)：f(a2)af(a1) a1 a2bf(a2)af(a1) a1b a221510.61823.3 3.3 黃金分割法黃金分割法212ab11-13(1-)2aab黃金分割法程序框圖黃金分割法程序框圖 開開 始始輸入輸入a, b, , 120.382()0.618()xabaxaba12

9、( )()f xf x22121111,0.382(),( )bx xx ffxabaff x11212222,0.618(),()ax xxffxabaff x結(jié)結(jié) 束束*0.5(),()xabff xaf(x2)f(x1)b x1 x2b x2f(x2) x1例例 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ū)間 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è)

10、 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 黃金分割法黃金分割法f(x1)=2x1=0f(x2)=1x2=1f(x3)=18x3=2ab2）用黃金分割法縮小區(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ù)縮小區(qū)間應(yīng)繼續(xù)縮小區(qū)間3.3 3.3 黃金分割法黃金分割法f(x1)=0.282x1=0.764f(x

11、2)=2.72x2=1.236abb3.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ū)間f(x1)=0.282x1=0.764f(x2)=2.72x2=1.236abbx2f(x2)x1f(x1)a 第三次縮小區(qū)間：第三次縮小區(qū)間： 令令 x1=x2=0.764, f1=f2=

12、0.282 x2=0.472+0.618 (1.236-0.472)=0.944, f2=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.26

13、2由于由于f1f2, 故故新區(qū)間新區(qū)間a,b=x1,b=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.2223.3 3.3 黃金分割法黃金分割法求導(dǎo)運(yùn)算求導(dǎo)運(yùn)算求的極小點(diǎn)與極小值：求的極小點(diǎn)與極小值： x=0.667, f(x)=0.222一、牛頓法一、牛頓法3.4 3.4 插值方法插值方法利用一點(diǎn)的利用一點(diǎn)的函數(shù)值函數(shù)值、一階導(dǎo)數(shù)一階導(dǎo)數(shù)以及以及二階二階導(dǎo)數(shù)導(dǎo)數(shù)構(gòu)造二次多項(xiàng)構(gòu)造二次多項(xiàng)式。用構(gòu)造的二次式

14、。用構(gòu)造的二次多項(xiàng)式的極小點(diǎn)作多項(xiàng)式的極小點(diǎn)作為原函數(shù)極小點(diǎn)的為原函數(shù)極小點(diǎn)的近似。近似。x*xf(x) x20(x) x0f(x) 1(x) x1一、牛頓法一、牛頓法設(shè)設(shè)f(x)為一個(gè)連續(xù)可微的函數(shù)，則在點(diǎn)為一個(gè)連續(xù)可微的函數(shù)，則在點(diǎn)x0附近附近進(jìn)行泰勒展開并保留到二次項(xiàng)：進(jìn)行泰勒展開并保留到二次項(xiàng)：2000001( )( )()()()()()2f xxf xfxxxfxxx1( )0 x用二次函數(shù)用二次函數(shù)(x)的極小點(diǎn)的極小點(diǎn)x1作為作為f(x)極小點(diǎn)的一個(gè)近似極小點(diǎn)的一個(gè)近似點(diǎn)。根據(jù)極值必要條件點(diǎn)。根據(jù)極值必要條件:3.4 3.4 插值方法插值方法xf(x) x1x20(x) x*f

15、(x) 1(x) x00010()()()0fxfxxx即即0100()()fxxxfx依此類推可得依此類推可得牛頓迭代公式：牛頓迭代公式：1()()kkkkfxxxfx一、牛頓法一、牛頓法3.4 3.4 插值方法插值方法x2x1x0 x*f(x) f(x) 0(x) 1(x) 在在x0處用一拋物線處用一拋物線(x)代替曲線代替曲線 f(x)，相當(dāng)于用一斜直線相當(dāng)于用一斜直線 (x)代替曲線代替曲線 f (x) 。這樣各個(gè)近似點(diǎn)。這樣各個(gè)近似點(diǎn)是通過(guò)對(duì)作是通過(guò)對(duì)作f (x)切切線求得與軸的交點(diǎn)線求得與軸的交點(diǎn)找到的，所以有時(shí)找到的，所以有時(shí)牛頓法又稱作切線牛頓法又稱作切線法。法。x2x1x0

16、x*f(x) f(x) 0(x) 1(x) f (x) f (x) x*x0 1(x) x2x11kkxx牛頓法牛頓法開開 始始計(jì)算計(jì)算 ，*1kxx給定初始點(diǎn)給定初始點(diǎn) ，誤差，誤差 ,令令k=00 x( ),( )kkf xf x計(jì)算計(jì)算 ，1()()kkkkfxxxfx1kk結(jié)結(jié) 束束數(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 4

17、.00066 4.00059 2.1667 0.83196 0.29514 0.03894 0.00007kxkfxkfx給定初始點(diǎn)給定初始點(diǎn)x0=3，=0.001，計(jì)算公式：，計(jì)算公式：1()()kkkkfxxxfx 2122412fxxx函數(shù)的二階導(dǎo)數(shù)：函數(shù)的二階導(dǎo)數(shù)：32( )4121216fxxxx解：解： 函數(shù)的一階導(dǎo)數(shù)：函數(shù)的一階導(dǎo)數(shù)：3.4 3.4 插值方法插值方法1kx1kkxx= 優(yōu)點(diǎn)優(yōu)點(diǎn)：1）收斂速度快。）收斂速度快。 缺點(diǎn)缺點(diǎn)：1）要計(jì)算函數(shù)的一階和二階導(dǎo)數(shù)，增加每次）要計(jì)算函數(shù)的一階和二階導(dǎo)數(shù)，增加每次 迭代的工作量。迭代的工作量。 2）數(shù)值微分計(jì)算函數(shù)二階導(dǎo)數(shù)，舍入誤

18、差將）數(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 插值方法插值方法1()()kkkkfxxxfx(1)( )()( )kkKkXXd二、二次插值法（二、二次插值法（）在給定的在給定的單峰區(qū)間單峰區(qū)間中，利用目標(biāo)函數(shù)上的中，利用目標(biāo)函數(shù)上的三個(gè)點(diǎn)三個(gè)點(diǎn)來(lái)來(lái)構(gòu)構(gòu)造造一個(gè)一個(gè)二次插值函數(shù)二次插值函數(shù)，以近似地表

19、達(dá)，以近似地表達(dá)原目標(biāo)函數(shù)原目標(biāo)函數(shù) f(a)，并，并求這個(gè)插值函數(shù)的求這個(gè)插值函數(shù)的極小點(diǎn)極小點(diǎn)近似作為原目標(biāo)函數(shù)的近似作為原目標(biāo)函數(shù)的極小點(diǎn)極小點(diǎn)。3.4 3.4 插值方法插值方法2( )=ABCp xxxB=-2Cpxf(x)xf1x1f2x2f3x3xpx*y0 xxp1x1x2xpx3xy0 x*y1y2ypy3x1x2xpx*y1y2ypyp1xpxp1x1x2xpx3xy0 x*y1y2ypy3x2x3xy0 x*y2ypy3yp1211112222223333p( )ABCp()ABCp()ABCxxxfxxxfxxxf構(gòu)造的構(gòu)造的上的三個(gè)點(diǎn)上的三個(gè)點(diǎn): : 解得解得系數(shù)系數(shù)2

20、22222231312123122331231312123122331()()()()()()()()()()()()xxfxxfxxfBxxxxxxxxfxxfxxfCxxxxxx 222222231312123231312123()()()122 ()()()pxxfxxfxxfBCxxfxxfxxf 二、二次插值法（二、二次插值法（）3.4 3.4 插值方法插值方法2pxx二次插值法二次插值法開開 始始計(jì)算計(jì)算 ，*2min,pyyy給定給定 ,123123x x x y y y ,ppx y縮短區(qū)間縮短區(qū)間名稱置換名稱置換結(jié)結(jié) 束束x1x2xpx3xy0 x*y1y2ypy3x1x2xpx3x0 x*yy1y2ypy3*2min,pyyy二次插值法程序編制換名方法二次插值法程序編制換名方法(1)(1)1) x2xp y2yp y2xp y2 ypyp y2y2y3xpx1x2x3xx3x2 y2ypypy1y2xpx1x2x