一类具有全局收敛性的共轭梯度法

2015年度本科生毕业论文（设计）一类具有全局收敛性的共轭梯度法院－系:数学学院专业:信息与计算科学年级:2011级学生姓名:马冲学号:201101050107导师及职称:曹香莲(讲师)2015年4月2015AnnualGraduationThesis(Project)oftheCollegeUndergraduateAConjugateGradientMethodwithGlobalConvergenceDepartment:InstituteofmathematicsMajor:InformationandComputingScienceGrade:2011Student’sName:MaChongStudentNo.:201101050107Tutor:CaoXianglian(Lectuter)April,2015毕业论文（设计）原创性声明本人所呈交的毕业论文（设计）是我在导师的指导下进行的研究工作及取得的研究成果，据我所知，除文中已经注明引用的内容外，本论文（设计）不包含其他个人已经发表或撰写过的研究成果。对本论文（设计）的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意。作者签名:日期:毕业论文（设计）授权使用说明本论文（设计）作者完全了解红河学院有关保留、使用毕业论文（设计）的规定，学校有权保留论文（设计）并向相关部门送交论文（设计）的电子版和纸质版。有权将论文（设计）用于非赢利目的的少量复制并允许论文（设计）进入学校图书馆被查阅。学校可以公布论文（设计）的全部或部分内容。保密的论文（设计）在解密后适用本规定。作者签名:指导教师签名:日期:日期:马冲毕业论文（设计）答辩委员会(答辩小组)成员名单姓名职称单位备注李薇副教授数学学院组长杨慧章讲师数学学院组员曾黎讲师数学学院组员曹香莲讲师数学学院组员红河学院本科毕业论文（设计）摘要本文给出了一种新的求解非线性无约束问题的共轭梯度算法,并证明了该方法在弱Wolfe线搜索下具有下降性和全局收敛性.关键词:无约束最优化；共轭梯度法；Wolfe线搜索；全局收敛性红河学院本科毕业论文（设计）ABSTRACTThispaperpresentsanewconjugategradientalgorithmforsolvingnonlinearunconstrainedoptimizationproblem,AndtheglobalconvergenceanddescentpropertyofthemethodaregivenundertheweakWolfelinesearch.Keywords:Unconstrainedoptimization；Conjugategradientmethod；Wolfelinesearch；Globalconvergence红河学院本科毕业论文（设计）目录第一章绪论..................................................................................................................11.1无约束最优化.................................................................................................11.1.1最速下降法...........................................................................................11.1.2共轭梯度法...........................................................................................21.2线搜索方法.....................................................................................................21.2.1精确线搜索...........................................................................................21.2.2Armijo线搜索技术.............................................................................21.2.3Wolfe-Powell线搜索技术.................................................................3第二章问题的提出......................................................................................................4第三章共轭梯度法的算法及其全局收敛性..............................................................63.1算法.................................................................................................................63.2算法的下降性.................................................................................................63.3算法的全局收敛性.........................................................................................7第四章结论................................................................................................................10参考文献......................................................................................................................11致谢..........................................................................................................................12红河学院本科毕业论文（设计）1第一章绪论1.1无约束最优化追求目标最优化是人们共同的愿望,最优化也就是从许多可能的方案中选出最佳的方案,使得目标达到最优化.第二次世界大战结束后,最优化的理论和算法得到迅速兴起和发展,最后衍变成为一门应用数学分支,它是一门应用性和实用性都十分强的学科.虽然在很早的极值问题中已经涉及到了最优化问题,但是一直到了二十世纪中叶乔治·伯纳德·丹齐格提出一般线性规划问题的单纯形法之后,才使得它成为一门真正独立的学科.近半个世纪以来,随着现代科学技术的发展和电脑在生活中的广泛运用,才推动了最优化问题的快速发展以及对其理论和算法的研究与运用.如今最优化理论的方法已经广泛运用于生产生活、信息管理、国防军事、商业投资、交通运输、经济规划等方面.无约束最优化的计算方法在生活中有着广泛的实际应用,与约束最优化的计算方法也有着十分重要的联系:首先有些处理无约束最优化问题中运用到的方法可以直接运用到约束最优化问题中；其次有的约束最优化问题还可以转变成无约束最优化问题来解决.所以说,无约束最优化的计算方法也可以运用到处理约束最优化问题中去.在近半个世纪以来,关于无约束最优化问题的理论和算法得到快速发展并且日趋成熟.随着电脑的发展与普及,无约束最优化方法在建筑设计、信息分类、系统管理等方面的应用越来越广,已经受到更多相关部门的重视,因此对研究与运用无约束最优化问题有着重大的意义.无约束最优化问题[1]:min()fx,其中1:nfRR,这个问题的求解是指,在nR中找到一点*x,使得对于任意的nxR都有:*()()fxfx.常用的无约束最优化方法一般有最速下降法、Newton法、修正Newton法、共轭梯度法、变尺度法等,其中介绍两种本文中主要用到的算法:最速下降法和共轭梯度法.1.1.1最速下降法基本思想:从点1x处出发,选择目标函数()fx的负梯度方向作为每一步的第一章绪论2搜索方向,以便于尽快达到极小点.特点:kx的负梯度方向,仅仅是在kx点的附近才具有使函数下降最快的性质,但是对于求最优解的整个过程来说就不是这样的.在一定的条件下,最速下降法是线性收敛的,收敛速度较慢.当初始点1x离最优点*x较远时,一般来说下降速度较快,效果也较好,在求最优解的前期,使用最速下降法是一种比较有效的方法.1.1.2共轭梯度法基本思想:它是一个比较典型的共轭方向法,它的每一个搜索方向都是相互共轭的,而这些搜索方向kd仅仅是负梯度kg与上一次迭代的搜索反向1kd的组合,然后再沿着kd的方向进行最优化搜索.特点:从理论上讲,如果目标函数是正定二次函数,利用共轭梯度法求解最优解的过程中,在n步以内必可达到极小点*x,它具有二次终止性.但在实际的计算过程中,由于计算误差和其他因素的影响,从而导致了经过n步迭代没有得到更加接近精确结果的解,如果说目标函数没有进入到一个正定二次函数的区域,就要将搜索方向重新开始,即将nx作为新的初始点,用重新设置负梯度方向的措施来加速收敛.其中比较常用的共轭梯度法有FR法、PRP法、HS法、CD法、DY法等.1.2线搜索方法[2]1.2.1精确线搜索精确线搜索就是要求步长ka满足:0()min()kkkkkafxadfxad,由精确线搜索的条件可知,精确线搜索中确定的步长ka满足:()0.Tkkkgxadd红河学院本科毕业论文（设计）31.2.2Armijo线搜索技术给定常数0,1,(0,1),求max,0,1,2,,jkaj使它满足:1()()0Tkkkkkkkfxadfxagd.由于kd是f在kx处的下降方向,且满足0Tkkgd,容易证明,不等式对充分小的正数ka均成立.1.2.3Wolfe-Powell线搜索技术给定1,2满足101/2,121,求0ka,使满足:1()()Tkkkkkkkfxadfxagd,2()TTkkkkkkgxaddgd.第二章问题的提出4第二章问题的提出本文主要考虑无约束优化问题:min(),,nfxxR（2-1）其中nR是n维欧几里得空间,:nfRR是一个连续可微函数.求解问题（2-1）常用的共轭梯度算法,由Fletcher和Reeves提出.共轭梯度法的一般迭代格式为:1,0,1,2...kkkkxxdk(2-2)1,1;,1,kkkkkgkdgdk(2-3)其中()kkgfx,kx为当前迭代点,kg为当前迭代点kx处的梯度,kd为搜索方向,k是通过一维线搜索获得的步长,k为共轭参数.关于k的计算有着不同的共轭梯度算法,常见的k有以下这些形式[3]:221kFRkkgg,121TPRPkkkkgyg,111THSkkkTkkgydy,111TLSkkkTkkgydg,211kDYkkkgdy,211kCDkkkgdg.其中向量的Euclidean范数用表示,11kk