修正Broyden族拟牛顿算法及其应用

论文摘要

最优化问题及其理论和算法来源于经济，管理，工程等许多重要领域，同时和计算数学中的微分方程数值解法，非线性方程组数值解法等分支有着密切的联系和应用。传统的Broyden族拟牛顿算法因为其良好的数值效果和快速收敛速度已成为求解最优化问题颇受欢迎的一类算法，自上世纪60年代以来，传统的Broyden族拟牛顿算法的理论受到了广泛的重视并且已经取得了丰硕的成果。当目标函数是凸函数时，该类算法的局部收敛性和全局收敛性理论已得到很好的解决。 当目标函数是非凸函数时，Dai构造了一个反例说明了使用非精确搜索的BFGS算法对非凸函数不是全局收敛的，来自工程中的许多实际问题往往是是非凸的，研究求解非凸的优化问题的拟牛顿算法的全局收敛性具有现实的理论意义和实际意义。 本文首先研究求解非凸的无约束优化问题的修正BFGS算法以及Broyden族拟牛顿算法的全局收敛性及其超线性收敛性，在此基础上，我们研究求解非线性最小二乘问题的结构化拟牛顿法及其收敛性理论。最后，我们研究求解变分不等式问题的模单调下降的BFGS算法及其全局收敛性分析。 首先，在第二章到第四章，我们研究求解下面无约束优化问题的算法： min，f(x)，x∈R~n，其中f：R~n→R是一光滑函数。最近，Zhang，Deng和Chen以及Wei，Yu和Yuan等分别提出了满足新的拟牛顿方程的拟牛顿算法，希望提高传统拟牛顿算法的效率，他们对所提出的拟牛顿算法的局部收敛性进行了分析。但是，当目标函数f是非凸函数时，这些算法的全局收敛性尚不清楚。我们在Li和Fukushima全局化MBFGS和CBFGS算法的基础上，分别提出基于Zhang，Deng和Chen以及Wei，Yu和Yuan等的拟牛顿方程的修正的BFGS算法和保守修正的BFGS算法。在较弱的条件下，我们证明这两种方法用于求解非凸函数的无约束优化问题时，具有全局收敛性及其超线性收敛性。进而，在第四章，我们研究修正的Broyden族拟牛顿算法及其全局收敛性，我们证明无论是基于传统的拟牛顿方程还是Zhang，Deng和Chen以及Wei，Yu和Yuan等的拟牛顿方程的修正的Broyden族拟牛顿算法在适当的条件下，不但是局部超线性收敛的，而且具有全局收敛性。 求解非线性最小二乘问题的结构化拟牛顿法的全局收敛性问题是人们关注的研究难点课题，研究该问题的主要困难在于结构化拟牛顿法产生的矩阵不能保证对称正定性。本文第五章致力于该问题的研究，我们在对Yabe和Takahashi及Yabe和Yamaki提出的分解结构化拟牛顿算法进行仔细分析的基础上，结合第四章的思想，提出了一种满秩分解的结构化的Broyden族算法，该算法的特点是，无

论文目录

• 学位论文原创性声明和学位论文版权使用授权书
• 摘要
• Abstract
• 附表索引
• 基本符号和数值实验的说明
• 第1章 绪论
• 1.1 概述
• 1.1.1 求解无约束优化问题的拟牛顿算法
• 1.1.2 求解非线性最小二乘问题的拟牛顿算法
• 1.1.3 求解对称变分不等式KKT系统的模下降的BFGS算法
• 1.2 本文的工作和结构
• 第2章 无约束优化问题的修正BFGS算法及收敛性分析
• 2.1 引言
• 2.2 修正的BFGS算法（mBFGS）
• 2.3 收敛性分析
• 2.4 数值实验
• 第3章 无约束优化问题的保守修正的BFGS算法及全局收敛性
• 3.1 引言
• 3.2 保守修正的BFGS算法（cBFGS）
• 3.3 收敛性分析
• 3.4 数值实验
• 第4章 无约束优化问题的修正Brodyen族拟牛顿算法及收敛性分析
• 4.1 引言
• 4.2 修正的Broyden族拟牛顿算法1（mBroyden1）
• 4.3 收敛性分析
• 4.4 修正的Broyden族拟牛顿算法2（mBroyden2）
• 4.5 数值实验
• 第5章 非线性最小二乘问题的满秩分解的结构化Broyden族拟牛顿算法
• 5.1 引言
• 5.2 预备知识
• 5.3 满秩分解的结构化Broyden族算法与GN算法的杂交
• 5.4 杂交算法的收敛性分析
• 5.5 数值实验
• 第6章 非线性最小二乘问题的修正的分解形式的结构化BFGS算法
• 6.1 引言
• 6.2 分解形式的结构化BFGS算法的修正（m-sBFGS）
• 6.3 m-sBFGS算法的收敛性分析
• 第7章 求解对称变分不等式问题KKT系统的模下降BFGS算法
• 7.1 引言
• 7.2 模单调下降的BFGS算法
• 7.3 收敛性分析
• 7.4 数值实验
• 结论
• 参考文献
• 附录A 攻读博士学位期间完成和发表论文目录
• 致谢