1、第三章 一維搜索方法概述針對不能求微分的函數搜索區間的確定縮小收縮區間確定極小點黃金分割法牛頓法(切線法)插值法2概述對于單個變量，通常稱為一維搜索或線性搜索多維問題轉化為一維問題求解適合于工程實踐3多維和一維間的轉換多維目標函數的極值問題，通常采用數值迭代的方法求解每一步都是從某一定點xk出發，沿著一規定方向dk（使函數值下降的），找出在此方向的極值點xk+1。在迭代計算過程中，當起步點和方向確定之后，就把求多維問題的目標函數的極小值這個多維問題，轉變成求一個變量即步長ak的最優值的一維問題沿著規定方向求ak的最優值以使f(xk+akdk)得到極小值的過程，就是一維搜索或一維最優化問題，而a

2、k則稱為一維搜索的最優化步長多維問題就轉換為一系列的一維搜索問題4第一是初始點的x0選取。x0應盡量選擇靠近極值點，這樣就能較快找到極值點第二是搜索方向的dk確定。從xk出發沿什么方向很快找到f(x)的極小點？以不同的原則選取dk就構成了優化方法中各種不同的方法第三在確定了搜索方向dk后，關鍵的問題是如何進行沿dk方向的一維搜索5一維搜索方法采用數值解法代替解析解法第一步是確定搜索區間，即最優步長ak所在的區間a,b，搜索區間應為單峰區間，區間內目標函數應只有一個極小值第二步是在此區間內求最優步長ak，使目標函數f(xk+ak)達到極小，即通過某種原理不斷縮小搜索區間，從而獲得最優步長a*的數

3、值近似解。6確定初始搜索區間的進退算法前進計算后退計算試探后作前進或后退計算。一）基本思路二) 迭代步驟h=h0y1=f(x1)、x2=x1+h、y2=f(x2)y1y2h=2hx3=x2+h、y3=f(x3)y2y3h0結束給定x1、h0h= -hx3=x1y3=y1x1=x2y1=y2x2=x3y2=y3a=x3、b=x1a=x1、b=x3前進計算后退計算是否否是是否8khx1 y1x2 y2x3 y310.10 90.1 8.203khx1 y1x2 y2x3 y310.10 90.1 8.20320.20.3 6.681khx1 y1x2 y2x3 y310.10 90.1 8.203

4、20.20.3 6.68130.40.1 8.2030.3 6.6810.7 4.429khx1 y1x2 y2x3 y310.10 90.1 8.20320.20.3 6.68130.40.1 8.2030.3 6.6810.7 4.42940.80.3 6.6810.7 4.4291.5 7.1259khx1 y1x2 y2x3 y310.11.8 12.0961.9 14.377khx1 y1x2 y2x3 y310.11.8 12.0961.9 14.3772-0.21.9 14.3771.8 12.0961.6 8.48834khx1 y1x2 y2x3 y310.11.8 12.0

5、961.9 14.3772-0.21.9 14.3771.8 12.0961.6 8.4883-0.41.8 12.0961.6 8.4881.2 4.584khx1 y1x2 y2x3 y310.11.8 12.0961.9 14.3772-0.21.9 14.3771.8 12.0961.6 8.4883-0.41.8 12.0961.6 8.4881.2 4.5844-0.81.6 8.4881.2 4.5840.4 5.99210一維搜索方法的分類為了每次縮短區間，只需要在區間內再插入一點并計算其函數值。然而，對于插入點的位置，是可以用不同的方法來確定的。黃金分割法一類稱作解析法或函數

6、逼近法：構造一個插值函數來逼近原來函數，用插值函數的極小點作為區間的插入點牛頓法、二次插值法等11一維搜索的試探方法黃金分割法是最常用的一維搜索試探方法，又稱作0.618法適用于區間上的任何單谷函數求極小值問題對函數除要求“單谷”外不作其他要求，甚至可以不連續基本思路：在搜索區間內適當插入兩點，并計算其函數值。將區間分成三段。應用函數的單谷性質，通過函數值大小的比較，刪去其中一段，使搜索區間得以縮短。然后再在保留下來的區間上作同樣的處置，如此迭代下去，使搜索區間無限縮小，從而得到極小點的數值近似解。12黃金分割法黃金分割法要求插入點1、2的位置相對于原區間a,b的兩端點具有對稱性，即13黃金分

7、割法的搜索過程給出初始搜索區間a,b及收斂精度，將賦以0.618按前頁中坐標點比例公式計算1和2 ，并計算其對應的函數值f(1)和f(2)。 比較函數值，利用進退法縮短搜索區間檢查區間是否縮短到足夠小和函數值是否收斂到足夠近，如果條件不滿足則返回到步驟如果條件滿足則取最后兩試驗點的平均值作為極小點的數值近似值14黃金分割法程序框圖給定 a, b, 0.618a1=b-(b-a); y1=f(a1);a2=a+(b-a); y2=f(a2);y1y2a=a1; a1=a2;y1=y2;a2=a+(b-a);y2=f(a2)b=a2; a2=a1;y2=y1;a1=b-(b-a);y1=f(a1)

8、a*=(a+b)/2結束是否是否15一維搜索的解析方法假定我們的問題是在某一確定區間內尋求函數的極小點位置，雖然沒有函數表達式，但能夠給出若干試驗點處的函數值。我們可以根據這些點處的函數值，利用插值方法建立函數的某種近似表達式，進而求出函數的極小點，并用它作為原來函數極小點的近似值。這種方法稱作解析法，又稱作函數逼近法。16一維搜索的解析方法多項式是函數逼近的一種常用工具。在搜索區間內我們可以利用若干試驗點處的函數值來構造低次多項式，用它作為函數的近似表達式，并用這個多項式的極小點作為原函數極小點的近似。常用的解析多項式為二次多項式。牛頓法（切線法）：利用一點的函數值、一階導數值和二階導數值來

9、構造此二次函數拋物線法（二次插值法）：它利用三個點的函數值形成一個拋物線來構造此二次函數 17牛頓法對于一維搜索函數，假定已給出極小點的一個較好的近似點a0，因為一個連續可微的函數在極小點附近與一個二次函數很接近，所以可以在a0點附近用一個二次函數來逼近函數，即在點a0將f(a)進行泰勒展開，并保留到二次項，有然后以二次函數的極小點作為極小點的一個新近似點，根據極值必要條件 對a求偏導依此繼續可得牛頓法迭代公式18牛頓法的計算步驟給定初始點a0，控制誤差，令k=0計算f(x)在ak點的一階和二階導數利用牛頓法迭代公式求ak+1若|ak+1-ak|，則求得近似解a*=ak+1，停止計算，否則作第

10、步令k=k+1，然后轉第步19牛頓法最大優點是收斂速度快缺點每一點處都要計算函數的導數和二階導數，因而增加了每次迭代的工作量用數值微分代替二階導數時，舍入誤差會影響牛頓法的收斂速度，當二階導數很小時問題更嚴重牛頓法要求初始點選得比較好，即不能離極小點太遠，否則在可能使極小化序列發散或收斂到非極小點20二次插值法（一）又稱拋物線法。利用y=f(x)在單谷區間中的三點x1x2f(x2)f(x3)，作出如下的二次插值多項式多項式的極值點可以從極值的必要條件求得21P(x)的系數確定與極小點的計算22縮短搜索區間(1)如果搜索區間足夠小，則可用P(x)的極小點x4作為f(x)的極小值x*的近似解(2)

11、否則，必須縮短搜索區間（利用單谷函數的性質）重復進行二次插值法(1)當x2x4時，如果f(x2)f(x4)則取x2,x3。(2)當x2x4時，如果f(x2)f(x4)則取x1, x2。x1x2x3x4x1x2x3x4x1x2x3x4x2x3x4x123計算機流程圖給定x1, x2, x3, 計算f1,f2,f3c1=(f2-f1)/(x3-x1);C2=(f2-f1)/x2-x1)-c1)/(x2-x3)x4=0.5*(x1+x3-c1/c2);f4=f(x4)|(f4-f2)/f2|x*=x4x2x4f2f4x3=x4;f3=f4x1=x2;f1=f2;x2=x4f2=f4f2f4x1=x4

12、;f1=f4x3=x2;f3=f2;x2=x4f2=f4結束是否是是是否否否24解析法與試探法的對比相同之處在于都是利用區間消去法原理將初始搜索區間不斷縮短，從而求得極小點的數值近似解。不同之處在于試驗點位置的確定方法不同。在試探法中試驗點位置是由某種給定的規律確定。在解析法中試驗點位置是按函數值近似分布的極小點確定。試探法僅僅利用了試驗點函數值的大小的比較。而解析法還要利用函數值的本身或者其導數信息。由于試探法僅對試驗點數值的大小進行比較，而函數值本身的特性沒有得到充分利用解析法則是利用函數在已知試驗點的值（或導數值）來確定新試驗點的位置。當函數具有比較好的性質時(例如連續可微性)，解析方法

13、比試探法效果更好。25例題：黃金分割法對函數f(x)x2+2x，給定搜索區間-3x5時，用黃金分割法求極小點x*此時a=-3，b=5，按公式計算兩插入點計算兩插入點的函數值消去區間a2,b，新的搜索區間a,b的端點a=-3不變，而b=a2=1.944依次重復黃金分割法的迭代過程，前五次迭代的結果假定，經過5次迭代后已滿足收斂精度要求，則得精確解為迭代序號aa1a2bf1比較f20-30.0561.94450.1157.6671-3-1.1110.0561.944-0.9870.1152-3-1.832-1.1110.056-0.306-0.9873-1.832-1.111-0.6650.056

14、-0.987-0.8884-1.832-1.386-1.111-0.665-0.851-0.9875-1.386-1.111-0.940-0.665例題：牛頓法給定 ，用牛頓法求其最小點首先求出函數的一階、二階導函數給定起始點a0=3，控制誤差0.001k0123435.166674.334744.039604.00066-52153.3518332.301993.382990.0055124184.33332109.4458686.8699284.047205.166674.334744.039604.000664.00059例題：二次插值法用二次插值法示f(a)=sin(a)在4a5上的最小值此時的搜索區間為4,5迭代兩次的計算過程及結果見下表1a14a24.5a35f1-0.756802f2-0.977590f3-0.968924a4f41a14a24.5a35f1-0.756802f2-0.977590f3-0.968924a44.705120f4-0.9999741