《最优化方法课程设计参考模.docx》由会员分享，可在线阅读，更多相关《最优化方法课程设计参考模.docx（27页珍藏版）》请在课桌文档上搜索。
1、最优化方法课程设计题目：共甄梯度法算法分析与实现院系：数学与计算科学学院专业：数学与应用数学姓名：梁婷艳学号：学00730103指导教师：李丰兵II期：2015年12月30日摘要在各种优化算法中，共牝梯度法是非常重要的一种。本文主要介绍的共扼梯度法是介于最速下降法与牛顿法之间的一种无约束优化算法，它具有超线性收敛速度，而且算法结构简单，容易编程实现。在本次实验中，我们首先分析共牝方向法、对该算法进行分析，运用基于共趣方向的一种算法一共甄梯度法进行无约束优化问题的求解。无约束最优化方法的核心问题是选择搜索方向。共趣梯度法的基本思想是把共辗性与最速下降方法相结合，利用已知点处的梯度构造一组共牝方向
2、，并沿这组方向进行搜索，求出目标函数的极小点。根据共牝方向的基本性质，这种方法具有二次终止性。再结合该算法编写matlab程序，求解无约束优化问题，再结合牛顿算法的理论知识，编写matlab程序，求解相同的无约束优化问题，进行比较分析，得出共轲梯度法和牛顿法的不同之处以及共趣梯度法的优缺点。共辗梯度法仅需利用一阶导数信息，避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共趣梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。共也梯度法是一个典型的共也方向法，它的每一个搜索方向是互相共牝的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此
3、，存储量少，计算方便。关键词：共飘梯度法；超线性收敛；牛顿法；无约束优化AbstractInavarietyofoptimizationalgorithms,conjugategradientmethodisaveryimportantone.Inthispaper,theconjugategradientmethodisbetweenthesteepestdescentmethodandNewtonmethodforunconstrainedoptimizationbetweenamethod,ithassuperlinearconvergencerate,andthealgorithmis
4、simpleandeasyprogramming.Inthisexperiment,wefirstanalyzetheconjugatedirectionmethod,thealgorithmanalysis,theuseofaconjugatedirection-basedalgorithm-conjugategradientmethodforunconstrainedoptimizationproblems.Unconstrainedoptimizationmethodistoselectthecoreissueofthesearchdirection.Conjugategradientm
5、ethodisthebasicideaoftheconjugatedescentmethodwiththemostcombinedpointsinthegradientusingtheknownstructureofasetofconjugatedirections,andsearchalongthedirectionofthisgroup,findtheminimumpointofobjectivefunction.Accordingtothebasicnatureoftheconjugatedirection,thismethodhasthequadratictermination.Com
6、binedwiththepreparationofthisalgorithmmatlabprogramforsolvingunconstrainedoptimizationproblems,combinedwithNewton,Stheoryofknowledge,writingmatlabprogramtosolvethesameproblemofunconstrainedoptimization,comparisonanalysis,theconjugategradientmethodandNewtonmethoddifferentOfficeandtheadvantagesanddisa
7、dvantagesoftheconjugategradientmethod.Conjugategradientmethodusingonlyfirstderivativeinformation,toavoidtheNewtonmethodrequiresstorageandcomputingtheinverse11essematrixandshortcomings,isnotonlytheconjugategradientmethodtosolvelargelinearsystemsoneofthemostuseful,butalsolarge-scalesolutionnonlinearop
8、timizationalgorithmisoneofthemosteffective.Conjugategradientmethodisatypicalconjugatedirectionmethod,eachofitssearchdirectionisconjugatetoeachother,andthesearchdirectiondisjustthenegativegradientdirectionwiththelastiterationofthesearchdirectionoftheportfolio,therefore,storagelesscomputationalcomplex
9、ity.Keywords：Conjugategradientmethod;Superlinearconvergence;NewtonmethodUnconstrainedoptimization目录K引言72、共扼梯度法的描述72.1共轴方向法72.2共轲梯度法82.3Armijo准则63、数值实验73.1代码实现73.2算法测试83.3结果分析104、算法比较104.1牛顿法的构造104.2算法实现114.3算法测试124.4算法比较135、总结255.1总结概括135.2个人感言14166、参考文献:1、引言在各种优化算法中，共匏梯度法(ConjugateGradient)是非常重要的一种
10、。其优点是所需存储量小，具有N步收敛性，稳定性高，而且不需要任何外来参数。共短梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共粗梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。共辗梯度法最早是又HeSteneS和StiefIe(1952)提出来的，用于解正定系数矩阵的线性方程组，在这个基础上，FIetCher和ReeVeS(1964)首先提出了解非线性最优化问题的共辗梯度法。由于共粗梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现
11、在共甄梯度法已经广泛地应用与实际问题中。共粗梯度法是一个典型的共趣方向法，它的每一个搜索方向是互相共粗的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此,存储量少，计算方便。2、共扼梯度法的描述2.1共扼方向法共轲方向法是介于最速下降法与牛顿法之间的一个方法。它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了存贮和计算牛顿法所需要的二阶导数信息。共牝方向法是从研究二次函数的极小化产生的，但是它可以推广到处理非二次函数的极小化问题。一般共牝方向法步骤如下：算法2.1.1(般共轲方向法)给出/的初始点/,步1计算go=VA/)步2计算/,使4瓜0步3令女=0步4计算
12、叫和%使得步5计算d*+使得dtGdj=0,y=0,l,步6令左:=左+1,转步4共飘方向法的一个基本性质是：只要执行精确线性搜索，就能得到二次终止性。这就是下面的共飘方向法基本定理。定理2.1.1(共短方向法基本定理)对于正定二次函数，共短方向法之多经n步精确线性搜索终止：且每一看“都是f(x)在/和方向d。,d,所张成的线性流行*=/+盲%4，VaJ中的极小点。2.2共施梯度法共期Ii梯度法是最着名的共牝方向法，它首先由Hestenes和Stiefel(1952)提出来作为解线性方程组的方法。由于解线性方程组等价于极小化一个正定二次函数，故1964年Fletcher和Reeves提出了无约
13、束极小化的共牝梯度法，它是直接从Hestenes和Stiefel解线性方程组的共匏梯度法发展而来的。共匏方向法基本定理告诉我们，共飘性和精确线性搜索产生二次终止性。共甄梯度法就是使得最速下降方向具有共牝性，从而提高算法的有效性和可靠性。下面针对二次函数情形讨论共牝梯度法，我们先给出共牝梯度法的推导。设/(x)=-xGx+brx+c2.1)其中G是“X对称正定矩阵，人是l向量，C是实数。/的梯度为g(x)=Gx+b2.2)令儿=go2.3)则玉=Xtl+o由精确线性搜索性质，g：4=o令2.4)2.5)4=当+AA选择耳，使得JlrG0-0.2.6)2.7)对(2.2.6)两边同乘以片G,得=以
14、飙=g1r(g1-g0)_girg1/Gdo儿(gg)SoSo完整版学习资料分享一2.8)由共牝方向法基本定理，g；4=0,7=0,1。利用（2.2.3）和（2.2.6）,可知g；go=O，g；gi=。.(2.2.9)又令4=Ga+瓦晶+讨，(2.2.10)选择自和自，使得G,=0,=O,1o从而有珞=ggL)=率(2.2.11)43-&)g|g一般地，在第攵次迭代，令&=-&+44，(2.2.12)选择4，使得dG,=O,i=0,L,Jt-lo也假定gdi=0,g：g=0,i=0,l,*,-lf(2.2.13)对(2.2.12)左乘46,7=0,l,-l,则6=g*G/=g*(gj+-gj)
15、；=Q(2214)由(2.2.13),=WORD完整版-可编辑-专业资料分享j+=0J=O,L/-2,gigj=0-=o,左-1,故得月3,/W.，.加-2和(2. 2, 15)O_g(g-g-j一_gg*14(g*-&T)g* 2. 16)因此，共匏梯度法的公式为*+=川+%4 2. 17)其中，在二次函数情形，1.dlGdk,一般地，4由精确线性搜索得到，当然也可以由非线性搜索得到，=-g*+1+&力，(2.2.18)=g翠(g.!妲(Crowder-Wolfe公式)(2.2.19)=母啜坦.(F1etcher-Reeves公式)(2.2.20)8k8k另两个常用的公式为氏=g*.(g=_
16、区2,(POIak-Ribiere-Polyak公式)(2.2.21)乱g*A=-吗迎1.（Dixon公式）（2,2,22）由上面的公式可见，共牝梯度法具有二次终止性（即对于二次函数，算法在有限步终止），所以共牝梯度法是一个很吸引人的方法。共短梯度法步骤如下：算法2.2.1（共血梯度法）步0给定迭代精度0e00证：不是一般性,不放假设xi是无穷序列,此时有g)M0,因dk=-gt+AMT故有或4=Tl心+以息九=T闻ok(wKl)类似地，：AeKJ也是有界序列，故存在子列x：火eKI收敛到；，这里K2uKl是无穷子序列，于是可得r=IimUJ=(Iim)=)-k(wK2)(,2故有G*)=(V
17、)=r.(2.2.23)下面用反证法证明g(x*)=0.如果不然，即g(x)H0,则对于充分小0,有f(x+adt)0,有f(x*+)=f(k+&4)/(Z+adk)对于ZeK2uKl,令&T8对上式去极限得=WORD完整版-可编辑-专业资料分享=/U)f(x+adi0,使得g()-g(u)4M-v,V,veR若选取的搜索方向4与-质的夹角4满足条件OWaW耳一*,(,5).那么算法2.2.1或者有限步终止，或者Iirng(X*)=0。tw证：不失一般性,不妨假设上是无穷序列.由LiPSChitZ及连续条件和Wolfe准则得=(1-JCoS况即于是利用上式及Wolfe准则可得注意到了(x)是有
18、下界的，由上式不难推得IH+co-这蕴含了当火f8时,有IgJfO.证毕2.3Armijo准则Armijo准则是指:给定4W(Oj),crw(0,0.5),令步长因子*=6.其中是满足下列不等式的最小非负整数：fxk+mdk)fxk)+Nf(xkYdk3.1)可以证明，若f(x)是连续可微的且满足可(，)40,则Armijo准则是有限终止的，即存在正数。，使得对于充分大的正整数m,(2.3.1)式成立.也就是说，目标函数/的下降要与步长和下降方向成一定的比例。为了程序实现的方便，我们将ArmijO准则写成下列详细的算法步骤。算法2.3.1(Armijo准则)步0给定夕6(0,1)qe(0,0.
19、5).令加:=0.步1若不等式成立，置/+l:=/+管4，停算，否则，转步2.步2mk:=/+!,转步1.3、数值实验3.1代码实现在共辗梯度法的实际使用中，通常在迭代步或+1步之后，重新取负梯度方向作为搜索方向，我们称之为再开始共辗梯度法。这是因为对于一般非二次函数而言，步迭代后共牝梯度法产生的搜索方向往往不再具有共粗性。而对于大规模问题，常常每机(m或?)步就进行再开始。此外，当搜索方向不是下降方向时，也插入负梯度方向作为搜索方向。基于Armijo非精确线性搜索的再开始FR共辆梯度法的MatIab程序如下：(分别新建frcg.M,fun.M,gfun.M三个M文件)functionx,va
20、l,k=frcg(fun,gfun,x)%功能：用FR共粗梯度法求解无约束问题：minf(x)%输入：x0是初始点，fun,gfun分别是目标函数和梯度%输出：X,Val分别是近似最优点和最优值，k是迭代次数.maxk=5000;%最大迭代次数rho=0.6;sigma=O.4;k=0;epsilon=le4;n=length(x);whiIe(k=O.0)d=-g；endendif(norm(g)epsilon),break;end%检验终止条件m-0;mk-0;while(m20)%Armijo搜索if(feval(fun,x0+rhom*d)feval(fun,xO)+sigma*rho
21、m*g,*d)mk=m;break;endm=n+l;endXO=Xo+rhomk*d;val=feval(fun,x);g=g;d=d;k=k+l;endx=x;val=feval(fun,x);3.2算法测试我们通过求解两个无约束优化问题来验证算法的稳定性和准确性。问题一：求解无约束优化问题min/(x)=3x：+_lx；_XX,-2X,该问题的有精确解瞧/22f=(U)T,f(x*)=-1问题二：求解无约束优化问题m:n/(x)=100(xl2-x2)2+(xl-I)2,该问题的有精确解/=(1,1)7,/(x*)=0。解：利用程序3.1求解以上两个问题，终止准则为v/o)qot,分别修
22、改目标函数和梯度如下：fun.M文件functionf=fun(x)%目标函数f=(3*x(l)2)2+x(2)22-(l)*x(2)-2*x(l);%问题一函数%f=100*(x(l)2-(2)2+(x(l)-l)2;%问题二函数gfun.M文件functiongf=gfun(x)%目标函数的梯度函数gf=3*x(l)-(2)-2,x(2)-(l);%问题一梯度函数%gf=400*x(1)*(x(1)2-(2)+2*(x(1)-1),-200*(x(l)2-(2)*;%问题二梯度函数分别取不同的起始点的数值结果如下表：表3.1问题一FR共粗梯度法的数值结果初始点(/)迭代次数()目标函数值(
23、/UJ)最优解()12-1.000011-1.000012-LOooo15-1.0000137.0000表3.2问题二FR共牝梯度法的数值结果初始点（XO）迭代次数（k）目标函数值（/（/）最优解（X*）281.8462e-007131.4796e-007153.2749e-007224.0962e-008183.5854e-0073.3结果分析由表3.1和表3.2可见FR共短梯度法在不同的初始点，求解最优解的迭代次数有所差异，分析可见，在接近精确解的输出点处的迭代次数会相对较少。并且计算结果比较稳定，误差在忽略范围内。4、算法比较4.1牛顿法的构造牛顿法是一种经典的无约束优化算法，并且因其收
24、敛速度快以及具有自适应性等优点而至今仍受到科技工作者的青睐牛顿法也是求解无约束优化问题最早使用的经典算法之一.其基本思想是用迭代点Z处的一阶导数（梯度）和二阶导数(HeSSe阵)对目标函数进行二次函数近似，然后把二次模型的极小点作为新的迭代点，并不断重复这一过程，直至求得满足精度的近似极小点.下面来推导牛顿法的迭代公式.设/(x)的HeSSe阵G(X)=V2/(X)连续，截取其在处的泰勒展开式的前三项得9x)=A+(X-Xjt)+gx-jG(X-XJ其中人=/(X*),=Wi)sG=/八4).求二次函数q*(X)的稳定点，得弘(X)=g*+Gx-xjt)=0.若G,非奇异，那么解上面的线性方程
25、组即得牛顿法的迭代公式x*+=xkIGjgk.在迭代公式中每步迭代需求Hesse阵的逆Gj,在实际计算中可通过先解Gm=-&得4,然后令XN=X+4来避免求逆。这样，可以写出基本牛顿法的步骤如下：算法4.1.1(基本牛顿法)步0给定终止误差Oe输出：X,VaI分别是近似最优点和最优值，k是迭代次数.maxk=5000;%最大迭代次数rho=0.5;sigma=0.4;k=0;epsilon=le-5;whiIe(kmaxk)g=feral(gfun,x);%计算梯度d=-g;%计算搜索方向if(norm(d)epsi1on),break;endm=0;mk=0;while(m20)%rmijo
26、搜索if(feral(fun,xO+rhom*d)feral(fun,x)+Sigma*rhom*g*d)=WORD完整版一可编辑.专业资料分享=mk=m;break;endm=ml;endXo=Xo+rho%k*d;k=k+l;endx=x;val=feral（fun,x）;4.3算法测试使用此牛顿法求解此前的问题一和问题二，取不同的起始点的数值结果分别如下表：问题一：表4.1问题一牛顿法的数值结果初始点（XO）迭代次数（）目标函数值（/（xt）最优解（4）23-1,000023-1.000025-1.000037-1.000025-1.0000问题二:表4.2问题二牛顿法的数值结果初始点（
27、XO）迭代次数（）目标函数值（/（X）最优解（5）382.8220e-009281.4429e-011371.3597e-009392.1601e-009371.4698e-0094.4算法比较通过求解问题一和问题二，由上表可以看出，共匏梯度法的收敛速度是比较令人满意的，在相同初始点处开始求解，使用牛顿法所需要的迭代次数共轲梯度法的迭代次数的两倍。虽然在算法设计上比较相似，但是微小的改进，使得共轲梯度法无论是准确性上还是效率上都优于牛顿法。5、总结5.1总结概括求解最优问题是一个艰难而具有挑战性的过程，最优化方法是近几十年形成的一门运用错误！超链接引用无效.研究各种系统的优化途径及方案，为决策
28、者提供科学决策的依据的学科，它涵盖了无约束最优化问题、凸集与凸函数、等式约束最优化问题和不等式约束最优化问题等知识点。本次课程设计，我们小组成员通过老师的点拨以及激烈的讨论，对该门课程中的无约束最优化问题进行了一定程度地了解和研究，无约束最优化方法的核心问题是选择搜索方向。过程中,我们运用基于共牝方向的一种算法一一共粗梯度法进行处理。我们从理论的来源、推导过程出发进行深入，共短梯度法最初由Hesteness和Stiefel于1952年为求解线性方程组而提出。后来，人们把这种方法用于求解无约束最优化问题。共粗梯度法的基本思想是把共粗性与最速下降方法相结合，利用己知点处的梯度构造一组共牝方向，并沿
29、这组方向进行搜索，求出目标函数的极小点。根据共牝方向的基本性质，这种方法具有二次终止性。之后，我们还实现了MATLAB程序实现的效果。我们对问题进行数值求解时，采用了大量的数据实例进行验证、对比，并且选择了较有代表性的几例编入我们的课程设计论文当中。最后，我们还将该方法与处理同类问题的牛顿法在算法和程序上的进行了效率等方面的比较，更进一步地加深了对它的理解也提高了处理该问题的水平能力.5.2个人感言通过本次试验，我学会了应该怎么从一个问题出发，对该问题进行研究：首先要对问题有一个大概的了解，通过查阅资料，对问题有了深入了解，然后确定问题的研究方向，以及要研究方向所需要进行的工作，然后一步步去完
30、成,如：在研究共轲梯度法的时侯，我了解到，共趣梯度法的适用范围很广，其算法也有很多研究方向，例如：无约束优化问题；非线性共施梯度法；非单调线搜索;共轲条件;全局收敛等等。结合所学知识，确定了研究方向，进行深入研究，通过分工合作，完成本次课程设计，其中由我负责的共牝梯度法与牛顿法的算法比较，首先理解了共趣梯度法与牛顿法后，我通过这两个算法研究同一个问题时的结果进行分析，得出共辗梯度法的优缺点，在本次实验中，我们充分发挥了团队协作精神，充分利用每个队员的优点长处，进行合理分工协作，共同完成课设。6、参考文献：1张光澄非线性最优化计算方法M.北京：高等教育出版社，2005.2席少霖.非线性最优化计算方法M.北京：高等教育出版社，1992.3薛嘉庆.最优化原理与方法M北京：清华大学出版社，2003.4邓乃杨.无约束最优化计算方法M.北京:科学出版社，1982.5袁亚湘，孙文瑜.最优化理论与方法M.北京:科学出版社，1993.
