第三章一維搜索

1、1CHAPTER 3CHAPTER 3 2無(wú)約束問(wèn)題的數(shù)值方法一般格式無(wú)約束問(wèn)題的數(shù)值方法一般格式(i)確定局部下降方向d(k),使f(x(k)Td(k)0,使f(x(k)+tkd(k)f(x(k);(iii)令x(k+1)=x(k)+tkd(k);(iv)判斷是否終止，終止則輸出，否則k:=k+1,返(i)每次迭代時(shí)需選擇下降方向每次迭代時(shí)需選擇下降方向d d(k)(k)、步長(zhǎng)因子步長(zhǎng)因子t tk k并驗(yàn)證是否終止。并驗(yàn)證是否終止。給定x(0),置k:=13 不同的確定下降方向d(k)的方法構(gòu)成不同的無(wú)約束最優(yōu)化算法。在確定了下降方向后，可根據(jù)“充分下降”的要求，沿這個(gè)方向找到使目標(biāo)函數(shù)取極

2、小的點(diǎn)，這樣就使目標(biāo)函數(shù)值在這個(gè)方向上下降的最多，從而確定步長(zhǎng)因子tk。)(min)()(0)(kktkkktdxfdtxf 選取tk,使這種方法稱(chēng)為一維搜索、直線搜索、精確線搜索一維搜索、直線搜索、精確線搜索( one_dimension search ,exact linear search )4),()()()(kktdxft 令令x(k)x(k+1)d(k)f(x(k+1)d(k+1)x(k+2)f(x(k+2)精確線搜索的性質(zhì)精確線搜索的性質(zhì)( (步長(zhǎng)因子tk的極小化原則) )()()()()kTkkdtdxft （則則 的的極極小小點(diǎn)點(diǎn)，為為而而)(ttk 亦亦即即：故故, 0)(

3、 kt 0)()()()( kTkkkddtxf0)()()1( kTkdxf0)(,)()(T)1()()1( kkkkdxfdxf即即正正交交與與ProofProof搜索過(guò)程圖示5單谷函數(shù)可以不可微甚至不連續(xù)tt步長(zhǎng)因子tk的確定，即求一元函數(shù)(t)的極小，即確定xk沿方向pk走多遠(yuǎn)。這是一個(gè)局部問(wèn)題由于由于, ,一個(gè)函數(shù)在一個(gè)局部范圍內(nèi)顯然只有一個(gè)極小解所以所以,我們不妨設(shè)函數(shù)(t)是一個(gè)單谷函數(shù)。本章求解的問(wèn)題： min (t), :R1R1, 為單谷函數(shù)6tt1t2t*tt* t1t2單谷函數(shù)單谷函數(shù) 若t*是的一個(gè)全局極小點(diǎn)，則對(duì)于的定義域上的任意兩點(diǎn)t1 (t2);當(dāng)t1t*:

4、(t1) (t2)滿(mǎn)足這樣條件的函數(shù)就稱(chēng)為單谷函數(shù)單谷函數(shù)7單谷函數(shù)的性質(zhì)單谷函數(shù)的性質(zhì)若已知三點(diǎn)t1t3 (t3) (t2)(兩頭大中間小兩頭大中間小)，則在t1、t2之間必有(t)的一個(gè)極小點(diǎn)反設(shè)t1、t2之間無(wú)極小點(diǎn)t*，則意味著t1,t2在t*的同一邊則對(duì)t1,t3,t2三點(diǎn)根據(jù)單谷函數(shù)的定義，它們必不能滿(mǎn)足已知條件(如圖示)ProofProof(反設(shè)法)tt2t*條件：(t3) (t2)t3tt*t1條件：(t1)(t3)定義：(t1)(t3)t3tt*t2t181 1 搜索區(qū)間搜索區(qū)間若在單谷函數(shù)(t)的定義域內(nèi)有兩個(gè)點(diǎn)t1、t2,使得t1t*(t0+h0):則令t1=t0+h0,

5、 h1=h0 (1一般取2)(3) 繼續(xù)計(jì)算并比較如此繼續(xù)下去直到出現(xiàn)函數(shù)值的增大，(tk)0,(t1)(t1+h1)，則令t2=t1+h1， h2=h111tt0t1t2h1t3t4h2h0h312若 (t0)(t0+h0):則 令t1=t0,h1=-h0(0 1一般取1/4或1/2)繼續(xù)計(jì)算并比較若 (t1+h1)(t1)，則令t2=t1+h1， h2=h1如此繼續(xù)下去直到，出現(xiàn)函數(shù)值的增大，(tk)(tk+hk)這時(shí)取a=tk+hk,b=tk-1，a,b即為極小區(qū)間13tt0+h0t0(t1)t2t3t4141.1.平分法平分法( (二分法、對(duì)分法二分法、對(duì)分法) )tab即(a)0,今

6、要求出使今要求出使 (t)=0(t)=0的點(diǎn)的點(diǎn)t t* *tabt* 假設(shè)函數(shù) (t）在極小區(qū)間上a,b有連續(xù)的一階導(dǎo)數(shù)(t)，且(t)有明顯的表達(dá)式2 2 幾種有效的一維搜索算法幾種有效的一維搜索算法15(1) 計(jì)算c=(a+b)/2,計(jì)算（c）(2) 若(c)=0,則c即為所求，停止；否則若（c）0 (t*在a與c之間故可以將c、b之間這一段拋棄)令b:=c，返回(1)t*每次得到一個(gè)新的搜索區(qū)間，長(zhǎng)度每次得到一個(gè)新的搜索區(qū)間，長(zhǎng)度是原來(lái)區(qū)間的一半是原來(lái)區(qū)間的一半ctaba(3) 繼續(xù)上述過(guò)程，直到區(qū)間已經(jīng)足夠小。在這個(gè)足夠小的區(qū)間中任意取一點(diǎn)在這個(gè)足夠小的區(qū)間中任意取一點(diǎn)（比如它的兩個(gè)

7、端點(diǎn)、中點(diǎn)等）作為最優(yōu)解的近似（比如它的兩個(gè)端點(diǎn)、中點(diǎn)等）作為最優(yōu)解的近似162. 2. 黃金分割法黃金分割法(0.618(0.618法法) )at1t2bat1t2b 設(shè)t1t2是a,b上的任兩點(diǎn),若(t1) (t2)，則t*a,t2(否則t*t1 , b) 函數(shù)(t)極小區(qū)間為a,b, 要求函數(shù)單谷即可,不必連續(xù)或可導(dǎo),這種方法比平分法適用范圍廣單谷函數(shù)的性質(zhì)單谷函數(shù)的性質(zhì)情形1情形217性質(zhì)應(yīng)用性質(zhì)應(yīng)用 可通過(guò)比較極小區(qū)間內(nèi)任意兩點(diǎn)的大小以將區(qū)間縮小為a,t2或t1,b。而且，通過(guò)繼續(xù)在這小區(qū)間內(nèi)取值以比較對(duì)應(yīng)函數(shù)值的大小可以將這小區(qū)間繼續(xù)縮小，從而可達(dá)任意小。18t1t2ba 事實(shí)上，

8、滿(mǎn)足這個(gè)要求的t1,t2取法無(wú)窮，比如在離a有x那么遠(yuǎn)的地方取為t1，那么，在離b也有x那么遠(yuǎn)的地方取為t2即可.縮小區(qū)間的方法的限制條件縮小區(qū)間的方法的限制條件(1) 使a,t2或t1,b被留下的機(jī)會(huì)相等即：選取試驗(yàn)點(diǎn)選取試驗(yàn)點(diǎn)t t1 1,t,t2 2時(shí)應(yīng)使得時(shí)應(yīng)使得t t2 2-a=b-t-a=b-t1 1從而a,t2=t1,b兩個(gè)區(qū)間長(zhǎng)度相等19(2) 每次區(qū)間總是縮小相同的比例縮小相同的比例(類(lèi)似于平分法中總是以相同的比例1/2縮小區(qū)間一樣)即若由a，b縮小為a,b時(shí)它們的長(zhǎng)度之比為，則由a,b縮小為a”,b”時(shí)它們的長(zhǎng)度之比仍為。(3) 在每次縮小區(qū)間后總有一個(gè)已經(jīng)計(jì)算過(guò)的點(diǎn)落在這

9、個(gè)區(qū)間內(nèi)，所以有理由希望該點(diǎn)在下次繼續(xù)縮下次繼續(xù)縮小區(qū)間時(shí)能被用到，小區(qū)間時(shí)能被用到，從而減少縮小區(qū)間所需計(jì)算量20t1at2bat1t2bat1t2b21黃金分割法算法推導(dǎo)黃金分割法算法推導(dǎo)akkk bk1. 計(jì)算f(k )和f(k),分如下兩種情形：(1)(1)若若 f(k )f(k) ，則 ak+1= ak,， bk+1= k設(shè)求解區(qū)間為ak ， bk，在ak ， bk內(nèi)選取的試探點(diǎn)為k ， k， k f(k) ，則 ak+1= k,， bk+1= bk22以下以情形(1)為例進(jìn)行討論2.ak ， bk試探點(diǎn)k ， k位置對(duì)等 k ak= bk-k3.每次區(qū)間長(zhǎng)度收縮比相等bk+1-ak

10、+1 =(bk ak)k - ak =(bk ak)bk-k=(bk ak)k= ak +(1-)(bk ak )k = ak +(bk ak )akkk bk+1ak+1 bk234. k作為ak+1 ， bk+1兩個(gè)試探點(diǎn)k+1 ， k+1 中的一個(gè)(即長(zhǎng)度比率取適當(dāng)?shù)闹?)k= ak +(1-)(bk ak )k = ak +(bk ak ) k+1 = ak+1 +(bk+1 ak+1 ) =ak +(k ak ) = ak +2(bkak )2 = 1-k+1 = k618. 0215 k= ak +0.382(bk ak )k = ak +0.618(bk ak )24類(lèi)似，對(duì)于情

11、形2ak ， bk縮小后的區(qū)間為ak +1， bk+1 = k ，bk k+1 = kk= ak +0.382(bk ak ) k = ak +0.618(bk ak )akkk bk+1ak+1 bk25黃金分割法的計(jì)算步驟黃金分割法的計(jì)算步驟(1)對(duì)區(qū)間對(duì)區(qū)間a，b= a1 ， b1中取兩點(diǎn)：中取兩點(diǎn)： 1 =a1 +0.382(b1 a1 ), 1 = a1 +0.618(b1 a1 ) 令令 k=1若若 (k ) (k )，則，則ak+1 = ak bk+1= k k+1= k k+1 = ak+1 +0.382(bk+1 ak +1)(2) 若若 bk ak (k )，則，則 ak+

12、1 = k bk+1= bk k+1= k k+1= ak+1 +0.618(bk+1 ak +1)(3) 置置 k:=k+1，返回，返回(2)263.3.NewtonNewton切線法切線法 函數(shù)(t)極小區(qū)間為a,b,該函數(shù)有連續(xù)的二階偏導(dǎo)數(shù)，尋找(t)=0的t*假設(shè)事先給定t*的一個(gè)近似值t0，將(t)在t0處Taylor展開(kāi)得：(t) (t0)+ “(t0)(t-t0)從而得t*的一個(gè)近似值)()( *000tttt (t*) (t0)+ “(t0)(t*-t0)置t:= t*代入顯然顯然此近似值不一定可以被接受，記為t127tabt*t0t1t1 :直線y- (t0)= “(t0)(t-t0)與橫坐標(biāo)軸的交點(diǎn)t1的產(chǎn)生過(guò)程圖示28在t1處繼續(xù)展開(kāi)求解，從而得t*的一個(gè)更好的更好的近似值)()(*111tttt 記為t2)()( 1kkkktttt 如此繼續(xù)下去可得到t*的一個(gè)近似值序列：NewtonNewton切線法迭代切線法迭代公式公式29(1)(1) 這種方法一旦好用收斂速度是很高的，達(dá)2階(2)(2) 這種方法要用到二階導(dǎo)數(shù)，對(duì)于多維問(wèn)題就意味著 要計(jì)算海