肖毕业论文(改)

1、2011年度本科生毕业论文(设计)一种新的全局收敛的共轭梯度算法院 系： 数学学院 专 业： 信息与计算科学 年 级： 2007级 学生姓名： 肖文真 学 号： 200705050318 导师及职称：曹香莲（助教）何斌（教授） 2011年5月2011Annual Graduation Thesis (Project) of the College Undergraduate Global Convergence of A New Kind of Conjugate Gradient MethodDepartment: College of Mathematics Major: Informat

2、ion and Computation Science Grade: 2007Students Name: Xiao WenzhenStudent No.: 200705050318Tutor: Cao Xianglian（Assistant）He Bin（Professor） Finished by May, 2011毕业论文（设计）原创性声明本人所呈交的毕业论文（设计）是我在导师的指导下进行的研究工作及取得的研究成果。据我所知，除文中已经注明引用的内容外，本论文（设计）不包含其他个人已经发表或撰写过的研究成果。对本论文（设计）的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意

3、。 作者签名： 日期： 毕业论文（设计）授权使用说明本论文（设计）作者完全了解红河学院有关保留、使用毕业论文（设计）的规定，学校有权保留论文（设计）并向相关部门送交论文（设计）的电子版和纸质版。有权将论文（设计）用于非赢利目的的少量复制并允许论文（设计）进入学校图书馆被查阅。学校可以公布论文（设计）的全部或部分内容。保密的论文（设计）在解密后适用本规定。   作者签名： 指导教师签名：日期： 日期： 肖文真 毕业论文（设计）答辩委员会(答辩小组)成员名单姓名职称单位备注副教授红河学院数学学院主席（组长）副教授红河学院数学学院冯祖针助 教红河学院数学学院李 灿助 教红河学院数学学院曹香

4、莲 助 教红河学院数学学院红河学院本科毕业论文 (设计)摘 要本文给出了一种新的求解非线性无约束优化问题的共轭梯度算法该算法允许初始点任意，在推广的强Wolfe线搜索下具有下降性，并且在适当的条件下具有全局收敛性关键词：无约束最优化；共轭梯度法；下降性；线搜索；全局收敛性ABSTRACT A new nonlinear conjugate gradient type formula for unconstrained optimization problems is presentedThe algorithm allows initial point is at random, the me

5、thod satisfies the descent condition in the condition of generalized strong wolfe steplength，and it has global convergence under the suitable conditionsKeywords：unconstrained optimization；conjugate gradient method；descent property；line search；global convergence目 录第一章 引言1第二章 共轭梯度算法4第三章 下降条件5第四章 全局收敛性

6、7第五章 结束语9参考文献10致谢12红河学院本科毕业论文 (设计)第一章 引言 本文主要考虑无约束最优化问题 (1-1)其中为上的连续可微函数共轭梯度算法是用来求解无约束优化问题(1-1)的一种方法，其迭代格式是 (1-2) (1-3)其中，为搜索方向，为的梯度，为某种参数共轭梯度法最早是1952年由计算数学家 Hestenes和几何学家Stiefel为求解线性方程组，时提出的由于解线性方程组等价于求解极小化的正定二次函数，因此，他们提出的方法也可视为求二次函数极小值的共轭梯度法1964年，Fletcher和Reeves将此方法推广到非线性优化，得到了求解一般函数极小值的共轭梯度算法共轭梯度

7、算法是最优化理论中最常用的方法之一，它具有算法简单，存储需求小等优点，十分适合大规模优化问题石油勘探、大气模拟、航天航空等领域出现的特大规模的优化问题常常利用共轭梯度算法求解符号说明：表示上的欧式范数，是f的梯度函数在点的值是由算法产生的点列若为当前的迭代点，则记为非线性共轭梯度算法的基本步骤4(1) 给出初始值；(2) 如果,则停;否则利用某种搜索方法求;令；(3) 利用某种公式计算参数,z转步(2)； 可由精确线搜索求得但在实际计算中精确线搜索要求准确度高，计算量较大，故实际计算中常常进行非精确线搜索 在应用中可由非精确线搜索求得： (1) 弱Wolfe-powell规则 寻找一个，满足

8、， ， (2) 强Wolfe-powell规则 寻找一个，满足， (1-4) ， (1-5) (3) Armijo规则寻找一个，其中，是最小的正整数，满足，.(4) Armijo-Goldstein规则寻找一个，满足， (5) 推广的Wolfe准则 寻找一个，满足，上式中，为常数，且不同的对应不同的共轭梯度算法著名的共轭梯度法有：, FR方法在计算方面的表现并不十分理想，但采用精确先搜索时可是证明FR方法对一般的非凸函数总是收敛的.而采用强Wolfe线搜索的FR方法只要每一步的搜索方向下降，则此方法可以在适当的函数假定下全局收敛.PRP方法是目前认为数值表现最好的共轭梯度算法之一，当算法产生一

9、个小步长时，由PRP方法定义的搜索方向自动靠近负梯度方向，从而较为有效地避免了FR方法可能连续产生小步长的缺点.CD方法的一个很重要的一个性质是：只要强Wolfe条件(1-4)和(1-5)条件中的参数方法在每次迭代均产生一个下降方向，而这时FR方法和PRP方法对一致凸函数都有可能产生上升搜索方向.虽然CD方法在Wolfe线搜索时能够保证每个搜索方向都下降，但全局收敛性不好，Dai和Yuan在文献5中严格证明了采用强Wolfe线搜索的DY方法在每一步产生一个下降方向，并且证明了该方法的全局收敛性.文献6对共轭下降法的收敛性做了进一步的分析；文献7-10对共轭下降法的作了改进，得到了包含共轭下降法

10、的一类无约束优化方法，并证明了全局收敛性；文献11-20对FR方法的作了改进，得到了一类新的共轭梯度法并证明了全局收敛性鉴于上述文献及其他相关文献的思路，本文给出了一个新的： (1-6) 其中 当得到了新的共轭梯度法，并证明了其在适当条件下的全局收敛性1 第一章 引言第二章 共轭梯度算法第2章 共轭梯度算法本文对目标函数作如下假设：(1)在上连续可微有界；(2)的梯度函数是Lipschitz连续的，即存在，使得： 采用推广的Wolfe准则确定步长，即要求满足： (2-1) (2-2)式(2-1)和(2-2)中，为常数，且取，即： (2-3) 本文收敛性采用搜索条件(2-1)和(2-3)具有下降

11、性的共轭梯度算法如下：(1)，令，若，则停；否则，转(2)；(2) 令，满足(2-1)和(2-3)；(3) 计算，若，则停；否则令，转(4)；(4) 令，其中满足(1-6)，转(2)注：文献13中非精确线搜索条件保证的存在性 红河学院本科毕业论文 (设计)第3章 下降条件 定理3.1 在假设成立的条件下，考虑共轭梯度法式(1-1)、(1-2)、(1-3)如果步长满足条件(2-1)和(2-2)，当取(1-6)式时，则算法对所有的k1，有下降性质 证明：当时，即，有假设当k=k-1时，有 (3-1)由于所以有 其中 所以，得证 定理3.2 在假设成立的条件下，考虑迭代格式(1-2)、(1-3),步

12、长由(2-1)、(2-2)求出，则有 证明: 由，知 ，k=1,2由(2-2)式及Lipschitz条件有， 所以 . (3-2) 其中 由的收敛性及(3-2)式知，结论成立.3 红河学院本科毕业论文 (设计)第4章 全局收敛性定理 4.1 假设成立的条件下，考虑共轭梯度法式(1-1)、(1-2)和(1-3) ，如果步长满足条件(2-1)和(2-3)，参数取值满足，则算法产生的迭代点列或对某个有下式成立： 证明：用反证法，若定理不成立，即存在c>0，使,k=1,2由 (4-1)将(4-1)式两边取模平方，得 (4-2)又由(3-1)式得 由(2-3)知,所以所以 得将代入(4-2)式得两

13、边同除以可得： 由上式递推可得即与定理(3-2)矛盾，所以全局收敛性得证红河学院本科毕业论文 (设计)红河学院本科毕业论文 (设计)第五章 结束语本文主要讨论了无约束优化问题的算法，给出了一个新的，即构造了一个新的共轭下降方向，从而得到一类新的共轭梯度算法，且该算法允许初始点任意，并且具有全局收敛性共轭梯度算法是常用的求解无约束优化问题的有效方法，进一步对它深入研究能否得到更好的混合算法，这是值得研究的由于时间和本人水平有限，本论文提出的算法没有给出具体的数值试验，这是进一步要做的工作参考文献1 Hestenes M R. Iterative method for solving linear

14、 equationsJ. JOTA, 1973, 11(4):323-3342 Stiefel E. Uber einige methoden der relaxationsrechnungJ. Zeitschrift für Angewandte Mathematik und Physik , 1952, 1(3): 1-333 Fletcher R, Reeves C M. Function minimization by conjugate gradientsJ. Compute Journal, 1964, 7(2): 149-1544 Hestenes M R. Itert

15、ive method for solving linear equation,NANLReport No 53-9,National Bureau of Standards,Washington D.C. 1973，1:322-3345 Dai Y H,Yuan Y.A nonlinear conjugate gradient method with a strong global convergence property J.SIAM Journal on Optimization,1999，10(1):177-1826 Fletcher R. Practical methods of op

16、timization: vol. 2: Constrained Optimization M, New York: John Wiley & Sons, 19817 Dai Y H, Yuan Y X. Convergence properties of the conjugate descentmethodJAdvances in Mathematics(In Chinese), 1996, 25(6):552-562 8 徐泽水. A class of new conjugate gradient methodsJ. 数学志,2002, 5(1):27-309 杜学武. 一类新共轭

17、下降算法的全局收敛性J数学的实践与认识, 2002, 32 (1):153-15710 焦宝聪, 陈兰平. 一类新共轭下降算法的全局收敛性J数学的实践与认识,，1998, 28(3):193-19611 杜学武, 叶留青, 徐成贤包含共轭下降法的一类无约束优化方法的全局收敛性J工程数学学报, 2001, 18(2):119-12112 柳娟, 谢铁军, 孙玉华. 一类共轭梯度法的全局收敛性J运筹与管理, 2007, 16(2):75-7813 范建芬, 谢铁军, 柳娟. 一族新的共轭梯度法的全局收敛性J运筹与管理, 2007, 16(2):65-6814 高丽, 谢铁军. Wolfe线搜索下新

18、的共轭梯度法的全局收敛性J运筹与管理, 2008, 2(1):38-4115 陈岩, 陈忠. 无约束优化问题的一种新共轭梯度法的全局收敛性J自然科学报, 2009, 6(2):129-13116 袁亚湘, 孙文瑜. 最优化理论与方法M. 北京:科学出版社,200617 Al-Baali M.Descent property and global convergence of the Flecher-Reeves method with inexact line searchJ.IMA,Journal of Numerical Analysis,1985, 5(1): 121-12418 Yu

19、G.H,zhao Y.L.and Wei Z.X.A descent nonlinear conjugate gradient formulas for large-scale unconstrained optimization problemsJ.Apll.Mput, 2006,179:407-43019 Yu G.H.,zhao Y.L.and Wei Z.X.A descent nonlinear conjugate method for large s- -cale unconstrained optimizationJ.J.Apll.Math.Comput,2007,187:636-64320 陈继红，焦宝聪.一种新的非线性共轭梯度算法的全局收敛性J.首都师范 大学学报(自然科学版),2006,27(3):1-4致谢 毕业论文暂告收尾, 这也意味着我在红河学院四年的学习生活既将结束. 回首既往，自己一生最宝贵的时光能于这样的校园之中,能在众