第二章一維搜索法

第二章一維搜索法概述確定初始單谷區(qū)間的進(jìn)退法一維搜索法分類區(qū)間消去法函數(shù)逼近法概述求一元函數(shù)F(x)的極小點(diǎn)和極小值問題就是一維最優(yōu)化問題。求解一維優(yōu)化問題的方法稱為一維優(yōu)化方法，又稱一維搜索法。一維搜索法是優(yōu)化問題中最簡單、最基本方法。因?yàn)樗粌H可以解決單變量目標(biāo)函數(shù)的最優(yōu)化問題，而且在求多變量目標(biāo)函數(shù)的最優(yōu)值時(shí)，大多數(shù)方法都要反復(fù)多次地進(jìn)行一維搜索，用到一維優(yōu)化法。一般多維優(yōu)化計(jì)算的迭代的基本格式：從一個(gè)已知點(diǎn) x(k)出發(fā)(x(k)由上次迭代獲得，開始時(shí)就是起始點(diǎn)x(0))，沿某一優(yōu)化方法所規(guī)定的是目標(biāo)函數(shù)值下降的搜索方向 S(k)，選擇一個(gè)步長因子，求得下一個(gè)新迭代點(diǎn)x(k1)，x(k1)x(k)S(k)并且滿足F(xk1)F(xk)，即新點(diǎn)必須能夠使目標(biāo)函數(shù)值有所下降，這個(gè)新點(diǎn)就是下一次迭代的出發(fā)點(diǎn)，如此重復(fù)，直到求出目標(biāo)函數(shù)的最優(yōu)解為止。理想步長k可以通過F()F(x(k)S(k))的極小點(diǎn)獲得minF()，使得目標(biāo)函數(shù)達(dá)到最小minF(x(k)S(k))，這種在第k次迭代中求理想步長k的過程，就是一維搜索過程。大致分為兩個(gè)步驟：確定初始搜索區(qū)域［a,b］，該區(qū)域應(yīng)該包括一維函數(shù)極小點(diǎn)在內(nèi)的單谷區(qū)域；在單谷區(qū)域［a,b］上尋找極小點(diǎn)。尋找極小點(diǎn)k可以采用解析解和數(shù)值解等方法。確定初始單谷區(qū)間的進(jìn)退法單谷區(qū)域的定義：設(shè)函數(shù)F(x)在區(qū)域［X..X2］內(nèi)有定義，且

(i)在區(qū)域［Xi,X2］內(nèi)存在極小值X，既有minF(x)F(x)，X [X!,X2]；(2)對(duì)區(qū)域［xi,X］上任意自變量x，有F(x)F(xx)，x0；對(duì)區(qū)域[x,x2]上任意自變量x，有F(x)F(xx)，X0;則稱［x,,x2］為函數(shù)F(x)的單谷區(qū)域。即在單谷區(qū)域內(nèi)，在極小點(diǎn)x的左邊，函數(shù)嚴(yán)格減小；在極小點(diǎn)x的右邊，函數(shù)嚴(yán)格增大。自動(dòng)確定單谷區(qū)域的進(jìn)退算法：其基本思路：按照一定的規(guī)則試算若干個(gè)點(diǎn)， 比較其函數(shù)值的大小，直到找到函數(shù)值按“高-低-高”變化的單谷區(qū)域，搜索過程如下 ：(1)選擇一個(gè)適當(dāng)?shù)某跏疾介Lh；⑵從任意點(diǎn)X)出發(fā)，以x,x0，x2x,h為兩個(gè)試算點(diǎn)計(jì)算該兩點(diǎn)的函數(shù)值FiF(x,)，F(xiàn)2F(X2)；⑶比較Fi、F2的大小，若FiF2，繼續(xù)向前搜索；若FiF2，做后退運(yùn)算。⑷當(dāng)FiF2，極小點(diǎn)在X2的右方，應(yīng)加大步長作前進(jìn)運(yùn)算， X3X22h，比較F2、F3，若F3F2，形成“高-低-高”變化，極小點(diǎn)在以必］，初始搜索區(qū)間確定。若F3F2，繼續(xù)向前搜索，重復(fù)以上步驟；⑸當(dāng)F］F2，極小點(diǎn)在xi的左方，做后退運(yùn)算，減小步長，x3X!h2，比較F2、F3，若F3F2，形成“高-低-高”變化，極小點(diǎn)在［X3,Xi］，初始搜索區(qū)間確定。若F3F2，繼續(xù)做后退運(yùn)算，或加大步長，直到函數(shù)出現(xiàn)“高 -低-高”變化。迭代開始時(shí)，必須選定起始點(diǎn) x迭代開始時(shí)，必須選定起始點(diǎn) x0和步長h般地，X。 0,步長h任意選定，過小需要多次迭代；過大，可能遺漏單谷區(qū)域。例題：試用進(jìn)退算法確定函數(shù) F(x)x26x9的初始搜索區(qū)間［Xi,X2】。設(shè)初始點(diǎn)Xo0,初始步長hi【解】(i)【解】(i)X!0，hi， x2 X)Fi F(Xi)9，F(xiàn)2F(x2)4；(2)因FiF2，前進(jìn)運(yùn)算：h2，X3X2h3，F(xiàn)3F(X3)0；11)f(ai)f(b1) 則取［aQ］為縮小后的搜索區(qū)域;(3)因F2F3，繼續(xù)推進(jìn):h4,xi1,x23必7,F3Fg)16⑷因F2 F3，故初始搜索區(qū)域形成 兇必］［1,7］。課后習(xí)題1：［試用進(jìn)退算法確定函數(shù)F(x)3x38x9的初始搜索區(qū)間［Xix］。設(shè)初始點(diǎn)x0 1，初始步長h0.05。課后習(xí)題2課后習(xí)題2■式用進(jìn)退算法確定函數(shù)F(x)x44x36x2 16x4的初始搜索區(qū)間［X1,X2］。設(shè)初始點(diǎn)Xo0,初始步長h0.1。一維搜索法分類當(dāng)已確定了初始單谷區(qū)間后，可以一維尋優(yōu)。具體方法有區(qū)間消去法和函數(shù)逼近法。區(qū)間消去法又稱試探法，就是不斷消去不存在最優(yōu)點(diǎn)的區(qū)間，使搜索區(qū)域越來越短，最終尋得最優(yōu)點(diǎn)。為了在每次迭代中縮短區(qū)間， 需要在區(qū)間內(nèi)插入計(jì)算點(diǎn)，計(jì)算函數(shù)值。插入計(jì)算點(diǎn)方法有斐波納契法、黃金分割法。函數(shù)逼近法又稱插值法或近似法，用多項(xiàng)式代替目標(biāo)函數(shù)，并利用這個(gè)多項(xiàng)式的極小點(diǎn)作為目標(biāo)函數(shù)的近似最優(yōu)點(diǎn)。這個(gè)多項(xiàng)式根據(jù)某點(diǎn)的函數(shù)值、一二階導(dǎo)數(shù)等構(gòu)造出來，有牛頓法(切線法)、二次插值法(拋物線法)等。區(qū)間消去法原理在搜索區(qū)域［a,b］確定后，在該區(qū)間內(nèi)任取兩點(diǎn)a1>b，a1b，并計(jì)算函數(shù)值f(a1)、f(bj。若f(ajf(bj，則?。踑,bj為縮短后的搜索區(qū)間；若 f(ajfg)，則取［anb］為縮短后的搜索區(qū)間。如圖所示：f(b1)f(a1)f(b1)f(a1)a1b1f(b1)f(a1)f(b1)f(a1)a1b1可以歸納為:2)fg) f(bj 則?。塾?，可為縮小后的搜索區(qū)域；實(shí)際計(jì)算中，常用斐波納契法、黃金分割法。例題1利用Fibonacci法，求解min(x22x)，允許誤差 0.2。3x5、 /解：a=-3,b=5,F(x) x22x，首先計(jì)算迭代次數(shù)n,一般Fn1(ba)/ (5 (3))/0.2 40,又因34，F(xiàn)9 55，n=8。初始兩個(gè)搜索點(diǎn)：為 a(F7/F9)(ba)0.054；x2a(F8/F9)(ba)1.945；由于F(xJ F(X2)，保留［-3,1.945］-新區(qū)間，保留點(diǎn)x0.054,增加新點(diǎn)x3ax2x1 1.109，比較F(x1),F(x3) 例題2：利用黃金分割法，求解 min(x22x)。3x5解：a=-3,b=5,插入兩個(gè)新點(diǎn)：x,b(ba)50.6188 0.056;x2x2a(ba)30.6188 1.944；因?yàn)镕(xJ F(X2)，消去［x2,b］,新區(qū)域［-3,1.944］，新一輪迭代:為1.111,x20.056,F(xJF(x2)00000直到前后兩次Fmin2課后習(xí)題3:|試用黃金分割法求函數(shù) F(x)(x3)的最小值，給定初始單谷域［2,4］，迭代精度為 0.04;課后習(xí)題4：試用黃金分割法求函數(shù) F(x)x20x1的最小值，給定初始單谷域［0.2,1］,迭代精度為 0.01；函數(shù)逼近法

利用插值方法建立函數(shù)的近似表達(dá)式，進(jìn)而求出函數(shù)的極小值，并用它作為原來函數(shù)的極小值的近似值，這種方法稱作函數(shù)逼近法，也稱插值方法。多項(xiàng)式是函數(shù)逼近的常用工具，常用的插值多項(xiàng)式為二次多項(xiàng)式，一種是牛頓法(切線法)，另一種是拋物線法(二次插值法)牛頓法(切線法)函數(shù)yf(x)在極小點(diǎn)附近有近似點(diǎn)，在x0附近用二次函數(shù) (x)逼近f(x),f(x)在x0進(jìn)行泰勒展開有:f(x)1f(x)(x) f(Xo)f(Xo)(XX。)-f(xo)(xxo)二次函數(shù)(X)的極小值作為f(x)極小值的新近似點(diǎn)x!。(xj0即:f(Xo)f(Xo)(X!Xo) 0得:Xi Xi Xof(Xo)

f(Xo)依次繼續(xù)，牛頓法的迭代公式:Xk1xXk1xkf(xk)f(xk)例題3:4 3 2f(x)x4x6x16x4，試用牛頓法求其極小點(diǎn)。3 2解：f(x) 4(x3x3x4)f(x