结构低秩矩阵优化问题的多阶段凸松弛法研究

Structured low-rank matrix optimization problems have a wide range of applications in a diverse set of fields such as statistics, control and system identification, signal and image processing, machine learning, combinatorial optimization, and so on. In this project, we conduct the research for the multi-stage convex relaxation approach to this class of nonconvex and nonsmooth optimization problems, starting with their equivalent MPECs and making suitable relaxations for the exact penalty problems yielded by the generalized complementarity constraint of the MPECs. It includes the following several aspects: (1) to study the exactness of the penalty problems yielded by penalizing the generalized complementarity constraint of MPECs to the objective, in the sense that the global optimal solution sets of the penalty problems coincide with those of the MPECs; (2) to design the multi-stage convex relaxation approach by relaxing the exact penalty problems of the MPECs into a sequence of tractable nonsmooth convex matrix optimization problems; (3) to study the error and approximate rank bounds for estimating the distance from the (approximate) optimal solution of convex relaxation problem in each stage to the true solution (or a global optimal solution of the original problem), and analyze the convergence rate of the multi-stage convex relaxation approach; (4) to design effective convergent algorithms for solving convex relaxation problems, and study the convergence rate of algorithms; (5) to write the codes for the multi-stage convex relaxation algorithms, and test the performance of new algorithms via numerical experiments. The research results will provide effective computational tools for structured low-rank matrix optimization problems and separable nonsmooth convex matrix optimization problems, and enrich the theory of low-rank matrix optimization and nonsmooth convex matrix optimization, having an important theoretical and practical significance.

结构低秩矩阵优化问题在统计、控制与系统辨识、信号与图像处理、机器学习、以及组合优化等诸多领域中有着广泛应用．本课题拟从结构低秩矩阵优化问题的等价MPEC入手，通过松弛其广义互补约束诱导的精确罚来开展该类非凸非光滑优化问题的多阶段凸松弛法研究，包括(1)研究将MPEC的广义互补约束罚到目标函数上所诱导的罚问题在全局意义下的精确性；(2)将MPEC的精确罚问题松弛为系列易处理的非光滑凸矩阵优化问题，设计多阶段凸松弛方法；(3)研究每阶段凸松弛问题的(近似)最优解与真实解(或原问题最优解)的误差和近似秩界，分析多阶段凸松弛方法的收敛速率；(4)设计求解凸松弛问题的有效收敛算法，研究其收敛速率；(5)编写多阶段凸松弛算法的程序代码，进行数值试验．该研究成果将为结构低秩矩阵优化问题和可分离非光滑凸矩阵优化问题提供有效的计算工具，丰富低秩矩阵优化和非光滑凸矩阵优化的理论，具有重要理论意义和应用价值．

结构低秩矩阵优化问题在统计、控制与系统辨识、信号与图像处理、机器学习、量子计算以及组合优化等诸多领域中有着广泛应用。本课题从低秩矩阵优化问题的等价 MPEC 形式入手，藉助其平衡约束诱导的全局精确罚开展了求解这类非凸非光滑矩阵优化问题的多阶段凸松弛法的研究。. 主要研究内容包括：(1)研究了等价 MPEC 的平衡约束所诱导的罚问题的全局精确惩罚性以及锥约束优化及广义方程的平稳性；(2)将全局精确罚松弛为系列易于处理的凸矩阵优化问题设计了相应的多阶段凸松弛法；(3)对所提出的多阶段凸松弛法，建立了统计理论保证；(4)研究了求解每阶段凸松弛问题的块分裂算法的迭代复杂界和收敛速率；(5)编写了多阶段凸松弛法的程序代码，并进行了大量数值试验究。取得了如下几方面的重要成果：(一)通过研究锥约束优化及广义方程的平稳性，对秩(正则)极小化问题，在适当的条件下证实了等价MPEC问题在全局最优解集上是部分一致平稳的，并藉助此性质建立了将其平衡约束加到目标函数而诱导的罚问题是全局精确罚；(二)根据全局精确罚的特殊结构，通过交替解全局精确罚问题提出了解这类NP-难矩阵优化的多阶段凸松弛算法，并针对结构低秩矩阵恢复问题，建立了每阶段凸松弛问题的最优解与真实解的误差界和近似秩界、以及多阶段凸松弛法统计意义下的收敛率；(三)根据每阶段凸松弛问题的可分离块结构，建立了求解子问题的半邻近交替方向乘子法的遍历迭代复杂界，并通过数值试验证实了多阶段凸松弛法会产生高质量的解。 . 本课题的研究既丰富了低秩矩阵优化和非光滑凸矩阵优化的理论，也为处理组合优化问题提供了新思路，具有重要理论意义和应用价值。.