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

摘要

最优化问题及其理论和算法来源于经济，管理，工程等许多重要领域，同时和计算数学中的微分方程数值解法，非线性方程组数值解法等分支有着密切的联系和应用.传统的Broyden族拟牛顿算法因为其良好的数值效果和快速收敛速度已成为求解最优化问题颇受欢迎的一类算法.自上世纪60年代以来，传统的Broyden族拟牛顿算法的理论受到了广泛的重视并且已经取得了丰硕的成果.当目标函数是凸函数时，该类算法的局部收敛性和全局收敛性理论已得到很好的解决. 当目标函数是非凸函数时，Dai构造了一个反例说明了使用非精确搜索的BFGS算法对非凸函数不是全局收敛的.来自工程中的许多实际问题往往是是非凸的.研究求解非凸的优化问题的拟牛顿算法的全局收敛性具有现实的理论意义和实际意义. 本文首先研究求解非凸的无约束优化问题的修正BFGS算法以及Broyden族拟牛顿算法的全局收敛性及其超线性收敛性.在此基础上，我们研究求解非线性最小二乘问题的结构化拟牛顿法及其收敛性理论.最后，我们研究求解变分不等式问题的模单调下降的BFGS算法及其全局收敛性分析. 首先，在第二章到第四章，我们研究求解下面无约束优化问题的算法：minf(x)，x∈Rn，其中f：Rn→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族算法.该算法的特点是，无论迭代点是否在解x*的附近，都能保证算法产生的迭代矩阵是正定的.我们证明，采用Wolfe线性搜索的这种结构化Broyden族拟牛顿法具有全局收敛性和超线性收敛性.此外，利用该算法与Gauss-Newton算法杂交使用，我们证明杂交算法对零残差问题是二次收敛的. 在第六章，通过QR正交分解，我们对Yabe和Takahashi的结构化分解形式的BFGS算法进行改进.改进后的分解形式的结构化BFGS算法总使得迭代矩阵是正定的.在适当的条件下，我们证明这种分解形式的结构化BFGS算法的局部超线性收敛性. 第七章，我们研究求解对称变分不等式的KKT系统的具有单调下降性的BFGS算法.我们首先将对称变分不等式的KKT系统转化为等价的非光滑方程组.然后考察用拟牛顿算法求解该非光滑方程组.我们对Li和Fukushima提出的非单调线性搜索加以改进，在此基础上构造一个使方程组模函数单调递减的BFGS算法，在适当的条件下我们建立算法的全局收敛性及其超线性收敛性定理.

目录

文摘

英文文摘

论文说明：附表索引、基本符号和数值实验的说明

湖南大学位论文原创性声明及学位论文版权使用授权书

第1章 绪论

第2章 无约束优化问题的修正BFGS算法及收敛性分析

第3章 无约束优化问题的保守修正的BFGS算法及全局收敛性

第4章 无约束优化问题的修正Brodyen族拟牛顿算法及收敛性分析

第5章 非线性最小二乘问题的满秩分解的结构化Broyden族拟牛顿算法

第6章 非线性最小二乘问题的修正的分解形式的结构化BFGS算法

第7章 求解对称变分不等式问题KKT系统的模下降BFGS算法

结论

参考文献

附录A 攻读博士学位期间完成和发表论文目录

致谢