非凸框架下大规模半定规划求解算法及其应用研究

Semidefinite programming (SDP) is a very active research direction in mathematical programming, which is widely applied in many problems of machine learning. However, the existing algorithms of SDP are not suitable for solving large-size SDP with big data. The matrix factorization is an effective way to reduce the dimension of SDP, but the resulted problem is nonconvex, which needs to be solved by nonconvex optimization. Combined with the hot point of nonconvex optimization in machine learning, this projection aims to develop a family of algorithms to solve many large-size SDPs in machine learning. The main contents and goals of this projection include: 1) from two different factorizations respectively, we will study the relationship (such as equivalence) between the original SDP and its factorized one; 2) under Euclidean and manifold geometries respectively, we will develop some batch algorithms to solve the factorized SDP; 3) under Euclidean and manifold geometries respectively, we will develop stochastic and online optimizations in nonconvex case, to solve larger-size factorized SDP. This projection will not only advance the development of SDP and nonconvex optimization, but also contribute to the ability of mining big data in machine learning.

半定规划(SDP)是最优化领域中一个很活跃的研究方向，它在诸多机器学习问题中有广泛应用。然而，传统的SDP求解算法并不适合于求解大数据背景下的大规模SDP问题。矩阵因子表示是降低SDP问题维数的一种有效方法，但基于因子表示的SDP是一个非凸问题，为此需发展非凸优化算法对其求解。结合当前机器学习中非凸优化研究热潮，本项目旨在发展一类大规模SDP求解算法，并将其应用于求解相关机器学习问题。主要研究内容及目标为: 1) 基于两种不同因子表示形式，研究原SDP和因子表示SDP之间的关系，如等价性等；2)分别在欧氏和流形两种几何范畴内，发展求解因子表示SDP问题的批处理型算法；3)分别在欧氏和流形两种几何范畴内，发展非凸优化的stochastic和online等序列型算法，以此求解更大规模的因子表示SDP问题。本项目研究将能推动SDP和非凸优化的发展，提升大数据背景下的机器学习能力。

半定规划 (SDP, Semidefinite Programing) 是最优化领域中一个很活跃的研究方向，它在诸多机器学习问题中有着广泛应用。然而，传统的SDP求解算法并不适合于求解大数据背景下的大规模SDP问题。半正定矩阵的低秩因子表示是降低SDP问题维数的一种有效方法，但基于因子表示的SDP是一个非凸问题，为此需发展非凸优化算法对其求解。结合当前机器学习中非凸优化研究热潮，本项目发展了几类大规模SDP问题的求解算法，并将其应用于求解相关的机器学习问题。主要研究内容及成果为：1) 通过半正定矩阵的双线性因子表示，首次提出了SDP问题的双凸罚模型及其求解算法，并给出了罚参数的理论下界; 2) 结合半正定矩阵低秩因子表示和鲁棒的凸损失函数，提出了一种鲁棒的SDP模型及其求解算法；3) 通过将凸损失函数推广到一类鲁棒的凹损失函数，提出了鲁棒性更好的SDP模型及其求解算法。在实验中，已将本项目研究的模型和算法应用于核矩阵学习、度量学习、矩阵填充、稀疏主成分分析等机器学习领域。本项目将能推动SDP和非凸优化的研究进展，提升大数据背景下相关的机器学习能力。此外，在本项目支持下：指导和培养了13名硕士研究生，使其在判别分析、聚类和流形学习等方面取得了一定研究成果；部分项目组成员还在广义方程解集及其牛顿型算法、自收缩型子流形等方面取得了一些研究进展。