黃金分割法,進退法,基礎原理及經(jīng)過流程圖

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

2、沿某一已知方向 求目標函數(shù)的極小值點。一維搜索的解法很多，這里主要采用黃金分 割法(0.618法)。該方法用不變的區(qū)間縮短率 0.618代替斐波那契 法每次不同的縮短率，從而可以看成是斐波那契法的近似， 實現(xiàn)起來 比較容易，也易于人們所接受。rl=a+0,382(>-a) r2=a+0,618Cb-a) 如圖班2戶母4) 所以新區(qū)間為a ,于2以為新區(qū)間，繼域求新的試點黃金分割法是用于一元函數(shù)f(x)在給定初始區(qū)間a,b內(nèi)搜索極 小點* *的一種方法。它是優(yōu)化計算中的經(jīng)典算法，以算法簡單、收 斂速度均勻、效果較好而著稱，是許多優(yōu)化算法的基礎，但它只適用 于一維區(qū)間上的凸函數(shù)6,即只在單峰

3、區(qū)間內(nèi)才能進行一維尋優(yōu)，其 收斂效率較低。其基本原理是：依照“去劣存優(yōu)”原則、對稱原則、 以及等比收縮原則來逐步縮小搜索區(qū)間7。具體步驟是：在區(qū)間a,b 內(nèi)取點：al , a2把a,b分為三段。如果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| 都大于收斂精度e重新開始。因為a,b為單峰區(qū)間，這樣每次可將搜索區(qū)間 縮小0.618倍或0.382倍，處理后的區(qū)間都將包含極小點的區(qū)間縮小， 然后在保留下來的區(qū)間上作同

4、樣的處理，如此迭代下去，將使搜索區(qū)a,b逐步縮小，直到滿足預先給定的精度時，即獲得一維優(yōu)化問題 的近似最優(yōu)解。黃金分割法原理如圖1所示，(3)程序流程如下:*4實驗所編程序框圖結(jié)束#include math.h#include «stdio.h»#define f(x) x*x+2*xdouble calc(double *a,double *b,double e,int *n) double x1,x2,s;if(fabs(*b-*a)<=e)s=f(*b+*a)/2);else x1=*b-0.618*(*b-*a);x2=*a+0.618*(*b-*a);if(

5、f(x1)>f(x2)*a=x1;else*b=x2;*n=*n+1;s=calc(a,b,e,n);return s;main() double s,a,b,e;int n=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程序運行結(jié)果如下圖:2進退法（1）算法原理進退法是用來確定搜索區(qū)間（包含極小值點白區(qū)間）的算法，其理論依據(jù)是：f（x）為單谷函數(shù)（只有一個極值

6、點），且a,b為其極小值點的一個搜索區(qū)間，對于任意xla,b,如果f k fX2，則a, X2為極小值的搜索區(qū)間，如果fxifX2,則xi,b為極小值的搜索區(qū)間。因此，在給定初始點xo,及初始搜索步長h的情況下，首先以初始步長向前搜索一步，計算f x0 h。(1)如果 f x0f x0 h則可知搜索區(qū)間為%x0 h,其中%寺求，為確定 %后退一步計算f(x°h),為縮小系數(shù)，且01,直接找到合適的，使得f(xoh) f xo ,從而確定搜* .索區(qū)間xoh, xo h。(2)如果 f % f x0 h則可知搜索區(qū)間為xo,%,其中%寺求，為確定 前進一步計算f (xoh), 為、，a

7、一，、 a 4、一*放大系數(shù)，且 1 ,知道找到合適的，使得f % hf (xoh),從而確定搜索*.區(qū)間xo, %h。進退法求極值基本思想:對f(x)任選一個初始點xi及初始步長ho,通過比較這兩點函數(shù)值的大 小，確定第三點位置，比較這三點的函數(shù)值大小，確定是否為“高一低-高”形態(tài)。 算法原理 1.試探搜索：選定初始點(a)(b)x1, x2= x 1+ ho,計算 y1=f(x1)，y2=f(x2)如y1>y2,轉(zhuǎn)2向右前進；如 y1<y22.前進搜索加大步長 h=2 h ,廣生新點 x3= x2+ 2h o ;*(a)如y2<y3,則函數(shù)在xi,x3內(nèi)必有極小點，令 a

8、=xi,b= x3搜索區(qū)間為a, b;(b)如 y2>y3,令 xi=x2 , y產(chǎn)y2 ；x2=x3 , y2=y3 ； h=2h重新構造新點 x3=x2+h,y2<y3。圖8.23.后退搜索令h = -ho，令x3=x 1產(chǎn)生新點x3= x 2+ h ；(a)如y2<y3,則函數(shù)在為a, b(b)如 y2>y3,y3=yi ； xi=x2 , yi=y2 ；xi, x3內(nèi)必有極小點,x2=x3 , y2=y3 ； h=2h；a= x3, b= x i,搜索區(qū)間令 xi=x2 , yi=y2 ； x2=x3 , y2=y3 ； 重新構造新點x3=x2+h,并比較y2、

9、y3的大小， 搜索區(qū)間為a, b;h=2h直至ij y2<y3。令 a= xi, b= x 3,圖8.3(2)算法步驟用進退法求一維無約束問題min f(x),x R的搜索區(qū)間(包含極小值點的區(qū)間)的基本算法步驟如下：(1) 給定初始點x(0),初始步長ho,令hho, x(i)x(0), k 0 ；(2) 令xxh,置k k 1；(3) 若f xf x，則轉(zhuǎn)步驟(4),否則轉(zhuǎn)步驟(5);(4)令 x(2)x x(1)x(4), f x(2)f x(1) , f x f x(4),令 h 2h,轉(zhuǎn)步驟(2);(5) 若k 1 ,則轉(zhuǎn)步驟(6)否則轉(zhuǎn)步驟(7);(6)令h h, xx，f

10、x f x，轉(zhuǎn)步驟(2)； 令xx，xx，xx，停止計算，極小值點包含于區(qū)間x(1),x(3)或x(3),x(1)(3)算法的MATLAB 實現(xiàn)在MATLAB中編程實現(xiàn)的進退函數(shù)為：min JT功能：用進退法求解一維函數(shù)的極值區(qū)間。調(diào)用格式：min x,max x min JT( f, x0, h0,eps)其中，f :目標函數(shù)；x0：初始點；h0：初始步長；eps :精度；minx：目標函數(shù)取包含極值的區(qū)間左端點； maxx：目標函數(shù)取包含極值的區(qū)間又端點。進退法的MATLAB 程序代碼如下：function minx,maxx=minJT(f,x0,h0,eps)%目標函數(shù)：f;%初始點：x0;%初始步長：h0;%精度:eps;%目標函數(shù)取包含極值的區(qū)間左端點：minx;%目標函數(shù)取包含極值的區(qū)間又端點：maxx;format long;if nargin=3eps=1.0e-6;endx1=x0;k=0;h=h0;while 1x4=x1+h;%試探步k=k+1;f4=subs(f,findsym,x4);f1=subs(f,findsym,x1);