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

1、数学与计算科学学院实验报告实验项目名称强wolfe非精确搜索+DFP所属课程名称最优化实验类型算法编程实验日期2015年12月11日班级信计1302学号201353100230姓名谢刘成绩 一、实验概述:【实验目的】1:掌握无约束优化问DFP算法的数值求解思路;2:学习强wolfe非精确搜索的有关知识。3:熟悉应用Matlab求解无约束最优化问题的编程方法.【实验原理】强wolfe准则：由于精确线搜索往往需要计算很多的函数值和梯度值，从而耗费很多的计算资源。特别是当迭代点原理最优点时，精确搜索通常不是十分有效和合理的，对于许多优化算法，其收敛速度并不依赖于精确搜索过程。因此，既能保证目标函数具

2、有可接受的下降量又能使最终形成的迭代序列收敛的非精确搜索变得越来越流行，本次实验主要介绍里面的强wolfe准则。wolfe准则是指给定pg(0,0.5)qg(p,0.5)，求%使得下面两个不等式同时成立：k(1.10)(1.11)(1.12)f(x+ad)agrdkkkkkk其中g=g(X)=Vf(x)，而当(1.11)改成另一个条件时kkkIVf(x+ad)Tdl-cgTdkkkkkk这样当b0充分小时，可保证(1.12)变成近似精确线搜索。(1.10)和(1.12)称强wolfe准则。强wolfe准则表明，由该准则到新的迭代点x二x+d在x的某一邻域内且使k+1kkkk目标函数值有一定的下

3、降量。由于gTd0，可以证明wolfe准则的有限终止性，kk即步长的存在性，有定理：设f(x)有下界且gTd0，令pG(0,0.5)，CG(p,0.5)，kk则存在一个区间【a,b】，0ab，使每个ga,b均满足(1.10)和(1.12)DFP算法：变尺度法是在牛顿法的基础上发展起来的，它和梯度法亦有密切关系变尺度法避免了Newton法在每次迭代都要计算目标函数的Hesse矩阵和它的逆矩阵而导致随问题的维数增加计算量迅速增加.DFP算法是变尺度法中一个非常好的算法.DFP算法首先是1959年由Davidon提出的后经Fletcher和Powell改进故名之为DFP算法，它也是求解无约束优化问题

4、最有效的算法之一.(1)变尺度法基本原理在Newton法中，基本迭代公式X二X+1P，k+1kkk其中，t=1，P=-V2f(X)-1Vf(X)，TOC o 1-5 h zkkkk于是有X二XG-1g,k二0,1,2(1)k+1kkk其中X是初始点，g和G分别是目标函数f(X)在点X的梯度和Hesse矩阵为0kkk了消除这个迭代公式中的Hesse逆矩阵G-1，可用某种近似矩阵H二H(X)來kkk替换它，即构造一个矩阵序列H去逼近Hesse逆矩阵序列G-1此时式(1)变kk为X=X-Hg事实上，式中P=-Hg无非是确定了第k次迭代的搜索方k+1kkkkkk向，为了取得更大的灵活性，我们考虑更一般

5、的的迭代公式X二X-tHgk+1kkkk其中步长因子kt通过从X出发沿P=-Hg.式（2）kkkk是代表很长的一类迭代公式例如，当H=I（单位矩阵）时：它变为最速下降k法的迭代公式为使H确实与G-1近似并且有容易计算的特点，必须对H附加某些kkk条件：第一，为保证迭代公式具有下降性质，要求H中的每一个矩阵都是对称k正定的.理由是，为使搜索方向P=-Hg总下降方向.只要kkkgTP二g-THg0成立当H对称正定时，此公式必然成立，从而保证式（2）具有下kkkk降性质.第二，要求H之间的迭代具有简单形式显然，kH二H+Ek+1kk是最简单的形式了其中E称为校正矩阵，式（3）称为校正公式.k第三，必

6、须满足拟Newton条件即：H（g-g）=（X-X）TOC o 1-5 h zk+1k+1kk+1k为了书写方便也记y二g-gkk+1kS二X-Xkk+1k于是拟Newton条件可写为Hy二S（5）k+1kk由式（3）和（5）知，E必须满足k(6)(H+E)y=S或Ey=S=HykkkkkkkkkDFP算法DFP校正是第一个拟牛顿校正是1959年由Davidon提出的后经Fletcher和Powell改进故名之为DFP算法它也是求解无约束优化问题最有效的算法之一.DFP算法基本原理考虑如下形式的校正公式H=H+aUUt+卩VVt(7)k+1kkkkkkk其中U,V是特定n维向量，a,kkkP,

7、是待定常数.这时，校正矩阵是kE=aUUt+pVVt.现在来确定E.kkkkkkkk根据拟Newton条件，E必须满足（6），k于是有(aUUt+卩VVt)y=S-Hykkkkkkkkkk或aUUT+BVVTy=S-Hykkkkkkkkkk.满足这个方程的待定向量U和Vkk有无穷多种取法，下面是其中的一种：UUTy=SkkkkkBVVTy=_Hykkkkkk注意到UTy和VTy都是数量，不妨取U=S,V=Hykkkkk同时定出11a=，B=kSTykyTHykkkkk.将这两式代回（5.32）得SStHyyTHH=H+kkkkkk+1kSTyyTHykkkkk（8）这就是DFP校正公式.1.D

8、FP算法迭代步骤在拟Newton算法中，只要把第五步改为计算式（8）而其他不变，该算法就是DFP算法了但是由于计算中舍去误差的影响，特别是直线搜索不精确的影响，可能要破坏迭代矩阵H的正定性，从而导致算法失效为保证的H正定性，采取kk以下重置措施：迭代n+1次后，重置初始点和迭代矩阵，即X二X,H二I，以后0n+10重新迭代.已知目标函数f(X)及其梯度g(X)，问题的维数n，终止限(1)选定初始点计算fo=f(X0),g厂g(X0).（2）置H=I,P=_g,k=0.000（3）作直线搜索X=ls（X,P）；计算f=f（X）,g=g（X）.k+1kkk+1k+1k+1k+1（4）判别终止准则是

9、否满足：若满足，则打印（X，/），结束；否转（5）.k+1k+1（5）若k=n：贝I.罔X=X,f=f,g=g，转（2）；否则转（6）.0k+10k+10k+1（6）计算S=X-X,kk+1ky=g-g,kk+1kHH,SSTHyyTH，k+1kSTyyTHykkkkkP=Hg,k+1k+1k+1置k=k+1，转(3).【实验环境】Windowsxp,matlab2007二、实验内容：【实验方案】1:根据强wolfe准则和dfp算法建立wolfe.m文件编写matlab程序代码。2:调用函数，带入不同的初始点，规定精确度，计算结果。【实验过程】(实验步骤、记录、数据、分析)1:代入目标函数为f

10、=(x(1)A2-x(2)A2+(x(1)-1)A2；选取初始点0,0，2,2,2,0.精确度分别为1e4,1e5.【实验结论】(结果)得到最优点是1.0000,1.0000最优值和迭代次数：精确度1初始点0,02,22,01e48.3532e-013|72.9957e-014|132.8877e-013|151e58.3532e-013|72.9957e-014|132.8877e-013|15分析：DFP算法只需计算一阶偏导数，无需计算二阶偏导数及其逆矩阵，对目标函数的初始点选择均无严格要求，收敛速度快。【实验小结】（收获体会）运用强wolfe准则和dfp算法解决无约束问题方便快捷，步骤不

11、用太繁琐。解决高维函数也是不错的选择。三、指导教师评语及成绩：评语评语等级优良中及格不及格1.实验报吿按时完成，字迹清楚,文字叙述流畅，逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细，记录完整，数据合理，分析透彻）4实验结论正确.附录1：源程序functionx,val,k=dfp(fun,gfun,xO)%功能：用DFP算法求解无约束问题：minf(x)%输入：x0是初始点,fun,gfun分别是目标函数及其梯度%输出：x,val分别是近似最优点和最优值，k是迭代次数maxk=1e8;%给出最大迭代次数rho=0.55;sigma=0.4;epsilon=1e-5;k=0;n=len

12、gth(xO);Hk=eye(n);while(kmaxk)gk=feval(gfun,xO);%计算梯度if(norm(gk)epsilon),break;end%检验终止准贝Udk=-Hk*gk;%解方程组，计算搜索方向m=0;mk=0;while(m20)%用Armijo搜索求步长if(feval(fun,x0+rhoAm*dk)0)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;fun

13、ctiongf=gfun(x)gf=4*x(1)*(x(1)入2_x(2)+2*(x(1)_1),_2*(x(1)A2_x(2);clearx0=0,0;x,val,k=dfp(fun,gfun,x0)附录2：实验报告填写说明1实验项目名称：要求与实验教学大纲一致。2实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。3实验原理：简要说明本实验项目所涉及的理论知识。4实验环境：实验用的软、硬件环境。5实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。对于设计性和综合性实验，在