一維搜索方法(與“區(qū)間”有關的文檔共37張)

第三章一維搜索方法第一頁，共37頁。求解一維目標函數(shù)

最優(yōu)解的過程，稱為一維優(yōu)化(一維搜索)，所使用的方法稱為一維優(yōu)化方法。由前數(shù)值迭代法可知，求某目標函數(shù)的最優(yōu)值時，迭代過程每一步的格式都是從某一定點出發(fā)，沿著某一使目標函數(shù)下降的規(guī)定方向搜索，以找出此方向的極小點。這一過程是各種最優(yōu)化方法的一種基本過程。一維搜索方法一般分兩步進行：

■

首先確定一個包含函數(shù)極小點的初始區(qū)間，即確定

函數(shù)的搜索區(qū)間，該區(qū)間必須是單峰區(qū)間；

■然后采用縮小區(qū)間或插值逼近的方法得到最優(yōu)步長，

最終求出該搜索區(qū)間內的一維極小點?！?.1搜索區(qū)間的確定第二頁，共37頁。根據函數(shù)的變化情況，可將區(qū)間分為單峰區(qū)間和多峰區(qū)間。所謂單峰區(qū)間，就是在該區(qū)間內的函數(shù)變化只有一個峰值，即函數(shù)的極小值。

即在單峰區(qū)間內的極小值點X*的左側：函數(shù)呈下降趨勢，而在單峰區(qū)間內的極小值點X*

的右側：函數(shù)呈上升趨勢。也就是說，單峰區(qū)間的函數(shù)值呈“高-低-高”的變化特征?！?.1搜索區(qū)間的確定O

f

(a)

b

x*

x

a

第三頁，共37頁。

目前在一維優(yōu)化搜索中確定單峰區(qū)間常用的方法是進退試算法。

進退試算法的基本思想為：

1)按照一定的規(guī)律給出若干試算點，

2)依次比較各試算點的函數(shù)值的大小，

3)直到找到相鄰三點函數(shù)值按“高-低-高”

變化的單峰區(qū)間為止§3.1搜索區(qū)間的確定第四頁，共37頁。

進退試算法的運算步驟如下：(2)將α0及α0+h代入目標函數(shù)f(x)進行計算并比較大小(1)給定初始點α0和初始步長h§3.1搜索區(qū)間的確定第五頁，共37頁。若，則所計算的相鄰三點

的函數(shù)值已具“高-低-高”特征，這時可確定搜索區(qū)間

(3)若，則表明極小點在試算點

的右側，需做前進試算。

否則，將步長再加倍，并重復上述運算?！?.1搜索區(qū)間的確定在做前進運算時，為加速計算，可將步長h

增加2倍，并取計算新點為α0+h+2h=α0+3h第六頁，共37頁。

(4)若，則表明極小點在試算點

的左側，需做后退試算。在做后退運算時，應將步長變?yōu)?h

，并從

點出發(fā)，得到后退點為

若，則搜索區(qū)間可取為否則，將步長加倍，繼續(xù)后退，重復上述步驟，直到滿足單峰區(qū)間條件為止。§3.1搜索區(qū)間的確定第七頁，共37頁。f(b1)f(a1)f(b1)f(a1)f(b1)af(a1)搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，找到極小點的數(shù)值近似解。假定在搜索區(qū)間內[a,b]任取兩點a1、b1,且a1<b1f1＝f（a1），

f2＝f（b1）一、基本思想a1a1a1b1baabbb1b1§3.2區(qū)間消去法原理f1>f2

f1<f2

f1=f2

f(x)

f(x)

f(x)

第八頁，共37頁。f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1a1b1baababb1b1(1)f1<f2,新區(qū)間為[a,b1];(2)f1>f2,新區(qū)間為[a1,b];(3)如f1=f2,新區(qū)間為[a1,b1]對于上述縮短后的新區(qū)間，可在其內再取一個新點，然后將此點和該區(qū)間內剩下的那一點進行函數(shù)值大小的比較，以再次按照上述方法，進一步縮短區(qū)間，這樣不斷進行下去，直到所保留的區(qū)間縮小到給定的誤差范圍內，而得到近似最優(yōu)解。新區(qū)間為第九頁，共37頁。ab

a2a1

a2a

a1f(a1)f(a2)f(a2)f(a1)b一、適用范圍

適用于[a,b]區(qū)間上的任何單谷函數(shù)求極小值問題。對函數(shù)除要求“單谷”外不作其他要求，甚至可以不連續(xù)。適應面相當廣。基本原理為區(qū)間消去法§3.3分割法分割法插入兩點：第十頁，共37頁。分割法還要求在保留下來的區(qū)間內再插入一點所形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布?！?.3分割法第十一頁，共37頁。分割法程序框圖開始輸入a,

b,

,

YNYN結束第十二頁，共37頁。例3-1用分割法求函數(shù)f(x)=3x3-4x+2的極小點，

初始點x0=0,步長h=1,精度。解：1）確定初始區(qū)間

x1=x0=0,f1=f(x1)=2

x2=x0+h=0+1=1

f2=f(x2)=1

由于f1>f2,應繼續(xù)向前探測

x3=

x0+2h=0+2=2

f3=f(x3)=18由于f2<f3,可知初始區(qū)間已經找到，即

[a,b]=[x1,x3]=[0,2]§3.3分割法第十三頁，共37頁。2）用分割法縮小區(qū)間第一次縮小區(qū)間：x1=0+0.382×(2-0)=0.764,f1x2=0+0.618×(2-0)=1.236,f2由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0,1.236]由于b-a＝>0.2,應繼續(xù)縮小區(qū)間§3.3分割法第二次縮小區(qū)間：令x2=x1=0.764,

f2=f1

x1=0+0.382×(1.236-0)=0.472,

f1由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.472,1.236]由于>0.2,應繼續(xù)縮小區(qū)間第十四頁，共37頁。

第三次縮小區(qū)間：令x1=x2=0.764,

f1=f2

x2=0.472+0.618×(1.236-0.472)=0.944,f2由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0.472,0.944]由于>0.2,應繼續(xù)縮小區(qū)間?！?.3分割法

第四次縮小區(qū)間：令x2=x1=0.764,

f2=f1

x1=0.472+0.382×(0.944-0.472)=0.652,f1由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0.472,0.764]由于>0.2,應繼續(xù)縮小區(qū)間。第十五頁，共37頁。第五次縮小區(qū)間：令x2=x1=0.652,

f2=f1

x1=0.472+0.382×(0.764-0.472)=0.584,f1由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.584,0.764]因為b-a=0.764-0.584=,停止迭代。分割法求的的極小點與極小值：x=0.5×(0.584+0.764)=0.674,f(x§3.3分割法求導運算求的極小點與極小值：

x=0.667,f(x第十六頁，共37頁。一、牛頓法§3.4插值方法利用一點的函數(shù)值、一階導數(shù)以及二階導數(shù)構造二次多項式。用構造的二次多項式的極小點作為原函數(shù)極小點的近似。第十七頁，共37頁。一、牛頓法設f(a)為一個連續(xù)可微的函數(shù)，則在點a0附近進行泰勒展開并保留到二次項：用二次函數(shù)φ(a)的極小點a1作為f(a)極小點的一個近似點。根據極值必要條件:§3.4插值方法第十八頁，共37頁。即依此類推可得牛頓迭代公式：一、牛頓法§3.4插值方法第十九頁，共37頁。在a0處用一拋物線φ(a)代替曲線f(a)，相當于用一斜直線φ’(a)代替曲線f’(a)。這樣各個近似點是通過對作f’(a)切線求得與軸的交點找到的，所以，有時，牛頓法又稱作切線法。第二十頁，共37頁。牛頓法程序框圖

開始計算，YN給定初始點，誤差,令k=0計算，結束第二十一頁，共37頁。數(shù)值\k

0

1

2

3

435.1667

4.33474

4.03960

4.00066-52

153.35183

32.30199

3.38299

0.0055124

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給定，試用牛頓法計算其極小點。給定初始點x0=3，ε=0.001，計算公式：函數(shù)的二階導數(shù)：解：函數(shù)的一階導數(shù)：§3.4插值方法第二十二頁，共37頁。

優(yōu)點：1）收斂速度快。

缺點：1）要計算函數(shù)的一階和二階導數(shù)，增加每次迭代的工作量。

2）數(shù)值微分計算函數(shù)二階導數(shù)，舍入誤差將嚴重影響牛頓法的收斂速度，f

’(x)的值越小問題越嚴重。

3）牛頓法要求初始點離極小點不太遠，否則可能使極小化序列發(fā)散或收斂到非極小點。一、牛頓法§3.4插值方法第二十三頁，共37頁。二、二次插值法（拋物線法）a1af(a)2a3a1ff23fa*

在給定的單峰區(qū)間中，利用目標函數(shù)上的三個點來構造一個二次插值函數(shù)，以近似地表達原目標函數(shù)，并求這個插值函數(shù)的極小點近似作為原目標函數(shù)的極小點。

ap§3.4插值方法第二十四頁，共37頁。y0aap1a1a2apa3ay0a*y1y2ypy3a1a2apa*y1y2ypyp1第二十五頁，共37頁。apap1a1a2apa3ay0a*y1y2ypy3a2a3ay0a*y2ypy3yp1第二十六頁，共37頁。構造的二次插值函數(shù)曲線通過原函數(shù)上的三個點:

解得系數(shù)可求得二、二次插值法（拋物線法）§3.4插值方法第二十七頁，共37頁。二次插值法程序框圖開始計算，YN給定,縮短區(qū)間名稱置換結束第二十八頁，共37頁。a1a2apa3ay0a*y1y2ypy3a1a2apa3a0a*yy1y2ypy3第二十九頁，共37頁。二次插值法程序編制換名方法(1)1)

a2<ap

y2≥yp

y2<yp第三十頁，共37頁。二次插值法程序編制換名方法(2)2)

a2>ap

y2≥yp

y2<yp第三十一頁，共37頁。（1）二次插值法只要求f(x)連續(xù)，不要求其一階可微；（2）收斂速度比分割法快，但可靠性不如分割法好，程序也較長。特點：§3.4插值方