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

1第1頁，共62頁，2023年，2月20日，星期三第三章一維優(yōu)化方法本章所解決的基本問題是對一維目標函數(shù)F(x)求最優(yōu)點的問題，它雖然是求單變量極值問題，考慮到很多時候函數(shù)的求導比較困難，甚至根本不可導，所以在最優(yōu)化技術中一般不用解析法而是采用直接探索方法求最優(yōu)點，對單變量直接探索稱為一維探索或一維搜索，這種求優(yōu)的方法稱為一維優(yōu)化方法。對于多維的優(yōu)化問題，一般是轉化為一維問題處理，所以一維優(yōu)化方法是用于求解多維優(yōu)化的基礎。第2頁，共62頁，2023年，2月20日，星期三二維優(yōu)化問題中一維搜索對于任意一次迭代計算，總是希望從已知的點x(k)出發(fā)，沿給定的方向s(k)搜索到目標函數(shù)極小值點x(k+1)，即求參數(shù)a的一個最優(yōu)步長因子a(k)，使：F(x(k+1))=minF(x(k)+a(k)

s(k))這種在給定方向上確定最優(yōu)步長的過程，在多維優(yōu)化過程中是多次反復進行的，所以說一維搜索是解多維優(yōu)化問題的基礎。上述極小化問題實際上是以a為變量的一維優(yōu)化問題，表示為：minf(a)第3頁，共62頁，2023年，2月20日，星期三第三章一維優(yōu)化方法Fibonacci法/分數(shù)法格點法黃金分割法***二次插值法***3.1初始搜索區(qū)間的確定***3.2一維搜索的最優(yōu)化方法試探搜索前進搜索后退搜索一維搜索一般分兩步進行。第一步是在s(k)方向上確定函數(shù)值最小點所在區(qū)間，第二步是求出該區(qū)間內(nèi)的最優(yōu)步長因子a(k)第4頁，共62頁，2023年，2月20日，星期三3.1搜索區(qū)間的確定

在一維搜索時，需要確定一個搜索區(qū)間[a，b]，此區(qū)間必須包含函數(shù)的極小點x*，因此搜索區(qū)間必須是單峰區(qū)間，即該區(qū)間內(nèi)的函數(shù)值呈現(xiàn)“高-低-高”的趨勢。如圖所示，通過將搜索區(qū)間[a，b]逐漸縮小，直至足夠小，就可以得到近似最優(yōu)點。第5頁，共62頁，2023年，2月20日，星期三確定初始搜索區(qū)間—進退法對于比較簡單的一維優(yōu)化問題，其搜索區(qū)間可以根據(jù)實際情況確定，但對于多維優(yōu)化問題，在每一次一維搜索之前都用人為方法確定搜索區(qū)間是很困難的。所以必須建立一定的方法，使計算機在優(yōu)化過程中自動地確定。第6頁，共62頁，2023年，2月20日，星期三一、試探搜索1、若y2<y1

，則極小點位于x1點右方，應繼續(xù)前進搜索2、若y2>y1，則極小點位于x1點左方，應反向后退搜索前進搜索后退搜索x1x1x2x2x3x3h02h0h02h0注意：x1x2互換后再取x3y1y3y2y2y3y1設函數(shù)為y=f(x),給定初始點為x1，選定的初始步長為h0。由初始點x1沿

x軸正向取x2點，x2=x1+h0，計算x1,x2的函數(shù)值y1,y2，比較y1,y2的大小，則極小點的位置有如圖所示兩種情況：第7頁，共62頁，2023年，2月20日，星期三一、前進搜索前進搜索x1x2x3h02h0y1y3y2令h

h0，并使步長加倍h2h，取得x3點，x3x2+h=x2+2h0，其函數(shù)值y3與y2比較有如下情況：1、若y2<y3，則有y1>

y2<y3，令：

ax1，bx3，從而構成搜索區(qū)間[a,b]第8頁，共62頁，2023年，2月20日，星期三二、前進搜索然后步長加倍，取新點x3，重復上述比較y2與y3的大小，直至出現(xiàn)y1>y2<y3時，令ax1，bx3，從而構成搜索區(qū)間[a,b]前進搜索x1x2x3h02h0y1y3y22、若y2>y3，則繼續(xù)前進搜索，各點變換如下：

x1x2，y1y2

x2x3，y2y3第9頁，共62頁，2023年，2月20日，星期三三、后退搜索x1x2h02h0注意：x1x2互換后再取x3y2y3y1令h

-h0，并將x1與

x2對調(diào)，使步長加倍h2h，取得x3點，x3x2+h，其函數(shù)值y3與y2比較有如下情況：1、若y2<y3，則有y1>y2<y3，此時函數(shù)f(x)在[x3,x1]必有極小點，故令ax3，bx1，從而構成搜索區(qū)間[a,b]x1x2x3h02h0注意：x1x2互換后再取x3y2y3y1第10頁，共62頁，2023年，2月20日，星期三三、后退搜索然后步長加倍，取新點x3，重復上述比較y2與y3的大小，直至出現(xiàn)y1>y2<y3時，令ax3，bx1，從而構成搜索區(qū)間[a,b]2、若y2>y3，則繼續(xù)后退搜索，各點變換如下：x1x2，y1y2x2x3，y2y3x1x2x3h02h0y1y3y2x1x2x3h02h0y1y3y2第11頁，共62頁，2023年，2月20日，星期三四、進退法確定搜索區(qū)間流程圖第12頁，共62頁，2023年，2月20日，星期三例題例題3.1：試用進退法確定函數(shù)f(x)=x2-6x+9的一維優(yōu)化搜索區(qū)間[a，b]，設初始點x1=0，初始步長h0=1解：計算過程如下:h←h0=1x2←x1+h=1y1=f(x1)=9,y2=f(x2)=4由于y2＜y1，作前進搜索：h←2h=2x3←x2+h=3y3=f(x3)=0比較y2,y3有y2＞y3，再做前進搜索x1←x2=1,y1←y2=4x2←x3=3,y2←y3=0h←2h=4x3←x2+h=7,y3=F(x3)=16第13頁，共62頁，2023年，2月20日，星期三再比較y2，y3有y2＜y3，則取a←x1=1，b←x3=7搜索區(qū)間a，b為[1，7]搜索過程見下圖第14頁，共62頁，2023年，2月20日，星期三3.2一維搜索的最優(yōu)化方法在確定了搜索區(qū)間以后，一維優(yōu)化的任務是采用某種方法將此區(qū)間逐步縮小，在滿足收斂精度或迭代精度的情況下，使其達到包含極小點的一個很小的鄰域，以取得一個近似的最優(yōu)點。

一維優(yōu)化的方法有如下幾種：1.分數(shù)法/Fibonacci法2.格點法3.黃金分割法4.二次插值法第15頁，共62頁，2023年，2月20日，星期三Fibonacci數(shù)列13世紀的意大利數(shù)學家斐波那契(Fibonacci)提出了這樣一個問題：假定一對兔子在它們出生整整兩個月以后可以生一對小兔子，其后每隔一個月又可以再生一對小兔子。假定現(xiàn)在在一個籠子里有一對剛生下來的小兔子，請問一年以后籠子里應該有幾對兔子？第16頁，共62頁，2023年，2月20日，星期三Fibonacci數(shù)列斐波那契(Fibonacci)數(shù)列：0,1,1,2,3,5,8,13…..第17頁，共62頁，2023年，2月20日，星期三Fibonacci數(shù)列的性質(zhì)數(shù)學定義：F0=0；F1=1；Fn=F

n-1+F

n–2，n≥2

數(shù)列{Fn}稱為Fibonacci數(shù)列，F(xiàn)n稱為第n個Fibonacci數(shù)，相鄰兩個Fibonacci數(shù)之比Fn-1/Fn

稱為稱為Fibonacci分數(shù)。第18頁，共62頁，2023年，2月20日，星期三一維搜索算法——試探法原理試探法主要有：斐波那契法（序貫實驗法）；

黃金分割法(0.618法)第19頁，共62頁，2023年，2月20日，星期三試探法原理在區(qū)間[a,b]內(nèi)任取兩點a1和b1，a1<b1，并計算函數(shù)值f(a1)和f(b1)，可能出現(xiàn)兩種情況：

f(a1)<f(b1)，b1一定在t*的右端。xf(x)abb1a1t*a1一定在t的右端可在t的右端也可在t的左端極小點t*必在區(qū)間[a,b1]內(nèi)。第20頁，共62頁，2023年，2月20日，星期三試探法原理

f(a1)≥f(b1)，a1一定在t*的左端。xf(x)abb1b1t*a1一定在t的左端可在t的左端也可在t的右端極小點t*必在區(qū)間[a1,b]內(nèi)第21頁，共62頁，2023年，2月20日，星期三試探法原理只要在區(qū)間[a,b]內(nèi)任取兩個不同點，并算出它們的函數(shù)值加以比較，就可以把搜索區(qū)間所小為

[a1,b]或[a

,b1]，因為縮小后的區(qū)間仍包含極小點要進一步縮小搜索區(qū)間，只需在縮小后的區(qū)間內(nèi)再取一點，并與f(a1)或f(b1)比較函數(shù)值大小。按照上述方法，隨著計算函數(shù)值次數(shù)的增加，區(qū)間變得越來越小，從而越接近極小點。第22頁，共62頁，2023年，2月20日，星期三Fibonacci法算法步驟第二步：k=1，計算最初的兩個搜索點t1和

t2，第一步：選取初始數(shù)據(jù)，確定單峰區(qū)間[a,b],給出搜索精度ε>0，確定搜索次數(shù)n。第23頁，共62頁，2023年，2月20日，星期三Fibonacci法算法步驟斐波那契法尋優(yōu)收斂快，計算次數(shù)少，然而每步取點繁瑣，且各步縮短率不同。為此，引出黃金分割法。

第三步：k=n-1時，t1=t2=(a+b)/2，無法比較，此時取第24頁，共62頁，2023年，2月20日，星期三黃金分割法1)若y1<y2，則極小點必在區(qū)間[a,x2]內(nèi)，令b=x2，新區(qū)間為[a,x2]2)若y1≥y2，則極小點必在區(qū)間[x1,b]內(nèi)，令a=x1，新區(qū)間為[x1,b]黃金分割法適用于[a,b]區(qū)間上的任何單峰函數(shù)求極小值問題。對函數(shù)除要求單峰外不作其它要求，甚至可以不連續(xù)。因此適應面廣一、黃金分割法的原理在搜索區(qū)間[a,b]內(nèi)適當插入兩點

x1,x2，x1<x2,且在區(qū)間內(nèi)對稱位置，計算其函數(shù)值：y1=f(x1)，y2=f(x2)經(jīng)過函數(shù)值比較，區(qū)間縮短一次。新區(qū)間只保留x1，x2中的一個第25頁，共62頁，2023年，2月20日，星期三黃金分割法區(qū)間縮短第26頁，共62頁，2023年，2月20日，星期三黃金分割法區(qū)間縮短第27頁，共62頁，2023年，2月20日，星期三黃金分割法的分點選取原則黃金分割法內(nèi)分點選取的原則：對稱且每次區(qū)間縮短率λ都相等。可證明λ≡0.618設原區(qū)間長度為l。保留區(qū)間長度為1l，區(qū)間縮短率為

1。進行第二次縮短時，新點為x3,設y1>f(x3)，則新區(qū)間為[a,x1]。設區(qū)間縮短率為2。為保持相同的區(qū)間縮短率，應有：證明：由此可得：=0.618。因而黃金分割法又稱0.618法，是一種等比例縮短區(qū)間的直接搜索法第28頁，共62頁，2023年，2月20日，星期三黃金分割法可使相鄰兩次搜索區(qū)間都具有相同的縮短率0.618。因而內(nèi)分點的取點規(guī)則為：

x1=a+0.382(b-a) x2=a+0.618(b-a)終止原則：最優(yōu)解：k為縮短區(qū)間的次數(shù)第29頁，共62頁，2023年，2月20日，星期三黃金分割法的搜索過程1、給出初始搜索區(qū)間[a,b]及收斂精度；2、按坐標點計算公式計算，并計算相應的函數(shù)值；3、縮短搜索區(qū)間；4、檢查是否滿足收斂條件；5、若滿足收斂條件，則取最后兩點的平均值作為極小點的近似解。第30頁，共62頁，2023年，2月20日，星期三黃金分割法的流程圖第31頁，共62頁，2023年，2月20日，星期三例題例題3.3試用黃金分割法求目標函數(shù)f(x)=x2-6x+9的最優(yōu)解。給定初始區(qū)間[1，7]，收斂精度ε=0.4。解：第一次區(qū)間縮短計算過程：計算兩內(nèi)點及對應函數(shù)值：x1=a+0.382(b-a)=3.292y1=f(x1)=0.085264x2=a+0.618(b-a)=4.708y2=f(x2)=2.917264作數(shù)值比較，可見y1<y2,再做置換：用終止準則判斷:a(1)←a=1b(1)←x2=4.708第32頁，共62頁，2023年，2月20日，星期三為第二次區(qū)間縮短做準備，做置換：x2←x1=3.292，y2←y1=0.085264各次縮短區(qū)間的計算數(shù)據(jù)見下頁表。第六次區(qū)間縮短的端點滿足精度要求，終止計算。取最優(yōu)解為第33頁，共62頁，2023年，2月20日，星期三區(qū)間縮短次數(shù)abx1x2y1y2原區(qū)間123456112.4164562.4164562.4164562.7509172.75091774.7084.7083.8326303.2923.2923.0853053.2922.4164563.2922.9574342.7509172.9574342.8786514.7083.2923.8326303.2922.9574343.0853052.9574340.0852640.34052400852640.0018120.0620440.0018120.0147252.9172640.0852640.6932730.0852640.0018120.0072770.001812黃金分割法例題計算數(shù)據(jù)第34頁，共62頁，2023年，2月20日，星期三格點法則最優(yōu)解為：x*xm，y*ym

若不能滿足精度要求，把當前區(qū)間作為初始搜索區(qū)間，重復上述步驟直至滿足精度為止設一維函數(shù)為f(x)，搜索區(qū)間為[a,b]，一維收斂精度為。在區(qū)間[a,b]的內(nèi)部取n個等分點：x1,x2,…,xn。區(qū)間被分為n+1等分，各分點坐標為:對應各點的函數(shù)值為y1,y2,…,yn。比較其大小，取最小者：格點法的原理ym=min{yk

,k=1,2,…,n}則在區(qū)間[xm-1,xm+1]內(nèi)必包含極小點，取[xm-1,xm+1]為縮短后新區(qū)間，若新區(qū)間滿足收斂條件：xm+1-xm-1第35頁，共62頁，2023年，2月20日，星期三格點法的區(qū)間縮短新區(qū)間y1ym-1ymym+1ynx1axm-1xmxm+1xnb第36頁，共62頁，2023年，2月20日，星期三格點法流程圖第37頁，共62頁，2023年，2月20日，星期三例題

例題3.2：用格點法求一維目標函數(shù)f(x)=4x2-12x+10的最優(yōu)解。給定搜索區(qū)間[a，b]為[1，2.2]，迭代精度ε=0.2，內(nèi)分點數(shù)n=4。解：計算區(qū)間端點的函數(shù)值f(a)=2f(b)=2.96由上式確定四個內(nèi)分點的位置，并計算其函數(shù)值，計算結果如表所示。其中最小的函數(shù)值為：對應的點：第38頁，共62頁，2023年，2月20日，星期三區(qū)間縮短次數(shù)xkykxmabb-a第一次1.241.481.721.961.27041.00161.19361.8461.481.241.720.48第二次1.3361.4321.5281.6241.1075841.0184961.0031361.0615041.5281.4321.6240.192第39頁，共62頁，2023年，2月20日，星期三新區(qū)間的端點為：新區(qū)間的長度為：，不滿足精度要求。再做第二次區(qū)間縮短后，得到區(qū)間端點為：新區(qū)間長度，滿足迭代精度。最優(yōu)解為：

第40頁，共62頁，2023年，2月20日，星期三二次插值法假定我們給定的問題是在某一確定區(qū)間內(nèi)尋求函數(shù)的極小點的位置，但是沒有函數(shù)表達式，只有若干試驗點處的函數(shù)值。我們可以根據(jù)這些函數(shù)值，構成一個與原目標函數(shù)相接近的低次插值多項式，用該多項式的最優(yōu)解作為原函數(shù)最優(yōu)解的近似解，這種方法是用低次插值多項式逐步逼近原目標函數(shù)的極小點的近似求解方法，稱為插值方法或函數(shù)逼近法。一、插值法概念第41頁，共62頁，2023年，2月20日，星期三插值法與試探法的異同點相同點：都是利用區(qū)間消去法原理將初始搜索區(qū)間不斷縮短，從而求得極小點的數(shù)值近似解。不同點：試驗點位置的確定方法不同試探法中試驗點的位置是由某種給定的規(guī)律確定的，并未考慮函數(shù)值的分布。例如：黃金分割法是按照等比例0.618縮短率確定的。插值法試驗點的位置是按函數(shù)值近似分布的極小點確定的。第42頁，共62頁，2023年，2月20日，星期三插值法與試探法的異同點試探法僅僅利用了試驗點函數(shù)值進行大小的比較，而插值法還要利用函數(shù)值本身或其導數(shù)信息。所以，當函數(shù)具有較好的解析性質(zhì)時，插值方法比試探方法效果更好。第43頁，共62頁，2023年，2月20日，星期三二次插值法利用原目標函數(shù)上的三個插值點，構成一個二次插值多項式，用該多項式的最優(yōu)解作為原函數(shù)最優(yōu)解的近似解，逐步逼近原目標函數(shù)的極小點，稱為二次插值方法或近似拋物線法。x*第44頁，共62頁，2023年，2月20日，星期三二次插值函數(shù)的構成設一維目標函數(shù)的搜索區(qū)間為[a,b]第一步：取三點x1,x2,x3，x1←a，x3←b，x2=0.5(x1+x3)第二步：計算三點函數(shù)值：f1=f(x1)，f2=f(x2)，f3=f(x3)第三步：過三點做一條二次曲線：p(x)=Ax2+Bx+C，則應滿足：p(x1)=Ax12+Bx1+C=f1

p(x2)=Ax22+Bx2+C=f2

p(x3)=Ax32+Bx3+C=f3解線性方程組得：第45頁，共62頁，2023年，2月20日，星期三于是函數(shù)p(x)就是一個確定的二次多項式，稱二次插值函數(shù)

如圖所示，虛線部分即為二次插值函數(shù)第46頁，共62頁，2023年，2月20日，星期三二次插值函數(shù)的構成第四步：計算二次曲線：p(x)=Ax2+Bx+C的極小值xp*=B/2A，帶入A，B令其一階導數(shù)為零，即：p’(x)=2Ax+B=0，得：令得第47頁，共62頁，2023年，2月20日，星期三二次插值函數(shù)的構成注意：

若c2=0，則

即說明三個插值點位于同一條直線上，因此說明區(qū)間已經(jīng)很小，插值點非常接近，故可將x2、f2輸出作為最優(yōu)解。第48頁，共62頁，2023年，2月20日，星期三二次插值法區(qū)間的縮短第一次區(qū)間縮短的方法是，計算xp*

點的函數(shù)值fp*，比較fp*

與

f2，取其中較小者所對應的點作為新的x2，以此點的左右兩鄰點作為新的x1和x3，得到縮短后的新區(qū)間[x1，x3]，如圖所示。新區(qū)間x1=ax2x3=bx*xP*x1x2x3為求得滿足收斂精度要求的最優(yōu)點，往往需要多次進行插值計算，搜索區(qū)間不斷縮短，使xp*不斷逼近原函數(shù)的極小點x*第49頁，共62頁，2023年，2月20日，星期三根據(jù)fp*相對于x2的位置，并比較fp*與f2，區(qū)間的縮短可以分為以下：x1x2x3xP*f2fp*x1x1x1x2x2x2xP*xP*xP*x3x3x3f2f2f2fP*fP*fP*bacd第50頁，共62頁，2023年，2月20日，星期三二次插值法區(qū)間縮短框圖入口xp*>x2?f2>fP*?f2<fP*?x1xp*f1

fP*x3x2f3

f2x2xp*f2

fP*x1x2f1

f2x2xp*f2

fP*x3xp*f3

fP*出口YYYNNNabcd第51頁，共62頁，2023年，2月20日，星期三終止準則及最優(yōu)解x*xp*(k)

f*

f(x*)最優(yōu)解：終止準則：第52頁，共62頁，2023年，2月20日，星期三二次插值算法的流程圖說明三點在一直線上說明xp*落在區(qū)間[x1,x3]外第53頁，共62頁，2023年，2月20日，星期三例題3.4例題3.4

試用二次插值法求函數(shù)f(x)=(x-3)2的最優(yōu)解，初始區(qū)間為[1，7]，精度ε=0.01解：(1)初始插值節(jié)點x1=a=1,f1=f(x1)=4x2=0.5(a+b)=4,f2=f(x2)=1x3=b=7,f3=f(x3)=16(2)計算插值函數(shù)的極小點與極小值第54頁，共62頁，2023年，2月20日，星期三例題3.4(3)縮短區(qū)間因有，故有x1=1,f1=4x2←xp*(1)=3,f2=0x3←x2=4,f3=1(4)重復步驟(2)c1=-1c2=1(5)檢查終止條件獲得最優(yōu)解xp*(2)=3fp*(2)=0第55頁，共62頁，2023年，2月20日，星期三例題3.5例題3.5用二次差值法求非二次函數(shù)的最優(yōu)解。初始區(qū)間端點為a=-0.5,b=2.5。精度要求ε=0.005(1)初始插值節(jié)點x1=a=-0.5,f1=f(x1)=-0.851279x2=0.5(a+b)=1f2=f(x2)=-2.610944x3=b=2.5,f3=f(x3)=15.615452(2)計算與

c1=5.488910,c2=4.441347解：第56頁，共62頁，2023年，2月20日，星期三例題3.5(3)縮短區(qū)間因有，故取x1=-0.5,f1=-0.851279x2=0.382067,f2=-20927209x3=1,f3=-2.610944(4)對新區(qū)間重復步驟二c1=-1.17311,c2=1.910196(5)檢查終止條件未滿足終止條件，返回步驟（3）第57頁，共62頁，2023年，