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

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

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

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

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

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

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

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

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

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

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

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

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

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

14、， 2） 若對(duì)任意若對(duì)任意 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ù)定理：定理：設(shè)設(shè)f(x)是區(qū)間是區(qū)間a,b上的一個(gè)單峰函數(shù)，上的一個(gè)單峰函數(shù)，x*a,b是其極小點(diǎn)，是其極小點(diǎn)， x1 和和x2是是a, b上的任意兩點(diǎn)，且上的任意兩點(diǎn)，且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)，計(jì)算兩個(gè)點(diǎn)的函數(shù)值，比較大小后，就能把搜索區(qū)在單峰函數(shù)的區(qū)間內(nèi)，計(jì)算兩個(gè)點(diǎn)的函數(shù)值，比較大小后，就能把搜索區(qū)間縮小。在已縮小的區(qū)間內(nèi)，仍含有一個(gè)函數(shù)值，若再計(jì)算另一點(diǎn)的函數(shù)間縮小。在已縮小的區(qū)間內(nèi)，仍含有一個(gè)函數(shù)值，若再計(jì)算另一點(diǎn)的函數(shù)值，比較后就可進(jìn)一步縮小搜索區(qū)間值，比較后就可進(jìn)一步縮小搜索區(qū)間 . .（I） 若f(x1)f(x2)，x*x1,b單峰函數(shù)具有一個(gè)重要的消去性質(zhì)單峰函數(shù)具有一個(gè)重要的消去性質(zhì) 通過(guò)上述定理：通過(guò)上述定理： 1去壞留好

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

17、t : 如圖設(shè)第一次保留如圖設(shè)第一次保留a, x2 (去掉去掉x2 , b), 第二次保第二次保留的長(zhǎng)度為留的長(zhǎng)度為a, x1 , 則則 x1 x2 b212(2)xaxatbaxa1x2xab1x，2x，a2x為了簡(jiǎn)化計(jì)算，使得計(jì)算為了簡(jiǎn)化計(jì)算，使得計(jì)算量減少，我們希望已經(jīng)計(jì)量減少，我們希望已經(jīng)計(jì)算的迭代點(diǎn)可以在下次迭算的迭代點(diǎn)可以在下次迭代的時(shí)候重復(fù)利用。代的時(shí)候重復(fù)利用。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)當(dāng)區(qū)間當(dāng)區(qū)間的長(zhǎng)度充分小時(shí)，可將的長(zhǎng)度充分小時(shí)，可將區(qū)間區(qū)間中點(diǎn)取做極小點(diǎn)的近似中點(diǎn)取做極小點(diǎn)的近似點(diǎn)。點(diǎn)。 步驟步驟1：給定初始區(qū)間：給定初始區(qū)間a,b及允許誤差及允許誤差 ，根據(jù)公式計(jì)算，根據(jù)公式計(jì)算x1和和 x2 以及以及f(x1)和和f(x2 )；步驟步驟2：若：若b-af(x2 )時(shí)，轉(zhuǎn)步時(shí)，轉(zhuǎn)步3，當(dāng)，當(dāng)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)點(diǎn)：不要求函數(shù)可微，且每次迭代只需計(jì)算一優(yōu)點(diǎn)：不要求函數(shù)可微，且每次迭代只需計(jì)算一 個(gè)函數(shù)值，計(jì)算量小，程序簡(jiǎn)單個(gè)函數(shù)值，計(jì)算量小，程序簡(jiǎn)單缺點(diǎn)：收斂速度慢。缺點(diǎn)：收斂速度慢。黃金分割法（黃金分割法（0.618 法）的優(yōu)缺點(diǎn)法）的優(yōu)缺點(diǎn) ：試用試用0.618法求目標(biāo)函數(shù)法求目標(biāo)函數(shù) 的最優(yōu)解。的最優(yōu)解。 給定初始區(qū)間給定初

20、始區(qū)間0,2，收斂精度，收斂精度第一次區(qū)間縮短計(jì)算過(guò)程：第一次區(qū)間縮短計(jì)算過(guò)程：計(jì)算兩點(diǎn)及對(duì)應(yīng)函數(shù)值：計(jì)算兩點(diǎn)及對(duì)應(yīng)函數(shù)值： 作數(shù)值比較，可見(jiàn)作數(shù)值比較，可見(jiàn) ,再做置換：再做置換：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ū)間縮短計(jì)算過(guò)程：第二次區(qū)間縮短計(jì)算過(guò)程： 作數(shù)值比較，作數(shù)值比較， , ,再做置換：再做置換：

21、10.382()0.472,xaba1 ()0.1612,f x12()()f xf x1:0.472,ax0.7880.002;ba第三次區(qū)間縮短計(jì)算過(guò)程：第三次區(qū)間縮短計(jì)算過(guò)程： 作數(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缺點(diǎn)：收斂速度慢缺點(diǎn)：收斂速度慢優(yōu)點(diǎn)：不要求函數(shù)可微，且每次迭代只需計(jì)算一個(gè)函數(shù)優(yōu)點(diǎn)：不要求函數(shù)可微，且每次迭代只需計(jì)算一個(gè)函數(shù) 值，計(jì)算量小值，計(jì)算量小第三章第三章 常用的一維搜索算法常用的一維搜索算法1 搜索算法概述搜索算法概述2 0.618法（黃金分割法）法（黃金分割法） 3 “成功成功-失敗失敗”法法4 牛頓法牛頓法5 插值法插值法 進(jìn)退算法進(jìn)退算法 ( (或稱成功或稱成功- -失敗法失敗法) )如何確定包含極小點(diǎn)在內(nèi)的初始區(qū)間如何確定包含極小點(diǎn)在內(nèi)的初始區(qū)間 ?（一）基本思想：（一）基本思想：由單峰函數(shù)的性質(zhì)可知，函數(shù)值在極

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

25、1)和后退和后退(2)兩種情況：兩種情況：(1) 前進(jìn)運(yùn)算：若前進(jìn)運(yùn)算：若f(a) f(a+h), (2) 后退運(yùn)算：若后退運(yùn)算：若f(a) 0 及精度及精度 0，步驟步驟2：計(jì)算：計(jì)算步驟步驟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。缺點(diǎn)：效率低，缺點(diǎn)：效率低， h 選擇要適當(dāng)，初始步長(zhǎng)不能選得太小。選擇要適當(dāng)，初始步長(zhǎng)不能選得太小。優(yōu)點(diǎn)：可以求優(yōu)點(diǎn)：可以求搜索區(qū)間搜索區(qū)間。1( ).f

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

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

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

29、00fx0bx0*xx|ba*2abx ：試用二分法求目標(biāo)函數(shù)試用二分法求目標(biāo)函數(shù) 的最優(yōu)解。的最優(yōu)解。 給定初始區(qū)間給定初始區(qū)間0,2，收斂精度，收斂精度在在0,2內(nèi)有極小點(diǎn)。內(nèi)有極小點(diǎn)。3( )21f xxx0:1,bx故=0.004.(0)=2,(2)=10,ff01,2abx10.004;ba , 0,1,a b 第一次區(qū)間縮短計(jì)算過(guò)程：第一次區(qū)間縮短計(jì)算過(guò)程：2( )32,fxx因?yàn)橐驗(yàn)樗院瘮?shù)所以函數(shù)3( )21f xxx0()= (1)10fxf ，第二次區(qū)間縮短計(jì)算過(guò)程：第二次區(qū)間縮短計(jì)算過(guò)程：第三次區(qū)間縮短計(jì)算過(guò)程：第三次區(qū)間縮短計(jì)算過(guò)程：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 插值法插值法對(duì)對(duì) f (x) 在在 x k 點(diǎn)二階泰勒展開(kāi)：點(diǎn)二階泰勒展

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

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

34、()kf x*kxx1()=()kkkkf xxxfx1kk 特點(diǎn)：收斂速度快，局部二階收斂。特點(diǎn)：收斂速度快，局部二階收斂。缺點(diǎn)：須計(jì)算二階導(dǎo)數(shù)，工作量大；對(duì)初始點(diǎn)要求高，要求初缺點(diǎn)：須計(jì)算二階導(dǎo)數(shù)，工作量大；對(duì)初始點(diǎn)要求高，要求初 始點(diǎn)離極小點(diǎn)不太遠(yuǎn)，否則有可能使極小化發(fā)散或收斂到非極始點(diǎn)離極小點(diǎn)不太遠(yuǎn)，否則有可能使極小化發(fā)散或收斂到非極 小點(diǎn)；局部收斂。小點(diǎn)；局部收斂。 ：試用試用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 個(gè)或個(gè)或3 個(gè)點(diǎn)的函數(shù)值或?qū)?shù)值，構(gòu)造個(gè)點(diǎn)的函數(shù)值或?qū)?shù)值，構(gòu)造2 次或次或3次多項(xiàng)式作為次多項(xiàng)式作為 的近似值，以這多項(xiàng)式的極小點(diǎn)作為一個(gè)的近似值，以這多項(xiàng)式的極小點(diǎn)作為一個(gè)試探點(diǎn)。試探點(diǎn)。 3點(diǎn)點(diǎn)2次，次，2點(diǎn)點(diǎn)2次，次，2點(diǎn)點(diǎn)3次，次，3點(diǎn)點(diǎn)3次，次，2點(diǎn)點(diǎn)3次等插值法次等插值法. 下面以下面以3點(diǎn)點(diǎn)2次插值法（二次插值法）為例：次插值法（二次插值

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

38、次插值法（拋物線法）為例：次插值法（拋物線法）為例：利用利用 在區(qū)間在區(qū)間 的函數(shù)值的函數(shù)值123xxx yf x 123fxfxfx作出如下的二次插值多項(xiàng)式作出如下的二次插值多項(xiàng)式 P xaxbxc2它應(yīng)滿足條件它應(yīng)滿足條件 P xaxbxcffx211111(1) P xaxbxcffx222222 P xaxbxcffx233333(2)(3)從極值的必要條件從極值的必要條件 求得求得 Pxaxb20 bxa2 求出系數(shù)求出系數(shù) 和和 ，就可得到極小點(diǎn)的表達(dá)式。，就可得到極小點(diǎn)的表達(dá)式。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 當(dāng)當(dāng)x1 ,x2 , x3 等距時(shí)，等距時(shí)，即即x2 -x1 = x3-x2 =h時(shí)，上面的式子

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

41、2近旁的左右兩點(diǎn)，繼續(xù)進(jìn)行迭代，直到滿近旁的左右兩點(diǎn)，繼續(xù)進(jìn)行迭代，直到滿足終止準(zhǔn)則。足終止準(zhǔn)則。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）用二次插值法逼近極小點(diǎn)）用二次插值法逼近極小點(diǎn)(1) 相鄰三點(diǎn)及其函數(shù)值相鄰三點(diǎn)及其函數(shù)值: x1=0, x2=1, x3=2; f1=2, f2=1, f3=18. 11321()22 ,bcxxxac例用二次插值法求函數(shù)例用二次插值法求函數(shù)f(x)=3x3-4x+2的極小點(diǎn)，的極小點(diǎn)， 給定給定 初始區(qū)間初始區(qū)間0,2, =0.2。解：解：1）確定初始搜索區(qū)間）確定初始

43、搜索區(qū)間初始區(qū)間初始區(qū)間a,b=0,2, 另有一中間點(diǎn)另有一中間點(diǎn)x2=1。1211312121323,ffcffxxccxxxx0 5550 292xf x.,( ).,根據(jù)公式計(jì)算差值多項(xiàng)式的極小點(diǎn)根據(jù)公式計(jì)算差值多項(xiàng)式的極小點(diǎn) (2) 在新區(qū)間，相鄰三點(diǎn)及其函數(shù)值在新區(qū)間，相鄰三點(diǎn)及其函數(shù)值: x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1.故新區(qū)間故新區(qū)間a,b=a,x2=0,1， 應(yīng)繼續(xù)迭代。應(yīng)繼續(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ì)算差值多項(xiàng)式的極小點(diǎn)根據(jù)公式計(jì)算差值多項(xiàng)式的極小點(diǎn)故新區(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 ，做二次插值多項(xiàng)式，做二次插值多項(xiàng)式P(x) ，可得到最小值點(diǎn)為可得到最小值點(diǎn)為已知已知f(x1)=f1， f (x1)=f1 (0)及二次函數(shù)的極小值及二次函數(shù)的極小值fm，做二次，做二次插值多項(xiàng)式插值多項(xiàng)式P(x) ，可得到最小值點(diǎn)為，可得到最小值點(diǎn)為已知已知f (x1)=f1 ， f (x2)=f2 (f1 f2) ，做二次插值多項(xiàng)式，做二次插值多項(xiàng)式P(x) ，可得到最小值點(diǎn)為可得到最小值點(diǎn)為xxfxxffxxf2211121211()1.2 ()() mffxxf1112. fxxxxf

46、f222112(). 基本思想與二次插值法類似：用四個(gè)已知值（如兩個(gè)點(diǎn)函數(shù)值及其導(dǎo)數(shù)值）基本思想與二次插值法類似：用四個(gè)已知值（如兩個(gè)點(diǎn)函數(shù)值及其導(dǎo)數(shù)值）構(gòu)造一個(gè)三次多項(xiàng)式構(gòu)造一個(gè)三次多項(xiàng)式P3(x)，用，用P3(x)的極小點(diǎn)近似目標(biāo)函數(shù)的極小點(diǎn)的極小點(diǎn)近似目標(biāo)函數(shù)的極小點(diǎn)x* 利用函數(shù)在兩點(diǎn)的函數(shù)值和導(dǎo)數(shù)值：利用函數(shù)在兩點(diǎn)的函數(shù)值和導(dǎo)數(shù)值： 32111p xA xxB xxC xxD 三次插值三次插值三次插值法的收斂速度比二次插值法要快，達(dá)到三次插值法的收斂速度比二次插值法要快，達(dá)到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 若極值充分條件為：將極值點(diǎn)方程帶入上式 212620d p xA xxBdx222122112333333(0)300, 23 BBACBBACB