共轭梯度算法分析与实现

PAGE编号:_09《最优化方法》课程设计题目：共轭梯度算法分析与实现院系：数学与计算科学学院专业：数学与应用数学姓名学号：指导教师：日期：2013年12月23日摘要在最优化计算中，共轭梯度法是非常重要的一种方法。共轭梯度法是一种改进的最速下降法，介于最速下降法与牛顿法之间的一种无约束优化算法,是为求解目标函数为二次函数的问题而设计的一类算法。它利用目标函数的梯度逐步产生共轭方向并将其作为搜索方向的方法，收敛速度快。共轭梯度法仅需利用一阶导数信息，避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，具有二次终止性。关键词：共轭梯度法；牛顿法；二次函数；无约束优化AbstractInthecalculationofoptimizationmethod,conjugategradientmethodisaveryimportantone.TheconjugategradientmethodisaunconstrainedoptimizationmethodbetweenthesteepestdescentmethodandNewtonmethod,andsovetheobjectivefunctionfortheoriginalquadraticfunctionproblemsanddesignforaclassofalgorithm.Conjugategradientmethodusingonlyfirstderivativeinformation,toavoidtheNewtonmethodrequiresstorageandcomputingtheinverseHessematrixandshortcomings,thismethodhasthequadratictermination.Keywords:Conjugategradientmethod;Newtonmethod;Unconstrainedoptimization目录1、引言 12、共轭梯度算法的描述 12.1无约束优化问题概述 12.2共轭方向 12.3共轭梯度法 2HYPERLINK3.1代码实现 2HYPERLINK3.2算法测试 3HYPERLINK4、算法比较 54.1最速下降法描述 64.1.1最速下降方向 64.1.2最速下降法 6HYPERLINK4.2最速下降法实现 6HYPERLINK5、总结 8HYPERLINK\l"_5.1_总结概括"5.1总结概括 8HYPERLINK\l"_5.3_个人感言"5.2个人感言 9HYPERLINK\l"_6、参考文献："6、参考文献： 9最优化方法课程设计PAGEPAGE101、引言共轭梯度法最早是由Hesternes和Stiefle(1952)提出来的，用于解正定系数矩阵的线性方程组，在这个基础上，Fletcher和Reeves(1964)首先提出了解非线性最优化问题的共轭梯度法。在各种优化算法中，共轭梯度法（ConjugateGradient）是非常重要的一种。是一种介于最速下降法与牛顿法之间的优化算法，是为求解目标函数为二次函数的问题而设计的一类算法。它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。可微的非二次函数在极小点附近的形态近似于二次函数，因此共轭梯度法也能用于求可微的非二次函数的无约束极小问题。共轭梯度法是一个典型的共轭方向法，它在共轭方向法基础上增加了一些性质:计算当前方向计算当前方向只需用到前一方向，对其他方向则无要求；计算出来的当前方向自动与前面所有方向共轭，因此，不需耗费大量内存存储所有方向，也节省了计算时间。2、共轭梯度法的描述2.1无约束优化问题概述一个非线性规划问题的自变量x没有任何约束，或说可行域既是整个n维向量空间：，称这样的非线性规划问题为无约束问题：或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)。自然，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给定迭代精度和初始点.计算.令.Step2若,停算,输出.Step3计算搜索方向:其中当时,确定.Step4利用精确(或非精确)线搜索方法确定搜索步长.Step5令,并计算.Step6令,转步Step1.3、数值实验3.1代码实现共轭梯度法的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)>epslambda=line_search(x_old,d_old);%步长x_new=x_old+lambda*d_old;dy_new=grad_obj(x_new);coef=norm(dy_new)/norm(dy_old);d_new=-dy_new+coef^2*d_old;%搜索方向k=k+1;x_old=x_new;dy_old=dy_new;d_old=d_new;x_mat(:,k)=x_new;%防止死循环ifk>100break;endendx=x_new;%目标函数极值点iter=k;%迭代次数val=obj(x_new);%目标函数在极值点处的函数值endline_search.m文件如下：functionlambda=line_search(xk,dk)%作线搜索，求步长%phi(lambda)=obj(xk+lambda*dk)%d_phi(lambda)=dk'*grad_obj(xk+lambda*dk)symseqnlambdaeqn=dk'*grad_obj(xk+lambda*dk);lambda=solve(eqn);%用符号计算命令solve求方程d_phi(\lambda)=0的根lambda=eval(lambda);%将符号计算的结果转化为数值类型end3.2算法测试我们通过求解两个无约束优化问题来验证算法的稳定性和准确性。问题一：求解无约束优化问题，该问题的有精确解。问题二：找出如下方程的极小值点：其中初始点为obj.m文件functiony=obj(x)%目标函数y=3*x(1).^2/2+x(2).^2/2-x(1).*x(2)-2*x(1);%问题一目标函数%y=x(1).^2-2*x(1).*x(2)+4*x(2).^2+x(1)-3*x(2);%问题二目标函数endgrad_obj.m文件如下functiondy=grad_obj(x)%目标函数的梯度dy=[3*x(1)-x(2)-2;x(2)-x(1)];%问题一目标函数的梯度%dy=[2*x(1)-2*x(2)+1;-2*x(1)+8*x(2)-3];%问题二目标函数的梯度end结果如下：问题一：问题二:3.3结果分析共轭梯度法是一种很有效求解无约束优化的方法，共轭梯度法是根据共轭方向去搜索，可以由较快的收敛速度找到最优解求得极小值，并且计算结果比较稳定，误差在忽略范围内。4、算法比较4.1最速下降法的描述4.1.1最速下降方向函数f(x)在点x处沿方向d的变化率可用方向导数来表示。对于可微函数，方向导数等于梯度与方向的内积，即：Df(x;d)

=

▽f(x)Td,因此，求函数f(x)在点x处的下降最快的方向，可归结为求解下列非线性规划：min

▽f(x)Tds.t.

||d||

≤

1当

d

=

-▽f(x)

/

||▽f(x)||

时等号成立。因此，在点x处沿上式所定义的方向变化率最小，即负梯度方向为最速下降方向。4.1.2最速下降法最速下降法又称为梯度法，是1847年由著名数学家Cauchy给出的，它是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。作为一种基本的算法，他在最优化方法中占有重要地位。其优点是工作量少，存储变量较少，初始点要求不高；缺点是收敛慢，效率不高，有时达不到最优解。非线性规划研究的对象是非线性函数的数值最优化问题。它的理论和方法渗透到许多方面，特别是在军事、经济、管理、生产过程自动化、工程设计和产品优化设计等方面都有着重要的应用。而最速下降法正是n元函数的无约束非线性规划问题minf(x)的一种重要解析法，研究最速下降法原理及其算法实现对我们有着极其重要的意义。4.2最速下降法的步骤最速下降法的迭代公式是x(k+1)

=

x(k)

+

λkd(k)

,其中d(k)是从x(k)出发的搜索方向，这里取在x(k)处的最速下降方向，即d

=

-▽f(x(k)).λk是从x(k)出发沿方向d(k)进行一维搜索的步长，即λk满足f(x(k)

+

λkd(k))

=

min

f(x(k)+λd(k))

(λ≥0).算法步骤如下：Step1:：给出初始点，和精度；Step2：计算，如果，则停止迭代，输出结果；否则转step3；Step3：令下降方向，计算步长因子使得，令，转step2。4.3最少下降法实现最速下降法的Matlab程序如下：新建Steepest_Descent_Method.m文件，并复用grad_obj.m、line_search.m、obj.m文件Steepest_Descent_Method.m文件如下：4.4最速下降法算法测试使用此最速下降法算法求解此前的问题一和问题二，取不同的起始点的数值结果分别如下：问题一：问题二:4.5共轭梯度法与最速下降法比较通过分别用两种算法求解问题一和问题二所得的结果可以看出，共轭梯度法的收敛速度是比较最速下降快，在相同初始点处开始求解，使用共轭梯度法所需要的迭代次数比最速下降法的迭代次数的少得很多，并且也比最速下降法稳定得多。虽然在算法设计上比较相似，但是微小的改进，使得共轭梯度法无论是准确性上还是效率上都优于牛顿法。5、总结5.1总结概括最优化理论研究在如今的研究领域发展得如火如荼，共轭梯度法是一种很有效求解无约束优化的方法，共轭梯度法是根据共轭方向搜索，可以由较快的收敛速度找到最优解。该算法最早是由Hesternes和Stiefle(1952)提出来的，用于解正定系数矩阵的线性方程组，在这个基础上，Fletcher和Reeves(1964)首先提出了解非线性最优化问题的共轭梯度法。当然该算法发展到现在已经发展出了FR,PR,HS,CD,DY等算法，在搜索方法上有