《最优化方法课程设计参考模版》由会员分享，可在线阅读，更多相关《最优化方法课程设计参考模版（23页珍藏版）》请在金锄头文库上搜索。
1、实用标准f誉魅林更&科找止厚K丿 niiHi ihAt ri rTDANir ifrriUNAi nnv?最优化方法?课程设计题目：共轭梯度法算法分析与实现院系：数学与计算科学学院专业：数学与应用数学姓名：梁婷艳学号：0800730103指导教师：李丰兵日 期：2021 年12 月30 日摘要在各种优化算法中,共轭梯度法是非常重要的一种.本文主要介绍的共轭梯 度法是介于最速下降法与牛顿法之间的一种无约束优化算法, 它具有超线性收敛 速度,而且算法结构简单,容易编程实现.在本次实验中,我们首先分析共轭方向法、对该算法进行分析,运用基于共 轭方向的一种算法一共轭梯度法进行无约束优化问题的求解.无约
2、束最优化方法的核心问题是选择搜索方向.共轭梯度法的根本思想是把共轭性与最速下降方法 相结合,利用点处的梯度构造一组共轭方向, 并沿这组方向进行搜索,求出 目标函数的极小点.根据共轭方向的根本性质,这种方法具有二次终止性.再结 合该算法编写matlab程序,求解无约束优化问题,再结合牛顿算法的理论知识, 编写matlab程序,求解相同的无约束优化问题,进行比拟分析,得出共轭梯度 法和牛顿法的不同之处以及共轭梯度法的优缺点.共轭梯度法仅需利用一阶导数信 息,防止了牛顿法需要存 储和计算 Hesse矩阵并求逆的缺点,共轭梯度法不仅是解决大型线性方程组最有用的 方法之一,也是解大型非线性最优化最有效的
3、算法之一.共轭梯度法是一 个典型的共轭方向法,它的每一个搜索方向是互相共轭的,而这些搜索方 向仅仅是负梯度方向与上一次迭代的搜索方向的组合,因此,存储量少, 计算方便.关键词：共轭梯度法；超线性收敛；牛顿法；无约束优化文案大全AbstractIn a variety of optimizati onalgorithms,con jugate gradie nt method isa very importa nt one.In this paper, the con jugate gradie nt method isbetwee n the steepest desce nt method
4、and Newt on method for uncon stra ined optimizatio n betwee n a method, it has superl in ear con verge nee rate, and the algorithm is simple and easy program ming.In this experime nt, we firstan alyze the con jugate direct ionmethod,the algorithm an alysis, the use of a con jugate directio n-basedal
5、gorithm-con jugate gradie nt method for uncon stra ined optimizati on problems. Unconstrained optimization method is to select the core issue of the search direct ion.Con jugate gradie nt method is the basic idea of thecon jugate desce nt method with the most comb ined points in the gradie nt using
6、the known structure of a set of con jugate direct ions, and search along the directi on of this group, find the minimum point of objective fun cti on. Accord ing to the basic n ature of the con jugate direct ion,thismethod has the quadratic term in atio n. Comb ined with the preparatio n of this alg
7、orithm matlab program for sol ving uncon stra ined optimizati on problems, comb ined with Newt on s theory of kno wledge, writi ng matlab program to solve the same problem of unconstrainedoptimization,comparis on an alysis, the con jugate gradie nt method and Newt on method differe nt Office and the
8、 adva ntages and disadva ntages of the con jugate gradie nt method.Con jugate gradie nt method using only first derivative in formati on, to avoid the Newt on method requires storage and comput ing the inv erse Hesse matrix and shortco min gs, is not only the con jugate gradie nt method to solve lar
9、ge linear systems one of the most useful, but also large-scale solution nonlinear optimization algorithm is one of the most effective.Con jugate gradie nt method is a typical conjugate direct ion method, each of its search directi on is con jugate to each other, and the search directi ond is just th
10、e n egativegradie ntdirecti onwith the lastiterati on of the search directi on of the portfolio, therefore, storage less computati onal complexity.Key words: Conjugate gradie nt method; Superl in ear con verge nee; Newt onmethod Uncon stra ined optimizati on目录1、弓丨言 62、共轭梯度法的描述 62.1共轭方向法 62.2共轭梯度法 72
11、.3 Armijo 准那么 63、数值实验 73.1代码实现 73.2算法测试 83.3结果分析 104、算法比拟 104.1牛顿法的构造 104.2算法实现 114.3算法测试 124.4算法比拟 135、总结 185.1总结概括 135.2个人感言 146、参考文献： 161、引言在各种优化算法中,共轭梯度法Conjugate Gradient 是非常重要的一种. 其优点是所需存储量小,具有N步收敛性,稳定性高,而且不需要任何外来参数.共轭梯度法是介于最速下降法与牛顿法之间的一个方法,它仅需利用一阶导数信息,但克服了最速下降法收敛慢的缺点,又防止了牛顿法需要存储和计算 Hesse矩阵并求逆
12、的缺点,共轭梯度法不仅是解决大型线性方程组最有用的方法 之一,也是解大型非线性最优化最有效的算法之一.共轭梯度法最早是又Hestenes和Stiefle 1952提出来的,用于解正定系数矩阵的线性方程组,在这个根底上,Fletcher 和Reeves 1964首先提出了解非线性最优化问题的共轭梯度法.由于共轭梯度法不需要矩阵存储,且有较快的收敛速度和二次终止性等优点,现在共轭梯度法已经广泛 地应用与实际问题中.共轭梯度法是一个典型的共轭方向法,它的每一个搜索方向是互相共轭的, 而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合,因此,存储量少,计算方便.2、共轭梯度法的描述2.1共轭方
13、向法共轭方向法是介于最速下降法与牛顿法之间的一个方法.它仅需利用一阶导数信息,但克服了最速下降法收敛慢的缺点,又防止了存贮和计算牛顿法所需要的二阶导数信息.共轭方向法是从研究二次函数的极小化产生的,但是它可以推广到处理非二次函数的极小化问题.一般共轭方向法步骤如下：算法2.1.1一般共轭方向法给出x*的初始点X.,步1计算g = f Xo步2计算do,使dig.： 0步3 令k =0步4计算k和Xk 1,使得心：kdQ 二 min f 仇：djaXk 1 = Xk kdk步5计算dk+使得d打Gdj =0, j =0,1,k.步6 令k k 1,转步4实用标准共轭方向法的一个根本性质是：只要执
14、行精确线性搜索,就能得到二次终止 性.这就是下面的共轭方向法根本定理.定理2.1.1共轭方向法根本定理对于正定二次函数,共轭方向法之多经n步精确线性搜索终止；且每一X都i是fX在X0和方向do,di所张成的线性流行xx = Xo +E a jdj ,Wa j 中的极 jJ小点.2.2共轭梯度法共轭梯度法是最著名的共轭方向法,它首先由Hestenes和Stiefel 1952提出来作为解线性方程组的方法.由于解线性方程组等价于极小化一个正定二次 函数,故1964年Fletcher和Reeves提出了无约束极小化的共轭梯度法,它是 直接从Hestenes和Stiefel解线性方程组的共轭梯度法开展
15、而来的.共轭方向 法根本定理告诉我们,共轭性和精确线性搜索产生二次终止性.共轭梯度法就是 使得最速下降方向具有共轭性,从而提升算法的有效性和可靠性.下面针对二次 函数情形讨论共轭梯度法,我们先给出共轭梯度法的推导.设1f xxT Gx bT x c2.2.1其中G是n n对称正定矩阵,b是n 1向量,c是实数.f的梯度为g(x)=Gx b(2.2.2)令do = -go(2.2.3)那么人(2.2.4)由精确线性搜索性质,g：d =0(2.2.5)令d -g ：0d0(2.2.6)dGdoT.(2.2.7)选择：0,使得文案大全实用标准对226 两边同乘以d：G ,得(2.2.15)文案大全g1 Gd0g1 (g1 g0)1TTd0 (g1 g0)dlGd.由共轭方向法根本定理,g；dj =0,i=0,1又令T g1 g T g.g.(228).利用2.2.3 和2.2.6,可g
