一种修正的PRP共轭梯度法2

2015年度本科生毕业论文（设计）一种修正的PRP共轭梯度法院－系：数学学院专业：信息与计算科学年级：2011级学生姓名：黄丽学号：201101050166导师及职称：曹香莲(讲师)2015年4月2015AnnualGraduationThesis(Project)oftheCollegeUndergraduateAModifiedPRPConjugateGradientMethodDepartment:CollegeofMathematicsMajor:InformationandComputingScienceGrade:2011Student’sName:HuangLiStudentNo:201101050166Tutor:CaoXianglian（Lecturer）April,2015毕业论文（设计）原创性声明本人所呈交的毕业论文（设计）是我在导师的指导下进行的研究工作及取得的研究成果．据我所知，除文中已经注明引用的内容外，本论文（设计）不包含其他个人已经发表或撰写过的研究成果．对本论文（设计）的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意．作者签名：日期：毕业论文（设计）授权使用说明本论文（设计）作者完全了解红河学院有关保留、使用毕业论文（设计）的规定，学校有权保留论文（设计）并向相关部门送交论文（设计）的电子版和纸质版．有权将论文（设计）用于非赢利目的的少量复制并允许论文（设计）进入学校图书馆被查阅．学校可以公布论文（设计）的全部或部分内容．保密的论文（设计）在解密后适用本规定．作者签名：指导教师签名：日期：日期：黄丽毕业论文（设计）答辩委员会(答辩小组)成员名单姓名职称单位备注李薇副教授红河学院数学学院组长曹香莲讲师红河学院数学学院组员曾黎讲师红河学院数学学院组员杨慧章讲师红河学院数学学院组员红河学院本科毕业论文（设计）摘要非线性共轭梯度算法是无约束优化问题中的一个重要组成部分，时常用来解决一些大规模的无约束最优化问题．本文提出一个修正的PRP共轭梯度法，并在广义的Wolfe线搜索下，证明了该算法的充分下降性和全局收敛性.关键词：共轭梯度法；充分下降；全局收敛性红河学院本科毕业论文（设计）ABSTRACTThenonlinearconjugategradientmethod，whichwasusedforsolvingunconstrainedoptimizationproblems，isanimportantcomponentofoptimizationmethods．Inthepaper，theauthorproposedamodifiedPRPconjugategradientmethod．Inthesuitableconditions，thesufficientdescentandglobalconvergencecanbeproved．Keywords：Conjugategradientmethod；Thesufficientdescentproperty；Globalconvergence红河学院本科毕业论文（设计）目录第一章绪论..................................................................................................................11.1研究背景与意义.............................................................................................11.1.1最优化问题..........................................................................................11.1.2无约束最优化问题的解法..................................................................11.2非精确线搜索.................................................................................................21.3经典的非线性共轭梯度法回顾.....................................................................31.3.1PRP方法...............................................................................................31.3.2CD方法.................................................................................................31.3.3FR方法.................................................................................................31.3.4HS方法.................................................................................................31.3.5DY方法.................................................................................................4第二章一个修正PRP共轭梯度法的提出..................................................................5第三章算法的充分下降性以及全局收敛性..............................................................63.1算法的下降性分析.........................................................................................63.2算法的全局收敛性分析................................................................................7第四章总结与展望....................................................................................................10参考文献......................................................................................................................11致谢..............................................................................................................................12红河学院本科毕业论文（设计）1第一章绪论1.1研究背景与意义1.1.1最优化问题最优化问题在生活中是一类很实用的问题，它是一门应用性质很强的学科,在许多领域（如工程设计、化学、环境科学、生物科学等）有着广泛的应用．最优化理论与方法是计算科学的一个重要组成部分，实质上是一个求极值的问题．如今，其在工程设计与科学应用中无处不在，对发展科技起到非常大的作用．本文主要考虑求解无约束最优化问题的共轭梯度法，用来求解某些问题的最优解，构造寻求最优解的方法．最优化问题的数学模型一般如下:xfmints.,0xci.,,2,1mi,0xci.,,1pmi其中nnRxxxx,,,21，RRfn:,PiRRcni,2,1:是连续函数,一般还要求连续可微,x是决策变量，)(xf为目标函数,pixci,,2,1,是约束条件．mixci,,2,1,0为等式约束，pmixci,1,0为不等式约束．在现实生活中，我们要将实际问题转化为数学模型，并且用最优化算法求解．1.1.2无约束最优化问题的解法关于求解最优化问题，如果不考虑它的约束条件，就变成了求解无约束优化问题．目前，求解无约束最优化问题的方法主要有牛顿法、拟牛顿法、最速下降法、共轭梯度法等．牛顿法[1]最初由艾萨克·牛顿于1736年在MethodofFluxions中公开提出．是一种经典的无约束最优化方法，牛顿法收敛速度非常快，具有二次收敛的优点．但是在使用牛顿法求解时，需要)(2kxf正定，否则k不一定是下降方向．且牛顿法方向构造困难，计算复杂，占用内存相当的大．拟牛顿法(Quasi-NewtonMethods)[1]最初是由美国物理学家W.C.Davidon于20世纪50年代所提出，此算法具有收敛速度较快的优点，但在大规模问题上，存储方面的开销是巨大的．第一章绪论2最速下降法[1]也称梯度下降法，大多数有效的算法都是以它为基础而得到的，最速下降法是用负梯度方向为搜索方向的，最速下降法(SteepestDescentMethods)和拟牛顿法一样只需计算每一步迭代时目标函数的梯度．但是，最速下降法越接近目标值，步长越小，前进越慢．共轭梯度法[1]是共轭方向法中的一个典型的方法，它计算方便，易编程实现，共轭梯度法只用它的梯度值和目标函数，从而降低了计算量和存储量．因此，它是求解无约束最优化问题的一种有效又实用的方法．共轭梯度法不要求精确的直线搜索．但是，不精确的直线搜索可能导致迭代出来的向量不再共轭，从而降低方法的效能．1.2非精确线搜索(1)Armijo线搜索[2]：给定1,0,1,0，求2,1,0,maxjjk满足条件kTkkkkkkdgxfdxf)(-)(．(1-1)(2)强Wolfe线搜索[2]：求k满足条件kTkkkkkkdgxfdxf)(-)(，(1-2)kTkkkkTkdgdxd)(g．(1-3)其中10．(3)广义的Wolfe线搜索[2]：求k满足条件kTkkkkkkdgxfdxf)()(，(1-4)kTkkTkkkkTkdgddxgdg21)(．(1-5)这里)1,(1，02．(4)Wolfe线搜索[2]：求k满足条件kTkkkkkkdgxfdxf)()(，(1-6)kTkkkkTkddxgdg)(．(1-7)(5)Goldshein线搜索[3]：红河学院本科毕业论文（设计）3求k满足条件kTkkkkkkkTkkdgxfdxfdg21)(-)(，(1-8)其中:121012．1.3经典的非线性共轭梯度法回顾一般的共轭梯度法形式如下：kkkkdxx1，．，2,1,1kdgkgdkkkkk下面主要介绍几种经典非线性共轭梯度法，不同的k代表着不同的共轭梯度法．1.3.1PRP方法PRP方法[4]是1969年被Polak和Ribieren和Polyakn所提出，迄今为止是被认为数值表现最好的共轭梯度法之一，它的参数PRPk公式如下：211kkkTkPRPkgggg．1.3.2CD方法共轭下降法[4]最早于1987年被Fletcher引入的，它的参数公式如下：112gkTkk