最优化方法-课程设计报告-运用DFP算法解决无约束最优化问题

北方民族大学课程设计报告系（部、中心）信息与计算科学学院专业信息与计算科学班级09信计（3）班小组成员课程名称最优化方法设计题目名称运用DFP算法解决无约束最优化问题提交时间2012年6月26日成绩指导教师摘要变尺度法是在牛顿法的基础上发展起来的，它和梯度法亦有密切关系.变尺度法避免了Newton法在每次迭代都要计算目标函数的Hesse矩阵和它的逆矩阵而导致随问题的维数增加计算量迅速增加.DFP算法是变尺度法中一个非常好的算法.DFP算法首先是1959年由Davidon提出的后经Fletcher和Powell改进，故名之为DFP算法，它也是求解无约束优化问题最有效的算法之一.DFP变尺度法综合了梯度法、牛顿法的优点而又避弃它们各自的缺点，只需计算一阶偏导数，无需计算二阶偏导数及其逆矩阵，对目标函数的初始点选择均无严格要求，收敛速度快.本文主要分析DFP算法原理及运用Matalb软件编程解决实际数学问题.最后运算结果符合计算精度且只用了一次迭代，由此可见收敛速度快.关键词：Newton法变尺度法Hesse矩阵Matlab软件目录一、课程设计目的.......................................................................................................1二、课程设计要求........................................................................................................1三、课程设计原理........................................................................................................1（1）变尺度法基本原理.......................................................................................1（2）DFP算法......................................................................................................3四、实验内容................................................................................................................4五、数学建模及求解....................................................................................................41.DFP算法迭代步骤..............................................................................................42.DFP算法的流程图..............................................................................................5六、程序实现................................................................................................................5七、数值实验的结果与分析........................................................................................8八、实验总结与体会....................................................................................................91.DFP公式恒有确切解..........................................................................................92.DFP算法的稳定性..............................................................................................9参考文献......................................................................................................................101一、课程设计目的：1、掌握无约束优化问题DFP算法的数值求解思路；2、训练分析DFP算法的运算存储量及收敛速度的能力，了解算法的优缺点；3、通过运用DFP算法求解实际无约束优化问题的意义；4、熟悉应用Matlab求解无约束最优化问题的编程方法.二、课程设计要求熟悉了解DFP算法原理及求解无约束优化问题的步骤，并运用Matlab件编程实现求解问题.三、课程设计原理（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)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条件.即：)()(111kkkkkXXggH(4)为了书写方便也记kkkggy1kkkXXS1于是拟Newton条件可写为kkkSyH1(5)有式（3）和（5）知，kE必须满足kkkkSyEH)(或kkkkkyHSyE(6)3（2）DFP算法DFP校正是第一个拟牛顿校正是1959年由Davidon提出的后经Fletcher和Powell改进故名之为DFP算法它也是求解无约束优化问题最有效的算法之一.DFP算法基本原理考虑如下形式的校正公式TkkkTkkkkkVVUUHH1(7)其中kkVU,是特定n维向量，kk,是待定常数.这时，校正矩阵是TkkkTkkkkVVUUE.现在来确定kE.根据拟Newton条件，kE必须满足（6），于是有kkkkTkkkTkkkyHSyVVUU)(或kkkkTkkkkTkkkyHSyVVyUU.满足这个方程的待定向量kU和kV有无穷多种取法，下面是其中的一种：kkTkkkSyUU，kkkTkkkyHyVV注意到kTkyU和kTkyV都是数量，不妨取kkSU，kkkyHV，同时定出kTkkyS1，kkTkkyHy1.将这两式代回（5.32）得kkTkkTkkkkTkTkkkkyHyHyyHySSSHH1.（8）这就是DFP校正公式.4四、实验内容采用课本P102页例5.3和P107页例5.4进行数值计算；1，求22212125),(minxxxxf，取初始点TX]2,2[0.2，求2221214),(minxxxxf，取初始点TX]1,1[0.五、数学建模及求解1.DFP算法迭代步骤在拟Newton算法中，只要把第五步改为计算式（8）而其他不变，该算法就是DFP算法了.但是由于计算中舍去误差的影响，特别是直线搜索不精确的影响，可能要破坏迭代矩阵kH的正定性，从而导致算法失效.为保证kH的正定性，采取以下重置措施：迭代1n次后，重置初始点和迭代矩阵，即IHXXn010,以后重新迭代.已知目标函数)(Xf及其梯度)(Xg，问题的维数n，终止限.（1）选定初始点.计算)(00Xff，)(00Xgg.（2）置IH0，00gP，0k.（3）作直线搜索),(1kkkPXlsX；计算)(11kkXff，)(11kkXgg.（4）判别终止准则是否满足：若满足，则打印),(11kkfX，结束；否转（5）.（5）若nk，则置10kXX，10kff，10kgg，转（2）；否则转（6）.（6）计算kkkXXS1，kkkggy1，kkTkkTkkkkTkTkkkkyHyHyyHySSSHH1，111kkkgHP，置1kk，转（3）.52.DFP算法的流程图六、程序实现开始选定0X，)(00Xff)(00Xgg，IH0，00gP，0k),(1kkkPXlsX)(11kkXff)(11kkXgg终止准则满足？Y),(11kkfX结束Nnk？YNkkkXXS1kkkggy1kkTkkTkkkkTkTkkkkyHyHyyHySSSHH1111kkkgHP1kk10kXX10kff10kgg678七、数值实验的结果与分析由上述运行结果可得出：第一题迭代一次就解得：]0664.0,2220.0[*0150.1eX与精确解]0,0[X误差远小于610，符合要求.9第二题同样迭代一次就解得：]0555.0,1110.0[*0150.1eX与精确解]0,0[X误差远小于610，符合要求.且所计算的kH矩阵和梯度与精确计算所得一样，这也表明DFP算法的matalb程序完全符合要求.八、实验总结与体会DFP变尺度法综合了梯度法、牛顿法的优点而又避弃它们各自的缺点，只需计算一阶偏导数，无需计算二阶偏导数及其逆矩阵，对目标函数的初始点选择均无严格要求，收敛速度快，这些良好的性能已作阐述。.对于高维（维数大于50）问题被认为是无约束极值问题最好的优化方法之一。下面对其效能特点再作一些补充说明.1.DFP公式恒有确切解分析DFP公式kkTkkTkkkkTkTkkkkyHyHyyHySSSHH1为使变尺度矩阵kH恒有确定的解，必须保证该式右端第二项和第三项的分母为异于零的数，南京大学编的《最优化方法》已证明了这两项的分母均为正数.2.DFP算法的稳定性优化算法的稳定性是指每次迭代都能使目标函数值逐次下降。在阐述构造变尺度矩阵kH的基本要求中。已经证明为保证拟牛顿方向目标函数值下降，kH必须是对称正定矩阵。南京大学编的《最优化方法》证明了对于f(X)的一切非极小点kX处，只要矩阵kH对称正定，则按DFP公式产生的矩阵1kH亦为对称正定。通