第三章 一維搜索方法

第三章一維搜索方法第1頁，課件共35頁，創(chuàng)作于2023年2月求解一維目標(biāo)函數(shù)

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

■

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

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

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

最終求出該搜索區(qū)間內(nèi)的一維極小點(diǎn)?！?.1搜索區(qū)間的確定第2頁，課件共35頁，創(chuàng)作于2023年2月根據(jù)函數(shù)的變化情況，可將區(qū)間分為單峰區(qū)間和多峰區(qū)間。所謂單峰區(qū)間，就是在該區(qū)間內(nèi)的函數(shù)變化只有一個(gè)峰值，即函數(shù)的極小值。

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

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

f

(a)

b

x*

x

a

第3頁，課件共35頁，創(chuàng)作于2023年2月

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

進(jìn)退試算法的基本思想為：

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

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

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

變化的單峰區(qū)間為止§3.1搜索區(qū)間的確定第4頁，課件共35頁，創(chuàng)作于2023年2月

進(jìn)退試算法的運(yùn)算步驟如下：(2)將α0及α0+h代入目標(biāo)函數(shù)f(x)進(jìn)行計(jì)算并比較大小(1)給定初始點(diǎn)α0和初始步長h§3.1搜索區(qū)間的確定第5頁，課件共35頁，創(chuàng)作于2023年2月若，則所計(jì)算的相鄰三點(diǎn)

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

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

的右側(cè)，需做前進(jìn)試算。

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

增加2倍，并取計(jì)算新點(diǎn)為α0+h+2h=α0+3h第6頁，課件共35頁，創(chuàng)作于2023年2月

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

的左側(cè)，需做后退試算。在做后退運(yùn)算時(shí)，應(yīng)將步長變?yōu)?h

，并從

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

若，則搜索區(qū)間可取為否則，將步長加倍，繼續(xù)后退，重復(fù)上述步驟，直到滿足單峰區(qū)間條件為止?！?.1搜索區(qū)間的確定第7頁，課件共35頁，創(chuàng)作于2023年2月f(b1)f(a1)f(b1)f(a1)f(b1)af(a1)搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，找到極小點(diǎn)的數(shù)值近似解。假定在搜索區(qū)間內(nèi)[a,b]任取兩點(diǎn)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)

第8頁，課件共35頁，創(chuàng)作于2023年2月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ū)間，可在其內(nèi)再取一個(gè)新點(diǎn)，然后將此點(diǎn)和該區(qū)間內(nèi)剩下的那一點(diǎn)進(jìn)行函數(shù)值大小的比較，以再次按照上述方法，進(jìn)一步縮短區(qū)間，這樣不斷進(jìn)行下去，直到所保留的區(qū)間縮小到給定的誤差范圍內(nèi)，而得到近似最優(yōu)解。新區(qū)間為第9頁，課件共35頁，創(chuàng)作于2023年2月ab

a2a1

a2a

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

適用于[a,b]區(qū)間上的任何單谷函數(shù)求極小值問題。對函數(shù)除要求“單谷”外不作其他要求，甚至可以不連續(xù)。適應(yīng)面相當(dāng)廣?；驹頌閰^(qū)間消去法§3.3黃金分割法黃金分割法插入兩點(diǎn)：第10頁，課件共35頁，創(chuàng)作于2023年2月黃金分割法還要求在保留下來的區(qū)間內(nèi)再插入一點(diǎn)所形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布?！?.3黃金分割法第11頁，課件共35頁，創(chuàng)作于2023年2月黃金分割法程序框圖開始輸入a,

b,

,

YNYN結(jié)束第12頁，課件共35頁，創(chuàng)作于2023年2月例3-1用黃金分割法求函數(shù)f(x)=3x3-4x+2的極小點(diǎn)，

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

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

x2=x0+h=0+1=1

f2=f(x2)=1

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

x3=

x0+2h=0+2=2

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

[a,b]=[x1,x3]=[0,2]§3.3黃金分割法第13頁，課件共35頁，創(chuàng)作于2023年2月2）用黃金分割法縮小區(qū)間

第一次縮小區(qū)間：

x1=0+0.382×(2-0)=0.764,f1=0.282x2=0+0.618×(2-0)=1.236,f2=2.72

由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0,1.236]由于b-a＝1.236>0.2,應(yīng)繼續(xù)縮小區(qū)間§3.3黃金分割法第二次縮小區(qū)間：令x2=x1=0.764,

f2=f1=0.282

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

f1=0.317由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.472,1.236]由于b-a=1.236-0.472=0.764>0.2,應(yīng)繼續(xù)縮小區(qū)間第14頁，課件共35頁，創(chuàng)作于2023年2月

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

f1=f2=0.282

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

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

f2=f1=0.282

x1=0.472+0.382×(0.944-0.472)=0.652,f1=0.223由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0.472,0.764]由于b-a=0.764-0.472=0.292>0.2,應(yīng)繼續(xù)縮小區(qū)間。第15頁，課件共35頁，創(chuàng)作于2023年2月第五次縮小區(qū)間：令x2=x1=0.652,

f2=f1=0.223

x1=0.472+0.382×(0.764-0.472)=0.584,f1=0.262由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.584,0.764]因?yàn)閎-a=0.764-0.584=0.18<0.2,停止迭代。黃金分割法求的的極小點(diǎn)與極小值：

x=0.5×(0.584+0.764)=0.674,f(x)=0.222§3.3黃金分割法求導(dǎo)運(yùn)算求的極小點(diǎn)與極小值：

x=0.667,f(x)=0.222第16頁，課件共35頁，創(chuàng)作于2023年2月一、牛頓法§3.4插值方法利用一點(diǎn)的函數(shù)值、一階導(dǎo)數(shù)以及二階導(dǎo)數(shù)構(gòu)造二次多項(xiàng)式。用構(gòu)造的二次多項(xiàng)式的極小點(diǎn)作為原函數(shù)極小點(diǎn)的近似。第17頁，課件共35頁，創(chuàng)作于2023年2月一、牛頓法設(shè)f(a)為一個(gè)連續(xù)可微的函數(shù)，則在點(diǎn)a0附近進(jìn)行泰勒展開并保留到二次項(xiàng)：用二次函數(shù)φ(a)的極小點(diǎn)a1作為f(a)極小點(diǎn)的一個(gè)近似點(diǎn)。根據(jù)極值必要條件:§3.4插值方法第18頁，課件共35頁，創(chuàng)作于2023年2月即依此類推可得牛頓迭代公式：一、牛頓法§3.4插值方法第19頁，課件共35頁，創(chuàng)作于2023年2月在a0處用一拋物線φ(a)代替曲線f(a)，相當(dāng)于用一斜直線φ’(a)代替曲線f’(a)。這樣各個(gè)近似點(diǎn)是通過對作f’(a)切線求得與軸的交點(diǎn)找到的，所以，有時(shí)，牛頓法又稱作切線法。第20頁，課件共35頁，創(chuàng)作于2023年2月牛頓法程序框圖

開始計(jì)算，YN給定初始點(diǎn)，誤差,令k=0計(jì)算，結(jié)束第21頁，課件共35頁，創(chuàng)作于2023年2月數(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給定，試用牛頓法計(jì)算其極小點(diǎn)。給定初始點(diǎn)x0=3，ε=0.001，計(jì)算公式：函數(shù)的二階導(dǎo)數(shù)：解：函數(shù)的一階導(dǎo)數(shù)：§3.4插值方法第22頁，課件共35頁，創(chuàng)作于2023年2月

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

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

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

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

3）牛頓法要求初始點(diǎn)離極小點(diǎn)不太遠(yuǎn)，否則可能使極小化序列發(fā)散或收斂到非極小點(diǎn)。一、牛頓法§3.4插值方法第23頁，課件共35頁，創(chuàng)作于2023年2月二、二次插值法（拋物線法）a1af(a)2a3a1ff23fa*

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

ap§3.4插值方法第24頁，課件共35頁，創(chuàng)作于2023年2月y0aap1a1a2apa3ay0a*y1y2ypy3a1a2apa*y1y2ypyp1第25頁，課件共35頁，創(chuàng)作于2023年2月apap1a1a2apa3ay0a*y1y2ypy3a2a3ay0a*y2ypy3yp1第26頁，課件共35頁，創(chuàng)作于2023年2月構(gòu)造的二次插值函數(shù)曲線通過原函數(shù)上的三個(gè)點(diǎn):

解得系數(shù)可求得二、二次插值法（拋物線法）§3.4插值方法第27頁，課件共35頁，創(chuàng)作于2023年2月二次插值法程序框圖開始計(jì)算，YN給定,縮短區(qū)間名稱置換結(jié)束第28頁，課件共35頁，創(chuàng)作于2023年2月a1a2apa3ay0a*y1y2ypy3a1a2apa3a0a*yy1y2ypy3第29頁，課件共35頁，創(chuàng)作于2023年2月二次插值法程序編制換名方法(1)1)

a2<ap

y2≥yp

y2<yp第30頁，課件共35頁，創(chuàng)作于2023年2月二次插值法程序編制換名方法(2)2)

a2>ap

y2≥yp

y2<yp第31頁，課件共35頁，創(chuàng)作于2023年2月（1）二次插值法只要求f(x)連續(xù)，不要求其一階可微；（2）收斂速度比黃金分割法快，但可靠性不如黃金分割

法好，程序也較長