最优化数值实验报告二

最优化数值 实验报告 化学实验报告单总流体力学实验报告观察种子结构实验报告观察种子结构实验报告单观察种子的结构实验报告单 二 实验目的: 1，能够将非线性方程组转化为有约束的问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ，并采用合适的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 进行求解，主要是外惩罚函数和广义乘子法。 2，用MATLAB变成求解问题，并对各种方法的计算过程和结果进行分析。 实验原理:(略) 实验内容: (主要是《最优化练习题022》中的第一题》，结合数值实验一进行比较分析。) 求解下面的方程组 ,3x,cos(xx),1/2,0,123,2(),,81(，0.1)，sin，1.06,0fxxxx ,123 ,1,xx12e，20x，(10,,3),03,3, 把它们转化为有约束的问题，处理的方法有几种: (1) 将第1和第2两个方程平方后相加，作为目标函数，将第3个方程作为约束方程，同样可以转化为有等式约束的问题。 (2) 将第1个方程平方之，作为目标函数，而将另外2个方程作为等式约束。如果我们 来求解在这2个等式约束条件下，最小化目标函数，就构成了一个有约束的最优化问题。 (3) 也可选第3个方程的平方作为目标函数，另外2个方程为约束条件，等等。 但这些问题没有本质区别，在下面我们均以第一种处理方法进行讨论。即求解如下的有约束的问题。 222min((3x,cos(xx),1/2)，(x,81(x，0.1)，sinx，1.06))123123 1,xx12s.t.e，20x，(10,,3),033 但是实际上，上面提到的两种方法的主要思想是借助罚函数将约束问题转化为无约束问题，用无约束的最优化方法求解(下面我们一律选择的是BFGS法，在第一次数值实验中，通过对无约束问题各种求解方法的分析比较，从各个方面的均衡来说，BFGS法是较理想的)。 另外，同第一次数值实验中的一样，在做一维搜索时，用进退法和黄金分割法来实现的，其中进退法确定一个单峰区间，而黄金分割法进行精确的一维搜索。(分别对应程序中的jintuifa.m和gold.m,具体程序见附录)。步长仍然选择为0.0125。(这些和实验一中是一样的，为了保证搜索能够很好的进行。) 1，外点惩罚函数法 外点惩罚函数法就是通过选择罚因子做出辅助的惩罚函数，从而将约束问题转化为无约束问题的求解。罚因子越大，则得到的近似解越接近于实际的最优解。 minf(x)，,P(x), 程序中采用SUMT方法来求解，即从某个开始，求解，从而得到一k1 ,P(x),个满足某种精度的极小点。实验中选取初始为1，放大系数1.5，当<，其中,k1 ,6时候，停止计算。 ,,1*10 程序: syms x1 x2 x3 t r; f1=3*x1-cos(x2*x3)-1/2;f2=x1^2-81*(x2+0.1)+sin(x3)+1.06;f3=exp(-x1*x2)+20*x3+1/3*(10*3.1 4159-3); f=f1^2+f2^2+t*f3^2;p=t*f3^2; x=[x1,x2,x3];xt=[x1,x2,x3,t]; df=jacobian(f,x);df=df.'; error1=1e-6;x0=[0,0,0]';t0=1;c0=1.5;j=0; error2=1e-6;H0=[1,0 0;0,1 0;0 0 1];k=0; g=subs(p,{x1,x2,x3,t},{x0(1),x0(2),x0(3),t0}); g=double(g); while(norm(g)>error1) y=subs(f,t,t0); dy=jacobian(y,x);dy=dy.'; g1=subs(dy,x,x0);double(g1); while(norm(g1)>error2) %下面为BFGS方法求解无约束的问题 if k==0 d=-H0*g1; else H1=H0+(1+qk'*H0*qk/(pk'*qk))*(pk*pk')/(pk'*qk)-(pk*qk'*H0+H0*qk*pk')/(pk'*qk); d=-H1*g1;H0=H1; end z=subs(y,x,x0+r*d); result=jintuifa(z,r); result2=gold(z,r,result); step=result2; x0=x0+step*d; g0=g1;g1=subs(dy,x,x0); qk=g1-g0; pk=step*d; k=k+1; end j=j+1; t0=t0*c0; g=subs(p,{x1,x2,x3,t},{x0(1),x0(2),x0(3),t0}); g=double(g); end x0 k j t0 g min=subs(f1^2+f2^2,[x1 x2 x3],x0) 结果: 由此方法得到的最优解为(0.4996，-0.0900，-0.5259)，迭代的次数为1，。取得的最优值为8.6570e-020。这是因为从BFGS方法求得的最优解已经精度非常高了，所以迭代次数很少。但是我们若是令初始的为100，则得到的最优解(0.4996，-0.0900，-0.5259)(实,1 际上得到的最优解和,取1时候得到的最优解是不同的，为了方便起见，小数点后面只取了1 4位有效数字。实际上若是取long的输出，得到的结果为分别为(0.49962645883917，-0.09002918391617，-0.52589873064733)和(0.49962645881558，-0.09002918391288，-0.52589873064255)，两者显然是不同的，而后者更接近真实的最优解)，最优值为1.0858e-026，显然，惩罚因子越大，得到的值越接近真实的最优值。 但是惩罚函数法的缺点也很明显，要取得足够精确的解就要保证惩罚因子足够大，这样就会给我们的极小化带来很大的困难。 2，广义乘子法 罚函数法方法很简单，也能够求解导数不存在的问题，因此应用很广泛。但是它的取点也是不容忽视的，就是随着罚因子趋向极限，罚函数的Hesse矩阵的条件数无限增大，因此变得越来越病态，广义乘子法就是为了克服罚函数的这个形态而提出的。下面我们将对其作具体的分析。 广义乘子法与罚函数的区别在于增加了乘子项，这样得到的增广拉格朗日函数与拉格朗日和罚函数的性能均不同。只要惩罚因子取得合适值，不必趋向于无穷大。就可以得到比较理想的值。 下面的步骤中，我们就可以看到它为什么可以抑制罚因子的无限增大。 乘子法的计算步骤: (0)(1),,1(1)给定初始点，乘子向量初始估计，参数，允许误差，常数 ,xv,,0 ,,(0,1),k,1和。 (k,1)x(2)以为初点，解无约束问题 (k)min,(x,v,,) (k) 解得。 x (k)(k)(3)若，则停止计算，得到点;否则进行步骤4。 xh(x),, (4)若 (k)h(x) ,,(k,1)h(x) 则置，转步骤5;否则，进行步骤。 ,,,, k，1(5)计算(j=1,2,…l)，置k=k+1,转步骤2。 vj 我们看到，乘子法提供了一种策略，当满足一定条件时，不必增大,，就可以继续寻找最优解，这也是它最好的地方。 ,6,,,0.5实验中选取初始为1，放大系数1.5，允许误差为时候，，乘子向量1*101 初始估计为1; 程序: syms x1 x2 x3 t v; f1=3*x1-cos(x2*x3)-1/2;f2=x1^2-81*(x2+0.1)+sin(x3)+1.06;f3=exp(-x1*x2)+20*x 3+1/3*(10*pi-3); f=f1^2+f2^2+0.5*t*f3^2-v*f3; x=[x1,x2,x3]; error1=1e-6;x0=[0，0，0]';t0=1;c0=1.5;v0=1;j=0;beta=0.5; error2=1e-6;H0=[1,0 0;0,1 0;0 0 1];k=0; h0=subs(f3,{x1,x2,x3},{x0(1),x0(2),x0(3)}); h0=double(h0); while(norm(h0)>error1) y=subs(f,{t,v},{t0,v0}); dy=jacobian(y,x);dy=dy.'; g1=subs(dy,x,x0);double(g1); while(norm(g1)>error2) %下面为BFGS方法求解无约束的问题 if k==0 d=-H0*g1; else H1=H0+(1+qk'*H0*qk/(pk'*qk))*(pk*pk')/(pk'*qk)-(pk*qk'*H0+H0*qk*pk' )/(pk'*qk); d=-H1*g1;H0=H1; end z=subs(y,x,x0+r*d); result=jintuifa(z,r); result2=gold(z,r,result); step=result2; x0=x0+step*d;g0=g1; g1=subs(dy,x,x0);double(g1); qk=g1-g0; pk=step*d; k=k+1; end x0 h1=subs(f3,{x1,x2,x3},{x0(1),x0(2),x0(3)});h1=double(h1); if norm(h1)>=beta*norm(h0) t0=t0*c0; end v0=v0-t0*h1; h0=h1; j=j+1; end x0 k j t0 min=subs(f1^2+f2^2,[x1 x2 x3],x0) 结果: MATLAB计算得到的最优解为(0.4996，-0.0900，-0.5259)，最优值为8.3369e-022，做了两次迭代，但是最后得到的惩罚因子并没有扩大，仍然为1，这就是广义乘子法的功劳。而且我们可以看出，在惩罚因子不变的情况下，广义乘子法得到的最优值要好于惩罚函数法，前者在惩罚因子为1时，得到的最优值为8.6570e-020，这正是所希望看到的。 另外，广义乘子法是罚函数方法和拉格朗日乘子法的综合。若是在程序中令v=0，则得到的就是罚函数法;若是令=0,就可以得到，一般的拉格朗日的表达式。罚函数的性能我, 们在上面已经研究过了，在实验中我们可以借助广义拉格朗日乘子法，对于一般的拉格朗日乘子法进行了研究，发现在用MATLAB求解的时候，收敛速度很慢，而且BFGS法经常出现除数为0的情况，导致情况出错。从这点上来说，广义乘子法要比一般乘子法要很多。所以说，这三种方法，广义乘子法是最优的。 实验结论: 在这次实验中，主要就惩罚函数法和广义乘子法进行了实验分析，得出了广义乘子法优于一般乘子法和惩罚函数法的结论，实验结果也证明了这一点。另外，在解得过程中对无约束问题的方法的选择很重要，这里经过权衡选择的是BFGS方法，不过它仍然有不足的地方，就是由于计算误差的产生，会导致除数为零的情况发生，这时候就会导致计算无法进行下去，这时候就要考虑其它的方法了。 在实验一中，我们对于同样的方程组，给出了将它写成最小二乘模型，然后用各种不同的无约束的最优化问题进行求解的方法，并对不同的方法进行比较。在这儿，对于同样的方程组，采用了一种不同的处理方法，即首先将它表示成约束的最优化问题，然后通过惩罚函数法或者是广义乘子法来进行求解。实际上，在这两种方法中，我们都是通过将有约束的问题进行转化成为无约束的问题，然后来进行对其求解，同时，这也是求解最优化问题的最常见的一种思路，我们总是希望将约束的问题转化成一定区间上的无约束的问题，然后再通过计算机或者其它的工具来处理。所以说，对无约束问题的求解是最优化的基础。 附录 进退法确定一维搜索区间 function result=jintuifa(y,r) t0=0; step=0.0125; t1=t0+step; ft0=subs(y,{r},{t0});ft1=subs(y,{r},{t1}); if(ft1<=ft0) step=2*step;t2=t1+step;ft2=subs(y,{r},{t2}); while(ft1>ft2) t1=t2;step=2*step;t2=t1+step;ft1=subs(y,{r},{t1});ft2=subs(y,{r},{t2}); end else step=step/2;t2=t1;t1=t2-step;ft1=subs(y,{r},{t1}); while(ft1>ft0) step=step/2;t2=t1;t1=t2-step;ft1=subs(y,{r},{t1}); end end result=[t2]; 黄金分割法进行一维搜索 function result=gold(y,r,m) a=0;b=m;e=1e-5;a1=a+0.382*(b-a);f1=subs(y,{r},{a1});a2=a+0.618*(b-a);f2=subs(y,{r},{a2}); while abs(b-a)>=e if f1