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

《最优化方法课程设计参考模.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=_区2,(POIak-Ribiere-Polyak公式)(2.2.21)乱g