一維搜索線性搜索PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1一維搜索線性搜索一維搜索線性搜索2()0f X12(,)TnXx xx第3章 一維搜索方法3.1 概述3.1.1 一維問題是多維問題的基礎(chǔ) 求目標(biāo)函數(shù) f (X)的極小點(diǎn)，從理論上說需要求解方程：其中那么如何來求 f (X)的極小點(diǎn)呢？基本思想:011,kkXXXX011()() ,()()kkf Xf Xf Xf X 這種方法是逐次迭代的方法，在電子計(jì)算機(jī)上很容易實(shí)這種方法是逐次迭代的方法，在電子計(jì)算機(jī)上很容易實(shí)現(xiàn)，因此它在優(yōu)化設(shè)計(jì)中被廣泛地采用?，F(xiàn)，因此它在優(yōu)化設(shè)計(jì)中被廣泛地采用。第1頁(yè)/共66頁(yè)3kkkSXfkkkSXfmin:kkkkSaXX1()f X這個(gè)過程稱為一維搜索過程

2、。kkkSXf52128)(212221xxxxXF如：如：52202521282212221xxxxF則則000 0 ,1 1TTXd1100X當(dāng)當(dāng)Sk方向上的任何一點(diǎn)可以表示為其中是步長(zhǎng)因子，為實(shí)系數(shù)，此時(shí) Sk 方向上任何一點(diǎn)的目標(biāo)函數(shù)值為 ，它是參數(shù)的一元函數(shù)。那么在沿 Sk 方向求的極小點(diǎn)，這就是求一元函數(shù) 的極小問題，它可表示為：第2頁(yè)/共66頁(yè))2 , 1 , 0(1kSXXkkk一維搜索示意圖一維搜索示意圖第3頁(yè)/共66頁(yè))(*0)(*)(*)()(xf3.1.2 的確定方法的確定方法第4頁(yè)/共66頁(yè)第5頁(yè)/共66頁(yè)第6頁(yè)/共66頁(yè) 解析法解析法: : f(X f(X(k)(k

3、) + S + S(k) (k) ) ) 沿沿S S(k)(k) 方向在方向在x x(k)(k) 點(diǎn)泰勒展開點(diǎn)泰勒展開； 取二次近似：取二次近似： ( )( )( )( )( )2( )( )( )1()()()2kkkkTkkTkkf xSf xf xSSG xS 0)()()(kkSxfdd對(duì)對(duì)求導(dǎo)，令其為零。求導(dǎo)，令其為零。 ()()()()()()()0kTkkTkkfxSSG xS()()()()()()()()kTkkkTkkfxSSGxS 求得最優(yōu)步長(zhǎng)求得最優(yōu)步長(zhǎng)1()()()kkkkkffs xx第7頁(yè)/共66頁(yè)數(shù)值解法數(shù)值解法基本思路：基本思路： kk 解析解法對(duì)于函數(shù)關(guān)系復(fù)

4、雜、求導(dǎo)困難等情況難以解析解法對(duì)于函數(shù)關(guān)系復(fù)雜、求導(dǎo)困難等情況難以實(shí)現(xiàn)。在實(shí)際優(yōu)化設(shè)計(jì)中，數(shù)值解法的應(yīng)用更為有效，實(shí)現(xiàn)。在實(shí)際優(yōu)化設(shè)計(jì)中，數(shù)值解法的應(yīng)用更為有效，且適合計(jì)算機(jī)的運(yùn)算特點(diǎn)。且適合計(jì)算機(jī)的運(yùn)算特點(diǎn)。 一維搜索也稱一維搜索也稱直線搜索直線搜索。這種方法不僅對(duì)于解決。這種方法不僅對(duì)于解決一維最優(yōu)化問題具有實(shí)際意義，而且也是求解多維最優(yōu)一維最優(yōu)化問題具有實(shí)際意義，而且也是求解多維最優(yōu)化問題的重要支柱?；瘑栴}的重要支柱。一維搜索一般分為兩大步驟：一維搜索一般分為兩大步驟：(1)(1)確定初始搜索區(qū)間確定初始搜索區(qū)間aa，bb，該區(qū)間應(yīng)是包括一維函數(shù)，該區(qū)間應(yīng)是包括一維函數(shù)極小點(diǎn)在內(nèi)的極小點(diǎn)

5、在內(nèi)的單谷區(qū)間單谷區(qū)間。(2)(2)在單谷區(qū)間在單谷區(qū)間a,ba,b內(nèi)通過縮小區(qū)間尋找極小點(diǎn)。內(nèi)通過縮小區(qū)間尋找極小點(diǎn)。 先確定先確定 在的搜索區(qū)間，然后根據(jù)區(qū)間消去法原理在的搜索區(qū)間，然后根據(jù)區(qū)間消去法原理不斷縮小此區(qū)間所，從而獲得不斷縮小此區(qū)間所，從而獲得 的數(shù)值近似解。的數(shù)值近似解。第8頁(yè)/共66頁(yè)1、確定搜索區(qū)間的外推法 在給定區(qū)間內(nèi)僅有一個(gè)谷值（或有唯一的極小點(diǎn)）的函數(shù)稱為單谷函數(shù)，其區(qū)間稱為單谷區(qū)間。函數(shù)值：“大小大”圖形：“高低高”單谷區(qū)間中一定能求得一個(gè)極小點(diǎn)。3.2 確定初始區(qū)間確定初始區(qū)間第9頁(yè)/共66頁(yè)單谷區(qū)間單谷區(qū)間第10頁(yè)/共66頁(yè)f (x)0130f (x)31說明

6、：?jiǎn)喂葏^(qū)間內(nèi)，函數(shù)可以有不可微點(diǎn)，也可以是不連續(xù)函數(shù)；第11頁(yè)/共66頁(yè)基本思想：基本思想：對(duì)對(duì) 任選一個(gè)初始點(diǎn)任選一個(gè)初始點(diǎn) 及初始步長(zhǎng)及初始步長(zhǎng) ，通過比較這兩點(diǎn)函數(shù)值的大小，確定第三點(diǎn)位置，比較這通過比較這兩點(diǎn)函數(shù)值的大小，確定第三點(diǎn)位置，比較這三點(diǎn)的函數(shù)值大小，確定是否為三點(diǎn)的函數(shù)值大小，確定是否為“高高低低高高”形態(tài)。形態(tài)。)(xf1ah步驟：步驟： 1 1）選定初始點(diǎn)）選定初始點(diǎn)a a1 1，初始步長(zhǎng)，初始步長(zhǎng)h=hh=h0 0，計(jì)算，計(jì)算y y1 1=f(a=f(a1 1) )和和y y2 2=f(a=f(a1 1+h)+h)2 2）比較）比較y y1 1和和y y2 2；a a

7、）如果）如果y y1 1yy2 2，向右前進(jìn)，加大步長(zhǎng)，向右前進(jìn)，加大步長(zhǎng)h=2hh=2h0 0，轉(zhuǎn)（，轉(zhuǎn)（3 3）向前；）向前；b b）如果）如果y y1 1yyy3 3 ，加大步長(zhǎng)，加大步長(zhǎng)h=2hh=2h，a a1 1=a=a2 2,a,a2 2=a=a3 3, ,轉(zhuǎn)（轉(zhuǎn)（3 3）繼）繼續(xù)探測(cè)；續(xù)探測(cè)；b b）如果）如果y y2 2y0h0否否初始進(jìn)退距初始進(jìn)退距3xf2x1xx1x2x3x前進(jìn)計(jì)算1x2x3xfx1x2x3x后退計(jì)算1x2x1y2y3y第20頁(yè)/共66頁(yè) ,a b11,a b， 搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，從而找到極小點(diǎn)的數(shù)值近似解。 假定在搜索區(qū)

8、間 內(nèi)任取兩點(diǎn) ，且 )(2)(111bffaff3.3 區(qū)間消去方法區(qū)間消去方法第21頁(yè)/共66頁(yè))(2)(111bffaff第22頁(yè)/共66頁(yè))(2)(111bffaff第23頁(yè)/共66頁(yè))(2)(111bffaff可以總結(jié)為兩種情況：若 ， 則取a,b1為縮小后的搜索區(qū)間。若 ，則取a1,b為縮小后的搜索區(qū)間。)()(11bfaf)()(11bfaf第24頁(yè)/共66頁(yè)試探法 黃金分割法插值法 二次插值法3 一維搜索方法分類 從前面的分析可知，每次縮短區(qū)間，只需要在區(qū)間內(nèi)再插入一點(diǎn)并計(jì)算其函數(shù)值。 而插入點(diǎn)的位置，可以由不同的方法來確定。就形成了不同的一維搜索方法。一維搜索方法分類第25頁(yè)

9、/共66頁(yè)3.4 黃金分割法（法）黃金分割法黃金分割法的搜索過程第26頁(yè)/共66頁(yè)3.4 黃金分割法（法）第27頁(yè)/共66頁(yè)1()bba2()aba1.黃金分割法黃金分割法第28頁(yè)/共66頁(yè)第29頁(yè)/共66頁(yè)第30頁(yè)/共66頁(yè)ab2111a213(1)2圖2-5 黃金分割法)(618. 0)()(618. 0)(21abaabaabbabb兩內(nèi)分點(diǎn)值兩內(nèi)分點(diǎn)值:結(jié)論：結(jié)論：所謂黃金分割是指將一線段分成兩段的方法，使整段長(zhǎng)與較長(zhǎng)段的長(zhǎng)度比值等于較長(zhǎng)段與較短段長(zhǎng)度的比值即所謂黃金分割是指將一線段分成兩段的方法，使整段長(zhǎng)與較長(zhǎng)段的長(zhǎng)度比值等于較長(zhǎng)段與較短段長(zhǎng)度的比值即 。215 10.6182 第3

10、1頁(yè)/共66頁(yè)黃金分割法要求插入兩點(diǎn)：)(618. 0)()(618. 0)(21abaabaabbabb黃金分割法區(qū)間消去示意圖： 黃金分割法（法）黃金分割法（法）第32頁(yè)/共66頁(yè)（1）給出初始搜索區(qū)間 及收斂精度 ，將 賦以 。 , a b0.618（2）按坐標(biāo)點(diǎn)計(jì)算公式計(jì)算 并計(jì)算其對(duì)應(yīng)的函數(shù)值 12和12,ff 黃金分割法（法）黃金分割法（法）第33頁(yè)/共66頁(yè)（3）根據(jù)區(qū)間消去法原理縮短搜索區(qū)間。為了能用原來的坐標(biāo)點(diǎn)計(jì)算公式，進(jìn)行區(qū)間名稱的代換，并在保留區(qū)間中計(jì)算一個(gè)新的試驗(yàn)點(diǎn)及其函數(shù)值。 黃金分割法（法）黃金分割法（法）第34頁(yè)/共66頁(yè)（4）檢查區(qū)間是否縮短到足夠小和函數(shù)值收斂

11、到足夠精度，如果收斂條件滿足，則取最后兩試驗(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ù)值近似解。 黃金分割法（法）黃金分割法（法）618.0ln)/(lnabk縮短區(qū)間的總次數(shù)（迭代次數(shù)）:第35頁(yè)/共66頁(yè)給定,ba)(),(618. 0222xfyabax)(),(382. 0111xfyabax21yy 否否21211,yyxxxa)(),(618. 0222xfyabax是)(),(382. 0111xfyabax12122,yyxxxbab是)()(5 . 0 xffb

12、ax止xfab1x2x1y2y1x2xbxfab1x2x1y2y1x2xa也可采用迭代次數(shù)是否大于或等于 k 作終止準(zhǔn)則。第36頁(yè)/共66頁(yè)38迭代序號(hào)aby1比較y20-30.0561.94450.1157.6671-3-1.1110.0561.944-0.987-0.9873-1.832-1.111-0.6650.056-0.987-0.9875-1.386-1.111-0.940-0.665例3-3：用黃金分割法求 的極小值 ，搜索區(qū)間是2( )2f35 *12解：abaabb21第37頁(yè)/共66頁(yè)39*1()21( 1.3860.665)21.0255ab *()1.0007f 解析解

13、：1,( )1f 第38頁(yè)/共66頁(yè)解：1）確定初始區(qū)間a1=x0=0, f1=f(a1)=2a2=x0+h=0+1=1, f2=f(a2)=1由于f1f2, 應(yīng)加大步長(zhǎng)繼續(xù)向前探測(cè)。a3= x0+2h=0+2=2, f3=f(a3)=18由于f2f3,可知初始區(qū)間已經(jīng)找到，即a,b=a1,a3=0,22）用黃金分割法縮小區(qū)間 第一次縮小區(qū)間： a1(2-0)=0.764, f1 a2=0+0.618 (2-0)=1.236, f2 f1f2, 新區(qū)間a,b=a,a2=0, 1.236, b-a第39頁(yè)/共66頁(yè) 第三次縮小區(qū)間：l令 x1=x2l x2Xl由于f10.2, 應(yīng)繼續(xù)縮小區(qū)間。第

14、40頁(yè)/共66頁(yè)第五次縮小區(qū)間：l令 x2=x1l x1Xl由于f1f2, 故新區(qū)間a,b=x1,b=0.584, 0.764l因?yàn)?b-a=0.764-0.584=0.180.2, 停止迭代。極小點(diǎn)與極小值：xX(0.584+0.764)=0.674, f(x第41頁(yè)/共66頁(yè) 一維搜索的二次插值法一維搜索的二次插值法第42頁(yè)/共66頁(yè)試探法試探法（如黃金分割法）與（如黃金分割法）與插值法插值法的比較：的比較：不同點(diǎn)不同點(diǎn)：表現(xiàn)在試驗(yàn)點(diǎn)（插入點(diǎn)）位置的確定方法不同。：表現(xiàn)在試驗(yàn)點(diǎn)（插入點(diǎn)）位置的確定方法不同。第43頁(yè)/共66頁(yè)第44頁(yè)/共66頁(yè)1、牛頓法（切線法）、牛頓法（切線法） 對(duì)于一維

15、搜索函數(shù)對(duì)于一維搜索函數(shù) ，假定已經(jīng)給出極小點(diǎn)的一個(gè)較，假定已經(jīng)給出極小點(diǎn)的一個(gè)較好的近似點(diǎn)好的近似點(diǎn) ，在，在 點(diǎn)附近用一個(gè)二次函數(shù)點(diǎn)附近用一個(gè)二次函數(shù) 來逼近函數(shù)來逼近函數(shù) 。 yf00 f 20000012ffff 然后以該二次函數(shù)然后以該二次函數(shù) 的極小點(diǎn)作為的極小點(diǎn)作為 極小點(diǎn)的一個(gè)新的極小點(diǎn)的一個(gè)新的近似點(diǎn)近似點(diǎn) 。根據(jù)極值必要條件：。根據(jù)極值必要條件： f1 0 0100ff 1(0,1 ,2 )kkkkfkf第45頁(yè)/共66頁(yè)牛頓法的幾何解釋：牛頓法的幾何解釋：1(0,1,2)kkkkfkf在上圖中，在在上圖中，在 處用一拋物線處用一拋物線 代替曲線代替曲線 ，相當(dāng)于用一斜線相

16、當(dāng)于用一斜線 代替代替 。這樣各個(gè)近似點(diǎn)是。這樣各個(gè)近似點(diǎn)是通過對(duì)通過對(duì) 作切線求得與作切線求得與 軸的交點(diǎn)找到，故牛頓法軸的交點(diǎn)找到，故牛頓法又稱為切線法。又稱為切線法。)(f0)()()(f)(f第46頁(yè)/共66頁(yè)牛頓法的計(jì)算步驟牛頓法的計(jì)算步驟：1 1）給定初始點(diǎn)）給定初始點(diǎn) 0，控制誤差，控制誤差 ，并令，并令 0k 2 2）計(jì)算）計(jì)算 ,kkff3 3）求）求 1kkkkff4 4）若）若 1kk，則求得近似解，則求得近似解 ，1k停止計(jì)算，否則作停止計(jì)算，否則作5 5）。）。 5 5）令）令 1kk轉(zhuǎn)轉(zhuǎn)2 2）。）。 第47頁(yè)/共66頁(yè)例題：例題： 給定給定 43246164f，試

17、用，試用牛頓法求其極小點(diǎn)牛頓法求其極小點(diǎn) 。 解：解：1 1）給定初始點(diǎn)）給定初始點(diǎn) 03，控制誤差，控制誤差 0.001 324(334)f 212(21)f01001331366ff31133662 2）3 3）4 4）第48頁(yè)/共66頁(yè)重復(fù)上邊的過程，進(jìn)行迭代，直到重復(fù)上邊的過程，進(jìn)行迭代，直到 10.001kk為止?？傻玫接?jì)算結(jié)果如下表為止?？傻玫接?jì)算結(jié)果如下表: : 表3-2 牛頓法的搜索過程k01234值ak35.166674.334744.03964.00066f(ak)-52153.3518332.301993.382990.00551f(ak)-24184.33332109.

18、4458686.8699284.04720ak+15.166674.334744.039604.000664.00059第49頁(yè)/共66頁(yè)優(yōu)點(diǎn)：收斂速度快。優(yōu)點(diǎn)：收斂速度快。缺點(diǎn)：每一點(diǎn)都要進(jìn)行二階導(dǎo)數(shù)，工作量大；缺點(diǎn)：每一點(diǎn)都要進(jìn)行二階導(dǎo)數(shù)，工作量大； 當(dāng)用數(shù)值微分代替二階導(dǎo)數(shù)，由于舍入誤當(dāng)用數(shù)值微分代替二階導(dǎo)數(shù)，由于舍入誤差會(huì)影響迭代速度；差會(huì)影響迭代速度； 要求初始點(diǎn)離極小點(diǎn)不太遠(yuǎn)，否則有可能要求初始點(diǎn)離極小點(diǎn)不太遠(yuǎn)，否則有可能使極小化發(fā)散或收斂到非極小點(diǎn)。使極小化發(fā)散或收斂到非極小點(diǎn)。牛頓法的特點(diǎn)：牛頓法的特點(diǎn)：第50頁(yè)/共66頁(yè)、二次插值法（拋物線法）、二次插值法（拋物線法）p p第

19、51頁(yè)/共66頁(yè)（1）二次插值多項(xiàng)式的構(gòu)成及其極值點(diǎn)）二次插值多項(xiàng)式的構(gòu)成及其極值點(diǎn) yf x設(shè) 在單谷區(qū)間中的三點(diǎn) 123的相應(yīng)函數(shù)值 123()fff，則可以做出如下的二次插值多項(xiàng)式： 2012Paaa21011211Paaaf22012222Paaaf23013233Paaaf第52頁(yè)/共66頁(yè)多項(xiàng)式多項(xiàng)式 P的極值點(diǎn)可從極值的必要條件求得的極值點(diǎn)可從極值的必要條件求得1220ppPaa，即，即 12/2paa， n 為了確定這個(gè)極值點(diǎn)，只需計(jì)算出系數(shù)為了確定這個(gè)極值點(diǎn)，只需計(jì)算出系數(shù)a a1 1和和a a2 2 。其方法法是利用其方法法是利用a a0 0、a a1 1、a a2 2的聯(lián)

20、立方程組中相鄰兩個(gè)的聯(lián)立方程組中相鄰兩個(gè)方程消去方程消去a a0 0 ，從而得到關(guān)于，從而得到關(guān)于a a1 1、a a2 2的方程組的方程組第53頁(yè)/共66頁(yè)第54頁(yè)/共66頁(yè)113212pcac31131ffc21121223ffccf() *p ）如果區(qū)間長(zhǎng)度 31足夠小，則由 31p便得出我們所要求的近似極小點(diǎn) p第55頁(yè)/共66頁(yè)2 2）如果不滿足，必須縮小區(qū)間）如果不滿足，必須縮小區(qū)間 13, ，根據(jù)區(qū)間消取法，根據(jù)區(qū)間消取法原理不斷縮小區(qū)間。原理不斷縮小區(qū)間。根據(jù)區(qū)間消去法原理，需要已知根據(jù)區(qū)間消去法原理，需要已知區(qū)間內(nèi)兩點(diǎn)的函數(shù)值。其中點(diǎn)區(qū)間內(nèi)兩點(diǎn)的函數(shù)值。其中點(diǎn)2 2的函數(shù)值的

21、函數(shù)值y y2 2=f=f（2 2）已知，另外已知，另外一點(diǎn)可取一點(diǎn)可取p p點(diǎn)并計(jì)算其函數(shù)值點(diǎn)并計(jì)算其函數(shù)值y yp p=f=f（p p）。）。當(dāng)當(dāng) y y2 2yyp p 時(shí)取時(shí)取 1 1，p p 為縮短后的搜索區(qū)間（如為縮短后的搜索區(qū)間（如右圖）。右圖）。當(dāng)當(dāng)y y2 2yyp p 時(shí)取時(shí)取 2 2，3 3 為縮短為縮短后的搜索區(qū)間。后的搜索區(qū)間。 第56頁(yè)/共66頁(yè)二二次次插插值值法法程程序序框框圖圖第57頁(yè)/共66頁(yè)例1： 用二次插值法求 sin45f在上的極小點(diǎn)。 12144.524.54.705120355y1-0.756802 -0.977590y2-0.977590-0.99

22、9974y3-0.958924 -0.958924p4.7051204.710594yp-0.999974-0.999998第58頁(yè)/共66頁(yè)2 2）用二次插值法逼近極小點(diǎn)）用二次插值法逼近極小點(diǎn)相鄰三點(diǎn)的函數(shù)值相鄰三點(diǎn)的函數(shù)值: : x x1 1=0, =0, x x2 2=1, =1, x x3 3=2; =2; f f1 1=2, =2, f f2 2=1, =1, f f3 3=18. =18. 代入公式：代入公式：222222*2313121232313121231 ()()()2 ()()()pxxfxxfxxfxxxfxxfxxfx xp p* *0.555, f0.555, f

23、p p解解 : : 1 1）確定初始區(qū)間）確定初始區(qū)間初始區(qū)間初始區(qū)間 a a, , b b=0, 2, =0, 2, 中間點(diǎn)中間點(diǎn)x x2 2=1, =1, f f( (x x2 2)=1)=1。第59頁(yè)/共66頁(yè)由于由于f fp p f f2 2, , x xp p * * 0.2, |=1-0.555=0.4450.2, 應(yīng)繼續(xù)迭代。應(yīng)繼續(xù)迭代。在新區(qū)間，相鄰三點(diǎn)的函數(shù)值在新區(qū)間，相鄰三點(diǎn)的函數(shù)值: : x x1 1=0, =0, x x2 2=0.555, =0.555, x x3 3=1; =1; f f1 1=2, =2, f f2 2=0.292, =0.292, f f3 3=

24、1, =1, 代入代入x xp p* *公式計(jì)算得：公式計(jì)算得：x xp p* *0.607, f0.607, fp p 由于由于f fp p x x2 2, , 新區(qū)間新區(qū)間 a a, , b b=x x2 2, , b b=0.555, 1=0.555, 1| |x x2 2- -x xp p * * |=|0.555-0.607|=0.0520.2, |=|0.555-0.607|=0.0520.2, 迭代終止。迭代終止。 x xp p* *第60頁(yè)/共66頁(yè)例例 3 用二次插值法求用二次插值法求 的極值點(diǎn)的極值點(diǎn)。初始搜索區(qū)間。初始搜索區(qū)間 ， 。432( )46164f xxxxx13 1 6x x 0.05解：取解：取x x2 2點(diǎn)為區(qū)間點(diǎn)為區(qū)間 x x1 1, , x x3 3 的中點(diǎn)的中點(diǎn) ， 計(jì)算計(jì)算x x1 1, , x x2 2, , x x3 3 3 3點(diǎn)處的函數(shù)值點(diǎn)處的函數(shù)值f f1 1=1