运筹学第六次实验报告

运筹学第六次实验报告题目：用matlab编程最速下降法SteepestDescent用matlab编程Newton法Newton一、Armijo算法的算法框架：1.给定初始点Rxxn00,，且令k=0；给定方向d;2.给定初始步长，通常取1；3.判断退出条件是否成立，若是则退出，否则执行step4，退出条件：)1,5.0(,)]([)()(11dxxxkTkkkfff，通常9.0；4.dxxkkkkkk1111;,为压缩系数，返回step3。二、最速下降法的算法框架：1.给定初始点Rxxn00,，令k=0；2.判断退出条件是否满足，若是则退出，否则执行step3，退出条件：)(xkf；3.选取方向dk1，满足0)(1dxkTkf，最速下降法中)(1xdkkf；4.利用Armijo算法确定步长1k；5.令dxxkkkk111，k=k+1，返回step2。三、Newton法的算法框架：1.给定初始点Rxxn00,，令k=0；2.判断退出条件是否满足，若是则退出，否则执行step3，退出条件：)(xkf；3.选取方向dk1，满足0)(1dxkTkf，Newton法中)(11xdkkfH,其中)(2xkfH；4.利用Armijo算法确定步长1k；5.令dxxkkkk111，k=k+1，返回step2。四、程序代码：%Armijo方法获取非精确步长functionalpha=Armijo(x,fx,d,g,nf)%输入--x:迭代点%输入x----迭代点%fx---测试函数在x处的函数值%d----下降方向%g----测试函数在x处的梯度值%nf---第nf个测试函数%输出alpha----步长mu=0.9;beta=0.5;%步长压缩系数alpha=1;%初始步长zeta=mu*g'*d;temp=fx+alpha*zeta;xnew=x+alpha*d;fnew=fun(xnew,nf);iter=0;whilefnew=tempalpha=alpha*beta;temp=fx+alpha*zeta;xnew=x+alpha*d;fnew=fun(xnew,nf);endend%最速下降法function[x,fmin,iter]=SteepestDescent(x0,nf)%输入x0----初始点%nf----第nf个测试函数%输出x-----极小值点%fmin----极小值，即x处的函数值%iter----迭代次数epsilon=1e-5;itermax=1e4;[f,g]=fun(x0,nf);ifisnan(g)error('该函数没有梯度或未给出梯度！');enditer=0;%记录迭代次数whilenorm(g)epsilon&&iteritermaxd=-g;alpha=Armijo(x0,f,d,g,nf);x0=x0+alpha*d;[f,g]=fun(x0,nf);iter=iter+1;endx=x0;fmin=f;end%Newton法function[x,fmin,iter]=Newton(x0,nf)%输入x0----初始点%nf----第nf个测试函数%输出x-----极小值点%fmin----极小值，即x处的函数值%iter----函数值计算次数epsilon=1e-5;itermax=1e4;[f,g,H]=fun(x0,nf);ifisnan(g)error('该函数没有梯度！');endifisnan(H)error('该函数没有二阶梯度,不能用Newton法计算！');enditer=0;%记录迭代次数whilenorm(g)epsilon&&iteritermaxd=-H^(-1)*g;alpha=Armijo(x0,f,d,g,nf);x0=x0+alpha*d;[f,g,H]=fun(x0,nf);iter=iter+1;endx=x0;fmin=f;endfunction[f,g,H]=fun(x,nf)%计算指定第nf个函数在x点处的函数值f、一阶梯度值g和二阶梯度值H%只计算二维例子switchnfcase1%p179例6%最小值点(1,1),最小值0%建议初始点(00)'f=(x(1)-1)^2+(x(2)-1)^2;g=zeros(2,1);g(1,1)=2*(x(1)-1);g(2,1)=2*(x(2)-1);H=zeros(2,2);H(1,1)=2;H(1,2)=0;H(2,1)=0;H(2,2)=2;case2%Rosenbrockfunction%最小值点(1,1),最小值0%建议初始点(-10.5)'f=100*(x(1)^2-x(2))^2+(x(1)-1)^2;g=zeros(2,1);g(1,1)=400*x(1)*(x(1)^2-x(2))+2*(x(1)-1);g(2,1)=-200*(x(1)^2-x(2));H=zeros(2,2);H(1,1)=400*(3*x(1)^2-x(2))+2;H(1,2)=-400*x(1);H(2,1)=H(1,2);H(2,2)=200;otherwise%modifiedBroydentridiagonalfunction%来自经典文献Kolda-Lewis-Torczon-2003的389页例子%该例子不存在导数%最小值点(0,0),最小值1%建议初始点(-0.9-1)'f=abs((3-2*x(1))*x(1)-2*x(2)+1)^(7/3)+abs((3-2*x(2))*x(2)-x(1)+1)^(7/3);g=NaN;H=NaN;end五、运行结果：[x,fmin,iter]=SteepestDescent([-2,2]',2)x=1.00001.0000fmin=1.1935e-010iter=2202[x,fmin,iter]=Newton([-2,2]',2)x=1.00001.0000fmin=1.6258e-012iter=196由上述可知，newton法要比最速下降法要快的多。