工程優(yōu)化敏第三章

1、第三章第三章 常用的一維搜索算法常用的一維搜索算法1 搜索算法概述搜索算法概述2 0.618法（黃金分割法）法（黃金分割法）3 “成功成功-失敗失敗”法法4 牛頓法牛頓法5 插值法插值法 設設 (1) (1) 為為D的一個內(nèi)點的一個內(nèi)點; ; (2) (2) 在在 可微可微; ; (3) (3) 為為 的極值點的極值點; ; 則則 。:nfDRR 0f x ( )f xx 求無約束的某可微函數(shù)的最優(yōu)解，求無約束的某可微函數(shù)的最優(yōu)解，根據(jù)一階必要條件，根據(jù)一階必要條件，可令函數(shù)的梯度等于零，由此求得駐點；可令函數(shù)的梯度等于零，由此求得駐點；然后用充分條件進行判別，求出所要的解然后用充分條件進行判

2、別，求出所要的解:nfDRR n元函數(shù)元函數(shù)min( )nx Rf x 求解無約束優(yōu)化問題求解無約束優(yōu)化問題x x ( )f x 設設 (1) (1) 為為D D的一個內(nèi)點的一個內(nèi)點; ; (2) (2) 在在 二次連續(xù)可微二次連續(xù)可微; ; (3) ; (3) ; (4) (4) 正定正定; ;則則 為為 的嚴格局部極小點。的嚴格局部極小點。:nfDRR 2f x ( *)0f x ( )f xx ( )f xx x 對某些較簡單的函數(shù)，這樣做有時是可行的；對某些較簡單的函數(shù)，這樣做有時是可行的； 但對一般但對一般n元函數(shù)元函數(shù) f(x) 來說，由條件來說，由條件 得到的是一得到的是一個非線

3、性方程組，解它相當困難。個非線性方程組，解它相當困難。 對于不可微函數(shù)，當然談不上使用這樣的方法。對于不可微函數(shù)，當然談不上使用這樣的方法。 為此，常直接使用迭代法。為此，常直接使用迭代法。( )0f x0 x10( )( )f xf xkx，*x ，*lim0kkxx ，為了求函數(shù)為了求函數(shù)f(x)的最優(yōu)解，的最優(yōu)解，然后按某種規(guī)劃然后按某種規(guī)劃(即算法即算法)找出比找出比更好的解更好的解再按此種規(guī)則找出比再按此種規(guī)則找出比更好的解更好的解如此即可得到一個解的序列如此即可得到一個解的序列若這個解序列有極限若這個解序列有極限則稱它收斂于則稱它收斂于x*。 若算法是有效的，則它產(chǎn)生的解序列收斂于

4、該問題的最優(yōu)解。若算法是有效的，則它產(chǎn)生的解序列收斂于該問題的最優(yōu)解。 計算機只能進行有限次迭代，一般很難得到準確解，而只能得計算機只能進行有限次迭代，一般很難得到準確解，而只能得到近似解。當達到滿足的精度要求后，即可停止迭代。到近似解。當達到滿足的精度要求后，即可停止迭代。0 x1x，1x2x ，首先給定一個初始估計首先給定一個初始估計x* ( )( *)f xf x ，*.xx根據(jù)相繼兩次迭代的結(jié)果根據(jù)相繼兩次迭代的結(jié)果（1）根據(jù)相繼兩次迭代的絕對誤差）根據(jù)相繼兩次迭代的絕對誤差（2）根據(jù)相繼兩次迭代的相對誤差）根據(jù)相繼兩次迭代的相對誤差（3）根據(jù)目標函數(shù)梯度的模足夠小根據(jù)目標函數(shù)梯度的模

5、足夠小11()(),kkkkf xf xxx11()(),()kkkkkkf xf xxxf xx()kf x011*(1)kkxxxx101 設序列設序列 收斂于收斂于 ，若存在與迭代次數(shù)，若存在與迭代次數(shù) k 無關(guān)的數(shù)無關(guān)的數(shù)時，稱超線性收斂。時，稱超線性收斂。時，稱線性收斂或一階收斂。時，稱線性收斂或一階收斂。 成立，就稱成立，就稱 收斂的階為收斂的階為 ，或者稱，或者稱 階收斂。階收斂。 kx*x 和和 ，使，使k從某個從某個k0開始，都有開始，都有 kx kx當當12當當 ，且，且具有二階收斂速度。具有二階收斂速度。 kx當當2時，稱為二階收斂，也可說時，稱為二階收斂，也可說找初始點

6、找初始點判斷當前點是否滿判斷當前點是否滿足終止條件足終止條件找下一個迭代點找下一個迭代點最優(yōu)解最優(yōu)解(a) 找初始點找初始點(b) 終止條件終止條件(c) 迭代格式迭代格式從當前點出發(fā)，按照某從當前點出發(fā)，按照某種規(guī)則找下一個迭代點種規(guī)則找下一個迭代點是是否否循循環(huán)環(huán)可行算法：所有迭代點都是可行點據(jù)迭代點的可行性 11,()(),()(),()()下降：根據(jù)目標函數(shù)的下降特性非單調(diào)下降算法：算法kkkkkkk lkk f xf xk f xf xlf xf x 不可行算法： 至少有一個迭代點不是可行點直接法：不需要導數(shù)信息根據(jù)是否計算目標函數(shù)和約束函數(shù)的導數(shù)： 需要導數(shù)信息非直接法 ： 迭代點

7、沿某方向產(chǎn)生根據(jù)迭代點是否沿某個方向產(chǎn)生信賴域方法： 迭代點在某區(qū)域內(nèi)搜索產(chǎn)線搜索方法生 kx現(xiàn)假定已迭代到點現(xiàn)假定已迭代到點則從則從都不能使目標函數(shù)值下降。都不能使目標函數(shù)值下降。若若 是一局部極小點，是一局部極小點， 若從若從 出發(fā)至少存在一個方向出發(fā)至少存在一個方向可使目標函數(shù)值有所下降，可使目標函數(shù)值有所下降，圖圖 1 出發(fā)沿任何方向移動出發(fā)沿任何方向移動,kxkxkd,kx如圖如圖1示示1kx1()( )kkf xf xkkxxd1kkkkxxdkdk 若從若從 出發(fā)至少存在一個方向出發(fā)至少存在一個方向 可使目標函數(shù)值有所下可使目標函數(shù)值有所下降，可選定這個方向降，可選定這個方向 ，

8、 這相當于在射線這相當于在射線其中，其中，稱為搜索方向；稱為搜索方向；稱為步長或步長因子。稱為步長或步長因子。圖圖 1kxkd 沿這個方向邁進適當?shù)囊徊?，得到下一個迭代點沿這個方向邁進適當?shù)囊徊剑玫较乱粋€迭代點 ，使使 。上選定新點上選定新點kd0 x:0;k ;kdkxk1;kx:1kk(1) 選定某一初始點選定某一初始點，并令，并令(2) 確定搜索方向確定搜索方向(3) 從從出發(fā)，沿方向出發(fā)，沿方向求步長求步長，以產(chǎn)生下一個迭代點，以產(chǎn)生下一個迭代點(4) 檢查得到的新點檢查得到的新點是否為極小點或近似極小點。是否為極小點或近似極小點。，轉(zhuǎn)回，轉(zhuǎn)回(2)繼續(xù)進行迭代。繼續(xù)進行迭代。 在以

9、上步驟中，選取搜索方向在以上步驟中，選取搜索方向是最關(guān)鍵的一步。是最關(guān)鍵的一步。 各種算法的區(qū)分，主要在于搜索方向各種算法的區(qū)分，主要在于搜索方向 的不同的不同。 若是，則停止迭代。若是，則停止迭代。否則，令否則，令kd1kxkd找初始點找初始點判斷當前點是否滿判斷當前點是否滿足終止條件足終止條件下一個迭代點下一個迭代點 最優(yōu)解最優(yōu)解(a) 找初始點找初始點(b) 終止條件終止條件(c) 迭代格式迭代格式是是否否循循環(huán)環(huán)1kkkkxxdkkd1kxkdkd各種算法的區(qū)各種算法的區(qū) 分，主要在于確定搜索方向的方法不同。分，主要在于確定搜索方向的方法不同。 后面介紹各種后面介紹各種 算法時會給出一

10、個明確的選取算法時會給出一個明確的選取 的方法。的方法。kdkd k(1) 令它等于某一常數(shù)令它等于某一常數(shù)(例如令例如令1k)，這樣做不能保證目標，這樣做不能保證目標函數(shù)值下降。函數(shù)值下降。(2) 第二種稱為可接受點算法，只要能使目標函數(shù)值下降，可第二種稱為可接受點算法，只要能使目標函數(shù)值下降，可 任意選取步長。任意選取步長。 : argmin ()kkkf xd()kkf xdk求目標函數(shù)求目標函數(shù) f(x) 的極小：的極?。哼@項工作是求以這項工作是求以 為變量的一元函數(shù)為變量的一元函數(shù)的極小點的極小點，故常稱這一過程為，故常稱這一過程為（精確）一維搜索或（精確）一維搜索或（精確）線搜索或

11、一維最優(yōu)化（精確）線搜索或一維最優(yōu)化，確定的步長為，確定的步長為。 (3) 第三種方法的思路是：沿搜索方向使目標函數(shù)值下降最多，第三種方法的思路是：沿搜索方向使目標函數(shù)值下降最多， 即沿射線即沿射線kkxxd( )f x1kx1argmin ()kkkkkkkf xdxxd1 T()0.kkf xd 設目標函數(shù)設目標函數(shù)具有一階連續(xù)偏導數(shù)，具有一階連續(xù)偏導數(shù)，規(guī)則產(chǎn)生規(guī)則產(chǎn)生則有則有按下述按下述函數(shù)函數(shù) ，則得，則得( )()kkf xd min k0( )k( ) k+1 T().kkf xd ()kT()kkkkf xdd (1) 試探法：按某種方式找試探點，通過比較一系列試探點的函試探法

12、：按某種方式找試探點，通過比較一系列試探點的函 數(shù)值的大小確定極小點。數(shù)值的大小確定極小點。(2) 區(qū)間收縮法：用某種分割技術(shù)縮小最優(yōu)解所在的區(qū)間區(qū)間收縮法：用某種分割技術(shù)縮小最優(yōu)解所在的區(qū)間(稱稱 為搜索區(qū)間為搜索區(qū)間)。(3) 函數(shù)逼近法：用比較簡單函數(shù)的極小值點近似代替原函數(shù)的函數(shù)逼近法：用比較簡單函數(shù)的極小值點近似代替原函數(shù)的 極小值點。從幾何上看是用比較簡單的曲線近似代替原極小值點。從幾何上看是用比較簡單的曲線近似代替原 來的曲線，用簡單曲線的極小值點代替原曲線的極小點。來的曲線，用簡單曲線的極小值點代替原曲線的極小點。 Newton法、二次插值法、三次插值法法、二次插值法、三次插值

13、法“成功成功-失敗失敗”法法二分法、二分法、0.618法法第三章第三章 常用的一維搜索算法常用的一維搜索算法1 搜索算法概述搜索算法概述2 0.618法（黃金分割法）法（黃金分割法） 3 “成功成功-失敗失敗”法法4 牛頓法牛頓法5 插值法插值法 常用的區(qū)間收縮法主要利用常用的區(qū)間收縮法主要利用單峰函數(shù)的消去性質(zhì)單峰函數(shù)的消去性質(zhì)，從某個，從某個初始搜索區(qū)間出發(fā)，逐步縮小搜索區(qū)間，直到滿足精度要求初始搜索區(qū)間出發(fā)，逐步縮小搜索區(qū)間，直到滿足精度要求為止。為止。：設設 f(x) 是定義在是定義在a, b上的函數(shù)，若上的函數(shù)，若 1） x* a, b 是是f(x)在在a, b上的最小點上的最小點

14、， 2） 若對任意若對任意 x1 , x2, a x1 f (x2); 2 若若x* x1 ，則，則 f (x1) f (x2).則稱則稱 f(x) 為為a, b上的單峰函數(shù)。上的單峰函數(shù)。 f(x)xab連續(xù)單峰函數(shù)f(x)xab不連續(xù)單峰函數(shù)f(x)xab離散單峰函數(shù)f(x)xa b非單峰函數(shù)定理：定理：設設f(x)是區(qū)間是區(qū)間a,b上的一個單峰函數(shù)，上的一個單峰函數(shù)，x*a,b是其極小點，是其極小點， x1 和和x2是是a, b上的任意兩點，且上的任意兩點，且ax1 x2b，那么比較，那么比較f(x1)與與f(x2)的值后，可得出如下的值后，可得出如下結(jié)論：結(jié)論：f(x)xab(I) 消

15、去a, x1 x*x1x2f(x)xab(II) 消去x2, bx*x2x1(II) 若f(x1) f(x2), x*a,x2在單峰函數(shù)的區(qū)間內(nèi)，計算兩個點的函數(shù)值，比較大小后，就能把搜索區(qū)在單峰函數(shù)的區(qū)間內(nèi)，計算兩個點的函數(shù)值，比較大小后，就能把搜索區(qū)間縮小。在已縮小的區(qū)間內(nèi)，仍含有一個函數(shù)值，若再計算另一點的函數(shù)間縮小。在已縮小的區(qū)間內(nèi)，仍含有一個函數(shù)值，若再計算另一點的函數(shù)值，比較后就可進一步縮小搜索區(qū)間值，比較后就可進一步縮小搜索區(qū)間 . .（I） 若f(x1)f(x2)，x*x1,b單峰函數(shù)具有一個重要的消去性質(zhì)單峰函數(shù)具有一個重要的消去性質(zhì) 通過上述定理：通過上述定理： 1去壞留好

16、原則：去壞留好原則：選二點選二點 x1 x2 , 比較比較 f (x1 ) 與與 f (x2 ) ,可去掉可去掉 a , x1 或者或者x2 , b. 2對稱原則：對稱原則： x1 a = b- x2 (1) （使（使“壞壞”的情況去掉，區(qū)間長度不小于的情況去掉，區(qū)間長度不小于“好好”的情況）的情況） 3保持縮減比原則保持縮減比原則 t =(保留的區(qū)間長度原區(qū)間長度保留的區(qū)間長度原區(qū)間長度) 不變。不變。 （使每次保留下來的節(jié)點，（使每次保留下來的節(jié)點， x1或或 x2 ，在下一次的比較中成，在下一次的比較中成 為一個相應比例位置的節(jié)點為一個相應比例位置的節(jié)點 ）。）。 推導縮減比推導縮減比

17、t : 如圖設第一次保留如圖設第一次保留a, x2 (去掉去掉x2 , b), 第二次保第二次保留的長度為留的長度為a, x1 , 則則 x1 x2 b212(2)xaxatbaxa1x2xab1x，2x，a2x為了簡化計算，使得計算為了簡化計算，使得計算量減少，我們希望已經(jīng)計量減少，我們希望已經(jīng)計算的迭代點可以在下次迭算的迭代點可以在下次迭代的時候重復利用。代的時候重復利用。1212, xxxxab21xabxtbaba12(1)()()xat baxat ba12122, xxxxax，1222(1)()()xat xaxat xa，(1) ()at t ba2()at ba11xx，若2

18、1xx，若 (1) ()(1)()t t bat ba 1t5 1 0.6182t2 ()(1)()t bat ba（不滿足要求）（不滿足要求）x1 = a+(1-t)(b-a)=a+0.328(b-a)x2 = a+t(b-a)= a+0.618(b-a)當區(qū)間當區(qū)間的長度充分小時，可將的長度充分小時，可將區(qū)間區(qū)間中點取做極小點的近似中點取做極小點的近似點。點。 步驟步驟1：給定初始區(qū)間：給定初始區(qū)間a,b及允許誤差及允許誤差 ，根據(jù)公式計算，根據(jù)公式計算x1和和 x2 以及以及f(x1)和和f(x2 )；步驟步驟2：若：若b-af(x2 )時，轉(zhuǎn)步時，轉(zhuǎn)步3，當，當f(x1)0 2/ )

19、15(tx1 = + （1- t）(b - )x2 = +t (b - )b - 0?No= x1 , x1 = x2 x2 = +t ( b )yesb= x2 , x2 = x1x1 = + （1-t）( b - )No x1 x2 b x2 b x1 x2 b x1 優(yōu)點：不要求函數(shù)可微，且每次迭代只需計算一優(yōu)點：不要求函數(shù)可微，且每次迭代只需計算一 個函數(shù)值，計算量小，程序簡單個函數(shù)值，計算量小，程序簡單缺點：收斂速度慢。缺點：收斂速度慢。黃金分割法（黃金分割法（0.618 法）的優(yōu)缺點法）的優(yōu)缺點 ：試用試用0.618法求目標函數(shù)法求目標函數(shù) 的最優(yōu)解。的最優(yōu)解。 給定初始區(qū)間給定初

20、始區(qū)間0,2，收斂精度，收斂精度第一次區(qū)間縮短計算過程：第一次區(qū)間縮短計算過程：計算兩點及對應函數(shù)值：計算兩點及對應函數(shù)值： 作數(shù)值比較，可見作數(shù)值比較，可見 ,再做置換：再做置換：3( )21f xxx2:1.236,bx=0.002.0,2ab10.382()0.764,xaba1 ()0.0821, f x20.618()1.236,xaba2()0.4162,f x12()()f xf x1.2360.002ba20.764,x2 ()0.0821, f x , 0,1.236,a b第二次區(qū)間縮短計算過程：第二次區(qū)間縮短計算過程： 作數(shù)值比較，作數(shù)值比較， , ,再做置換：再做置換：

21、10.382()0.472,xaba1 ()0.1612,f x12()()f xf x1:0.472,ax0.7880.002;ba第三次區(qū)間縮短計算過程：第三次區(qū)間縮短計算過程： 作數(shù)值比較，作數(shù)值比較， , ,再做置換：再做置換：2:0.944,bx20.618()0.944,xaba2 ()0.0468, f x12()()f xf x0.4720.002ba22 , 0,1.236,0.764,()0.0821,a bxf x , 0.472,1.236,a b 110.764,( )0.0821,xf x 220.764,()0.0821,xf x , 0.472,0.944,a

22、b 各次的迭代結(jié)果如下：各次的迭代結(jié)果如下：迭代次數(shù)迭代次數(shù)x1x2f(x1)f(x2)a,b|b-a|第第1次次0.7641.236-0.08210.41260,1.2361.236第第2次次0.4720.7640.1612-0.0821 0.472,1.236 0.788第第3次次0.7640.944-0.0821 -0.0468 0.472,0.944 0.472第第4次次0.6520.764-0.0268 -0.0821 0.652,0.944 0.292第第5次次0.7640.832-0.0821 -0.0881 0.764,0.944 0.230第第6次次0.8320.906-0.

23、0881 -0.0683 0.764,0.906 0.124缺點：收斂速度慢缺點：收斂速度慢優(yōu)點：不要求函數(shù)可微，且每次迭代只需計算一個函數(shù)優(yōu)點：不要求函數(shù)可微，且每次迭代只需計算一個函數(shù) 值，計算量小值，計算量小第三章第三章 常用的一維搜索算法常用的一維搜索算法1 搜索算法概述搜索算法概述2 0.618法（黃金分割法）法（黃金分割法） 3 “成功成功-失敗失敗”法法4 牛頓法牛頓法5 插值法插值法 進退算法進退算法 ( (或稱成功或稱成功- -失敗法失敗法) )如何確定包含極小點在內(nèi)的初始區(qū)間如何確定包含極小點在內(nèi)的初始區(qū)間 ?（一）基本思想：（一）基本思想：由單峰函數(shù)的性質(zhì)可知，函數(shù)值在極

24、小點左邊嚴格下降，在右邊嚴格上升。由單峰函數(shù)的性質(zhì)可知，函數(shù)值在極小點左邊嚴格下降，在右邊嚴格上升。f(x)xabx*x0 x1x2從某個初始點出發(fā)，沿函數(shù)值下降的方向前進，直至發(fā)現(xiàn)函數(shù)值上升為止。從某個初始點出發(fā)，沿函數(shù)值下降的方向前進，直至發(fā)現(xiàn)函數(shù)值上升為止。由兩邊高，中間低的三點，可確定極小點所在的初始區(qū)間。由兩邊高，中間低的三點，可確定極小點所在的初始區(qū)間。（二）（二）設給定初始點設給定初始點為為 a 及初始步長為及初始步長為 h, 求搜索區(qū)間求搜索區(qū)間c, d1、選定初始點、選定初始點a 和步長和步長h;f(x) x2、計算并比較、計算并比較f(a)和和f(a+h)；有前進；有前進(

25、1)和后退和后退(2)兩種情況：兩種情況：(1) 前進運算：若前進運算：若f(a) f(a+h), (2) 后退運算：若后退運算：若f(a) 0 及精度及精度 0，步驟步驟2：計算：計算步驟步驟3：若：若 搜索成功搜索成功, 轉(zhuǎn)步驟轉(zhuǎn)步驟4；否則，搜索失敗，；否則，搜索失敗， 轉(zhuǎn)步驟轉(zhuǎn)步驟5。步驟步驟4：令：令 x:= x + h, 轉(zhuǎn)步驟轉(zhuǎn)步驟 2。步驟步驟5：判斷：判斷 若若 停止迭代，停止迭代， ；否則令；否則令 轉(zhuǎn)步驟轉(zhuǎn)步驟 2。缺點：效率低，缺點：效率低， h 選擇要適當，初始步長不能選得太小。選擇要適當，初始步長不能選得太小。優(yōu)點：可以求優(yōu)點：可以求搜索區(qū)間搜索區(qū)間。1( ).f

26、x2().f xh21,12:,:2hh?hh ，*xx,4hh （三）求極小點計算步驟（三）求極小點計算步驟 ：利用利用“成功成功-失敗失敗”法求函數(shù)法求函數(shù) 的搜索區(qū)間，的搜索區(qū)間， 取初始點取初始點 ，步長，步長取初始點取初始點 ，步長，步長3( )21f xxx115 ( )(),28f xf( )()f xf xh因為，12x 1.2h 12x 1,2h 11 ()()(0)1,22f xhff搜索成功，步長加倍；11 (+2 )(3 )(3)(1)0,22f xhhf xhff計算()(3 )f xhf xh因為， 搜索成功，步長加倍；11 (3 +4 )(7 )(7)(3)22,

27、22f xhhf xhff計算(3 )(7 )f xhf xh因為， 搜索失敗，停止迭代；,7 0,3.xh xh得到搜索區(qū)間為得到搜索區(qū)間為 設設 f (x)在在 a ,b上可微，求函數(shù)上可微，求函數(shù)f在在a,b的極小點，就是求的極小點，就是求函數(shù)導數(shù)為零的點。函數(shù)導數(shù)為零的點。 如果如果 則在則在(a,b)內(nèi)一定存在一點內(nèi)一定存在一點x，使得，使得 。 為求極小點，可取為求極小點，可取 ， 若若 , x 為最小點為最小點, x0 = x* ; , x0 在上升段在上升段, x* x0，去掉，去掉a, x0 .00fx00fx00fx 0,0,fafb 0fx02abx用用 或者或者 作新的

28、區(qū)間作新的區(qū)間a,b，繼續(xù)這個過程，繼續(xù)這個過程，逐步將區(qū)間逐步將區(qū)間a,b縮小，縮小，當區(qū)間當區(qū)間a,b的長度充分小時，可將的長度充分小時，可將a,b的中點取做極小的中點取做極小點的近似點的近似點。點。 0, a x0,x b優(yōu)點：計算量較少，而且總能收斂到一個局部極小點。優(yōu)點：計算量較少，而且總能收斂到一個局部極小點。缺點：收斂速度較慢缺點：收斂速度較慢0=2abx步驟步驟1：計算：計算步驟步驟2：若：若 ，令，令 ，轉(zhuǎn)步驟，轉(zhuǎn)步驟3； 若若 ，令，令 ，轉(zhuǎn)步驟，轉(zhuǎn)步驟3； 若若 ，停止，停止， 。步驟步驟3：若：若 ，則，則 ，停止，否則，轉(zhuǎn)步，停止，否則，轉(zhuǎn)步1.0ax00fx00fx

29、00fx0bx0*xx|ba*2abx ：試用二分法求目標函數(shù)試用二分法求目標函數(shù) 的最優(yōu)解。的最優(yōu)解。 給定初始區(qū)間給定初始區(qū)間0,2，收斂精度，收斂精度在在0,2內(nèi)有極小點。內(nèi)有極小點。3( )21f xxx0:1,bx故=0.004.(0)=2,(2)=10,ff01,2abx10.004;ba , 0,1,a b 第一次區(qū)間縮短計算過程：第一次區(qū)間縮短計算過程：2( )32,fxx因為因為所以函數(shù)所以函數(shù)3( )21f xxx0()= (1)10fxf ，第二次區(qū)間縮短計算過程：第二次區(qū)間縮短計算過程：第三次區(qū)間縮短計算過程：第三次區(qū)間縮短計算過程：2 , 0,1,( )32,a bf

30、xx1 , ,1,2a b 01:,2ax故01,22abx10.004;2ba015()= ()024fxf ，3 , ,1,4a b 03:,4ax故03,24abx10.004;4ba035()= ()0416fxf ，各次的迭代結(jié)果如下：各次的迭代結(jié)果如下：迭代迭代9次后，次后，|b-a|=0.003910.004, 故故迭代次數(shù)迭代次數(shù)x0=(a+b)/2f(x0)a,b|b-a|第第1次次x0=110,11第第2次次x0=1/2-5/41/2,11/2第第3次次x0=3/4-5/163/4,11/4第第4次次x0=7/819/643/4,7/81/8第第5次次x0=13/16-0.

31、019513/16,7/81/16第第6次次x0=27/320.013613/16,27/321/32第第7次次x0=53/640.057413/16,53/641/64第第8次次x0=105/1280.018413/16,105/1281/128第第9次次x0=209/256-0.0004209/256,105/1281/256*0.81836.x 第三章第三章 常用的一維搜索算法常用的一維搜索算法1 搜索算法概述搜索算法概述2 0.618法（黃金分割法）法（黃金分割法）3 “成功成功-失敗失敗”法法4 牛頓法牛頓法5 插值法插值法對對 f (x) 在在 x k 點二階泰勒展開：點二階泰勒展

32、開：略去高階項得略去高階項得兩邊對兩邊對x求導，求導，令令 ，得到，得到 牛頓法是一種函數(shù)逼近法，牛頓法是一種函數(shù)逼近法，基本思想是：基本思想是：在極小點附近用在極小點附近用函數(shù)的二階泰勒多項式近似代替目標函數(shù)，從而求得目標函數(shù)函數(shù)的二階泰勒多項式近似代替目標函數(shù)，從而求得目標函數(shù)的極小點的近似值。的極小點的近似值。221( )()()()()()() )2kkkkkkf xf xfxxxfxxxo xx21( )()()()()()2kkkkkf xf xf xxxfxxx( )()()()kkkf xf xfxxx( )=0f x()()kkkf xxxfx當當 f 是二次函數(shù)時，一次迭代

33、就是二次函數(shù)時，一次迭代就可得到極小點?？傻玫綐O小點。取取 作為新的迭代點，繼續(xù)迭代，直到達到精度，這樣就得到了作為新的迭代點，繼續(xù)迭代，直到達到精度，這樣就得到了函數(shù)函數(shù) f 的一個駐點的一個駐點 。以上過程以上過程即即Newton法法。在一定條件下（例如在一定條件下（例如 ），這個駐點是極小點。），這個駐點是極小點。1()=()kkkkf xxxfx( *)0fx*x步驟步驟1：給定初始點：給定初始點 令令 。步驟步驟2：計算：計算 。步驟步驟3：若：若 ，停止，停止， ，否則轉(zhuǎn)步驟，否則轉(zhuǎn)步驟4。步驟步驟4：計算：計算 令令 ，轉(zhuǎn)步驟，轉(zhuǎn)步驟2。10,xR，1k (),()kkf xfx

34、()kf x*kxx1()=()kkkkf xxxfx1kk 特點：收斂速度快，局部二階收斂。特點：收斂速度快，局部二階收斂。缺點：須計算二階導數(shù)，工作量大；對初始點要求高，要求初缺點：須計算二階導數(shù)，工作量大；對初始點要求高，要求初 始點離極小點不太遠，否則有可能使極小化發(fā)散或收斂到非極始點離極小點不太遠，否則有可能使極小化發(fā)散或收斂到非極 小點；局部收斂。小點；局部收斂。 ：試用試用Newton法求函數(shù)法求函數(shù) 的最優(yōu)解。的最優(yōu)解。432( )46164f xxxxx206,10 x0100()()fxxxfx(6)89664.75(6)69ff1211()()fxxxfx(4.75)84

35、.944.75=4.75=4.163(4.75)144.75ff21()(4.75)84.9410,fxf繼續(xù)迭代；22()(4.163)14.66610,fxf繼續(xù)迭代；32( )4121216,fxxxx2( )122412,fxxx2322()()fxxxfx(4.163)14.6664.1634.1634.010(4.163)96.055ff3433()()fxxxfx(4.010)0.84364.010=4.010=4.00004(4.010)84.7212ff24.163x 33()(4.010)0.843610,fxf繼續(xù)迭代；24()(4.00004)0.003410,fxf得

36、到近似解得到近似解*4.00004.x 第三章第三章 常用的一維搜索算法常用的一維搜索算法1 搜索算法概述搜索算法概述2 0.618法（黃金分割法）法（黃金分割法） 3 “成功成功-失敗失敗”法法4 牛頓法牛頓法5 插值法插值法 用用 在在2 個或個或3 個點的函數(shù)值或?qū)?shù)值，構(gòu)造個點的函數(shù)值或?qū)?shù)值，構(gòu)造2 次或次或3次多項式作為次多項式作為 的近似值，以這多項式的極小點作為一個的近似值，以這多項式的極小點作為一個試探點。試探點。 3點點2次，次，2點點2次，次，2點點3次，次，3點點3次，次，2點點3次等插值法次等插值法. 下面以下面以3點點2次插值法（二次插值法）為例：次插值法（二次插值

37、法）為例： f x f x 給定一個初始的最優(yōu)區(qū)間，找到兩個試探點，通過比較這兩給定一個初始的最優(yōu)區(qū)間，找到兩個試探點，通過比較這兩個點函數(shù)值的大小，縮短最優(yōu)區(qū)間，當區(qū)間個點函數(shù)值的大小，縮短最優(yōu)區(qū)間，當區(qū)間的長度充分小時，的長度充分小時，可將可將區(qū)間區(qū)間中點取做極小點的近似中點取做極小點的近似點。點。 可用成功失敗法尋找可用成功失敗法尋找初始的最優(yōu)區(qū)間初始的最優(yōu)區(qū)間， 可作可作為一個試探點，只需找到另外一個試探點即縮短最優(yōu)區(qū)間。為一個試探點，只需找到另外一個試探點即縮短最優(yōu)區(qū)間。123xxx，2x另外一個試探點利用插值法尋找另外一個試探點利用插值法尋找區(qū)間收縮法區(qū)間收縮法下面以下面以3點點2

38、次插值法（拋物線法）為例：次插值法（拋物線法）為例：利用利用 在區(qū)間在區(qū)間 的函數(shù)值的函數(shù)值123xxx yf x 123fxfxfx作出如下的二次插值多項式作出如下的二次插值多項式 P xaxbxc2它應滿足條件它應滿足條件 P xaxbxcffx211111(1) P xaxbxcffx222222 P xaxbxcffx233333(2)(3)從極值的必要條件從極值的必要條件 求得求得 Pxaxb20 bxa2 求出系數(shù)求出系數(shù) 和和 ，就可得到極小點的表達式。，就可得到極小點的表達式。ab b xxa xxff22232323 b xxa xxff22121212, P xaxbxcf

39、fx211111（1） P xaxbxcffx222222 P xaxbxcffx233333（2）（3） b xxa xxffb xxa xxff2222121212232323, xxfxxfxxfbxxxxxx222222231312123122331 xxfxxfxxfaxxxxxx231312123122331 P xaxbxc2聯(lián)立方程組（聯(lián)立方程組（1）、（）、（2）、（）、（3） xxfxxfxxfbxaxxfxxfxxf2222222313121232313121231(4)22 當當x1 ,x2 , x3 等距時，等距時，即即x2 -x1 = x3-x2 =h時，上面的式子

40、可化簡時，上面的式子可化簡所以所以 2122223123(2)22122hxh fh xhxh fhxh fxhfhfhf 132123(- )1+(5)22h f fxfff 1. 尋找滿足如下條件的點（成功失敗法尋找），成為兩頭大尋找滿足如下條件的點（成功失敗法尋找），成為兩頭大中間小的點：中間小的點： x 1 x 2 f (x2 ), f (x2 ) 0 , 則則 為為P(x)的極小值點，且的極小值點，且3.若若 ，則迭代結(jié)束，取，則迭代結(jié)束，取 ，否則在點，否則在點 中中，選取使，選取使f (x) 最小的點作為新的最小的點作為新的x2，并使新的并使新的x 1 ， x3各是新的各是新的x

41、2近旁的左右兩點，繼續(xù)進行迭代，直到滿近旁的左右兩點，繼續(xù)進行迭代，直到滿足終止準則。足終止準則。x13,xx x2xx*xx123,x x x x算法思路：算法思路：cbxxxacffcffxxccxxxx113212113121213231()22(6),. 聯(lián)立方程組（聯(lián)立方程組（1）、（）、（2）、（）、（3）, 可得可得 ffba xxcxx1313113:, ffba xxcxx1212312: 從而從而 b xxa xxff22131313, b xxa xxff22121212所以所以 bca xx113,因此因此ffffccccxxxxacxxxxxx121211131212

42、2323223=: cbxxxacffcffxxccxxxx113212113121213231()22(6),. xxfxxfxxfbxaxxfxxfxxf2222222313121232313121231(4)22 2）用二次插值法逼近極小點）用二次插值法逼近極小點(1) 相鄰三點及其函數(shù)值相鄰三點及其函數(shù)值: x1=0, x2=1, x3=2; f1=2, f2=1, f3=18. 11321()22 ,bcxxxac例用二次插值法求函數(shù)例用二次插值法求函數(shù)f(x)=3x3-4x+2的極小點，的極小點， 給定給定 初始區(qū)間初始區(qū)間0,2, =0.2。解：解：1）確定初始搜索區(qū)間）確定初始

43、搜索區(qū)間初始區(qū)間初始區(qū)間a,b=0,2, 另有一中間點另有一中間點x2=1。1211312121323,ffcffxxccxxxx0 5550 292xf x.,( ).,根據(jù)公式計算差值多項式的極小點根據(jù)公式計算差值多項式的極小點 (2) 在新區(qū)間，相鄰三點及其函數(shù)值在新區(qū)間，相鄰三點及其函數(shù)值: x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1.故新區(qū)間故新區(qū)間a,b=a,x2=0,1， 應繼續(xù)迭代。應繼續(xù)迭代。0 5550 292xf x.,( ).,x1=0, x2=1, x3=2; f1=2, f2=1, f3=18220 2921,0.5551,

44、f xfxx( ).由于由于210.5550.4450.2,xx 11321()22 ,bcxxxac1211312121323,ffcffxxccxxxx0 6070 243xf x.,( ).,根據(jù)公式計算差值多項式的極小點根據(jù)公式計算差值多項式的極小點故新區(qū)間故新區(qū)間a,b=x2,b=0.555,1， 迭代終止。迭代終止。x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1220 2430.292,0.6070.555,f xfxx( ).由于由于20.6070.5550.0520.2,xx0 6070 243xf x.,( ).,故故*0 6070 24

45、3.xxff x.,( ).已知已知f(x1)=f1， f (x1)=f1 ， f(x2)=f2 ，做二次插值多項式，做二次插值多項式P(x) ，可得到最小值點為可得到最小值點為已知已知f(x1)=f1， f (x1)=f1 (0)及二次函數(shù)的極小值及二次函數(shù)的極小值fm，做二次，做二次插值多項式插值多項式P(x) ，可得到最小值點為，可得到最小值點為已知已知f (x1)=f1 ， f (x2)=f2 (f1 f2) ，做二次插值多項式，做二次插值多項式P(x) ，可得到最小值點為可得到最小值點為xxfxxffxxf2211121211()1.2 ()() mffxxf1112. fxxxxf

46、f222112(). 基本思想與二次插值法類似：用四個已知值（如兩個點函數(shù)值及其導數(shù)值）基本思想與二次插值法類似：用四個已知值（如兩個點函數(shù)值及其導數(shù)值）構(gòu)造一個三次多項式構(gòu)造一個三次多項式P3(x)，用，用P3(x)的極小點近似目標函數(shù)的極小點的極小點近似目標函數(shù)的極小點x* 利用函數(shù)在兩點的函數(shù)值和導數(shù)值：利用函數(shù)在兩點的函數(shù)值和導數(shù)值： 32111p xA xxB xxC xxD 三次插值三次插值三次插值法的收斂速度比二次插值法要快，達到三次插值法的收斂速度比二次插值法要快，達到2階收斂速度。階收斂速度。10fx20fx fx p x1x2xx*x求出：11322212121211222121232p xDfxp xA xxB xxC xxDfxpxCfxpxA xxB xxCfx21211232121212122111()()()2()()()3()()()()2()()()()xxfxfxf xf xAxxf xf xxxfxfxBxxCfxDf x極值的條件極值的條件： 211320dp xA xxB xxCdx1/ 2xxCB21303BBACxxAA若0A 若極值充分條件為：將極值點方程帶入上式 212620d p xA xxBdx222122112333333(0)300, 23 BBACBBACB