最优化方法课程设计参考模.docx

《最优化方法课程设计参考模.docx》由会员分享，可在线阅读，更多相关《最优化方法课程设计参考模.docx（25页珍藏版）》请在第一文库网上搜索。

1、最优化方法课程设计题目：共一梯度法算法分析与实现院系：数学与计算科学学院专业：数学与应用数学姓名：梁婷艳学号：0800730103指导教师：李丰兵日期：2015年12月30日摘要在各种优化算法中，共班梯度法是非常重要的一种。本文主要介绍的共班梯度法是介于最速下降法与牛顿法之间的一种无约束优化算法，它具有超线性收敛速度，而且算法结构简单，容易编程实现。在本次实验中，我们首先分析共甄方向法、对该算法进行分析，运用基于共辄方向的一种算法一共辄梯度法进行无约束优化问题的求解。无约束最优化方法的核心问题是选择搜索方向。共班梯度法的基本思想是把共颖性与最速下降方法相结合，利用已知点处的梯度构造一组共辄方向

2、，并沿这组方向进行搜索，求出目标函数的极小点。根据共辄方向的基本性质，这种方法具有二次终止性。再结合该算法编写mat1ab程序，求解无约束优化问题，再结合牛顿算法的理论知识，编写mat1ab程序，求解相同的无约束优化问题，进行比较分析，得出共把梯度法和牛顿法的不同之处以及共班梯度法的优缺点。共班梯度法仅需利用一阶导数信息，避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共班梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。共班梯度法是一个典型的共辄方向法，它的每一个搜索方向是互相共掘的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此

3、，存储量少，计算方便。关键词：共辗梯度法；超线性收敛；牛顿法；无约束优化AbstractInavarietyofoptimizationa1gorithms,conjugategradientmethodisaveryimportantone.Inthispaper,theconjugategradientmethodisbetweenthesteepestdescentmethodandNewtonmethodforunconstrainedoptimizationbetweenamethod,ithassuper1inearconvergencerate,andthea1gorithmis

4、simp1eandeasyprogramming.Inthisexperiment,wefirstana1yzetheconjugatedirectionmethod,thea1gorithmana1ysis,theuseofaconjugatedirection-baseda1gorithm-conjugategradientmethodforunconstrainedoptimizationprob1ems.Unconstrainedoptimizationmethodistose1ectthecoreissueofthesearchdirection.Conjugategradientm

5、ethodisthebasicideaoftheconjugatedescentmethodwiththemostcombinedpointsinthegradientusingtheknownstructureofasetofconjugatedirections,andsearcha1ongthedirectionofthisgroup,findtheminimumpointofobjectivefunction.Accordingtothebasicnatureoftheconjugatedirection,thismethodhasthequadratictermination.Com

6、binedwiththepreparationofthisa1gorithmmat1abprogramforso1vingunconstrainedoptimizationprob1ems,combinedwithNewtonstheoryofknow1edge,writingmat1abprogramtoso1vethesameprob1emofunconstrainedoptimization,comparisonana1ysis,theconjugategradientmethodandNewtonmethoddifferentOfficeandtheadvantagesanddisad

7、vantagesoftheconjugategradientmethod.Conjugategradientmethodusingon1yfirstderivativeinformation,toavoidtheNewtonmethodrequiresstorageandcomputingtheinverseHessematrixandshortcomings,isnoton1ytheconjugategradientmethodtoso1ve1arge1inearsystemsoneofthemostusefu1,buta1so1arge-sca1eso1utionnon1inearopti

8、mizationa1gorithmisoneofthemosteffective.Conjugategradientmethodisatypica1conjugatedirectionmethod,eachofitssearchdirectionisconjugatetoeachother,andthesearchdirectiondisjustthenegativegradientdirectionwiththe1astiterationofthesearchdirectionoftheportfo1io,therefore,storage1esscomputationa1comp1exit

9、y.Keywords:Conjugategradientmethod;Super1inearconvergence;NewtonmethodUnconstrainedoptimization1、引言72、共粗梯度法的描述72.1共甄方向法72. 2共辗梯度法82. 3Armijo准则63、数值实验73. 1代码实现73. 2算法测试83. 3结果分析104、算法比较104. 1牛顿法的构造105. 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(一般共辗方向法)给出X*的初始点频,步1计算go=V)步2计算d0,使djg0O步

12、3令k=a步4计算和乙+使得步5计算也使得比1G%=0,J=O,1,左。步6令左:=左+1,转步4共掘方向法的一个基本性质是：只要执行精确线性搜索，就能得到二次终止性。这就是下面的共辄方向法基本定理。定理2.1.1(共辄方向法基本定理)对于正定二次函数，共辄方向法之多经n步精确线性搜索终止；且每一九都是/(x)在/和方向do,4所张成的线性流行XX=x+ajdjyaj中的极、j=。,小点。2.2共辗梯度法共粒梯度法是最着名的共掘方向法，它首先由Hestenes和Stiefe1(1952)提出来作为解线性方程组的方法。由于解线性方程组等价于极小化一个正定二次函数，故1964年F1etcher和R

13、eeves提出了无约束极小化的共辄梯度法，它是直接从Hestenes和Stiefe1解线性方程组的共辄梯度法发展而来的。共加方向法基本定理告诉我们，共颖性和精确线性搜索产生二次终止性。共辗梯度法就是使得最速下降方向具有共辗性，从而提高算法的有效性和可靠性。下面针对二次函数情形讨论共辗梯度法，我们先给出共辗梯度法的推导。(2.2.1)f的梯度为(2.2.2)(2.2.3)(2.2.4)(2.2.5)2.6)(2.2.7)(2.2.8)/(x)=-xGx+bX+c其中G是对称正定矩阵，人是x1向量，C是实数。g(x)=Gx+b令d。二-go则X1=X0+C1f0J0由精确线性搜索性质，g：do=。

14、令4=S+选择用，使得d：GdG=0.对(2.2.6)两边同乘以或G,得、=g：Gdo=非(&-go)=.4)Gdod0(g1g0)g0g0-完整版学习资料分享-由共辗方向法基本定理，g=0,z=0,1o利用(223)和(2.2.6),可g；go=O，g；gi=O2.9)又令d2=g2+0OdO2.10)选择A)和4，使得%G4=o,：0,1。从而有A)=，=gf(g2g)=g1(g2-g1)gg1,一般地，在第左次迭代，令dk=-gk+Z44，(2.2.12)选择，使得Gd,=O,z=O,1,左-1。也假定gdi=0,g1kgi=0,z=O,1-1,2.13)对(2.2.12)左乘d：G,/

15、=0,1,左-1,则2.14)由(2.2.13),g；gj+i=。，j=61#2,=。，J=O,1欢-1,故得4=0,/=0,1,左-2和Bk=g；（gkgk-J=g：gk.Idk-（sk-gk-g1k-（2.2.15）因此，共辗梯度法的公式为=%+，2.16）其中，在二次函数情形,-晨4.d；Gdk2.17）一般地，如由精确线性搜索得到，当然也可以由非线性搜索得到,ek+=8k+片4，2.18）4=%1（取+1一呢）（Crowder-Wo1fe公式）（2.2.19）d：（gkgk）二&+*+.（F1etcher-Reeves公式）（2.2.20）SkSk另两个常用的公式为4=义+（g*一取）,（Po1ak-Ribiere-Po1yak公式）（2.2.21）g；gkk=叼生.(Dixon公式)(2.2.22)Gk由上面的公式可见，