共轭梯度算法分析与实现(共12页).doc

《共轭梯度算法分析与实现(共12页).doc》由会员分享，可在线阅读，更多相关《共轭梯度算法分析与实现(共12页).doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上专心-专注-专业编号:_ 09 最最最最 优优优优 化化化化 方方方方 法法法法课课课课 程程程程 设设设设 计计计计题 目： 共轭梯度算法分析与实现 院 系： 数学与计算科学学院 专 业： 数学与应用数学 姓名学号： 指导教师： 日 期： 2013 年 12 月 23 日精选优质文档-倾情为你奉上专心-专注-专业摘摘 要要在最优化计算中，共轭梯度法是非常重要的一种方法。共轭梯度法是一种改进的最速下降法，介于最速下降法与牛顿法之间的一种无约束优化算法,是为求解目标函数为二次函数的问题而设计的一类算法。它利用目标函数的梯度逐步产生共轭方向并将其作为搜索方向的方法，收敛速

2、度快。共轭梯度法 仅需利用一阶导数信息，避免了牛顿法需要存储和计算 Hesse 矩阵并求逆的缺点 ，具有二次终止性。关键词关键词：共轭梯度法；牛顿法；二次函数；无约束优化 AbstractIn the calculation of optimization method, conjugate gradient method is a very important one. The conjugate gradient method is a unconstrained optimization method between the steepest descent method and New

3、ton method, and sove the objective function for the original quadratic function problems and design for a class of algorithm. Conjugate gradient method using only first derivative information, to avoid the Newton method requires storage and computing the inverse Hesse matrix and shortcomings, this m

4、ethod has the quadratic termination.Keywords: Conjugate gradient method; Newton method;Unconstrained optimization精选优质文档-倾情为你奉上专心-专注-专业目目 录录4.1.1 最速下降方向.64.1.2 最速下降法.689精选优质文档-倾情为你奉上专心-专注-专业1 1、引言引言共轭梯度法最早是由 Hesternes 和 Stiefle(1952)提出来的，用于解正定系数矩阵的线性方程组，在这个基础上，Fletcher 和 Reeves(1964)首先提出了解非线性最优化问题的共轭

5、梯度法。在各种优化算法中，共轭梯度法（Conjugate Gradient）是非常重要的一种。是一种介于最速下降法与牛顿法之间的优化算法，是为求解目标函数为二次函数的问题而设计的一类算法。它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算 Hesse 矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。可微的非二次函数在极小点附近的形态近似于二次函数，因此共轭梯度法也能用于求可微的非二次函数的无约束极小问题。共轭梯度法是一个典型的共轭方向法，它在共轭方向法基础上增加了一些性质:计算当前方向计算当前方向只

6、需用到前一方向，对其他方向则无要求；计算出来的当前方向自动与前面所有方向共轭，因此，不需耗费大量内存存储所有方向，也节省了计算时间。2 2、共轭梯度法的描述共轭梯度法的描述2.1 无约束优化问题概述无约束优化问题概述一个非线性规划问题的自变量 x 没有任何约束，或说可行域既是整个 n 维向量空间：，称这样的非线性规划问题为无约束问题：rnx 或)(minxf)(minxfRnx2.2 共轭方向共轭方向无约束问题最优化方法的核心问题是选择搜索方向。以正定二次函数为例，来观察两个方向关于矩阵共轭的几何意义。设有二次函数：f(x) = 1/2 (x - x*)TA(x - x*) ,其中 A 是 n

7、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)Tf(x(1) = 0，因此有d(1)TAd(2) = 0，即等值面上一点处的切向量

8、与由这一点指向极小点的向量关于 A 共轭。2.3 共轭梯度法共轭梯度法共轭梯度法是最著名的共轭方向法，它首先由 Hestenes 和Stiefel（1952）提出来作为解线性方程组的方法。由于解线性方程组等价于极小化一个正定二次函数，故 1964 年 Fletcher 和 Reeves 提出了无约束极小化的共轭梯度法，它是直接从 Hestenes 和 Stiefel 解线性方程组的共轭梯度法发展而来的。共轭梯度法的基本思想是把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。根据共轭方向的基本性质，这种方法具有二次终止性。共轭梯度法就是

9、使得最速下降方向具有共轭性，从而提高算法的有效性和可靠性。在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。2.4 共轭梯度算法的步骤共轭梯度算法的步骤 共轭梯度算法步骤如下：Step1 给定迭代精度和初始点.计算.令.100 x)(00 xfg0 :kStep2 若,停算,输出.kgkxx *Step3 计算搜索方向:kd1, , 0 ,11kdgkgdkkkkk其中当时,确定.1k111kTkkTkkgggg1kStep4 利用精确(或非精确)线搜索方法确定搜索步长.kStep5 令,并计算.kkkkdxx :1)(11kk

10、xfgStep6 令,转步 Step1.1 : kk 3 3、数值实验、数值实验精选优质文档-倾情为你奉上专心-专注-专业3.1 代码实现代码实现共轭梯度法的共轭梯度法的MatlabMatlab程序如下：程序如下：分别新建Conjugate_Gradient_Method.m、grad_obj.m、line_search.m、obj.m文件Conjugate_Gradient_MethodConjugate_Gradient_Method.m.m文件如下：文件如下：function x,iter,val = Conjugate_Gradient_Method(x,eps)k = 0;x_mat

11、(:,1) = x;%存储每一次迭代得到的点 xx_old = x;dy_old = grad_obj(x_old);d_old = -dy_old;while norm(dy_old)eps lambda = 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 + coef2*d_old; % 搜索方向 k = k + 1; x_old = x_new; dy_old = dy

12、_new; d_old = d_new; x_mat(:,k) = x_new; %防止死循环 if k 100 break; endend x = x_new;%目标函数极值点iter = k;%迭代次数val = obj(x_new);%目标函数在极值点处的函数值endline_searchline_search.m.m文件如下：文件如下：function lambda = line_search(xk,dk)%作线搜索，求步长%phi(lambda) = obj( xk + lambda*dk )%d_phi(lambda) = dk*grad_obj( xk + lambda*dk )

13、syms eqn lambdaeqn = dk*grad_obj(xk+lambda*dk);lambda = solve(eqn); %用符号计算命令solve求方程d_phi(lambda)=0的根lambda = eval(lambda);%将符号计算的结果转化为数值类型end精选优质文档-倾情为你奉上专心-专注-专业3.2 算法测试算法测试我们通过求解两个无约束优化问题来验证算法的稳定性和准确性。问题一：求解无约束优化问题，该问题的有精确解121222122123)(min2xxxxxxfRx。1)() 1 , 1 (*xfxT，问题二：找出如下方程的极小值点：21222121342)

14、(minxxxxxxxf其中初始点为 01,1Tx obj.mobj.m 文件文件function y = 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_objgrad_obj.m.m文件如下文件如下function dy = grad_obj(x)%目标函数的梯度dy = 3*x(1)-x(2)-2; x(2)-x(1);%问题一目标函数的梯度%dy = 2*x(1) - 2*x(2)

15、 + 1; -2*x(1) + 8*x(2) - 3;%问题二目标函数的梯度end结果如下：结果如下：问题一：问题一：精选优质文档-倾情为你奉上专心-专注-专业问题二问题二: : 精选优质文档-倾情为你奉上专心-专注-专业 3.3 结果分析结果分析共轭梯度法是一种很有效求解无约束优化的方法，共轭梯度法是根据共轭方向去搜索，可以由较快的收敛速度找到最优解求得极小值，并且计算结果比较稳定，误差在忽略范围内。4 4、算法比较、算法比较4.1 最速下降法的描述最速下降法的描述4.1.1 最速下降方向最速下降方向函数 f(x)在点 x 处沿方向 d 的变化率可用方向导数来表示。对于可微函数，方向导数等于

16、梯度与方向的内积，即：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 给出的，它是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。作为一种基本的算法，他在最优化方法中占精选优质文档-倾情为你奉上专心-专注-专业有重

17、要地位。其优点是工作量少，存储变量较少，初始点要求不高；缺点是收敛慢，效率不高，有时达不到最优解。非线性规划研究的对象是非线性函数的数值最优化问题。它的理论和方法渗透到许多方面，特别是在军事、经济、管理、生产过程自动化、工程设计和产品优化设计等方面都有着重要的应用。而最速下降法正是 n 元函数的无约束非线性规划问题 min f (x)的一种重要解析法，研究最速下降法原理及其算法实现对我们有着极其重要的意义。4.2 最速下降法的步骤最速下降法的步骤最速下降法的迭代公式是x(k+1) = x(k) + kd(k) ,其中 d(k)是从 x(k)出发的搜索方向，这里取在 x(k)处的最速下降方向，即

18、d = -f(x(k).k是从 x(k)出发沿方向 d(k)进行一维搜索的步长，即 k满足f(x(k) + kd(k) = min f(x(k)+d(k) (0).算法步骤如下：Step1:：给出初始点，和精度；0 x1;0kStep2：计算，如果，则停止迭代，输出结果；否则转()kf x()kf xstep3；Step3：令下降方向，计算步长因子使得()kkdf x k，令，转 step2。0()min()kkkkkf xdf xd1,1kkkkxxdkk4.3 最少下降法实现最少下降法实现最速下降法的 Matlab 程序如下：新建Steepest_Descent_Method.m文件，并复

19、用grad_obj.m、line_search.m、obj.m文件Steepest_Descent_Method.mSteepest_Descent_Method.m文件如下：文件如下：精选优质文档-倾情为你奉上专心-专注-专业4.4 最速下降法算法测试最速下降法算法测试使用此最速下降法算法求解此前的问题一和问题二，取不同的起始点的数值结果分别如下：问题一：问题一：精选优质文档-倾情为你奉上专心-专注-专业问题二问题二: : 4.5 共轭梯度法与最速下降法比较共轭梯度法与最速下降法比较通过分别用两种算法求解问题一和问题二所得的结果可以看出，共轭梯度法的收敛速度是比较最速下降快，在相同初始点处开

20、始求解，使用共轭梯度法所需要的迭代次数比最速下降法的迭代次数的少得很多，并且也比最速下降法稳定得多。虽然在算法设计上比较相似，但是微小的改进，使得共轭梯度法无精选优质文档-倾情为你奉上专心-专注-专业论是准确性上还是效率上都优于牛顿法。5 5、总结、总结5.15.1 总结概括总结概括最优化理论研究在如今的研究领域发展得如火如荼，共轭梯度法是一种很有效求解无约束优化的方法，共轭梯度法是根据共轭方向搜索，可以由较快的收敛速度找到最优解。该算法最早是由 Hesternes 和 Stiefle(1952)提出来的，用于解正定系数矩阵的线性方程组，在这个基础上，Fletcher 和 Reeves(196

21、4)首先提出了解非线性最优化问题的共轭梯度法。当然该算法发展到现在已经发展出了 FR,PR,HS,CD,DY 等算法，在搜索方法上有了较大的改进，迭代次数减少，收敛速度加快。无约束问题最优化方法的核心问题是选择搜索方向。而共轭梯度法只计算当前方向只需用到前一方向，对其他方向则无要求；因此相对与其他算法大大减少了计算量。 本次课程设计，对最优化算法中的共轭梯度法做了一定程度的研究，并通过 MATLABLE 实现了该算法。除此之外还实现了最速下降法，将二者所求的结果进行比较分析，进一步深入理解共轭梯度法。5.2 个人感言个人感言通过本次课程设计，我学会了如何对提出的问题进行研究，首先要对该问题有个

22、大致的了解，再通过查阅资料对该问题深入研究，确定研究的方向和步骤，并一步步实现。比如在对共轭梯度法的定义及算法的具体步骤进行研究时，我还了解到了共轭方向，梯度法，无约束优化问题等知识。由于已经将关于MATLAB 编程的知识忘得差不多了，所以在使用 MATLAB 实现该算法时，遇到遇到了不少困难，在不断利用各种途径寻找解决的方法后，最终能够使该算法在MATLAB 上得到实现。让我得到了一个复习前面所学 MATLAB 知识的好机会。通过本次课程设计，了解到了共轭梯度法的定义、描述以及算法的实现，及其使用共轭梯度法来解决最优化问题，使得我对最优化问题有了更深刻的了解。6 6、参考文献：、参考文献：1 何坚勇.最优化方法M.北京：清华大学出版社，2007.2 袁亚湘，孙文瑜.最优化理论与方法M.北京：科学出版社，19973 薛嘉庆.最优化原理与方法M.北京：清华大学出版社，2003.4 张光澄.非线性最优化计算方法M.北京：高等教育出版社，20055 傅英定，成孝予，唐应辉.最优化理论与方法M.北京：国防工业出版社，2008