第十七章線搜索

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

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

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

4、o)和(to h)的值，轉(zhuǎn) , 3若(to)(toh),比較 (to)和(to h),轉(zhuǎn),。4若(to)(toh),計算(to (2k1)h),h 1,2,，直到有某個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,(實際應該為 V ,的兩倍長。(-V =2 ( v - N)(b)圖 17.1.2(c)因此只需比較V和區(qū)間 卜，的中點 的對應函數(shù)值，即可將區(qū)間2g縮短1/3。由圖(a),(b)可見，當()()時，取山丫的搜

5、索區(qū)間(圖(a)。當()()v, 丫為搜索區(qū)間。(圖(b)當(toh)(to),取t0-h, t0, t0+h為搜索區(qū)間。當(toh)(to),與4類似，計算(to (2k1)h),k 1,2,.,直到有某個 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)鍵是開始時怎樣選擇步長h ,如選

6、得太小，需迭代多次才能找到搜索區(qū)間，而若選得太大，雖然一次就能找到搜索區(qū)間，但給下一步找極小點 過程增加了負擔。下面將介紹選擇初始步長h的一種方法。設(t)具有連續(xù)二階偏導數(shù)，且(to) 0, (to) 00現(xiàn)在要從t0出發(fā)確定一個搜索區(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)的唯一極小點，可作為 (

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

8、搜索來確定 下一個迭代點，每次迭代需要確定直線搜索的初始步長，如下面考察由Zk到Zk+1 迭代的情況。設已獲得迭代點Zk,并按某種規(guī)則選定了向量 Pk為下降方向，并設|Pk 則下一迭代點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)確定 初始步長h,但此時公式(6)中應令t0=0, e應該取f(z)極小值的估計值fe, 即 f(z*)= fe , 又 (0) f(zj (0)f (Zk)T pk從 而h 2fe g/

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

10、t遞減，即t*0,而當t t* ,函數(shù)遞增，即 t 0。若找到一個區(qū)間a,b,滿足性質(zhì) a 0, b 0。則a,b內(nèi)必有 t的極小點t* ,且t*0為找此t* ,取t。b ,若2t00則在a,t0中有極小點，這時用a,t0作新的區(qū)間a,b,繼續(xù)這個過程，逐步將區(qū)間a,b縮小，當區(qū)間a,b的長度充分小時，或者當t0充分小時，即可將a,b的中點取做極小點的近似點，這時有估計:至于區(qū)間a,b的確定，一般可采用下述方法：首先取初始點to ,若 t0 0 ,則在t0右方取點ti t0 t , ( t也是事先給 定的步長)；若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ù)下去。對于t00的情況，可類似于上面在t左側(cè)取點。注意這種方法不僅對于對分法有用，在后面方法中也有用。下面將對分法的 過程敘述一下：已知：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=，則求出駐點t* t,終止；否則轉(zhuǎn)7)若b7)若若2(t)0,則 t: b,轉(zhuǎn)6。例i7.2.i：用對分法求下面問題的極小值點: 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( 精確極小點：t=2,(2)=0,(2)0)17.3 Newton 切線法設：R1R1,

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

14、然后以7t)的極小點作為極小點的一個新的近似點t1由極值必要條件：-(t 1)=0即： (t 0)+ ,(t 0)(t 1-t 0)=0即：t1=t-T,(t。)此式正好為迭代公式。方法二：Newton法的幾何解釋如圖：圖 17.3.1y= ，(t)在tk處的切線與t軸交點的下一個點作為新的迭代點t k+1.Newton法的最大優(yōu)點是收斂速度快，但也有不少缺點：1 ) 在每次迭代時均要計算二階導數(shù)，增加了工作量，而且用數(shù)值微分代替二階導數(shù)時，舍入誤差會影響收斂速度，特別是,(t) 很小時，更加嚴重。對于多元最優(yōu)化問題，計算二階導數(shù)涉及到Hesse陣，計算起來比較困難。2)方法對初始點的依賴性很

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

16、,b分為三段，通過比較(t1)= 1， (t 2)2便可斷定極小點是在a,t 2 內(nèi)或者是在t 1,b 內(nèi)，從而可用此小區(qū)間取代a,b ，將此縮小了的新區(qū)間記為 a 1,b1.又可在新的區(qū)間內(nèi)取兩點 t 3t4, 通過比較函數(shù)值(t 3)3和 (t4)4，即可得新的區(qū)間 a2,b2 如此做下去，最后便可定出近似的極小點 .怎樣選擇 t 1,t 2呢?因為每次比較兩點函數(shù)值區(qū)間都將縮小，如果縮小的區(qū)間中保留的一點仍然用 , 那么除開始的空間要陣兩點的函數(shù)值外后面每一步只須計陣一個函數(shù)值即可這樣就節(jié)省了計陣。假定每次迭代區(qū)間的長度按比例 縮小， (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拋物線插值法上面我們介紹的方法僅對諸點函數(shù)值大小進行比較，而函數(shù)值本身沒有得到充分利用，因而即使對簡單函數(shù)如二次函數(shù)也不得不像一般函數(shù)一樣進行同樣多 的函數(shù)值計算，下面介紹拋物線插值法，二次插值法，利用函數(shù)在已知點的值來 確定新的迭

18、代點，當函數(shù)有比較好的解析性(如連續(xù)可微)這往往比對分法，黃 金分割法效果好些。與Newton法一樣，拋物線法也是用二次函數(shù)逼近原函數(shù)，并取二次函數(shù)的極小值點作為新的近似點，不同之處在于：Newton法利用前一點處的函數(shù)值和一、二階導數(shù)值來構(gòu)造二次函數(shù)，拋物線法利用前三個點的函數(shù)值構(gòu)造 來構(gòu)造二次函數(shù)。 TOC o 1-5 h z 首先，像黃金分割法一樣，找點 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 )這是由三個點：(t0, (t。)、(t 1, (t1)、(t2, (t2)定出的拋物線。求其極小點：f(t) 0t 2t 2tt 2t 2 tt 2t 2t設：t= (t1t2)(to)(t2t0) (t1)(t0t1)(t2)作為(t)的近似極小點。2(tl t2) (to) (t2 to) (t1) (to t1) (t2)若區(qū)間長度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