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

2、極小值點。一維搜索的解法很多，這里主要采用黃金分割法（0.618法）。該方法用不變的區間縮短率0.618代替斐波那契法每次不同的縮短率，從而可以看成是斐波那契法的近似，實現起來比較容易，也易于人們所接受。 黃金分割法是用于一元函數f(x)在給定初始區間a,b內搜索極小點*的一種方法。它是優化計算中的經典算法，以算法簡單、收斂速度均勻、效果較好而著稱，是許多優化算法的基礎，但它只適用于一維區間上的凸函數6，即只在單峰區間內才能進行一維尋優，其收斂效率較低。其基本原理是：依照“去劣存優”原則、對稱原則、以及等比收縮原則來逐步縮小搜索區間7。具體步驟是：在區間a,b內取點：a1 ，a2 把a,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都大于收斂精度重新開始。因為a,b為單峰區間，這樣每次可將搜索區間縮小0.618倍或0.382倍，處理后的區間都將包含極小點的區間縮小，然后在保留下來的區間上作同樣的處理，如此迭代下去，將使搜索區a,b逐步縮小，直到滿足預先給定的精度時，即獲得一維優化問題的近似最優解。黃金分割法原理如圖所示， （3） 程序流程如下：4 實驗所編程序框圖開始r=0.618給定a=-3,b=5,收斂精

4、度=0.001結束a*=(a+b)/2a1=b-r*(b-a)y1=f(a1)b=a2a2=a1 y2=y1a2=a+r*(b-a)y2=f(a2)a=a1a1=a2 y1=y2y1>=y2a1=b-r*(b-a) y1=f(a1)a2=a+r*(b-a) y2=f(a2)否是(b-a)/b<和 （y2-y1）/y2<?否是#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

5、-*a)<=e) s=f(*b+*a)/2); else x1=*b-0.618*(*b-*a); x2=*a+0.618*(*b-*a); if(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

6、",a,b,s,n); 5 程序運行結果如下圖：2進退法 （1）算法原理進退法是用來確定搜索區間（包含極小值點的區間）的算法，其理論依據是：為單谷函數（只有一個極值點），且為其極小值點的一個搜索區間，對于任意，如果，則為極小值的搜索區間，如果，則為極小值的搜索區間。因此，在給定初始點，及初始搜索步長的情況下，首先以初始步長向前搜索一步，計算。（1） 如果則可知搜索區間為，其中待求，為確定，后退一步計算，為縮小系數，且，直接找到合適的，使得，從而確定搜索區間。（2） 如果則可知搜索區間為，其中待求，為確定，前進一步計算，為放大系數，且，知道找到合適的，使得，從而確定搜索區間。進退法求極

7、值基本思想： 對f(x)任選一個初始點x1及初始步長h0， 通過比較這兩點函數值的大小，確定第三點位置，比較這三點的函數值大小，確定是否為 “高低高” 形態。算法原理1.試探搜索： 選定初始點x1, x2= x1+ h0，計算 y1f(x1)， y2f(x2) （a）如y1>y2,轉2向右前進； （b）如y1<y2, 轉3向左后退；圖8.12.前進搜索 加大步長 h2 h ，產生新點x3= x2+ 2h0 ；（a）如y2<y3，則函數在x1，x3內必有極小點，令a= x1，b= x3搜索區間為a，b ；(b)如y2>y3， 令x1=x2 ，y1=y2 ； x2=x3 ，

8、y2=y3 ； h=2h 重新構造新點x3=x2+h，并比較y2、y3的大小，直到y2<y3。 圖8.23.后退搜索 令 h-h0 ，令x3=x1 ，y3=y1 ；x1=x2 ，y1=y2 ；x2=x3 ，y2=y3 ；h=2h；產生新點x3= x2+ h ； （a）如y2<y3，則函數在x1，x3內必有極小點，令a= x3，b= x1，搜索區間為a，b （b）如y2>y3， 令x1=x2 ，y1=y2 ； x2=x3 ，y2=y3 ；h=2h重新構造新點x3=x2+h，并比較y2、y3的大小，直到y2<y3。令a= x1，b= x3，搜索區間為a，b ； 圖8.3（2

9、）算法步驟用進退法求一維無約束問題的搜索區間（包含極小值點的區間）的基本算法步驟如下：（1） 給定初始點，初始步長，令，；（2） 令，置；（3） 若，則轉步驟（4），否則轉步驟（5）；（4） 令，令，轉步驟（2）；（5） 若，則轉步驟（6）否則轉步驟（7）；（6） 令，轉步驟（2）；（7） 令，停止計算，極小值點包含于區間（3）算法的MATLAB實現在MATLAB中編程實現的進退函數為：功能：用進退法求解一維函數的極值區間。調用格式：其中，：目標函數； ：初始點； ：初始步長； ：精度； ：目標函數取包含極值的區間左端點； ：目標函數取包含極值的區間又端點。進退法的MATLAB程序代碼如下：function minx,maxx=minJT(f,x0,h0,eps)%目標函數:f;%初始點:x0;%初始步長:h0;%精度:eps;%目標函數取包含極值的區間左端點:minx;%目標函數取包含極值的區間又端點:maxx;format long;if nargin=3 eps=1.0e-6;endx1=x0;k=0;h=h0;while 1 x4=x1+h; %試探步 k=k+1; f4=subs(f,findsym(f),x4); f1=subs(f,findsym(f),x1); if f4<f1 x2=x1; x1=x4; f2=