1、黃金分割法的優(yōu)化問題(1) 黃金分割法基本思路：黃金分割法適用于a,b區(qū)間上的任何單股函數(shù)求極小值問題，對(duì)函數(shù)除要求“單谷”外不做其他要求，甚至可以不連續(xù)。因此，這種方法的適應(yīng)面非常廣。黃金分割法也是建立在區(qū)間消去法原理基礎(chǔ)上的試探方法，即在搜索區(qū)間a，b內(nèi)適當(dāng)插入兩點(diǎn)al,a2,并計(jì)算其函數(shù)值。al,a2將區(qū)間分成三段，應(yīng)用函數(shù)的單谷性質(zhì)，通過函數(shù)值大小的比較，刪去其中一段，是搜索區(qū)間得以縮小。然后再在保留下來的區(qū)間上作同樣的處理，如此迭代下去，是搜索區(qū)間無限縮小，從而得到極小點(diǎn)的數(shù)值近似解。(2) 黃金分割法的基本原理一維搜索是解函數(shù)極小值的方法之一，其解法思想為沿某一已知方向求目標(biāo)函數(shù)的

2、極小值點(diǎn)。一維搜索的解法很多，這里主要采用黃金分割法(0.618法)。該方法用不變的區(qū)間縮短率0.618代替斐波那契法每次不同的縮短率，從而可以看成是斐波那契法的近似，實(shí)現(xiàn)起來比較容易，也易于人們所接受。黃金分割法是用于一元函數(shù)f(x)在給定初始區(qū)間a,b內(nèi)搜索極小點(diǎn)a*的一種方法。它是優(yōu)化計(jì)算中的經(jīng)典算法，以算法簡單、收斂速度均勻、效果較好而著稱，是許多優(yōu)化算法的基礎(chǔ)，但它只適用于一維區(qū)間上的凸函數(shù)，即只在單峰區(qū)間內(nèi)才能進(jìn)行一維尋優(yōu)，其收斂效率較低。其基本原理是：依照去劣存優(yōu)”原則、對(duì)稱原則、以及等比收縮原則來逐步縮小搜索區(qū)間。具體步驟是：在區(qū)間a,b內(nèi)取點(diǎn)：al，a2把a(bǔ),b分為三段。如果

3、f(a1)>f(a2)，令a=a1,a1=a2,a2=a+r*(b-a)如果f(a1)<f(a2)，令b=a2，a2=a1,a1=b-r*(b-a)如果|(b-a)/b|和|(y1-y2)/y2|都大于收斂精度s重新開始。因?yàn)閍,b為單峰區(qū)間，這樣每次可將搜索區(qū)間縮小0.618倍或0.382倍，處理后的區(qū)間都將包含極小點(diǎn)的區(qū)間縮小，然后在保留下來的區(qū)間上作同樣的處理，如此迭代下去，將使搜索區(qū)a,b逐步縮小，直到滿足預(yù)先給定的精度時(shí)，即獲得一維優(yōu)化問題的近似最優(yōu)解。黃金分割法原理如圖1所示，(3) 程序流程如下:4實(shí)驗(yàn)所編程序框圖yf給定a=-3,b=5收斂精度&=0.001

4、是否a1=b-r*#ineludemath.h#definef(x)x*x+#ineludestdio.hy1>=y22*x-0=0.618y1=f(a1)a2=a+H*(M)/bI<2=f(a2)J(y2-y1)/y2I<doublkxXg2y1=y2a2=a1y2=y1doubQ嚴(yán)砌ble*a,double*b,doub|ee,inb衛(wèi)if(fabsa1=b-r*(b-a)y1=f(a1)a2=a+r*(b-a)s=f(*b+*a)/2)2=f(a2)elsex1=*b-0.618*(*b-*a);x2=*a+0.618*(*b-*a);*a=x1;else*b=x2;*

5、n=*n+1;s=calc(a,b,e,n);returns;main()doubles,a,b,e;intn=0;scanf("%lf%lf%lf",&a,&b,&e);s=calc(&a,&b,e，&n);printf("a=%lf,b=%lf,s=%lf,n=%dn",a,b,s,n);5程序運(yùn)行結(jié)果如下圖：2進(jìn)退法(1)算法原理進(jìn)退法是用來確定搜索區(qū)間(包含極小值點(diǎn)的區(qū)間)的算法，其理論依據(jù)是：f(x)為單谷函數(shù)(只有一個(gè)極值點(diǎn))，且a,b為其極小值點(diǎn)的一個(gè)搜索區(qū)間，對(duì)于任意X1,x2a,b，如果f

6、x1fX2，則舊兀為極小值的搜索區(qū)間，如果f捲fx.，則x為極小值的搜索區(qū)間。因此，在給定初始點(diǎn)X。，及初始搜索步長h的情況下，首先以初始步長向前搜索一步，計(jì)算fX。h。（1）如果fXo:fXoh則可知搜索區(qū)間為X,Xoh，其中X待求，為確定X，后退一步計(jì)算f（Xo-，h），為縮小系數(shù)，且0：1，直接找到合適的*，使得f（X*h）fXo，從而確定搜索區(qū)間Xo-叮h,Xoh。（2）如果fXofXoh則可知搜索區(qū)間為Xo,X，其中X待求，為確定X，前進(jìn)一步計(jì)算f（X-h），為放大系數(shù)，且1，知道找到合適的*，使得fxoh:f（xo'*h），從而確定搜索區(qū)間*Xo,Xo+九h。進(jìn)退法求極值基

7、本思想：對(duì)f（X）任選一個(gè)初始點(diǎn)X1及初始步長ho，通過比較這兩點(diǎn)函數(shù)值的大小，確定第三點(diǎn)位置，比較這三點(diǎn)的函數(shù)值大小，確定是否為“高一低一高”形態(tài)。算法原理1. 試探搜索：選定初始點(diǎn)X1,X2=Xi+ho，計(jì)算yi=f（x"，y2=f（X2）（a）如yi>y2,轉(zhuǎn)2向右前進(jìn)；b）如yi<y2,轉(zhuǎn)3向左后退；圖8.12. 前進(jìn)搜索加大步長h=2h，產(chǎn)生新點(diǎn)X3=X2+2ho;a）如y2<y3,則函數(shù)在Xi，X3內(nèi)必有極小點(diǎn)，令a=Xi，b=X3搜索區(qū)間為a，b;（b）如y2>ya，令Xi=X2，yi=y2；X2=X3，y2=ya；h=2h重新構(gòu)造新點(diǎn)X3=X2

8、+h，并比較y2、y3的大小，直到z<y圖8.23. 后退搜索令h=-ho，令X3=Xi，y3=yi；xi=X2，屮；X2=X3，甘屮；h=2h；產(chǎn)生新點(diǎn)X3=x2+h；（a）如y2<y3，則函數(shù)在xi，X3內(nèi)必有極小點(diǎn)，令a=X3，b=Xi，搜索區(qū)間為a，b（b）女口y2>ya，令xi=X2，yi=y2；X2=X3，y2=ya；h=2h重新構(gòu)造新點(diǎn)X3=X2+h,并比較y2、y3的大小，直到y(tǒng)%令a=Xi,b=x3,搜索區(qū)間為a,b;圖8.3（2）算法步驟用進(jìn)退法求一維無約束問題minf（x）,xR的搜索區(qū)間（包含極小值點(diǎn)的區(qū)間）的基本算法步驟如下：（1）給定初始點(diǎn)x（0）

9、，初始步長ho，令h=h°，x二x（0），k=0；（2）令x=xh，置k=k1；（3）若f（x（4）£f（x），則轉(zhuǎn)步驟（4），否則轉(zhuǎn)步驟（5）；（4）令x（2）=xx二x，fx（2）二fx（1），fx二fx（4），令h=2h，轉(zhuǎn)步驟（2）；（5）若k-1，則轉(zhuǎn)步驟（6）否則轉(zhuǎn)步驟（7）;（6）令h=-h，x二x，fx（2）=fx，轉(zhuǎn)步驟（2）；（7）令x（3）=x（2）,x=x（1）,x=x（4），停止計(jì)算，極小值點(diǎn)包含于區(qū)間xx或x，x（3）算法的MATLAB實(shí)現(xiàn)在MATLAB中編程實(shí)現(xiàn)的進(jìn)退函數(shù)為：minJT功能：用進(jìn)退法求解一維函數(shù)的極值區(qū)間。調(diào)用格式：minx,m

10、axx二minJT（f,x0,h0,eps）其中，f:目標(biāo)函數(shù)；x0:初始點(diǎn)；h0:初始步長；eps精度；miix:目標(biāo)函數(shù)取包含極值的區(qū)間左端點(diǎn)；maxx:目標(biāo)函數(shù)取包含極值的區(qū)間又端點(diǎn)。進(jìn)退法的MATLAE程序代碼如下：functionminx,maxx=minJT（f,x0,h0,eps）%目標(biāo)函數(shù):f;%初始點(diǎn):x0;%初始步長:h0;%精度:eps;%目標(biāo)函數(shù)取包含極值的區(qū)間左端點(diǎn)：minx;%目標(biāo)函數(shù)取包含極值的區(qū)間又端點(diǎn)：maxx;formatlong;ifnargin=3eps=1.0e-6;endx1=x0;k=0;h=h0;while1x4=x1+h;%試探步k=k+1;f4=subs(f,findsym(f),x4);f1=subs(f,findsym(f),x1);iff