凸可分半定规划的数值算法

Separable convex semidefinite programming is a class of mathematical problem with broad applications in finance, engineering et al.. The applications of convex nonlinear semidefinite programming and large-scale matrix optimization can also be considered in this framework. This model provides new ideas for further researches of these practical problems. This project is to analyze the theoretical properties of various matrix-valued functions and explore numerical methods for solving separable convex semidefinite programming problems. Firstly by using the tool of optimization, we transform original problem equivalently to variational inequalities on matrix space. Then alternating direction method, a popular first order method, can be extended to solve separable convex semidefinite programming problems. However, because of special properties of matrix conic optimization, we must modify original algorithm to make it more practical and efficient. For some special separable convex semidefinite programming problems, we can propose simplified versions. Most importantly, global convergence of modified alternating direction methods has to be mathematically proved. Furthermore, we will analyze their theoretical convergence rate and test their numerical performance in solving practical examples.

凸可分半定规划是一类在金融、工程等领域具有广泛应用背景的数学问题。凸非线性半定规划和大规模矩阵优化目前的一些实际应用均可以放在此框架下考虑，该模型也为这些实际问题的进一步研究提供了新的视野。本项目旨在通过分析各种矩阵函数的理论性质研究求解凸可分半定规划的数值算法。我们首先运用优化的思想，将原问题转换成一个矩阵空间下的变分不等式问题。这样属于一阶算法的交替方向法可以被推广用来求解凸可分半定规划问题。但是由于矩阵锥优化的结构特点，必须对原始算法作出适当的改良，以设计出易实现、高效率的实用数值算法。同时对于某些特殊类型的凸可分半定规划问题，提出相应的简便算法。最重要的是，改进后交替方向法的全局收敛性必须得到严格的数学证明。更进一步，我们还将分析其理论收敛速度以及用实际算例检验其数值表现。

在大数据广泛应用的背景下，凸可分半定规划属于一类重要的大规模数据矩阵优化问题。我们项目根据矩阵函数的理论性质，提出一些求解凸可分半定规划的易实行、高效率的实用数值算法。我们还根据实际出现的一些特殊类型问题，设计出相应的简便算法。为了解决大数据模型，我们将之转换成变分不等式后，一般使用包括交替方向法在内的一阶算法。我们证明了其收敛性，并分析了其收敛速度，更重要的是数值检验其计算效果。在项目资助发表的文章中，这些算法被应用来解决Netflix问题、投资组合问题、设施选址问题等重要的实际大数据问题，而且得到了良好的结果。