最优化课程设计--共轭梯度法算法分析与实现(设计程序)题目共轭梯度法算法分析与实现班级 / 学号 14140101/2011041401011 学生姓名黄中武指导教师王吉波王微微课程设计任务书课程名称最优化方法课程设计院(系) 理学院专业信息与计算科学课程设计题目共轭梯度法算法分析与实现课程设计时间: 2014 年 6月 16日至 2014 年 6月 27日课程设计的要求及内容:[要求]1. 学习态度要认真，要积极参与课程设计，锻炼独立思考能力;2. 严格遵守上机时间安排;3. 按照MATLAB编程训练的任务要求来编写程序;4. 根据任务书来完成课程设计论文;5. 报告书写格式要求按照沈阳航空航天大学“课程设计报告撰写规范”;6. 报告上交时间:课程设计结束时上交报告;7. 严禁抄袭行为，一旦发现，课程设计成绩为不及格。

一、运用共轭梯度法求解无约束最优化问题要求:1)了解求解无约束最优化问题的共轭梯度法;2)绘出程序流程图;3)编写求解无约束最优化问题的共轭梯度法MATLAB程序;4)利用编写文件求解某无约束最优化问题;5)给出程序注释。

指导教师年月日负责教师年月日学生签字年月日沈阳航空航天大学课程设计成绩评定单课程名称最优化理论与算法课程设计院(系) 理学院专业信息与计算科学课程设计题目共轭梯度法算法分析与实现学号 2011041401011 姓名黄中武指导教师评语:课程设计成绩指导教师签字年月日最优化方法课程设计沈阳航空航天大学课程设计用纸目录目录一、正文 (1)二、总结 ...............................................................8 参考文献 ............................................................... 9 附录 .. (10)第 I 页最优化方法课程设计沈阳航空航天大学课程设计用纸正文一、正文一无约束最优化问题的共轭梯度法共轭梯度法最初是由Hesteness和Stiefel于1952年为求解线形方程组而提出的。

后来，人们把这种方法用于求解无约束最优化问题，使之成为一种重要的最优化方法。

下面，重点介绍Fletcher-Reeves共轭梯度法，简称FR法。

共轭梯度法的基本思想是把共轭性与最速下降法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。

根据共轭梯度方向的基本性质，这种方法具有二次终止性。

首先讨论对于二次函数的共轭梯度法，然后再把这种方法推广到极小化一般函数的情形。

考虑问题TTmi fx(),，，0.5xAxbxcn其中A是对称正定矩阵，c是常数。

具体求解方法如下:(1)首先，任意给定一个初始点，计算出目变函数在这点的梯度，fx()xg若=0，则停止计算，否则，令 1(1)(1)dfxg,,,,,() 1(1)(2)(2),0沿方向搜索，得到点，计算在处的梯度，若g，则利用dxx2(1)(2)(2)和构造第二个搜索方向，再沿搜索。

,gddd2()k()k()k()k一般地，若已知点和搜索方向，则从出发，沿进行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()gd()()kTkk (10.3.17) ,,,dAdk(1)k，计算在处的梯度，若，则停止计算;否则，用fx()g,0x,gk，1k，1()k(1)k，(1)k，()k和构造下一个搜索方向，并使和关于A共轭。

按此设dddd想，令(1)()kk，dgd,,，, (10.3.18) kk，1()kT上式两端左乘，并令 dA()(1)()()()kTkkTkTk，dAddAgdAd,,，,,0 kk，1由此得到()kT()()kTk,,dAg (10.3.19) dAd，kk1(1)k，(1)k，再从出发，沿方向搜索 xd综上分析，在第一个搜索方向取负梯度的前提下，重复使用公式(10.3.14)，(10.3.17)，(10.3.18)和(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 页最优化方法课程设计沈阳航空航天大学课程设计用纸正文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(fun,x0+rho^m*d)<feval(fun,x0)+sigma*rho^m*g'*d) mk=m;break;endm=m+1;endx0=x0+rho^mk*d;val=feval(fun,x0);g0=g;d0=d;k=k+1;end第 4 页最优化方法课程设计沈阳航空航天大学课程设计用纸正文 x=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))]'四利用所编程序求解实际问题222mifxxxx()100*()(1),,，,例 n121**Txfx,,(1,1),()0该问题有精确解利用所编程序求解此问题，在命令窗口输入:运行结果为:第 5 页最优化方法课程设计沈阳航空航天大学课程设计用纸正文五程序注释function [x,val,k]=frcg(fun,gfun,x0)%用FR共轭梯度法求解无约束问题:min f(x) %输入:x0时初始点，fun，gfun 分别是目标函数和梯度 %输出:x，val分别是近似最优点和最优值，k是迭代次数。

maxk=5000;%最大迭代次数rho=0.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)第 6 页最优化方法课程设计沈阳航空航天大学课程设计用纸正文if(feval(fun,x0+rho^m*d)<feval(fun,x0)+sigma*rho^m*g'*d) mk=m;break;endm=m+1;endx0=x0+rho^mk*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))]'%梯度第 7 页最优化方法课程设计沈阳航空航天大学课程设计用纸正文二、总结不知不觉，一个学期就这样过去了，随着期末尾声的到来，《最优化》这门课也已经结课了，接着而来的是为期两个星期的课程设计。

作为信息与计算科学系的一员，我们在课堂上接触最多的就是理论部分，刚好课程设计可以给我们验证理论，联系实际的机会，所以，这次课程设计，我一直都在认真完成。

在拿到自己的课程设计题目的时候，我对它进行了一定时间的审题，题目中要求我用共轭梯度法求解无约束优化问题，所以我拿到课本，仔细地看了共轭梯度法的原理与例题求解，以便帮助我更好的理解共轭梯度法的应用。

我记得，再一次研究生面试中，有的老师问过考生:你在你的大学生涯中学到了什么,如果让我回答，我会说:我学到了一种发现问题与解决问题的方法，这种方法是在我的学习中慢慢形成的一种潜移默化的思想，关于学到的内容，我们不会一直保留太清晰的记忆，也不会在以后的生活中用到太多，就像买菜不会用到微积分，不会求导，但是，数学方法和思想给我们思考问题所带来的方法论却是大有裨益。

这次课程设计，我发现我的很多不足，比如在MATLAB上的应用上，我还不熟练，这与我在平时的练习中没有加以重视有关，而且在《最优化》的很多知识点上，自己还没有很好地掌握。

最后，我要感谢我们的任课教师王吉波老师，感谢他在给我们上课中的带来的幽默感和知识的传授。

在此，祝愿老师身体健康，工作顺利。

完稿日期: 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.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(fun,x0+rho^m*d)<feval(fun,x0)+sigma*rho^m*g'*d) 第 10 页最优化方法课程设计沈阳航空航天大学课程设计用纸附录mk=m;break;endm=m+1;endx0=x0+rho^mk*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))]' 第 11 页。