共轭梯度算法分析与实现

编号:_ 09 最最最最 优优优优 化化化化 方方方方 法法法法 课课课课 程程程程 设设设设 计计计计 题 目： 共轭梯度算法分析与实现 院 系： 数学与计算科学学院 专 业： 数学与应用数学 姓名学号： 指导教师： 日 期： 2013 年 12 月 23 日 摘摘 要要 在最优化计算中，共轭梯度法是非常重要的一种方法。共轭梯度法是一种改进的最速 下降法，介于最速下降法与牛顿法之间的一种无约束优化算法,是为求解目标函数为二次函 数的问题而设计的一类算法。它利用目标函数的梯度逐步产生共轭方向并将其作为搜索方 向的方法，收敛速度快。共轭梯度法 仅需利用一阶导数信息，避免了牛顿法需要存储和 计算 Hesse 矩阵并求逆的缺点 ，具有二次终止性。 关键词关键词：共轭梯度法；牛顿法；二次函数；无约束优化 Abstract In 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 Newton 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 method has the quadratic termination. Keywords: Conjugate gradient method; Newton method;Unconstrained optimization 目目 录录 1、引言引言.1 2、共轭梯度算法的描述共轭梯度算法的描述.1 2.1 无约束优化问题概述.1 2.2 共轭方向.1 2.3 共轭梯度法.2 2.4 共轭梯度算法的步骤.2 3、数值实验数值实验.2 3.1 代码实现.2 3.2 算法测试.3 3.3 结果分析.5 4、算法比较算法比较.5 4.1 最速下降法描述.6 4.1.1 最速下降方向.6 4.1.2 最速下降法.6 4.2 最速下降法实现.6 4.3 最速下降法测试.7 4.4 共轭梯度法与最速下降法比较.8 5、总结总结.8 5.1 总结概括.8 5.2 个人感言.9 6、参考文献、参考文献：.9 最优化方法课程设计 1 1 1、引言引言 共轭梯度法最早是由 Hesternes 和 Stiefle(1952)提出来的，用于解正定系数矩阵的 线性方程组，在这个基础上，Fletcher 和 Reeves(1964)首先提出了解非线性最优化问题的 共轭梯度法。 在各种优化算法中，共轭梯度法（Conjugate Gradient）是非常重要的一种。是一种 介于最速下降法与牛顿法之间的优化算法，是为求解目标函数为二次函数的问题而设计的 一类算法。它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿 法需要存储和计算 Hesse 矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有 用的方法之一，也是解大型非线性最优化最有效的算法之一。可微的非二次函数在极小点 附近的形态近似于二次函数，因此共轭梯度法也能用于求可微的非二次函数的无约束极小 问题。 共轭梯度法是一个典型的共轭方向法，它在共轭方向法基础上增加了一些性质:计算当 前方向计算当前方向只需用到前一方向，对其他方向则无要求；计算出来的当前方向自动 与前面所有方向共轭，因此，不需耗费大量内存存储所有方向，也节省了计算时间。 2 2、共轭梯度法的描述共轭梯度法的描述 2.1 无约束优化问题概述无约束优化问题概述 一个非线性规划问题的自变量 x 没有任何约束，或说可行域既是整个 n 维 向量空间：，称这样的非线性规划问题为无约束问题： r n x 或)(minxf)( min xf R n x 2.2 共轭方向共轭方向 无约束问题最优化方法的核心问题是选择搜索方向。 以正定二次函数为例，来观察两个方向关于矩阵共轭的几何意义。 设有二次函数： f(x) = 1/2 (x - x*)TA(x - x*) , 其中 A 是 nn 对称正定矩阵，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)处的一个切向量。记作 最优化方法课程设计 2 d(2) = x* - x(1)。 自然，d(1)与f(x(1)正交，即 d(1)Tf(x(1) = 0，因此有 d(1)TAd(2) = 0， 即等值面上一点处的切向量与由这一点指向极小点的向量关于 A 共轭。 2.3 共轭梯度法共轭梯度法 共轭梯度法是最著名的共轭方向法，它首先由 Hestenes 和 Stiefel（1952）提出来作为解线性方程组的方法。由于解线性方程组等价于极 小化一个正定二次函数，故 1964 年 Fletcher 和 Reeves 提出了无约束极小化的 共轭梯度法，它是直接从 Hestenes 和 Stiefel 解线性方程组的共轭梯度法发展 而来的。共轭梯度法的基本思想是把共轭性与最速下降方法相结合，利用已知 点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小 点。根据共轭方向的基本性质，这种方法具有二次终止性。共轭梯度法就是使 得最速下降方向具有共轭性，从而提高算法的有效性和可靠性。在各种优化算 法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性， 稳定性高，而且不需要任何外来参数。 2.4 共轭梯度算法的步骤共轭梯度算法的步骤 共轭梯度算法步骤如下： Step1 给定迭代精度和初始点.计算.令.10 0 x)( 00 xfg0 :k Step2 若,停算,输出. k g k xx * Step3 计算搜索方向: k d 1, , , 0 , 11 kdg kg d kkk k k 其中当时,确定.1k 11 1 k T k k T k k gg gg 1k Step4 利用精确(或非精确)线搜索方法确定搜索步长. k Step5 令,并计算. kkkk dxx : 1 )( 11 kk xfg Step6 令,转步 Step1.1 : kk 3 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(:,1) = x;%存储每一次迭代得到的点 x x_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_new; d_old = d_new; x_mat(:,k) = x_new; %防止死循环 if k 100 break; end end x = x_new;%目标函数极值点 iter = k;%迭代次数 val = obj(x_new);%目标函数在极值点处的函数值 end line_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 ) syms eqn lambda eqn = dk*grad_obj(xk+lambda*dk); lambda = solve(eqn); %用符号计算命令solve求方程d_phi(lambda)=0的根 lambda = eval(lambda);%将符号计算的结果转化为数值类型 end 最优化方法课程设计 4 3.2 算法测试算法测试 我们通过求解两个无约束优化问题来验证算法的稳定性和准确性。 问题一： 求解无约束优化问题，该问题的有精确解 121 2 2 2 1 2 2 1 2 3 )(min 2 xxxxxxf Rx 。1)() 1 , 1 ( * xfx T， 问题二： 找出如下方程的极小值点： 21 2 221 2 1 342)(minxxxxxxxf 其中初始点为 0 1,1 T x 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);%问题二目标函数 end grad_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) + 1; -2*x(1) + 8*x(2) - 3;%问题二目标函数的 梯度 end 结果如下：结果如下： 问题一：问题一： 最优化方法课程设计 5 问题二问题二: : 最优化方法课程设计 6 3.3 结果分析结果分析 共轭梯度法是一种很有效求解无约束优化的方法，共轭梯度法是根据共轭 方向去搜索，可以由较快的收敛速度找到最优解求得极小值，并且计算结果比 较稳定，误差在忽略范围内。 4 4、算法比较、算法比较 4.1 最速下降法的描述最速下降法的描述 4.1.1 最速下降方向最速下降方向 函数 f(x)在点 x 处沿方向 d 的变化率可用方向导数来表示。对于可微函数， 方向导数等于梯度与方向的内积，即： Df(x;d) = f(x)Td, 因此，求函数 f(x)在点 x 处的下降最快的方向，可归结为求解下列非线性规 划： min f(x)Td s.t. |d| 1 当 d = -f(x) / |f(x)| 时等号成立。因此，在点 x 处沿上式所定义的方向变化率最小，即负梯度方向 为最速下降方向。 4.1.2 最速下降法最速下降法 最速下降法又称为梯度法，是 1847 年由著名数学家 Cauchy 给出的，它是 解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到 的，因此它是最优化方法的基础。作为一种基本的算法，他在最优化方法中占 最优化方法课程设计 7 有重要地位。其优点是工作量少，存储变量较少，初始点要求不高；缺点是收 敛慢，效率不高，有时达不到最优解。非线性规划研究的对象是非线性函数的 数值最优化问题。它的理论和方法渗透到许多方面，特别是在军事、经济、管 理、生产过程自动化、工程设计和产品优化设计等方面都有着重要的应用。而 最速下降法正是 n 元函数的无约束非线性规划问题 min f (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:：给出初始点，和精度； 0 x1;0k Step2：计算，如果，则停止迭代，输出结果；否则转() k f x() k f x step3； Step3：令下降方向，计算步长因子使得() kk df x k ，令，转 step2。 0 ()min() kkkkk f xdf xd 1 ,1 kkkk xxdkk 4.3 最少下降法实现最少下降法实现 最速下降法的 Matlab 程序如下： 新建Steepest_Descent_Method.m文件，并复用 grad_obj.m、line_search.m、obj.m文件 Steepest_Descent_Method.mSteepest_Descent_Method.m文件如下：文件如下： 最优化方法课程设计 8 4.4 最速下降法算法测试最速下降法算法测试 使用此最速下降法算法求解此前的问题一和问题二，取不同的起始点的数 值结果分别如下： 问题一：问题一： 最优化方法课程设计 9 问题二问题二: : 4.5 共轭梯度法与最速下降法比较共轭梯度法与最速下降法比较 通过分别用两种算法求解问题一和问题二所得的结果可以看出，共轭梯度 法的收敛速度是比较最速下降快，在相同初始点处开始求解，使用共轭梯度法 所需要的迭代次数比最速下降法的迭代次数的少得很多，并且也比最速下降法 稳定得多。虽然在算法设计上比较相似，但是微小的改进，使得共轭梯度法无 最优化方法课程设计 10 论是准确性上还是效率上都优于牛顿法。 5 5、总结、总结 5.15.1 总结概括总结概括 最优化理论研究在如今的研究领域发展得如火如荼，共轭梯度法是一种很 有效求解无约束优化的方法，共轭梯度法是根据共轭方向搜索，可以由较快的 收敛速度找到最优解。该算法最早是由 Hesternes 和 Stiefle(1952)提出来的， 用于解正定系数矩阵的线性方程组，在这个基础上，Fletcher 和 Reeves(1964) 首先提出了解非线性最优化问题的共轭梯度法。当然该算法发展到现在已经发 展出了 FR,PR,HS,CD,DY 等算法，在搜索方法上有了较大的改进，