关于一类凸半定规划附加秩约束问题的理论与算法的研究

Convex semi-definite programming problems with additional rank constraint have broad applications in finance, computer sciences and other fields. Rank constraint is non-convex, non-smooth. Matrix variables demand huge calculations. These unfavorable properties make rank constrained problems extremely hard to solve. Available results are restricted to limited simple rank constrained problems with special structures. Theoretical results is far from perfect, and only few limited class of rank constrained problems are able to be solved efficiently. This project mainly discuss a special class of convex semi-definite programming problems with additional rank constraint (CSDPR), in both theoretical and numerical aspects. Aforementioned problem will be transformed to a mathematical programs with complementarity constraint (MPCC), based on which constraint qualifications (CQ) and optimality conditions will be discussed. First order conditions, including S-/M-/C stationary conditions, will be characterized, and together with CQ will be compared with that developed by other means. Second order conditions play an important role in theoretical aspects, and it is an important component of this project. MPCC reformulation also sheds lights on potential new algorithms that solves CSDPR. New algorithms will be developed via alternatively fixing variables, via DC programming reformulation and via splitting and smoothing techniques. We hope this project will help in promoting the study of rank constrained matrix optimization problems.

在凸半定规划问题中附加秩约束的问题是在金融、计算机技术等领域有着广泛应用的一类优化问题。秩约束非凸非光滑，且矩阵为变量运算量大，该类模型的求解十分困难。现有关于该类问题的研究主要局限于几类特殊的模型上，理论尚未完善，能有效求解的问题有限。本项目主要讨论一类凸半定规划附加秩约束优化问题的理论和相关算法。首先利用相关性质，将上述问题转化为一个等价的互补约束（MPCC）问题。从互补约束模型出发，讨论问题的约束规范条件和一阶最优性条件（S-、M-、C-稳定点条件），并与其他方式得到的约束规范条件和最优性条件进行比较。此外，约束非退化条件和二阶最优性条件在理论上有重要意义，是本项目的一个重要课题。另一方面，互补模型的建立提示了求解上述问题可能的新方法，本项目将分别从交替固定变量的方式，转化为DC优化求解的方式，以及分裂光滑化的方式研究该模型的迭代算法。期望本项目能推动含有秩约束矩阵优化问题的研究。

本项目主要通过研究半定矩阵互补约束优化模型（SDPMPCC）来讨论可转化为SDPMPCC的秩约束优化模型。试图在理论和算法两方面取得一定的成果。.理论方面，本项目执行过程中，厘清了SDPMPCC的特例——二阶锥互补约束优化模型的C-稳定性和弱C-稳定性的不同，并得到了二者等价的一个充分条件。讨论了与秩约束优化模型密切相关的扰动l1锥优化模型的相关理论，得到：在Robinson条件成立时，约束非退化条件、强二阶充分条件、KKT点的强正则性与Clarke广义雅克比非奇异条件是等价的，而孤立平稳性等价于严格约束规范加二阶充分条件。这部分深刻的理论结果完善了扰动l1锥优化模型的理论体系，是很有价值的。为了研究SDPMPCC模型的二阶条件，详细讨论了“半正定锥互补集合”及其特例“二阶锥互补集合”，证明了它们是外二阶正则的。还得到了到二阶锥互补集合上投影算子的二阶方向导数以及二阶锥互补集合外二阶切集合的具体表达式。由此构造二阶充分条件和二阶必要条件。而二阶条件是进一步分析模型灵敏性，估计算法收敛速度的基础，理论意义重大。.算法方面，一般的SDPMPCC模型不具有可依赖的具体结构，对应设计的算法实用价值不高。这提示我们考虑具有特殊结构的模型。本项目重点研究了含有随机变量的二阶锥互补约束优化模型的求解。具体的提出了光滑化随机抽样(SAA)方法和松弛SAA方法，并在一定假设下，证明了SAA子问题的可行集合、最优解集合和稳定点集合，以概率1分别对应收敛于原问题的可行集合、最优解集合、C-稳定点集合与弱C-稳定点集合。在更强的假设下，证明了子问题的稳定点以概率1收敛到原问题的M-稳定点。本项目还研究了二阶锥约束模型的求解，提出了对应的乘子邻近点算法（PMM），并在一定假设下估计出其最高可达到超线性收敛。考虑到其为高效的增广拉格朗日方法的变型，PMM算法具有较大的发展潜力。