第三章一維搜索

1、1CHAPTER 3CHAPTER 3 2無約束問題的數(shù)值方法一般格式無約束問題的數(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)每次迭代時需選擇下降方向每次迭代時需選擇下降方向d d(k)(k)、步長因子步長因子t tk k并驗證是否終止。并驗證是否終止。給定x(0),置k:=13 不同的確定下降方向d(k)的方法構(gòu)成不同的無約束最優(yōu)化算法。在確定了下降方向后，可根據(jù)“充分下降”的要求，沿這個方向找到使目標(biāo)函數(shù)取極

2、小的點，這樣就使目標(biāo)函數(shù)值在這個方向上下降的最多，從而確定步長因子tk。)(min)()(0)(kktkkktdxfdtxf 選取tk,使這種方法稱為一維搜索、直線搜索、精確線搜索一維搜索、直線搜索、精確線搜索( 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ì)( (步長因子tk的極小化原則) )()()()()kTkkdtdxft （則則 的的極極小小點點，為為而而)(ttk 亦亦即即：故故, 0)(

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

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

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

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

7、端點、中點等）作為最優(yōu)解的近似（比如它的兩個端點、中點等）作為最優(yōu)解的近似162. 2. 黃金分割法黃金分割法(0.618(0.618法法) )at1t2bat1t2b 設(shè)t1t2是a,b上的任兩點,若(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)用 可通過比較極小區(qū)間內(nèi)任意兩點的大小以將區(qū)間縮小為a,t2或t1,b。而且，通過繼續(xù)在這小區(qū)間內(nèi)取值以比較對應(yīng)函數(shù)值的大小可以將這小區(qū)間繼續(xù)縮小，從而可達(dá)任意小。18t1t2ba 事實上，

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

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

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黃金分割法的計算步驟黃金分割法的計算步驟(1)對區(qū)間對區(qū)間a，b= a1 ， b1中取兩點：中取兩點： 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*的一個近似值t0，將(t)在t0處Taylor展開得：(t) (t0)+ “(t0)(t-t0)從而得t*的一個近似值)()( *000tttt (t*) (t0)+ “(t0)(t*-t0)置t:= t*代入顯然顯然此近似值不一定可以被接受，記為t127tabt*t0t1t1 :直線y- (t0)= “(t0)(t-t0)與橫坐標(biāo)軸的交點t1的產(chǎn)生過程圖示28在t1處繼續(xù)展開求解，從而得t*的一個更好的更好的近似值)()(*111tttt 記為t2)()( 1kkkktttt 如此繼續(xù)下去可得到t*的一個近似值序列：NewtonNewton切線法迭代切線法迭代公式公式29(1)(1) 這種方法一旦好用收斂速度是很高的，達(dá)2階(2)(2) 這種方法要用到二階導(dǎo)數(shù)，對于多維問題就意味著 要計算海