线性共轭梯度法解决二次正定优化问题

最优化理论与算法实验报告(四)实验名称线性共轭梯度法解决二次正定优化问题实验时间姓名专业班级学号成绩一、实验目的和内容实验目的：通过实验,让学生掌握线性共轭梯度法解决二次正定优化问题的具体实现,同时对于具体的问题设计,让学生根据在实验中出现的数值计算结果,分析并发现共轭梯度法存在的不足.理解共轭梯度法的基本思想.实验内容：请采用FR方法采用精确的线搜索求解问题2221212min()448xfxxxxx终止的准则610kg,10,0Tx.二、相关背景知识介绍共轭梯度法在迭代过程中通过对负梯度方向进行适当校正获得共轭方向,当算法用于正定二次函数时，可以在有限多次迭代后终止，得到最优解.设1()2TTfxxGxbxc其中G为nn正定矩阵，则()gxGxb.对二次函数总有:11kkkkkkggGxxGd1）设0x为初始点.首先取00dg，令1000xxd（0为精确步长因子）则有：100Tgd（精确一维搜索性质）.2）令1100dgd，适当选择0，使100TdGd，得101101100001000()()TTTTTTgGdgggggdGddgggg（从而得到1d）且有正交性：210Tgd，200Tgd,210Tgg，200Tgg3）再令220011dgdd，适当选择0，1，使得20TidGd（0,1i），由此得：00，22122112111()()TTTTgggggdgggg4）一般地，在第k次迭代中，令10kkkiiidgd适当选取i，使0TkidGd（0,,1ik），可得到11()()TTkikiiiTTiiiiigGdgggdGddgg（0,,1ik）利用归纳法可以证明:0Tkigd（0,,1ik），再由ig与id的关系得：0Tkigg（0,,1ik）所以当0,,2ik时，0i，而111111()()TTkkkkkkTTkkkkkgggggdgggg.共轭梯度法的迭代公式为：1kkkkxxd（kd为共轭方向，k为最佳步长因子）对二次函数:TkkkTkkgddGd；算法如下描述:Step1:取初始点1nx,如果1g,则停机;否则11dg,1kStep2:计算精确步长,,kkkkkgdadGd,1kkkkxxad如果1kg,则停机;否则gotoStep3；Step3:11TkkkTkkgggg,11kkkkdgd1kk,gotoStep2三、代码functionf=getd(x0,t)x=x0;symsxiyiaf=xi^2+4*yi^2-4*xi-8*yi;fx=diff(f,xi);fy=diff(f,yi);fx=subs(fx,{xi,yi},x0);fy=subs(fy,{xi,yi},x0);fi=[fx,fy];c=0;whiledouble(sqrt(fx^2+fy^2))ts=-fi;ifc=0s=-fi;elses=s1;endx=x+a*s;f=subs(f,{xi,yi},x);f1=diff(f);f1=solve(f1);iff1~=0ai=double(f1);elsebreakx,f=subs(f,{xi,yi},x),cendx=subs(x,a,ai);f=xi-xi^2+2*xi*yi+yi^2;fxi=diff(f,xi);fyi=diff(f,yi);fxi=subs(fxi,{xi,yi},x);fyi=subs(fyi,{xi,yi},x);fii=[fxi,fyi];d=(fxi^2+fyi^2)/(fx^2+fy^2);s1=-fii+d*s;c=c+1;fx=fxi;fy=fyi;endx,f=subs(f,{xi,yi},x),c四、数值结果f=getd([0,0],0.000001)运算次数8最优解X1=0.2500,x2=-0.2500函数最小值0.1250五、计算结果的分析最速下降法在接近极小值时步长越小，前进越慢。牛顿法要求二阶导数，计算量很大。共轭梯度法是介于最速下降和牛顿法之间的算法，克服了最速下降法的收敛速度慢的缺点，还减少了计算量。六、计算中出现的问题，解决方法及体会群众的力量是伟大的，我在对于这一次的实习报告时，其实我对于这方面的学习还是不够的，但是我在编写代码的时候，虚心请教同学，在遇到了一些问题的时候，通过自己查找资料和请教于同学，得以将问题解决。所以这一次的实验不是我一个人的努力结果，对于帮助我的同学，他们的帮助是我进步的源泉！实验原始数据记录教师评语指导教师：年月日