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

《《最最优优化化方方法法》》课课程程设设计计题目：共轭梯度法算法分析与实现院系：数学与计算科学学院专业：数学与应用数学姓名：梁婷艳学号：0800730103指导教师：李丰兵日期：2015年12月30日摘要在各种优化算法中，共轭梯度法是非常重要的一种。本文主要介绍的共轭梯度法是介于最速下降法与牛顿法之间的一种无约束优化算法，它具有超线性收敛速度,而且算法结构简单,容易编程实现。在本次实验中,我们首先分析共轭方向法、对该算法进行分析，运用基于共轭方向的一种算法—共轭梯度法进行无约束优化问题的求解。无约束最优化方法的核心问题是选择搜索方向。共轭梯度法的基本思想是把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。根据共轭方向的基本性质，这种方法具有二次终止性。再结合该算法编写matlab程序，求解无约束优化问题，再结合牛顿算法的理论知识，编写matlab程序，求解相同的无约束优化问题，进行比较分析，得出共轭梯度法和牛顿法的不同之处以及共轭梯度法的优缺点。共轭梯度法仅需利用一阶导数信息，避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便。关键词：共轭梯度法；超线性收敛；牛顿法；无约束优化AbstractInavarietyofoptimizationalgorithms,conjugategradientmethodisaveryimportantone.Inthispaper,theconjugategradientmethodisbetweenthesteepestdescentmethodandNewtonmethodforunconstrainedoptimizationbetweenamethod,ithassuperlinearconvergencerate,andthealgorithmissimpleandeasyprogramming.Inthisexperiment,wefirstanalyzetheconjugatedirectionmethod,thealgorithmanalysis,theuseofaconjugatedirection-basedalgorithm-conjugategradientmethodforunconstrainedoptimizationproblems.Unconstrainedoptimizationmethodistoselectthecoreissueofthesearchdirection.Conjugategradientmethodisthebasicideaoftheconjugatedescentmethodwiththemostcombinedpointsinthegradientusingtheknownstructureofasetofconjugatedirections,andsearchalongthedirectionofthisgroup,findtheminimumpointofobjectivefunction.Accordingtothebasicnatureoftheconjugatedirection,thismethodhasthequadratictermination.Combinedwiththepreparationofthisalgorithmmatlabprogramforsolvingunconstrainedoptimizationproblems,combinedwithNewton’stheoryofknowledge,writingmatlabprogramtosolvethesameproblemofunconstrainedoptimization,comparisonanalysis,theconjugategradientmethodandNewtonmethoddifferentOfficeandtheadvantagesanddisadvantagesoftheconjugategradientmethod.Conjugategradientmethodusingonlyfirstderivativeinformation,toavoidtheNewtonmethodrequiresstorageandcomputingtheinverseHessematrixandshortcomings,isnotonlytheconjugategradientmethodtosolvelargelinearsystemsoneofthemostuseful,butalsolarge-scalesolutionnonlinearoptimizationalgorithmisoneofthemosteffective.Conjugategradientmethodisatypicalconjugatedirectionmethod,eachofitssearchdirectionisconjugatetoeachother,andthesearchdirectiondisjustthenegativegradientdirectionwiththelastiterationofthesearchdirectionoftheportfolio,therefore,storagelesscomputationalcomplexity.Keywords:Conjugategradientmethod;Superlinearconvergence;NewtonmethodUnconstrainedoptimization目录1、引言.......................................................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个人感言..............................................146、参考文献：................................................161、引言在各种优化算法中，共轭梯度法（ConjugateGradient）是非常重要的一种。其优点是所需存储量小，具有N步收敛性，稳定性高，而且不需要任何外来参数。共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。共轭梯度法最早是又Hestenes和Stiefle（1952）提出来的，用于解正定系数矩阵的线性方程组，在这个基础上，Fletcher和Reeves（1964）首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用与实际问题中。共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便。2、共轭梯度法的描述2.1共轭方向法共轭方向法是介于最速下降法与牛顿法之间的一个方法。它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了存贮和计算牛顿法所需要的二阶导数信息。共轭方向法是从研究二次函数的极小化产生的，但是它可以推广到处理非二次函数的极小化问题。一般共轭方向法步骤如下：算法2.1.1（一般共轭方向法）给出*x的初始点0x，步1计算)(00xfg步2计算0d，使000gdT步3令0k步4计算k和1kx，使得步5计算1kd使得01jTkGdd,kj,,1,0。步6令1:kk,转步4共轭方向法的一个基本性质是：只要执行精确线性搜索，就能得到二次终止性。这就是下面的共轭方向法基本定理。定理2.1.1（共轭方向法基本定理）对于正定二次函数，共轭方向法之多经n步精确线性搜索终止；且每一1ix都是)(xf在0x和方向idd,,0所张成的线性流行jijjjdxxx,00中的极小点。2.2共轭梯度法共轭梯度法是最着名的共轭方向法，它首先由Hestenes和Stiefel（1952）提出来作为解线性方程组的方法。由于解线性方程组等价于极小化一个正定二次函数，故1964年Fletcher和Reeves提出了无约束极小化的共轭梯度法，它是直接从Hestenes和Stiefel解线性方程组的共轭梯度法发展而来的。共轭方向法基本定理告诉我们，共轭性和精确线性搜索产生二次终止性。共轭梯度法就是使得最速下降方向具有共轭性，从而提高算法的有效性和可靠性。下面针对二次函数情形讨论共轭梯度法，我们先给出共轭梯度法的推导。设cxbGxxxfTT21)((2.2.1)其中G是nn对称正定矩阵，b是1n向量，c是实数。f的梯度为bGxxg)((2.2.2)令00gd(2.2.3)则0001dxx(2.2.4)由精确线性搜索性质，001dgT(2.2.5)令0011dgd(2.2.6)选择0，使得001GddT.(2.2.7)对（2.2.6）两边同乘以GdT0，得001101001100011)()(ggggggdgggGddGdgTTTTTT.(2.2.8)由共轭方向法基本定理，02iTdg，1,0i。利用（2.2.3）和（2.2.6），可知002ggT,012ggT.(2.2.9)又令110022ddgd,(2.2.10)选择0和1