第三章一維優(yōu)化方法

1、 一維搜索方法概述一維搜索方法概述 初始搜索區(qū)間的確定初始搜索區(qū)間的確定 一維搜索的最優(yōu)化方法一維搜索的最優(yōu)化方法1、格點法、格點法2、黃金分割法、黃金分割法3、二次插值法、二次插值法教學要求：教學要求： 1、掌握初始搜索區(qū)間的確定方法、掌握初始搜索區(qū)間的確定方法 2、掌握黃金分割法、掌握黃金分割法 3、掌握二次插值法、掌握二次插值法 在優(yōu)化設計的迭代運算中，在搜索方向在優(yōu)化設計的迭代運算中，在搜索方向s(k)上尋求最優(yōu)步長上尋求最優(yōu)步長 (k) 的方法稱一維搜索法。實的方法稱一維搜索法。實際上一維搜索法就是一元函數(shù)極小化的數(shù)值迭際上一維搜索法就是一元函數(shù)極小化的數(shù)值迭代算法，其求解過程稱為一

2、維搜索。代算法，其求解過程稱為一維搜索。 一維搜索法是非線性優(yōu)化方法的基本算一維搜索法是非線性優(yōu)化方法的基本算法，多元函數(shù)的迭代算法都可以歸結為在一系法，多元函數(shù)的迭代算法都可以歸結為在一系列逐步產(chǎn)生的下降方向上的一維搜索。例如：列逐步產(chǎn)生的下降方向上的一維搜索。例如：下圖所示的二維優(yōu)化的例子。下圖所示的二維優(yōu)化的例子。 注意：二維優(yōu)化問題的一維搜索方向注意：二維優(yōu)化問題的一維搜索方向s(k)是由具體的優(yōu)化方法決定的，迭代公式是由具體的優(yōu)化方法決定的，迭代公式 x(k+1)=x(k)+ (k)s(k) 因此，二維優(yōu)化問題因此，二維優(yōu)化問題min f(x1, x2)就可以表就可以表示為一維優(yōu)化問

3、題示為一維優(yōu)化問題min f( )x2x1o (k)S(k)S(k)x(k+1)x(k)x*F(x(k)F(x(k+1)二維優(yōu)化問題中的一維搜索二維優(yōu)化問題中的一維搜索 在一維搜索時，需要確定一個搜索區(qū)間在一維搜索時，需要確定一個搜索區(qū)間a,b，此區(qū)間必須包含函數(shù)的極小點此區(qū)間必須包含函數(shù)的極小點 x*，因此搜索區(qū)間因此搜索區(qū)間必須是必須是單峰區(qū)間單峰區(qū)間，即該區(qū)間內(nèi)的函數(shù)值呈現(xiàn)，即該區(qū)間內(nèi)的函數(shù)值呈現(xiàn)“高高-低低-高高”的趨勢。如圖所示，通過將搜索的趨勢。如圖所示，通過將搜索區(qū)間區(qū)間a,b逐漸縮小，直至足夠小，就可以得到近似逐漸縮小，直至足夠小，就可以得到近似最優(yōu)點。最優(yōu)點。一、試探搜索極小

4、點位置一、試探搜索極小點位置 設函數(shù)為設函數(shù)為 y=f(x) ,給定初始點為給定初始點為x1 ，選定選定的初始步長為的初始步長為h0。 由初始點由初始點x1沿沿x軸正向取軸正向取x2點，點，x2=x1+h0，計算計算x1 、x2的函數(shù)值的函數(shù)值y1 、y2 ，比較，比較y1 、y2 的的大小，則極小點的位置有如圖所示兩種情況大小，則極小點的位置有如圖所示兩種情況 1、若、若y2 y1 ，則極小點位于則極小點位于x1點左方，點左方，應反向后退搜索。應反向后退搜索。二、前進搜索二、前進搜索 令令h h0，并使步長加倍并使步長加倍h2h，取得前取得前進方向的進方向的x3點，點，x3 x2+h=x2+

5、2h0，其函其函數(shù)值數(shù)值y3與與y2比較比較有如下情況：有如下情況： 1、若、若y2 y2y3，則繼續(xù)前進搜索，各點變換則繼續(xù)前進搜索，各點變換如下：如下： x1 x2 ，y1 y2 x2 x3 ，y2 y3然后然后步長加倍，取新點步長加倍，取新點x3，重復上述比較重復上述比較y2與與y3的大小，直至出現(xiàn)的大小，直至出現(xiàn)y1 y2y3時，令時，令a x1，b x3，從而構成搜索區(qū)間從而構成搜索區(qū)間a,b三、后退搜索三、后退搜索 令令h -h0，并將并將x1與與 x2對調(diào)，對調(diào)，使步長加使步長加倍倍h2h，取得取得x3點，點，x3 x2+h，其函數(shù)值其函數(shù)值y3與與y2比較比較有如下情況：有如下

6、情況： 1、若、若y2 y2y3，則繼續(xù)后退搜索，各點變換則繼續(xù)后退搜索，各點變換如下：如下： x1 x2 ，y1 y2 x2 x3 ，y2 y3然后然后步長加倍，取新點步長加倍，取新點x3，重復上述比較重復上述比較y2與與y3的大小，直至出現(xiàn)的大小，直至出現(xiàn)y1 y2f(x3)則則新區(qū)間為新區(qū)間為a,x1為保持相同的區(qū)間縮短率，應為保持相同的區(qū)間縮短率，應有（有（1- ）/ = 故：故：1- = 2 2 + -1=0由此可得：由此可得： =0.618黃金分割法可使相鄰兩次搜索區(qū)間都具有相同黃金分割法可使相鄰兩次搜索區(qū)間都具有相同的縮短率的縮短率0.618。x1=a+ 0.382(b-a)x2

7、=a+ 0.618(b-a)二、黃金分割法的搜索過程二、黃金分割法的搜索過程 1、給出初始搜索區(qū)間、給出初始搜索區(qū)間a,b及收斂精度及收斂精度 。 2、按坐標點計算公式計算，并計算相應的函數(shù)值、按坐標點計算公式計算，并計算相應的函數(shù)值 3、縮短搜索區(qū)間、縮短搜索區(qū)間 4、檢查是否滿足收斂條件、檢查是否滿足收斂條件 5、若滿足收斂條件，則取最后兩點的平均值作為、若滿足收斂條件，則取最后兩點的平均值作為極小點的近似解。極小點的近似解。三、黃金分割法的流程圖三、黃金分割法的流程圖四、例題四、例題 一、插值法概念一、插值法概念 假定我們給定的問題是在某一確定區(qū)間假定我們給定的問題是在某一確定區(qū)間內(nèi)尋求

8、函數(shù)的極小點的位置，但是沒有函數(shù)表內(nèi)尋求函數(shù)的極小點的位置，但是沒有函數(shù)表達式，只有若干試驗點處的函數(shù)值。我們可以達式，只有若干試驗點處的函數(shù)值。我們可以根據(jù)這些函數(shù)值，構成一個與原目標函數(shù)相接根據(jù)這些函數(shù)值，構成一個與原目標函數(shù)相接近的低次插值多項式，用該多項式的最優(yōu)解作近的低次插值多項式，用該多項式的最優(yōu)解作為原函數(shù)最優(yōu)解的近似解，這種方法是用低次為原函數(shù)最優(yōu)解的近似解，這種方法是用低次插值多項式逐步逼近原目標函數(shù)的極小點的近插值多項式逐步逼近原目標函數(shù)的極小點的近似求解方法，稱為插值方法或函數(shù)逼近法。似求解方法，稱為插值方法或函數(shù)逼近法。二、插值法與試探法的異同點二、插值法與試探法的異同

9、點 相同點：相同點：都是利用區(qū)間消去法原理將初都是利用區(qū)間消去法原理將初始搜索區(qū)間不斷縮短，從而求得極小點的數(shù)值始搜索區(qū)間不斷縮短，從而求得極小點的數(shù)值近似解。近似解。 不同點：不同點：試驗點位置的確定方法不同。在試探法試驗點位置的確定方法不同。在試探法中試驗點的位置是由某種給定的規(guī)律確定的，并未考中試驗點的位置是由某種給定的規(guī)律確定的，并未考慮函數(shù)值的分布。例如：黃金分割法是按照等比例慮函數(shù)值的分布。例如：黃金分割法是按照等比例0.618縮短率確定的。而在插值法中，試驗點的位置縮短率確定的。而在插值法中，試驗點的位置是按函數(shù)值近似分布的極小點確定的。試探法僅僅利是按函數(shù)值近似分布的極小點確定

10、的。試探法僅僅利用了試驗點函數(shù)值進行大小的比較，而插值法還要利用了試驗點函數(shù)值進行大小的比較，而插值法還要利用函數(shù)值本身或其導數(shù)信息。所以，當函數(shù)具有較好用函數(shù)值本身或其導數(shù)信息。所以，當函數(shù)具有較好的解析性質(zhì)時，插值方法比試探方法效果更好。的解析性質(zhì)時，插值方法比試探方法效果更好。三、二次插值法的概念三、二次插值法的概念 利用原目標函數(shù)上的三個插值點，構成利用原目標函數(shù)上的三個插值點，構成一個二次插值多項式，用該多項式的最優(yōu)解作一個二次插值多項式，用該多項式的最優(yōu)解作為原函數(shù)最優(yōu)解的近似解，逐步逼近原目標函為原函數(shù)最優(yōu)解的近似解，逐步逼近原目標函數(shù)的極小點，稱為二次插值方法或拋物線法。數(shù)的極

11、小點，稱為二次插值方法或拋物線法。四、二次插值函數(shù)的構成四、二次插值函數(shù)的構成 設一維目標函數(shù)的搜索區(qū)間為設一維目標函數(shù)的搜索區(qū)間為a,b，取，取三點三點x1、x2、x3，其中其中x1、x3取區(qū)間的端點，取區(qū)間的端點，即即 x1a ， x3 b 而而x2為區(qū)間內(nèi)的一個點，開始可以取區(qū)為區(qū)間內(nèi)的一個點，開始可以取區(qū)間的中點，即間的中點，即 x2=0.5 ( x1 + x3 ) 計算函數(shù)值計算函數(shù)值f 1=f (x1)、 f 2= f (x2)、 f 3= f (x3) 過函數(shù)曲線上的三點過函數(shù)曲線上的三點P1(x1 , f 1)、 P2(x2 , f 2)、 P3(x3 , f 3) 作作二次插

12、值多項式二次插值多項式 p(x)=Ax2+Bx+C 它應滿足條件它應滿足條件 p(x1)=Ax12+Bx1+C 1=f 1 p(x2)=Ax22+Bx2+C = f 2 p(x3)=Ax32+Bx3+C = f 3 解方程組，得待定系數(shù)解方程組，得待定系數(shù)A、B、C分別分別為為 )()()()()(133221321213132xxxxxxfxxfxxfxxA)()()()()(133221322212212312322xxxxxxfxxfxxfxxB)()()()()(133221321122313113223xxxxxxfxxxxfxxxxfxxxxC 于是函數(shù)于是函數(shù)p(x)就是一個確定

13、的二次多項式，稱二次插就是一個確定的二次多項式，稱二次插值函數(shù)，如圖所示，虛線部分即為二次插值函數(shù)值函數(shù)，如圖所示，虛線部分即為二次插值函數(shù) 令插值函數(shù)令插值函數(shù)p(x)的一介導數(shù)為的一介導數(shù)為0，即，即 p(x)=2ax+b=0 得得p(x)極小點為極小點為 xp* = B / 2 A 代入代入A、B得得 則則 321213132322212212312322*)()()()()()(21fxxfxxfxxfxxfxxfxxxp13131xxffc32112122)/()(xxcxxffc令令)2131(21*ccxxxP注意：注意： 若若c2=0， 則則 即即 說明三個插值點位于同一條直線

14、上，因此說明區(qū)間說明三個插值點位于同一條直線上，因此說明區(qū)間已經(jīng)很小，插值點非常接近，故可將已經(jīng)很小，插值點非常接近，故可將x2、y2輸出作為輸出作為最優(yōu)解。最優(yōu)解。0)/()(32112122xxcxxffc131311212xxffcxxff五、區(qū)間的縮短五、區(qū)間的縮短 為求得滿足收斂精度要求的最優(yōu)點，往往需為求得滿足收斂精度要求的最優(yōu)點，往往需要多次進行插值計算，搜索區(qū)間不斷縮短，使要多次進行插值計算，搜索區(qū)間不斷縮短，使xp*不斷逼近原函數(shù)的極小點不斷逼近原函數(shù)的極小點x*。 第一次區(qū)間縮短的方法是，計算第一次區(qū)間縮短的方法是，計算xp*點的函點的函數(shù)值數(shù)值fp*，比較比較fp*與與f

15、2，取其中較小者所對應的點取其中較小者所對應的點作為新的作為新的x2，以此點的左右兩鄰點作為新的以此點的左右兩鄰點作為新的x1和和x3，得到縮短后的新區(qū)間得到縮短后的新區(qū)間x1，x3，如圖所示。如圖所示。 以后，根據(jù)以后，根據(jù)fp*相對于相對于x2的位置，并比較的位置，并比較fp*與與 f2 ，區(qū)間的縮短可以分為以下四種情況。區(qū)間的縮短可以分為以下四種情況。入口入口xp*x2?f2fP*?f2y1) h=-h0; x3=x1; x1=x2; x2=x3; y3=y1; y1=y2; y2=y3;for(;) h=2*h; x3=x2+h; y3=f(x3); if(y2y3) break; x1=x2; y1=y2;