已阅读5页,还剩14页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
BatchDoc Word文档批量处理工具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: Information and Computation Science Grade: 2007Students Name: Xiao WenzhenStudent No.: 200705050318Tutor: Cao Xianglian(Assistant)He Bin(Professor) Finished by May, 2011毕业论文(设计)原创性声明本人所呈交的毕业论文(设计)是我在导师的指导下进行的研究工作及取得的研究成果。据我所知,除文中已经注明引用的内容外,本论文(设计)不包含其他个人已经发表或撰写过的研究成果。对本论文(设计)的研究做出重要贡献的个人和集体,均已在文中作了明确说明并表示谢意。 作者签名: 日期: 毕业论文(设计)授权使用说明本论文(设计)作者完全了解红河学院有关保留、使用毕业论文(设计)的规定,学校有权保留论文(设计)并向相关部门送交论文(设计)的电子版和纸质版。有权将论文(设计)用于非赢利目的的少量复制并允许论文(设计)进入学校图书馆被查阅。学校可以公布论文(设计)的全部或部分内容。保密的论文(设计)在解密后适用本规定。 作者签名: 指导教师签名:日期: 日期: 肖文真 毕业论文(设计)答辩委员会(答辩小组)成员名单姓名职称单位备注副教授红河学院数学学院主席(组长)副教授红河学院数学学院冯祖针助 教红河学院数学学院李 灿助 教红河学院数学学院曹香莲 助 教红河学院数学学院BatchDoc Word文档批量处理工具BatchDoc Word文档批量处理工具摘 要本文给出了一种新的求解非线性无约束优化问题的共轭梯度算法该算法允许初始点任意,在推广的强Wolfe线搜索下具有下降性,并且在适当的条件下具有全局收敛性关键词:无约束最优化;共轭梯度法;下降性;线搜索;全局收敛性ABSTRACT A new nonlinear conjugate gradient type formula for unconstrained optimization problems is presentedThe algorithm allows initial point is at random, the method 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第四章 全局收敛性7第五章 结束语9参考文献10致谢12BatchDoc Word文档批量处理工具第一章 引言 本文主要考虑无约束最优化问题 (1-1)其中为上的连续可微函数共轭梯度算法是用来求解无约束优化问题(1-1)的一种方法,其迭代格式是 (1-2) (1-3)其中,为搜索方向,为的梯度,为某种参数共轭梯度法最早是1952年由计算数学家 Hestenes和几何学家Stiefel为求解线性方程组,时提出的由于解线性方程组等价于求解极小化的正定二次函数,因此,他们提出的方法也可视为求二次函数极小值的共轭梯度法1964年,Fletcher和Reeves将此方法推广到非线性优化,得到了求解一般函数极小值的共轭梯度算法共轭梯度算法是最优化理论中最常用的方法之一,它具有算法简单,存储需求小等优点,十分适合大规模优化问题石油勘探、大气模拟、航天航空等领域出现的特大规模的优化问题常常利用共轭梯度算法求解符号说明:表示上的欧式范数,是f的梯度函数在点的值是由算法产生的点列若为当前的迭代点,则记为非线性共轭梯度算法的基本步骤4(1) 给出初始值;(2) 如果,则停;否则利用某种搜索方法求;令;(3) 利用某种公式计算参数,z转步(2); 可由精确线搜索求得但在实际计算中精确线搜索要求准确度高,计算量较大,故实际计算中常常进行非精确线搜索 在应用中可由非精确线搜索求得: (1) 弱Wolfe-powell规则 寻找一个,满足 , , (2) 强Wolfe-powell规则 寻找一个,满足, (1-4) , (1-5) (3) Armijo规则寻找一个,其中,是最小的正整数,满足,.(4) Armijo-Goldstein规则寻找一个,满足, (5) 推广的Wolfe准则 寻找一个,满足,上式中,为常数,且不同的对应不同的共轭梯度算法著名的共轭梯度法有:, FR方法在计算方面的表现并不十分理想,但采用精确先搜索时可是证明FR方法对一般的非凸函数总是收敛的.而采用强Wolfe线搜索的FR方法只要每一步的搜索方向下降,则此方法可以在适当的函数假定下全局收敛.PRP方法是目前认为数值表现最好的共轭梯度算法之一,当算法产生一个小步长时,由PRP方法定义的搜索方向自动靠近负梯度方向,从而较为有效地避免了FR方法可能连续产生小步长的缺点.CD方法的一个很重要的一个性质是:只要强Wolfe条件(1-4)和(1-5)条件中的参数方法在每次迭代均产生一个下降方向,而这时FR方法和PRP方法对一致凸函数都有可能产生上升搜索方向.虽然CD方法在Wolfe线搜索时能够保证每个搜索方向都下降,但全局收敛性不好,Dai和Yuan在文献5中严格证明了采用强Wolfe线搜索的DY方法在每一步产生一个下降方向,并且证明了该方法的全局收敛性.文献6对共轭下降法的收敛性做了进一步的分析;文献7-10对共轭下降法的作了改进,得到了包含共轭下降法的一类无约束优化方法,并证明了全局收敛性;文献11-20对FR方法的作了改进,得到了一类新的共轭梯度法并证明了全局收敛性鉴于上述文献及其他相关文献的思路,本文给出了一个新的: (1-6) 其中 当得到了新的共轭梯度法,并证明了其在适当条件下的全局收敛性BatchDoc Word文档批量处理工具BatchDoc Word文档批量处理工具BatchDoc Word文档批量处理工具第2章 共轭梯度算法本文对目标函数作如下假设:(1)在上连续可微有界;(2)的梯度函数是Lipschitz连续的,即存在,使得: 采用推广的Wolfe准则确定步长,即要求满足: (2-1) (2-2)式(2-1)和(2-2)中,为常数,且取,即: (2-3) 本文收敛性采用搜索条件(2-1)和(2-3)具有下降性的共轭梯度算法如下:(1),令,若,则停;否则,转(2);(2) 令,满足(2-1)和(2-3);(3) 计算,若,则停;否则令,转(4);(4) 令,其中满足(1-6),转(2)注:文献13中非精确线搜索条件保证的存在性 BatchDoc Word文档批量处理工具第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),步长由(2-1)、(2-2)求出,则有 证明: 由,知 ,k=1,2由(2-2)式及Lipschitz条件有, 所以 . (3-2) 其中 由的收敛性及(3-2)式知,结论成立.BatchDoc Word文档批量处理工具BatchDoc Word文档批量处理工具第4章 全局收敛性定理 4.1 假设成立的条件下,考虑共轭梯度法式(1-1)、(1-2)和(1-3) ,如果步长满足条件(2-1)和(2-3),参数取值满足,则算法产生的迭代点列或对某个有下式成立: 证明:用反证法,若定理不成立,即存在c0,使,k=1,2由 (4-1)将(4-1)式两边取模平方,得 (4-2)又由(3-1)式得 由(2-3)知,所以所以 得将代入(4-2)式得两边同除以可得: 由上式递推可得即与定理(3-2)矛盾,所以全局收敛性得证BatchDoc Word文档批量处理工具BatchDoc Word文档批量处理工具第五章 结束语本文主要讨论了无约束优化问题的算法,给出了一个新的,即构造了一个新的共轭下降方向,从而得到一类新的共轭梯度算法,且该算法允许初始点任意,并且具有全局收敛性共轭梯度算法是常用的求解无约束优化问题的有效方法,进一步对它深入研究能否得到更好的混合算法,这是值得研究的由于时间和本人水平有限,本论文提出的算法没有给出具体的数值试验,这是进一步要做的工作参考文献1 Hestenes M R. Iterative method for solving linear equationsJ. JOTA, 1973, 11(4):323-3342 Stiefel E. Uber einige methoden der relaxationsrechnungJ. Zeitschrift fr 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. Itertive 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 optimization: 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 杜学武. 一类新共轭下降算法的全局收敛性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线搜索下新的共轭梯度法的全局收敛性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 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致谢 毕业论文暂告收尾, 这也意味着我在红河学院四年的学习生活既将结束. 回首既往,自己一生最宝贵的时光能
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2027届高三地理一轮复习《地球的历史与圈层结构》教学设计
- 小学四年级心理健康教学设计:第五单元 第13课 同窗情谊深
- 初中七年级数学有理数加法运算律教学设计
- 十五五智能下悬窗:数据合规下的用户隐私保护与信任机制
- 中游算法迭代:智能拉伸器关键技术与感知精度提升
- 工业机器人仓储调度优化指南
- 食品生产部门主管能力评估表
- 有关2026年新合作框架协议的沟通说明(6篇)范文
- 工业自动化产线柔性生产指导书
- 医疗健康领域医生临床治疗绩效评估表
- 护理学导论期末复习知识点归纳总结
- 中医养生功法选介
- 雨课堂学堂在线学堂云《园艺植物研究法( 宁夏)》单元测试考核答案
- 企业文化建设咨询服务合同
- 雨课堂在线学堂《医学实验技术与方法新进展》单元考核测试答案
- 2025年陕西省公务员行测(A类)真题及答案
- 项目经理带班记录
- 国家基本公共卫生服务项目培训课件
- 2025年ISO90012015内审员培训测试卷含答案
- (正式版)DB32∕T 5139-2025 《滑坡崩塌地面塌陷精细调查与风险评价规范》
- 实验五金属有机框架MOF纳米材料的合成与制备87课件
评论
0/150
提交评论