第三章 一維搜索(線性搜索)

第三章一維搜索方法3.1概述3.2確定初始區(qū)間3.3縮小區(qū)間3.4黃金分割法〔0.618法〕3.5一維搜索的插值方法編輯課件第3章一維搜索方法3.1概述3.1.1一維問題是多維問題的根底求目標(biāo)函數(shù)f(X)的極小點(diǎn)，從理論上說需要求解方程：其中那么如何來求f(X)的極小點(diǎn)呢？根本思想:這種方法是逐次迭代的方法，在電子計(jì)算機(jī)上很容易實(shí)現(xiàn)，因此它在優(yōu)化設(shè)計(jì)中被廣泛地采用。2編輯課件這個(gè)過程稱為一維搜索過程。如：則當(dāng)Sk方向上的任何一點(diǎn)可以表示為其中α是步長因子，為實(shí)系數(shù)，此時(shí)Sk方向上任何一點(diǎn)的目標(biāo)函數(shù)值為，它是參數(shù)α的一元函數(shù)。那么在沿Sk方向求的極小點(diǎn)，這就是求一元函數(shù)

的極小問題，它可表示為：3編輯課件一維搜索示意圖編輯課件求多元函數(shù)極值點(diǎn)，需要進(jìn)行一系列的一維搜索?？梢娨痪S搜索是優(yōu)化搜索方法的根底。求解一元函數(shù)的極小點(diǎn)，可采用解析解法，即利用一元函數(shù)的極值條件求在用函數(shù)的導(dǎo)數(shù)求時(shí)，所用的函數(shù)是僅以步長因子為變量的一元函數(shù)，而不是以設(shè)計(jì)點(diǎn)x為變量的多元函數(shù)。3.1.2的確定方法為了直接利用的函數(shù)式求解最正確步長因子。把或它的簡寫形式進(jìn)行泰勒展開，取到二階項(xiàng)，即將上式對(duì)進(jìn)行微分并令其等于零，給出極值點(diǎn)應(yīng)滿足的條件從而求得編輯課件這里是直接利用函數(shù)而不需要把它化成步長因子。的函數(shù)。不過，此時(shí)需要計(jì)算點(diǎn)處梯度和海賽矩陣H。解析解法的缺點(diǎn)——需要進(jìn)行求導(dǎo)計(jì)算。對(duì)于函數(shù)關(guān)系復(fù)雜、求導(dǎo)困難或無法求導(dǎo)的情況，使用解析法將是非常不便的。因此，在優(yōu)化設(shè)計(jì)中，求解最正確步長因子主要采用數(shù)值解法，利用計(jì)算機(jī)通過反復(fù)迭代計(jì)算求得最正確步長因子的近似值。數(shù)值解法的根本思路是：首先確定所在的搜索區(qū)間，然后根據(jù)區(qū)間消去法原理不斷縮小此區(qū)間，從而獲得的數(shù)值近似解。編輯課件解析法:①f(X(k)+αS(k))沿S(k)

方向在x(k)

點(diǎn)泰勒展開；②取二次近似：

對(duì)α求導(dǎo)，令其為零。

④求得最優(yōu)步長編輯課件數(shù)值解法根本思路：解析解法對(duì)于函數(shù)關(guān)系復(fù)雜、求導(dǎo)困難等情況難以實(shí)現(xiàn)。在實(shí)際優(yōu)化設(shè)計(jì)中，數(shù)值解法的應(yīng)用更為有效，且適合計(jì)算機(jī)的運(yùn)算特點(diǎn)。

一維搜索也稱直線搜索。這種方法不僅對(duì)于解決一維最優(yōu)化問題具有實(shí)際意義，而且也是求解多維最優(yōu)化問題的重要支柱。一維搜索一般分為兩大步驟：(1)確定初始搜索區(qū)間[a，b]，該區(qū)間應(yīng)是包括一維函數(shù)極小點(diǎn)在內(nèi)的單谷區(qū)間。(2)在單谷區(qū)間[a,b]內(nèi)通過縮小區(qū)間尋找極小點(diǎn)。先確定在的搜索區(qū)間，然后根據(jù)區(qū)間消去法原理不斷縮小此區(qū)間所，從而獲得的數(shù)值近似解。編輯課件1、確定搜索區(qū)間的外推法在給定區(qū)間內(nèi)僅有一個(gè)谷值〔或有唯一的極小點(diǎn)〕的函數(shù)稱為單谷函數(shù)，其區(qū)間稱為單谷區(qū)間。函數(shù)值：“大—小—大〞圖形：“高—低—高〞單谷區(qū)間中一定能求得一個(gè)極小點(diǎn)。3.2確定初始區(qū)間編輯課件從開始，以初始步長向前試探。如果函數(shù)值上升，那么步長變號(hào)，即改變?cè)囂椒较?。如果函?shù)值下降，那么維持原來的試探方向，并將步長加倍。區(qū)間的始點(diǎn)、中間點(diǎn)依次沿試探方向移動(dòng)一步。此過程一直進(jìn)行到函數(shù)值再次上升時(shí)為止，即可找到搜索區(qū)間的終點(diǎn)。最后得到的三點(diǎn)即為搜索區(qū)間的始點(diǎn)、中間三點(diǎn)和終點(diǎn)，形成函數(shù)值的“高－低－高〞趨勢。單谷區(qū)間編輯課件f(x)0α1α3α0f(x)α3α1說明：單谷區(qū)間內(nèi)，函數(shù)可以有不可微點(diǎn)，也可以是不連續(xù)函數(shù)；編輯課件外推方法基本思想：對(duì)任選一個(gè)初始點(diǎn)及初始步長，通過比較這兩點(diǎn)函數(shù)值的大小，確定第三點(diǎn)位置，比較這三點(diǎn)的函數(shù)值大小，確定是否為“高—低—高”形態(tài)。步驟：1〕選定初始點(diǎn)a1，初始步長h=h0，計(jì)算y1=f(a1)和y2=f(a1+h)2〕比較y1和y2；a〕如果y1>y2，向右前進(jìn)，加大步長h=2h0，轉(zhuǎn)〔3〕向前；b〕如果y1<y2，向左后退，h=-2h0，將a1和a2,y1和y2的值互換。轉(zhuǎn)〔3〕向后探測；c〕如果y1=y2，極小點(diǎn)在a1和a1+h之間。3〕產(chǎn)生新的探測點(diǎn)a3=a2+h，y3=f(a3)；編輯課件4〕比較函數(shù)值y2和y3：a〕如果y2>y3，加大步長h=2h，a1=a2,a2=a3,轉(zhuǎn)〔3〕繼續(xù)探測；b〕如果y2<y3，那么初始區(qū)間得到：a=min[a1,a3],b=max[a1,a3]，函數(shù)最小值所在區(qū)間為[a,b]。編輯課件右圖表示沿的正向試探。每走一步都將區(qū)間的始點(diǎn)、中間點(diǎn)沿試探方向移動(dòng)一步〔進(jìn)行換名〕。經(jīng)過三步最后確定搜索間，并且得到區(qū)間始點(diǎn)、中間點(diǎn)和終點(diǎn)所對(duì)應(yīng)的函數(shù)值。y1y3→y2y2→y1a3→a2a2→a1a1Oaa3h0h02h0圖3-2正向搜索的外推法右圖所表示的情況是：開始是沿的正方向試探，但由于函數(shù)值上升而改變了試探方向，最后得到始點(diǎn)，中間點(diǎn)和終點(diǎn)

及它們的對(duì)應(yīng)函數(shù)值

從而形成單谷區(qū)間為一維搜索區(qū)間。y1←y2a2←a3a1←a2←a1Oaa32h0h0h0y3y1←y2←y1y2←y3a1←a2圖3-3反向搜索的外推法編輯課件khx1x2x30h0初始點(diǎn)初始點(diǎn)+h012h0初始點(diǎn)初始點(diǎn)+h0初始點(diǎn)+3h024h0初始點(diǎn)+h0初始點(diǎn)+3h0初始點(diǎn)+7h038h0初始點(diǎn)+3h0初始點(diǎn)+7h0初始點(diǎn)+15h0前進(jìn)搜索步驟表編輯課件khx1x2x30h0初始點(diǎn)初始點(diǎn)+h012h0初始點(diǎn)+h0初始點(diǎn)初始點(diǎn)-2h024h0初始點(diǎn)初始點(diǎn)-2h0初始點(diǎn)-6h038h0初始點(diǎn)-2h0初始點(diǎn)-6h0初始點(diǎn)-14h0后退搜索步驟表khx1y1x2y2x3y310.10.2090.18.2030.36.68120.40.18.2030.36.6810.74.42930.80.36.6810.74.4291.57.125解：19編輯課件khx1y1x2y2x3y310.1-0.21.812.0961.914.3771.914.3771.812.0961.68.4882-0.41.812.0961.68.4881.24.5843-0.81.68.4881.24.5840.45.992

運(yùn)用進(jìn)退法確定出初始搜索區(qū)間[a,b]后，便可采用一維優(yōu)化方法來求出函數(shù)f(x)在區(qū)間內(nèi)的最優(yōu)點(diǎn)x*。20編輯課件2.程序框圖h=h0y1=f(x1)、x2=x1+h、y2=f(x2)給定x1、h0y1≥y2y2≥y3是h=2hx3=x2+h、y3=f(x3)結(jié)束否h=-hx3=x1y3=y1a=x1、b=x3是x1=x2y1=y2x2=x3y2=y3是a=x3、b=x1否h>0否初始進(jìn)退距前進(jìn)計(jì)算后退計(jì)算21編輯課件

，

搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，從而找到極小點(diǎn)的數(shù)值近似解。

假定在搜索區(qū)間內(nèi)任取兩點(diǎn)，且

3.3區(qū)間消去方法編輯課件(1)f〔a1〕<f〔b1〕,那么極小點(diǎn)必在區(qū)間[a，b1]內(nèi);編輯課件(1)f〔a1〕<f〔b1〕,那么極小點(diǎn)必在區(qū)間[a，b1]內(nèi);(2)f〔a1〕>f〔b1〕,那么極小點(diǎn)必在區(qū)間[α1，b]內(nèi);編輯課件(1)f〔a1〕<f〔b1〕,那么極小點(diǎn)必在區(qū)間[a，b1]內(nèi);(2)f〔a1〕>f〔b1〕,那么極小點(diǎn)必在區(qū)間[α1，b]內(nèi);(3)f〔a1〕=f〔b1〕,那么極小點(diǎn)必在區(qū)間[α1，b1]內(nèi)可以總結(jié)為兩種情況：若，則取[a,b1]為縮小后的搜索區(qū)間。若，則取[a1,b]為縮小后的搜索區(qū)間。編輯課件試探法黃金分割法插值法二次插值法3一維搜索方法分類從前面的分析可知，每次縮短區(qū)間，只需要在區(qū)間內(nèi)再插入一點(diǎn)并計(jì)算其函數(shù)值。而插入點(diǎn)的位置，可以由不同的方法來確定。就形成了不同的一維搜索方法。一維搜索方法分類編輯課件3.4黃金分割法〔0.618法〕黃金分割法黃金分割法的搜索過程編輯課件概述在實(shí)際計(jì)算中，最常用的一維搜索試探方法是黃金分割法，又稱作0.618法。我們可以通過學(xué)習(xí)黃金分割法來了解一維搜索試探方法的根本思想。在搜索區(qū)間[a,b]內(nèi)適當(dāng)插入兩點(diǎn)α1、α2，并計(jì)算其函數(shù)值。α1、α2將區(qū)間分成三段。應(yīng)用函數(shù)的單谷性質(zhì)，通過函數(shù)值大小的比較，刪去其中一段，使搜索區(qū)間得以縮短。然后再在保存下來的區(qū)間上作同樣的處置，如此迭代下去，使搜索區(qū)間無限縮小，從而得到極小點(diǎn)的數(shù)值近似解。3.4黃金分割法〔0.618法〕編輯課件黃金分割法是建立在區(qū)間消去法原理根底上的試探方法。適用于[a,b]區(qū)間上的任何單谷函數(shù)求極小值問題。對(duì)函數(shù)除要求“單谷〞外不作其它要求，甚至可以不連續(xù)。因此，這種方法的適應(yīng)面相當(dāng)廣。黃金分割法對(duì)插入點(diǎn)的要求：1〕要求插入點(diǎn)α1、α2的位置相對(duì)于區(qū)間[a,b]兩端點(diǎn)具有對(duì)稱性，即

其中為待定常數(shù)。1.黃金分割法編輯課件2〕黃金分割法還要求在保存下來的區(qū)間內(nèi)再插入一點(diǎn)所形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布。即每次縮小所得的新區(qū)間長度與縮小前區(qū)間長度之比〔即：區(qū)間收縮率〕為定值。編輯課件設(shè)原區(qū)間[a,b]長度為1如以下圖所示，保存下來的區(qū)間[a,α2]長度為，區(qū)間縮短率為。為了保持相同的比例分布，新插入點(diǎn)α3應(yīng)在位置上，α1在原區(qū)間的位置應(yīng)相當(dāng)于在保存區(qū)間的位置。故有取方程正數(shù)解，得α1、α2將區(qū)間分成三段黃金分割法要求在保存下來的區(qū)間內(nèi)再插入一點(diǎn)所形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布。兩內(nèi)分點(diǎn)值:結(jié)論：所謂黃金分割是指將一線段分成兩段的方法，使整段長與較長段的長度比值等于較長段與較短段長度的比值即。編輯課件黃金分割法要求插入兩點(diǎn)：黃金分割法區(qū)間消去示意圖：3.4黃金分割法〔0.618法〕編輯課件2.黃金分割法的搜索過程（1）給出初始搜索區(qū)間及收斂精度，將賦以

。

〔2〕按坐標(biāo)點(diǎn)計(jì)算公式計(jì)算并計(jì)算其對(duì)應(yīng)的函數(shù)值3.4黃金分割法〔0.618法〕編輯課件〔3〕根據(jù)區(qū)間消去法原理縮短搜索區(qū)間。為了能用原來的坐標(biāo)點(diǎn)計(jì)算公式，進(jìn)行區(qū)間名稱的代換，并在保存區(qū)間中計(jì)算一個(gè)新的試驗(yàn)點(diǎn)及其函數(shù)值。3.4黃金分割法〔0.618法〕編輯課件〔4〕檢查區(qū)間是否縮短到足夠小和函數(shù)值收斂到足夠精度，如果收斂條件滿足，那么取最后兩試驗(yàn)點(diǎn)的平均值作為極小點(diǎn)的數(shù)值近似解。如果條件不滿足那么轉(zhuǎn)向步驟5。〔5〕產(chǎn)生新的插入點(diǎn)：如N0=0，那么取〔5〕如果條件滿足，那么取最后兩試驗(yàn)點(diǎn)的平均值作為極小點(diǎn)的數(shù)值近似解。3.4黃金分割法〔0.618法〕縮短區(qū)間的總次數(shù)〔迭代次數(shù)〕:編輯課件黃金分割法程序框圖給定否否是是止也可采用迭代次數(shù)是否大于或等于k作終止準(zhǔn)那么。編輯課件迭代序號(hào)aby1比較y20-30.0561.94450.115<7.6671-3-1.1110.0561.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.665例3-3：用黃金分割法求的極小值，搜索區(qū)間是解：38編輯課件解析解：39編輯課件例3-1用黃金分割法求函數(shù)f(x)=3x3-4x+2的極小點(diǎn)，給定x0=0,h=1,ε=0.2。解：1〕確定初始區(qū)間a1=x0=0,f1=f(a1)=2a2=x0+h=0+1=1,f2=f(a2)=1由于f1>f2,應(yīng)加大步長繼續(xù)向前探測。a3=x0+2h=0+2=2,f3=f(a3)=18由于f2<f3,可知初始區(qū)間已經(jīng)找到，即[a,b]=[a1,a3]=[0,2]2〕用黃金分割法縮小區(qū)間第一次縮小區(qū)間：a1=0+0.382×(2-0)=0.764,f1=0.282a2=0+0.618×(2-0)=1.236,f2=2.72f1<f2,新區(qū)間[a,b]=[a,a2]=[0,1.236],b-a>0.2編輯課件第二次縮小區(qū)間：令x2=x1=0.764,f2=f1=0.282

x1=0+0.382X(1.236-0)=0.472,f1=0.317由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.472,1.236]因?yàn)閎-a=1.236-0.472=0.764>0.2,應(yīng)繼續(xù)縮小區(qū)間。

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

x2=0.472+0.618X(1.236-0.472)=0.944,f2=0.747由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0.472,0.944]因?yàn)閎-a=0.944-0.472=0.472>0.2,應(yīng)繼續(xù)縮小區(qū)間。編輯課件

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

x1=0.472+0.382X(0.944-0.472)=0.652,f1=0.223由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0.472,0.764]因?yàn)閎-a=0.764-0.472=0.292>0.2,應(yīng)繼續(xù)縮小區(qū)間。第五次縮小區(qū)間：令x2=x1=0.652,f2=f1=0.223

x1=0.472+0.382X(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.5X(0.584+0.764)=0.674,f(x*)=0.222編輯課件概述一維搜索問題是在某一確定區(qū)間內(nèi)尋求一元函數(shù)的極小點(diǎn)的位置，在某些情況下，如果沒有函數(shù)表達(dá)式，但能夠給出假設(shè)干試驗(yàn)點(diǎn)處的函數(shù)值，就可以根據(jù)這些點(diǎn)處的函數(shù)值，利用插值法建立函數(shù)的某種近似表達(dá)式，進(jìn)而求出函數(shù)的極小點(diǎn)，并用它作為原來函數(shù)極小點(diǎn)的近似值。這種方法稱作插值法，又稱作函數(shù)逼近法。3.5

一維搜索的二次插值法編輯課件試探法〔如黃金分割法〕與插值法的比較：不同點(diǎn)：表現(xiàn)在試驗(yàn)點(diǎn)〔插入點(diǎn)〕位置確實(shí)定方法不同。編輯課件多項(xiàng)式是函數(shù)逼近的一種常用工具。在搜索區(qū)間內(nèi)可以利用假設(shè)干試驗(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ù)值來構(gòu)造二次函數(shù)。二次插值法〔拋物線法〕利用三個(gè)點(diǎn)的函數(shù)值形成一個(gè)拋物線來構(gòu)造二次函數(shù)。編輯課件1、牛頓法〔切線法〕對(duì)于一維搜索函數(shù)，假定已經(jīng)給出極小點(diǎn)的一個(gè)較好的近似點(diǎn)，在點(diǎn)附近用一個(gè)二次函數(shù)來逼近函數(shù)

。然后以該二次函數(shù)的極小點(diǎn)作為極小點(diǎn)的一個(gè)新的近似點(diǎn)。根據(jù)極值必要條件：編輯課件牛頓法的幾何解釋：在上圖中，在處用一拋物線代替曲線，相當(dāng)于用一斜線代替。這樣各個(gè)近似點(diǎn)是通過對(duì)作切線求得與軸的交點(diǎn)找到，故牛頓法又稱為切線法。編輯課件牛頓法的計(jì)算步驟：1）給定初始點(diǎn)，控制誤差，并令2）計(jì)算3）求4）若，則求得近似解，停止計(jì)算，否則作5）。5）令轉(zhuǎn)2）。編輯課件例題：

給定，試用牛頓法求其極小點(diǎn)。解：1〕給定初始點(diǎn)，控制誤差2〕3〕4〕編輯課件重復(fù)上邊的過程，進(jìn)行迭代，直到為止?？傻玫接?jì)算結(jié)果如下表:表3-2牛頓法的搜索過程k01234值ak35.166674.334744.03964.00066f'(ak)-52153.3518332.301993.382990.00551f"(ak)-24184.33332109.4458686.8699284.04720ak+15.166674.334744.039604.000664.00059編輯課件優(yōu)點(diǎn)：收斂速度快。缺點(diǎn)：每一點(diǎn)都要進(jìn)行二階導(dǎo)數(shù)，工作量大；當(dāng)用數(shù)值微分代替二階導(dǎo)數(shù)，由于舍入誤差會(huì)影響迭代速度；要求初始點(diǎn)離極小點(diǎn)不太遠(yuǎn)，否那么有可能使極小化發(fā)散或收斂到非極小點(diǎn)。牛頓法的特點(diǎn)：編輯課件２、二次插值法〔拋物線法〕根本思想：二次插值的根本思想是利用目標(biāo)函數(shù)在不同3點(diǎn)的函數(shù)值構(gòu)成一個(gè)與原函數(shù)f(x)相近似的二次多項(xiàng)式p(x)，以函數(shù)p(x)的極值點(diǎn)xp(即p′(x*p)=0的根)作為目標(biāo)函數(shù)f(x)的近似極值點(diǎn)?！?〕二次插值多項(xiàng)式的構(gòu)成及其極值點(diǎn)設(shè)在單谷區(qū)間中的三點(diǎn)

的相應(yīng)函數(shù)值

，那么可以做出如下的二次插值多項(xiàng)式：編輯課件多項(xiàng)式的極值點(diǎn)可從極值的必要條件求得，即，

為了確定這個(gè)極值點(diǎn)，只需計(jì)算出系數(shù)a1和a2

。其方法法是利用a0、a1、a2的聯(lián)立方程組中相鄰兩個(gè)方程消去a0

，從而得到關(guān)于a1、a2的方程組編輯課件解得所以編輯課件如果令那么這樣就得到了f(α)極小點(diǎn)α*的近似解αp。

１）如果區(qū)間長度

足夠小，則由

便得出我們所要求的近似極小點(diǎn)

編輯課件2）如果不滿足，必須縮小區(qū)間

，根據(jù)區(qū)間消取法原理不斷縮小區(qū)間。根據(jù)區(qū)間消去法原理，需要區(qū)間內(nèi)兩點(diǎn)的函數(shù)值。其中點(diǎn)α2的函數(shù)值y2=f〔α2〕，另外一點(diǎn)可取αp點(diǎn)并計(jì)算其函數(shù)值yp=f〔αp〕。當(dāng)y2<yp時(shí)取[α1，αp]為縮短后的搜索區(qū)間〔如右圖〕。當(dāng)y2≥yp時(shí)取[α2，α3]為縮短后的搜索區(qū)間。編輯課件二次插值法程序框圖編輯課件例1：用二次插值法求

上的極小點(diǎn)。

12α144.5α24.54.705120α355y1-0.756802-0.977590y2-0.977590-0.999974y3-0.958924-0.958924αp4.7051204.710594yp-0.999974-0.999998二次插值法計(jì)算過程例如編輯課件例2用二次插值法求函數(shù)f(x)=3x3-4x+2的極小點(diǎn)，給定x0=0,ε=0.2。2〕用二次插值法逼近極小點(diǎn)相鄰三點(diǎn)的函數(shù)值:x1=0,x2=1,x3=2;f1=2,f2=1,f3=18.代入公式：xp*＝0.555,fp=0.292解:1〕確定初始區(qū)間初始區(qū)間[a,b]=[0,2],中間點(diǎn)x2=1,f(x2)=1。編輯課件由于fp<f2,xp*

<x2,新區(qū)間[a,b]=[a,x2]=[0,1]|x2-xp*

|=1-0.555=0.445>0.2,