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

2015年度本科生毕业论文（设计）一类具有全局收敛性的共轭梯度法院 系: 数学学院专 业: 信息与计算科学年 级: 2011级学生姓名: 马冲学 号: 201101050107导师及职称: 曹香莲(讲师)2015年4月2015Annual GraduationThesis (Project)of theCollege UndergraduateAConjugate GradientMethodwith GlobalConvergenceDepartment: InstituteofmathematicsMajor: Information and Computing ScienceGrade: 2011Students Name:Ma ChongStudent No.: 201101050107Tutor: Cao Xianglian (Lectuter)April,2015毕业论文（设计）原创性声明本人所呈交的毕业论文（设计）是我在导师的指导下进行的研究工作及取得的研究成果，据我所知，除文中已经注明引用的内容外，本论文（设计）不包含其他个人已经发表或撰写过的研究成果。对本论文（设计）的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意。作者签名: 日期:毕业论文（设计）授权使用说明本论文（设计）作者完全了解红河学院有关保留、使用毕业论文（设计）的规定，学校有权保留论文（设计）并向相关部门送交论文（设计）的电子版和纸质版。有权将论文（设计）用于非赢利目的的少量复制并允许论文（设计）进入学校图书馆被查阅。学校可以公布论文（设计）的全部或部分内容。保密的论文（设计）在解密后适用本规定。作者签名: 指导教师签名:日期: 日期:马冲毕业论文（设计）答辩委员会(答辩小组)成员名单姓名 职称 单位 备注李 薇 副教授 数学学院 组长杨慧章 讲师 数学学院 组员曾 黎 讲师 数学学院 组员曹香莲 讲师 数学学院 组员红河学院本科毕业论文（设计）摘 要本文给出了一种新的求解非线性无约束问题的共轭梯度算法,并证明了该方法在弱Wolfe线搜索下具有下降性和全局收敛性.关键词:无约束最优化；共轭梯度法；Wolfe线搜索；全局收敛性红河学院本科毕业论文（设计）ABSTRACTThispaper presents anew conjugate gradient algorithm for solvingnonlinearunconstrained optimizationproblem,And theglobal convergence anddescentproperty ofthemethod are given under theweakWolfelinesearch .Key words:Unconstrained optimization；Conjugategradient method；Wolfelinesearch；Global convergence红河学院本科毕业论文（设计）目 录第一章绪论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 ( )f x ,其中 1: nf R R ,这个问题的求解是指,在nR 中找到一点 *x ,使得对于任意的 nx R 都有: *( ) ( )f x f x .常用的无约束最优化方法一般有最速下降法、Newton法、修正Newton法、共轭梯度法、变尺度法等,其中介绍两种本文中主要用到的算法:最速下降法和共轭梯度法.1.1.1最速下降法基本思想:从点1x 处出发,选择目标函数 ( )f x 的负梯度方向作为每一步的第一章 绪论2搜索方向,以便于尽快达到极小点.特点: kx 的负梯度方向,仅仅是在 kx 点的附近才具有使函数下降最快的性质,但是对于求最优解的整个过程来说就不是这样的.在一定的条件下,最速下降法是线性收敛的,收敛速度较慢.当初始点 1x 离最优点 *x 较远时,一般来说下降速度较快,效果也较好,在求最优解的前期,使用最速下降法是一种比较有效的方法.1.1.2共轭梯度法基本思想:它是一个比较典型的共轭方向法,它的每一个搜索方向都是相互共轭的,而这些搜索方向kd 仅仅是负梯度 kg 与上一次迭代的搜索反向 1kd 的组合,然后再沿着 kd 的方向进行最优化搜索.特点:从理论上讲,如果目标函数是正定二次函数,利用共轭梯度法求解最优解的过程中,在n步以内必可达到极小点 *x ,它具有二次终止性.但在实际的计算过程中,由于计算误差和其他因素的影响,从而导致了经过n步迭代没有得到更加接近精确结果的解,如果说目标函数没有进入到一个正定二次函数的区域,就要将搜索方向重新开始,即将 nx 作为新的初始点,用重新设置负梯度方向的措施来加速收敛.其中比较常用的共轭梯度法有FR法、PRP法、HS法、CD法、DY法等.1.2线搜索方法21.2.1精确线搜索精确线搜索就是要求步长 ka 满足: 0( ) min ( )k k k k kaf x a d f x ad ,由精确线搜索的条件可知,精确线搜索中确定的步长 ka 满足:( ) 0.Tk k kg x ad d 红河学院本科毕业论文（设计）31.2.2Armijo线搜索技术给定常数 0 , 1, (0,1), 求 max , 0,1,2, ,jka j 使它满足:1( ) ( ) 0Tk k k k k k kf x a d f x a g d .由于 kd 是f 在 kx 处的下降方向,且满足 0Tk kg d ,容易证明,不等式对充分小的正数 ka 均成立.1.2.3Wolfe-Powell线搜索技术给定1 , 2 满足 10 1/2 , 1 2 1 ,求 0ka ,使满足:1( ) ( ) Tk k k k k k kf x a d f x a g d ,2( )T Tk k k k k kg x a d d g d .第二章 问题的提出4第二章问题的提出本文主要考虑无约束优化问题:min ( ), ,nf x x R （2-1）其中 nR 是n维欧几里得空间, : nf R R 是一个连续可微函数.求解问题（2-1）常用的共轭梯度算法,由Fletcher和Reeves提出.共轭梯度法的一般迭代格式为: 1 , 0,1,2.k k k kx x d k (2-2)1, 1; , 1,kk k k kg kd g d k (2-3)其中 ( )k kg f x , kx 为当前迭代点, kg 为当前迭代点 kx 处的梯度, kd 为搜索方向, k 是通过一维线搜索获得的步长, k 为共轭参数.关于 k 的计算有着不同的共轭梯度算法,常见的 k 有以下这些形式3:221kFRk kgg , 121TPRP k kk kg yg , 11 1THS k kk Tk kg yd y ,11 1TLS k kk Tk kg yd g , 21 1kDYk k kgd y , 21 1kCDk k kgd g .其中向量的Euclidean范数用 表示, 1 1k k ky g g ,以上对应的方法分别叫做FR（Fletcher-Revees）方法、PRP（Polak-Ribiere-Polyak）方法、HS（Hestenes-Stiefel）方法、LS（Liu-Storey）方法、DY（Dai-Yuan）方法、CD(ConjugateDescent)方法.其中PRP法、HS法和LS法的数值计算结果比较好,而DY法和CD法的理论收敛性比较好.对Fletcher-Revees方法已经得出许多结果,比如Powell4证明了Fletcher-Revees方法在精确线搜索条件下具有全局收敛性,Al-Baali5证明了Fletcher-Revees方法在强Wolfe线搜索条件下具有全局收敛性,但是这两种证明方法得到的数值结果较差.虽然PRP方法有比较好的数值计算结果,但是它的局部收敛性较差.后来学者Wei Z.X., Li G.Y. 和 Qi L.Q6提出了一个新的参数 k 的取法:红河学院本科毕业论文（设计）521 22 1 3 1( ) kVFRk Tk k kgg d g . (2-4)再后来,G.Yu,Y.Zhao,Z.Wei7对此作了深入的研究,在文献6的基础上进行修改,得出了另一个更具有充分下降性和全局收敛性的 k ,即:2 21 121 1 ,( ) 0, Tk k k Tk k kN Tk k k kg g d g g dg d g , (2-5)其中 (1, ) ,以上两种方法的数值结果都比较好.本文结合（2-4）（2-5）得出一个新的参数k 的公式:2 1 1 1 1 11 1 1( ),0 1( )0, T Tk k k k k k kT Tk k k k k k kg g g g d g dg d g g g d , （2-6）其中定义 max 0,k k 来保证 k 的非负性.第三章 共轭梯度法的算法及其全局收敛性6第三章 共轭梯度法的算法及其全局收敛性3.1算法首先,为了证明的需要,对目标函数 ( )f x 作出以下的假设（H）8:（）目标函数 ( )f x 在水平集 1( ) ( )E x f x f x 上有界,其中 1x 为初始点；（）设N E ,目标函数 ( )f x 在N 内连续可微且导数函数g满足Lipschitz条件,即:存在常数 0L ,使得: ( ) ( ) ,g x g y L x y ,x y N .在构造共轭梯度法时,通常步长 k 满足所谓的Wolfe(SWP)条件:( ) ( )Tk k k k k k kf x f x a d a g d , (3-1)( )T Tk k k k k kg d g x a d d , (3-2)其中,0 1 .引入基于式（2-6）的共轭梯度算法如下:步骤1:给出 1 nx R , 0 ,令k:=1.步骤2:计算 kg ,若 kg ,立即停止计算,否则转入步骤3；步骤3:由弱Wolfe线搜索（3-1）（3-2）,求得 k ,计算 1k k k kx x d ,1 1( )k kg f x ,若 1kg ,迭代停止.步骤4:由 max 0,k k 计算 1 1 1 1 1, , : 1k k k k k kd g d k k ,转步骤3.3.2算法的下降性定理3.1 假设条件H成立,考虑公式（2-2）（2-3）中步长因子 k 由线搜索（3-1）（3-2）确定,参数 k满足(2-6)式,则 0Tk kg d .证明:当 1n 时, 02111 gdgT ；假设:当 1n k 时, 011 kTk dg 成立；当n k 时,由（2-3）式得:红河学院本科毕业论文（设计）72 1T Tk k k k k kg d g g d , 22 1 1 1 11 1( )( ) Tk k k k k Tk k kTk k k kg g g g dg g dg d g g , 22 1 111 1Tk kk k kk k k k kg dg g gg g g g g , 1 11Tk kk kg dg g , （3-3）0.由以上证明得,当k满足（2-6）时,有 0Tk kg d ,算法具有下降性.3.3算法的全局收敛性引理3.19 假设条件H成立,考虑公式（2-2）（2-3）中步长因子 k 由线搜索（3-1）（3-2）式确定,若 0kTk dg ,则:221 ( ) .Tk kk kg dd 定理3.2 假设条件H成立,考虑公式（2-2）和（2-3）中步长因子 k 由Wolfe线搜索（3-1）（3-2）式确定,参数 k 满足（2-6）,则算法或者终止于稳定点或者: liminf 0.kk g 证明:因为 2 1 1 11 1( )( ) Tk k k k kk Tk k k kg g g g dg d g g ,2 1 1 11 1 1 1( )( ) ( )Tk k k k kT Tk k k k k k k kg g g g dg d g g g d g g ,又因为第三章 共轭梯度法的算法及其全局收敛性81 110 1Tk kTk kg dg d , 1 0Tk kg d ,所以 2 11 1 0( )k k kTk k k kg g gg d g g ,所以 1 11 1( )( )Tk kk Tk k k kg dg d g g ,所以11k k kg g ,代入（3-3）式得: 1 1Tk kk Tk kg dg d . （3-4）利用反证法,假设定理不成立,则存在 0c 使得:kg c , 3,2,1k . (3-5)由（2-3）得: 1k k k kd g d , (3-6)取（3-6）两边模平方,并移项得:2 2 22 1( ) 2 Tk k k k k kd d g d g . (3-7)若 0k ,将（3-4）代入（3-7）式,两边同时除以 2k kg d 得: 2 2 212 2 21 1 2 ,k k kTT T Tk kk k k k k kd d gg dg d g d g d 221 2 21 1 1 1 ,k kTT k k k kk kd gg g d gg d 21 2 21 1 1kT kk kd gg d , (3-8)红河学院本科毕业论文（设计）9又因为 21 2 211 1 1Td gg d ,所以由（3-8）式递推可得: 2 2 21 1kkT i ik kd gg d , （3-9）结合（3-5）式与（3-9）式可得: 2 2 2kTk kd kcg d .从而: 1 2 2k k kTkddg ,这与引理3.1矛盾,所以定理成立.第四章 结论10第四章结论本文一共分为四个章节,前面的三个章节是对知识和算法的具体介绍,而第四章节则是对本文的一个总结.第一章,主要讲述的是最优化问题在生产生活中的运用及其发展,介绍了几种常用的无约束最优化方法,对最速下降法和共轭梯度法做了简单的分析.然后又介绍了精确线搜索、Armijo线搜索技术、Wolfe-Powell线搜索技术这三种线搜索方法.第二章,主要根据 k 的几种不同形式,在不同的学者对 k 改进的基础上,构造了一个新的 k .第三章,将新的 k 代入Wolfe线搜索条件下进行计算,通过证明得到算法具有下降性和全局收敛性.优缺点:本文通过参考各类文献和书籍后得出新的 k ,利用新的 k 可以有效的证明出最优化算法具有下降性和全局收敛性.但文中对于 k 的限制条件过多,对算法的证明有一定影响,数值实验结果不好.红河学院本科毕业论文（设计）11参考文献1郭科,陈聆,魏友华.最优化方法及其应用M.北京:高等教育出版社,2007:86-103.2梁玉梅,刘云.一类新共轭梯度法在几种非精确线搜索下的收敛性J.广西大学学报（自然科学版）,2001年,第26卷,(第2期).3洪玲,莫利柳.一个新的全局收敛的共轭梯度法J.运筹学学报,2009年,第13卷（第1期）.4 Powell M.J.D. Nonconvex minimization calculations and conjugate gradientmethodJ.Lecture Notes in Mathematics, 1984,1066:122-141.5 Al-Baali M.D escent property and global convergence of the Flecher-Reeves method with inexact line searchJ.IMA,Journal of Numerical Analysis, 1985,5(1):121-124.6 Wei Z.X. Li G.Y. and Qi L.Q. New nonlinear conjugate gradient formulasfor large-scale unconstrained optimization problems J. Apll. Match. Co