基于子空间技术的（无）约束优化问题的不精确（高斯-）牛顿法的理论与应用

发布时间：2018-03-23 08:36

本文选题：优化问题　切入点：不精确牛顿法　出处：《上海师范大学》2016年博士论文　论文类型：学位论文

【摘要】：最优化理论与方法被广泛运用于科学,工程,经济学,管理学等许多领域。它使用数学方法来研究各种系统的优化方案及途经,以研究人类对各种资源的筹划活动为核心,以期通过了解和发展这种活动的基本规律,发挥出有限资源的最大效益,达到整体最优的目标,从而为决策者提供进行科学决策的依据。随着高性能计算机的飞速发展和计算方法的进步,越来越多的大规模优化问题可以被研究和解决。无导数优化是一个有着悠久历史和当前快速发展的领域。Powell提出的基于近似二次模型的无约束优化方法(UOBYQA:Unconstrained Optimization BY Quadratic Approximation)[65],其构建了基于拉格朗日函数的目标函数的插值二次模型并且该模型的参数在一个插值点变化时被更新。Wild与Shoemaker[79]将Conn,Scheinberg与Vicente[29]的工作扩展到了线性化模型,其包括一个非线性项且分析了基于径向基函数插值模型的无导数信赖域算法的整体收敛性。为了减少牛顿法的计算工作量,Dembo,Eisenstat与Steihaug在文献[32]中推广了牛顿法提出了不精确牛顿法。不精确牛顿法在每次迭代时,只需要通过一个高效的迭代求解线性方程组系统的方法来近似求解牛顿方程,如经典的拆分方法或现代的Krylov子空间方法,通过选择合适的停止标准,就可以减少整个迭代的总计算量。随着Krylov子空间投影方法的发展,一些整体收敛的改进的不精确牛顿法一直被认为增强了从任意初始点的收敛性。本文提供了一类基于子空间技术的不精确(高斯-)牛顿法并运用无导数技术来求解(无)约束优化问题。我们关心的是通过广义最小残差(GMRES)[75],Lanczos[51]和共轭梯度(CG)等算法,将Krylov子空间方法用作内层迭代来近似求解(高斯-)牛顿方程,并构造具有整体收敛性的不精确牛顿法,这类方法是不使用回溯线搜索技术的Newton-Krylov方法求解非线性方程组或优化问题的扩展。所提出的方法的整体收敛依赖于Krylov子空间迭代的性质和搜索方向的接受规则,Krylov子空间迭代保证了目标函数所对应的(高斯-)牛顿方程的残差范数在每次迭代时是非增的,且对于每一个由Krylov子空间迭代产生的搜索方向满足文献[35]的局部收敛的条件。同时,结合搜索方向的接受规则和预计下降量满足充分下降条件来获得每次迭代时目标函数的范数的实际下降量的一个充分下降,从而,得到了等价于文献[35]的整体收敛的条件。针对(无)约束优化问题,在结合GMRES,Lanczos,CG等Krylov子空间方法,大大加快了作为内层迭代求解(高斯-)牛顿方程的速度,由此提出了结合插值多项式,有限差分,非单调技术等的不精确(高斯-)牛顿法求解(无)约束优化问题的各种算法的总体框架。其通过对相关残差的控制以及合适的搜索方向的接受规则,保证了所提出的算法在通常的假设条件下具有了整体收敛性,为求解(无)约束优化问题提供了一类有效的方法。此外,我们指出,所提出的方法与高效的无矩阵执行是一致的。本文共分为八章,第一章介绍了最优化理论与方法的相关知识。第二章到第六章,针对无约束的非线性方程组和优化问题,提出了一类基于子空间和无导数技术的不精确(高斯-)牛顿法,这类方法的整体收敛性并不依赖传统的回溯线搜索技术或信赖域方法,而是通过诸如GMRES,Lanczos,CG等Krylov子空间迭代算法的性质并结合适当的搜索方向的接受规则来获得。第七章,提出了求解线性等式约束无导数优化问题的一个无线搜索技术限制预处理共轭梯度路径法,该方法源自经典的共轭梯度法及其限制预处理的变化。在合理的假设条件下,证明了算法的整体收敛性和局部超线性收敛速率,数值结果表明算法的有效性和可行性。最后,对本文的研究进行了总结,并进一步提出了需要改进的方面。
[Abstract]:......
【学位授予单位】：上海师范大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O224

【参考文献】