非线性共轭梯度法的全局收敛性研究

非线性共轭梯度法的全局收敛性研究

周雪琴[1]2016年在《几个修正的非线性共轭梯度法及其全局收敛性研究》文中进行了进一步梳理本文主要论述几个修正的非线性共轭梯度法在某些已成熟的线搜索条件下的下降性质和全局收敛性。非线性共轭梯度法隶属于优化方法的一种,随着最优化理论在生产、经济、交通等方面的应用变得广泛,尤其是对于较为复杂的大规模问题,共轭梯度法具有思想简单,易于编程且计算时所占的存储空间小等优势,这使得共轭梯度法在实际应用中被频繁使用,为本文的研究提供了实践价值。本文的主要工作:一是介绍共轭梯度法的相关预备知识,还涉及算法在运行过程中要用到的一系列搜索条件和算法的下降性质以及收敛性研究,二是提出几个修正的非线性共轭梯度法,并证明这些算法在相应的线搜索条件下的下降性质和收敛性。本文的内容分布如下:第一章,阐述本文的研究背景和现状,介绍共轭梯度法的相关基础知识。第二章,提出两个修正的共轭梯度法,并证明这两个修正的共轭梯度法公式在强Wolfe线搜索下都是全局收敛的。一个是对PRP方法进行修正,得到不依赖线搜索且具有充分下降性的新的共轭梯度法。另一个则是对HS共轭梯度法进行适当的修正,得到一个新的HS共轭梯度法,证明它具有不依赖线搜索的充分下降性。第叁章,提出两个修正的DY共轭梯度法,并证明这两个修正的共轭梯度法公式在Wolfe线搜索下都是全局收敛的,其中一个在Wolfe线搜索下是下降的,另一个在不依赖于任何线搜索下充分下降。第四章,在戴志峰提出的修正共轭梯度法—DPRP方法的基础上,证明其在广义Wolfe线搜索条件下全局收敛。第五章,对本文做出简单的总结与展望,概述本文提出的几个非线性共轭梯度法在相应的线搜索条件下的全局收敛性,这为算法进一步的数值研究和计算奠定了坚实的理论基础。

张雁[2]2012年在《混合非线性共轭梯度法及其全局收敛性的研究》文中研究指明非线性共轭梯度法是求解一些大规模非线性无约束优化问题的基本迭代方法,具有算法简单、存储空间需求小的特点。在经典的非线性共轭梯度法中,不同的方法其收敛性和数值表现各不相同。近年来,各种混合共轭梯度法被广泛研究,寻求同时具有良好的收敛性和数值表现的共轭梯度法成为该方向研究的一个重点。论文主要对混合非线性共轭梯度法进行深入的研究,提出了一些新的算法,并讨论其收敛性。首先,研究了非线性共轭梯度法的产生、发展和特点,给出了这种方法的一些重要形式及其产生的背景。其次,论文基于修正的HS方法提高算法效率和PC方法保证算法全局收敛性的思想,构建了一类混合的修正HS-PC共轭梯度法—MHP法,该算法不需要给定下降条件,并且相应算法在Wolfe线搜索下具有全局收敛性,数值试验表明算法是有效的。再次,针对算法的优劣主要依赖于步长因子和搜索方向的特点,结合共轭梯度法的共轭性质,在保证目标函数充分下降的条件下,论文构造出一种新的线搜索,并结合参数公式,构建出一类混合共轭梯度法—NHGP法,在充分下降条件满足的情况下,给出了算法的全局收敛性证明。数值试验表明算法可行且有效。最后,CD方法在使用强Wolfe线搜索时虽然能够保证每个搜索方向下降,但全局收敛性不好。论文结合CD方法和LS方法,构建出一类新的非线性共轭梯度法—NCDLS法,该方法不但具有下降性,而且在推广的Wolfe线搜索下是全局收敛的,数值验证该方法可行且有效。

苏文芳[3]2009年在《无约束最优化问题的非线性共轭梯度算法的研究》文中提出共轭梯度法在最优化计算方法中是一种比较重要的方法,自从20世纪60年代它被提出以后发展至今已有四十多年的历史了,先后有许多国内外的学者对其做了大量研究,使其一时成为学术界研究的热点。近年来,由于实际问题中越来越多大规模优化问题的涌现,以及计算机科学技术的飞速发展,在许多应用领域如电力分配、石油勘探、经济管理和天气预测等提出来的无约束优化问题规模往往很大,共轭梯度法恰恰能够解决此类大规模问题。因此,共轭梯度法又一次成为学术界学者们关注的热点。论文构建了一种修正的LS共轭梯度算法,一种混合的共轭梯度法,将共轭梯度法应用于金融时间序列的建模中。首先介绍了五大经典的共轭梯度算法,它们分别是:FR法,PRP法,HS法,CD下降法以及DY方法,而且对它们的全局收敛性以及下降性条件给出了相应的结论。接着给出了一些关于异方差时间序列的基本知识。其次给出了Beale叁项共轭梯度算法,构建了一种修正的LS共轭梯度算法,而且对这两种方法的下降性和收敛性给出了证明。最后用数值试验检验了其算法的优良性。再次构建了一种混合的共轭梯度算法—NLSDY算法。新算法有机地结合了LS算法与DY算法的优点,并采用强Wolfe搜索证明了新算法的全局收敛性,数值算例亦表明新算法具有良好的计算效能。最后做了基于共轭梯度法的误差最小的异方差时间序列模型,利用统计分析软件SAS解决了经济非平稳时间序列的模型拟合。对澳大利亚储备银行2年期有价证券月度利率数据进行建模,最终拟合效果图显示模型拟合很成功。

张丽[4]2006年在《求解最优化问题的非线性共轭梯度法》文中认为本文研究求解无约束优化问题和带简单有界约束优化问题的非线性共轭梯度法,并讨论这些方法的全局收敛性和数值表现。 我们首先在第1章简单的介绍本文将要研究的问题的背景和已有结果,在第2-4章提出几种修正的非线性共轭梯度法,分别称为MFR方法,MPRP方法和MHS方法。这几种修正方法的一个最重要的特征是能产生充分下降方向,即搜索方向d_k满足d_k~Tg_k=-‖g_k‖~2。这种性质不依赖方法所采用的线性搜索,这也是本文提出的算法与已有的非线性共轭梯度法的主要区别之一。此外,当采取精确线性搜索时,MFR方法,MPRP方法和MHS方法分别退化为标准的FR方法,PRP方法和HS方法。因此,当目标函数是严格凸的二次函数,且采用精确线性搜索时,这些修正的共轭梯度法具有共轭性和二次终止性。 在一定条件下,我们证明采用标准Armijo线性搜索和Wolfe线性搜索的MFR方法求解非凸极小化问题的全局收敛性.我们在第3章还提出一种修正的Armijo线性搜索并证明MPRP方法在该修正的Armijo线性搜索下求解非凸极小化问题的全局收敛性。 注意到对于共轭梯度法,初始步长的选取对算法的数值效果有较大影响,我们在第3章提出一种自调比的初始步长策略,数值结果表明在大多数情况下,本文提出的初始步长选取策略是可接受的,从而减少了函数值的计算次数,提高了算法的有效性。 为了证明MHS方法的全局收敛性,我们对MHS方法又提出两种修正形式,称为MMHS方法和CMHS方法,这两种修正方法仍然保持g_k~Td_k=-‖g_k‖~2的性质,在适当的假设条件下,我们证明MMHS方法和CMHS方法在标准Armijo线性搜索和Wolfe线性搜索下用于求解非凸极小化问题时也具有全局收敛性。更为重要的是,我们测试了CUTE函数库中大量的无约束优化问题,数值结果表明,本文的算法非常成功,特别是MPRP,MMHS和CMHS方法基本上可与CG_DESCENT方法相媲美。 本文第5章,我们在DY算法中引入一种控制准则,利用此准则提出一种最速下降-DY型混合算法,该算法也能产生下降方向,在一定条件下,我们证明采取标准Armijo线性搜索的这种混合算法求解非凸无约束优化问题的全局收敛性。 我们在第6-7章分别提出一种非单调的共轭梯度法和固定步长策略下的共轭梯度法,并证明MFR,MPRP,MMHS,CMHS方法在非单调的Armijo型线性搜索和取固定步长策略下求解非凸目标函数时的全局收敛性。此外,我们在第6章还提出一种杂交的PS方法并证明该方法求解非凸问题的全局收敛性。 最后在第8章,我们提出一种求解简单有界约束优化问题的非线性共轭梯度法,该方法能产生可行下降方向,在适当的条件下,我们建立该方法的全局收敛性

李素文[5]2008年在《非线性共轭梯度法的研究》文中指出共轭梯度法是求解无约束优化的一类有效的方法。它具有算法简便,存储需求小等优点,适合于求解大规模优化问题。经典的非线性共轭梯度法有:FR、PRP、CD、HS等。近几年,韦增欣、张建中、Hiroshi Yabe等学者利用Dai和Liao的新的拟牛顿条件(正割条件),产生了许多新的算法,新算法既有梯度信息,又有函数值信息,且数值表现比以往的算法好。本文提出了两类共轭梯度法,第一类在Hiroshi Yabe和Masahiro Takano的共轭梯度法的基础上,就μ_(k-1)(由于μ_(k-1)=s_(k-1)或μ_(k-1)=y_(k-1)的良好的数值表现)的选择,分别用s_(k-1)和y_(k-1)的算术平均值和凸组合来修正,以及对θ_k的系数进行修正,从而得到叁种新的非线性共轭梯度法,从而扩大了β_k的范围。然后证明叁种新算法在强Wolfe线搜索下的全局收敛性,数值验证表明这类共轭梯度法是比较有效的。CD方法在使用强Wolfe线搜索时虽然能够保证每个搜索方向下降,但全局收敛性质不好。第二类算法是结合CD法和Liu.Y,Storey.C提出的新共轭梯度法(简记LS法),提出一类新的非线性共轭梯度法,新方法不但具有下降性质,而且在推广的Wolfe线搜索下是全局收敛的,最后进行了数值验证。

刘金魁[6]2009年在《几类非线性共轭梯度法的全局收敛性研究》文中进行了进一步梳理最优化是一门应用广泛、发展迅速的学科。它研究某些数学上定义的问题的最优解,即对于给出的实际问题,诸如石油勘探、大气模拟、航天航空等领域出现的特大规模的问题,从众多的方案中选出最优方案。共轭方向法是无约束最优化中一种常用方法,是介于最速下降法与Newton法之间的一个有效方法。它仅需要利用一阶导数信息,既克服了最速下降法收敛慢的缺点,又避免了存储和计算Newton法所需要的二阶导数信息。共轭方向法是从研究二次函数的极小化产生的,但是它可以推广到处理非二次函数的极小化问题。本文研究的共轭梯度法是最常用的共轭方向法之一。它在自然科学、社会科学、生产实际、工程设计及现代化管理中有着重要的实用价值。本文对近年来备受关注的非线性共轭梯度算法进行了探索,主要结果有:①在PRP、LS方法的基础上给出了两种非线性共轭梯度法,无需任何线搜索,即可得到方法的充分下降性,并在Wolfe线搜索下具有全局收敛性。②结合CD方法与DY方法的优点提出了一种杂交的非线性共轭梯度法,并在Wolfe线搜索下分析了新方法的下降性和全局收敛性。③在HS方法的基础上给出了一种新的非线性共轭梯度法,此方法在强Wolfe线搜索下具有充分下降性和全局收敛性。④给出一种新的非线性线搜索条件,并在这种线搜索条件下得到了PLS方法的全局收敛性。

陈禹[7]2012年在《共轭梯度法的收敛性研究》文中研究表明最优化方法是运筹学的一个重要组成部分,在自然科学、社会科学、生产实际、工程设计和现代化管理中具有广泛的应用.很多实际问题都可以归结为最优化的问题来解决,最优化问题的一个核心是设计有效的算法.最优化问题根据函数的具体性质和复杂程度,可以分为很多不同的类型。根据决策变量的取值是离散的还是连续的可以分为离散最优化和连续最优化。根据模型所有函数是否连续可微,可以分为光滑最优化和非光滑最优化。根据所有函数的变量是否为线性函数可分为线性最优化和非线性最优化。无约束优化问题是最优化问题的基础,通常采用迭代法求它的最优解.求解无约束优化问题的常用算法包括最速下降法、牛顿法、拟牛顿法、共轭梯度法等.最速下降法具有存储量小,结构简单,易于实现的优点,具有良好的全局收敛性,但最速下降法收敛速度很慢,理论上只具有线性的局部收敛速度.牛顿法因其局部收敛速度快等优点而受到广泛关注,并且它具有二阶收敛速度,这使得该算法应用很广泛.然而,牛顿法需要计算目标函数的二阶导数矩阵,当Hesse矩阵▽f2(xk)奇异时,牛顿方向可能不存在,或者存在但不是f(x)在xk处的下降方向.拟牛顿法克服了牛顿法的这一缺陷,它只需计算目标函数的一阶导数,而且大多数拟牛顿法是下降算法,具有良好的全局收敛性和超线性收敛速度.由于拟牛顿法的这一优点,使得该算法成为颇受欢迎的算法.但拟牛顿法在每次迭代过程中都需要存储一个矩阵,而且确定下降方向需要求解一个线性方程组,并且该方程组的系数矩阵一般是稠密的,所以该类算法不适合求解大规模问题.共轭梯度法很好的解决了最速下降法和牛顿法的缺点,它只需要利用一阶导数的信息,就可以避免牛顿法要计算Hesse矩阵并求逆的繁琐,也解决了最速下降法下降速度慢的缺陷,因此,这是一种很受广大研究者欢迎的方法,也是求解大型最优化问题最有效的问题之一。共轭梯度法最早是由Hestenes(?)口Stiefel于1952年在求解线性方程组时提出的,并由Fletcher和Reeves于1964年推广到非线性优化领域.随后,Beale, Powell, Fletcher等着名的优化专家对非线性共轭梯度法进行了深入研究,取得了十分丰富的成果.但几乎同时问世的拟牛顿方法由于其良好的计算表现以及快速的收敛性质很快受到了人们的青睐,从而在很长一段时间里共轭梯度法被研究者所忽视.近年来,随着计算机的飞速发展以及实际问题的需要,大规模优化问题越来越受到重视,而共轭梯度法正是求解大规模问题的一种主要方法.于是,共轭梯度法的理论研究又受到人们的关注.近年来,Nocedal、Gilbert、 Nazareth、storey、A-Baali、Dai、Yuan、Wang和Wei等中外学者对共轭梯度法继续不断地深入研究,在收敛性方面得到了不少新结果,使得共轭梯度法在理论和应用上的发展日趋进步。但由于各种决定步长因子大小的线搜索和搜索方向的不同组合,使得共轭梯度法仍然是一个非常值得研究的方向。在实际问题中,非线性共轭梯度法无论在科学、工程、经济和管理系统中,还是在政府决策、生产管理、交通运输和军事国防等方面都得到了广泛的应用.本文在共轭梯度法已有成果的基础上,对共轭梯度法进行了一些探讨,提出了几种新的共轭梯度法,并获得了一些收敛性结果.其主要内容如下:第一章介绍了无约束最优化问题的相关概念,以及几种常见的求解无约束最优化问题的方法,并介绍了本文的主要工作.第二章对近年来国内外备受关注的非线性共轭梯度算法研究的现状进行了总结和归纳.第叁章在根据文献中βk得出一个新的βk的取值方法,结合文献中张秀军给出的一种新的线搜索构成一种新的方法,并给出充分下降性和收敛性的证明.第四章给出了一类求解无约束优化问题的共轭梯度法,在文献中提出的新的线搜索下给出了新算法的充分下降性和全局收敛性证明;本章第二节给出新的共轭梯度法充分下降性的证明,对共轭梯度法来说充分下降性是一个非常重要的性质,它对于保证算法的全局收敛性有很好的作用;第叁节给出了这类新的共轭梯度法的全局收敛性证明.第五章根据文献得到一个新的βk的取值,并和文献中的一种新的线搜索方法结合成一种新的混合算法,并给出充分下降性和收敛性的证明.

张秀军, 徐安农[8]2005年在《一种新的非线性共轭梯度法的全局收敛性》文中研究指明基于标准W olfe线搜索条件,提出一种新的线搜索:kα满足f(xk+kαdk)-f(xk)≤m ax{δkαgkTdk,-γ2kαdk 2}和g(xk+kαdk)Tdk≥m ax{σgTkdk,-2σkαdk 2},并在此基础上给出了一种新的非线性共轭梯度算法及其全局收敛性定理.

崔少勇[9]2008年在《求解无约束与简单界约束优化问题的非线性共轭梯度法》文中提出本论文研究求解无约束优化问题和简单界约束优化问题的非线性共轭梯度法,主要讨论这些方法的全局收敛性和数值表现.第二章,我们提出一个改进的共轭梯度算法,此算法是对Ls共轭梯度法的一种改进.在适当的假设条件下,我们将非单调技术应用到所提算法中,并证明了所提算法在非单调线搜索下的全局收敛性.第叁章,我们将非线性共轭梯度方法应用到求解简单界约束优化问题中,并证明了所提算法的全局收敛性.并对所提算法做了数值试验,结果表明我们的算法是适定的.

董晓亮[10]2015年在《自适应共轭梯度法的研究》文中认为无约束优化问题广泛应用于经济计划、工程设计、生产管理、国防与航空航天等重要领域,因此构造大规模优化问题的计算方法,研究这些方法的理论性质及其实际数值表现具有重要的理论意义和实际应用价值.存储量小和迭代简单的特点使共轭梯度法在求解大规模问题的算法中脱颖而出.在过去的20年中,充分下降条件和共轭性使得共轭梯度法在优化领域更为活跃.本文在总结己有非线性共轭梯度算法的基础上,从实用角度出发,设计出若干能满足上述两个条件的白适应共轭梯度法.主要具体工作如下:1.我们引入了两类白适应的共轭梯度法,该法在每步迭代可满足充分下降条件.与现有方法不同的是,本文提出新的共轭条件是动态调整的,它可视作HS共轭性和DL共轭性的继承与发展.在适当情况下,可证明该法对一般函数全局收敛.2.我们对六类基本共轭梯度法进行了修正,其中的搜索方向满足不依赖于任何搜索条件的充分下降条件.此外,我们提出了一个一般形式的共轭梯度法,对应的搜索方向总是充分下降方向.该方法无须Yuan提出的”步长要有正的下界”的假设条件,可以建立算法的全局收敛性.3.我们构造了一个非一致凸的二维函数,它可以说明这样一种可能性,即无论TTCG方法在极小化我们提出的函数时是否收敛,TTCG方法的收敛性分析中关于‘sTKyK>τ(τ>0是常数)”这一充分条件都不成立.主要原因在于在数量上,sTkyk是恢||2的高阶无穷小.此外,我们提出了一类具有一般形式的叁项共轭梯度法,它的搜索方向同时满足白适应共轭条件和充分下降条件.4.原TTDES方法中的某些结果因为参数选取不当需要修正,我们在迭代矩阵条件数最小的意义下找至TTDES方法的最优参数.具体地,既然该迭代矩阵既非对称也不正则,在讨论条件数时,一种谨慎而合理的策略是采取奇异值分析而非特征值分析.5.我们通过不同搜索方向之间的仿射组合而得到新的Hestenes-Stiefel类型不Polak-Ribiere-Polyak类型的叁项共轭梯度法.在迭代过程中,搜索方向满足充分下降条件,并能接近拟牛顿方向或满足共轭条件.算法在Wolfe搜索下收敛.6.数值结果显示,本文提出的上述方法适于求解大型优化问题,从而是有效的.白适应的算法机制不仅有益于共轭梯度法的理论与计算,随着时间的推移,它将展示出更有意义的重要性.

参考文献:

[1]. 几个修正的非线性共轭梯度法及其全局收敛性研究[D]. 周雪琴. 贵州师范大学. 2016

[2]. 混合非线性共轭梯度法及其全局收敛性的研究[D]. 张雁. 燕山大学. 2012

[3]. 无约束最优化问题的非线性共轭梯度算法的研究[D]. 苏文芳. 燕山大学. 2009

[4]. 求解最优化问题的非线性共轭梯度法[D]. 张丽. 湖南大学. 2006

[5]. 非线性共轭梯度法的研究[D]. 李素文. 南京理工大学. 2008

[6]. 几类非线性共轭梯度法的全局收敛性研究[D]. 刘金魁. 重庆大学. 2009

[7]. 共轭梯度法的收敛性研究[D]. 陈禹. 长江大学. 2012

[8]. 一种新的非线性共轭梯度法的全局收敛性[J]. 张秀军, 徐安农. 广西科学. 2005

[9]. 求解无约束与简单界约束优化问题的非线性共轭梯度法[D]. 崔少勇. 河南大学. 2008

[10]. 自适应共轭梯度法的研究[D]. 董晓亮. 西安电子科技大学. 2015

标签:;  ;  ;  ;  ;  ;  ;  

非线性共轭梯度法的全局收敛性研究
下载Doc文档

猜你喜欢