第十七章線搜索

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

2、插值法：適用于一般的連續(xù)函數(shù)。17.1搜索區(qū)間的確定定義17.1.1:設(shè)：L R1R1 , t*是 在L上的全局極小點(diǎn)。如果對(duì)于L上任取的兩點(diǎn)t1和t2且t1 t2,均有：當(dāng)t20t*時(shí)，（L） 他），當(dāng)tt*時(shí)，（L）&）則稱（t）是區(qū)間L上的單谷函數(shù)。t1t2,則稱此區(qū)問定義L,t2L,使 L t*以下假設(shè)一元函數(shù) （t）是單谷函數(shù)。圖 17.1.1t*是（t）在L上的全局極小點(diǎn)。若找到 t1, t2為（t）的極小點(diǎn)的一個(gè)搜索區(qū)間,記為 t1,t2 。若t1t3 t2,也可將搜索區(qū)間t1,t2記為t1,t3,t2單谷函數(shù)的性質(zhì)：設(shè)a,b是單谷函數(shù)極小點(diǎn)的一個(gè)搜索區(qū)間。 在（a,b）上任取兩

3、點(diǎn)t1, t2,使t1 t2,若（t） &）則a,t2是（t）極小點(diǎn)的一個(gè)搜索區(qū)間；若（t） &）,則t1,b 是 極小點(diǎn)的一個(gè)搜索區(qū)間。證明：利用反證法證明。對(duì)于后一種情況，即（3）心）。若b不是搜索區(qū)間，即（t）的極小點(diǎn)必在（a,t1）中。此時(shí)有t*&t1t2,根據(jù)單谷函數(shù)定義知:(tl) (t2)矛盾故(t1,b)是搜索區(qū)間，同樣可證前種情形。單谷函數(shù)的這一性質(zhì)可用來將搜索區(qū)間無限縮小，以至求到極小點(diǎn)。本章下 面就介紹的直線搜索法，第一步就是要找一個(gè)初始搜索區(qū)間，下面就介紹一種有 效的找初始搜索區(qū)間的方法。算法1：(搜索區(qū)間的確定)已知目標(biāo)函數(shù) (t)1選擇初始點(diǎn)to和步長(zhǎng)h.2比較(t

4、o)和(to h)的值，轉(zhuǎn) , 3若(to)(toh),比較 (to)和(to h),轉(zhuǎn),。4若(to)(toh),計(jì)算(to (2k1)h),h 1,2,，直到有某個(gè)m1 使(to (2m1 1)h) (to (2m 1)h) (to (2m1 1)h)令尸to (2m1 1)h, v= to (2m 1)h,co=to (2m 1 1)h放大)。但區(qū)間V ,就確定了搜索區(qū)間 & V,(實(shí)際應(yīng)該為 V ,的兩倍長(zhǎng)。(-V =2 ( v - N)(b)圖 17.1.2(c)因此只需比較V和區(qū)間 卜，的中點(diǎn) 的對(duì)應(yīng)函數(shù)值，即可將區(qū)間2g縮短1/3。由圖(a),(b)可見，當(dāng)()()時(shí)，取山丫的搜

5、索區(qū)間(圖(a)。當(dāng)()()v, 丫為搜索區(qū)間。(圖(b)當(dāng)(toh)(to),取t0-h, t0, t0+h為搜索區(qū)間。當(dāng)(toh)(to),與4類似，計(jì)算(to (2k1)h),k 1,2,.,直到有某個(gè) m(1)使(to (2m1 1)h)(to (2m 1)h) (to (2m1 1)h)0令尸to (2m1 1)h,v=t (2m 1)h,co=to (2m 1 1)h y=(n+v)/2,比較(v), (r)：若(v)(r),取，t,v為搜索區(qū)間(圖(d)若(v)(r),取 丫，v e為搜索區(qū)間。(圖(e)1,(d)(e)圖 17.1.3上述過程的關(guān)鍵是開始時(shí)怎樣選擇步長(zhǎng)h ,如選

6、得太小，需迭代多次才能找到搜索區(qū)間，而若選得太大，雖然一次就能找到搜索區(qū)間，但給下一步找極小點(diǎn) 過程增加了負(fù)擔(dān)。下面將介紹選擇初始步長(zhǎng)h的一種方法。設(shè)(t)具有連續(xù)二階偏導(dǎo)數(shù)，且(to) 0, (to) 00現(xiàn)在要從t0出發(fā)確定一個(gè)搜索區(qū)間。在to附近將(t)二次Taylor展開：(to)(t to)2(1) TOC o 1-5 h z 1 HYPERLINK l bookmark10 o Current Document (t)(t0)(t0)(tt0) 2令 (t) 0,則(to) (to)(tto)0 (2)由此解得 t0(t0)/ (t0) .(3)這是(to)的唯一極小點(diǎn)，可作為 (

7、t)極小點(diǎn)t*的一個(gè)近似。因此想到用 t to作為初始步長(zhǎng)h但to中要計(jì)算二階導(dǎo)數(shù)。一般來說計(jì)算二階導(dǎo)數(shù)比較困難，而一階導(dǎo)數(shù)即使 較困難，也可用差分近似，因此，要想辦法避免二階導(dǎo)數(shù)的計(jì)算。假設(shè)(t)的極小值可以估計(jì)出來,如為e,即(t*) e若對(duì)某個(gè) ，使得(t) e，則將作為t*的一個(gè)近似由(1):(to)1(to)(t%to) 2(to)(% to)2eL (4)(to) (to)(tto)0 (5)(4) (5)2(tto)： tto2( e(to)則可取步長(zhǎng)ht to2(to)e (to)(to)(6)這樣就避免了二階導(dǎo)數(shù)的計(jì)算。在多維最優(yōu)化問題時(shí)，若采用迭代計(jì)算法時(shí)，每次迭代要用直線

8、搜索來確定 下一個(gè)迭代點(diǎn)，每次迭代需要確定直線搜索的初始步長(zhǎng)，如下面考察由Zk到Zk+1 迭代的情況。設(shè)已獲得迭代點(diǎn)Zk,并按某種規(guī)則選定了向量 Pk為下降方向，并設(shè)|Pk 則下一迭代點(diǎn)Zk+1由下述直線搜索確定的：f(Zk tkPk) min f(Zk tpj k Pk令(t) f(Zk tpk) ,則 (t)f (Zk tPk)T Pk則上述直線搜索(7)就是(t)從t=0出發(fā)的直線搜索，因而可按(6)確定 初始步長(zhǎng)h,但此時(shí)公式(6)中應(yīng)令t0=0, e應(yīng)該取f(z)極小值的估計(jì)值fe, 即 f(z*)= fe , 又 (0) f(zj (0)f (Zk)T pk從 而h 2fe g/

9、f(Zk)T Pk(8)公式中沒有絕對(duì)值符號(hào)，這是因?yàn)椋菏紫龋合陆捣较騊k應(yīng)選擇滿足f(Zk)T Pk 0其次：估計(jì)值fe一般比真實(shí)值f(Z*)偏小，從而fe0.實(shí)際操作時(shí)可采用兩種方案：一是下降迭代算法每次迭代均用(8)來確定初始步長(zhǎng)，二是在第一次迭代算法時(shí)用(8)而以后每次迭代初始步長(zhǎng)均用h| ZkZki|(9)來計(jì)算。這是因?yàn)閨 Zkiz與Zk一般是接近的。因而用前依次迭代所走的距離作為下一次迭代的初始步長(zhǎng)是合適的，計(jì)算經(jīng)驗(yàn)表明，后一種方案更有效些。17.2 對(duì)分法這個(gè)方法的特點(diǎn)是計(jì)算量較少，而且總能收斂到一個(gè)局部極小點(diǎn)，但收斂速 度較慢。我們知道，在極小點(diǎn)t*處，t*0,且t t*時(shí)，

10、t遞減，即t*0,而當(dāng)t t* ,函數(shù)遞增，即 t 0。若找到一個(gè)區(qū)間a,b,滿足性質(zhì) a 0, b 0。則a,b內(nèi)必有 t的極小點(diǎn)t* ,且t*0為找此t* ,取t。b ,若2t00則在a,t0中有極小點(diǎn)，這時(shí)用a,t0作新的區(qū)間a,b,繼續(xù)這個(gè)過程，逐步將區(qū)間a,b縮小，當(dāng)區(qū)間a,b的長(zhǎng)度充分小時(shí)，或者當(dāng)t0充分小時(shí)，即可將a,b的中點(diǎn)取做極小點(diǎn)的近似點(diǎn)，這時(shí)有估計(jì):至于區(qū)間a,b的確定，一般可采用下述方法：首先取初始點(diǎn)to ,若 t0 0 ,則在t0右方取點(diǎn)ti t0 t , ( t也是事先給 定的步長(zhǎng))；若ti 0,則令a t0,b ti；若仍然有 t0 0,則取t2 ti t(或 將

11、t放大一倍，即取12 t1 2 t),若 t2 0則以ti,t2作區(qū)間a,b;否則繼 續(xù)下去。對(duì)于t00的情況，可類似于上面在t左側(cè)取點(diǎn)。注意這種方法不僅對(duì)于對(duì)分法有用，在后面方法中也有用。下面將對(duì)分法的 過程敘述一下：已知：t , t ,t0, t 0,01)若 t 0,則t t0終止。若t00轉(zhuǎn)2), 3)若t00,轉(zhuǎn) 4), 5)。2) ti t t 3)右 t 0 ,則 tti ,右 ti 0 ,則 a,bt0,ti ,轉(zhuǎn) 6);若 ti 0 ,則 ti : to; t t: t,轉(zhuǎn) 2) 04 ti t0t5)若(3) =0,則t*二t1；若(t i)0,t i t0, t tt,轉(zhuǎn)

12、4)。a bt=，則求出駐點(diǎn)t* t,終止；否則轉(zhuǎn)7)若b7)若若2(t)0,則 t: b,轉(zhuǎn)6。例i7.2.i：用對(duì)分法求下面問題的極小值點(diǎn): min (t)=3t 4-i6t 3+30t 2-24t+8解： ,(t)=i2(t 3-4t 2+5t-2)取 t0=0, t=i, =0.00i(t 0)= (0)=-240a,b=0,3a+bt= =i.5,(t)=-i.50,則a,b=i.5,2.25 貝 U a,b=i.992i875,2.0039062* a+b 一 一t =- =2.00ii392( 精確極小點(diǎn)：t=2,(2)=0,(2)0)17.3 Newton 切線法設(shè)：R1R1,

13、在已獲得的搜索區(qū)間a,b內(nèi)具有連續(xù)二階導(dǎo)數(shù)，并且已得出其一階二階導(dǎo)數(shù)的表達(dá)式，此時(shí)利用高等數(shù)學(xué)學(xué)過的切線法將能很快地求 出(t) =0的一個(gè)根。Newton線法的迭代公式是：取初始點(diǎn)品,令k=0t計(jì)算,(tk),求 t k+1 tk若t*=tk+1 -t k1),&),(tk)，則得近似最優(yōu)點(diǎn)k+1,終止計(jì)算，否則轉(zhuǎn)k+1: k,轉(zhuǎn)1)。4) oNewton迭代公式的推導(dǎo)：方法一：設(shè)已給定極小點(diǎn)附近的一個(gè)點(diǎn) 極小點(diǎn)附近與二次函數(shù)很接近，則在t0,因?yàn)橐粋€(gè)二次連續(xù)可微函數(shù)在其10附近用二次函數(shù)逼近 12(t)一(t)= (t 0)+ ,(t 0)(t-t 0)+ 萬 ,(t 0)(t-t 0)2

14、然后以7t)的極小點(diǎn)作為極小點(diǎn)的一個(gè)新的近似點(diǎn)t1由極值必要條件：-(t 1)=0即： (t 0)+ ,(t 0)(t 1-t 0)=0即：t1=t-T,(t。)此式正好為迭代公式。方法二：Newton法的幾何解釋如圖：圖 17.3.1y= ，(t)在tk處的切線與t軸交點(diǎn)的下一個(gè)點(diǎn)作為新的迭代點(diǎn)t k+1.Newton法的最大優(yōu)點(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ì)算起來比較困難。2)方法對(duì)初始點(diǎn)的依賴性很

15、強(qiáng)，初始點(diǎn)不能選得離極小點(diǎn)太遠(yuǎn)，否則所得極小化序列是發(fā)散的，或收斂到非極小點(diǎn)。另外：要求函數(shù)二階導(dǎo)數(shù)正定，即 (, t k) 0。3)當(dāng)曲線 y= ,(t) 在 a,b 中有較復(fù)雜的彎曲時(shí)，這種方法往往失效。4 )即使曲線y=,(t)比較正常，在 a,b 中或上凹或下凹，初始點(diǎn)也必須選擇適當(dāng)。17.4黃金分割法黃金分割法適應(yīng)于區(qū)間 a,b 上的任何單谷函數(shù)(t) 求極小點(diǎn)的問題 .對(duì)函數(shù)除 “ 單谷” 外不作其他要求，甚至可以不連續(xù)，因此這種方法的適應(yīng)面極廣。其特點(diǎn)是只需要計(jì)陣一個(gè)點(diǎn)的位置及其函數(shù)值, 從而極大地減少了工作量。黃金分割的思路是：在a,b內(nèi)適當(dāng)插入兩點(diǎn)3, t2(tit2),將a

16、,b分為三段，通過比較(t1)= 1， (t 2)2便可斷定極小點(diǎn)是在a,t 2 內(nèi)或者是在t 1,b 內(nèi)，從而可用此小區(qū)間取代a,b ，將此縮小了的新區(qū)間記為 a 1,b1.又可在新的區(qū)間內(nèi)取兩點(diǎn) t 3t4, 通過比較函數(shù)值(t 3)3和 (t4)4，即可得新的區(qū)間 a2,b2 如此做下去，最后便可定出近似的極小點(diǎn) .怎樣選擇 t 1,t 2呢?因?yàn)槊看伪容^兩點(diǎn)函數(shù)值區(qū)間都將縮小，如果縮小的區(qū)間中保留的一點(diǎn)仍然用 , 那么除開始的空間要陣兩點(diǎn)的函數(shù)值外后面每一步只須計(jì)陣一個(gè)函數(shù)值即可這樣就節(jié)省了計(jì)陣。假定每次迭代區(qū)間的長(zhǎng)度按比例 縮小， (0 D，則t： a,b ：b,t 2:3，2 ：1

17、,轉(zhuǎn)5)若(t1)= (t 2),則t1 ： a,t 2:b轉(zhuǎn) 1)4)求t1二a+(1- )(b-a), (t)=轉(zhuǎn)2 )5)求t2=a+ (b-a), (t2)= 2轉(zhuǎn)2)。例 17.4.1: min (t)=3t 4-16t 3+30t 2-24t+8解：取a,b=0,3經(jīng)過9次迭代可得:=0.618034=0.001* a+bt =2.001552517.5拋物線插值法上面我們介紹的方法僅對(duì)諸點(diǎn)函數(shù)值大小進(jìn)行比較，而函數(shù)值本身沒有得到充分利用，因而即使對(duì)簡(jiǎn)單函數(shù)如二次函數(shù)也不得不像一般函數(shù)一樣進(jìn)行同樣多 的函數(shù)值計(jì)算，下面介紹拋物線插值法，二次插值法，利用函數(shù)在已知點(diǎn)的值來 確定新的迭

18、代點(diǎn)，當(dāng)函數(shù)有比較好的解析性(如連續(xù)可微)這往往比對(duì)分法，黃 金分割法效果好些。與Newton法一樣，拋物線法也是用二次函數(shù)逼近原函數(shù)，并取二次函數(shù)的極小值點(diǎn)作為新的近似點(diǎn)，不同之處在于：Newton法利用前一點(diǎn)處的函數(shù)值和一、二階導(dǎo)數(shù)值來構(gòu)造二次函數(shù)，拋物線法利用前三個(gè)點(diǎn)的函數(shù)值構(gòu)造 來構(gòu)造二次函數(shù)。 TOC o 1-5 h z 首先，像黃金分割法一樣，找點(diǎn) 10,t 1,t 2并使t0 (t1,t 2),(t 0)(t1),(t0) (t2)； t0，t 1，t 2的確定按黃金分割法中求a,b的公式定，然后利用Lagrange插值公式構(gòu)造二次函數(shù)：飛)(tt1)(t(t0)+(tt。)(t

19、i)+ (tt0)(t t1)(t2)(tot 1 )(t0t 2) (tlt o)(tl t 2) (t2t 0)(t2 t 1 )這是由三個(gè)點(diǎn)：(t0, (t。)、(t 1, (t1)、(t2, (t2)定出的拋物線。求其極小點(diǎn)：f(t) 0t 2t 2tt 2t 2 tt 2t 2t設(shè)：t= (t1t2)(to)(t2t0) (t1)(t0t1)(t2)作為(t)的近似極小點(diǎn)。2(tl t2) (to) (t2 to) (t1) (to t1) (t2)若區(qū)間長(zhǎng)度t2 t1充分小，則lt-t 密若 tot,取 t1,=t1.t o=t.t 2,=to 即可若 toT 取 t1,=to.t o,=ft 2,=t2 即可)若(to) 取 t1,=t o,=to，t2,=t2若 to o :2t：to,： o,轉(zhuǎn)2,o： o,t： ti,：，轉(zhuǎn) 2)若to