最优化马昌凤第五章作业

最优化方法及其Matlab程序设计习题作业暨实验报告学院：数学与信息科学学院班级：12级信计一班姓名：李明学号：1201214049第四章共轭梯度法一、上机问题与求解过程1、用DFP算法求解,3)(min2221xxxf取初始点和初始矩阵为.1112,1100Hx。解：仿照书上编写DFP程序，将程序HESS矩阵变为0H具体如下：function[x,val,k]=dfp(fun,gfun,x0)%功能：用DFP算法求解吴宇舒问题：minf(x)%输入：x0是初始点，fun,gfun分别是目标函数及其梯度%输出：x,val分别是近似最优点和最优值，k是迭代次数maxk=1e5;%给出最大迭代次数rho=0.55;sigma=0.4;epsilon=1e-5;k=0;n=length(x0);Hk=[21;11];while(kmaxk)gk=feval(gfun,x0);%计算梯度if(norm(gk)epsilon),break;enddk=-Hk*gk;%计算搜索方向m=0;mk=0;while(m20)%用Armijo搜索求步长if(feval(fun,x0+rho^m*dk)feval(fun,x0)+sigma*rho^m*gk'*dk)mk=m;break;endm=m+1;endx=x0+rho^mk*dk;sk=x-x0;yk=feval(gfun,x)-gk;if(sk'*yk0)Hk=Hk-(Hk*yk*yk'*Hk)/(yk'*Hk*yk)+(sk*sk')/(sk'*yk);endk=k+1;x0=x;endval=feval(fun,x0);然后仿照书上建立两个目标函数和梯度的M文件：functionf=fun(x)f=x(1)^2+3*x(2)^2;functiong=gfun(x)g=[2*x(1)6*x(2)]';选取初始点为']1,1[，调用函数程序，得出最小极值点为'66]101599.0,102203.0[，极小值为13102527.1，在界面框中输入的程序如下：x0=[1-1]';[x,val,k]=dfp('fun','gfun',x0)x=1.0e-06*-0.2203-0.1599val=1.2527e-13k=4从结果可以看出迭代次数为4次，如果选取不同的初值点则迭代次数不一样，但是极小值相同。2、用BFGS算法求222121)(xxxxxf的极小点，选取初始点为Tx)2,3(0解：仿照书上编写BFGS程序具体如下：function[x,val,k]=bfgs(fun,gfun,x0,varargin)%功能：用BFGS算法求解无约束问题：minf(x)；%输入：x0是初始点，fun,gfun分别是目标函数及梯度；%varargin是输入的可变参数变量，简单调用bfgs时可以忽略它；%但若其他程序循环调用该程序时将会发生重要的作用%输出：x,val分别为近似最优点和最优值，k是迭代次数maxk=500;rho=0.55;sigma=0.4;epsilon=1e-5;k=0;n=length(x0);Bk=eye(n);while(kmaxk)gk=feval(gfun,x0,varargin{:});if(norm(gk)epsilon),break;enddk=-Bk\gk;%解方程组，计算搜索方向m=0;mk=0;while(m20)%用Armijo搜索求步长newf=feval(fun,x0+rho^m*dk,varargin{:});oldf=feval(fun,x0,varargin{:});if(newfoldf+sigma*rho^m*gk'*dk)mk=m;break;endm=m+1;end%BFGS校正x=x0+rho^mk*dk;sk=x-x0;yk=feval(gfun,x,varargin{:})-gk;if(yk'*sk0)Bk=Bk-(Bk*sk*sk'*Bk)/(sk'*Bk*sk)+(yk*yk')/(yk'*sk);endk=k+1;x0=x;endval=feval(fun,x0,varargin{:});%在一开始的时候输入格式有错误为：[x,val,k]=bfgs(‘fun’,‘gfun’,x0,varargin)%后来改为[x,val,k]=bfgs(fun,gfun,x0)得出正确答案建立两个目标函数和梯度的M文件：functionf=fun(x)f=x(1)^2+x(2)^2+x(1)*x(2);functiong=gfun(x)g=[2*x(1)+x(2)2*x(2)+x(1)]';选取初始点为']2,3[，调用函数程序，得出最小极值点为'55]105555.1,100513.0[，极小值为6108846.1，在界面框中输入的命令如下：x0=[32]';[x,val,k]=bfgs('fun','gfun',x0)x=1.0e-05*0.0513-0.1555val=1.8846e-12k=3从结果可以看出迭代次数为3次，如果选取不同的初值点则迭代次数不一样，但是极小值相同。3、分别利用BFGS算法和DFP算法的Matlab程序求解下列优化问题,33)(min)1(2112221xxxxxxf取;)0,0(0Tx,)(5)1(4)(min)2(221221xxxxf取;)0,2(0Tx解：（1）BFGS算法解题与前面程序相同，编写不同的函数文件，如下：functionf=fun(x)f=x(1)^2+x(2)^2-3*x(1)-x(1)*x(2)+3;functiong=gfun(x)g=[2*x(1)-x(2)-32*x(2)-x(1)]';在窗口中输入命令并得出结果：x0=[00]';[x,val,k]=bfgs('fun','gfun',x0)x=2.00001.0000val=3.4737e-12k=4由输入的命令与现实的结果可以知道，极小值点为]1,2[，迭代的次数为4次。DFP算法解题：在上面计算的基础之上，添加函数文件，调用第一题程序：functionHe=Hess(x)He=[2,-1;-1,2];在窗口中输入命令并得出结果：x0=[00]';[x,val,k]=dfp('fun','gfun',x0)x=21val=0k=1由输入的命令与现实的结果可以知道，极小值点为]1,2[，迭代的次数为1次。（2）BFGS算法解题与前面程序相同，编写不同的函数文件，如下：functionf=fun(x)f=4*(1-x(1))^2+5*(x(2)-x(1)^2);functiong=gfun(x)g=[-8*(1-x(1))-10*x(1)*(x(2)-x(1)^2)10*(x(2)-x(1)^2)]';在窗口中输入命令并得出结果：x0=[20]';[x,val,k]=bfgs('fun','gfun',x0)x=1.00001.0000val=-1.6236e-06k=31由输入的命令与现实的结果可以知道，极小值点为]1,1[，迭代的次数为31次。DFP算法解题：在上面计算的基础之上，添加函数文件，调用第一题程序：functionHe=Hess(x)He=[8-10*(x(2)-x(1)^2)+20*x(1),-10*x(1);-10*x(1),10];在窗口中输入命令并得出结果：x0=[20]';[x,val,k]=dfp('fun','gfun',x0)x=1.00001.0000val=1.7009e-07k=18由输入的命令与现实的结果可以知道，极小值点为]1,1[，迭代的次数为18次。4、分别利用BFGS算法和DFP算法的Matlab程序求Powell奇异函数的极小值：,)(10)2()10(5)10()(min241232243221xxxxxxxxxf初始点取为Tx)1,0,1,3(0。解：BFGS算法解题与前面程序相同，编写不同的函数文件，如下：functionf=fun(x)f=(x(1)+10*x(2))^2+5*(x(3)-10*x(4))^2+(x(2)-2*x(3))^2+10*(x(1)-x(4))^2;functiong=gfun(x)g=[20*(x(1)+10*x(2))+20*(x(1)-x(4))20*(x(1)+10*x(2))+2*(x(2)-2*x(3))10*(x(3)-10*x(4))-4*(x(2)-2*x(3))-100*(x(3)-10*x(4))-20*(x(1)-x(4))]';在窗口中输入命令并得出结果：x0=[3,-1,0,1]';[x,val,k]=bfgs('fun','gfun',x0)x=1.0e-08*-0.00620.01310.44650.0432val=8.1534e-17k=13由输入的命令与现实的结果可以知道，极小值点为]100432.0,104465.0,100131.0,100062.0[8888，迭代的次数为13次。DFP算法解题：在上面计算的基础之上，添加Hess矩阵文件，functionHe=Hess(x)n=length(x);He=zeros(n,n);He=[40,20,0,-20;20,202,-4,0;0,-4,18,-100;-20,0,-100,1020];调用第一题程序。由输入的命令与现实的结果可以知道，极小值点为]0,0,0,0[。二、实验结果与心得通过上机作四道题可以发现使用拟牛顿法求解问题，DFP方法需要Hess矩阵比较麻烦，但是计算结果精确程度较高，收敛速度快。迭代次数少。而BFGS方法不需要Hess矩阵，初始矩阵为单位矩阵，但是迭代速度慢。在做第四题的时候用DFP方法计算速度较快，但结果明显不精确到真实值。