最優(yōu)化 第3章 一維搜索方法

1、第三章,一維搜索方法,3.3,一維搜索的試探法,3.1,搜索區(qū)間的確定,3.2,區(qū)間消去法原理,3.4,一維搜索的插值法,求解,一維目標函數,f,(X),最優(yōu)解的過程，稱為,一維優(yōu)化,(,一,維搜索,),，所使用的方法稱為,一維優(yōu)化方法,。,由前,數值迭代法,可知，求某目標函數的最優(yōu)值時，,迭代過,程,每一步的格式都是從,某一定點,X,(,k,),出發(fā)，沿著某一使目標,函數下降的規(guī)定,方向,S,(,k,),搜索，以找出此方向的,極小點,X,(,k,+1),。這一過程是各種最優(yōu)化方法的一種,基本過程,。,一維搜索方法,一般,分兩步進行,：,首先,確定,一個包含函數極小點的,初始區(qū)間,，即,確定,

2、函數的搜索區(qū)間，該區(qū)間必須是,單峰區(qū)間,；,然后采用縮小區(qū)間或插值逼近的方法,得到,最優(yōu)步長,，,最終求出該搜索區(qū)間內的,一維極小點,。,3.1,搜索區(qū)間的確定,根據函數的變化情況，可將,區(qū)間,分為,單峰區(qū)間,和,多峰區(qū)間,。,所謂,單峰區(qū)間,，就是在該區(qū)間內的函數變化只有一個峰值，,即函數的極小值。,即在,單峰區(qū)間,內的,極小值點,X,*,的,左側,：函數呈,下降趨勢,，,而在,單峰區(qū)間,內的,極小值點,X,*,的,右側,：函數呈,上升趨勢,。,也就是說，,單峰區(qū)間,的函數值呈,“高,-,低,-,高”,的變化特征,。,3.1,搜索區(qū)間的確定,x*,a,b,x,0,f,(,x,),目前在一維優(yōu)

3、化搜索中確定,單峰區(qū)間,常用的方法,是,進退試算法,。,進退試算法的,基本思想,為：,1),按照一定的規(guī)律給出,若干試算點,，,2),依次比較各,試算點的函數值,的大小，,3),直到找到,相鄰三點,函數值按,“高,-,低,-,高”,變化的,單峰區(qū)間,為止,3.1,搜索區(qū)間的確定,進退試算法的,運算步驟,如下：,(2),將,0,及,0,+,h,代入目標函數,f,(x),進行計算并比較大小,(1),給定,初始點,0,和,初始步長,h,3.1,搜索區(qū)間的確定,f,(,x,),x,0,a,b,a,0,f,(,a,0,),a,0,+h,f,(,a,0,+h,),a,0,+,3,h,f,(,a,0,+,3

4、,h,),f,(,x,),x,0,a,b,a,0,-h,f,(,a,0,-h,),a,0,f,(,a,0,),a,0,+h,f,(,a,0,+h,),若,f,(,0,+,h,) ,f,(,0,+3,h,),，則所計算的相鄰三點,的函數值已具“,高,-,低,-,高,”特征，這時可確定,搜索區(qū)間,(3),若,f,(,0,),f,(,0,+,h,),，則表明極小點在試算點,的右側，需做,前進試算,。,0,0,3,a,b,h,?,?,?,?,?,否則，將步長再加倍，并重復上述運算。,3.1,搜索區(qū)間的確定,在做,前進運算,時，為加速計算，可將步長,h,增加,2,倍，并取計算新點為,0,+,h,+2,h

5、,=,0,+3,h,(4),若,f,(,0,) ,f,(,0,+,h,),，則表明極小點在試算點,的左側，需做,后退試算,。,在做后退運算時，應將,步長變?yōu)?-,h,，并從,點出,0,發(fā)，得到后退點為,0,-,h,若,f,(,0,-,h,) ,f,(,0,),，則,搜索區(qū)間,可取為,0,0,a,h,b,h,?,?,?,?,?,?,否則，將步長加倍，繼續(xù)后退，重復,上述步驟,，,直到滿足,單峰區(qū)間,條件為止。,3.1,搜索區(qū)間的確定,f,(,b,1,),f,(,a,1,),f,(,b,1,),f,(,a,1,),f,(,b,1,),a,f,(,a,1,),搜索區(qū)間確定,之后，采用區(qū)間消去法逐步,

6、縮短搜索區(qū)間,，,找到極小點的數值近似解。,假定在搜索區(qū)間內,a,b,任取兩點,a,1,、,b,1,且,a,1,b,1,f,1,f,（,a,1,），,f,2,f,（,b,1,）,一、基本思想,a,1,a,1,a,1,b,1,b,a,a,b,b,b,1,b,1,3.2,區(qū)間消去法原理,f,1,f,2,f,1,f,2,f,1,=,f,2,f,(,x,),f,(,x,),f,(,x,),(1),f,1,f,2,新區(qū)間為,a,b,1,(2),f,1,f,2,新區(qū)間為,a,1,b,(3),f,1,=,f,2,新區(qū)間為,a,1,b,1,對于上述,縮短后的新區(qū)間,，可在其內再取一個,新點,，然后,將此點和該

7、區(qū)間內剩下的那一點進行函數值大小的比較，,以再次按照,上述方法,，進一步,縮短區(qū)間,，這樣不斷進行下,去，直到,所保留的區(qū)間,縮小到給定的誤差范圍內，而得到,近似最優(yōu)解,。,1,2,f,f,?,新區(qū)間為,a,1,b,f,(,b,1,),a,f,(,a,1,),a,1,b,1,b,f,(,b,1,),f,(,a,1,),a,1,a,b,b,1,f,(,b,1,),f,(,a,1,),a,1,b,a,b,1,1,1,1,2,2,2,(1,)(,),(,),(,),(,),a,a,b,a,f,f,a,a,a,b,a,f,f,a,?,?,?,?,?,?,?,?,?,?,?,?,一、適用范圍,適用于,a

8、,b,區(qū)間上的任何,單谷函數,求極小值問題。對,函數除要求“單峰”外不作其他要求，甚至可以,不連,續(xù),。適應面相當廣?；驹頌?區(qū)間消去法,3.3,黃金分割法,黃金分割法插入兩點：,f,(,a,2,),a,f,(,a,1,),a,1,a,2,b,f,(,a,2,),a,f,(,a,1,),a,1,b,a,2,黃金分割法還要求在保留下來的區(qū)間內再插入一點所形成,的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布,。,2,1,5,1,0.618,2,?,?,?,?,?,?,?,?,3.3,黃金分割法,2,1,2,a,b,1,1-,1,3,(1-,),2,a,a,b,?,?,?,黃金分割法程序框圖,

9、開,始,輸入,a,b,?,1,2,0.382(,),0.618(,),x,a,b,a,x,a,b,a,?,?,?,?,?,?,1,2,(,),(,),f,x,f,x,?,Y,2,2,1,2,1,1,1,1,0.382(,),(,),b,x,x,x,f,f,x,a,b,a,f,f,x,?,?,?,?,?,?,?,N,1,1,2,1,2,2,2,2,0.618(,),(,),a,x,x,x,f,f,x,a,b,a,f,f,x,?,?,?,?,?,?,?,結,束,Y,*,*,*,0.5(,),(,),x,a,b,f,f,x,?,?,?,N,a,f,(,x,2,),f,(,x,1,),b,x,1,x,

10、2,b,x,2,f,(,x,2,),x,1,例,3-1,用黃金分割法求函數,f,(,x,)=3,x,3,-4,x,+2,的極小點，,初始點,x,0,=0,步長,h,=1,精度,=0.2,。,解：,1,）,確定初始區(qū)間,x,1,=,x,0,=0,f,1,=,f,(,x,1,)=2,x,2,=,x,0,+,h,=0+1=1,f,2,=,f,(,x,2,)=1,由于,f,1,f,2,應繼續(xù)向前探測,x,3,=,x,0,+2,h,=0+2=2,f,3,=,f,(,x,3,)=18,由于,f,2,f,3,可知初始區(qū)間已經找到，即,a, b=,x,1,x,3,=0, 2,3.3,黃金分割法,f,(,x,1

11、,)=2,x,1,=0,f,(,x,2,)=1,x,2,=1,f,(,x,3,)=18,x,3,=2,a,b,2,）,用黃金分割法縮小區(qū)間,第一次縮小區(qū)間：,x,1,=0+0.382,(2-0)=0.764,f,1,=0.282,x,2,=0+0.618,(2-0)=1.236,f,2,=2.72,由于,f,1,f,2,故,新區(qū)間,a, b=a,x,2,=0, 1.236,由于,b-a,1.236,0.2,應繼續(xù)縮小區(qū)間,3.3,黃金分割法,f,(,x,1,)=0.282,x,1,=0.764,f,(,x,2,)=2.72,x,2,=1.236,a,b,b,3.3,黃金分割法,第二次縮小區(qū)間：

12、,令,x,2,=,x,1,=0.764,f,2,=,f,1,=0.282,x,1,=0+0.382,(1.236-0)=0.472,f,1,=0.317,由于,f,1,f,2,故,新區(qū)間,a, b=,x,1, b=0.472, 1.236,由于,b-a=1.236-0.472=0.764,0.2,應繼續(xù)縮小區(qū)間,f,(,x,1,)=0.282,x,1,=0.764,f,(,x,2,)=2.72,x,2,=1.236,a,b,b,x,2,f,(,x,2,),x,1,f,(,x,1,),a,第三次縮小區(qū)間：,令,x,1,=,x,2,=0.764,f,1,=,f,2,=0.282,x,2,=0.47

13、2+0.618,(1.236-0.472)=0.944,f,2,=0.747,由于,f,1,f,2,故,新區(qū)間,a,b=a,x,2,=0.472, 0.944,由于,b-a=0.944-0.472=0.472,0.2,應繼續(xù)縮小區(qū)間。,3.3,黃金分割法,第四次縮小區(qū)間：,令,x,2,=,x,1,=0.764,f,2,=,f,1,=0.282,x,1,=0.472+0.382,(0.944-0.472)=0.652,f,1,=0.223,由于,f,1,f,2,故,新區(qū)間,a,b=a,x,2,=0.472, 0.764,由于,b-a=0.764-0.472=0.292,0.2,應繼續(xù)縮小區(qū)間。,

14、第五次縮小區(qū)間：,令,x,2,=,x,1,=0.652,f,2,=,f,1,=0.223,x,1,=0.472+0.382,(0.764-0.472)=0.584,f,1,=0.262,由于,f,1,f,2,故,新區(qū)間,a,b=,x,1,b=0.584, 0.764,因為,b-a=0.764-0.584=,0.180.2,停止迭代。,黃金分割法,求的的極小點與極小值：,x,=0.5,(0.584+0.764)=0.674,f,(,x,)=0.222,3.3,黃金分割法,求導運算,求的極小點與極小值：,x,=0.667,f,(,x,)=0.222,一、牛頓法,3.4,插值方法,利用一點的,函數值

15、,、,一階導數,以及,二階,導數,構造二次多項,式。用構造的二次,多項式的極小點作,為原函數極小點的,近似。,x,*,x,f,(,x,),x,2,0,(,x,),x,0,f,(,x,),1,(,x,),x,1,一、牛頓法,設,f,(,x,),為一個連續(xù)可微的函數，則在點,x,0,附近,進行泰勒展開并保留到二次項：,2,0,0,0,0,0,1,(,),(,),(,),(,)(,),(,)(,),2,f,x,x,f,x,f,x,x,x,f,x,x,x,?,?,?,?,?,?,?,1,(,),0,x,?,?,用二次函數,(,x,),的極小點,x,1,作為,f,(,x,),極小點的一個近似,點。根據極

16、值必要條件,:,3.4,插值方法,x,f,(,x,),x,1,x,2,0,(,x,),x,*,f,(,x,),1,(,x,),x,0,0,0,1,0,(,),(,)(,),0,f,x,f,x,x,x,?,?,?,即,0,1,0,0,(,),(,),f,x,x,x,f,x,?,?,依此類推可得,牛頓迭代公式：,1,(,),(,),k,k,k,k,f,x,x,x,f,x,?,?,?,一、牛頓法,3.4,插值方法,x,2,x,1,x,0,x,*,f,(,x,),f,(,x,),0,(,x,),1,(,x,),在,x,0,處用一拋物線,(,x,),代替曲線,f,(,x,),，,相當于用一斜直線,(,x

17、,),代替曲線,f,(,x,),。這樣各個近似點,是通過對作,f,(,x,),切,線求得與軸的交點,找到的，所以有時,牛頓法又稱作切線,法。,x,2,x,1,x,0,x,*,f,(,x,),0,(,x,),1,(,x,),f ,(,x,),f ,(,x,),x,*,x,0,1,(,x,),x,2,x,1,1,k,k,x,x,?,?,?,?,牛頓法程序框圖,開,始,計算,，,Y,*,1,k,x,x,?,?,N,給定初始點,，誤差,令,k=0,?,?,0,x,?,(,),(,),k,k,f,x,f,x,?,?,計算,，,1,(,),(,),k,k,k,k,f,x,x,x,f,x,?,?,?,1,k

18、,k,?,?,結,束,數值,k,0,1,2,3,4,3,5.1667,4.33474,4.03960,4.00066,-52,153.35183,32.30199,3.38299,0.00551,24,184.33332,109.44586,86.86992,84.04720,5.1667,4.33474,4.03960,4.00066,4.00059,2.1667,0.83196,0.29514,0.03894,0.00007,例,3-2,給定,f,(,x,)=,x,4,-4,x,3,-6,x,2,-16x+4,，試用牛頓法計算其極小點。,k,x,?,?,k,f,x,?,?,?,k,f,x,

19、?,?,給定初始點,x,0,=3,，,=0.001,，計算公式：,1,(,),(,),k,k,k,k,f,x,x,x,f,x,?,?,?,?,?,2,12,24,12,f,x,x,x,?,?,?,?,?,函數的二階導數：,3,2,(,),4,12,12,16,f,x,x,x,x,?,?,?,?,?,解：,函數的一階導數：,3.4,插值方法,1,?,k,x,1,k,k,x,x,?,?,?,=,優(yōu)點,：,1,）收斂速度快。,缺點,：,1,）要計算函數的一階和二階導數，增加每次,迭代的工作量。,2,）數值微分計算函數二階導數，舍入誤差將,嚴重影響牛頓法的收斂速度，,f,(,x,),的值越,小問題越嚴

20、重。,3,）牛頓法要求,初始點離極小點不太遠,，否則,可能使極小化序列發(fā)散或收斂到非極小點。,一、牛頓法,3.4,插值方法,1,(,),(,),k,k,k,k,f,x,x,x,f,x,?,?,?,(,1),(,),(,),(,),k,k,K,k,X,X,d,?,?,?,?,二、二次插值法（,拋物線法,）,在給定的,單峰區(qū)間,中，利用目標函數上的,三個點,來,構,造,一個,二次插值函數,，以近似地表達,原目標函數,f,(,a,),，并,求這個插值函數的,極小點,近似作為原目標函數的,極小點,。,3.4,插值方法,2,(,)=A,B,C,p,x,x,x,?,?,B,=-,2C,p,x,f,(,x,

21、),x,f,1,x,1,f,2,x,2,f,3,x,3,x,p,x,*,y,0,x,x,p1,x,1,x,2,x,p,x,3,x,y,0,x,*,y,1,y,2,y,p,y,3,x,1,x,2,x,p,x,*,y,1,y,2,y,p,y,p1,x,p,x,p1,x,1,x,2,x,p,x,3,x,y,0,x,*,y,1,y,2,y,p,y,3,x,2,x,3,x,y,0,x,*,y,2,y,p,y,3,y,p1,2,1,1,1,1,2,2,2,2,2,2,3,3,3,3,p(,),A,B,C,p(,),A,B,C,p(,),A,B,C,x,x,x,f,x,x,x,f,x,x,x,f,?,?,?

22、,?,?,?,?,?,?,?,?,?,?,?,?,?,?,構造的,二次插值函數曲線,通過,原函數,上的三個點,:,解得,系數,2,2,2,2,2,2,2,3,1,3,1,2,1,2,3,1,2,2,3,3,1,2,3,1,3,1,2,1,2,3,1,2,2,3,3,1,(,),(,),(,),(,)(,)(,),(,),(,),(,),(,)(,)(,),x,x,f,x,x,f,x,x,f,B,x,x,x,x,x,x,x,x,f,x,x,f,x,x,f,C,x,x,x,x,x,x,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,2,2,2,2,2,2,2,3,1,3

23、,1,2,1,2,3,2,3,1,3,1,2,1,2,3,(,),(,),(,),1,2,2,(,),(,),(,),p,x,x,f,x,x,f,x,x,f,B,C,x,x,f,x,x,f,x,x,f,?,?,?,?,?,?,?,?,?,?,?,?,?,?,可求得,二、二次插值法（,拋物線法,）,3.4,插值方法,2,p,x,x,?,?,?,二次插值法程序框圖,開,始,計算,，,Y,*,2,min,p,y,y,y,?,N,給定,1,2,3,1,2,3,x,x,x,y,y,y,?,?,?,?,?,?,?,?,p,p,x,y,縮短區(qū)間,名稱置換,結,束,x,1,x,2,x,p,x,3,x,y,0,x,*,y,1,y,2,y,p,y,3,x,1,x,2,x,p,x,3,x,0,x,*,y,y,1,y,2,y,p,y,3,*,2,min,p,y,y,y,?,二次插值法程序編制換名方法,(1),1),x,2,x,p,y,2,y,p,y,2,y,p,y,2,y,1,y,p,y,2,x,p,x,1,x,2,x,3,x,y,2,y,p,y,3,x,p,x,1,x,2,x,3,x,x,1,x,2,x,3,二次插值法程序編制換名方法,(2),2),x,2,x,p,y,2,y,p,y,p,y,2,y,2,y,3,x,p,x,1,x,2,x,3,x,x,3,x,2,y,2,y,p,y,p,y,1,y,2