1、第三章 一維搜索方法概述針對(duì)不能求微分的函數(shù)搜索區(qū)間的確定縮小收縮區(qū)間確定極小點(diǎn)黃金分割法牛頓法(切線法)插值法2概述對(duì)于單個(gè)變量，通常稱為一維搜索或線性搜索多維問題轉(zhuǎn)化為一維問題求解適合于工程實(shí)踐3多維和一維間的轉(zhuǎn)換多維目標(biāo)函數(shù)的極值問題，通常采用數(shù)值迭代的方法求解每一步都是從某一定點(diǎn)xk出發(fā)，沿著一規(guī)定方向dk（使函數(shù)值下降的），找出在此方向的極值點(diǎn)xk+1。在迭代計(jì)算過程中，當(dāng)起步點(diǎn)和方向確定之后，就把求多維問題的目標(biāo)函數(shù)的極小值這個(gè)多維問題，轉(zhuǎn)變成求一個(gè)變量即步長(zhǎng)ak的最優(yōu)值的一維問題沿著規(guī)定方向求ak的最優(yōu)值以使f(xk+akdk)得到極小值的過程，就是一維搜索或一維最優(yōu)化問題，而a

2、k則稱為一維搜索的最優(yōu)化步長(zhǎng)多維問題就轉(zhuǎn)換為一系列的一維搜索問題4第一是初始點(diǎn)的x0選取。x0應(yīng)盡量選擇靠近極值點(diǎn)，這樣就能較快找到極值點(diǎn)第二是搜索方向的dk確定。從xk出發(fā)沿什么方向很快找到f(x)的極小點(diǎn)？以不同的原則選取dk就構(gòu)成了優(yōu)化方法中各種不同的方法第三在確定了搜索方向dk后，關(guān)鍵的問題是如何進(jìn)行沿dk方向的一維搜索5一維搜索方法采用數(shù)值解法代替解析解法第一步是確定搜索區(qū)間，即最優(yōu)步長(zhǎng)ak所在的區(qū)間a,b，搜索區(qū)間應(yīng)為單峰區(qū)間，區(qū)間內(nèi)目標(biāo)函數(shù)應(yīng)只有一個(gè)極小值第二步是在此區(qū)間內(nèi)求最優(yōu)步長(zhǎng)ak，使目標(biāo)函數(shù)f(xk+ak)達(dá)到極小，即通過某種原理不斷縮小搜索區(qū)間，從而獲得最優(yōu)步長(zhǎng)a*的數(shù)

3、值近似解。6確定初始搜索區(qū)間的進(jìn)退算法前進(jìn)計(jì)算后退計(jì)算試探后作前進(jìn)或后退計(jì)算。一）基本思路二) 迭代步驟h=h0y1=f(x1)、x2=x1+h、y2=f(x2)y1y2h=2hx3=x2+h、y3=f(x3)y2y3h0結(jié)束給定x1、h0h= -hx3=x1y3=y1x1=x2y1=y2x2=x3y2=y3a=x3、b=x1a=x1、b=x3前進(jìn)計(jì)算后退計(jì)算是否否是是否8khx1 y1x2 y2x3 y310.10 90.1 8.203khx1 y1x2 y2x3 y310.10 90.1 8.20320.20.3 6.681khx1 y1x2 y2x3 y310.10 90.1 8.203

4、20.20.3 6.68130.40.1 8.2030.3 6.6810.7 4.429khx1 y1x2 y2x3 y310.10 90.1 8.20320.20.3 6.68130.40.1 8.2030.3 6.6810.7 4.42940.80.3 6.6810.7 4.4291.5 7.1259khx1 y1x2 y2x3 y310.11.8 12.0961.9 14.377khx1 y1x2 y2x3 y310.11.8 12.0961.9 14.3772-0.21.9 14.3771.8 12.0961.6 8.48834khx1 y1x2 y2x3 y310.11.8 12.0

5、961.9 14.3772-0.21.9 14.3771.8 12.0961.6 8.4883-0.41.8 12.0961.6 8.4881.2 4.584khx1 y1x2 y2x3 y310.11.8 12.0961.9 14.3772-0.21.9 14.3771.8 12.0961.6 8.4883-0.41.8 12.0961.6 8.4881.2 4.5844-0.81.6 8.4881.2 4.5840.4 5.99210一維搜索方法的分類為了每次縮短區(qū)間，只需要在區(qū)間內(nèi)再插入一點(diǎn)并計(jì)算其函數(shù)值。然而，對(duì)于插入點(diǎn)的位置，是可以用不同的方法來確定的。黃金分割法一類稱作解析法或函數(shù)

6、逼近法：構(gòu)造一個(gè)插值函數(shù)來逼近原來函數(shù)，用插值函數(shù)的極小點(diǎn)作為區(qū)間的插入點(diǎn)牛頓法、二次插值法等11一維搜索的試探方法黃金分割法是最常用的一維搜索試探方法，又稱作0.618法適用于區(qū)間上的任何單谷函數(shù)求極小值問題對(duì)函數(shù)除要求“單谷”外不作其他要求，甚至可以不連續(xù)基本思路：在搜索區(qū)間內(nèi)適當(dāng)插入兩點(diǎn)，并計(jì)算其函數(shù)值。將區(qū)間分成三段。應(yīng)用函數(shù)的單谷性質(zhì)，通過函數(shù)值大小的比較，刪去其中一段，使搜索區(qū)間得以縮短。然后再在保留下來的區(qū)間上作同樣的處置，如此迭代下去，使搜索區(qū)間無限縮小，從而得到極小點(diǎn)的數(shù)值近似解。12黃金分割法黃金分割法要求插入點(diǎn)1、2的位置相對(duì)于原區(qū)間a,b的兩端點(diǎn)具有對(duì)稱性，即13黃金分

7、割法的搜索過程給出初始搜索區(qū)間a,b及收斂精度，將賦以0.618按前頁中坐標(biāo)點(diǎn)比例公式計(jì)算1和2 ，并計(jì)算其對(duì)應(yīng)的函數(shù)值f(1)和f(2)。 比較函數(shù)值，利用進(jìn)退法縮短搜索區(qū)間檢查區(qū)間是否縮短到足夠小和函數(shù)值是否收斂到足夠近，如果條件不滿足則返回到步驟如果條件滿足則取最后兩試驗(yàn)點(diǎn)的平均值作為極小點(diǎn)的數(shù)值近似值14黃金分割法程序框圖給定 a, b, 0.618a1=b-(b-a); y1=f(a1);a2=a+(b-a); y2=f(a2);y1y2a=a1; a1=a2;y1=y2;a2=a+(b-a);y2=f(a2)b=a2; a2=a1;y2=y1;a1=b-(b-a);y1=f(a1)

8、a*=(a+b)/2結(jié)束是否是否15一維搜索的解析方法假定我們的問題是在某一確定區(qū)間內(nèi)尋求函數(shù)的極小點(diǎn)位置，雖然沒有函數(shù)表達(dá)式，但能夠給出若干試驗(yàn)點(diǎn)處的函數(shù)值。我們可以根據(jù)這些點(diǎn)處的函數(shù)值，利用插值方法建立函數(shù)的某種近似表達(dá)式，進(jìn)而求出函數(shù)的極小點(diǎn)，并用它作為原來函數(shù)極小點(diǎn)的近似值。這種方法稱作解析法，又稱作函數(shù)逼近法。16一維搜索的解析方法多項(xiàng)式是函數(shù)逼近的一種常用工具。在搜索區(qū)間內(nèi)我們可以利用若干試驗(yàn)點(diǎn)處的函數(shù)值來構(gòu)造低次多項(xiàng)式，用它作為函數(shù)的近似表達(dá)式，并用這個(gè)多項(xiàng)式的極小點(diǎn)作為原函數(shù)極小點(diǎn)的近似。常用的解析多項(xiàng)式為二次多項(xiàng)式。牛頓法（切線法）：利用一點(diǎn)的函數(shù)值、一階導(dǎo)數(shù)值和二階導(dǎo)數(shù)值來

9、構(gòu)造此二次函數(shù)拋物線法（二次插值法）：它利用三個(gè)點(diǎn)的函數(shù)值形成一個(gè)拋物線來構(gòu)造此二次函數(shù) 17牛頓法對(duì)于一維搜索函數(shù)，假定已給出極小點(diǎn)的一個(gè)較好的近似點(diǎn)a0，因?yàn)橐粋€(gè)連續(xù)可微的函數(shù)在極小點(diǎn)附近與一個(gè)二次函數(shù)很接近，所以可以在a0點(diǎn)附近用一個(gè)二次函數(shù)來逼近函數(shù)，即在點(diǎn)a0將f(a)進(jìn)行泰勒展開，并保留到二次項(xiàng)，有然后以二次函數(shù)的極小點(diǎn)作為極小點(diǎn)的一個(gè)新近似點(diǎn)，根據(jù)極值必要條件 對(duì)a求偏導(dǎo)依此繼續(xù)可得牛頓法迭代公式18牛頓法的計(jì)算步驟給定初始點(diǎn)a0，控制誤差，令k=0計(jì)算f(x)在ak點(diǎn)的一階和二階導(dǎo)數(shù)利用牛頓法迭代公式求ak+1若|ak+1-ak|，則求得近似解a*=ak+1，停止計(jì)算，否則作第

10、步令k=k+1，然后轉(zhuǎn)第步19牛頓法最大優(yōu)點(diǎn)是收斂速度快缺點(diǎn)每一點(diǎn)處都要計(jì)算函數(shù)的導(dǎo)數(shù)和二階導(dǎo)數(shù)，因而增加了每次迭代的工作量用數(shù)值微分代替二階導(dǎo)數(shù)時(shí)，舍入誤差會(huì)影響牛頓法的收斂速度，當(dāng)二階導(dǎo)數(shù)很小時(shí)問題更嚴(yán)重牛頓法要求初始點(diǎn)選得比較好，即不能離極小點(diǎn)太遠(yuǎn)，否則在可能使極小化序列發(fā)散或收斂到非極小點(diǎn)20二次插值法（一）又稱拋物線法。利用y=f(x)在單谷區(qū)間中的三點(diǎn)x1x2f(x2)f(x3)，作出如下的二次插值多項(xiàng)式多項(xiàng)式的極值點(diǎn)可以從極值的必要條件求得21P(x)的系數(shù)確定與極小點(diǎn)的計(jì)算22縮短搜索區(qū)間(1)如果搜索區(qū)間足夠小，則可用P(x)的極小點(diǎn)x4作為f(x)的極小值x*的近似解(2)

11、否則，必須縮短搜索區(qū)間（利用單谷函數(shù)的性質(zhì)）重復(fù)進(jìn)行二次插值法(1)當(dāng)x2x4時(shí)，如果f(x2)f(x4)則取x2,x3。(2)當(dāng)x2x4時(shí)，如果f(x2)f(x4)則取x1, x2。x1x2x3x4x1x2x3x4x1x2x3x4x2x3x4x123計(jì)算機(jī)流程圖給定x1, x2, x3, 計(jì)算f1,f2,f3c1=(f2-f1)/(x3-x1);C2=(f2-f1)/x2-x1)-c1)/(x2-x3)x4=0.5*(x1+x3-c1/c2);f4=f(x4)|(f4-f2)/f2|x*=x4x2x4f2f4x3=x4;f3=f4x1=x2;f1=f2;x2=x4f2=f4f2f4x1=x4

12、;f1=f4x3=x2;f3=f2;x2=x4f2=f4結(jié)束是否是是是否否否24解析法與試探法的對(duì)比相同之處在于都是利用區(qū)間消去法原理將初始搜索區(qū)間不斷縮短，從而求得極小點(diǎn)的數(shù)值近似解。不同之處在于試驗(yàn)點(diǎn)位置的確定方法不同。在試探法中試驗(yàn)點(diǎn)位置是由某種給定的規(guī)律確定。在解析法中試驗(yàn)點(diǎn)位置是按函數(shù)值近似分布的極小點(diǎn)確定。試探法僅僅利用了試驗(yàn)點(diǎn)函數(shù)值的大小的比較。而解析法還要利用函數(shù)值的本身或者其導(dǎo)數(shù)信息。由于試探法僅對(duì)試驗(yàn)點(diǎn)數(shù)值的大小進(jìn)行比較，而函數(shù)值本身的特性沒有得到充分利用解析法則是利用函數(shù)在已知試驗(yàn)點(diǎn)的值（或?qū)?shù)值）來確定新試驗(yàn)點(diǎn)的位置。當(dāng)函數(shù)具有比較好的性質(zhì)時(shí)(例如連續(xù)可微性)，解析方法

13、比試探法效果更好。25例題：黃金分割法對(duì)函數(shù)f(x)x2+2x，給定搜索區(qū)間-3x5時(shí)，用黃金分割法求極小點(diǎn)x*此時(shí)a=-3，b=5，按公式計(jì)算兩插入點(diǎn)計(jì)算兩插入點(diǎn)的函數(shù)值消去區(qū)間a2,b，新的搜索區(qū)間a,b的端點(diǎn)a=-3不變，而b=a2=1.944依次重復(fù)黃金分割法的迭代過程，前五次迭代的結(jié)果假定，經(jīng)過5次迭代后已滿足收斂精度要求，則得精確解為迭代序號(hào)aa1a2bf1比較f20-30.0561.94450.1157.6671-3-1.1110.0561.944-0.9870.1152-3-1.832-1.1110.056-0.306-0.9873-1.832-1.111-0.6650.056

14、-0.987-0.8884-1.832-1.386-1.111-0.665-0.851-0.9875-1.386-1.111-0.940-0.665例題：牛頓法給定 ，用牛頓法求其最小點(diǎn)首先求出函數(shù)的一階、二階導(dǎo)函數(shù)給定起始點(diǎn)a0=3，控制誤差0.001k0123435.166674.334744.039604.00066-52153.3518332.301993.382990.0055124184.33332109.4458686.8699284.047205.166674.334744.039604.000664.00059例題：二次插值法用二次插值法示f(a)=sin(a)在4a5上的最小值此時(shí)的搜索區(qū)間為4,5迭代兩次的計(jì)算過程及結(jié)果見下表1a14a24.5a35f1-0.756802f2-0.977590f3-0.968924a4f41a14a24.5a35f1-0.756802f2-0.977590f3-0.968924a44.705120f4-0.9999741