1、擬牛頓算法一、算法流程圖/算法步驟1、DFP算法：(1)算法步驟：步0給定參數3 G (0,1), a e (0.0.5).初始點期W Rn.終止法是。二eL 初始對稱正定陣冊(通常取為Gg尸取單位陣人).令k ：= 0.步1計算血=若弧| W 3停算，-揄出外 作為近似極小點.步2計算搜索方向；dk = HkOz步3設是滿足下列不等式的最小非由整數7加4一 出)W+仃6看(杰，令以=/，網+i =以+步4由校正公式|確定+步5令/：=A + 1, 轉步1 一2、BFGS算法(1)算法步驟：步0給定參數臺 (0,1).仃W (0：0.5),初始點出 睡2終止誤呈0L初始對母正定陣& (通常取為

2、G(工o)或單位陣ZJ.令/； ：= 0.步1計算9k = V7(rQ,若|麻| 3,停算.物出以作為近似極小點.步2解性方小組得解烝:步3設m.是滿足下列不等式的馥小非負整鞅m;fa + V4)epsilon)%迭代終止條件 |g1|=epsilonif k=0d=-H0*g1;%負梯度方向elseH1=H0+pk*pk/(qk*pk)-H0*qk*qk*H0/(qk*H0*qk);d=-H1*g1;H0=H1;endz=subs(f,x,x0+r*d); %關于 r 的函數result1=jintuifa(z,r);%進退法求下單峰區間result2= gold(z,r,result1);

3、%黃金分割法求最優步長step=result2;x0=x0+step*d;g0=g1;g1=subs(df,x,x0);%gk=double(gk);qk=g1-g0;pk=step*d;k=k+1;endk%最優點x0min=subs(f,x1 x2,x0)% 最優值toc%進退法求下單峰區間function result= jintuifa(y,r)t0=0;step=0.0125;t1=t0+step;ft0=subs(y,r,t0); %step1 求 f(t0)將函數 y 中變量 x 替換為 t0 ft1=subs(y,r,t1);if (ft1ft2)t1=t2; step=2*s

4、tep;t2=t1+step;ft1=subs(y,r,t1);ft2=subs(y,r,t2);endelse %step5 step6step=step/2;t2=t1;t1=t2-step;ft1=subs(y,r,t1);while(ft1ft0)step=step/2;t2=t1;t1=t2-step;ft1=subs(y,r,t1);endendresult=t2；%黃金分割法求最優步長function result=gold(y,r,m)a=0;b=m;e=1e-5;a1=a+0.382*(b-a); %step1f1=subs(y,r,a1);a2=a+0.618*(b-a);

5、 %step2 f2=subs(y,r,a2); while(abs(b-a)e) if f1f2 %step4 b=a2;a2=a1;f2=f1; a1=a+0.382*(b-a);%轉 step2f1=subs(y,r,a1); elsea=a1;a1=a2;f1=f2;a2=a+0.618*(b-a); %step5 f2=subs(y,r,a2); end end answer=(a+b)/2;%最優的 x 值result=answer;%M 優的函數值2、BFGS算法%擬牛頓法中 BFGS算法求解f=x1*x1+2*x2*x2-2*x1*x2-4*x1的最小值tic format l

6、ong%要最小化的函數%函數f的偏導%起始點的梯度%0.000001為搜索精度|g1|epsilon)% 迭代終止條件if k=0d=-H0*g1;%負梯度方向elseH1=H0+(1+qk*H0*qk/(pk*qk)*(pk*pk)/(pk*qk)-(pk*qk*H0+H0*qk*pk)/(pk*qk); d=-H1*g1;H0=H1;endz=subs(f,x,x0+r*d); %關于 r 的函數result1=jintuifa(z,r);%進退法求下單峰區間result2= gold(z,r,result1);%黃金分割法求最優步長step=result2;x0=x0+step*d;g0

7、=g1; g1=subs(df,x,x0);qk=g1-g0;pk=step*d;k=k+1;end kx0 min=subs(f,x1 x2,x0)% 最優值toc%進退法求下單峰區間function result= jintuifa(y,r)t0=0;step=0.0125;t1=t0+step;ft0=subs(y,r,t0); %step1 求 f(t0)將函數 y 中變量 x 替換為 t0 ft1=subs(y,r,t1);if (ft1ft2)t1=t2; step=2*step;t2=t1+step;ft1=subs(y,r,t1);ft2=subs(y,r,t2);endels

8、e %step5 step6step=step/2;t2=t1;t1=t2-step;ft1=subs(y,r,t1);while(ft1ft0)step=step/2;t2=t1;t1=t2-step;ft1=subs(y,r,t1);endendresult=t2；%黃金分割法求最優步長function result=gold(y,r,m)a=0;b=m;e=1e-5;a1=a+0.382*(b-a);%step1f1=subs(y,r,a1);a2=a+0.618*(b-a);%step2f2=subs(y,r,a2);while(abs(b-a)e)if f1f2 %step4 b=a

9、2;a2=a1;f2=f1;a1=a+0.382*(b-a);%轉 step2f1=subs(y,r,a1);elsea=a1;a1=a2;f1=f2;a2=a+0.618*(b-a); %step5 f2=subs(y,r,a2); end end answer=(a+b)/2;%最優的 x 值result=answer;%最優的函數值3、模式搜索算法function u,I=touzi(m,n,L) for i=1:m+1v(i,n)=L(i,n);w(i,n)=i-1;end for k=n-1:-1:2 for i=1:m+1v(i,k)=0;w(i,k)=i-1; for j=1:i

10、 if v(i,k)L(j,k)+v(i+1-j,k+1)v(i,k)=L(j,k)+v(i+1-j,k+1); w(i,k)=j-1; end end end end v(m+1,1)=0; w(m+1,1)=m; for j=1:m+1if v(m+1,1)DFP方法BFGST法。且收斂的值相對于真實值的精度也是：模式搜索法DFP方法BFGST法。所以，當在真實極值點附近，最好使用模式搜索法，收斂速度快而精確。b、DFP方法的收斂速度和收斂精度要高于BFGS方法。BFGS方法要比DFP方法偏向于真實值。說明當初值點偏離真實點較遠時，BFGS方法有更強的穩定性。五、體會1、通過與牛頓法的比較

11、，以及對 DFP和BPGS算法的編程實現與分析，我發現 Hesse矩陣 在擬牛頓法中是不計算的，擬牛頓法是構造與Hesse矩陣相似的正定矩陣，這個構造方法，使用了目標函數的梯度(一階導數)信息和兩個點的“位移” ( Xk-Xk-1 )來實現。使用 Hesse矩陣 的近似矩陣來代替 Hesse矩陣，不僅不會導致求解效果變差，效果反而會變好。具體來說，擬牛頓法與牛頓法的迭代過程一樣，僅僅是各個Hesse矩陣的求解方法不一樣。在遠離極小值點處，Hesse矩陣一般不能保證正定，使得目標函數值不降反升。而擬牛頓法可以使目標函數值沿下降方向走下去，并且到了最后，在極小值點附近，可使構造出來的矩陣與 Hesse矩陣“很像”，這樣，擬牛頓法也會具有牛頓法的二階收斂性。2、模式搜索是一種很直接的搜索方法，就是設置一定的終止條件，尋找一系列的X。，Xi, X2,，這些點都越來越靠近最優值點，當搜索進行到終止條件時則將最后一個點作 為本次搜索的解。這樣的算法也許會因為終止條件的不同，計算的結果和效率有所差異，但是它省去了更為繁瑣的