强wolfe非线性搜索+dfp实验报告

数学与计算科学学院实验报告实验项目名称强wolfe非精确搜索+DFP所属课程名称最优化实验类型算法编程实验日期2015年12月11日班级信计1302学号201353100230姓名谢刘成绩1一、实验概述：【实验目的】1：掌握无约束优化问题DFP算法的数值求解思路；2：学习强wolfe非精确搜索的有关知识。3：熟悉应用Matlab求解无约束最优化问题的编程方法.【实验原理】强wolfe准则：由于精确线搜索往往需要计算很多的函数值和梯度值，从而耗费很多的计算资源。特别是当迭代点原理最优点时，精确搜索通常不是十分有效和合理的，对于许多优化算法，其收敛速度并不依赖于精确搜索过程。因此，既能保证目标函数具有可接受的下降量又能使最终形成的迭代序列收敛的非精确搜索变得越来越流行，本次实验主要介绍里面的强wolfe准则。wolfe准则是指，给定)5.0,0(，)5.0,(，求k使得下面两个不等式同时成立：)10.1()()(kTkkkkkkdgxfdxf)11.1()(kTkkTkkkdgddxf其中)()(kkkxfxgg，而当（1.11）改成另一个条件时)12.1(|)(|kTkkTkkkdgddxf这样当0充分小时，可保证（1.12）变成近似精确线搜索。（1.10）和（1.12）称强wolfe准则。强wolfe准则表明，由该准则到新的迭代点kkkkdxx1在kx的某一邻域内且使目标函数值有一定的下降量。由于kTkdg0，可以证明wolfe准则的有限终止性，即步长的存在性，有定理：设)(xf有下界且0kTkdg，令)5.0,0(，)5.0,(，则存在一个区间【a,b】，0ab,使每个],[ba均满足（1.10）和（1.12）DFP算法：变尺度法是在牛顿法的基础上发展起来的，它和梯度法亦有密切关系.变尺度法避免了Newton法在每次迭代都要计算目标函数的Hesse矩阵和它的逆矩阵而导致2随问题的维数增加计算量迅速增加.DFP算法是变尺度法中一个非常好的算法.DFP算法首先是1959年由Davidon提出的后经Fletcher和Powell改进，故名之为DFP算法，它也是求解无约束优化问题最有效的算法之一.（1）变尺度法基本原理在Newton法中，基本迭代公式kkkkPtXX1，其中，1kt，)()]([12kkkXfXfP，于是有....2,1,0,11kgGXXkkkk（1）其中0X是初始点，kg和kG分别是目标函数)(Xf在点kX的梯度和Hesse矩阵.为了消除这个迭代公式中的Hesse逆矩阵1kG，可用某种近似矩阵)(kkXHH换它，即构造一个矩阵序列}{kH去逼近Hesse逆矩阵序列}{1kG此时式（1）变为kkkkgHXX1事实上，式中kkkgHP无非是确定了第k次迭代的搜索方向，为了取得更大的灵活性，我们考虑更一般的的迭代公式kkkkkgHtXX1(2)其中步长因子kt通过从kX出发沿kkkgHP.式（2）是代表很长的一类迭代公式.例如，当IHk法的迭代公式.为使kH确实与1kG近似并且有容易计算的特点，必须对kH附加某些条件：第一，为保证迭代公式具有下降性质，要求}{kH中的每一个矩阵都是对称正定的.理由是，为使搜索方向kkkgHP0kkTkkTkgHgPg成立即可，即0kkTkgHg成立.当kH对称正定时，此公式必然成立，从而保证式（2）具有下降性质.第二，要求kH之间的迭代具有简单形式.显然，kkkEHH1(3)是最简单的形式了.其中kE称为校正矩阵，式（3）称为校正公式.第三，必须满足拟Newton条件.即：3)()(111kkkkkXXggH(4)为了书写方便也记kkkggy1kkkXXS1于是拟Newton条件可写为kkkSyH1(5)由式（3）和（5）知，kE必须满足kkkkSyEH)(或kkkkkyHSyE(6)（2）DFP算法DFP校正是第一个拟牛顿校正是1959年由Davidon提出的后经Fletcher和Powell改进故名之为DFP算法它也是求解无约束优化问题最有效的算法之一.DFP算法基本原理考虑如下形式的校正公式TkkkTkkkkkVVUUHH1(7)其中kkVU,是特定n维向量，kk,,是待定常数.这时，校正矩阵是TkkkTkkkkVVUUE.现在来确定kE.根据拟Newton条件，kE必须满足（6），于是有kkkkTkkkTkkkyHSyVVUU)(或kkkkTkkkTkkkyHSyVVUU.满足这个方程的待定向量kU和kV有无穷多种取法，下面是其中的一种：kkTkkkSyUUkkkTkkkyHyVV注意到kTkyU和kTkyV都是数量，不妨取kkkkkyHVSU,同时定出kTkkyS1，kkTkkyHy1。.将这两式代回（5.32）得kkTkkTkkkkTkTkkkkyHyHyyHySSSHH1（8）这就是DFP校正公式.1.DFP算法迭代步骤在拟Newton算法中，只要把第五步改为计算式（8）而其他不变，该算法就是DFP算法了.但是由于计算中舍去误差的影响，特别是直线搜索不精确的影响，4可能要破坏迭代矩阵kH的正定性，从而导致算法失效.为保证的kH正定性，采取以下重置措施：迭代1n次后，重置初始点和迭代矩阵，即IHXXn010,,以后重新迭代.已知目标函数)(Xf及其梯度)(Xg，问题的维数n，终止限.（1）选定初始点.计算)(),(0000XggXff.（2）置0,,000kgPIH.（3）作直线搜索),(1kkkPXlsX；计算)(),(1111kkkkXggXff.（4）判别终止准则是否满足：若满足，则打印）（11,kkfX，结束；否转（5）.（5）若nk101010,,kkkggffXX，转（2）；否则转（6）.（6）计算,,,,111111kkkkkTkkTkkkkTkTkkkkkkkkkkgHPyHyHyyHySSSHHggyXXS，置1kk，转（3）.【实验环境】Windowsxp,matlab2007二、实验内容：【实验方案】1：根据强wolfe准则和dfp算法建立wolfe.m文件编写matlab程序代码。2：调用函数，带入不同的初始点，规定精确度，计算结果。5【实验过程】（实验步骤、记录、数据、分析）1:代入目标函数为f=(x(1)^2-x(2))^2+(x(1)-1)^2；选取初始点[0,0]’，[2,2]’,[2,0]’.精确度分别为1e4,1e5.【实验结论】（结果）得到最优点是[1.0000,1.0000]最优值和迭代次数：精确度|初始点[0,0]’[2,2]’[2,0]’1e48.3532e-013|72.9957e-014|132.8877e-013|151e58.3532e-013|72.9957e-014|132.8877e-013|15分析：DFP算法只需计算一阶偏导数，无需计算二阶偏导数及其逆矩阵，对目标函数的初始点选择均无严格要求，收敛速度快。【实验小结】（收获体会）运用强wolfe准则和dfp算法解决无约束问题方便快捷，步骤不用太繁琐。解决高维函数也是不错的选择。三、指导教师评语及成绩：评语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确.成绩：指导教师签名：批阅日期：附录1：源程序function[x,val,k]=dfp(fun,gfun,x0)%功能:用DFP算法求解无约束问题:minf(x)6%输入:x0是初始点,fun,gfun分别是目标函数及其梯度%输出:x,val分别是近似最优点和最优值,k是迭代次数maxk=1e8;%给出最大迭代次数rho=0.55;sigma=0.4;epsilon=1e-5;k=0;n=length(x0);Hk=eye(n);while(kmaxk)gk=feval(gfun,x0);%计算梯度if(norm(gk)epsilon),break;end%检验终止准则dk=-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;end%DFP校正x=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);functionf=fun(x)f=(x(1)^2-x(2))^2+(x(1)-1)^2;functiongf=gfun(x)gf=[4*x(1)*(x(1)^2-x(2))+2*(x(1)-1),-2*(x(1)^2-x(2))]';clearx0=[0,0]';[x,val,k]=dfp('fun','gfun',x0)7附录2：实验报告填写说明1．实验项目名称：要求与实验教学大纲一致。2．实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。3．实验原理：简要说明本实验项目所涉及的理论知识。4．实验环境：实验用的软、硬件环境。5．实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以相应的文字说明。对于创新性实验，还应注明其创新点、特色。6．实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包括实验过程中的记录、数据和相应的分析。7．实验结论（结果）：根据实验过程中得到的结果，做出结论。8．实验小结：本次实验心得体会、思考和建议。9．指导教师评语及成绩：指导教师依据学生的实际报告内容，给出本次实验报告的评价。