秩约束半定规划问题的算法研究

本项目旨在研究秩约束半定规划问题的算法。该问题源于组合优化、金融分析与预测、机器学习、数据挖掘、控制论等多个应用领域，是一类重要的非凸优化问题。此类问题非凸性体现在秩约束条件，因此如何处理秩约束十分关键。本项目将摆脱传统求解松弛问题的思路，拟采用"等价转化-算法设计"的思路，研究秩约束条件，建立等价问题并设计算法直接求解。理论上，我们将借鉴国际上研究五类特殊双曲锥的思路，探讨如何恰当描述秩约束条件，建立问题的等价形式并研究其对偶性质。算法上，有针对性地设计算法，分析算法的计算复杂性及局部收敛速度。在国际上，设计算法直接求解该类问题的研究工作正处于起步阶段。据我们所知，目前国内还没有从直接求解的角度对该问题进行研究的相关工作。因此，开展本项目的研究可以进一步丰富我国在最优化理论与算法方面的研究工作，具有重要的研究意义。

项目研究了秩约束半定规划问题及相关的低秩矩阵优化问题及应用，主要成果如下：（1）对于谱范数意义下的带有等式约束和对称半正定约束的矩阵逼近问题，利用谱范数函数的Moreau-Yosida正则化性质，提出了交替方向算法求解，数值实验表明该算法可快速有效地求解快速分配线性平均问题和最优相关系数矩阵逼近问题；（2）在求解实际问题方面，研究了广域雷达系统中的地面动目标检测问题，提出了结构化RPCA模型和行模RPCA模型来更好地描述该问题，并设计了基于交替方向思想的算法求解两个模型。数值模拟结果表明，两类模型具有更好的地面动目标检测效果。（3）对地面动目标检测问题，从理论上研究了该问题的适定性，证明了在三个及以上等间距分布通道的情形下，该问题是适定的，为建立模型和设计算法提供了有力的理论支撑。提出了基于相位的RPCA模型，该模型可以精确刻画地面动目标检测问题，并设计了基于交替方向思想的算法进行求解。数值模拟结果表明，该模型较已有模型具有更好的检测效果。（4）对带有Schatten-p正则项的矩阵最小二乘问题，建立了其最优解的非零奇异值的下界理论，刻画了问题的一阶和二阶必要性条件，并研究了其对应的光滑化问题的相关内容。提出了光滑化梯度算法求解原问题，并将非零奇异值的下界理论用于算法设计中。数值实验表明，建立的下界理论可以有效地帮助我们得到更稀疏的解。（5）对相位提取问题，提出了基于小波框架的模型，并借助交替方向的思想设计算法进行求解。数值实验表明所提算法和已有算法不相上下。.本项目共发表学术论文2篇，SCI收录1篇，已投稿3篇。 项目申请人在国际重要学术会议上做报告3次，包括大会报告1次，分组报告两次；在国内重要学术会议上做报告2次，包括大会报告1次，分组报告1次。项目申请人出境学术交流1次2个月，邀请境外专家来访2人次。