三章一維優(yōu)化方法ppt課件

1、x2x1o (k)S(k)S(k)x(k+1)x(k)x*F(x(k)F(x(k+1) 在一維搜索時(shí)，需要確定一個(gè)搜索區(qū)間a,b，此區(qū)間必須包含函數(shù)的極小點(diǎn) x*，因此搜索區(qū)間必須是單峰區(qū)間，即該區(qū)間內(nèi)的函數(shù)值呈現(xiàn)“高-低-高的趨勢(shì)。如下圖，通過(guò)將搜索區(qū)間a,b逐漸縮小，直至足夠小，就可以得到近似最優(yōu)點(diǎn)。f(x)f(x)xxaax*x*bb一、試探搜索極小點(diǎn)位置一、試探搜索極小點(diǎn)位置 設(shè)函數(shù)為設(shè)函數(shù)為 y=f(x) ,給定初始點(diǎn)為給定初始點(diǎn)為x1 ，選定的，選定的初始步長(zhǎng)為初始步長(zhǎng)為h0。 由初始點(diǎn)由初始點(diǎn)x1沿沿x軸正向取軸正向取x2點(diǎn)，點(diǎn)，x2=x1+h0，計(jì)算計(jì)算x1 、x2的函數(shù)值的函

2、數(shù)值y1 、y2 ，比較，比較y1 、y2 的的大小，則極小點(diǎn)的位置有如圖所示兩種情況大小，則極小點(diǎn)的位置有如圖所示兩種情況 1、若、若y2 y1 ，則極小點(diǎn)位于，則極小點(diǎn)位于x1點(diǎn)左方，應(yīng)點(diǎn)左方，應(yīng)反向后退搜索。反向后退搜索。x1x1x2x2x3x3h02h0h02h0前進(jìn)搜索前進(jìn)搜索后退搜索后退搜索注意：注意：x1x2互換互換后再取后再取x3 x1，b x3，從而構(gòu)成搜索區(qū)間，從而構(gòu)成搜索區(qū)間a,b述比較述比較y2與與y3的大小，直至出現(xiàn)的大小，直至出現(xiàn)y1 y2y3時(shí)，令時(shí)，令a x3，b x1，從而構(gòu)成，從而構(gòu)成搜索區(qū)間搜索區(qū)間a,b96)(2xxxf 由于用y2y1，作前進(jìn)搜索：在比

3、較y2，y3有y2y3，則取 在確定了搜索區(qū)間以后，一維優(yōu)化的任務(wù)是采用某在確定了搜索區(qū)間以后，一維優(yōu)化的任務(wù)是采用某種方法將此區(qū)間逐步縮小，在滿足收斂精度或迭代精度種方法將此區(qū)間逐步縮小，在滿足收斂精度或迭代精度的情況下，使其達(dá)到包含極小點(diǎn)的一個(gè)很小的鄰域，以的情況下，使其達(dá)到包含極小點(diǎn)的一個(gè)很小的鄰域，以取得一個(gè)近似的最優(yōu)點(diǎn)。取得一個(gè)近似的最優(yōu)點(diǎn)。 一維優(yōu)化的方法有如下幾種：一維優(yōu)化的方法有如下幾種： 1、格點(diǎn)法、格點(diǎn)法 2、黃金分割法、黃金分割法 3、二次插值法、二次插值法ym 若不能滿足精度要求，把當(dāng)前區(qū)間作為初始搜索區(qū)若不能滿足精度要求，把當(dāng)前區(qū)間作為初始搜索區(qū)間，重復(fù)上述步驟直至滿

4、足精度為止間，重復(fù)上述步驟直至滿足精度為止kbaxak(k1,2,.,n)n1 新區(qū)間新區(qū)間y1ym-1ymym+1ynx1axm-1xmxm+1xnb+-+-10124)(2xxxfkbaxak(k1,2,.,n)n10016. 12)1( yym48. 1)1(mx區(qū)間縮短次數(shù)xkykxmabb-a第一次1.241.481.721.961.27041.00161.19361.8461.481.241.720.48第二次1.3361.4321.5281.6241.1075841.0184961.0031361.0615041.5281.4321.6240.19224. 11)1(mxa72.

5、 11)1(mxb48. 0)1()1(ab432. 1)2(a624. 1)2(b192. 0)2()2(ab528. 1)2(*mxx003136. 1)()2(*mxff 黃金分割法適用于黃金分割法適用于a,b區(qū)間上的任何單峰函區(qū)間上的任何單峰函數(shù)求極小值問(wèn)題。對(duì)函數(shù)除要求單峰外不作其它數(shù)求極小值問(wèn)題。對(duì)函數(shù)除要求單峰外不作其它要求，甚至可以不連續(xù)。因而，這種方法的適應(yīng)要求，甚至可以不連續(xù)。因而，這種方法的適應(yīng)面相當(dāng)廣。面相當(dāng)廣。一、黃金分割法的原理一、黃金分割法的原理在搜索區(qū)間在搜索區(qū)間a,b內(nèi)適當(dāng)插入兩點(diǎn)內(nèi)適當(dāng)插入兩點(diǎn)x1,x2 ，x1x2,且在區(qū)間內(nèi)對(duì)稱位置，計(jì)算其函數(shù)值。且在區(qū)間

6、內(nèi)對(duì)稱位置，計(jì)算其函數(shù)值。 y1=f(x1) y2=f(x2)1)若若y1y2則極小點(diǎn)必在區(qū)間則極小點(diǎn)必在區(qū)間a,x2內(nèi)，令內(nèi)，令b=x2，新區(qū)間為新區(qū)間為a，x22)若若y1y2則極小點(diǎn)必在區(qū)間則極小點(diǎn)必在區(qū)間x1,b內(nèi)，令內(nèi)，令a=x1，新區(qū)間為新區(qū)間為x1，b經(jīng)過(guò)函數(shù)值比較，區(qū)間縮短一次。新區(qū)間只保留經(jīng)過(guò)函數(shù)值比較，區(qū)間縮短一次。新區(qū)間只保留x1，x2中的一個(gè)。中的一個(gè)。入入口口出出口口y1?x x* *0 0. .5 5( (a a+ +b b) )f f* *f f( (x x* *) )+-+-96)(2xxxfX1=a+0.382(b-a)=3.292 y1=f(x1)=0.08

7、5264X2=a+0.618(b-a)=4.708 y2=f(x2)=2.9172641)1( aa708. 42)1( xb708. 31708. 4)1()1(ab416456. 2)(382. 0)1()1()1(1abax340524. 0)(11xfy750917. 2)6(a085305. 3)6(b334388. 0)6()6(ab91811. 2)(21)6()6(bax00670. 0*)(*xfy 不同點(diǎn)：試驗(yàn)點(diǎn)位置的確定方法不同。不同點(diǎn)：試驗(yàn)點(diǎn)位置的確定方法不同。 在試探法中試驗(yàn)點(diǎn)的位置是由某種給定的規(guī)律確定的，在試探法中試驗(yàn)點(diǎn)的位置是由某種給定的規(guī)律確定的，并未考慮函數(shù)

8、值的分布。并未考慮函數(shù)值的分布。 例如：例如： 黃金分割法是按照等比例黃金分割法是按照等比例0.618縮短率確定的?？s短率確定的。 插值法中，試驗(yàn)點(diǎn)的位置是按函數(shù)值近似分布的極小點(diǎn)確插值法中，試驗(yàn)點(diǎn)的位置是按函數(shù)值近似分布的極小點(diǎn)確定的。定的。 試探法僅僅利用了試驗(yàn)點(diǎn)函數(shù)值進(jìn)行大小的比較，而插值試探法僅僅利用了試驗(yàn)點(diǎn)函數(shù)值進(jìn)行大小的比較，而插值法還要利用函數(shù)值本身或其導(dǎo)數(shù)信息。所以，當(dāng)函數(shù)具有法還要利用函數(shù)值本身或其導(dǎo)數(shù)信息。所以，當(dāng)函數(shù)具有較好的解析性質(zhì)時(shí)，插值方法比試探方法效果更好。較好的解析性質(zhì)時(shí)，插值方法比試探方法效果更好。 計(jì)算函數(shù)值計(jì)算函數(shù)值f 1=f (x1)、 f 2= f (

9、x2)、 f 3= f (x3) 過(guò)函數(shù)曲線上的三點(diǎn)過(guò)函數(shù)曲線上的三點(diǎn)P1(x1 , f 1)、 P2(x2 , f 2)、 P3(x3 , f 3) 作二次插值多項(xiàng)式作二次插值多項(xiàng)式 p(x)=Ax2+Bx+C 它應(yīng)滿足條件它應(yīng)滿足條件 p(x1)=Ax12+Bx1+C 1=f 1 p(x2)=Ax22+Bx2+C = f 2 p(x3)=Ax32+Bx3+C = f 3 解方程組，得待定系數(shù)解方程組，得待定系數(shù)A、B、C分別為分別為 )()()()()(133221321213132xxxxxxfxxfxxfxxA)()()()()(133221322212212312322xxxxxxf

10、xxfxxfxxB)()()()()(133221321122313113223xxxxxxfxxxxfxxxxfxxxxC 于是函數(shù)p(x)就是一個(gè)確定的二次多項(xiàng)式，稱二次插值函數(shù) 如下圖，虛線部分即為二次插值函數(shù)321213132322212212312322*)()()()()()(21fxxfxxfxxfxxfxxfxxxp13131xxffc32112122)/()(xxcxxffc)2131(21*ccxxxP0)/()(32112122xxcxxffc131311212xxffcxxff新區(qū)間新區(qū)間x1=ax2x3=bx*xP*x1x2x3x1x2x3xP*f2fP*x1x1x1x2x2x2xP*xP*xP*x3x3x3f2f2f2fP*fP*fP*bacd入口入口xp*x2?f2fP*?f2y1) h=-h0; x3=x1; x1=x2; x2=x3; y3=y1; y1=y2; y2=y3;for(;) h=2*h; x3=x2+h; y3=f(x3); if(y2y3) break; x1=x2; y1=y2; x2=x3; y2=y3;if(h0) *a=