共轭梯度算法分析与实现

编号:_09《《最最优优化化方方法法》》课课程程设设计计题目：共轭梯度算法分析与实现院系：数学与计算科学学院专业：数学与应用数学姓名学号：指导教师：日期：2013年12月23日摘要在最优化计算中，共轭梯度法是非常重要的一种方法。共轭梯度法是一种改进的最速下降法，介于最速下降法与牛顿法之间的一种无约束优化算法,是为求解目标函数为二次函数的问题而设计的一类算法。它利用目标函数的梯度逐步产生共轭方向并将其作为搜索方向的方法，收敛速度快。共轭梯度法仅需利用一阶导数信息，避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，具有二次终止性。关键词：共轭梯度法；牛顿法；二次函数；无约束优化AbstractInthecalculationofoptimizationmethod,conjugategradientmethodisaveryimportantone.TheconjugategradientmethodisaunconstrainedoptimizationmethodbetweenthesteepestdescentmethodandNewtonmethod,andsovetheobjectivefunctionfortheoriginalquadraticfunctionproblemsanddesignforaclassofalgorithm.Conjugategradientmethodusingonlyfirstderivativeinformation,toavoidtheNewtonmethodrequiresstorageandcomputingtheinverseHessematrixandshortcomings,thismethodhasthequadratictermination.Keywords:Conjugategradientmethod;Newtonmethod;Unconstrainedoptimization目录1、引言........................................................................................................................12、共轭梯度算法的描述.......................................................................................12.1无约束优化问题概述.......................................................................................12.2共轭方向...........................................................................................................12.3共轭梯度法.......................................................................................................12.4共轭梯度算法的步骤.......................................................................................23、数值实验..............................................................................................................23.1代码实现...........................................................................................................23.2算法测试...........................................................................................................33.3结果分析...........................................................................................................54、算法比较..............................................................................................................54.1最速下降法描述...............................................................................................64.1.1最速下降方向...............................................................................................64.1.2最速下降法...................................................................................................64.2最速下降法实现...............................................................................................64.3最速下降法测试...............................................................................................74.4共轭梯度法与最速下降法比较........................................................................85、总结.......................................................................................................................85.1总结概括...........................................................................................................85.2个人感言...........................................................................................................96、参考文献：.........................................................................................................9最优化方法课程设计11、引言共轭梯度法最早是由Hesternes和Stiefle(1952)提出来的，用于解正定系数矩阵的线性方程组，在这个基础上，Fletcher和Reeves(1964)首先提出了解非线性最优化问题的共轭梯度法。在各种优化算法中，共轭梯度法（ConjugateGradient）是非常重要的一种。是一种介于最速下降法与牛顿法之间的优化算法，是为求解目标函数为二次函数的问题而设计的一类算法。它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。可微的非二次函数在极小点附近的形态近似于二次函数，因此共轭梯度法也能用于求可微的非二次函数的无约束极小问题。共轭梯度法是一个典型的共轭方向法，它在共轭方向法基础上增加了一些性质:计算当前方向计算当前方向只需用到前一方向，对其他方向则无要求；计算出来的当前方向自动与前面所有方向共轭，因此，不需耗费大量内存存储所有方向，也节省了计算时间。2、共轭梯度法的描述2.1无约束优化问题概述一个非线性规划问题的自变量x没有任何约束，或说可行域既是整个n维向量空间：rnx，称这样的非线性规划问题为无约束问题：)(minxf或)(minxfRnx2.2共轭方向无约束问题最优化方法的核心问题是选择搜索方向。以正定二次函数为例，来观察两个方向关于矩阵Ａ共轭的几何意义。设有二次函数：f(x)=1/2(x-x*)TA(x-x*),其中A是n×n对称正定矩阵，x*是一个定点，函数f(x)的等值面1/2(x-x*)TA(x-x*)=c是以x*为中心的椭球面，由于▽f(x*)=A(x-x*)=0，A正定，因此x*是f(x)的极小点。设x(1)是在某个等值面上的一点，该等值面在点x(1)处的法向量▽f(x(1))=A(x(1)-x*)。又设d(1)是这个等值面在d(1)处的一个切向量。记作d(2)=x*-x(1)。最优化方法课程设计2自然，d(1)与▽f(x(1))正交，即d(1)T▽f(x(1))=0，因此有d(1)TAd(2)=0，即等值面上一点处的切向量与由这一点指向极小点的向量关于A共轭。2.3共轭梯度法共轭梯度法是最著名的共轭方向法，它首先由Hestenes和Stiefel（1952）提出来作为解线性方程组的方法。由于解线性方程组等价于极小化一个正定二次函数，故1964年Fletcher和Reeves提出了无约束极小化的共轭梯度法，它是直接从Hestenes和Stiefel解线性方程组的共轭梯度法发展而来的。共轭梯度法的基本思想是把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。根据共轭方向的基本性质，这种方法具有二次终止性。共轭梯度法就是使得最速下降方向具有共轭性，从而提高算法的有效性和可靠性。在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。2.4共轭梯度算法的步骤共轭梯度算法步骤如下：Step1给定迭代精度10和初始点0x.计算)(00xfg.令0:k.Step2若kg,停算,输出kxx*.Step3计算搜索方向kd:1,,,0,11kdgkgdkkkkk其中当1k时,111kTkkTkkgggg确定1k.Step4利用精确(或非精确)线搜索方法确定搜索步长k.Step5令kkkkdxx:1,并计算)(11kkxfg.Step6令1:kk,转步Step1.3、数值实验3.1代码实现最优化方法课程设计3共轭梯度法的Matlab程序如下：分别新建Conjugate_Gradient_Method.m、grad_obj.m、line_search.m、obj.m文件Conjugate_Gradient_Method.m文件如下：function[x,iter,val]=Conjugate_Gradient_Method(x,eps)k=0;x_mat(:,1)=x;%存储每一次迭代得到的点xx_old=x;dy_old=grad_obj(x_old);d_old=-dy_old;whilenorm(dy_old)epslamb