多维搜索算法程序

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,，这些点都越来越靠近最优值点，当搜索进行到终止条件时则将最后一个点作 为本次搜索的解。这样的算法也许会因为终止条件的不同，计算的结果和效率有所差异，但是它省去了更为繁琐的