《一种新的全局收敛的共轭梯度算法.doc》由会员分享，可在线阅读，更多相关《一种新的全局收敛的共轭梯度算法.doc（21页珍藏版）》请在金锄头文库上搜索。
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 method sa
5、tisfies 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第五章 结束
6、语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规则 寻找一个，满足 ， ， (2)
8、 强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),步长由(2-1)、(2-2)求出，则有 证明: 由，知 ，k=1,2由(2-2)式及Lipschitz条件有， 所以 .
