31 搜索算法結(jié)構(gòu)

《31 搜索算法結(jié)構(gòu)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

3.1搜索算法結(jié)構(gòu)一、下降算法模型考慮（fs）常用一種線性搜索的方式來求解：迭代中從一點出發(fā)沿下降可行方向找一個新的、性質(zhì)有改善的點。迭代計算：其中為第次迭代的搜索方向，為沿搜索的最佳步長因子（通常也稱作最佳步長）。minf(x)s.t.x∈S第三章常用的一維搜索方法

1△可行方向：設(shè)∈S，d∈Rn,d≠0,若存在，使，稱d為點的可行方向。同時滿足上述兩個性質(zhì)的方向稱下降可行方向?！飨陆捣较颍涸O(shè)∈S，d∈Rn,d≠0,若存在，使，稱d為在點的下降方向。

2模型算法線性搜索求，新點使x(k+1)∈S初始x(1)∈S,k=1對x(k)點選擇下降可行方向d(k)是否滿足停機條件？停k=k+1yesno531

3二、收斂性概念：考慮（fs）設(shè)迭代算法產(chǎn)生點列{x(k)}?S.1.理想的收斂性：設(shè)x*∈S是g.opt(全局最優(yōu)解).當(dāng)x*∈{x(k)}或x(k)≠x*，?k，滿足時，稱算法收斂到最優(yōu)解x*。minf(x)s.t.x∈S

4由于非線性規(guī)劃問題的復(fù)雜性，實用中建立下列收斂性概念：2.實用收斂性：定義解集S*={x|x具有某種性質(zhì)}例：S*={x|x---g.opt}S*={x|x---l.opt}S*={x|?f(x)=0}S*={x|f(x)≤β}(β為給定的實數(shù)，稱為閾值)

52.實用收斂性（續(xù)）▲收斂性：設(shè)解集S*≠，{x(k)}為算法產(chǎn)生的點列。下列情況之一成立時，稱算法收斂：1°?x(k)∈S*;2°x(k)S*，?k，{x(k)}的任意極限點∈S*。▲全局收斂：對任意初始點x(1),算法均收斂。局部收斂：當(dāng)x(1)充分接近解x*時，算法收斂。?有限步終止

6三、收斂速度設(shè)算法產(chǎn)生點列{x(k)}，收斂到解x*，且x(k)≠x*，?k，關(guān)于算法的收斂速度，有1.線性收斂：當(dāng)k充分大時成立。2.超線性收斂：3.二階收斂：??﹥0，是使當(dāng)k充分大時有

7三、收斂速度（續(xù)）定理：設(shè)算法點列{x(k)}超線性收斂于x*,且x(k)≠x*，?k，那么證明：只需注意|||x(k+1)–x*||-||x(k)–x*|||≤||x(k+1)–x(k)||≤||x(k+1)–x*||+||x(k)–x*||，除以||x(k)–x*||并令k→∞，利用超線性收斂定義可得結(jié)果。該結(jié)論導(dǎo)出算法的停止條件可用：

8四、二次終結(jié)性▲一個算法用于解正定二次函數(shù)的無約束極小時，有限步迭代可達最優(yōu)解，則稱該算法具有二次終結(jié)性。

9問題描述：已知并且求出了處的可行下降方向從出發(fā)，沿方向求如下目標函數(shù)的最優(yōu)解，或者選取使得：常用的一維搜索算法

10設(shè)其最優(yōu)解為（叫精確步長因子），所以線性搜索是求解一元函數(shù)的最優(yōu)化問題（也叫一維最優(yōu)化問題或一般地，一維優(yōu)化問題可描述為：于是得到一個新點：一維搜索）?；蚪?/p>

11一般地，線性搜索算法分成兩個階段：第一階段確定包含理想的步長因子（或問題最優(yōu)解）的搜索區(qū)間；第二階段采用某種分割技術(shù)或插值方法縮小這個區(qū)間。

12搜索區(qū)間的確定黃金分割法(0.618法)二次插值法Newton法要點：單峰函數(shù)的消去性質(zhì)、進退算法基本思想、黃金分割法基本思想、重新開始、二次插值法要求、極小化框架、Newton法基本思想、方法比較。我們主要介紹如下一些搜索方法：

13學(xué)習(xí)的重要性：1、工程實踐中有時需要直接使用；2、多變量最優(yōu)化的基礎(chǔ)，迭代中經(jīng)常要用到。方法分類：1、直接法：迭代過程中只需要計算函數(shù)值；2、微分法：迭代過程中還需要計算目標函數(shù)的導(dǎo)數(shù)；

14f(x)xab§3.2搜索區(qū)間的確定常用的一維直接法有消去法和近似法兩類。它們都是從某個初始搜索區(qū)間出發(fā)，利用單峰函數(shù)的消去性質(zhì)，逐步縮小搜索區(qū)間，直到滿足精度要求為止?！?.2.1單峰函數(shù)連續(xù)單峰函數(shù)f(x)xab不連續(xù)單峰函數(shù)f(x)xab離散單峰函數(shù)f(x)xab非單峰函數(shù)定義：如果函數(shù)f(x)在區(qū)間[a,b]上只有一個極值點,則稱f(x)為[a,b]上的單峰函數(shù)。

15單峰函數(shù)具有一個重要的消去性質(zhì)定理：設(shè)f(x)是區(qū)間[a,b]上的一個單峰函數(shù)，x*∈[a,b]是其極小點，x1和x2是[a,b]上的任意兩點，且a

16§3.2.2進退算法(或稱成功-失敗法)如何確定包含極小點在內(nèi)的初始區(qū)間?（一）基本思想：由單峰函數(shù)的性質(zhì)可知，函數(shù)值在極小點左邊嚴格下降，在右邊嚴格上升。f(x)xabx*x0x1x2從某個初始點出發(fā)，沿函數(shù)值下降的方向前進，直至發(fā)現(xiàn)函數(shù)值上升為止。由兩邊高，中間低的三點，可確定極小點所在的初始區(qū)間。

17（二）算法1、選定初始點a和步長h;f(x)x2、計算并比較f(a)和f(a+h)；有前進(1)和后退(2)兩種情況：(1)前進運算：若f(a)≥f(a+h),(2)后退運算：若f(a)

18(三)幾點說明缺點：效率低；優(yōu)點：可以求搜索區(qū)間；注意：h選擇要適當(dāng)，初始步長不能選得太?。?/p>

19§3.3區(qū)間消去法－黃金分割法消去法的思想：反復(fù)使用單峰函數(shù)的消去性質(zhì)，不斷縮小包含極小點的搜索區(qū)間，直到滿足精度為止。消去法的優(yōu)點：只需計算函數(shù)值，通用性強。消去法的設(shè)計原則：（1）迭代公式簡單；（2）消去效率高；（3）對稱：x1–a=b-x2；（4）保持縮減比：λ=(保留的區(qū)間長度／原區(qū)間長度)不變。（使每次保留下來的節(jié)點，x1或x2，在下一次的比較中成為一個相應(yīng)比例位置的節(jié)點）。（一）黃金分割xabLλL(1－λ)L取“＋”，λ=0.61803398874189

20（二）黃金分割法的基本思想黃金分割重要的消去性質(zhì):x2abLλL(1－λ)Lx1λL(1－λ)L設(shè)x1，x2為[a,b]中對稱的兩個黃金分割點，x1為[a,x2]的黃金分割點x2為[x1,b]的黃金分割點在進行區(qū)間消去時，不管是消去[a,x1]，還是消去[x2，b]，留下來的區(qū)間中還含一個黃金分割點，只要在對稱位置找另一個黃金分割點，又可以進行下一次區(qū)間消去。每次消去后，新區(qū)間的長度是原區(qū)間的0.618倍，經(jīng)過n次消去后，保留下來的區(qū)間長度為0.618nL，需計算函數(shù)值的次數(shù)為n+1。黃金分割比λ?0.618，所以此法也稱為0.618法。

21（三）算法開始b-x1

22!!!在迭代過程中，四個點的順序始終應(yīng)該是a

23f(x)=x2,a=-1.5,b=1;精度10-5ax1x2b-3.6034e-0052.9804e-0062.7093e-0056.6107e-005220.6180340.618034?(x1-a)/(x2-a)(b-x2)/(b-x1)-3.6034e-005-1.1922e-0052.9804e-0062.7093e-005230.6180340.618034-1.1922e-0052.9804e-0061.219e-0052.7093e-005240.6180350.618035-1.1922e-005-2.7117e-0062.9804e-0061.219e-005250.6180320.618032-1.1922e-005-6.2296e-006-2.7117e-0062.9804e-006260.6180380.618038x*=-2.7117e-006若用0.618效果較差

24f(x)=x2,a=-1.5,b=1;精度10-10ax1x2b-2.1976e-007-9.7339e-008-2.4483e-0089.7933e-008340.6269020.626902-9.7339e-008-2.4483e-0082.5078e-0089.7933e-008350.5951450.595145-9.7339e-008-4.7778e-008-2.4483e-0082.5078e-008360.6802640.680264-4.7778e-008-2.4483e-0081.7832e-0092.5078e-008370.4700170.470017-2.4483e-0081.7832e-009-1.1888e-0092.5078e-008381.127581.12758?(x1-a)/(x2-a)(b-x2)/(b-x1)1.7832e-009-1.1888e-0092.805e-0082.5078e-00839-0.113146-0.1131461.7832e-0093.1022e-008-1.1888e-0092.805e-008-9.83816-9.83816x*=-1.1888e-009(不滿足精度)若用0.618效果更差

25f(x)=x2,a=-1.5,b=1;精度10-10重新開始ax1x2b-7.8811e-0101.9703e-0108.0587e-0101.791e-009440.6180340.618034?(x1-a)/(x2-a)(b-x2)/(b-x1)-7.8811e-010-1.7926e-0101.9703e-0108.0587e-010450.6180340.618034-7.8811e-010-4.1182e-010-1.7926e-0101.9703e-010460.6180340.618034-4.1182e-010-1.7926e-010-3.5532e-0111.9703e-010470.6180340.618034-1.7926e-010-3.5532e-0115.3298e-0111.9703e-010480.6180340.618034-1.7926e-010-9.0432e-011-3.5532e-0115.3298e-011490.6180340.618034-9.0432e-011-3.5532e-011-1.6019e-0125.3298e-011500.6180340.618034x*=-1.6019e-012(滿足要求)

26設(shè)f(x)在[a,b]上可微，且當(dāng)導(dǎo)數(shù)為零時是解。取x=(a+b)/2,那么f'(x)=0時,x為最小點,x=x*;f'(x)>0時,x在上升段,x*x，去掉[a,x].(自己畫算法框圖)axbαtgα>0f′(x)αaxbtgα<0f′(x)§3.4二分法

27[a,b]縮小，當(dāng)區(qū)間[a,b]的長度充分小時，或者當(dāng)充分小時，即可將[a,b]的中點取做極小點的近似點，這時有估計：我們知道，在極小點處，，且時，遞減，即，而當(dāng)，函數(shù)遞增，即若找到一個區(qū)間[a,b],滿足性質(zhì)。，則[a,b]內(nèi)必有的極小點，且，為找此，取，若，則在中有極小點，這時用作為新的區(qū)間[a,b]，繼續(xù)這個過程，逐步將區(qū)間

28假設(shè)f(x)是具有極小點的單峰函數(shù)，則必存在區(qū)間[a,b]，使f'(a)<0,f'(b)>0。由f'(x)的連續(xù)性可知，必有x*?(a,b)，使f'(x)=0f'(x)xaba1b1a2b2優(yōu)點：計算量較少，總能找到最優(yōu)點缺點：要計算導(dǎo)數(shù)值，收斂速度較慢，收斂速度為一階其中區(qū)間[a,b]的確定,一般可采用“進退法”。

29§3.5多項式近似法－二次插值法（一）基本思想對形式復(fù)雜的函數(shù)，數(shù)學(xué)運算時不方便找一個近似的、解析性能好、便于計算的簡單函數(shù)來代替。用近似函數(shù)的極小點作為原函數(shù)極小點的近似復(fù)雜函數(shù)f(x)極小點x**簡單函數(shù)P(x)極小點x*函數(shù)近似，最優(yōu)點也應(yīng)近似一次多項式二次多項式三次多項式?如何構(gòu)造符合要求的多項式?

30f(x)P2(x)（二）二次插值多項式近似法（拋物線法）的基本原理設(shè)目標函數(shù)f(x)在三點x1

31!迭代過程要點！f(x)P2(x)x1x2x3x1x2x3x**x*x**若任意取x1

32在完成一次計算后，得到近似x*，比較f(x*)與f(x2)，以函數(shù)值較小的x為起點，縮短步長近似x*進退算法構(gòu)造“極小化框架”x1

33f(x)xx1x2x3f(x)xx1x2x4前進成功x5極小化框架x1x2x3前進失敗x1x2x3x4x5x6極小化框架x3x2x1后退h02h04h0h0h02h04h0（三）進退算法（用于求“極小化框架”或初始搜索區(qū)間）

34（四）逐次二次插值近似法的算法初始點x1，h0，精度ε1，溢出下限ε2，步長縮短率m進退算法即“極小化框架”x1

35二次插值法的優(yōu)點：收斂速度較快，約為1.32階缺點：對強扭曲或多峰的，收斂慢，甚至?xí)。室蠛瘮?shù)具有較好的解析性能（五）二次插值法與黃金分割法的結(jié)合黃金分割法二次插值法迭代收斂時迭代不收斂時

362）用二次插值法逼近極小點相鄰三點的函數(shù)值:x1=0,x2=1,x3=2;f1=2,f2=1,f3=18.代入公式：xp*＝0.555,fp=0.292例3-3用二次插值法求函數(shù)f(x)=3x3-4x+2的極小點，給定x0=0,h=1,ε=0.2。解1）確定初始區(qū)間初始區(qū)間[a,b]=[0,2],另有一中間點x2=1。

37在新區(qū)間，相鄰三點的函數(shù)值:x1=0,x2=0.555,x3=1;f1=2,f2=0.292,f3=1.xp*＝0.607,fp=0.243由于fpx2,新區(qū)間[a,b]=[x2,b]=[0.555,1]|x2-xp*|=|0.555-0.607|=0.052<0.2,迭代終止。xp*＝0.607,f*=0.243由于fp0.2,應(yīng)繼續(xù)迭代。此例黃金分割法需要5次收縮區(qū)間，例

38例3-4用二次插值法求的極值點。初始搜索區(qū)間，。圖解：取x2點為區(qū)間[x1,x3]的中點，,計算x1,x2,x33點處的函數(shù)值f1=19，f2=-96.9375，f3=124。可見函數(shù)值滿足“高－低－高”形態(tài)。以x1,x2,x3為插值點構(gòu)造二次曲線，求第一次近似的二次曲線p(x)的極小值點，由公式得。，比較函數(shù)值可知這種情況應(yīng)消除左邊區(qū)段。然后用作為x1,x2,x3新3點,重新構(gòu)造二次曲線p(x)，如此反復(fù)計算，直到為止。整個迭代過程的計算結(jié)果列于表2-2.從表中可見，經(jīng)7次迭代后，　　　　　　，終止迭代。故最優(yōu)點

39

40

41要求計算導(dǎo)數(shù)的插值法若目標函數(shù)f(x)可導(dǎo)，可通過解f'(x)＝0求平穩(wěn)點，進而求出極值點。對高度非線性函數(shù)，要用逐次逼近求平穩(wěn)點。一、Newton法要求目標函數(shù)f(x)在搜索區(qū)間內(nèi)具有二階連續(xù)導(dǎo)數(shù)，且已知f‘(x)和f“(x)的表達式。（一）基本思想采用迭代法求φ(x)=0的根xkφ(x)xxk+1xk+2φ’(xk)=－φ(xk)/(xk＋1－xk)xk+1=xk－φ(xk)/φ’(xk)用于求φ(x)＝f'(x)＝0的根xK+1=xk－f’(xk)/f”(xk)0——一點二次插值

42

43牛頓法程序流程：

44例題用Newton法求解初始點取x0=1。（迭代二次）解：f(x)的一階和二階導(dǎo)函數(shù)為迭代公式為xK+1=xk－f’(xk)/f”(xk)第一次迭代：x0=1,f’(x0)＝－12,f”(x0)＝36x1＝1－(－12)/36＝1.33第二次迭代：x1=1.33,f’(x1)＝－3.73,f”(x1)＝17.6x2＝1.33－(－3.73)/17.6＝1.54(本例精確解為x*)第三次迭代：x2=1.54,f’(x2)＝－0.5865,f”(x1)＝12.76x2＝1.54－(－0.587)/12.76＝1.586

45例1：求minf(x)=arctantdt解：f′(x)=arctanx,f″(x)=1／(1+x2)迭代公式：xk+1=xk-(1+xk2)arctanxk取x1=1，計算結(jié)果：kxkf′(xk)1／f″(xk)110.785422-0.5708-0.51871.325830.1169-0.11641.01374-0.001095-0.00109557.9631e-010x4≈x*=0取x1=2，計算結(jié)果如下：2?-3.5357?13.9510?-279.3441?1.2202e+005?不收斂！

46

47(二)優(yōu)缺點1、優(yōu)點：收斂速度快；在f'(x)=0的單根處，是2階收斂；在f'(x)=0的重根處，是線性收斂。2、缺點：需要求二階導(dǎo)數(shù)，若用數(shù)值導(dǎo)數(shù)代替，由于舍入誤差將影響收斂速度；收斂性還依賴于初始點及函數(shù)性質(zhì)。f’(x)x!!!通常在計算程序中規(guī)定最大迭代次數(shù)，當(dāng)次數(shù)達到K還不能滿足精度時，則認為不收斂，要換一個初始點。

48二、二點二次插值af’(x)xbx*1)割線法——基本思想：用割線代替Newton法中的切線，并與區(qū)間消去法相結(jié)合。c?P52(3-14)?P51(3-12)2)另一個二點二次插值——較割線法稍好收斂速度都為1.618階通過檢查區(qū)間兩端導(dǎo)數(shù)來收縮區(qū)間——新區(qū)間兩端點的導(dǎo)數(shù)值異號

49基本思想與二次插值法類似：用四個已知值（如兩個點函數(shù)值及其導(dǎo)數(shù)值）構(gòu)造一個三次多項式P3(x)，用P3(x)的極小點近似目標函數(shù)的極小點x*利用函數(shù)在兩點的函數(shù)值和導(dǎo)數(shù)值：三、三次插值三次插值法的收斂速度比二次插值法要快，達到2階收斂速度。

50求出：

51極值的條件：

52極值充分條件為：將極值點方程帶入上式僅取正號

53

54

55二點三次插值法一般流程：編寫程序應(yīng)用時建議結(jié)合教材框圖編寫，其更具普適性、魯棒性。

56教材P56-58的D.S.C.法、Powell法及其組合法是區(qū)間搜索一二次插值法的結(jié)合！P59-P64介紹了有理插值、連分式方法屬特殊方法，含教材作者的一些研究成果，大家參閱教材，注意其適應(yīng)條件，必要時課選用.

57方法綜述（1）如目標函數(shù)能求二階導(dǎo)數(shù)：用Newton法收斂快（2）如目標函數(shù)能求一階導(dǎo)數(shù)：首先考慮用三次插值法，收斂較快對分法、收斂速度慢，但可靠二次插值如割線法也可選擇.（3）只需計算函數(shù)值的方法：首先考慮用二次插值法,收斂快黃金分割法收斂速度較慢，但可靠

58作業(yè)一、用黃金分割法求函數(shù)f(x)=3x4-4x2+2的極小點，給定x0=-2,h=1,ε=0.1(x0=2,h=1,ε=0.1)。二、ch33.13.7-9課件見http://web.ee.xidian.edu.cn/sszhou/--課程教學(xué)

59解：1)確定初始區(qū)間x1=x0=0,f1=f(x1)=2x2=x0+h=0+1=1,f2=f(x2)=1由于f1>f2,應(yīng)加大步長繼續(xù)向前探測。x3=x0+2h=0+2=2,f3=f(x3)=18由于f20.2例3-1用黃金分割法求函數(shù)f(x)=3x3-4x+2的極小點，給定x0=0,h=1,ε=0.2。

60第三次縮小區(qū)間：令x1=x2=0.764,f1=f2=0.282x2=0.472+0.618X(1.236-0.472)=0.944,f2=0.747由于f10.2,應(yīng)繼續(xù)縮小區(qū)間。第二次縮小區(qū)間：令x2=x1=0.764,f2=f1=0.282x1=0+0.382X(1.236-0)=0.472,f1=0.317由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.472,1.236]因為b-a=1.236-0.472=0.764>0.2,應(yīng)繼續(xù)縮小區(qū)間。

61第四次縮小區(qū)間：令x2=x1=0.764,f2=f1=0.282x1=0.472+0.382X(0.944-0.472)=0.652,f1=0.223由于f10.2,應(yīng)繼續(xù)縮小區(qū)間。第五次縮小區(qū)間：令x2=x1=0.652,f2=f1=0.223x1=0.472+0.382X(0.764-0.472)=0.584,f1=0.262由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.584,0.764]因為b-a=0.764-0.584=0.18<0.2,停止迭代。極小點與極小值：x*=0.5X(0.584+0.764)=0.674,f(x*)=0.222返回