3.一維優(yōu)化方法

1、2021-6-141第三章第三章 一維搜索方法一維搜索方法1 1）確定初始搜索區(qū)間的進(jìn)退算法；）確定初始搜索區(qū)間的進(jìn)退算法；2 2）格點(diǎn)法；）格點(diǎn)法；3 3）黃金分割法；）黃金分割法；4 4）二次插值法；）二次插值法；5 5）三次兩點(diǎn)插值法。）三次兩點(diǎn)插值法。2021-6-1423-1 3-1 問題的提出問題的提出 )()() 1(kkkSXX52128)(212221xxxxXF如：如：)(kX)(kS* * 在上次迭代中已求得在上次迭代中已求得， 由某種邏輯方式由某種邏輯方式（如負(fù)梯度方向如負(fù)梯度方向、共軛共軛方向等方向等）給定給定，每次迭代可歸結(jié)為以每次迭代可歸結(jié)為以 為變量的一維問題為

2、變量的一維問題。一）一維問題是多維問題的基礎(chǔ)一）一維問題是多維問題的基礎(chǔ)52202521282212221xxxxF則則TTSX11,00) 0() 0(1100X當(dāng)當(dāng)2021-6-143.5, 0204是最優(yōu)步長(zhǎng)得令ddF上例中，上例中，2 2）取最優(yōu)步長(zhǎng)：）取最優(yōu)步長(zhǎng)：,10, 3,52)0()1()0(FFF得取上例中，上例中，-能使目標(biāo)函數(shù)值下降的步長(zhǎng)能使目標(biāo)函數(shù)值下降的步長(zhǎng)；1 1）取下降步長(zhǎng)：）取下降步長(zhǎng)：二）二） 的確定方法的確定方法52202521282212221xxxxFTTSX11,00)0()0(2*F.3是下降步長(zhǎng)故2021-6-144 三）一維搜索的步驟三）一維搜索

3、的步驟foxab原區(qū)間長(zhǎng)度新區(qū)間長(zhǎng)度* 區(qū)間縮短率區(qū)間縮短率： 當(dāng)該區(qū)間的長(zhǎng)度小于預(yù)先給定的一個(gè)很小的正數(shù)當(dāng)該區(qū)間的長(zhǎng)度小于預(yù)先給定的一個(gè)很小的正數(shù) ，則可認(rèn)為該區(qū)間中的某點(diǎn)則可認(rèn)為該區(qū)間中的某點(diǎn)( (如中點(diǎn)如中點(diǎn)) )是最優(yōu)點(diǎn)是最優(yōu)點(diǎn)。2)2)將含最優(yōu)點(diǎn)的區(qū)間不斷縮小將含最優(yōu)點(diǎn)的區(qū)間不斷縮小特點(diǎn)：特點(diǎn)：高高-低低-高高1)1)確定一個(gè)包含最優(yōu)點(diǎn)的初始搜索區(qū)間確定一個(gè)包含最優(yōu)點(diǎn)的初始搜索區(qū)間2021-6-1453-2 3-2 確定初始搜索區(qū)間的進(jìn)退算法確定初始搜索區(qū)間的進(jìn)退算法3xf2x1xx1x2x3x1x2x3xfx1x2x3x前進(jìn)計(jì)算前進(jìn)計(jì)算后退計(jì)算后退計(jì)算試探后作前進(jìn)或后退計(jì)算試探后作

4、前進(jìn)或后退計(jì)算。一）基本思路一）基本思路1x2x2021-6-146h=hh=h0 0y y1 1=f(x=f(x1 1) )、x x2 2=x=x1 1+h+h、y y2 2=f(x=f(x2 2) )給定給定x x1 1、h h0 0y y1 1yy2 2y y22y y3 3是是h=2hh=2hx x3 3=x=x2 2+h+h、y y3 3=f(x=f(x3 3) )結(jié)束結(jié)束否否h= -hh= -hx x3 3=x=x1 1y y3 3=y=y1 1a=xa=x1 1、b=xb=x3 3是是x x1 1=x=x2 2y y1 1=y=y2 2x x2 2=x=x3 3y y2 2=y=

5、y3 3是是a=xa=x3 3、b=xb=x1 1否否h0h0否否二二) 迭代步驟迭代步驟初始進(jìn)退距初始進(jìn)退距3xf2x1xx1x2x3x前進(jìn)計(jì)算前進(jìn)計(jì)算1x2x3xfx1x2x3x后退計(jì)算后退計(jì)算1x2x1y2y3y2021-6-147. 1 . 0, 0,983)(. 13013hxxxxf初始進(jìn)退距初始點(diǎn)給定的一維優(yōu)化初始區(qū)間用進(jìn)退法確定函數(shù)：解khx1 y1x2 y2x3 y310.10.20 90.1 8.2030.3 6.68120.40.1 8.2030.3 6.6810.7 4.42930.80.3 6.6810.7 4.4291.5 7.125 .5 . 1, 3 . 0,b

6、a可得初始搜索區(qū)間2021-6-148. 1 . 0, 8 . 1,983)(. 23013hxxxxf初始進(jìn)退距初始點(diǎn)給定的一維優(yōu)化初始區(qū)間用進(jìn)退法確定函數(shù)：解khx1 y1x2 y2x3 y310.1-0.21.8 12.096 1.9 14.3771.9 14.3771.8 12.0961.6 8.488 2-0.41.8 12.0961.6 8.4881.2 4.5843-0.81.6 8.4881.2 4.5840.4 5.992 .6 . 1, 4 . 0,ba可得初始搜索區(qū)間2021-6-1493-3 3-3 格點(diǎn)法格點(diǎn)法 abfx 先將搜索區(qū)間分成若干等分，計(jì)算出當(dāng)中的先將搜索

7、區(qū)間分成若干等分，計(jì)算出當(dāng)中的n n個(gè)等分個(gè)等分點(diǎn)的目標(biāo)函數(shù)值點(diǎn)的目標(biāo)函數(shù)值. . 再通過比較再通過比較, ,找出其中的最小點(diǎn)，則該找出其中的最小點(diǎn)，則該點(diǎn)的兩個(gè)鄰近點(diǎn)圍成縮短了的新區(qū)間。點(diǎn)的兩個(gè)鄰近點(diǎn)圍成縮短了的新區(qū)間。一）基本思路一）基本思路mx1mx1mx2021-6-1410二）每輪迭代區(qū)間的縮短率二）每輪迭代區(qū)間的縮短率12n1 1）思路簡(jiǎn)單，編程容易，宜于離散型優(yōu)化問題；）思路簡(jiǎn)單，編程容易，宜于離散型優(yōu)化問題；三）特點(diǎn)三）特點(diǎn)2 2）計(jì)算量大，不宜用于高維優(yōu)化問題。）計(jì)算量大，不宜用于高維優(yōu)化問題。2021-6-14113-4 3-4 黃黃 金金 分分 割割 法法一）基本思路一）

8、基本思路618. 0ln)/(lnabk為預(yù)先給定的誤差限為預(yù)先給定的誤差限。2）縮短區(qū)間的總次數(shù)縮短區(qū)間的總次數(shù)618. 01） 將區(qū)間按一定的比例縮小，且正常迭代時(shí)將區(qū)間按一定的比例縮小，且正常迭代時(shí)每縮短一次區(qū)間只需計(jì)算一次函數(shù)值每縮短一次區(qū)間只需計(jì)算一次函數(shù)值。2021-6-1412ll11)1 (2ll令令21得得：012其正根為其正根為：618033988. 0215ll )1 (lab1x2xll )1 (l )1 (fx證證：618. 0*關(guān)于關(guān)于 的證明的證明2021-6-1413關(guān)于縮小區(qū)間總次數(shù)的證明關(guān)于縮小區(qū)間總次數(shù)的證明 )(618. 0abkabk618. 0abk

9、ln618. 0ln618. 0ln)/(lnabk)618. 0lg)/(lg(abk或即即證：證：2021-6-1414給定給定,ba)(),(618. 0222xfyabax)(),(382. 0111xfyabax21yy 否否否否21211,yyxxxa)(),(618. 0222xfyabax是是)(),(382. 0111xfyabax12122,yyxxxbab是是)()(5 . 0 xffbax止止二二) )迭代步驟迭代步驟xfab1x2x1y2y1x2xbxfab1x2x1y2y1x2xa* * 也可采用迭代次數(shù)是否大也可采用迭代次數(shù)是否大于或等于于或等于 k k 作終止準(zhǔn)

10、則。作終止準(zhǔn)則。2021-6-14153-5 3-5 二次插值法二次插值法 px原函數(shù)原函數(shù)1x2x3x1f2f3f用三點(diǎn)二次插值多項(xiàng)式來逼近原函數(shù)。用三點(diǎn)二次插值多項(xiàng)式來逼近原函數(shù)。一）基本思路一）基本思路2021-6-1416二）二次插值曲線的極小點(diǎn)二）二次插值曲線的極小點(diǎn)02baxdxdpabxp2)()()()()()(21213132321222132123223221xxfxxfxxfxxfxxfxxfxp求出求出a a、b b后得后得3323fcbxax2222fcbxax1121fcbxax)()()()()(133221213132321xxxxxxxxfxxfxxfa)()

11、()()()(133221222132123223221xxxxxxxxfxxfxxfb2 2）求系數(shù)）求系數(shù)a a和和b b1 1）求駐點(diǎn)）求駐點(diǎn)cbxaxxp2)(插值多項(xiàng)式：插值多項(xiàng)式：2021-6-1417 三）區(qū)間的縮短三）區(qū)間的縮短x4=0.5(x1+x2)f4=f(x4)x1=x4f1=f4x3=x2f3=f2x2=x4f2=f4x1=xpf1=fpx3=x2f3=f2x2=xpf2=fpx1=x2f1=f2x2=xpf2=fpx3=xpf3=fp是是否否輸出輸出二次插值法縮小區(qū)間流程圖二次插值法縮小區(qū)間流程圖輸入輸入xpx2f4f2f2fpxp0 x*=xp,f*=fpx*=x

12、2, f*=f2否否給定給定 x1、x3、)()()()()()(21213132321222132123223221xxfxxfxxfxxfxxfxxfxp否否否否是是結(jié)結(jié) 束束是是是是是是 本書認(rèn)本書認(rèn)為是由于為是由于區(qū)間縮到區(qū)間縮到很小時(shí)因很小時(shí)因計(jì)算機(jī)舍計(jì)算機(jī)舍入誤差引入誤差引起，可取起，可取中間點(diǎn)輸中間點(diǎn)輸出。出。2021-6-1420)A=0)A=00)()()(213132321xxfxxfxxf0)()()()(21313213121xxfxxfxxxxf13131212xxffxxff1f3f2f1x3x2x1f3f2f1x3x2x0)(31PPxxxx) 這表明此時(shí)三個(gè)插值

13、點(diǎn)共線。這表明此時(shí)三個(gè)插值點(diǎn)共線。2021-6-14213-5 3-5 三次兩點(diǎn)插值法三次兩點(diǎn)插值法 ab)(af)(bfxfCaxBaxAxpDaxCaxBaxAxp)(2)(3)()()()()(2/23二）插值多項(xiàng)式二）插值多項(xiàng)式根據(jù)兩點(diǎn)處的目標(biāo)函數(shù)值和一階導(dǎo)數(shù)插值。根據(jù)兩點(diǎn)處的目標(biāo)函數(shù)值和一階導(dǎo)數(shù)插值。一）插值條件一）插值條件2021-6-1422三）插值多項(xiàng)式系數(shù)三）插值多項(xiàng)式系數(shù)3/)()()( 2)()()(abbfafafbfabA2/)()(2)()()()( 3abafbfabafbfB)(/afC )(afD 2021-6-1423四）插值函數(shù)的極小點(diǎn)四）插值函數(shù)的極小點(diǎn)0)(2)(3)(2/CaxBaxAxp由由得得AACBBax612422AACBB332因有極小，因有極小，其二階導(dǎo)數(shù)應(yīng)大于其二階導(dǎo)數(shù)應(yīng)大于0 0：ABaxBaxAxp302)(6)( 應(yīng)取應(yīng)取“+”+”號(hào)號(hào)ACBBCaAACBBaxp33322故有故有* 如何選取如何選取？2021-6-1424)(/pxf六）終止準(zhǔn)則六）終止準(zhǔn)則五）縮短區(qū)間的方法五）縮短區(qū)間的方法abpx1）當(dāng)當(dāng);, 0)(ppxbxf則2）當(dāng)當(dāng)., 0)(ppxaxf則*