車輛優(yōu)化設(shè)計(jì)理論與實(shí)踐課件：一維搜索方法 -

車輛優(yōu)化設(shè)計(jì)理論與實(shí)踐一維搜索方法2.1概述2.2搜索區(qū)間的確定和區(qū)間消除法原理2.3黃金分割法2.4一維搜索的插值方法2.1

概述當(dāng)采用數(shù)學(xué)規(guī)劃法尋求多元函數(shù)的極值點(diǎn)時(shí)，一般要進(jìn)行一系列迭代，產(chǎn)生迭代點(diǎn)列，使他們逐漸逼近最優(yōu)點(diǎn)。迭代的一般格式可表示為：其中為第k+1次迭代的搜索方向，為沿搜索的最佳步長(zhǎng)因子。當(dāng)方向給定，求最佳步長(zhǎng)就是求一元函數(shù)的極值問(wèn)題，它稱作一維搜索。而求多元函數(shù)極值點(diǎn)，需要進(jìn)行一系列的一維搜索?？梢?jiàn)一維搜索是優(yōu)化搜索方法的基礎(chǔ)。2.1

概述求解一元函數(shù)的極小點(diǎn)，可采用解析解法，即利用一元函數(shù)的極值條件求。解析解法的缺點(diǎn)是需要進(jìn)行求導(dǎo)計(jì)算。對(duì)于函數(shù)關(guān)系復(fù)雜、求導(dǎo)困難或無(wú)法求導(dǎo)的情況。所以在優(yōu)化設(shè)計(jì)中，求解最佳步長(zhǎng)因子主要采用數(shù)值解法，即利用計(jì)算機(jī)通過(guò)反復(fù)迭代計(jì)算求得最佳步長(zhǎng)因子的近似值。數(shù)值解法的基本思路是：先確定所在的搜索區(qū)間，然后根據(jù)區(qū)間消去法原理不斷縮小此區(qū)間，從而獲得的數(shù)值近似解。2.2搜索區(qū)間的確定與區(qū)間消去法原理2.2.1確定搜索區(qū)間的進(jìn)退法1．算法原理前進(jìn)運(yùn)算后退運(yùn)算確定搜索區(qū)間的外推法的程序框圖如圖

2．算法的MATLAB實(shí)現(xiàn)在MATLAB中編程實(shí)現(xiàn)的進(jìn)退法函數(shù)為：minJT。功用：用進(jìn)退法求解一維函數(shù)的極值區(qū)間。調(diào)用格式：[minx,maxx]=minJT(f,x0,f0,eps0)

其中，f:目標(biāo)函數(shù);x0:初始點(diǎn)；

h0:初始步長(zhǎng)；

eps0:精度；

minx:目標(biāo)函數(shù)包含極值的區(qū)間左端點(diǎn)；

maxx:目標(biāo)函數(shù)包含極值的區(qū)間右端點(diǎn)。3．算法舉例例2-1用進(jìn)退法求函數(shù)的極值區(qū)間。取初始點(diǎn)為0，初始步長(zhǎng)為0.1。2.2.2區(qū)間消去法原理搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，從而找到極小點(diǎn)的數(shù)值近似解。2.2.2區(qū)間消去法原理為了避免多計(jì)算函數(shù)值，我們把第三種情形合并到前面兩種情形中去。例如，可以把前面三種情形改為下列兩種情形：1）若則取[a，b1]

為縮短后的搜索區(qū)間。2）若則取[a1，b]

為縮短后的搜索區(qū)間。2.2.3一維搜索方法的分類可將一維搜索方法分成兩大類。一類稱作試探法。這類方法是按某種給定的規(guī)律來(lái)確定區(qū)間內(nèi)插入點(diǎn)的位置。此點(diǎn)位置的確定僅僅按照區(qū)間縮短如何加快，而不顧及函數(shù)值的分布關(guān)系。屬于試探法一維搜索的有黃金分割法，斐波那契（Fibonacci）法等。另一類一維搜索方法稱作插值法或函數(shù)逼近法。這類方法是根據(jù)某些點(diǎn)處的某些信息，如函數(shù)值、一階導(dǎo)數(shù)、二階導(dǎo)數(shù)等，構(gòu)造一個(gè)插值函數(shù)來(lái)逼近原函數(shù)，用插值函數(shù)的極小點(diǎn)作為區(qū)間的插入點(diǎn)。屬于插值法一維搜索的有二次插值法、三次插值法等。以下我們分別討論這兩類一維搜索方法。2.3黃金分割法黃金分割法適用于[a，b]

區(qū)間上的任何單峰函數(shù)求極小值問(wèn)題。對(duì)函數(shù)除要求“單峰”外不作其他要求，甚至可以不連續(xù)。因此，這種方法的適應(yīng)面相當(dāng)廣。黃金分割法也是建立在區(qū)間消去法原理基礎(chǔ)上的試探方法，即在搜索區(qū)間[a，b]內(nèi)適當(dāng)插入兩點(diǎn)，并計(jì)算其函數(shù)值,將區(qū)間分成三段。應(yīng)用函數(shù)的單谷性質(zhì)，通過(guò)函數(shù)值大小的比較，刪去其中一段，是搜索區(qū)間得以縮短。然后再在保留下來(lái)的區(qū)間上作同樣的處置，如此迭代下去，是搜索區(qū)間無(wú)限縮小，從而得到極小點(diǎn)的數(shù)值近似解。2.3黃金分割法1．算法原理黃金分割法要求插入點(diǎn)的位置相對(duì)于區(qū)間[a，b]兩端點(diǎn)具有對(duì)稱性，即除對(duì)稱要求外，黃金分割法還要求在保留下來(lái)的區(qū)間內(nèi)再插入一點(diǎn)所形成的區(qū)間新三段，與原來(lái)區(qū)間的三段具有相同的比例分布。黃金分割法原理圖為了保持相同的比例分布有:2．算法步驟黃金分割法的搜索過(guò)程是：1）給出初始搜索區(qū)間[a，b]

及收斂精度，將賦以0.618.2）按坐標(biāo)點(diǎn)計(jì)算公式（2-3）計(jì)算兩點(diǎn)，并計(jì)算其對(duì)應(yīng)的函數(shù)值。3）根據(jù)區(qū)間消去法原理縮短搜索區(qū)間。為了能用原來(lái)的坐標(biāo)點(diǎn)計(jì)算公式，需進(jìn)行區(qū)間名稱的代換，并在保留區(qū)間中計(jì)算一個(gè)新的試驗(yàn)點(diǎn)及函數(shù)值。4）檢查區(qū)間是否縮短到足夠小和函數(shù)值收斂到足夠近，如果條件不滿足則返回到步驟2。5）如果條件滿足，則取最后兩試驗(yàn)點(diǎn)的平均值作為極小點(diǎn)的數(shù)值近似解。例2-2試用黃金分割法求函數(shù)極小點(diǎn)，搜索區(qū)間為[-35]時(shí)。迭代序號(hào)aby1比較y20-30.0561.94450.115<7.6671-3-1.1110.564.944-0.987<0.1152-3-1.832-1.1110.056-0.306>-0.9873-1.832-1.111-0.6650.056-0.987<-0.8884-1.832-1.386-1.111-0.665-0.851>-0.9875-1.386-1.111-0.940-0.6653．算法的MATLAB實(shí)現(xiàn)在MATLAB中編程實(shí)現(xiàn)的黃金分割法的函數(shù)為：minHJ。功用：用黃金分割法求解一維函數(shù)的極值。調(diào)用格式：[x,minf]=minHJ(f,a,b,eps)

其中，f:目標(biāo)函數(shù);a:極值的區(qū)間左端點(diǎn)；

b:極值的區(qū)間右端點(diǎn)；

eps:精度；

minf:目標(biāo)函數(shù)的極小值。2.4一維搜索的插值方法假定我們的問(wèn)題是在某一確定區(qū)間內(nèi)尋求函數(shù)的極小點(diǎn)位置，雖然沒(méi)有函數(shù)表達(dá)式，但能夠給出若干試驗(yàn)點(diǎn)處的函數(shù)值。我們可以根據(jù)這些點(diǎn)處的函數(shù)值，利用插值方法建立函數(shù)的某種近似表達(dá)式，進(jìn)而求出函數(shù)的極小點(diǎn)，并用它作為原來(lái)函數(shù)極小點(diǎn)的近似值。這種方法稱作插值方法，又稱作函數(shù)逼近法。2.4一維搜索的插值方法多項(xiàng)式是函數(shù)逼近的一種常用工具。在搜索區(qū)間內(nèi)我們可以利用若干試驗(yàn)點(diǎn)處的函數(shù)值來(lái)構(gòu)造低次多項(xiàng)式，用它作為函數(shù)的近似表達(dá)式，并用這個(gè)多項(xiàng)式的極小點(diǎn)作為原函數(shù)極小點(diǎn)的近似。常用的插值多項(xiàng)式為二次多項(xiàng)式。因此，這里介紹兩種用二次函數(shù)逼近原來(lái)函數(shù)的方法。一種是牛頓法（切線法）。它是利用一點(diǎn)的函數(shù)值、一階導(dǎo)數(shù)值和二階導(dǎo)數(shù)值來(lái)構(gòu)造此二次函數(shù)的。另一種方法是拋物線法（二次插值法）。它是利用三個(gè)點(diǎn)的函數(shù)值形成一個(gè)拋物線來(lái)構(gòu)造此二次函數(shù)的。2.4.1牛頓法1．算法原理對(duì)于一維搜索函數(shù)，假定已給出極小點(diǎn)的一個(gè)較好的近似點(diǎn)，因?yàn)橐粋€(gè)連續(xù)可微的函數(shù)在極小點(diǎn)附近與一個(gè)二次函數(shù)很接近，所以可在點(diǎn)附近用一個(gè)二次函數(shù)來(lái)逼近函數(shù)，2.4.1牛頓法1．算法原理然后以二次函數(shù)的極小點(diǎn)作為極小點(diǎn)的一個(gè)新近似點(diǎn)。根據(jù)極值必要條件2.4.1牛頓法1．算法原理依次繼續(xù)下去，可得牛頓法迭代公式牛頓法的幾何解釋2.4.1牛頓法2．算法步驟給定初始點(diǎn)，控制誤差，并令k=0；1）計(jì)算,；2）求3）若則求得近似解=，停止計(jì)算，否則作4；4）令k=k+1轉(zhuǎn)1）。給定，試用牛頓法求其極小值點(diǎn)。0123435.166674.334744.039604.00066-52153.3518332.301993.382990.0055124184.33332109.4458686.8699284.047205.166674.334744.039604.000664.000593．算法的MATLAB實(shí)現(xiàn)在MATLAB中編程實(shí)現(xiàn)的牛頓法的函數(shù)為：minNewton。功用：用牛頓法求解一維函數(shù)的極值。調(diào)用格式：[x,minf]=minNewton(f,x0,eps)

其中，f:目標(biāo)函數(shù);x0:初始點(diǎn)；

eps:精度；

minf:目標(biāo)函數(shù)的極小值。4．算法實(shí)例例2-5用牛頓法求函數(shù)的極小值，取初始點(diǎn)2。2.4.2二次插值法1．算法原理二次插值法又稱拋物線法。它是利用在單股區(qū)間中的三點(diǎn)的相應(yīng)函數(shù)值，作出如下的二次插值多項(xiàng)式

上面多項(xiàng)式的極值點(diǎn)可從極值的必要條件求得：2.4.2二次插值法利用：求得：=2.4.2二次插值法（a）第一次迭代（b）第二次迭代2．算法的MATLAB實(shí)現(xiàn)在MATLAB中編程實(shí)現(xiàn)的二次插值法的函數(shù)為：minPWX。功用：用二次插值法求解一維函數(shù)的極值。