第二章直線搜索

1、第二章 直線搜索 本章討論 的主要問題是 解決這個(gè)問題的方法承為直線搜索或一維搜索。這種方法不僅對(duì)于解決一維最優(yōu)化本身具有實(shí)際意義，而且也是解多維最優(yōu)化問題的重要支柱。 在微積分中解 的方法限于方程 可以直接求解出來的情況。本章介紹的方法對(duì) 不作嚴(yán)格要求，它可以很復(fù)雜，其導(dǎo)數(shù)可能不存在或者很難求出。當(dāng)然對(duì)于可以求導(dǎo)數(shù)的情況，相應(yīng)的方法也會(huì)簡單些。)(min t1Rt11:RR )(mint0)( t 本章將討論以下四種直線搜索方法： （1）對(duì)分法對(duì)分法：適用于 的一階導(dǎo)數(shù)連續(xù)并可以求出的情況。 （2）Newton切線法切線法：適用于 的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)都可求出的情況。 （3）黃金分割法黃金分

2、割法：適用于一般的函數(shù)。 （4）拋物線插值法拋物線插值法：適用于一般的連續(xù)函數(shù)。)(t)(t1 搜索區(qū)間的確定0tt*0tt*)(t 定義定義1：設(shè) ，t*是 在L 上的 全局極小點(diǎn)。如果對(duì)于L上任取的兩點(diǎn)t1和t2且t1 t2,均有：當(dāng)t2t*時(shí)， ，當(dāng)t1t*時(shí)， 則稱 是區(qū)間L上的單谷函數(shù)單谷函數(shù)。 以下假設(shè)一元函數(shù) 是單谷函數(shù)。)(t)()(21tt)()(21tt11:RRL)(t單谷函數(shù)的性質(zhì)單谷函數(shù)的性質(zhì)： 設(shè) 是單谷函數(shù)極小點(diǎn)的一個(gè)搜索區(qū)間。在 (a,b)上任取兩點(diǎn)t1，t2，使t1 t2,若 則 是 極小點(diǎn)的一個(gè)搜索區(qū)間；若 ，則 是 極小點(diǎn)的一個(gè)搜索區(qū)間。12( )()tt

3、)(t)()(21ttbt ,1)(t2,taba, 定義定義2： ，t*是 在L上的全局極小點(diǎn)。若找到 ,則稱此區(qū)間t1，t2 為 的極小點(diǎn)的一個(gè)搜索區(qū)間搜索區(qū)間，記為 。 若t1t3 t2,也可將搜索區(qū)間 記為)(t2121*,tttLtLt使)(t21,tt21,tt231,ttt11:LRR 證明證明：利用反證法證明。對(duì)于后一種情況，即 。若 不是搜索區(qū)間，即 的極小點(diǎn)必在（a,t1)中。此時(shí)有t*t1t2, 根據(jù)單谷函數(shù)定義知： 矛盾。 故（t1,b)是搜索區(qū)間，同樣可證前種情形。)()(21ttbt ,1)(t)()(21tt 單谷函數(shù)的這一性質(zhì)可用來將搜索區(qū)間無限縮小，以至求到極

4、小點(diǎn)。 本章下面就介紹的直線搜索法，第一步就是要找一個(gè)初始搜索區(qū)間，下面就介紹一種有效的找初始搜索區(qū)間的 方法。2 比較 的值，轉(zhuǎn)，)()(00htt和3若 ，比較 ，轉(zhuǎn) ， 。)()(00htt)()(00htt和)(t算法算法1：（搜索區(qū)間的確定）已知目標(biāo)函數(shù) 。1 選擇初始點(diǎn)t0和步長 h.令=t0+(2m-1-1)h,=t0+(2m-1)h,=t0+(2m+1-1)h, 2 , 1),) 12(0hhtk 4若 ，計(jì)算)()(00htt) 12() 12() 12(10010hththtmmm直到有某個(gè)m1使 確定了搜索區(qū)間，（實(shí)際應(yīng)該為，放大）。但區(qū)間，是，的兩倍長。（-=2（-）0

5、t （a)0t(b)t0 t0-h t0t0+h(c)因此只需比較和區(qū)間，的中點(diǎn) 的對(duì)應(yīng)函數(shù)值，即可將區(qū)間，縮短1/3。由圖(a),(b)可2 見，當(dāng) 時(shí)，取，為搜索區(qū)間（圖（a）。當(dāng) ，為搜索區(qū)間。（圖(b)()()()( 當(dāng) ，取t0-h, t0, t0+h為搜索區(qū)間。)()(00tht 當(dāng) ，與4類似，計(jì)算 ， 直到有某個(gè)m（1）使 令=t0-(2m-1-1)h,=t0-(2m-1)h,=t0-(2m+1-1)h, =(+)/2,比較 ： 若 , 取,為搜索區(qū)間(圖(d) 若 ,取,為搜索區(qū)間。)()(00tht,.2 , 1),) 12(0khtk)12()12()12(10010ht

6、hthtmmm)(),(rv)()(rv)()(rv(圖(e)t0(d)t0(e) 上述過程的關(guān)鍵是開始時(shí)怎樣選擇步長h ，如選得太小,需迭代多次才能找到搜索區(qū)間，而若選得太大，雖然一次就能找到搜索區(qū)間，但給下一步找極小點(diǎn)過程增加了負(fù)擔(dān)。 下面將介紹選擇初始步長下面將介紹選擇初始步長h的一種方法的一種方法。)(t 設(shè) 具有連續(xù)二階偏導(dǎo)數(shù)，且 ?，F(xiàn)在要從t0出發(fā)確定一個(gè)搜索區(qū)間。在t0附近將 二次Taylor 展開： 令 )(t0)(, 0)(00 tt) 1 ()(21)()()()(200000ttttttttt ) 2(0)()(, 0)(000 ttttt則 由此解得 .(3) 這是 的

7、唯一極小點(diǎn)，可作為 極小點(diǎn)t*的一個(gè)近似。因此想到用 作為初始步長h。 但 中要計(jì)算二階導(dǎo)數(shù)。一般來說計(jì)算二階導(dǎo)數(shù)比較困難，而一階導(dǎo)數(shù)即使較困難，也可用差分近似，因此，要想辦法避免二階導(dǎo)數(shù)的計(jì)算。)(/)(000tttt )(0t0tt )(tt 假設(shè) 的極小值可以估計(jì)出來，如為 ，即 若對(duì)某個(gè) ，使得 ，則將 作為t*的一個(gè)近似。)(teet*)(tet)(t) 5 (0)()(000 tttt:)(21)5()4(0tt )()(2000tttte)6()()(2000tttthe則可取步長2000001( )( )()( )()(4)2ettt ttt t由（1）：這樣就避免了二階導(dǎo)數(shù)的

8、計(jì)算。) 7()(min)(1kkkkkkkkkptzztpzfptzf 在多維最優(yōu)化問題時(shí)，若采用迭代計(jì)算法時(shí)，每次迭代要用直線搜索來確定下一個(gè)迭代點(diǎn)，每次迭代需要確定直線搜索的初始步長，如下面考察由Zk到Zk+1迭代的情況。 設(shè)已獲得迭代點(diǎn)Zk，并按某種規(guī)則選定了向量Pk 為下降方向，并設(shè) ，則 下一迭代點(diǎn)Zk+1由下述直線搜索確定的：1kP 令 ，則 則上述直線搜索（7）就是 從t=0出發(fā)的直線搜索，因而可按（6）確定初始步長h，但此時(shí)公式（6）中應(yīng)令t0=0, 應(yīng)該取f(z)極小值的估計(jì)值fe，即f(z*)fe，又 從而)()(kktpzftkTkkptpzft)()()(tekTkk

9、pzfzf)() 0(),() 0()8()(/)( 2kTkkepzfzffh 公式中沒有絕對(duì)值符號(hào)，這是因?yàn)椋?首先：下降方向Pk應(yīng)選擇滿足 其次：估計(jì)值fe一般比真實(shí)值f(z*)偏小，從而 fe0.0)(kTkpzf 實(shí)際操作時(shí)可采用兩種方案實(shí)際操作時(shí)可采用兩種方案：一是一是下降迭代算法每次迭代均用（8）來確定初始步長，二是二是在第一次迭代 算法時(shí)用（8）而以后每次迭代初始步長均用 來計(jì)算。這是因?yàn)?一般是接近的。 因而用前依次迭代所走的距離作為下一次迭代的初始步長是合適的，計(jì)算經(jīng)驗(yàn)表明，后一種方案更有效些。)9(1kkzzh11kkkkzzzz與 我們知道，在極小點(diǎn) 處， ，且 時(shí)，

10、遞減，即 ，而當(dāng) ，函數(shù)遞增，即 。若找到一個(gè)區(qū)間a,b,滿足性質(zhì) 則a,b內(nèi)必有 的極小點(diǎn) ，且 為找此 取 ，若 則在 中有極小點(diǎn)，這時(shí)用 作新的區(qū)間a,b，繼續(xù)這個(gè)過程，逐步將區(qū)間a,b縮小，當(dāng)區(qū)間a,b的長度充分小時(shí)，或者當(dāng) 充分小時(shí)，即可將a,b的中點(diǎn)取做極小點(diǎn)的近似點(diǎn)，*t 0* t*tt t 0*t*tt 0t 0, 0ba t*t 0* t*t20bat 00 t0,t b0,t b 0t2 對(duì)分法 這個(gè)方法的特點(diǎn)是計(jì)算量較少，而且總能收斂到一個(gè)局部極小點(diǎn)，但收斂速度較慢。 這時(shí)有估計(jì)： 。至于區(qū)間a,b的確定，一般可采用下述方法： 22*abbat 有用。注意這種方法不僅對(duì)于

11、對(duì)分法有用，在后面方法中也 首先取初始點(diǎn) ，若 ，則在 右方取點(diǎn) ，（ 也是事先給定的步長）；若 則令 ；若仍然有 ，則取 （或?qū)?放大一倍，即取 ）若 則以 作區(qū)間a,b；否則繼續(xù)下去。 對(duì)于 的情況，可類似于上面在 左側(cè)取點(diǎn)。0t 00 tttt01 01 t10,tbta 01 ttttt21221,tt 00t21ttt 20t0tt0t2. 。ttt013.若 ，則 ，若 ，則 ，轉(zhuǎn)6；若 ，則 01 t1*tt 01 t10,ttba 01 t01:tt ，轉(zhuǎn)2 。ttt:1.若 ，則 終止。若 轉(zhuǎn)2，3 若 ，轉(zhuǎn)4，5。 00t0*tt 00 t 00 t下面將對(duì)分法的過程敘述一

12、下： 0, 0,0tttt已知10,*4.5.,42,ttttttabbatt *11，110，110若 （t）=0,則t =t; 若 (t )0,tt ,轉(zhuǎn) 。6.t=若則求出駐點(diǎn)，終止；否則轉(zhuǎn)7,432,320,07.若 (t)0,則t:b,轉(zhuǎn)6.例：用對(duì)分法求下面問題的極小值點(diǎn)： min (t)=3t -16t +30t -24t+8解： (t)=12(t -4t +5t-2) 取t =0, t=1, =0.001 (t )= (0)=-240 a,b=0,3a+b t=1.5, (t)=-1.50,2 則a,b=1.5,2.25 . 則a,b=1.9921875,2.0039062a+

13、b t =2.0011392 (精確極小點(diǎn)：t=2,(2)=0,(2)0)11設(shè)： RR,在 已 獲 得 的 搜 索 區(qū) 間 a,b內(nèi) 具 有 連續(xù) 二 階 導(dǎo) 數(shù) ,并 且 已 得 出 其 一 階 二 階 導(dǎo) 數(shù) 的 表 達(dá) 式 ， 此時(shí) 利 用 高 等 數(shù) 學(xué) 學(xué) 過 的 切 線 法 將 能 很 快 地 求 出,（ t） =0的 一 個(gè) 根 。3Newton 切線法 ,(),(),(),()ttkktktktkNewton切 線 法 的 迭 代 公 式 是 ： 取 初 始 點(diǎn) t,令 k=00, 1 .計(jì) 算 2 .求 tk+1* 3 .若 t-t,則 得 近 似 最 優(yōu) 點(diǎn) :t=t，

14、終 止 計(jì) 算 ， 否 則 轉(zhuǎn) 4。k+1kk+1 4 .k+1:k,轉(zhuǎn) 1.Newton迭代公式的推導(dǎo)： 方法一：設(shè)已給定極小點(diǎn)附近的一個(gè)點(diǎn)t ，因?yàn)橐粋€(gè)二次0 連續(xù)可微函數(shù)在其極小點(diǎn)附近與二次函數(shù)很接近，則在 t 附近用二次函數(shù)逼近 (t)0 1(2,()0,()0tt,2(t)t)= (t)+(t)(t-t)+(t)(t-t)00000 然 后 以(t)的 極 小 點(diǎn) 作 為 極 小 點(diǎn) 的 一 個(gè) 新 的 近 似 點(diǎn) t1 由 極 值 必 要 條 件 : (t )=01, 即 : (t)+(t)(t -t)=0 即 : t =t-001010 此 式 正 好 為 迭 代 公 式 。 .

15、,kk+1方法二：Newton法的幾何解釋如圖： y= (t)在t 處的切線與t軸交點(diǎn)的 下一個(gè)點(diǎn)作為新的迭代點(diǎn)tt,(t)k+1tktk-1t,點(diǎn)斂點(diǎn)：1 在每次迭代時(shí)均要計(jì)算二階導(dǎo)數(shù)，增加了工作量，而且用數(shù)值微分代替二階導(dǎo)數(shù)時(shí)，舍入誤差會(huì)影響收斂速度，特別是(t)很小時(shí)，更加嚴(yán)重。對(duì)于多元最優(yōu)化問題，計(jì)算二階導(dǎo)數(shù)涉及到Hesse陣，計(jì)算起來比較困難。Newton法的最大優(yōu)是收速度快，但有不少缺2 方 法 對(duì) 初 始 點(diǎn) 的 依 賴 性 很 強(qiáng) ， 初 始 點(diǎn) 不 能 選 得 離極 小 點(diǎn) 太 遠(yuǎn) ， 否 則 所 得 極 小 化 序 列 是 發(fā) 散 的 ， 或 收斂 到 非 極 小 點(diǎn) 。

16、另 外 ： 要 求 函 數(shù) 二 階 導(dǎo) 數(shù) 正 定 ，, ,即（ t） 0k3 ( ) ,.4 ( ) , .yta byta b當(dāng)曲線在中有較復(fù)雜的彎曲時(shí)，這種方法往往失效即使曲線比較正常，在中或上凹或下凹，初始點(diǎn)也必須選擇適當(dāng) 黃金分割法適應(yīng)于區(qū)間a,b上的任何單谷函數(shù) (t)求極小點(diǎn)的問題.對(duì)函數(shù)除“單谷”外不作其他要求，甚至可以不連續(xù)，因此這種方法的適應(yīng)面極廣。其特點(diǎn)是只需要計(jì)算一個(gè)點(diǎn)的位置及其函數(shù)值,從而極大地減少了工作量.4 黃金分割法（0.618法）()2黃：在a,b內(nèi)適當(dāng)插入兩點(diǎn)t ，t (t t ),1212將a,b分為三段，通過比較t )=， (t便可斷定112極小點(diǎn)是在a

17、,t 內(nèi)或者是在t ,b內(nèi)，從而可用此小區(qū)間21取代a,b，將此縮小了的新區(qū)間記為a ,b .11 金分割的思路是()()又可在新的區(qū)間內(nèi)取兩點(diǎn)t t ,通過比較函數(shù)值t3433和t，即可得新的區(qū)間a ,b 如此做下去，最后便4422可定出近似的極小點(diǎn). 怎樣選擇t ,t 呢?因?yàn)槊看伪容^兩點(diǎn)函數(shù)值區(qū)間都將縮小，12如果縮小的區(qū)間中保留的一點(diǎn)仍然用,那么除開始的區(qū)間要算兩點(diǎn)的函數(shù)值外后面每一步只須計(jì)算一個(gè)函數(shù)值即可這樣就節(jié)省了計(jì)算。,2,4)tt 假定每次迭代區(qū)間的長度按比例 縮小，(0 1)則經(jīng)過一次迭代后的區(qū)間或者為:a,a+(b-a) ，或者為b-(b-a) ,b.由上面的分析知：應(yīng)取t

18、 =b-(b-a)=a+(b-a)若下一個(gè)1新區(qū)間為a,a+(b-a) ,則:=a +(b -a )111 t =b -(b -a )a +(1-(b -a )31111112)4)t因:a =a,b =a+(b-a)則:t =a+ (1-(b-a),=a+(b-a) 113由于我們縮小區(qū)間是通過割去（t ,b而得到的,所以t 保留21在a,t 內(nèi). 又由于 (t )=a+(1-(b-a), 因而在新的21區(qū)間a ,b 中自然希望t 或t 與t 重合以便減少計(jì)算一個(gè)函數(shù)值.11341242)1,.15251012t 1331314141 因: t =a+(1-(b-a) t =a+ (1-(b

19、-a) =a+(b-a)那么 t 與t 重合便是1-= (1-不合理.故不能取t =t t 與t 重合便是1-= 0.618033988 此時(shí)t 與t 重合.)512)51232kk2k+12k+22k+1kkk2k+2kkk對(duì)于下一個(gè)新區(qū)間是a+(1-(b-a)，b的情形也可類似推出： 0.618033988 此時(shí)t 與t 重合.因此不管哪種情形，我們都有結(jié)論：在a ,b 確定后,就按下面方式取t,t t= a +(1-(b -a ) ta + (b -a )(其中0.618)():,:1():2():b ab a黃驟1 求：t =a+(1-(b-a)，t =a+ (b-a) t )= ，t

20、 )=121122a+b*2 若,求得近似極小點(diǎn)t =;若轉(zhuǎn)323 若t ) (t則ta,bb,tt ,轉(zhuǎn)5121211,若t )= (t則ta,tb轉(zhuǎn)11212金分割法步：)(4 求t =a+(1-(b-a),t )=轉(zhuǎn)21115 求t =a+ (b-a), t )=轉(zhuǎn)22222.0015525432*例：min (t)=3t -16t +30t -24t+8 取 a,b=0,3 =0.618034 =0.001a+b 經(jīng)9次迭代可得：t =25 拋物線插值法 上 面 我 們 介 紹 的 方 法 僅 對(duì) 諸 點(diǎn) 函 數(shù) 值 大 小 進(jìn) 行 比 較 ， 而 函 數(shù)值 本 身 沒 有 得 到 充

21、 分 利 用 ， 因 而 即 使 對(duì) 簡 單 函 數(shù) 如 二 次 函 數(shù) 也 不得 不 像 一 般 函 數(shù) 一 樣 進(jìn) 行 同 樣 多 的 函 數(shù) 值 計(jì) 算 ， 下 面 介 紹 拋 物 線插 值 法 ， 二 次 插 值 法 ， 利 用 函 數(shù) 在 已 知 點(diǎn) 的 值 來 確 定 新 的 迭 代 點(diǎn) ，當(dāng) 函 數(shù) 有 比 較 好 的 解 析 性 （ 如 連 續(xù) 可 微 ） 這 往 往 比 對(duì) 分 法 、 黃 金分 割 法 效 果 好 些 。 樣拋線數(shù)數(shù)數(shù)點(diǎn)為點(diǎn) 與 Newton法 一，物法 也 是 用 二 次 函逼 近 原 函， 并 取二 次 函的 極 小 值作新 的 近 似，處點(diǎn) 處數(shù)階 導(dǎo)

22、 數(shù)來數(shù)拋線個(gè) 點(diǎn)數(shù)來數(shù)不 同 之在 于 ： Newton法利 用 前 一的 函值 和 一 、 二值構(gòu) 造 二 次 函，物法 利 用 前 三的 函值 構(gòu) 造構(gòu) 造 二 次 函。0011(), ()( ), ()()()()( )()()()()()( )()()()(ttttttttt012012010201212012021020首先，像黃金分割法一樣，找點(diǎn)t ,t ,t 并使tt ,ttttt t ,t ,t 的確定按黃金分割法中求a,b的公式定，然后利用Lagrange插值公式構(gòu)造二次函數(shù)：tt tttttt +tttt +22)()()()(), ( )(, ()ttt1201001122tttt 這是由三個(gè)點(diǎn)：（t ，t ）、(tt ）、tt定出的拋物線。222222001202211( )0() ( ) () ( ) () ( )2() ( ) () ( ) () ( )( ).,ttttttttt，12