工程優(yōu)化方法及應(yīng)用 第三章(8學(xué)時(shí))

1、Page 1第三章第三章 常用的一維搜索算法常用的一維搜索算法1 一維搜索算法概述一維搜索算法概述2 單峰函數(shù)及其性質(zhì)單峰函數(shù)及其性質(zhì)3 “成功成功-失敗失敗”法（進(jìn)退法）法（進(jìn)退法）4 0.618法（黃金分割法）法（黃金分割法）5 二分法二分法6 牛頓法牛頓法7 插值法插值法Page 21kkkkxxd 步長(zhǎng)因子步長(zhǎng)因子搜索方向搜索方向Page 3u若若 是一局部極小點(diǎn)，則從是一局部極小點(diǎn)，則從 出發(fā)沿任何方向移動(dòng)，都不出發(fā)沿任何方向移動(dòng)，都不能使目標(biāo)函數(shù)值下降。能使目標(biāo)函數(shù)值下降。kxkxu若從若從 出發(fā)至少存在一個(gè)方向出發(fā)至少存在一個(gè)方向 可使目標(biāo)函數(shù)值有所下降，可使目標(biāo)函數(shù)值有所下降，

2、可選定這個(gè)方向可選定這個(gè)方向 ，沿這個(gè)方向邁進(jìn)適當(dāng)?shù)囊徊?，得到下一個(gè)迭，沿這個(gè)方向邁進(jìn)適當(dāng)?shù)囊徊?，得到下一個(gè)迭代點(diǎn)代點(diǎn) ，使，使kxkdkd1kx1()( )kkf xf x這相當(dāng)于在射線(xiàn)這相當(dāng)于在射線(xiàn) 選定新點(diǎn)選定新點(diǎn)kkxxd1kkkkxxd現(xiàn)假定已經(jīng)迭代到點(diǎn)現(xiàn)假定已經(jīng)迭代到點(diǎn) 且已知搜且已知搜索方向索方向 （后面章節(jié)重點(diǎn)講）（后面章節(jié)重點(diǎn)講）現(xiàn)在問(wèn)題：如何確定步長(zhǎng)因子現(xiàn)在問(wèn)題：如何確定步長(zhǎng)因子 ？,kxkdkkkdPage 4u第二種稱(chēng)為可接受點(diǎn)算法：只要能使目標(biāo)函數(shù)值下降，使得第二種稱(chēng)為可接受點(diǎn)算法：只要能使目標(biāo)函數(shù)值下降，使得 f(xk) -f(xk+1) 達(dá)到一個(gè)可接受的量，可任意

3、選取步長(zhǎng)。達(dá)到一個(gè)可接受的量，可任意選取步長(zhǎng)。（不精確一（不精確一維搜索）維搜索）u令它等于某一常數(shù)令它等于某一常數(shù)( (例如令例如令 ) )，這樣做不能保證目標(biāo)函數(shù)，這樣做不能保證目標(biāo)函數(shù)值下降。值下降。1kmin()kkf xd這種方法是求以這種方法是求以 為變量的一元函數(shù)為變量的一元函數(shù) 的極小點(diǎn)的極小點(diǎn) 。故稱(chēng)這一過(guò)程為故稱(chēng)這一過(guò)程為（精確）一維搜索或（精確）線(xiàn)搜索或一維最優(yōu)（精確）一維搜索或（精確）線(xiàn)搜索或一維最優(yōu)化化，確定的步長(zhǎng)為最佳步長(zhǎng)。，確定的步長(zhǎng)為最佳步長(zhǎng)。()kkf xdku第三種方法的思路是：沿搜索方向使目標(biāo)函數(shù)值下降最多，第三種方法的思路是：沿搜索方向使目標(biāo)函數(shù)值下降最

4、多，即沿射線(xiàn)即沿射線(xiàn) ，求目標(biāo)函數(shù)求目標(biāo)函數(shù) 的極小點(diǎn)：的極小點(diǎn)：kkxxd()kkf xdPage 5( )f x1kx1argmin ()kkkkkkkxxdf xd1 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)生構(gòu)造函數(shù)構(gòu)造函數(shù) ，則得，則得( )()kkf xd min k即即 是函數(shù)是函數(shù) 的極小點(diǎn)，所以的極小點(diǎn)，所以0( )k( ) k+1 T().kkf xd ()kT()kkkkf xdd 1()kf xPage 6：若若 使使稱(chēng)稱(chēng) 為為 （1）的搜索區(qū)間。）的搜索區(qū)間。 , (0,)a b* , a

5、b , a bStep 1: 首先確定包含最優(yōu)解的搜索區(qū)間（進(jìn)退法首先確定包含最優(yōu)解的搜索區(qū)間（進(jìn)退法確定搜索區(qū)間確定搜索區(qū)間的一種簡(jiǎn)單方法）；的一種簡(jiǎn)單方法）；Step 2: 然后再采用某種分割技術(shù)或插值方法縮小搜索區(qū)間，直至區(qū)然后再采用某種分割技術(shù)或插值方法縮小搜索區(qū)間，直至區(qū)間收縮為一點(diǎn)為止。間收縮為一點(diǎn)為止。 * 0min ()(1)kkf xdPage 7精確一維搜索方法精確一維搜索方法不精確一維搜索方法不精確一維搜索方法 Armijo-Goldstein、Wolf-Powell準(zhǔn)則準(zhǔn)則消去法：消去法：0.6180.618法、二分法法、二分法函數(shù)逼近法：函數(shù)逼近法：Newton法、插

6、值法法、插值法試探法：試探法：進(jìn)退法（成功失敗法）進(jìn)退法（成功失敗法）u試探法：按某種方式找試探點(diǎn)，通過(guò)比較一系列試探點(diǎn)的函試探法：按某種方式找試探點(diǎn)，通過(guò)比較一系列試探點(diǎn)的函數(shù)值的大小確定極小點(diǎn)。數(shù)值的大小確定極小點(diǎn)。u消去法（區(qū)間收縮法）：用某種分割技術(shù)縮小最優(yōu)解所在區(qū)消去法（區(qū)間收縮法）：用某種分割技術(shù)縮小最優(yōu)解所在區(qū)間。間。u函數(shù)逼近法（近似法）：用簡(jiǎn)單函數(shù)的極小值點(diǎn)近似代替原函數(shù)逼近法（近似法）：用簡(jiǎn)單函數(shù)的極小值點(diǎn)近似代替原函數(shù)的極小值點(diǎn)。從幾何上看是用簡(jiǎn)單的曲線(xiàn)近似代替原來(lái)函數(shù)的極小值點(diǎn)。從幾何上看是用簡(jiǎn)單的曲線(xiàn)近似代替原來(lái)的曲線(xiàn)，用簡(jiǎn)單曲線(xiàn)的極小值點(diǎn)代替原曲線(xiàn)的極小點(diǎn)。的曲線(xiàn)，

7、用簡(jiǎn)單曲線(xiàn)的極小值點(diǎn)代替原曲線(xiàn)的極小點(diǎn)。Page 8第三章第三章 常用的一維搜索算法常用的一維搜索算法1 一維搜索算法概述一維搜索算法概述2 單峰函數(shù)及其性質(zhì)單峰函數(shù)及其性質(zhì)3 “成功成功-失敗失敗”法（進(jìn)退法）法（進(jìn)退法）4 0.618法（黃金分割法）法（黃金分割法）5 二分法二分法6 牛頓法牛頓法7 插值法插值法Page 9常用的一維直接法有常用的一維直接法有消去法消去法和和近似法近似法兩類(lèi)。它們都是從某個(gè)初始搜兩類(lèi)。它們都是從某個(gè)初始搜索區(qū)間出發(fā)，利用索區(qū)間出發(fā)，利用單峰函數(shù)的消去性質(zhì)單峰函數(shù)的消去性質(zhì)，逐步縮小搜索區(qū)間，直到，逐步縮小搜索區(qū)間，直到滿(mǎn)足精度要求為止。因此，本章給出的一維

8、搜索方法主要是針對(duì)單滿(mǎn)足精度要求為止。因此，本章給出的一維搜索方法主要是針對(duì)單峰函數(shù)和單峰區(qū)間。峰函數(shù)和單峰區(qū)間。：設(shè)設(shè) f(x) 是定義在是定義在a, b上的函數(shù)，若上的函數(shù)，若 1） x* a, b 是是f(x)在在a, b上的最小點(diǎn)。上的最小點(diǎn)。 2） 若對(duì)任意若對(duì)任意 x1 , x2, a x1 f (x2); 2 若若x* x1 ，則，則 f (x1) f (x2).則稱(chēng)則稱(chēng) f(x) 為為a, b上的單峰函數(shù)。上的單峰函數(shù)。Page 10f(x)xab連續(xù)單峰函數(shù)f(x)xab不連續(xù)單峰函數(shù)f(x)xab離散單峰函數(shù)f(x)xa b非單峰函數(shù)根據(jù)單峰函數(shù)的定義不難知道，對(duì)于任意三點(diǎn)

9、根據(jù)單峰函數(shù)的定義不難知道，對(duì)于任意三點(diǎn) 有有 ，則區(qū)間，則區(qū)間 包含包含 f(x) 的最小值點(diǎn)。的最小值點(diǎn)。123 xxx123 ()()()f xf xf x13 ,xxPage 11設(shè)設(shè) f(x) 是區(qū)間是區(qū)間a,b上的單峰函數(shù)，上的單峰函數(shù)，x*a,b是其極小點(diǎn)，是其極小點(diǎn)， ax1 x2b，那么比較，那么比較 f(x1) 與與 f(x2)，可得，可得如下結(jié)論：如下結(jié)論：f(x)xabx*x1x2f(x)xabx*x2x1Page 12第三章第三章 常用的一維搜索算法常用的一維搜索算法1 一維搜索算法概述一維搜索算法概述2 單峰函數(shù)及其性質(zhì)單峰函數(shù)及其性質(zhì)3 “成功成功-失敗失敗”法（

10、進(jìn)退法）法（進(jìn)退法）4 0.618法（黃金分割法）法（黃金分割法）5 二分法二分法6 牛頓法牛頓法7 插值法插值法Page 13如何確定包含極小點(diǎn)在內(nèi)的初始區(qū)間如何確定包含極小點(diǎn)在內(nèi)的初始區(qū)間 ?f(x)xabx*x0 x1x2u由單峰函數(shù)的定義可知，函數(shù)值在極小點(diǎn)左邊嚴(yán)格下降，右邊嚴(yán)由單峰函數(shù)的定義可知，函數(shù)值在極小點(diǎn)左邊嚴(yán)格下降，右邊嚴(yán)格上升。格上升。u思想：從某個(gè)初始點(diǎn)出發(fā)，沿函數(shù)值下降的方向前進(jìn)，直至發(fā)現(xiàn)思想：從某個(gè)初始點(diǎn)出發(fā)，沿函數(shù)值下降的方向前進(jìn)，直至發(fā)現(xiàn)函數(shù)值上升為止。函數(shù)值上升為止。u由兩邊高，中間低的三點(diǎn)，可確定極小點(diǎn)所在的初始區(qū)間。由兩邊高，中間低的三點(diǎn)，可確定極小點(diǎn)所在的

11、初始區(qū)間。Page 14 則將步長(zhǎng)改為則將步長(zhǎng)改為h，計(jì)算，計(jì)算f(ah)，若，若f(ah) f(a)令令 a1=ah, b1=a+h, 停止運(yùn)算；否則將步長(zhǎng)加倍，繼續(xù)后退。停止運(yùn)算；否則將步長(zhǎng)加倍，繼續(xù)后退。 則步長(zhǎng)加倍，計(jì)算則步長(zhǎng)加倍，計(jì)算f(a+3h)。若。若f(a+h) f(a+3h)，令令 a1=a, b1=a+3h, 停止運(yùn)算；否則將步長(zhǎng)加倍，并重復(fù)上述運(yùn)算。停止運(yùn)算；否則將步長(zhǎng)加倍，并重復(fù)上述運(yùn)算。進(jìn)退算法步驟進(jìn)退算法步驟1、選定初始點(diǎn)、選定初始點(diǎn)a 和步長(zhǎng)和步長(zhǎng)h;f(x) x2、計(jì)算并比較、計(jì)算并比較f(a)和和f(a+h)；有前進(jìn)；有前進(jìn)(1)和后退和后退(2)兩種情況：兩

12、種情況：(1) 前進(jìn)運(yùn)算：若前進(jìn)運(yùn)算：若f(a) f(a+h), (2) 后退運(yùn)算：若后退運(yùn)算：若f(a) f(a+h), a a+ha+3hf(x) xaa+ha+7ha1b1a-ha-3ha-7ha1b1兩頭高中間低的三點(diǎn)確定搜索區(qū)間兩頭高中間低的三點(diǎn)確定搜索區(qū)間Page 15 ：利用利用“成功成功-失敗失敗”法求函數(shù)法求函數(shù) 的搜索區(qū)間，的搜索區(qū)間， 取初始點(diǎn)取初始點(diǎn) ，步長(zhǎng)，步長(zhǎng)3( )21f xxx115 ( )(),28f xf( )()f xf xh因?yàn)椋?1 ()()(0)1,22f xhff搜索成功，步長(zhǎng)加倍；11 (+2 )(3 )(3)(1)0,22f xhhf xhff

13、計(jì)算()(3 )f xhf xh因?yàn)椋?搜索成功，步長(zhǎng)加倍；11 (3 +4 )(7 )(7)(3)22,22f xhhf xhff計(jì)算(3 )(7 )f xhf xh因?yàn)椋?搜索失敗，停止迭代；,7 0,3.xh xh得到搜索區(qū)間為得到搜索區(qū)間為1/ 2x 1/ 2,h Page 16缺點(diǎn)：缺點(diǎn)：效率低；效率低；優(yōu)點(diǎn)：優(yōu)點(diǎn)：可以求搜索區(qū)間；可以求搜索區(qū)間；注意：注意：h 選擇要適當(dāng)，選擇要適當(dāng)，初始步長(zhǎng)不能選得太小初始步長(zhǎng)不能選得太小。 如果是多峰函數(shù)，分段單峰，區(qū)間收縮法。如果是多峰函數(shù)，分段單峰，區(qū)間收縮法。 Page 17第三章第三章 常用的一維搜索算法常用的一維搜索算法1 一維搜索算

14、法概述一維搜索算法概述2 單峰函數(shù)及其性質(zhì)單峰函數(shù)及其性質(zhì)3 “成功成功-失敗失敗”法（進(jìn)退法）法（進(jìn)退法）4 0.618法（黃金分割法）法（黃金分割法）5 二分法二分法6 牛頓法牛頓法7 插值法插值法Page 18反復(fù)利用單峰函數(shù)的消去性質(zhì)，不斷縮小包含極小點(diǎn)反復(fù)利用單峰函數(shù)的消去性質(zhì)，不斷縮小包含極小點(diǎn)的搜索區(qū)間，直到滿(mǎn)足精度為止。的搜索區(qū)間，直到滿(mǎn)足精度為止。設(shè)設(shè) f：RR 在在a, b 上是單峰函數(shù)，上是單峰函數(shù)， a x1 x2 b 。那么那么 1若若 f (x1) f (x2)，則，則 x* x1 , b= a1 , b1 2若若 f (x1) f (x2) ，則，則 x* a,

15、x2 = a1 , b1一直下去，得到一區(qū)間套一直下去，得到一區(qū)間套f(x)xab(I) 消去a, x1 x*x1x2f(x)xab(II) 消去x2, bx*x2x1(II) 若f(x1) 0 0.618w b - f( x2)?No x1 x2 b x2 b x1 x2 b x1當(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)。 Page 22 ：試用試用0.618法求目標(biāo)函數(shù)法求目標(biāo)函數(shù) 的最優(yōu)解。的最優(yōu)解。 給定初始區(qū)間給定初始區(qū)間0,2，收斂精度，收斂精度第一次區(qū)間縮短計(jì)算過(guò)程：第一次區(qū)間縮短計(jì)算過(guò)程：計(jì)算兩點(diǎn)及對(duì)應(yīng)函數(shù)值：計(jì)

16、算兩點(diǎn)及對(duì)應(yīng)函數(shù)值： 作數(shù)值比較，可見(jiàn)作數(shù)值比較，可見(jiàn) ,消去消去x2,b，再做置換：，再做置換：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 b22 , 0,1.236,0.764,()0.0821,a bxf x Page 23第二次區(qū)間縮短計(jì)算過(guò)程：第二次區(qū)間縮短計(jì)算過(guò)程： 作數(shù)值比較，作數(shù)值比較， , , 消去消去 a,x

17、1，再做置換：再做置換：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ù)值比較， , ,消去消去x2,b，再做置換：再做置換：2:0.944,bx20.618()0.944,xaba2 ()0.0468, f x12()()f xf x0.4720.002ba , 0.472,1.236,a b 110.764,( )0.0821,xf x 220.764,()0.0821,xf x , 0.472,0.944,a b Page 24各次的迭代

18、結(jié)果如下：各次的迭代結(jié)果如下：迭代次數(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.08210.472,1.2360.788第3次0.7640.944-0.0821-0.04680.472,0.9440.472第4次0.6520.764-0.0268-0.08210.652,0.9440.292第5次0.7640.832-0.0821-0.08810.764,0.9440.230第6次0.8320.906-0.0881-0.06830.764,0.9060.124缺點(diǎn)：收斂速度

19、慢缺點(diǎn)：收斂速度慢優(yōu)點(diǎn)：不要求函數(shù)可微，且每次迭代只需計(jì)算一個(gè)函數(shù)優(yōu)點(diǎn)：不要求函數(shù)可微，且每次迭代只需計(jì)算一個(gè)函數(shù) 值，計(jì)算量小，程序簡(jiǎn)單。值，計(jì)算量小，程序簡(jiǎn)單。Page 25第三章第三章 常用的一維搜索算法常用的一維搜索算法1 一維搜索算法概述一維搜索算法概述2 單峰函數(shù)及其性質(zhì)單峰函數(shù)及其性質(zhì)3 “成功成功-失敗失敗”法（進(jìn)退法）法（進(jìn)退法）4 0.618法（黃金分割法）法（黃金分割法）5 二分法二分法6 牛頓法牛頓法7 插值法插值法Page 26 設(shè)設(shè) f (x)在在 a ,b上可續(xù)可微且為單峰函數(shù)，求函數(shù)上可續(xù)可微且為單峰函數(shù)，求函數(shù) f 在在a,b的極小點(diǎn)，就是求函數(shù)導(dǎo)數(shù)為零的點(diǎn)。

20、的極小點(diǎn)，就是求函數(shù)導(dǎo)數(shù)為零的點(diǎn)。 如果如果 則在則在(a,b)內(nèi)一定存在一點(diǎn)內(nèi)一定存在一點(diǎn) x，使得使得 。 為求極小點(diǎn)，可取為求極小點(diǎn)，可取 若若 , x0為最小點(diǎn)為最小點(diǎn), x0 = x* ;若若 , x0 在上升段在上升段, x* x0，保留，保留x0 ,b .00fx00fx00fx 0,0,fafb 0fx02abx當(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)。 繼繼續(xù)續(xù)Page 27步驟步驟1：設(shè)初始搜索區(qū)間：設(shè)初始搜索區(qū)間 a ,b，計(jì)算計(jì)算步驟步驟2：若：若 ，令，令 ，轉(zhuǎn)步驟，轉(zhuǎn)步驟3； 若若 ，令，令 ，轉(zhuǎn)步驟

21、，轉(zhuǎn)步驟3； 若若 ，停止，停止， 。步驟步驟3：若：若 ，則，則 ，停止，否則，轉(zhuǎn)步，停止，否則，轉(zhuǎn)步1.優(yōu)點(diǎn)：計(jì)算量較少，而且總能收斂到一個(gè)局部極小點(diǎn)。優(yōu)點(diǎn)：計(jì)算量較少，而且總能收斂到一個(gè)局部極小點(diǎn)。缺點(diǎn)：收斂速度較慢。缺點(diǎn)：收斂速度較慢。0=2abx0ax00fx00fx00fx0bx0*xx|ba*2abxPage 28 ：試用二分法求目標(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 ,

22、0,1,a b 第一次區(qū)間縮短計(jì)算過(guò)程：第一次區(qū)間縮短計(jì)算過(guò)程：2( )32,fxx因?yàn)橐驗(yàn)樗院瘮?shù)所以函數(shù)3( )21f xxx0()= (1)10fxf ，Page 29第二次區(qū)間縮短計(jì)算過(guò)程：第二次區(qū)間縮短計(jì)算過(guò)程：第三次區(qū)間縮短計(jì)算過(guò)程：第三次區(qū)間縮短計(jì)算過(guò)程：2 , 0,1,( )32,a bfxx1 , ,1,2a b 01:,2ax故01,22abx10.004;2ba015()= ()024fxf ，3 , ,1,4a b 03:,4ax故03,24abx10.004;4ba035()= ()0416fxf ，Page 30各次的迭代結(jié)果如下：各次的迭代結(jié)果如下：迭代迭代9次后

23、，次后，|b-a|=0.003910.004, 故故迭代次數(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.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

24、/256*0.81836.x Page 31第三章第三章 常用的一維搜索算法常用的一維搜索算法1 一維搜索算法概述一維搜索算法概述2 單峰函數(shù)及其性質(zhì)單峰函數(shù)及其性質(zhì)3 “成功成功-失敗失敗”法（進(jìn)退法）法（進(jìn)退法）4 0.618法（黃金分割法）法（黃金分割法）5 二分法二分法6 牛頓法牛頓法7 插值法插值法Page 32在搜索區(qū)間取一點(diǎn)在搜索區(qū)間取一點(diǎn)x k ，對(duì)，對(duì) f (x) 在在 x k 點(diǎn)二階泰勒展開(kāi)：點(diǎn)二階泰勒展開(kāi)：略去高階項(xiàng)得略去高階項(xiàng)得兩邊對(duì)兩邊對(duì) x 求導(dǎo)，得求導(dǎo)，得最后令最后令 ，得，得 牛頓法的基本思想：牛頓法的基本思想：牛頓法是一種函數(shù)逼近法，其基本思想在牛頓法是一種函

25、數(shù)逼近法，其基本思想在極小點(diǎn)附近用函數(shù)的二階泰勒多項(xiàng)式近似代替目標(biāo)函數(shù)，從而極小點(diǎn)附近用函數(shù)的二階泰勒多項(xiàng)式近似代替目標(biāo)函數(shù)，從而求得目標(biāo)函數(shù)的極小點(diǎn)的近似值。求得目標(biāo)函數(shù)的極小點(diǎn)的近似值。221( )()()()()()() )2kkkkkkf xf xfxxxfxxxo xx21( )()()()()()2kkkkkf xf xf xxxfxxx( )()()()kkkf xf xfxxx( )=0f x()()kkkf xxxfxPage 33取取 作為新的迭代點(diǎn)，繼續(xù)迭代，直到達(dá)到所需精度，這樣就得作為新的迭代點(diǎn)，繼續(xù)迭代，直到達(dá)到所需精度，這樣就得到了函數(shù)到了函數(shù) f 的一個(gè)駐點(diǎn)的一

26、個(gè)駐點(diǎn) x* 。在一定條件下（例如在一定條件下（例如 ），這個(gè)駐點(diǎn)是極小點(diǎn)。），這個(gè)駐點(diǎn)是極小點(diǎn)。1()=()kkkkf xxxfx( *)0fx特別，當(dāng)特別，當(dāng) f 是二次函數(shù)時(shí)，一次迭代就可得到極小點(diǎn)。換言是二次函數(shù)時(shí)，一次迭代就可得到極小點(diǎn)。換言之，牛頓法具有二次終止性。之，牛頓法具有二次終止性。牛頓迭代公式牛頓迭代公式Page 34步驟步驟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 (),()kkfxfx()kf x*kxx1()=()k

27、kkkf xxxfx1kk 優(yōu)點(diǎn)：收斂速度快，局部二階收斂。優(yōu)點(diǎn)：收斂速度快，局部二階收斂。缺點(diǎn)缺點(diǎn)：(1)需計(jì)算二階導(dǎo)數(shù)，工作量大；需計(jì)算二階導(dǎo)數(shù)，工作量大；(2)對(duì)初始點(diǎn)要求高，要對(duì)初始點(diǎn)要求高，要求初始點(diǎn)離極小點(diǎn)不能太遠(yuǎn)，否則有可能使極小化發(fā)散或收斂求初始點(diǎn)離極小點(diǎn)不能太遠(yuǎn)，否則有可能使極小化發(fā)散或收斂到非極小點(diǎn)；到非極小點(diǎn)；(3)局部收斂。局部收斂。牛頓迭代公式牛頓迭代公式Page 35 ：試用試用Newton法求函數(shù)法求函數(shù) 的最優(yōu)解。的最優(yōu)解。432( )46164f xxxxx206,10 x0100()()fxxxfx(6)89664.75(6)69ff1211()()fxxx

28、fx(4.75)84.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,fxxxPage 362322()()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.00

29、004)0.003410,fxf得到近似解得到近似解*4.00004.x Page 37第三章第三章 常用的一維搜索算法常用的一維搜索算法1 一維搜索算法概述一維搜索算法概述2 單峰函數(shù)及其性質(zhì)單峰函數(shù)及其性質(zhì)3 “成功成功-失敗失敗”法（進(jìn)退法）法（進(jìn)退法）4 0.618法（黃金分割法）法（黃金分割法）5 二分法二分法6 牛頓法牛頓法7 插值法插值法Page 38對(duì)形式復(fù)雜的對(duì)形式復(fù)雜的函數(shù)，數(shù)學(xué)運(yùn)函數(shù)，數(shù)學(xué)運(yùn)算時(shí)不方便算時(shí)不方便找一個(gè)近似的、解析找一個(gè)近似的、解析性能好、便于計(jì)算的性能好、便于計(jì)算的簡(jiǎn)單函數(shù)來(lái)代替。簡(jiǎn)單函數(shù)來(lái)代替。用近似函數(shù)的極用近似函數(shù)的極小點(diǎn)作為原函數(shù)小點(diǎn)作為原函數(shù)極小

30、點(diǎn)的近似極小點(diǎn)的近似復(fù)雜函數(shù)復(fù)雜函數(shù) f(x) 極小點(diǎn)極小點(diǎn)x* 簡(jiǎn)單函數(shù)簡(jiǎn)單函數(shù)P(x) 極小點(diǎn)極小點(diǎn)x* 一次多項(xiàng)式一次多項(xiàng)式二次多項(xiàng)式二次多項(xiàng)式三次多項(xiàng)式三次多項(xiàng)式牛頓法是一種插值方法（一點(diǎn)二次插值法），是利用一點(diǎn)處的牛頓法是一種插值方法（一點(diǎn)二次插值法），是利用一點(diǎn)處的函數(shù)值、一階和二階導(dǎo)數(shù)值構(gòu)造二次插值函數(shù)。下面再介紹其他的函數(shù)值、一階和二階導(dǎo)數(shù)值構(gòu)造二次插值函數(shù)。下面再介紹其他的一些插值方法。一些插值方法。Page 39利用利用 在搜索區(qū)間在搜索區(qū)間 的函數(shù)值的函數(shù)值123xxx yf x 123fxfxfx作出如下的二次插值多項(xiàng)式作出如下的二次插值多項(xiàng)式 2012P xaa xa

31、 x它應(yīng)滿(mǎn)足條件它應(yīng)滿(mǎn)足條件 210112111P xaa xa xffx(1)3點(diǎn)點(diǎn)2次插值法的基本原理次插值法的基本原理 220122222P xaa xa xffx 230132333P xaa xa xffx(2)(3)x2f(x)P2(x)x1x3Page 40從極值的必要條件從極值的必要條件 求得求得 1220Pxaa x axa122 根據(jù)克萊姆法則，得根據(jù)克萊姆法則，得fxfxfxxxfxfxf21122223311223311111211 xxfxxfxxfxaaxxfxxfxxf222222231312123122313121231/ 2(A)2 按列展開(kāi)，得按列展開(kāi)，得P

32、age 41 兩式相減（兩式相減（1）-（3）、）、 （1） -（2）, 可得可得 131213113:,ffaaxxcxx 121212312:ffaaxxcxx 從而從而 2211321313,axxaxxff 2211221212axxaxxff所以所以 11213,acaxx12121113121222323223=:ffffccccxxxxacxxxxxx cxaaxxcffcffxxccxxxx11213212113121213231/ 2()2(B),. (A) 式可簡(jiǎn)化（式可簡(jiǎn)化（B）式）式Page 42 xxfxxfxxfxaaxxfxxfxxf222222231312123

33、122313121231/ 2(A)2 注：注：當(dāng)當(dāng)x1 ,x2 , x3 等距時(shí)，即等距時(shí)，即x2 -x1 = x3-x2 =h時(shí)，上面的式子可化簡(jiǎn)時(shí)，上面的式子可化簡(jiǎn)h f fxxfff132123(- )1+(A )22 ffcffcxxxxxcccxxxx121131121312213231(),(B)2 從極小化從極小化公式公式 (A) 到公式到公式 (B)，乘除的運(yùn)算次數(shù)從，乘除的運(yùn)算次數(shù)從 14 降為降為 5。Page 43Step 1. 尋找滿(mǎn)足如下條件的點(diǎn)（成功失敗法尋找），成為兩頭大尋找滿(mǎn)足如下條件的點(diǎn)（成功失敗法尋找），成為兩頭大中間小的點(diǎn)：中間小的點(diǎn)： x 1 x 2

34、f (x2 ) f (x3 )Step 2. 計(jì)算計(jì)算 fi=f (xi ) ，i=1, 2, 3。Step 3. 計(jì)算計(jì)算 如果如果 ，停止；否則，停止；否則，當(dāng)當(dāng) ，轉(zhuǎn)步，轉(zhuǎn)步4，否則轉(zhuǎn)步，否則轉(zhuǎn)步5。*2xx*2xxffcxx13113, ffcxxcxx12112223, cxxxc*11321()2Step 4. 若若 ，則令，則令 ，否則令，否則令 ， 轉(zhuǎn)步轉(zhuǎn)步2。*2()()f xf x*322=,=xxxx*1=xxStep 5. 若若 ，則令，則令 ，否則令，否則令 ，轉(zhuǎn)步轉(zhuǎn)步2。*3=xx*2()()f xf x*122=,=xxxxx1x2x3Page 44f(x)P2(

35、x)x1x2x3x1x2x3x*x*x*若任取若任取x1 x2 x3 三點(diǎn)三點(diǎn)，則求出的則求出的x* 可能位于區(qū)間之外或誤差太大?？赡芪挥趨^(qū)間之外或誤差太大。最初的三個(gè)點(diǎn)最初的三個(gè)點(diǎn)x1 x2 x3 應(yīng)構(gòu)成一個(gè)兩邊高，中間低的應(yīng)構(gòu)成一個(gè)兩邊高，中間低的“極小化框極小化框架架” ，即滿(mǎn)足，即滿(mǎn)足f1f2，f3f2 ，極小化框架可由進(jìn)退算法求得。極小化框架可由進(jìn)退算法求得。收斂速度較快，約為收斂速度較快，約為 1.32 1.32 階階對(duì)強(qiáng)扭曲或多峰的，收斂慢，甚至?xí)。室蠛瘮?shù)具對(duì)強(qiáng)扭曲或多峰的，收斂慢，甚至?xí)?，故要求函?shù)具有較好的解析性能有較好的解析性能 Page 45(a) 相鄰三點(diǎn)及

36、其函數(shù)值相鄰三點(diǎn)及其函數(shù)值: x1=0, x2=1, x3=2; f1=2, f2=1, f3=18. 11321()2,cxxxc例用二次插值法求函數(shù)例用二次插值法求函數(shù)f(x)=3x3-4x+2的極小點(diǎn)，的極小點(diǎn)， 給定給定 x0=0, h=1, =0.2。解：解：1）確定初始搜索區(qū)間）確定初始搜索區(qū)間初始區(qū)間初始區(qū)間a,b=0,2, 另有一中間點(diǎn)另有一中間點(diǎn)x2=1。131138=ffcxx0 5550 292xf x.,( ).,根據(jù)公式計(jì)算差值多項(xiàng)式的極小點(diǎn)根據(jù)公式計(jì)算差值多項(xiàng)式的極小點(diǎn)2）用二次插值法逼近極小點(diǎn)）用二次插值法逼近極小點(diǎn)121122239=ffcxxcxxPage 4

37、6 (b) 在新區(qū)間，相鄰三點(diǎn)及其函數(shù)值在新區(qū)間，相鄰三點(diǎn)及其函數(shù)值: x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=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,f xfxx( ).而而11321()2,cxxxc0 6070 243xf x.,( ).,根據(jù)公式計(jì)算差值多項(xiàng)式的極小點(diǎn)根據(jù)公式計(jì)算差值多項(xiàng)式的極小點(diǎn)故消去區(qū)間故消去區(qū)間x2,x3，得新區(qū)間得新區(qū)間a,b=a,x2=0,1210.5550.4450.2,xx 由于由于1

38、3113ffcxx12112223ffcxxcxxPage 47故新區(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 243.xxff x.,( ).Page 48用兩個(gè)點(diǎn)函數(shù)值及其導(dǎo)數(shù)值，構(gòu)造一用兩個(gè)點(diǎn)函數(shù)值及其導(dǎo)數(shù)值，構(gòu)造一個(gè)三次多項(xiàng)式個(gè)三次多項(xiàng)式P3(x)，用，用P3(x)的極小點(diǎn)近似目標(biāo)函數(shù)的極小點(diǎn)的極小點(diǎn)

39、近似目標(biāo)函數(shù)的極小點(diǎn)x* 構(gòu)造三次多項(xiàng)式：構(gòu)造三次多項(xiàng)式： 32111p xA xxB xxC xxD三次插值法的收斂速度比二次插值法要快，達(dá)到三次插值法的收斂速度比二次插值法要快，達(dá)到2階收斂速度。階收斂速度。10fx20fx fx p x1x2xx*x利用利用 在搜索區(qū)間在搜索區(qū)間 兩點(diǎn)的函數(shù)值及其導(dǎo)數(shù)值兩點(diǎn)的函數(shù)值及其導(dǎo)數(shù)值12xx yf x fxfx120,0Page 49 32111p xA xxB xxC xxD113222121212112221212(1)(2)(3)32(4)p xDfxp xA xxB xxC xxDfxpxCfxpxA xxB xxCfx由由3221212

40、11212212121(2)32(4)A xxB xxfxfxfxxxA xxB xxfxfx故故顯然顯然11(),()CfxDf xPage 50(2)式式*2- (4)式式*(x2-x1)，得，得212121321()()() -2()- ()()xxfxfxf xf xAxx(2)式式*3- (4)式式*(x2-x1)，得，得2121212213()()()()2()()f xf xxxfxfxBxx21212132121212122111()()() -2()- ()()3()()()()2()()()()xxfxfxf xf xAxxf xf xxxfxfxBxxCfxDf xPage 51根據(jù)極值的必要條件根據(jù)極值的必要條件： 211320dp xA xxB xxCdx121/ 2,03,03xCBAxBBACxAA 212620d p xA xxBdx22232230BBACBBAC 當(dāng)當(dāng) 時(shí)，將極值點(diǎn)方程帶入上式時(shí)，將極值點(diǎn)方程帶入上式0A僅取正號(hào)，即僅取正號(hào)，即Page 52123CxxBBAC當(dāng)當(dāng) 時(shí)，將極值點(diǎn)方程帶入上式得時(shí)，將極值點(diǎn)方程帶入上式得 ，0B0A12CxxB此時(shí)此時(shí)21123,(0)33BBACCxxxAABBAC當(dāng)當(dāng) 時(shí)時(shí)0A無(wú)論無(wú)論A是否為零，綜合起來(lái)可得是否為零，綜合起來(lái)可得21212132121212122111()()() -