最优化方法课程设计报告运用DFP算法解决无约束最优化问题.docx
《最优化方法课程设计报告运用DFP算法解决无约束最优化问题.docx》由会员分享，可在线阅读，更多相关《最优化方法课程设计报告运用DFP算法解决无约束最优化问题.docx（12页珍藏版）》请在冰点文库上搜索。
最优化方法课程设计报告运用DFP算法解决无约束最优化问题
北方民族大学
课程设计报告
系（部、中心）信息与计算科学学院
专业信息与计算科学班级09信计（3）班
小组成员
课程名称最优化方法
设计题目名称运用DFP算法解决无约束最优化问题
提交时间2012年6月26日
成绩
指导教师
摘要
变尺度法是在牛顿法的基础上发展起来的，它和梯度法亦有密切关系.变尺
度法避免了Newton法在每次迭代都要计算目标函数的Hesse矩阵和它的逆矩阵而导致随问题的维数增加计算量迅速增加.DFP算法是变尺度法中一个非常好的算法.DFP算法首先是1959年由Davidon提出的后经Fletcher和Powell改进，故名之为DFP算法，它也是求解无约束优化问题最有效的算法之一.
DFP变尺度法综合了梯度法、牛顿法的优点而又避弃它们各自的缺点，只需
计算一阶偏导数，无需计算二阶偏导数及其逆矩阵，对目标函数的初始点选择均无严格要求，收敛速度快.
本文主要分析DFP算法原理及运用Matalb软件编程解决实际数学问题.最后运算结果符合计算精度且只用了一次迭代，由此可见收敛速度快.
一、课程设计目的错.误!
未定义书签
二、课程设计要求错.误!
未定义书签
三、课程设计原理错.误!
未定义书签
（1）变尺度法基本原理错.误!
未定义书签
（2）DFP算法错误!
未定义书签
四、实验内容错..误!
未定义书签
五、数学建模及求解错.误!
未定义书签
算法迭代步骤错.误!
未定义书签
算法的流程图错.误!
未定义书签
六、程序实现错..误!
未定义书签
七、数值实验的结果与分析错.误!
未定义书签
八、实验总结与体会错.误!
未定义书签
公式恒有确切解错.误!
未定义书签
算法的稳定性错.误!
未定义书签
参考文献错..误!
未定义书签
课程设计目的：
1、掌握无约束优化问题DFP算法的数值求解思路;
2、训练分析DFP算法的运算存储量及收敛速度的能力，了解算法的优缺
点;
八\、‘
3、通过运用DFP算法求解实际无约束优化问题的意义；
4、熟悉应用Matlab求解无约束最优化问题的编程方法.
二、课程设计要求
熟悉了解DFP算法原理及求解无约束优化问题的步骤，并运用Matlab件编程实现求解问题.
三、课程设计原理
（1）变尺度法基本原理
在Newton法中，基本迭代公式
Xk1XktkPk，
其中，tk1，
Pk[2f（Xk）]1f（Xk），
于是有
XkiXkGk1gk，k0,1,2…
（1）
其中Xo是初始点，gk和Gk分别是目标函数f（X）在点Xk的梯度和Hesse矩阵.
为了消除这个迭代公式中的Hesse逆矩阵Gk1，可用某种近似矩阵HkH（Xk）来
替换它，即构造一个矩阵序列｛HJ去逼近Hesse逆矩阵序列｛Gk1｝
此时式
（1）变为
Xk1XkHkgk
事实上，式中PkHkgk无非是确定了第k次迭代的搜索方向，为了取得更大的
灵活性，我们考虑更一般的的迭代公式
Xk1XktkHkgk
（2）
其中步长因子tk通过从Xk出发沿PkHkgk作直线搜索来确定.式
（2）是代表
很长的一类迭代公式.例如，当HkI（单位矩阵）时，它变为最速下降法的迭代公式.为使Hk确实与Gk1近似并且有容易计算的特点，必须对Hk附加某些条件：
第一，为保证迭代公式具有下降性质，要求{Hk}中的每一个矩阵都是对称正定的.
理由是，为使搜索方向PkHkgk是下降方向，只要
gkTPkgkTHkgk0
成立即可，即
gkTHkgk0
成立.当Hk对称正定时，此公式必然成立，从而保证式
（2）具有下降性质.
第二，要求Hk之间的迭代具有简单形式.显然，
Hk1HkEk（3）
是最简单的形式了.其中Ek称为校正矩阵，式（3）称为校正公式.
第三，必须满足拟Newton条件.即：
Hk1（gk1gk）
（Xk1Xk）
（4）
为了书写方便也记
yk
gk1gk
Sk
Xk1Xk
于是拟Newton条件可写为
Hk1yk
Sk（5）
有式（3）和（5）知，Ek必须满足
或EkykSkHkyk⑹
（2）DFP算法
DFP校正是第一个拟牛顿校正是1959年由Davidon提出的后经Fletcher和Powell改进故名之为DFP算法它也是求解无约束优化问题最有效的算法之一.
DFP算法基本原理
考虑如下形式的校正公式
Hk1Hk时：
MVj（7）
其中Uk,Vk是特定n维向量，k,k是待定常数.这时，校正矩阵是
EkkUkU：
MVj.
现在来确定Ek.
根据拟Newton条件，Ek必须满足（6），于是有
（kUkUTkVkVjMSkHkVk
满足这个方程的待定向量Uk和Vk有无穷多种取法，下面是其中的一种:
kUkUkykSk，
kVkVkykHkyk
注意到UTyk和Vjyk都是数量，不妨取
同时定出
将这两式代回（）得
这就是DFP校正公式.
四、实验内容
采用课本P102页例和P107页例进行数值计算;
1,求minf（Xi,X2）x：
25x；，取初始点X。
［2,2］：
.
2,求minf（Xi,X2）x；4x；，取初始点X。
［1,1］：
.
五、数学建模及求解
算法迭代步骤
在拟Newton算法中，只要把第五步改为计算式（8）而其他不变，该算法就是DFP算法了•但是由于计算中舍去误差的影响，特别是直线搜索不精确的影响，可能要破坏迭代矩阵Hk的正定性，从而导致算法失效.为保证Hk的正定性，采取以下重置措施：
迭代n1次后，重置初始点和迭代矩阵，即X。
Xm,H0I以后重新迭代•
已知目标函数f（X）及其梯度g（X），问题的维数n，终止限.
（1）选定初始点.计算fof（Xo），gog（Xo）.
（2）置HoI，F0go，k0.
（3）作直线搜索Xk1ls（Xk,R）；计算fk1f（Xk1），gk1g（Xk1）.
（4）判别终止准则是否满足：
若满足，则打印（Xk1,fk1），结束；否转（5）.
（5）若kn,则置XoXk1，fofk1，gogk1，转
（2）；否则转（6）.
（6）计算
SkXk1Xk，
uuQSkHkykykHk
Hk1HkTT
SkykykHkyk
Pk1Hk1gk1,
置kk
1，转（3）.
算法的流程图
六、程序实现
二
»A二[20；050]；
»fw=iiJLineCx（l）^2+25*x
（2）^）:
I
〉＞g£un=inline（[2*x）:
5G*x
（2）]?
）；
»[乙f,tdc]=dfp（xO,A.fuit,gfun）
»^0=[1#1?
；
»A二[20:
08]：
»fg=inliM»gftm=iiklin«tC[2*x
（1）:
8*x
（2）]'）:
>>[x,tdc]=dfp（xO^A,fun,gfun）
七、数值实验的结果与分析
由上述运行结果可得出：
第一题迭代一次就解得：
X1.0e015*[0.2220,0.0664]与精确解
第二题同样迭代一次就解得：
X1.0e015*[0.1110,0.0555]与精确解
X[0,0]误差远小于106，符合要求.且所计算的Hk矩阵和梯度与精确计算
所得一样，这也表明DFP算法的matalb程序完全符合要求.
八、实验总结与体会
DFP变尺度法综合了梯度法、牛顿法的优点而又避弃它们各自的缺点，只需计算一阶偏导数，无需计算二阶偏导数及其逆矩阵，对目标函数的初始点选择均无严格要求，收敛速度快，这些良好的性能已作阐述。
.对于高维（维数大于
50）问题被认为是无约束极值问题最好的优化方法之一。
下面对其效能特点再作一些补充说明.
公式恒有确切解
分析DFP公式
为使变尺度矩阵Hk恒有确定的解，必须保证该式右端第二项和第三项的分母为异于零的数，南京大学编的《最优化方法》已证明了这两项的分母均为正数.
算法的稳定性
优化算法的稳定性是指每次迭代都能使目标函数值逐次下降。
在阐述构造变尺度矩阵Hk的基本要求中。
已经证明为保证拟牛顿方向目标函数值下降，Hk必须
是对称正定矩阵。
南京大学编的《最优化方法》证明了对于f（X）的一切非极小点
Xk处，只要矩阵Hk对称正定，则按DFP公式产生的矩阵Hk1亦为对称正定。
通常我们取初始变尺度矩阵H。
为对称正定的单位矩阵I，因此随后构造的变尺
度矩阵序列｛Hk（k=1,2,必为对称正定矩阵序列，这就从理论上保证DFP法使目标函数值稳定地下降。
但实际上由于一维最优搜索不可能绝对准确，而且计算机也不可避免地有舍入误差，仍有可能使变尺度矩阵的正定性遭到破坏或导致奇异。
为提高实际计算的稳定性，除提高一维搜索的精度外，通常还将进行n次（n
为目标函数的维数）迭代作为一个循环，将变尺度矩阵重置为单位矩阵I,并以上一循环的终点作为起点继续进行循环迭代，这己反映在迭代过程和算法框图之中.
参考文献：
[1]《优化设计方法[M]》邵陆寿北京：
农业出版社,2007.
[2]《最优化方法》南京大学出版社
[3]《最优化方法及其应用》郭科陈聆魏友华高等教育出版社
[4]《MATLAB使用教程》张磊毕靖郭莲英人民邮电出版社
升级会员 