两类大规模矩阵优化问题的算法研究与软件设计

凸半定规划和核范数矩阵优化问题是两类重要的矩阵优化问题，在结构优化，最优控制，组合优化，应用统计，金融管理等领域，许多问题的模型都是半定规划或核范数矩阵优化模型。实际中有重大价值的两类问题往往是大规模的，因此系统研究这两类大规模凸矩阵优化问题的算法理论和软件设计有着重大的意义。本项目以凸规划的基础理论和算法为基础，研究大规模凸半定规划问题的迫近点-加速迫近梯度方法和加速迫近梯度-(半) 光滑Newton方法，大规模核范数优化问题的迫近点-加速迫近梯度方法，迫近点-(半) 光滑Newton方法和加速迫近梯度-(半) 光滑Newton方法，并研制上述算法的matlab软件。算法的理论分析以半光滑理论以及相关的变分分析为基础，算法的数值实现充分利用矩阵的特征值和奇异值理论。本项目旨在获得两类大规模问题的有效算法及数值软件，推动大规模矩阵优化特别是非对称矩阵优化理论和算法的进一步研究。

非对称矩阵优化问题是一类重要的矩阵优化问题，在结构优化，最优控制，数值代数，应用统计，压缩感知等领域，许多问题的模型都是非对称矩阵优化的模型。本项目以凸规划的基础理论和算法为基础，研究了大规模凸非对称矩阵优化的有效算法，并研制了相应的Matlab程序，其代表性结果可归纳如下：.1. 针对大规模矩阵核范数优化问题，研究了求解该问题的可实现的迫(邻)近点算法框架，该算法框架包含了原始、对偶以及原始-对偶三种不同形式的迫近点算法。基于算法编制的软件包PPApack能够处理矩阵规模达到10万维的大规模(低秩)矩阵核范数优化问题。这一结果发表在国际顶级优化期刊Mathematical Programming, Series A，受到国际国内同行广泛关注，论文已被他引62次。.2. 针对带线性等式和线性不等式约束的矩阵谱范数逼近问题(核范数优化问题的对偶问题)，提出了非精确半光滑牛顿-共轭梯度对偶迫近点方法。研究了矩阵核范数单位球投影算子B-微分的具体计算公式，并证明了：当对偶邻近点算法子问题的原约束非退化条件成立时，用于求解子问题的半光滑牛顿方法至少具有局部超线性收敛率。通过Matlab语言有效实现，对于超过500维的大规模问题，我们的算法是第一个具有高精度、稳定、高效特性的算法。.3. 基于参数方法，研究了求解一闭半空间与可变盒子交投影算子显示解的强多项式算法，并分析了算法至多进行O(mlog(m))步可得到投影算子的显示解，其中m为向量的维数。通过对算法的Matlab有效实现，得到了相应的数值结果，数值结果表明，对于向量规模达到100万维的问题，只需要大约18秒就能得到其投影算子的显示表达式。. 项目研究成果以论文的形式提供，共完成10余篇论文，其中8篇正式发表。本项目取得的大规模矩阵优化问题的有效算法及数值软件的成果，可推动大规模矩阵优化在相关领域的应用。