共轭梯度算法的设计与实现毕业设计

1、 本科毕业设计（论文）开题报告 题 目： 共轭梯度算法的设计与实现 学生姓名： 院 （系）： 理学院 专业班级： 信息0602 指导教师： 完成时间： 2010年 月 日 一、课题的意义最优化方法是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效率及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、国防等各个领域，发挥着越

2、来越重要的作用。最优化方法又可分为无约束最优化方法和约束最优化方法，其中无约束最优化方法包括最速下降法，牛顿法，共轭方向法，以及共轭梯度法和变尺度法，约束优化方法包括单纯形法，解线性规划的图解法，等式约束的罚函数法，以及Rosen梯度投影法。本文将讨论无约束最优化方法下的共轭梯度法，通过MATLAB编程实现，并以具体实例得出相应的数值结果，然后验证该方法是否有效。二、国内外研究现状近年来，随着模糊理论、神经网络等智能技术和计算机技术的发展，智能式的优化方法越来越受重视。现今，国内外主要研究的方法有：（1）神经网络优化方法 HYPERLINK :/wiki.mbalib /wiki/%E4%BA

3、%BA%E5%B7%A5%E7%A5%9E%E7%BB%8F%E7%BD%91%E7%BB%9C o 人工神经网络 人工神经网络的研究起源于1943年和 HYPERLINK :/wiki.mbalib /w/index.php?title=Mc_Culloch&action=edit o Mc Culloch Mc Culloch和hp?title=Pitts&action=edit o Pitts Pitts的工作。在优化方面，1982年 HYPERLINK :/wiki.mbalib /w/index.php?title=Hopfield&action=edit o Hopfield Ho

4、pfield首先引入Lyapuov能量函数用于5判断网络的稳定性，提出了%8D%95%E5%B1%82%E7%A6%BB%E6%95%A3%E6%A8%A1%E5%9E%8B&action=edit o Hopfield单层离散模型 Hopfield单层离散模型； HYPERLINK :/wiki.mbalib /w/index.php?title=Hopfield&action=edit o Hopfield Hopfield和=Tank&action=edit o Tank Tank又发展了 HYPERLINK :/wiki.mbalib /w/index.php?title=Hopfie

5、ld%E5%8D%95%E5%B1%82%E8%BF%9E%E7%BB%AD%E6%A8%A1%E5%9E%8B&action=edit o Hopfield单层连续模型 Hopfield单层连续模型。1986年，Hopfield和Tank将电子电路与Hopfield模型直接对应，实现了硬件模拟； HYPERLINK :/wiki.mbalib /w/index.php?title=Kennedy&action=edit o Kennedy Kennedy和 HYPERLINK :/wiki.mbalib /w/index.php?title=Chua&action=edit o Chua C

6、hua基于非线性电路理论提出了模拟电路模型，并使用系统微分方程的Lyapuov函数研究了电子电路的稳定性。这些工作都有力地促进了对神经网络优化方法的研究。（2）模糊优化方法最优化问题一直都是模糊理论应用最为广泛的领域之一。自从 HYPERLINK :/wiki.mbalib /w/index.php?title=Bellman&action=edit o Bellman Bellman和 HYPERLINK :/wiki.mbalib /wiki/L.A.zadeh o L.A.zadeh 在70年代初期对这一研究作出开创性工作以来，其主要研究集中在一般意义下的理论研究、 HYPERLINK

7、:/wiki.mbalib /wiki/%E6%A8%A1%E7%B3%8A%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92 o 模糊线性规划 模糊线性规划、 HYPERLINK :/wiki.mbalib /w/index.php?title=%E5%A4%9A%E7%9B%AE%E6%A0%87%E6%A8%A1%E7%B3%8A%E8%A7%84%E5%88%92&action=edit o 多目标模糊规划 多目标模糊规划、以及模糊规划理论在 HYPERLINK :/wiki.mbalib /wiki/%E9%9A%8F%E6%9C%BA%E8%A7%84%E5%

8、88%92 o 随机规划 随机规划及许多实际问题中的应用。主要的研究方法是利用模糊集的a截集或确定模糊集的隶属函数将模糊规划问题转化为经典的规划问题来解决。 （3）支持向量机方法支持向量机是由Vapnik领导的AT&TBell实验室研究小组在1963年提出的一种新的非常有潜力的分类技术，SVM是一种基于统计学习理论的模式识别方法，主要应用于模式识别领域。由于当时这些研究尚不十分完善，在解决模式识别问题中往往趋于保守，且数学上比较艰涩，这些研究一直没有得到充分的重视。直到90年代，统计学习理论的实现和由于神经网络等较新兴的机器学习方法的研究遇到一些重要的困难，比如如何确定网络结构的问题、过学习与

9、欠学习问题、局部极小点问题等，使得SVM迅速发展和完善，在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。 共轭梯度法在以上的优化方法中都得到了应用，例如，有学者就应用共轭梯度法对网络的权值和阂值进行优化计算，完成神经网络训练的方法；还有学者在支持向量机方法中应用共轭梯度法，便得到了一种更有效的光滑支持向量机方法。三、毕业论文的主要内容1了解共轭梯度法的背景和意义。2建立一个求解无约束最优化问题的共轭梯度算法。3阐述该算法的具体实现步骤并分析该算法的全局收敛性。4通过MATLAB编程实现得到的数值实验结果来验证算法是否有效。四、所采用的

10、方法、手段以及步骤 通过网络、书籍和一些参考资料，查询相关信息，理解什么是共轭梯度法，以及如何应用共轭梯度法完成最优化设计。将从以下几个内容考虑：1. 建立一个求解无约束最优化问题的共轭梯度算法：通过实例，结合参考资料以及自己所掌握的知识，建立一个求解该实例的共轭梯度算法。2. 分析算法的全局收敛性：运用所学知识，并借鉴一些学者的文献证明该算法在指定的搜索方向下具有全局收敛性。3. 通过数值实验结果来验证算法是否有效：通过MATLAB编程，代入实例中的相关数据得到一些相关的数值结果，最后对数据进行分析验证，判断该算法是否有效。五、阶段进度计划第1-2周：在老师的指导下,搜索与共轭梯度法相关的资

11、料，按照规定做相应的外文翻译，并了解其背景、应用及意义，弄懂该方法的基本思想。第3-4周：查阅相关参考资料，完成开题报告和外文翻译，并通过老师的审查第5-6周：对毕业设计的具体内容做详细的了解，分析研究共轭梯度法，并完成论文的引言部分。第7-9周：建立一个求解实际问题的共轭梯度算法，阐述该算法的具体实现步骤并分析该算法的全局收敛性，完成论文的核心部分。第9-10周：通过MATLAB编程对算法进行检验并对算法是否有效进行解释，并完成论文最后的结束语部分。第11-12周：整合以上各个阶段的成果，总结所做的工作，并完成论文的初稿。第13-15周：将论文初稿交予指导老师审阅，根据老师的意见修改并完善论

12、文。第16周：请评阅老师评阅论文，最后进行毕业论文的答辩。六、参考文献1 袁亚湘，孙文瑜.最优化理论与算法M.北京：科学出版社,1997. 2 蒋金山,何春雄,潘少华.最优化计算方法M.广东：华南理工大学出版社,2008.3 张秀军，徐安农.htm%09%09%09%09%09%09%09%09%09%09%09%09%09 t _blank 一种新的非线性共轭梯度法的全局收敛性J.广西科学报，2005，5(04)：87-96.4 时贞军. HYPERLINK :/www ki /Article/CJFDTOTAL-SXWX200406004.htm%09%09%09%09%09%09%09%

13、09%09%09%09%09%09 t _blank 精确搜索下的非线性共轭梯度法J.数学物理学报，2004，21（06）：55-58.5 云天铨. HYPERLINK :/www ki /Article/CJFDTOTAL-HZLG198003003.htm%09%09%09%09%09%09%09%09%09%09%09%09%09 t _blank 二维无约束优化问题的最优方向搜索法J.华中科技大学学报(自然科学版)，1980，22（03）：73-85.6 张秀军,徐安农,李安坤,蒋利华. HYPERLINK :/www ki /Article/CJFDTOTAL-GLDZ2005060

14、16.htm%09%09%09%09%09%09%09%09%09%09%09%09%09 t _blank 改进的共轭梯度法及其收敛性J.桂林电子工业学院学报，2005，13（06）：5-8.7 孟江,王耀才,洪留荣.%09%09%09%09%09%09%09 t _blank 共轭梯度与牛顿混杂算法及在神经网络的应用J.计算机工程与应用，2004，25(35)：31-37.8 陈红霞,袁业立,刘娜,曲媛媛. HYPERLINK :/www ki /Article/CJFDTOTAL-SEAC200306004.htm%09%09%09%09%09%09%09%09%09%09%09%09%

15、09 t _blank 非线性共轭梯度法在东海黑潮流计算中的应用J.海洋学报(中文版)，2003，18(06)：131-139.9 王磊.支持向量机学习算法的若干问题研究.成都：电子科技大学博士学位论文，2007.10袁玉波，严杰，徐成贤.多项式光滑的支持向量机.计算机学报，2005，28(1)：9-17. 指导教师意见：指导教师签字：年 月 日系(教研室)意见：主任签字：年 月 日共轭梯度算法的设计与实现摘要：共轭梯度法是最优化方法中一种重要的方法.它是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆

16、的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化问题最有效的算法之一.近年来，随着计算机的飞速发展和实际问题中大规模优化问题的涌现，寻找快速有效的共轭梯度法成为了学者们研究的热门方向之一.本文主要研究求解无约束最优化问题的共轭梯度法.具体从以下方面着手，介绍所选课题的研究背景、意义和研究现状；阐述共轭梯度法理论，包括共轭梯度法的一些基本概念，计算公式和迭代步骤；引入一些实际问题，建立共轭梯度算法；根据已有学者的研究结果，分析算法的收敛性；运用MATLAB编程，代入实例中的相关数据得到一些相关的数值结果；最后对数据进行分析验证，判断该算法的有效性.关键词：无约束

17、最优化；共轭梯度法；迭代；全局收敛性Conjugate Gradient Algorithm Design and ImplementationAbstract：Conjugate gradient method is one of the important optimization methods. It is between the steepest descent method and Newton method, which only requires the first order derivative. It not only overcomes the shortcomings

18、 of slow convergence of steepest descent method, but also avoids the shortcomings of storing and calculating the inverse Hesse matrix of Newton method. The conjugate gradient method is not only one of the most useful methods to solve the large-scale linear equations, but also is one of the most effe

19、ctive algorithms to solve a large nonlinear optimization problem.In recent years, with the rapid development of computer and the practical issues in the emergence of large-scale optimization problems, looking for quick and efficient conjugate gradient method becomes one of the most popular direction

20、s of scholars. This paper mainly discusses the conjugate gradient method in the unconstrained optimization methods. We focus on the following aspects, describe the background and the significance of the selected research projects; elaborate the theory of conjugate gradient method, which includes som

21、e of the basic concepts, formulas and iterative steps; introduce some practical problems, establish the conjugate gradient algorithm; based on the existing academic research results, analyze the convergence of the algorithm; use the MATLAB programming, behalf of the relevant data into the instances

22、to get some relevant numerical results; finally, analyze the data and determine the effectiveness of the algorithm. Key words：Unconstrained optimization；Conjugate gradient method；Iteration；Global convergence目 录 TOC o 1-3 h z u HYPERLINK l _Toc263421787 第一章 绪论 PAGEREF _Toc263421787 h 1 HYPERLINK l _T

23、oc263421788 1.1 研究背景和意义 PAGEREF _Toc263421788 h 1 HYPERLINK l _Toc263421789 1.2 共轭梯度法的研究现状 PAGEREF _Toc263421789 h 1 HYPERLINK l _Toc263421790 1.2.1 理论研究 PAGEREF _Toc263421790 h 1 HYPERLINK l _Toc263421791 1.2.2 应用研究 PAGEREF _Toc263421791 h 3 HYPERLINK l _Toc263421792 1.3 本文工作和结构安排 PAGEREF _Toc26342

24、1792 h 4 HYPERLINK l _Toc263421793 第二章 共轭梯度法 PAGEREF _Toc263421793 h 5 HYPERLINK l _Toc263421794 2.1 最优化方法 PAGEREF _Toc263421794 h 5 HYPERLINK l _Toc263421795 2.2 共轭梯度法理论 PAGEREF _Toc263421795 h 5 HYPERLINK l _Toc263421796 2.2.1 共轭梯度法的概念 PAGEREF _Toc263421796 h 5 HYPERLINK l _Toc263421797 2.2.2 共轭方向

25、及性质 PAGEREF _Toc263421797 h 6 HYPERLINK l _Toc263421798 2.2.3 共轭梯度法的公式结构 PAGEREF _Toc263421798 h 7 HYPERLINK l _Toc263421799 2.2.4 共轭梯度法的算法步骤 PAGEREF _Toc263421799 h 11 HYPERLINK l _Toc263421800 2.2.5 共轭梯度法的优点 PAGEREF _Toc263421800 h 11 HYPERLINK l _Toc263421801 2.3 算法实例 PAGEREF _Toc263421801 h 12 H

26、YPERLINK l _Toc263421802 第三章 算法的收敛性 PAGEREF _Toc263421802 h 15 HYPERLINK l _Toc263421803 3.1 共轭梯度法的性质与收敛性定理 PAGEREF _Toc263421803 h 15 HYPERLINK l _Toc263421804 3.1.1 共轭梯度法的性质 PAGEREF _Toc263421804 h 15 HYPERLINK l _Toc263421805 3.1.2 共轭梯度法的收敛性定理 PAGEREF _Toc263421805 h 17 HYPERLINK l _Toc263421806

27、3.2 戴彧虹-袁亚湘共轭梯度法 PAGEREF _Toc263421806 h 19 HYPERLINK l _Toc263421807 第四章 算法编程 PAGEREF _Toc263421807 h 24 HYPERLINK l _Toc263421808 4.1 MATLAB的发展历程和影响 PAGEREF _Toc263421808 h 24 HYPERLINK l _Toc263421809 4.2 共轭梯度法的MATLAB程序 PAGEREF _Toc263421809 h 24 HYPERLINK l _Toc263421810 第五章 结论 PAGEREF _Toc26342

28、1810 h 30 HYPERLINK l _Toc263421811 参考文献 PAGEREF _Toc263421811 h 31 HYPERLINK l _Toc263421812 致 谢 PAGEREF _Toc263421812 h 33第一章 绪论本章首先阐明了所选课题的研究背景和意义；然后对最优化方法下的共轭梯度方法的产生、主要研究内容以及国内外的研究现状进行阐述；最后给出了本论文的主要研究工作和结构安排.1.1 研究背景和意义 最优化方法是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据.最优化方法的目的在于针对所研究的系统，求得一个合

29、理运用人力、物力和财力的最佳方案，发挥和提高系统的效率及效益，最终达到系统的最优目标.实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、国防等各个领域，发挥着越来越重要的作用.最优化方法又可分为无约束最优化方法和约束最优化方法，其中无约束最优化方法包括最速下降法，牛顿法，共轭方向法，以及共轭梯度法和变尺度法，约束优化方法包括单纯形法，解线性规划的图解法，等式约束的罚函数法，以及Rosen梯度投影法.其中最优化方法下的共轭梯度法，具有较快的收敛速度和二次终止性等优点，得到许多学者们的青睐，使得寻

30、找快速有效的共轭梯度法成为了学者们研究的热门方向.因此研究所选课题的意义非常重大.1.2 共轭梯度法的研究现状共轭梯度法最早是由Hestenes和Stiefle(1952)提出来的，用于解正定系数矩阵的线性方程组，在这个基础上，Fletcher和Reeves(1964)首先提出了解非线性最优化问题的共轭梯度法.共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一.共轭梯度法又是一个典型的共轭方向法，

31、它的每一个搜索方向是互相共轭的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便.由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用到实际问题中.1.2.1 理论研究目前，国内外对共轭梯度法的研究已经相当完善，更有一套几乎完美的共轭梯度法理论，并且广泛的应用到实际问题中，为其应用研究奠定了坚实的基础.在此简单给出共轭梯度法的一些理论，内容主要如下：1.1 共轭方向的概念与性质 在优化方法中，共轭方向有着重要的意义.一些有效的无约束优化算法大多是以共轭方向作为搜索方向的.共轭梯度法就是共轭方向法的一种.若要使第二个

32、迭代点成为该正定二元二次函数的极小点，只要使两次一维搜索的搜索方向和关于函数的二阶导数矩阵为共轭就可以了.对于一般函数，共轭方向具有以下性质：(1)若 (1，2，)是以共轭的个向量，则对于正定二次函数从任意初始点出发，依次沿这个方向进行一维搜索，最多次即可达到极小点.(2)从任意两个点和出发，分别沿同一方向进行一维搜索，得到两个一维极小点和，则连接此两点构成的向量=-，与原方向关于该函数的二阶导数矩阵相共轭.2 共轭梯度法的计算公式 共轭梯度法是在每一迭代步利用当前点处的最速下降方向来生成二次函数的Hesse矩阵的共轭方向，并建立求在上的极小点的方法.根据这个思想，下面简单给出共轭梯度法的一些

33、计算公式.设 ，其中，为阶对称正定矩阵，为维常量，为实数，的梯度向量为 .详细求解过程在第二章中给出.于此同时我们还能给出计算步长的算式.设是上的一组线性无关的向量，则从任意指定的出发，按以下迭代产生的序列：取，； ：计算，取； 计算，得出； 如此进行下去，直到第步； ：计算，取；计算，得出 显然：1.2.2 应用研究近年来，随着模糊理论、神经网络等智能技术和计算机技术的发展，智能式的优化方法越来越受重视.现今，国内外主要研究的方法有：(1)神经网络优化方法7%BD%91%E7%BB%9C o 人工神经网络 人工神经网络的研究起源于1943年和 HYPERLINK :/wiki.mbalib

34、/w/index.php?title=Mc_Culloch&action=edit o Mc Culloch Mc Culloch和 HYPERLINK :/wiki.mbalib /w/index.php?title=Pitts&action=edit o Pitts Pitts的工作.在优化方面，1982年 HYPERLINK :/wiki.mbalib /w/index.php?title=Hopfield&action=edit o Hopfield Hopfield首先引入Lyapuov能量函数用于5判断网络的稳定性，提出 HYPERLINK :/wiki.mbalib /w/ind

35、ex.php?title=Hopfield%E5%8D%95%E5%B1%82%E7%A6%BB%E6%95%A3%E6%A8%A1%E5%9E%8B&action=edit o Hopfield单层离散模型 Hopfield单层离散模型； HYPERLINK :/wiki.mbalib /w/index.php?title=Hopfield&action=edit o Hopfield Hopfield和ion=edit o Tank Tank又发展了 HYPERLINK :/wiki.mbalib /w/index.php?title=Hopfield%E5%8D%95%E5%B1%82%

36、E8%BF%9E%E7%BB%AD%E6%A8%A1%E5%9E%8B&action=edit o Hopfield单层连续模型 Hopfield单层连续模型.1986年，Hopfield和Tank将电子电路与Hopfield模型直接对应，实现了硬件模拟； HYPERLINK :/wiki.mbalib /w/index.php?title=Kennedy&action=edit o Kennedy Kennedy和 HYPERLINK :/wiki.mbalib /w/index.php?title=Chua&action=edit o Chua Chua基于非线性电路理论提出了模拟电路模型

37、，并使用系统微分方程的Lyapuov函数研究了电子电路的稳定性.这些工作都有力地促进了对神经网络优化方法的研究.(2)模糊优化方法最优化问题一直都是模糊理论应用最为广泛的领域之一.自从 HYPERLINK :/wiki.mbalib /w/index.php?title=Bellman&action=edit o Bellman Bellman和 HYPERLINK :/wiki.mbalib /wiki/L.A.zadeh o L.A.zadeh L.A.zadeh在70年代初期对这一研究作出开创性工作以来，其主要研究集中在一般意义下的理论研究、 HYPERLINK :/wiki.mbali

38、b /wiki/%E6%A8%A1%E7%B3%8A%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92 o 模糊线性规划 模糊线性规划、 HYPERLINK :/wiki.mbalib /w/index.php?title=%E5%A4%9A%E7%9B%AE%E6%A0%87%E6%A8%A1%E7%B3%8A%E8%A7%84%E5%88%92&action=edit o 多目标模糊规划 多目标模糊规划、以及模糊规划理论在 HYPERLINK :/wiki.mbalib /wiki/%E9%9A%8F%E6%9C%BA%E8%A7%84%E5%88%92 o 随机规划

39、 随机规划及许多实际问题中的应用.主要的研究方法是利用模糊集的截集或确定模糊集的隶属函数将模糊规划问题转化为经典的规划问题来解决. (3)支持向量机方法支持向量机是由Vapnik领导的AT&TBell实验室研究小组在1963年提出的一种新的非常有潜力的分类技术，SVM是一种基于统计学习理论的模式识别方法，主要应用于模式识别领域.由于当时这些研究尚不十分完善，在解决模式识别问题中往往趋于保守，且数学上比较艰涩，这些研究一直没有得到充分的重视.直到90年代，统计学习理论的实现和由于神经网络等较新兴的机器学习方法的研究遇到一些重要的困难，比如如何确定网络结构的问题、过学习与欠学习问题、局部极小点问题

40、等，使得SVM迅速发展和完善，在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中.共轭梯度法在以上的优化方法中都得到了应用，例如，有学者就应用共轭梯度法对网络的权值和阂值进行优化计算，完成神经网络训练的方法；还有学者在支持向量机方法中应用共轭梯度法，得到了一种更有效的光滑支持向量机方法.除此之外，共轭梯度法还被应用于其他一些优化方法，由于本文对应用领域不做专门研究，其他应用共轭梯度法的优化方法不再详细列举.1.3 本文工作和结构安排本文研究的课题主要围绕无约束最优化方法下的共轭梯度法进行.通过一个具体的实际问题，结合参考资料已经自己所了解

41、的知识，建立一个求解该问题的共轭梯度算法；针对该算法，运用所学知识和一些学者的研究结果，对该算法在指定的搜索方向下的全局收敛性，进行讨论分析；基于以上的步骤实现后，通过MATLAB编程，代入实例中的相关数据得到一些相关的数值结果，最后对数据进行分析验证，判断该算法是否有效.具体内容安排如下：第一章为绪论.首先阐明了所选课题的研究背景和意义；然后介绍了共轭梯度法的研究现状；最后是全文的内容和结构安排.第二章引入共轭梯度法理论.简单的介绍最优化方法；然后详细的阐述共轭梯度法，并引入共轭梯度法的一些基本概念，计算公式和迭代步骤；引入一个实际问题，建立共轭梯度算法，为以后各章的研究奠定了基础.第三章分

42、析算法的全局收敛性.该章主要分两部分，第一部分先给出共轭梯度法的一些性质和收敛性定理；然后第二部分则是分析算法的全局收敛性，通过总结已有学者的研究结果，证明该算法在一定条件下具有全局收敛性.第四章验证算法的有效性.也是论文的关键部分，主要思想就是通过MATLAB编程，代入实例中的相关数据得到一些相关的数值结果，最后对数据进行分析验证，判断该算法是否有效.最后是结论.系统的总结了本文的研究工作，不仅指出了一些有待解决的问题，还展望了共轭梯度法未来的研究方向.第二章 共轭梯度法本章先简单的介绍最优化方法；然后详细的阐述共轭梯度法，并引入共轭梯度法的一些基本概念，迭代公式和迭代步骤；最后引入一个实际

43、问题，建立共轭梯度算法，为以后各章的研究奠定了基础. 最优化方法最优化方法大体可分为无约束最优化方法和约束最优化方法，而无约束最优化方法就是求元函数的极值的方法，它包括最速下降法，拟牛顿法，以及共轭梯度法和信赖域方法.其中最速下降法是以负梯度方向作为下降方向的极小化算法，又称梯度法，是1874年法国科学家Cauchy提出的，该方法是无约束最优化中最简单的方法；拟牛顿法是目前为止最为行之有效的一种算法，具有收敛速度快、算法稳定性强、编写程序容易等优点，在现今的大型计算程序中有着广泛的应用.我们知道约束优化问题是在自变量满足约束条件的情况下目标函数最小化的问题，其中约束条件既可以是等式约束也可以是

44、不等式约束,而约束最优化方法就是用来求解这一类问题的方法，它包括单纯形法，解线性规划的图解法，等式约束的罚函数法，以及Rosen梯度投影法.其中单纯形法是由美国数学家G.B.丹齐克于1947年首先提出来的，其理论根据是：线性规划问题的可行域是维向量空间中的多面凸集，其最优值如果存在，必在该凸集的某顶点处达到，而顶点所对应的可行解称为基本可行解.以上是最优化方法的一些基本介绍，接下来本文将讨论最优化方法下的共轭梯度法. 共轭梯度法理论 共轭梯度法的概念共轭梯度法是在每一迭代步利用当前点处的最速下降方向来生成二次函数的Hesse矩阵的共轭方向，并建立求在上的极小点的方法.这一方法早年称为共轭斜量法

45、，于1952年由Hestenes和Stiefle提出来，用于解正定系数矩阵的线性方程组.后经Fletcher和Reeves等人研究并应用于优化问题，取得了丰富的成果，共轭梯度法也成为当前最优化方法的重要算法类.共轭梯度法是利用目标函数的梯度逐步产生共轭方向并将其作为搜索方向的方法.本节先引进共轭方向的概念，讨论目标函数是二次函数产生共轭方向的方法，由此得到无约束二次规划问题的共轭梯度法，然后将该算法推广到求解一般的无约束非线性规划问题. 共轭方向及性质在第一章我们已经给出共轭方向的一些基本概念和性质，在此我们再次详细的介绍一下该概念，为后面建立共轭梯度算法做铺垫.定义 设是对称正定阵.若对非零

46、向量，有 (2-1)则称向量，对共轭. 例如=，则 ，所以向量，对共轭. 当时，(2-1)变为，即与互相正交，由此可见，“共轭”概念是“正交”概念的推广.定义 若对非零向量组中任意两个向量对共轭，即 ， ，成立，则称为的共轭向量组.定理 是共轭向量组，必是线性无关向量组.定理2.4 假设为连续可微的严格凸函数，且存在极小点，为一组线性无关的向量，则 (2-2)是在通过点由向量生成的维超平面上的唯一极小点的充要条件是： ， . (2-3) 证明 设，则，的表达式代入，令 =， .可证在上的极小点就是，则它应满足 ， . (2-4)将解出代入式(2-2)得，由式(2-4)既得式(2-3)成立.定理

47、2.5 设，正定，是关于为初始点顺次沿方向采用精确搜索进行迭代，则是在时，就是在上的最小点.这个定理说明，若能得到的个共轭方向，则从任一初始点出发，顺次沿方向采用精确搜索求步长进行迭代，则步迭代后得到的点是上的最小点，步迭代后，其最后一点即为在上的最小点.这一定理又称为扩张子空间定理.2.2.3 共轭梯度法的公式结构共轭梯度法是在每一迭代步利用当前点处的最速下降方向来生成二次函数的Hesse矩阵的共轭方向，并建立求在上的极小点的方法.根据这个思想，可以给出共轭梯度法的公式结构.设 ，其中，为阶对称正定矩阵，为维常量，为实数，的梯度向量为 . (2-5) 我们取第一个方向为初始点处的负梯度方向，

48、即 =，从出发沿做精确一维搜索求的步长，得点 ，由定理2.4可得满足条件 . (2-6)在处，我们可以用的负梯度方向与的组合来生成方向，即令 =+ (2-7)选取一个系数使得与关于共轭，即令 (2-8)通过这个式子我们可以确定系数将式(2-7)代入式(2-8)可得 . (2-9)由式(2-5)得 ， (2-10)因此 . 又由式(2-6)可知，上式可简化为 ， (2-11)一经求出，出发沿方向的步长为，有 ， 则令方向 ， (2-12)选取待定系数与，使满足共轭条件 ， (2-13)即要求方向与，共轭. 将式(2-12)代入式(2-13)并解出 ， ， (2-14) 代回式(2-12)便可得.

49、由式(2-7)和(2-10)知，是与即与的线性组合，而是与的线性组合，由定理2.5，即扩张子空间定理，可知与，从而 =0. (2-15) 类似地，可得 . (2-16)从而式(2-12)中的方向仅由两项组合而成.我们要证明这一性质对一般情形也成立，下面给出证明.一般地，若已得及，则令 ， (2-17)为使与共轭，选择，满足共轭条件 ， ， (2-18)将式(2-17)代入式(2-18)并利用共轭性，可得 . (2-19)在式(2-17)中，令，并且写成，由定理2.4可知 ， . (2-20)接下来我们要证明，在式(2-19)中 ， (2-21)与 成立，即对任一均有式(2-12)的只含两项的简

50、单结构.类似式(2-10)和式(2-16)，我们有 及 . (2-22)由此可得 ，由式(2-20)及上式，便可得到 ，. 这一重要性质，使得我们在求各时避免了式(2-17)中的繁复计算，每次产生的共轭方向只由处的与两项组成，从而得到了结构简单的共轭梯度法.下面给出组合系数的另一种公式表示.由于，所以 .在式(2-17)中，应用的表达式，即 再由定理2.4，可得 ， 从而得到公式(2-21) (2-23)又由式(2-20)，这样便可得到由Fletcher-Reeves给出的公式(简称FR公式) (2-24)如上，采用FR公式的共轭梯度法，称为Fletcher-Reeves共轭梯度法. 共轭梯度

51、法的算法步骤根据不同的函数结构，我们会得出不同的共轭梯度算法，而利用共轭梯度法求解二次凸函数的最小点，在我们的理论学习中最常见而且应用相当熟练.下面我们给出共轭梯度法求二次凸函数的最小点的算法步骤.步骤1 任取初始点，令 ，转步骤3.步骤2 对，计算及， ， (2-25)步骤3 线性搜索求步长： .令.步骤4 若，则计算结束，.否则转步骤5.步骤5 令，转回步骤2. 共轭梯度法的优点近年来，随着计算机的飞速发展和实际问题中大规模优化问题的涌现，再加上共轭梯度法具有相当多的优点，使得寻找快速有效的共轭梯度法成为了学者们研究的热门方向之一.主要优点有：(1)共轭梯度法不仅克服了最速下降法收敛慢的缺

52、点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，使得共轭梯度法已成为解大型非线性最优化最有效的算法之一.(2)共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向d仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，共轭梯度法具有存储量少、计算方便的优点.(3)共轭梯度法不需要矩阵存储，所以它具有较快的收敛速度和二次终止性等优点.2.3 算法实例我们知道，共轭梯度法是在每一迭代步利用当前点处的最速下降方向来生成二次函数的Hesse矩阵的共轭方向，并建立求在上的极小点的方法.所以我们要先生成共轭方向，再建立求解方法.例1 ，为，求共轭方向，.解 由题可知，

53、取初始点，由，得，.然后求从出发沿方向的线性最优步长： .令，因而 .由定理2.5可知，解得.所以有 .计算处的和，有 ， .因而.由上可知共轭方向，.从上面的例子中，我们可以很容易的得到二元二次方程共轭方向的求解过程，而对于三次以上的方程，由于计算复杂，在此不列出详细求解过程.接下来我们都将讨论二元二次方程的求解过程，从简单的求解过程当中理解什么是共轭梯度法，以及如何熟练的应用共轭梯度法求解，这些即是本文的主要目的.下面给出的例子，详细给出了共轭梯度法的全部求解过程，并最终求得方程的最小解.而且这个例子将被用在第四章，作为MATLAB编程的算法实例.例2 用共轭梯度法求的最小解.解 取初始点

54、，由，得 ，.然后求从出发沿方向的线性最优步长： .令，因而 .由定理2.5可知，解得.所以有 .计算处的和，有 ， .因而 .求从出发沿方向的线性最优步长.令 ， (2-26)将的表达式代入中，得 =.同样的有 ，解得 .再将的值代入式（2-26），可得 .以代入中，得， .值得注意的是，在共轭梯度法中，初始方向应取最速下降方向，否则产生的方向不一定是共轭方向.例3 用共轭梯度法求的最小点.解 取初始点，由题可知，取初始方向，令，则.从方程中，解出沿的步长.因而 ，.由于，可得.接下来验证.取，因而可得 .这说明与对不共轭，从出发沿方向求解也得不到的最小点.这个例子充分解释了，在选取初始方向

55、时，应取最速下降方向，否则产生的方向不一定是共轭方向.第三章 算法的收敛性本章主要分两部分，第一部分先给出共轭梯度法的一些性质和收敛性定理；然后第二部分则是分析算法的收敛性，通过总结已有学者的研究结果，证明该算法在一定条件下具有全局收敛性. 共轭梯度法的性质与收敛性定理 共轭梯度法的性质定理 对于二次凸函数，若用共轭梯度法求解且采用线性最优步长，则算法对任一迭代步，有下述关系式成立： ， ， (3-1) ， ， (3-2) ， (3-3)且算法最多步便可求得的最小点. 证明 利用归纳法.由共轭梯度法的计算公式，若初始点为，则取初始方向，又由步长采用精确线性搜索求得，因而步长满足关系即.由，的选

56、择使，即式(3-1)的定义，当时式(3-3)时式(3-1)，(3-2)，(3-3)均成立.现设对于任一迭代步，式(3-1)式(3-3)均成立，要证时，它们也成立.由式(2-5)可得 ， . (3-4)下面证明式(3-1)和式(3-2)当(3-4)和式(2-25)，可得 (3-5)又由的定义，以及在式(3-4)中，令，可得 . (3-6) 由归纳假设，式(3-1)式(3-3)，当时成立，因而式(3-5)与式(3-6)的右端都为零，即 , ,， (3-7)成立，亦即式(3-1)和式(3-2)当时对也成立.当时，式(3-5)可写成 .对于，我们在式(3-4)中两边乘，注意到，将解出，利用式(3-3)

57、的归纳假设，可得的另一个表达式 . (3-8)将此式代入上式，可得 (3-9)成立，即式(3-2)对成立.对于式(3-1)，当时，式(3-6)变为 ，利用式(3-8)以及的FR公式，可知 (3-10)成立，亦即式(3-1)成立.对于式(3-3)，当时，由的定义及精确搜索，可得. (3-11)因而上述式(3-9)式(3-11)当时也成立，这就充分证明了式(3-1)式(3-3)当时也成立. 共轭梯度法的收敛性定理前面我们已经简要给出了FR共轭梯度法，下面我们简述一下FR共轭梯度法应用于极小化非二次函数时，在精确一维搜索与非精确强Wolfe搜索下的收敛性问题.因此，现在我们要引用一维搜索与强Wolf

58、e搜索的基本概念.在迭代算法求步长的计算中，要有充分下降性要求，否则当移动步长很小时，点与点很接近，函数值与的有效方法.令 ，若使的方法，称为一维搜索方法. 一维搜索方法有多种，下面介绍两种常用的方法.(1)线性最优步长 在式()中求()的最小点或第一个极小点对于的步长.这种方法是理论上的，常在理论论证中使用，称为精确线性搜索.而且在上章的算法实例中都使用了该方法求线性最优步长.(2)Wolfe方法给定数，.求使下列两个不等式 ， (3-12) (3-13)(3-13)有时也可用更强的条件 (3-14)(3-12)和条件(3-14)则称为强Wolfe充分小，则式(3-14)就变成了近似精确线性

59、搜索.接下来是给出共轭梯度法的一些收敛性定理，同样是针对FR共轭梯度法.对于FR共轭梯度法，对于当前点，令 ， ， (3-15)其中的组合系数 ，. (3-16)作一维搜索求，令 ， (3-17)重复上述计算.算法停止规则，可取.定理 （FR共轭梯度法的收敛性定理）设连续可微，水平集有界，则当FR算法采用一维精确搜索应用于极小化时，若产生的迭代点列为，则有以下结论：(1)若为有穷点列，则其最后一点为的稳定点.(2)若为无穷点列，则其任一极限点是的稳定点. 证明 (1)当为有限点列时，由停止规则可知，点列的最后一点有，因而为的稳定点或近似稳定点.(2)若为无穷点列，则有与.由式(3-15)及一维

60、搜索性质可得 ，是在处的一个下降方向，因而 ，是单调下降序列且点列.由水平集合有界，可知为有界序列且必有极限点存在.设极限点为，则存在的子列，使得 .因为，所以.由的连续性,可知对于，有 .同理，也是有界点列，因而有极限点及子列，当时， ， . 于是，我们得到 . (3-18)接下来证明.用反证法，设，并令，则在处，对于充分小的，有 成立.由一维精确搜索， ，因而，对，当时，由上面的结果可得 ，此式与式(3-18)矛盾，即.从而证明了极限点为稳定点.当FR方法采用强Wolfe非精确搜索时，又有如下的收敛性定理.定理3.3 设二阶连续可微，水平集有界，步长采用强Wolfe非精确搜索，且，则对FR