最 优 化 方 法课 程 设 计题 目： 共轭梯度法算法分析与实现 院 系： 数学与计算科学学院 专 业： 数学与应用数学 姓 名： 梁婷艳 学 号： 0800730103 指导教师： 李丰兵 日 期： 2015 年 12 月 30 日摘 要在各种优化算法中，共轭梯度法是非常重要的一种。本文主要介绍的共轭梯度法是介于最速下降法与牛顿法之间的一种无约束优化算法，它具有超线性收敛速度, 而且算法结构简单, 容易编程实现。在本次实验中,我们首先分析共轭方向法、对该算法进行分析，运用基于共轭方向的一种算法共轭梯度法进行无约束优化问题的求解。无约束最优化方法的核心问题是选择搜索方向。共轭梯度法的基本思想是把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。根据共轭方向的基本性质，这种方法具有二次终止性。再结合该算法编写matlab程序，求解无约束优化问题，再结合牛顿算法的理论知识，编写matlab程序，求解相同的无约束优化问题，进行比较分析，得出共轭梯度法和牛顿法的不同之处以及共轭梯度法的优缺点。共轭梯度法仅需利用一阶导数信息，避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便。关键词：共轭梯度法；超线性收敛；牛顿法；无约束优化 AbstractIn a variety of optimization algorithms, conjugate gradient method is a very important one. In this paper, the conjugate gradient method is between the steepest descent method and Newton method for unconstrained optimization between a method, it has superlinear convergence rate, and the algorithm is simple and easy programming.In this experiment, we first analyze the conjugate direction method, the algorithm analysis, the use of a conjugate direction-based algorithm - conjugate gradient method for unconstrained optimization problems. Unconstrained optimization method is to select the core issue of the search direction. Conjugate gradient method is the basic idea of the conjugate descent method with the most combined points in the gradient using the known structure of a set of conjugate directions, and search along the direction of this group, find the minimum point of objective function. According to the basic nature of the conjugate direction, this method has the quadratic termination. Combined with the preparation of this algorithm matlab program for solving unconstrained optimization problems, combined with Newtons theory of knowledge, writing matlab program to solve the same problem of unconstrained optimization, comparison analysis, the conjugate gradient method and Newton method different Office and the advantages and disadvantages of the conjugate gradient method.Conjugate gradient method using only first derivative information, to avoid the Newton method requires storage and computing the inverse Hesse matrix and shortcomings, is not only the conjugate gradient method to solve large linear systems one of the most useful, but also large-scale solution nonlinear optimization algorithm is one of the most effective. Conjugate gradient method is a typical conjugate direction method, each of its search direction is conjugate to each other, and the search direction d is just the negative gradient direction with the last iteration of the search direction of the portfolio, therefore, storage less computational complexity.Key words: Conjugate gradient method; Superlinear convergence; Newton method Unconstrained optimization目 录1、引言12、共轭梯度法的描述12.1 共轭方向法12.2 共轭梯度法22.3 ARMIJO准则63、数值实验73.1 代码实现73.2 算法测试83.3 结果分析104、算法比较104.1 牛顿法的构造104.2 算法实现114.3 算法测试124.4算法比较135、总结135.1 总结概括135.2 个人感言146、参考文献：161、引言在各种优化算法中，共轭梯度法（Conjugate Gradient）是非常重要的一种。其优点是所需存储量小，具有N步收敛性，稳定性高，而且不需要任何外来参数。共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。 共轭梯度法最早是又Hestenes和Stiefle（1952）提出来的，用于解正定系数矩阵的线性方程组，在这个基础上，Fletcher和Reeves（1964）首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用与实际问题中。 共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便。2、共轭梯度法的描述2.1 共轭方向法共轭方向法是介于最速下降法与牛顿法之间的一个方法。它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了存贮和计算牛顿法所需要的二阶导数信息。共轭方向法是从研究二次函数的极小化产生的，但是它可以推广到处理非二次函数的极小化问题。一般共轭方向法步骤如下：算法 2.1.1 （一般共轭方向法）给出的初始点，步1 计算步2 计算，使步3 令步4 计算和，使得步5 计算使得,。步6 令,转步4共轭方向法的一个基本性质是：只要执行精确线性搜索，就能得到二次终止性。这就是下面的共轭方向法基本定理。定理 2.1.1 （共轭方向法基本定理）对于正定二次函数，共轭方向法之多经n步精确线性搜索终止；且每一都是在和方向所张成的线性流行中的极小点。2.2 共轭梯度法共轭梯度法是最着名的共轭方向法，它首先由Hestenes和Stiefel（1952）提出来作为解线性方程组的方法。由于解线性方程组等价于极小化一个正定二次函数，故1964年Fletcher和Reeves提出了无约束极小化的共轭梯度法，它是直接从Hestenes和Stiefel解线性方程组的共轭梯度法发展而来的。共轭方向法基本定理告诉我们，共轭性和精确线性搜索产生二次终止性。共轭梯度法就是使得最速下降方向具有共轭性，从而提高算法的有效性和可靠性。下面针对二次函数情形讨论共轭梯度法，我们先给出共轭梯度法的推导。设 (2.2.1)其中是对称正定矩阵，是向量，是实数。的梯度为 (2.2.2)令 (2.2.3)则 (2.2.4)由精确线性搜索性质， (2.2.5)令 (2.2.6)选择，使得. (2.2.7)对（2.2.6）两边同乘以，得. (2.2.8)由共轭方向法基本定理，。利用（2.2.3）和（2.2.6），可知, . (2.2.9)又令, (2.2.10)选择和，使得，。从而有,. (2.2.11)一般地，在第次迭代，令, (2.2.12)选择，使得，。也假定, , , (2.2.13)对(2.2.12)左乘，则, . (2.2.14)由(2.2.13)，, , ,故得,和. (2.2.15)因此，共轭梯度法的公式为, (2.2.16)其中，在二次函数情形，.