无约束最优化问题研究毕业论文.doc 14页

'无约束最优化问题研究毕业论文目录第一章引言1第二章共轭梯度算法4第三章下降条件5第四章全局收敛性7第五章结束语9参考文献10致　谢12 红河学院本科毕业论文(设计)第一章引言本文主要考虑无约束最优化问题(1-1)其中为上的连续可微函数．共轭梯度算法是用来求解无约束优化问题(1-1)的一种方法，其迭代格式是(1-2)(1-3)其中，为搜索方向，，为的梯度，为某种参数．共轭梯度法最早是1952年由计算数学家Hestenes和几何学家Stiefel为求解线性方程组，时提出的．由于解线性方程组等价于求解极小化的正定二次函数，因此，他们提出的方法也可视为求二次函数极小值的共轭梯度法．1964年，Fletcher和Reeves将此方法推广到非线性优化，得到了求解一般函数极小值的共轭梯度算法．共轭梯度算法是最优化理论中最常用的方法之一，它具有算法简单，存储需求小等优点，十分适合大规模优化问题．石油勘探、大气模拟、航天航空等领域出现的特大规模的优化问题常常利用共轭梯度算法求解．符号说明：表示上的欧式范数，是f的梯度函数在点的值．是由算法产生的点列．若为当前的迭代点，则记为．非线性共轭梯度算法的基本步骤[4](1)给出初始值；(2)如果,则停;否则利用某种搜索方法求;令；(3)利用某种公式计算参数,,z转步(2)；可由精确线搜索求得．但在实际计算中精确线搜索要求准确度高，计算量较大，故实际计算中常常进行非精确线搜索．在应用中可由非精确线搜索求得：(1)弱Wolfe-powell规则寻找一个，满足，　　，，．3 红河学院本科毕业论文(设计)(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方法在3 红河学院本科毕业论文(设计)Wolfe线搜索时能够保证每个搜索方向都下降，但全局收敛性不好，Dai和Yuan在文献[5]中严格证明了采用强Wolfe线搜索的DY方法在每一步产生一个下降方向，并且证明了该方法的全局收敛性.文献[6]对共轭下降法的收敛性做了进一步的分析；文献[7-10]对共轭下降法的作了改进，得到了包含共轭下降法的一类无约束优化方法，并证明了全局收敛性；文献[11-20]对FR方法的作了改进，得到了一类新的共轭梯度法并证明了全局收敛性．鉴于上述文献及其他相关文献的思路，本文给出了一个新的：(1-6)其中．当．得到了新的共轭梯度法，并证明了其在适当条件下的全局收敛性．3第一章引言3 第二章共轭梯度算法第二章共轭梯度算法本文对目标函数作如下假设：(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]中非精确线搜索条件保证的存在性．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条件有，11 红河学院本科毕业论文(设计)所以.(3-2)其中由的收敛性及(3-2)式知，，结论成立.11 红河学院本科毕业论文(设计)第三章全局收敛性定理4.1假设成立的条件下，考虑共轭梯度法式(1-1)、(1-2)和(1-3)，如果步长满足条件(2-1)和(2-3)，参数取值满足，，，则算法产生的迭代点列或对某个有下式成立：．证明：用反证法，若定理不成立，即存在c>0，使,k=1,2．由　(4-1)将(4-1)式两边取模平方，得(4-2)又由(3-1)式得由(2-3)知,．所以．所以得．将代入(4-2)式得．两边同除以可得：　　11 红河学院本科毕业论文(设计)由上式递推可得　　即．与定理(3-2)矛盾，所以全局收敛性得证．11红河学院本科毕业论文(设计)11 红河学院本科毕业论文(设计)第五章结束语本文主要讨论了无约束优化问题的算法，给出了一个新的，即构造了一个新的共轭下降方向，从而得到一类新的共轭梯度算法，且该算法允许初始点任意，并且具有全局收敛性．共轭梯度算法是常用的求解无约束优化问题的有效方法，进一步对它深入研究能否得到更好的混合算法，这是值得研究的．由于时间和本人水平有限，本论文提出的算法没有给出具体的数值试验，这是进一步要做的工作．11 红河学院本科毕业论文(设计)参考文献[1]HestenesMR.Iterativemethodforsolvinglinearequations[J].JOTA,1973,11(4):323-334．[2]StiefelE.Ubereinigemethodenderrelaxationsrechnung[J].ZeitschriftfürAngewandteMathematikundPhysik,1952,1(3):1-33．[3]FletcherR,ReevesCM.Functionminimizationbyconjugategradients[J].ComputeJournal,1964,7(2):149-154．[4]HestenesMR.Itertivemethodforsolvinglinearequation,NANL　ReportNo53-9,NationalBureauofStandards,WashingtonD.C.1973，1:322-334．[5]DaiYH,YuanY.AnonlinearconjugategradientmethodwithastrongglobalconvergencepropertyJ.SIAMJournalonOptimization,1999，10(1):177-182．[6]FletcherR.Practicalmethodsofoptimization:vol.2:ConstrainedOptimization[M],NewYork:JohnWiley&Sons,1981．[7]DaiYH,YuanYX.Convergencepropertiesoftheconjugatedescentmethod[J]．　　　AdvancesinMathematics(InChinese),1996,25(6):552-562．　[8]徐泽水.Aclassofnewconjugategradientmethods[J].数学志,2002,5(1):27-30．[9]杜学武.一类新共轭下降算法的全局收敛性[J]．数学的实践与认识,2002,32(1):153-157．[10]焦宝聪,陈兰平.一类新共轭下降算法的全局收敛性[J]．数学的实践与认识,，1998,28(3):193-196．[11]杜学武,叶留青,徐成贤．包含共轭下降法的一类无约束优化方法的全局收敛性[J]．工程数学学报,2001,18(2):119-121．[12]柳娟,谢铁军,孙玉华.一类共轭梯度法的全局收敛性[J]．运筹与管理,2007,16(2):75-78．[13]范建芬,谢铁军,柳娟.一族新的共轭梯度法的全局收敛性[J]．运筹与管理,2007,16(2):65-68．[14]高丽,谢铁军.Wolfe线搜索下新的共轭梯度法的全局收敛性[J]．运筹与管理,2008,2(1):38-41．11 红河学院本科毕业论文(设计)[15]陈岩,陈忠.无约束优化问题的一种新共轭梯度法的全局收敛性[J]．自然科学报,2009,6(2):129-131．[16]袁亚湘,孙文瑜.最优化理论与方法[M].北京:科学出版社,2006．[17]Al-BaaliM.DescentpropertyandglobalconvergenceoftheFlecher-Reeves　methodwithinexactlinesearch[J].IMA,JournalofNumericalAnalysis,1985,　5(1):121-124．[18]YuG.H,zhaoY.L.andWeiZ.X.Adescentnonlinearconjugategradientformulas　forlarge-scaleunconstrainedoptimizationproblems[J].Apll.Mach.comput,2006,179:407-430．[19]YuG.H.,zhaoY.L.andWeiZ.X.Adescentnonlinearconjugatemethodforlarges--caleunconstrainedoptimization[J].J.Apll.Math.Comput,2007,187:636-643．[20]陈继红，焦宝聪.一种新的非线性共轭梯度算法的全局收敛性[J].首都师范大学学报(自然科学版),2006,27(3):1-4．11 红河学院本科毕业论文(设计)致　谢毕业论文暂告收尾,这也意味着我在红河学院四年的学习生活既将结束.回首既往，自己一生最宝贵的时光能于这样的校园之中,能在众多学富五车、才华横溢的老师们的熏陶下度过，实是荣幸之极.在这四年的时间里，我在学习上和思想上都受益非浅.这除了自身努力外，与各位老师、同学和朋友的关心、支持和鼓励是分不开的.这篇论文是在我的导师——曹香莲老师的悉心指导下完成的．从论文的选题到结构安排，从内容到文字润饰，都凝聚了他们大量的心血.在这篇论文的写作过程中，曹香莲老师不辞辛劳，多次与我就论文中许多核心问题作深入细致地探讨，给我提出切实可行的指导性建议，并细心全面地修改了我的论文．对此，我表示我最衷心的感谢．曹老师严谨的治学态度、丰富渊博的知识、敏锐的学术思维、精益求精的工作态度、积极进取的科研精神以及诲人不倦的师者风范是我毕生的学习楷模．曹老师的高深精湛的造诣与严谨求实的治学精神将永远激励着我．曹老师这种一丝不苟的负责精神，使我深受感动．更重要的是曹老师在指导我的论文的过程中，始终践行着“授人以鱼，不如授之以渔”的原则.他们常教导我要志存高远，严格遵守学术道德和学术规范，为以后的继续深造打好坚实的基础．在此，请允许我向尊敬曹老师表示真挚的谢意！感谢和我一起度过四年大学的朋友们，是你们在我失意时给我鼓励，在我失落时给我支持，感谢你和我一路走来，让我在人生这一驿站中倍感温暖！在论文的写作过程中，也得到了许多同学的宝贵建议，在此一并致以诚挚的谢意！最后，衷心感谢所有老师对我的栽培、支持和鼓励，感谢所有朋友的关心和帮助.向在百忙中抽出时间对此论文进行评审并提出宝贵意见的各位专家表示衷心地感谢！衷心祝愿母校云南红河学院的明天更加美好！11'