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

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

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

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

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

其中，f:目標函數(shù);x0:初始點；

h0:初始步長；

eps0:精度；

minx:目標函數(shù)包含極值的區(qū)間左端點；

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

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

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

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

及收斂精度，將賦以0.618.2）按坐標點計算公式（2-3）計算兩點，并計算其對應的函數(shù)值。3）根據(jù)區(qū)間消去法原理縮短搜索區(qū)間。為了能用原來的坐標點計算公式，需進行區(qū)間名稱的代換，并在保留區(qū)間中計算一個新的試驗點及函數(shù)值。4）檢查區(qū)間是否縮短到足夠小和函數(shù)值收斂到足夠近，如果條件不滿足則返回到步驟2。5）如果條件滿足，則取最后兩試驗點的平均值作為極小點的數(shù)值近似解。例2-2試用黃金分割法求函數(shù)極小點，搜索區(qū)間為[-35]時。迭代序號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實現(xiàn)在MATLAB中編程實現(xiàn)的黃金分割法的函數(shù)為：minHJ。功用：用黃金分割法求解一維函數(shù)的極值。調(diào)用格式：[x,minf]=minHJ(f,a,b,eps)

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

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

eps:精度；

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

其中，f:目標函數(shù);x0:初始點；

eps:精度；

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

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