優(yōu)化一維搜索

1、一.一維搜索問題二.一維搜索法的思想 三.搜索區(qū)間及其確定方法四.一維搜索的分類五.方法簡述六.一維搜索方法的發(fā)展 一維搜索方法一維搜索方法一.一維搜索問題 （目標(biāo)函數(shù)為單變量的非線性規(guī)劃問題） 一維搜索又稱線性搜索(Line Search)，就是指單變量函數(shù)的最優(yōu)化，它是多變量函數(shù)最優(yōu)化的基礎(chǔ)，是求解無約束非線性規(guī)劃問題的基本方法之一。 有關(guān)一維搜索算法的研究歷史悠久，研究成果十分豐富。 一維搜索既可獨(dú)立的用于求解單變量最優(yōu)化問題，同時(shí)又是求解多變量最優(yōu)化問題常用的手段，雖然求解單變量最優(yōu)化問題相對(duì)比較簡單，但其中也貫穿了求解最優(yōu)化問題的基本思想。由于一維搜索的使用頻率較高，因此努力提高求解

2、單變量問題算法的計(jì)算效率具有重要的實(shí)際意義。當(dāng)方向 給定，求最佳步長就是求一元函數(shù) :kdk1()()()kkkkkff xxd的極值問題，這一過程被稱為一維搜索. 當(dāng)采用數(shù)學(xué)規(guī)劃法尋求多元函數(shù)的極值點(diǎn)時(shí)，一般要進(jìn)行一系列如下格式的迭代計(jì)算:問題簡述問題簡述1(0,1,2,)kkkkkxxd二.一維搜索法的思想 一維搜索法求解一維目標(biāo)函數(shù)的極值點(diǎn)的數(shù)值迭代方法，可歸結(jié)為單變量函數(shù)的極小化問題。雖然優(yōu)化設(shè)計(jì)中的大部分問題都是多維問題，但是一維優(yōu)化方法是優(yōu)化中最基本的方法，在數(shù)值迭代過程中都要進(jìn)行一維搜索，因此對(duì)一維搜索的研究有著重要的意義。三.搜索區(qū)間及確定方法 O f (a) b x* x a

3、 1.單谷單谷(峰）區(qū)間峰）區(qū)間l在給定區(qū)間內(nèi)僅有一個(gè)谷值的函數(shù)稱為單谷數(shù)，其區(qū)間稱為單谷區(qū)間。 2. 找初始單谷區(qū)間是一維找初始單谷區(qū)間是一維搜索的第一步搜索的第一步.第二步使區(qū)間縮小。 單谷區(qū)間中一定能求得一個(gè)極小點(diǎn)函數(shù)值：“大小大”圖形：“高低高”（1）選定初始點(diǎn)a, 初始步長hh0，計(jì)算 y1f(a1)， y2f(a1h)。（2）比較y1和y2。 （a）如y1y2, 向右前進(jìn)；加大步長 h2 h ，轉(zhuǎn)（3）向前。 （b）如y1y2, 向左后退；h h0，轉(zhuǎn)（3）向后探測。 （c）如y1y2，極小點(diǎn)在a1和a1h之間。l基本思想：基本思想：l對(duì)f(x)任選一個(gè)初始點(diǎn)a1及初始步長h， 通

4、過比較這兩點(diǎn)函數(shù)值的大小，確定第三點(diǎn)位置，比較這三點(diǎn)的函數(shù)值大小，確定是否為 “高低高” 形態(tài)。3.3.確定初始單谷區(qū)間的進(jìn)退法確定初始單谷區(qū)間的進(jìn)退法步驟：（3）產(chǎn)生新的探測點(diǎn)a3a1h，y3f(a3);（4）比較函數(shù)值 y2與y3：（a）如y20時(shí)，a,b=a1,a3; hy3, 加大步長 h2 h ，a1=a2, a2=a3,轉(zhuǎn)（3）繼續(xù)探測。y1y3y2y2y1a3a2a2a1a1Oaa3h0h02h0y1y2a2a3a1a2a1Oaa32h0h0h0y3y1y2y1y2y3a1a2f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1 b1baabab b1b1f

5、1f（a1）， f2f（b1）l搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，從而找到極小點(diǎn)的數(shù)值近似解。l假定在搜索區(qū)間內(nèi)a,b 任取兩點(diǎn)a1,b1; 4 4. .區(qū)間消去法原理區(qū)間消去法原理f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1b1baabab b1 b1綜合為兩種情況：若 則取 為縮短后的搜索區(qū)間。若 則取 為縮短后的搜索區(qū)間。11( )( )f af b1 ,a b11()()f af b1 , a bl f1f（a1）， f2f（b1）l(1)如f1f2, 則縮小的新區(qū)間為a1,b;l(3)如f1=f2, 則縮小的新區(qū)間為a1,b1四.一維搜索

6、的分類1.1.精確一維搜索精確一維搜索 二分法，黃金分割法，F(xiàn)ibonacci法（分?jǐn)?shù)法），割線法成功失敗法不用函數(shù)導(dǎo)數(shù)的方法 牛頓法，插值法（拋物線法，三次插值法）需要用到函數(shù)導(dǎo)數(shù)2.2.不精確一維搜索不精確一維搜索 常用的不精確一維搜索算法包括利用簡單準(zhǔn)則的后退方法、經(jīng)典的ArmijoGoldstein方法、Wolfe-Powell方法和強(qiáng)Wolfe-Powell方法、以及其后發(fā)展起來的利Curry-Altman步長律、改進(jìn)的Curry-Altman步長律、Danilin-Pshenichuyi步長律、De Leone-G-rippo步長律Backtracking步長律等的各種方法。121

7、.1.精確一維搜索精確一維搜索 精確一維搜索，作為一種理想的狀態(tài)，雖然在實(shí)際計(jì)算中被采用的概率較之不精確一維搜索要小，但有關(guān)精確一維搜索技術(shù)的研究歷史悠久成果相當(dāng)豐富，方法眾多，其理論體系也相對(duì)比較完備，對(duì)其進(jìn)行進(jìn)一步的研究仍有著重要的理論意義和現(xiàn)實(shí)意義。 通常我們根據(jù)算法中有無使用導(dǎo)數(shù)的情況，將精確一維搜索算法分為兩大類：一類是不用函數(shù)導(dǎo)數(shù)的方法，這其中就包括二分法(又稱作對(duì)分法或中點(diǎn)法)、0618法(黃金分割法)、Fibonacci法(分?jǐn)?shù)法)、割線法、成功一失敗法等；另類是使用函數(shù)導(dǎo)數(shù)的方法，包括經(jīng)典的Newton法、拋物線法以及各種插值類方法等。 (i)在不用導(dǎo)數(shù)的方法中，二分法、06

8、18法(黃金分割法)以及Fibonacci法均是分割方法，其基本思想就是通過取試探點(diǎn)和進(jìn)行函數(shù)值比較，使包含極小點(diǎn)的搜索區(qū)間不斷縮短，當(dāng)區(qū)間長度縮短到一定程度時(shí)，區(qū)間上各點(diǎn)的函數(shù)值均接近函數(shù)的極小值，從而各點(diǎn)均可看作極小點(diǎn)的近似。分割類方法僅需計(jì)算函數(shù)值，因此使用的范圍較廣，尤其適用于非光滑及導(dǎo)數(shù)表達(dá)式復(fù)雜或?qū)懖怀龅惹樾?。具體到各種方法他們也各有自己的優(yōu)勢和不足，下面我們分別簡述之。 1）二分法是一種最簡單的分割方法，每次迭代都將搜索區(qū)間縮短一半，故二分法的收斂速度是線性的，收斂比為0.5，收斂速度較慢。其優(yōu)勢就是每一步迭代的計(jì)算量都相對(duì)較小，程序簡單，而且總能收斂到一個(gè)局部極小點(diǎn)。 2）黃金

9、分割法是一種針對(duì)目標(biāo)函數(shù)是單峰函數(shù)亦即目標(biāo)函數(shù)為凸的情形的分割類方法，因其不要求函數(shù)可微，且每次迭代只需計(jì)算一個(gè)函數(shù)值，程序簡單容易實(shí)現(xiàn)而被廣泛采用。由于黃金分割法是以等比例百0.618分割縮小區(qū)間的，因此它是一種近似最優(yōu)方法。 針對(duì)在實(shí)際中遇到的目標(biāo)函數(shù)往往不是單峰函數(shù)的情況，Hopfinger(1976)提出了0.618法的改進(jìn)形式，即在縮小區(qū)間時(shí)，不只是比較兩個(gè)內(nèi)點(diǎn)處的函數(shù)值，而是對(duì)兩內(nèi)點(diǎn)及其兩端點(diǎn)處的函數(shù)值進(jìn)行綜合比較，以避免搜索得到的函數(shù)值反而比初始區(qū)間端點(diǎn)處的函數(shù)值大的情況。經(jīng)過這樣的修改，算法比O618法要更加可靠。 3） Fibonacci法是另一種與0618法相類似的分割類方

10、法，兩者的主要區(qū)別在于Fibonacci法搜索區(qū)間的縮短比率不是采用黃金分割數(shù)，而是采用FJbonacci數(shù)列。在使用Fibonacci法時(shí)，通常是由用戶給定最終區(qū)間長度的上限，從而確定探索點(diǎn)的個(gè)數(shù)，逐步進(jìn)行搜索。通過對(duì)Fibonacci數(shù)列進(jìn)行分析表明，在迭代次數(shù)以 的情形，F(xiàn)bonacci法與0.618法的區(qū)間縮短率相同，因而Fibonacci法的收斂速度也是線性的，收斂比也是黃金分割數(shù)。可以證明，F(xiàn)ibonacci法是分割方法求解一維極小化問題的晟優(yōu)策略，而O.618法只是近似雖優(yōu)的，但因0618法不必預(yù)先知道探索點(diǎn)的個(gè)數(shù)，程序?qū)崿F(xiàn)更加容易，因而應(yīng)用也更加廣泛。n 4）割線法與分割法類似

11、，也是通過取試探點(diǎn)和進(jìn)行函數(shù)值比較，使包含所求點(diǎn)的搜索區(qū)間縮小，但試探點(diǎn)的取法與分割法不同，它是選取連接兩個(gè)端點(diǎn)的線段與橫軸的交點(diǎn) 作為試探點(diǎn)。割線法不能保證每次都使搜索區(qū)間縮小一定的比例，因而不具有全局線性收斂性，但是它卻利用了函數(shù)的一些性質(zhì)。在函數(shù)接近線性時(shí)，它是非?？斓?。如果函數(shù)本身是線性函數(shù)時(shí)，它可以一步找到解。 1） 插值法是一類重要的一維搜索方法，其基本思想是在搜索區(qū)間內(nèi)不斷用低次強(qiáng)常不超過三次)多項(xiàng)式來逼近目標(biāo)函數(shù)，并用插值多項(xiàng)式的極小點(diǎn)去近似目標(biāo)函數(shù)的極小點(diǎn)。實(shí)踐表明，在目標(biāo)函數(shù)具有較好的解析性質(zhì)時(shí)，插值方法比直接方法(如0618或Fibonacci法)效果更好。 2）牛頓法的

12、優(yōu)點(diǎn)是收斂速度快，具有局部二階收斂速度：缺點(diǎn)是要在每個(gè)迭代點(diǎn)處計(jì)算函數(shù)的二階導(dǎo)數(shù)值，增加了每次迭代的工作量，而且它要求迭代初始點(diǎn)要選的好，也就是說初始點(diǎn)不能離極小值太遠(yuǎn)，在極小點(diǎn)未知的情況下，做到這一點(diǎn)是很困難的，這就限制了算法的應(yīng)用范圍，導(dǎo)致算法不實(shí)用。事實(shí)上，牛頓法也是插值類方法的一種。 3）拋物線法也可稱作三點(diǎn)二次插值法，其基本思想與下面要敘述的牛頓法相同，也是用二次函數(shù)近似目標(biāo)函數(shù)，并以其極小點(diǎn)去近似目標(biāo)函數(shù)的極小點(diǎn)，不同之處是牛頓法是利用目標(biāo)函數(shù)f(x)在 處的二階Taylor展式來逼近f(x)，而拋物線法則是利用目標(biāo)函數(shù)f(x)在三個(gè)點(diǎn) , , 處的函數(shù)值構(gòu)造一個(gè)二次函數(shù)作為其近似

13、。一般地，拋物線法并不能保證算法一定收斂，迭代過程中有可能會(huì)出現(xiàn)相鄰迭代點(diǎn) ， 充分接近,且 ，并非函數(shù)近似極小點(diǎn)的退化隋況。0 x0 x1x2xkx1kx1kx(ji)一般地，使用導(dǎo)數(shù)的方法通常包括Newton法、插值法等，其中插值法又有一點(diǎn)二次插值法(牛頓法)、二點(diǎn)二次插值法(I)(II)、三點(diǎn)二次插值法以及三次插值法、有理插檀法等常用方法。 求一維無約束極小化問題的牛頓法是從計(jì)算方法中方程求根的牛頓法演化而來的，其基本思想是用目標(biāo)函數(shù)f(x)在已知點(diǎn) 處的二階Taylor展式g(x)來近似代替目標(biāo)函數(shù)，用g(x)的極小點(diǎn)作為f(x)的近似極小點(diǎn)。 牛頓法的優(yōu)點(diǎn)是收斂速度快，具有局部二階收

14、斂速度：缺點(diǎn)是要在每個(gè)迭代點(diǎn)處計(jì)算函數(shù)的二階導(dǎo)數(shù)值，增加了每次迭代的工作量，而且它要求迭代初始點(diǎn)要選的好，也就是說初始點(diǎn)不能離極小值太遠(yuǎn)，在極小點(diǎn)未知的情況下，做到這一點(diǎn)是很困難的，這就限制了算法的應(yīng)用范圍，導(dǎo)致算法不實(shí)用。事實(shí)上，牛頓法也是插值類方法的一種。0 x五五. .方法簡述方法簡述 二分法二分法 黃金分割法黃金分割法 FibonacciFibonacci法法 割線法割線法 牛頓法牛頓法 拋物線法拋物線法 三次插值法三次插值法 二分法二分法 基本原理 min ( ) t)(mintbta確定一個(gè)有限搜索區(qū)間 ba，設(shè) 在已獲得的搜索區(qū)間 內(nèi)具有連續(xù)的一階導(dǎo)數(shù) 11RR：ba，因?yàn)榭蓪?dǎo)

15、連續(xù) 有最小值 令 ，總可求得極小點(diǎn) 0)( t*t不妨設(shè) 在 上是單減函數(shù)；在 上是單增函數(shù)則 )(t)(*ta，)(*bt ，當(dāng) 時(shí)， ，故 ； )(*tat，0)( t0)( a當(dāng) 時(shí)， ，故 ； )(*btt，0)( t0)( b迭代步驟 已知 ， 表達(dá)式，終止限 )(t( ) t(1) 確定初始搜索區(qū)間 ，要求 ,ba( )0( )0ab，(2) 計(jì)算 的中點(diǎn) ,ba)(21bac(3) 若 ，則 ，轉(zhuǎn)(4)； 若 ，則 ，轉(zhuǎn)(5)； 若 ，則 ，轉(zhuǎn)(4) 0)( cca 0)( cct *0)( ccb (4) 若 ，則 ， 轉(zhuǎn)(5)；否則轉(zhuǎn)(2) |ba)(21*bat(5) 打

16、印 ，結(jié)束 *t說明：由于每次迭代都取區(qū)間中點(diǎn)，使區(qū)間長度縮短一半，故名曰對(duì)分法或二分法。 12, l黃金分割法適用于a,b區(qū)間上的任何單谷函數(shù)求極小值問題。對(duì)函數(shù)除要求“單谷”外不作其他要求，甚至可以不連續(xù)。因此，這種方法的適應(yīng)面相當(dāng)廣。l黃金分割法也是建立在區(qū)間消去法原理基礎(chǔ)上的試探方法。 l在搜索區(qū)間內(nèi)a,b適當(dāng)插入兩點(diǎn) ，將區(qū)間分成三段；l利用區(qū)間消去法，使搜索區(qū)間縮小，通過迭代計(jì)算，使搜索區(qū)間無限縮小，從而得到極小點(diǎn)的數(shù)值近似解。黃金分割法黃金分割法12, 黃金分割法還要求在保留下來的區(qū)間內(nèi)再插入一點(diǎn)所形黃金分割法還要求在保留下來的區(qū)間內(nèi)再插入一點(diǎn)所形成的區(qū)間新三段，與原來區(qū)間的三段

17、具有相同的比例分布成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布 。ab2111a213(1)2圖2-5 黃金分割法21510.6182 f(a1)f(a2)f(a1)f(a2)a1 a1 a2abab a2111222(1)(),( )(),()aabaff aaabaff a黃金分割法要求插入兩點(diǎn)：黃金分割法要求插入兩點(diǎn)：黃金分割法區(qū)間消去示意：黃金分割法區(qū)間消去示意：1212ff2 ,a12ff1 , a b22121,bff11212,aff黃金分割法的搜索過程：黃金分割法的搜索過程：l1）給出初始搜索區(qū)間及收斂精度 ，將賦以0.618。l2）按坐標(biāo)點(diǎn)計(jì)算公式計(jì)算 ， ；并計(jì)算其對(duì)

18、應(yīng)的函數(shù)值。l3）根據(jù)區(qū)間消去法原理縮短搜索區(qū)間。為了能用原來的坐標(biāo)點(diǎn)計(jì)算公式，需進(jìn)行區(qū)間名稱的代換，并在保留區(qū)間中計(jì)算一個(gè)新的試驗(yàn)點(diǎn)及其函數(shù)值。l如果 ，則新區(qū)間 令 , 記N0=0;l如果 ，則新區(qū)間l令 , 記N0=1;4）檢查區(qū)間是否縮短到足夠小和函數(shù)值收斂到足夠精度，如果收斂條件滿足，則取最后兩試驗(yàn)點(diǎn)的平均值作為極小點(diǎn)的數(shù)值近似解。如果條件不滿足則轉(zhuǎn)向步驟5）。 黃金分割法總結(jié)黃金分割法總結(jié)黃金分割法是通過所選試點(diǎn)的函數(shù)值而逐步縮短單谷區(qū)間來搜索最優(yōu)點(diǎn)，該方法適用于單谷區(qū)間a,b上的任何函數(shù)，甚至可以是不連續(xù)函數(shù)，因此這種算法屬于直接法，適應(yīng)相當(dāng)廣泛。Fibonacci法 , 2 ,

19、 111110kFFFFFkkk)()(111kkknknkkkkknknkkabFFaabFFa1, 2 , 1nk其中迭代次數(shù)n不包括初始區(qū)間端點(diǎn)的計(jì)算。經(jīng)n-1次迭代后得到的區(qū)間長度：)(1121nnnnabFFab)(1113221abFFFFFFnn)(111abFn分?jǐn)?shù)法的計(jì)算步驟如下： Fibonacci法的區(qū)間收縮比率的極限: 618. 0lim1nnnFFFibonacciFibonacci法總結(jié)法總結(jié) Fibonacci法是另一種與0618法相類似的分割類方法，兩者的主要區(qū)別在于Fibonacci法搜索區(qū)間的縮短比率不是采用黃金分割數(shù)，而是采用FJbonacci數(shù)列。在使用

20、Fibonacci法時(shí)，通常是由用戶給定最終區(qū)間長度的上限，從而確定探索點(diǎn)的個(gè)數(shù)，逐步進(jìn)行搜索。通過對(duì)Fibonacci數(shù)列進(jìn)行分析表明，在迭代次數(shù)以 的情形，F(xiàn)bonacci法與0.618法的區(qū)間縮短率相同，因而Fibonacci法的收斂速度也是線性的，收斂比也是黃金分割數(shù)。可以證明，F(xiàn)ibonacci法是分割方法求解一維極小化問題的晟優(yōu)策略，而O.618法只是近似雖優(yōu)的，但因0618法不必預(yù)先知道探索點(diǎn)的個(gè)數(shù)，程序?qū)崿F(xiàn)更加容易，因而應(yīng)用也更加廣泛。割線法用割線逼近目標(biāo)函數(shù)導(dǎo)數(shù)曲線 ，把割線的零點(diǎn)作為目標(biāo)函數(shù)駐點(diǎn)的估計(jì)。)(kxfy迭代公式為 )()()(111kkkkkkkxfxfxfxx

21、xx設(shè) 存在連續(xù)三階導(dǎo)數(shù)，滿足 且 ，若 充分接近 ，則割線法產(chǎn)生的序列 收斂于 。)(xfx0)( xf0)( xf21,xxx kxx關(guān)于割線法的收斂性，有下面的結(jié)論， 割線法總結(jié)割線法總結(jié) 割線法與分割法類似，也是通過取試探點(diǎn)和進(jìn)行函數(shù)值比較，使包含所求點(diǎn)的搜索區(qū)間縮小，但試探點(diǎn)的取法與分割法不同，它是選取連接兩個(gè)端點(diǎn)的線段與橫軸的交點(diǎn)作為試探點(diǎn)。割線法不能保證每次都使搜索區(qū)間縮小一定的比例，因而不具有全局線性收斂性，但是它卻利用了函數(shù)的一些性質(zhì)。在函數(shù)接近線性時(shí)，它是非?？斓摹Ｈ绻瘮?shù)本身是線性函數(shù)時(shí)，它可以一步找到解。352.2.一維搜索的插值方法一維搜索的插值方法 假定要在某一區(qū)間

22、內(nèi)尋找函數(shù)的極小點(diǎn)的位置，雖然沒有函數(shù)表達(dá)式，但能夠給出若干試驗(yàn)點(diǎn)處的函數(shù)值。 我們可以根據(jù)這些點(diǎn)處的函數(shù)值，利用插值的方法建立函數(shù)的近似表達(dá)式，進(jìn)而求處函數(shù)的極小點(diǎn)，作為原來函數(shù)的極小點(diǎn)的近似值。這種方法稱作插值法，也稱函數(shù)逼近法。牛頓法（切線法）牛頓法（切線法） 20000012ffff yf一維搜索函數(shù)，假定一給出極小點(diǎn)的一個(gè)較好的近似點(diǎn)0，因?yàn)橐粋€(gè)連續(xù)可微的函數(shù)在極小點(diǎn)附近與一個(gè)二次函數(shù)很接近，因此，在 點(diǎn)附近用一個(gè)二次函數(shù) 逼近。0 3610 求二次函數(shù) 的極小點(diǎn)作為 f極小點(diǎn)的新近似點(diǎn)1即0000ff0100ff依次繼續(xù)下去，可得牛頓法迭代公式：1kkkkff0,1,2,.k 37

23、牛頓法的幾何解釋：38牛頓法的計(jì)算步驟：給定初始點(diǎn) ，控制誤差 ，并令k=0。01）計(jì)算kfkf2）求1kkkkff3)若1kkaa則求得近似解*1kaa，停止計(jì)算，否則作4。4）令1kk轉(zhuǎn)1。39牛頓法總結(jié)牛頓法總結(jié) 優(yōu)點(diǎn)：收斂速度快。 缺點(diǎn)：每一點(diǎn)都要進(jìn)行二階導(dǎo)數(shù)的計(jì)算，工作量大。 要求初始點(diǎn)離極小點(diǎn)不太遠(yuǎn)，否則有可能使極 小化序列發(fā)散或收斂到非極小點(diǎn)。 用數(shù)值為分代替二階導(dǎo)數(shù)時(shí)，舍入誤差會(huì)影響 牛頓的收斂速度，當(dāng)二階導(dǎo)數(shù)很小時(shí)問題更嚴(yán)重。*pxx23p2p1f3x*1xf(x)p(x)xx1p3f2fp二次插值的基本思想是利用目標(biāo)函數(shù)在不同3點(diǎn)的函數(shù)值構(gòu)成一個(gè)與原函數(shù)f(x)相近似的二次

24、多項(xiàng)式p(x)，以函數(shù)p(x)的極值 點(diǎn)(即p(x)=0的根)作為目標(biāo)函數(shù)f(x)的近似極值點(diǎn)。二次插值法二次插值法210112112201222223013233( )()()p xaa xa xfp xaa xa xfp xaa xa xf12( )20p xaa x122axa 222222*2313121232313121231 ()()()2 ()()()pxxfxxfxxfxxxfxx fxxf1. 1. 二次多項(xiàng)式二次多項(xiàng)式p p( (x x) )的構(gòu)成及其極小點(diǎn)的構(gòu)成及其極小點(diǎn)l設(shè)原目標(biāo)函數(shù)的初始單峰區(qū)間為。函數(shù)在x1, x2, x3 3點(diǎn)處函數(shù)值分別為f1, f2, f3，

25、求待定系數(shù)a0, a1和a2, 并代入上式，得：*2pxxl假若f(x)本身為二次函數(shù)，則在理論上按前式一次求值就可找到最優(yōu)點(diǎn) 。l若f(x)為高于二次的函數(shù)或?yàn)槠渌瘮?shù) ,可采用區(qū)間消去法逐步縮小區(qū)間 。l根據(jù)xp* ，x2，f(xp* )和f(x2)的相互關(guān)系，分6種情況進(jìn)行區(qū)間縮小。l在已有的四x1,x2,x3,xp* 中選擇新的三個(gè)點(diǎn)x1,x2,x3，再進(jìn)行二次插值。 l選點(diǎn)要求：lx1x2f2, f2f3 （高低高形態(tài)）l如果 ，以x2,xp* 中函數(shù)值較小的點(diǎn)作為最優(yōu)點(diǎn)x*。二次插值法總結(jié)二次插值法總結(jié) 二次插值法是多項(xiàng)式逼近的一種，所謂多項(xiàng)式逼近，是利用目標(biāo)函數(shù)在若干點(diǎn)的函數(shù)值或

26、導(dǎo)數(shù)值等信息，構(gòu)成一個(gè)與目標(biāo)函數(shù)接近的低次插值多項(xiàng)式，用該多項(xiàng)式的最優(yōu)解作為目標(biāo)函數(shù)的近似最優(yōu)解。三次插值法（Cubic interpolation method） 步驟步驟插值法總結(jié)插值法總結(jié) 插值法是一類重要的一維搜索方法，其基本思想是在搜索區(qū)間內(nèi)不斷用低次強(qiáng)常不超過三次)多項(xiàng)式來逼近目標(biāo)函數(shù)，并用插值多項(xiàng)式的極小點(diǎn)去近似目標(biāo)函數(shù)的極小點(diǎn)。實(shí)踐表明，在目標(biāo)函數(shù)具有較好的解析性質(zhì)時(shí)，插值方法比直接方法(如0618或Fibonacci法)效果更好。462.2.不精確一維搜索不精確一維搜索 所謂不精確一維搜索方法是指應(yīng)用各種可接受的步長選擇律的線性搜索方法。常用的不精確一維搜索算法包括利用簡單準(zhǔn)則的后退方法、經(jīng)典ArmijoGoldstein方法、Wolfe-Powell方法和強(qiáng)Wolfe-Powell方法、以及其后發(fā)展起來的利用Curry-Altman步長律、改進(jìn)的Curry-Altman步長律、Danilin-Pshenichuyi步長律、DeLeone-G-rippo步長律、Backtracking步長律等的各種方法。五五. .一維搜索方