wolfe算法确定步长的牛顿法

数学与计算科学学院实验报告实验项目名称wolfe算法确定步长的牛顿法所属课程名称最优化方法实验类型算法编程实验日期2015.11.13班级学号201姓名成绩1一、实验概述：【实验目的】1、实验掌握在非线性搜索wolf算法确定步长的牛顿法的实现算法。2、了解二次终止性，加深对牛顿法（原始，阻尼，修正方法，这里主要针对阻尼方法讨论）的掌握。【实验原理】（一）1、牛顿法公式：21111()(),,1kkkkkkkkkkxxfxfxxxddGg即其中2、原始牛顿法的缺点及改进方法：（1）11,kkx不一定是kd上的最优解，改进方法为阻尼牛顿法。（2）kd不一定是下降方向，改进方法为修正牛顿法。（3）G可能奇异（即逆矩阵不一定存在），改进方法为牛顿最速下降法。3、Wolfe线性搜索准则为：给定常数11210,12，取0k使得12()()().....(1)()()......(2)TkkkkkkkTTkkkkkkfxdfxfxdfxddfxd（二）其算法步骤如下：Step1：给出初始点0,0,1nxRk。Step2：计算121(),(())kkkkgfxGfx。Step3：若||()||kfx，则停止迭代；否则，令1kkkdGgStep4：利用Wolfe线性搜索求得步长k，1kkkkxxdStep5：k=k+1，转步骤2。【实验环境】Windows7Matlabr2010b二、实验内容：【实验方案】1、本次试验的题目为：2用wolfe线性搜索下的阻尼牛顿法求解：332(1)122111min(),(0,0),0.533Tfxxxxxx选取初点为：2、根据阻尼牛顿法的求解步骤，在求解步长k时，用wolfe线性搜索确定，编写程序，在计算机上实现。【实验过程】（实验步骤、记录、数据、分析）（一）由题目可得，21212222201(),()0222xxfxGfxxxx，选取初值(1)00x时，21111111111002(),(),,||||0020gfxGfxdGgd，程序的运行顺序是这样的：1.1=1若，则11112,0xd检验其是否满足12()()().....(1)()()......(2)TkkkkkkkTTkkkkkkfxdfxfxdfxddfxd，其中11210,12，若满足，则1=1，2111xxd，检验2||||d2、若不满足（1），（2），10,(0,1)，令0{|i=0,1,2,...}ik是集合中使(1)成立的最大者，令0i。若ik满足(2)则停止，并取得步长(1)kk，3、否则，令(1)1()ikk，(1)()()()1{+(,j=0,1,...}iijiikkkk令是集合使(1)成立的最大者，令i=i+1,继续2.【实验结论】（结果）输入：x0=[0,0];[x,val,k]=dampnm('fun','gfun','Hess',x0)运行结果得到最优解为：[x1,x2]=[1,2]【实验小结】（收获体会）在运用阻尼牛顿法求解约束问题时，运用wolfe线性搜索步长虽然笔算较为繁琐，但在计算机上实现会变得较简单。但是对比与线性搜索等方法，编程实现比较复杂。本次试验加深了对牛顿法的掌握，但对于算法的实现还不是很熟练，需要加3强练习。三、指导教师评语及成绩：评语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确.成绩：指导教师签名：批阅日期：附录1：源程序4functiony=fun(x);y=(1/3)*(x(1)^3-x(2)^3-x(2)^2-x(1);functiong=gfun(x);g=[x(1)^2-1,x(2)^2-2*x(2)];functionHe=Hess(x);n=length(x);He=zeros(n,n);He=[2*x(1),0,0,2*x(2)-2];function[x,val,k]=dampnm(fun,gfun,Hess,x0);maxk=100;rho=0.5;sigma=0.4;k=0;epsion=le-5;while(kmaxk)gk=feval(gfun,x0);Gk=feval(Hess,x0);dk=Gk\gk;if(norm(dk)epsion)break;end;m=0;mk=0;while(m20)if(feval(fun.x0+rho^m*dk)feval(fun,xo)+sigma*rho^m*gk*dk)mk=m;break;endm=m+1;5endx0=x0+rho^mk*dk;k=k+1;endx=x0;val=feval(fun,x);