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

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

2、精确搜索过程。因此，既能保证目标函数具有可接受的下降量又能使最终形成的迭代序列收敛的非精确搜索变得越来越流行，本次实验主要介绍里面的强wolfe准则。wolfe准则是指，给定，求使得下面两个不等式同时成立： 其中，而当（1.11）改成另一个条件时 这样当充分小时，可保证（1.12）变成近似精确线搜索。（1.10）和（1.12）称强wolfe准则。强wolfe准则表明，由该准则到新的迭代点在的某一邻域内且使目标函数值有一定的下降量。由于，可以证明wolfe准则的有限终止性，即步长的存在性，有定理：设有下界且，令，则存在一个区间【a,b】，0ab,使每个均满足（1.10）和（1.12）DFP算法：

3、 变尺度法是在牛顿法的基础上发展起来的，它和梯度法亦有密切关系.变尺度法避免了Newton法在每次迭代都要计算目标函数的Hesse矩阵和它的逆矩阵而导致随问题的维数增加计算量迅速增加.DFP算法是变尺度法中一个非常好的算法.DFP算法首先是1959年由Davidon提出的后经Fletcher和Powell改进，故名之为DFP算法，它也是求解无约束优化问题最有效的算法之一.（1） 变尺度法基本原理 在Newton法中，基本迭代公式 +=+， 其中， ， ， 于是有 （1） 其中是初始点，和分别是目标函数在点的梯度和Hesse矩阵.为了消除这个迭代公式中的Hesse逆矩阵，可用某种近似矩阵=来替换

4、它，即构造一个矩阵序列去逼近Hesse逆矩阵序列此时式（1）变为 事实上，式中无非是确定了第k次迭代的搜索方向，为了取得更大的灵活性，我们考虑更一般的的迭代公式 (2) 其中步长因子kt通过从出发沿-=作直线搜索来确定.式（2）是代表很长的一类迭代公式.例如，当（单位矩阵）时，它变为最速下降法的迭代公式.为使确实与近似并且有容易计算的特点，必须对附加某些条件： 第一，为保证迭代公式具有下降性质，要求中的每一个矩阵都是对称 正定的. 理由是，为使搜索方向-=是下降方向，只要 成立即可，即 成立.当对称正定时，此公式必然成立，从而保证式（2）具有下降性质. 第二，要求之间的迭代具有简单形式.显然，

5、 (3) 是最简单的形式了.其中称为校正矩阵，式（3）称为校正公式. 第三，必须满足拟Newton条件.即： (4) 为了书写方便也记 于是拟Newton条件可写为 (5) 由式（3）和（5）知，必须满足 或 (6) （2）DFP算法 DFP校正是第一个拟牛顿校正是1959年由Davidon提出的后经Fletcher和Powell改进故名之为DFP算法它也是求解无约束优化问题最有效的算法之一. DFP算法基本原理 考虑如下形式的校正公式 (7) 其中是特定n维向量，,是待定常数.这时，校正矩阵是 . 现在来确定. 根据拟Newton条件，必须满足（6），于是有 a 或 =+ba. 满足这个方程

6、的待定向量和有无穷多种取法，下面是其中的一种： a， =b 注意到和都是数量，不妨取 =， 同时定出 ，。= a-=b. 将这两式代回（5.32）得 +=+ （8） 这就是DFP校正公式.1. DFP算法迭代步骤 在拟Newton算法中，只要把第五步改为计算式（8）而其他不变，该算法就是DFP算法了.但是由于计算中舍去误差的影响，特别是直线搜索不精确的影响，可能要破坏迭代矩阵的正定性，从而导致算法失效.为保证的正定性，采取以下重置措施：迭代次后，重置初始点和迭代矩阵，即,以后重新迭代. 已知目标函数及其梯度，问题的维数n，终止限e. （1） 选定初始点.计算. （2） 置. （3） 作直线搜索

7、；计算.（4） 判别终止准则是否满足：若满足，则打印，结束；否转（5）. （5） 若=，则置，转（2）；否则转（6）.（6） 计算 ， 置，转（3）.【实验环境】Windows xp,matlab 2007二、实验内容：【实验方案】1：根据强wolfe准则和dfp算法建立wolfe.m文件编写matlab程序代码。2：调用函数，带入不同的初始点，规定精确度，计算结果。【实验过程】（实验步骤、记录、数据、分析）1:代入目标函数为f=(x(1)2-x(2)2+(x(1)-1)2；选取初始点0,0，2,2,2,0.精确度分别为1e4,1e5.【实验结论】（结果） 得到最优点是1.0000,1.000

8、0 最优值和迭代次数：精确度|初始点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算法解决无约束问题方便快捷，步骤不用太繁琐。解决高维函数也是不错的选择。三、指导教师评语及成绩：评 语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性

9、强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确. 成 绩： 指导教师签名： 批阅日期：附录1：源 程 序function x,val,k=dfp(fun,gfun,x0) %功能: 用DFP算法求解无约束问题:min f(x) %输入: 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) g

10、k=feval(gfun,x0); %计算梯度 if(norm(gk)epsilon), break; end %检验终止准则 dk=-Hk*gk; %解方程组, 计算搜索方向 m=0; mk=0; while(m20) %用Armijo搜索求步长 if(feval(fun,x0+rhom*dk)0) Hk=Hk-(Hk*yk*yk*Hk)/(yk*Hk*yk)+(sk*sk)/(sk*yk); end k=k+1; x0=x; end val=feval(fun,x0); function f=fun(x) f=(x(1)2-x(2)2+(x(1)-1)2; function gf=gfun

11、(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)附录2：实验报告填写说明 1实验项目名称：要求与实验教学大纲一致。2实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。3实验原理：简要说明本实验项目所涉及的理论知识。4实验环境：实验用的软、硬件环境。5实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以