最优化课程设计--共轭梯度法算法分析报告与实现

1、最优化课程设计 -共轭梯度法算法分析与实现（设计程序）题目 共轭梯度法算法分析与实现班级 / 学号 14140101/11学 生 姓 名 黄中武 指 导 教 师 王吉波 王微微 课程设计任务书课 程 名称 最优化方法课程设计 院（系） 理学院 专业 信息与计算科学课程设计题目 共轭梯度法算法分析与实现 课程设计时间 : 2014 年 6月 16日至 2014 年 6月 27日课程设计的要求及容 :要求1. 学习态度要认真，要积极参与课程设计，锻炼独立思考能力 ; 2. 严格遵守上 机时间安排 ;3. 按照 MATLAB 编程训练的任务要求来编写程序 ;4. 根据任务书来完成课程设计论文 ;5.

2、 报告书写格式要求按照航空航天大学“课程设计报告撰写规” ; 6. 报告上交 时间 :课程设计结束时上交报告 ;7. 严禁抄袭行为，一旦发现，课程设计成绩为不及格。一、 运用共轭梯度法求解无约束最优化问题要求 :1）了解求解无约束最优化问题的共轭梯度法 ;2）绘出程序流程图 ;3）编写求解无约束最优化问题的共轭梯度法 MATLAB 程序 ;4）利用编写文件求解某无约束最优化问题 ;5）给出程序注释。指导教师 年 月 日负责教师 年 月 日学生签字 年 月 日航空航天大学课程设计成绩评定单课程 名称 最优化理论与算法课程设计 院（系） 理学院 专业 信息与计算科学 课 程设计题目 共轭梯度法算法

3、分析与实现 学号 11 黄中武 指导教师评语 :课程设计成绩指导教师签字年月日最优化方法课程设计 航空航天大学 课程设计用纸 目 录 目录一、正文 1二、总结 8参考文献 9附录 10第 I 页最优化方法课程设计 航空航天大学 课程设计用纸 正 文一、正文一 无约束最优化问题的共轭梯度法共轭梯度法最初是由Hesteness和Stiefel于1952年为求解线形方程组而提出 的。后来，人们把这种方法用于求解无约束最优化问题，使之成为一种重要的最优 化方法。下面，重点介绍Fletcher-Reeves共轭梯度法，简称FR法。共轭梯度法的基本思想是把共轭性与最速下降法相结合，利用已知点处的梯度构造一

4、组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。根据共轭梯度方向的基本性质，这种方法具有二次终止性。首先讨论对于二次函数的共轭梯度 法，然后再把这种方法推广到极小化一般函数的情形。考虑问题TTmi fx(), ， 0.5xAxbxcn其中 A 是对称正定矩阵， c 是常数。具体求解方法如下 :(1)首先，任意给定一个初始点，计算出目变函数在这点的梯度，fx()xg 若=0，则停止计算，否则，令 1(1)(1)dfxg,() 1(2)(2),0沿方向搜索，得到点，计算在处的梯度，若g,贝闲用dxx2(1)(2)(2)和构造第二个搜索方向，再沿搜索。 ,gddd2()k()k()k()k

5、一般地，若已知点和搜索方向，贝以出发，沿进行 xdxd搜索，得到(1)()()kkk， xxd,， , k其中步长满足 ,k()()kk()()kkfxd() ， ,fxd()， ,min k此时可求出的显式表达。令 ,k()()kk,()(),， fxd,()求得极小点，令'(1)()kTk， ,()()0,fxd第 1 页最优化方法课程设计 航空航天大学 课程设计用纸 正 文 根据二次函数的梯度表达式，即(1)()kTk， ()0Axbd， ,T()()kkk Axdbd(+)0, ， ,kT()()kk (10.3.16) gAdd ，,0,()kk由(10.3.16)式得到Tk

6、()gd()()kTkk (10.3.17) ,dAdkk，计算在处的梯度，若，则停止计算；否则，用fx()g,Ox,gk , 1k, 1()k(1)k，(1)k，()k和构造下一个搜索方向，并使和关于A共轭。按此设dddd想，令(1)()kk， dgd,， , (1O.3.18) kk， 1()kT 上式两端左乘，并令 dA()(1)()()()kTkkTkTk ， dAddAgdAd, ， ,O kk， 1由此得到()kT()()kTk,dAg (1O.3.19) dAd ， kk1(1)k，(1)k，再从出发，沿方向搜索xd 综上分析，在第一个搜索方向取负梯度的前提下，重复使用公式 (1

7、O.3.14)，(10.3.17)，(10318)和(10.3.19)，就能伴随计算点的增加，构造出一组搜索方向。第 2 页最优化方法课程设计 航空航天大学 课程设计用纸 正 文二 程序流程图 开始输入初始点 x0精度 e继续迭代 满足精度要 N 求Y输出迭代结果结束图一 共轭梯度法程序流程图三 共轭梯度法的 MATLAB 程序 function x,val,k=frcg(fun,gfun,x0) maxk=5000;rho=0.6;sigma=0.4; k=0;epsilon=1e-7;n=length(x0);while (k<maxk) g=feval(gfun,x0);第 3 页

8、最优化方法课程设计 航空航天大学 课程设计用纸 正 文 itern=k-(n+1)*floor(k/(n+1);itern=itern+1;if(itern=1)d=-g;elsebeta=(g'*g)/(g0'*g0); d=-g+beta*d0;gd=g'*d;if(gd>=0) d=-g;endendif (norm(g)<epsilon) break;endm=0;mk=0;while (m<20)if(feval(fu n,xO+rh°Am*d)vfeval(fu n,xO)+sigma*rh°Am*g'*d)mk

9、=m;break;endm=m+1;endx0=x0+rhoAmk*d;val=feval(fun,xO);g0=g;d0=d;k=k+1;end第 4 页最优化方法课程设计 航空航天大学 课程设计用纸 正 文 x=x0;val=feval(fun,x);function f=fun(x)f=100*(x(1F2-x(2)F2+(x(1)-1F2;fun cti on g=gf un(x)g=400*x(1)*(x(1)A2-x (2)+2*(x(1)-1),-200*(x(1)A2-x (2)'四利用所编程序求解实际问题222mifxxxx()100*()(1),，例 n 121*T

10、xfx,(1,1),()0该问题有精确解利用所编程序求解此问题，在命令窗口输入：>> 0= -1. 2 1 "+ ; Iz. valj kJ =f rc1 tun T 吐un 宝0】运行结果为：累二k DCOO1.OCOOval -乩 7224017it -第5页最优化方法课程设计 航空航天大学 课程设计用纸正文五程序注释function x,val,k=frcg(fun,gfun,x0)%用FR共轭梯度法求解无约束问题:min f(x) %输入:x0时初始点，fun，gfun分别是目标函数和梯度 输出:x，val分别是近似最优点和最优值，k是迭代次数。maxk=5000

11、;%最大迭代次数K9«(OCXIVE)壬 mgLUohlupu三eq e<七練湄匍&(uo_ 一 sd V(6EOU)七pupu (0HAP6)七 -P®P6s6*o6)、(F6Hea)q sa)6HP(lhhu£)七 叵 4«®M44£ L+U3HE9一 二 L+u)2)00_r(L+u)&HU£ 翌BM44 £ (ox-u na_e> IT6wxeluvE -ZMSX)£6U-Hu l< LHUO-一 sd OH>I &oHeg一 s&oHoll

12、«仪腿B最优化方法课程设计 航空航天大学 课程设计用纸 正 文 if(feval(fu n,xO+rh°Am*d)vfeval(fu n,xO)+sigma*rh°Am*g'*d) mk=m;break;endm=m+1;endx0=x0+rhoAmk*d;val=feval(fun,xO);g0=g;d0=d;k=k+1;endx=x0;val=feval(fun,x);梯度最优化这function f=fun(x) f=100*(x(1)A2-x(2)A2+(x(1)-1)A2;% 需要求解的函数 function g=gfun(x) g=400*x(

13、1)*(x(1)A2-x(2)+2*(x(1)-1),-200*(x(1)A2-x(2)'% 第 7 页最优化方法课程设计 航空航天大学 课程设计用纸 正 文 二、总结 不知不觉，一个学期就这样过去了，随着期末尾声的到来，门课也已经结课了，接着而来的是为期两个星期的课程设计。作为信息与计算科学系的一员，我们在课堂上接触最多的就是理论部分，刚好 课程设计可以给我们验证理论，联系实际的机会，所以，这次课程设计，我一直都 在认真完成。在拿到自己的课程设计题目的时候，我对它进行了一定时间的审题， 题目中要求我用共轭梯度法求解无约束优化问题， 所以我拿到课本，仔细地看了 共轭梯度法的原理与例题求

14、解，以便帮助我更好的理解共轭梯度法的应用。我记得，再一次研究生面试中，有的老师问过考生:你在你的大学生涯中学到了什么 ,如果让我回答，我会说 :我学到了一种发现问题与解决问题的方法，这种方法 是在我的学习中慢慢形成的一种潜移默化的思想，关于学到的容，我们不会一直保 留太清晰的记忆，也不会在以后的生活中用到太多，就像买菜不会用到微积分，不 会求导，但是，数学方法和思想给我们思考问题所带来的方法论却是大有裨益。这次课程设计，我发现我的很多不足，比如在 MATLAB 上的应用上，我还不 熟练，这与我在平时的练习中没有加以重视有关，而且在最优化的很多知识点 上，自己还没有很好地掌握。最后 ，我要感我们

15、的任课教师王吉波老师，感他在给我们上课中的带来的幽默 感和知识的传授。在此，祝愿老师身体健康，工作顺利。完稿日期 : 2014 年 6月 21日第 8 页最优化方法课程设计 航空航天大学 课程设计用纸 参考文献参考文献1宝林.最优化理论与算法M.,清华大学,2013. 2卫国.MATLAB程序 设计教程 M., 中国水利水电 ,2010. 3 马昌凤.最优化方法及其 MATLAB 程序 设计 M., 科学,2010.第 9 页最优化方法课程设计 航空航天大学 课程设计用纸 附 录 附录 源程序:function x,val,k=frcg(fun,gfun,x0)maxk=5000;rho=0.

16、6;sigma=0.4;k=0;epsilon=1e-7;n=length(x0);while (k<maxk)g=feval(gfun,x0);itern=k-(n+1)*floor(k/(n+1);itern=itern+1;if(itern=1)d=-g;elsebeta=(g'*g)/(g0'*g0);d=-g+beta*d0;gd=g'*d;if(gd>=0)d=-g;endendif (norm(g)<epsilon)break;endm=0;mk=0;while (m<20)if(feval(fu n,xO+rh°Am*d)vfeval(fu n,xO)+sigma*rh°Am*g'*d)第 10