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

《《最最优优化化方方法法》》课课程程设设计计题目：共轭梯度法算法分析与实现院系：数学与计算科学学院专业：数学与应用数学姓名：梁婷艳学号：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、引言........................................................................................................................52、共轭梯度法的描述............................................................................................52.1共轭方向法.......................................................................................................52.2共轭梯度法.......................................................................................................62.3Armijo准则.......................................................................................................63、数值实验..............................................................................................................73.1代码实现...........................................................................................................73.2算法测试...........................................................................................................83.3结果分析.........................................................................................................104、算法比较............................................................................................................104.1牛顿法的构造.................................................................................................104.2算法实现.........................................................................................................114.3算法测试.........................................................................................................124.4算法比较..........................................................................................................135、总结.....................................................................................................................175.1总结概括.........................................................................................................135.2个人感言.........................................................................................................146、参考文献：.......................................................................................................16最优化方法课程设计51、引言在各种优化算法中，共轭梯度法（ConjugateGradient）是非常重要的一种。其优点是所需存储量小，具有N步收敛性，稳定性高，而且不需要任何外来参数。共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。共轭梯度法最早是又Hestenes和Stiefle（1952）提出来的，用于解正定系数矩阵的线性方程组，在这个基础上，Fletcher和Reeves（1964）首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用与实际问题中。共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜