大型稀疏极大极小问题的数值方法

论文摘要

本文研究求解大型稀疏极大极小问题的对称相容分组修正Newton型方法、不精确牛顿法和不精确对称相容分组修正Newton型方法.取得的主要结果可概括如下:1.在第2章,我们先从光滑问题入手,对大型稀疏光滑无约束优化问题的几种对称相容分组修正Newton型法和对称相容分组修正Cholesky因子算法作了一些改进,并给出不精确的分组修正Newton型方法,证明了它们的q-超线性收敛性和全局收敛性并给出r-敛速估计.2.在第3章,我们研究稀疏的极大极小问题的对称相容分组修正算法.由于极大极小问题涉及多个函数,每个函数的Hesse矩阵的稀疏结构不一定相同,每个函数需要采用不同的分组策略,因而有不同的换元周期,我们在不假设严格互补的条件下证明了分组修正算法的q-超线性收敛性和全局收敛性,并给出r-敛速估计.此外,还基于修改的Cholesky因子分解提出了非凸极大极小问题的有效算法.3.在第4章,我们研究求解极大极小问题的不精确Newton法.在求解极大极小问题的不精确Newton法中,每步迭代需要近似求解一个二次极大极小问题,而求解二次极大极小问题则需要近似求解一系列特殊的线性方程组.我们给出二次极大极小子问题和线性方程组求解精度的控制准则,在保持Newton法的超线性收敛性的前提下尽可能减少子问题求解的计算量.在不假设严格互补的条件下,证明了算法的局部超线性收敛性和全局收敛性,并给出q-收敛阶.4.在第5章,我们给出求解大型稀疏的极大极小问题的不精确对称相容分组修正算法.我们给出二次极大极小子问题和线性方程组求解精度的控制准则,在保持分组修正算法的超线性收敛性的前提下尽可能减少子问题求解的计算量.在不假设严格互补的条件下,证明了算法的局部超线性收敛性和全局收敛性,并给出其收敛阶.对所给出的算法,都用C/C++或Matlab语言编程实现,并通过数值实验与已有的算法进行了比较.数值结果表明这些方法是有效的.

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 大型稀疏极大极小问题
• 1.2 预备知识和记号说明
• 1.3 本文的主要工作
• 2 大型稀疏光滑无约束优化问题的几种算法
• 2.1 大型稀疏光滑无约束优化的对称相容分组修正Cholesky因子算法
• 2.1.1 对称相容分组修正Cholesky因子算法
• 2.1.2 算法的收敛性质
• 2.1.3 数值结果
• 2.1.4 结论
• 2.2 对称相容分组修正算法
• 2.2.1 对称相容分组修正算法及其性质
• 2.2.2 局部收敛性质
• 2.2.3 正定化对称相容分组修正Cholesky因子算法
• 2.2.4 数值结果
• 2.2.5 结论
• 2.3 不精确对称相容分组修正算法
• 2.3.1 局部算法及其收敛性质
• 2.3.2 全局算法及其收敛性质
• 2.3.3 数值结果
• 2.3.4 结论
• 2.4 本章小结
• 3 大型稀疏极大极小问题的对称相容分组修正算法
• 3.1 局部对称相容分组修正算法及其一些性质
• 3.2 算法的局部收敛性质
• 3.3 全局对称相容分组修正算法及其收敛性质
• 3.4 非凸情形
• 3.5 数值结果
• 3.6 本章小结
• 4 极大极小问题的不精确Newton算法
• 4.1 局部不精确算法及其收敛性质
• 4.2 全局不精确算法及其收敛性质
• 4.3 SQP方法近似求解对偶问题
• 4.4 数值结果
• 4.5 本章小结
• 5 大型稀疏极大极小问题的不精确对称相容分组修正算法
• 5.1 局部不精确对称相容分组修正算法及其收敛性质
• 5.2 全局不精确对称相容分组修正算法及其收敛性质
• 5.3 数值结果
• 5.4 本章小结
• 6 结论与展望
• 6.1 结论
• 6.2 今后研究工作展望
• 参考文献
• 读博期间发表、完成论文情况
• 创新点摘要
• 致谢