《最优化课程设计--共轭梯度法算法分析与实现》由会员分享，可在线阅读，更多相关《最优化课程设计--共轭梯度法算法分析与实现（16页珍藏版）》请在金锄头文库上搜索。
1、 最优化方法课程设计最优化方法课程设计（设计程序）（设计程序）题目题目 共轭梯度法算法分析与实现共轭梯度法算法分析与实现 班级班级 / / 学号学号 14140101/2011041401011 学学 生生 姓姓 名名 黄中武 指指 导导 教教 师师 王吉波王吉波 王微微王微微 课课 程程 设设 计计 任任 务务 书书课 程 名 称 最优化方法课程设计 院（系） 理学院 专业 信息与计算科学 课程设计题目 共轭梯度法算法分析与实现 课程设计时间: 2014 年 6 月 16 日至 2014 年 6 月 27 日课程设计的要求及内容：要求要求1.学习态度要认真，要积极参与课程设计，锻炼独立思考能
2、力；2.严格遵守上机时间安排；3.按照 MATLAB 编程训练的任务要求来编写程序；4.根据任务书来完成课程设计论文；5.报告书写格式要求按照沈阳航空航天大学“课程设计报告撰写规范” ；6.报告上交时间：课程设计结束时上交报告；7.严禁抄袭行为，一旦发现，课程设计成绩为不及格。一、运用共轭梯度法求解无约束最优化问题要求：1）了解求解无约束最优化问题的共轭梯度法；2）绘出程序流程图；3）编写求解无约束最优化问题的共轭梯度法 MATLAB 程序；4）利用编写文件求解某无约束最优化问题；5）给出程序注释。指导教师 年 月 日负责教师 年 月 日学生签字 年 月 日沈阳航空航天大学 课课 程程 设设
3、计计 成成 绩绩 评评 定定 单单课 程 名 称 最优化理论与算法课程设计 院（系） 理学院 专业 信息与计算科学 课程设计题目 共轭梯度法算法分析与实现 学号 2011041401011 姓名 黄中武 指导教师评语：课程设计成绩 指导教师签字 年 月 日最优化方法课程设计 沈阳航空航天大学 课程设计用纸 目 录第 I 页目 录一、正文.1 二、总结.2 参考文献.3 附 录.4最优化方法课程设计 沈阳航空航天大学 课程设计用纸 正 文第 1 页一、正文一、正文一一 无约束最优化问题的共轭梯度法无约束最优化问题的共轭梯度法共轭梯度法最初是由 Hesteness 和 Stiefel 于 1952
4、 年为求解线形方程组而提出的。后来，人们把这种方法用于求解无约束最优化问题，使之成为一种重要的最优化方法。下面，重点介绍 Fletcher-Reeves 共轭梯度法，简称 FR 法。共轭梯度法的基本思想是把共轭性与最速下降法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。根据共轭梯度方向的基本性质，这种方法具有二次终止性。首先讨论对于二次函数的共轭梯度法，然后再把这种方法推广到极小化一般函数的情形。考虑问题min( )f x0.5TTx Axb xc其中 A 是对称正定矩阵，c 是常数。具体求解方法如下：首先，任意给定一个初始点，计算出目变函数在这点的梯
5、度，(1)x( )f x若=0，则停止计算，否则，令1g(1)(1) 1()df xg 沿方向搜索，得到点，计算在处的梯度，若，则利(1)d(2)x(2)x2g0用和构造第二个搜索方向，再沿搜索。2g(1)d(2)d(2)d一般地，若已知点和搜索方向，则从出发，沿进行( )kx( )kd( )kx( )kd搜索，得到(1)( )( )kkk kxxd其中步长满足k( )( )()kk kf xdmin( )( )()kkf xd此时可求出的显式表达。令k( )( )( )()kkf xd 求得极小点，令( ) (1)( )( )()0kTkf xd 最优化方法课程设计 沈阳航空航天大学 课程设
6、计用纸 正 文第 2 页根据二次函数的梯度表达式，即(1)( )()0kTkAxbd ( )( )+)0Tkkk kA xdbd（10.3.16）( )( ) ( )0Tkk kkgAdd由（10.3.16）式得到（10.3.17）( )Tkg dkk ( )( )k TkdAd计算在处的梯度，若，则停止计算；否则，用( )f x(1)kx 10kg和构造下一个搜索方向，并使和关于共轭。1kg( )kd(1)kd(1)kd( )kdA按此设想，令 （10.3.18）(1)( ) 1kk kkdgd 上式两端左乘，并令( )k TdA( )(1)( )( )( ) 10k Tkk Tk Tk k
7、kdAddAgdAd 由此得到（10.3.19）( ) 1k T kkdAg( )( )k TkdAd再从出发，沿方向搜索(1)kx(1)kd综上分析，在第一个搜索方向取负梯度的前提下，重复使用公式（10.3.14） ， （10.3.17） ， （10.3.18）和（10.3.19） ，就能伴随计算点的增加，构造出一组搜索方向。最优化方法课程设计 沈阳航空航天大学 课程设计用纸 正 文第 3 页二二 程序流程图程序流程图NY 图一 共轭梯度法程序流程图三三 共轭梯度法的共轭梯度法的 MATLAB 程序程序function x,val,k=frcg(fun,gfun,x0)maxk=5000;r
8、ho=0.6;sigma=0.4;k=0;epsilon=1e-7;n=length(x0);while (k=0)d=-g;endendif (norm(g)=0)d=-g;endendif (norm(g)=0)d=-g;endendif (norm(g)epsilon)break;endm=0;mk=0;while (m20)if (feval(fun,x0+rhom*d)feval(fun,x0)+sigma*rhom*g*d)最优化方法课程设计 沈阳航空航天大学 课程设计用纸 附 录第 11 页mk=m;break;endm=m+1;endx0=x0+rhomk*d;val=feval(fun,x0);g0=g;d0=d;k=k+1;endx=x0;val=feval(fun,x);function f=fun(x)f=100*(x(1)2-x(2)2+(x(1)-1)2;function g=gfun(x)g=400*x(1)*(x(1)2-x(2)+2*(x(1)-1),-200*(x(1)2-x(2)
