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

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

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

3、计院( 系) 理学院专业 信息与计算科学 课程设计题目共轭梯度法算法分析与实现学号 2011041401011 姓名 黄中武指导教师评语 :课程设计成绩指导教师签字年 月 日最优化方法课程设计沈阳航空航天大学课程设计用纸目 录目 录一、正文 . 1二、总结 .8 参考文献 . 9附录 . 10第 i页最优化方法课程设计沈阳航空航天大学课程设计用纸正 文一、正文一 无约束最优化问题的共轭梯度法.共轭梯度法最初是由hesteness 和 stiefel于 1952 年为求解线形方程组而提出的。后来，人们把这种方法用于求解无约束最优化问题，使之成为一种重要的最优化方法。下面，重点介绍fletcher

4、-reeves共轭梯度法，简称fr法。共轭梯度法的基本思想是把共轭性与最速下降法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。根据共轭梯度方向的基本性质，这种方法具有二次终止性。首先讨论对于二次函数的共轭梯度法，然后再把这种方法推广到极小化一般函数的情形。考虑问题ttmi fx(),， 0.5xaxbxcn其中 a 是对称正定矩阵， c 是常数。具体求解方法如下 :(1) 首先，任意给定一个初始点，计算出目变函数在这点的梯度，fx()xg 若 =0，则停止计算，否则，令1(1)(1)dfxg,() 1(1)(2)(2),0沿方向搜索，得到点，计算在处的

5、梯度，若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(

6、)()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 ，

7、(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=lengt

8、h(x0);while (k=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)mk=m;break;endm=m+1;endx0=x0+rhomk*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

9、)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分别是目标函数和梯

10、度 %输出 :x ，val 分别是近似最优点和最优值， k 是迭代次数。maxk=5000;%最大迭代次数rho=0.6;sigma=0.4;k=0;epsilon=1e-7;n=length(x0);while (k=0)d=-g;endendif (norm(g)epsilon)%检验终止条件break;endm=0;mk=0;while (m20)第 6 页最优化方法课程设计沈阳航空航天大学课程设计用纸正 文if(feval(fun,x0+rhom*d)feval(fun,x0)+sigma*rhom*g*d)mk=m;break;endm=m+1;end.x0=x0+rhomk*d;v

11、al=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 页最优化方法课程设计 沈阳航空航天大学 课程设计用纸 正 文二、总结不知不觉，一个学期就这样过去了，随着期末尾声的到来，最优化这门课也已经结课了，接着而来的是为期两个星期的课程设计。作为信息与计算科学系的一员，我们在课堂上

12、接触最多的就是理论部分，刚好课程设计可以给我们验证理论，联系实际的机会，所以，这次课程设计，我一直都在认真完成。在拿到自己的课程设计题目的时候，我对它进行了一定时间的审题，题目中要求我用共轭梯度法求解无约束优化问题， 所以我拿到课本，仔细地看了共轭梯度法的原理与例题求解，以便帮助我更好的理解共轭梯度法的应用。我记得，再一次研究生面试中，有的老师问过考生: 你在你的大学生涯中学到了什么 , 如果让我回答，我会说 : 我学到了一种发现问题与解决问题的方法，这种方.法是在我的学习中慢慢形成的一种潜移默化的思想，关于学到的内容，我们不会一直保留太清晰的记忆，也不会在以后的生活中用到太多，就像买菜不会用

13、到微积分，不会求导，但是，数学方法和思想给我们思考问题所带来的方法论却是大有裨益。这次课程设计，我发现我的很多不足，比如在 matlab上的应用上，我还不熟练，这与我在平时的练习中没有加以重视有关，而且在最优化的很多知识点上，自己还没有很好地掌握。最后 ，我要感谢我们的任课教师王吉波老师，感谢他在给我们上课中的带来的幽默感和知识的传授。在此，祝愿老师身体健康，工作顺利。完稿日期 : 2014年 6 月 21 日第 8页最优化方法课程设计沈阳航空航天大学课程设计用纸参考文献参考文献1陈宝林 . 最优化理论与算法 m. 北京 , 清华大学出版社 ,2013. 2刘卫国 . matlab程序设计教程

14、 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=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)第 10 页.最优化方法课程设计沈阳航空航天大学课程设