求解无约束优化问题的共轭梯度法.doc

(完整word)求解无约束优化问题的共轭梯度法(完整word)求解无约束优化问题的共轭梯度法(完整word)求解无约束优化问题的共轭梯度法求解无约束优化问题的共轭梯度法李芳梅，姚瑞哲指导教师:李良摘要：本文主要针对无约束优化问题，利用共轭梯度法(CG方法）求解此类问题，并得出其迭代次数及问题的解。论文对此种方法给出了具体事例,并对例子进行了matlab软件实现。1.引言共轭梯度法时介于最速下降法与牛顿法之间的一个方法。它仅需利用一阶导数信息,但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点.共轭梯度法最早是由Hestenes和Stiefel（1952)提出来的,用于解正定系数矩阵的线性方程组.由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现已广泛应用与实际问题中。2。共轭梯度法共轭梯度法是共轭方向法的一种。所谓共轭方向法就是其所有的搜索方向都是相互共轭的方法。定义设G是n×n对称正定矩阵，d1，d2是n维非零向量。如果d1TGd2=0，则称向量d1和d2是G—共轭的，简称共轭的.设d1，d2，…，dm是Rn中任一组非零向量，如果diTGdj=0(i≠j）,则称d1，d2，…，dm是G—共轭的,简称共轭的。显然，如果d1，d2，…，dm是共轭的，则它们是线性无关的。算法(共轭梯度法）步1.初始步：给出x0,ε〉0，计算r0=Gx0—b，令d0=-r0,k:=0.步2。如果‖rk‖≤ε，停止。步3。计算αk=rkTrk/dkTGdk，xk+1=xk+αkdk，rk+1=rk+αkGdk，βk=rk+1Trk+1/rkTrk,dk+1=—rk+1+βkdk.步4。令k:=k+1,转步2.共轭梯度法的matlab实现（数值例子）首先建立如下的m.文件function［x，iter］=cgopt(G,b,x0,max_iter，tol)x=x0;fprintf（’\nx0=’)；fprintf(’％10.6f',x0）;r=G＊x-b;%残差d=-r;fork=1：max_iterifnorm(r)〈=toliter=k-1；fprintf(’\nAlgorithmfindsasolution！’)；returnendalpha=(r'*r）/(d’*G*d);%收敛速度xx=x+alpha＊d;rr=r+alpha＊G＊d；beta=(rr'*rr)/（r’*r）;d=—rr+beta＊d;x=xx;r=rr;fprintf(’\nx%d=’,k）；fprintf('％10.6f',x);enditer=max_iter；return然后建立CG_main的m.文件，带入数值例子functionCG_main（)G=［101234；19-12-3;2—173—5；32312-1;4—3-5—115]；b=［12-2714-1712］'；x0=[00000]’;max_iter=1000;tol=1e—6;fprintf('\n')；fprintf（’ConjugateGradiantMethod:\n'）;fprintf('=================\n’);[x,iter］=cgopt（G,b,x0,max_iter,tol)；fprintf（'Iterativenumber:\n％d\n’,iter)；fprintf（'Solution:\n');fprintf('％10.6f’，x)；fprintf('\n================\n’);结论实际上,共轭梯度法是最速下降法的一种改进。它不涉及矩阵,仅仅有向量运算，因而存储量小，适合于维数较高的优化问题。上述数值例子说明了用共轭梯度法求解无约束优化问题的可行性，同时也表明了我们所编写的程序的正确性.参考文献孙文瑜，徐成贤，朱德通。最优化方法（第二版）北京：高等教育出版社，2010。7.