低秩稀疏矩阵优化问题的模型与算法  

Models and algorithms for low-rank and sparse matrix optimization problems

作　　者：潘少华[1] 文再文 PAN Shaohual;WEN Zaiwen(School of Mathematics,South China University of Technology,Guangzhou 510641,China;Beijing International Center For Mathematical Research,Peking University,Beijing 100871,China)

机构地区：[1]华南理工大学数学学院,广州510641 [2]北京大学北京国际数学研究中心,北京100871

出　　处：《运筹学学报》2020年第3期1-26,共26页Operations Research Transactions

基　　金：国家重点研发计划(No.2018YFC0704300);国家自然科学基金(Nos.11971177,11831002);北京智源人工智能研究院资助。

摘　　要：低秩稀疏矩阵优化问题是一类带有组合性质的非凸非光滑优化问题.由于零模与秩函数的重要性和特殊性,这类NP-难矩阵优化问题的模型与算法研究在过去十几年里取得了长足发展。本文从稀疏矩阵优化问题、低秩矩阵优化问题、低秩加稀疏矩阵优化问题、以及低秩张量优化问题四个方面来综述其研究现状;其中,对稀疏矩阵优化问题,主要以稀疏逆协方差矩阵估计和列稀疏矩阵优化问题为典例进行概述,而对低秩矩阵优化问题,主要从凸松弛和因子分解法两个角度来概述秩约束优化和秩(正则)极小化问题的模型与算法研究。最后,总结了低秩稀疏矩阵优化研究中的一些关键与挑战问题,并提出了一些可以探讨的问题。Low-rank and sparse matrix optimization problem is a class of non-convex and non-smooth optimization problems with combinatorial properties.Due to the importance and special structure of the l0-norm and rank functions,the models and algorithms of such NP-hard matrix optimization problems have been studied extensively in the past ten years with great success.This paper summarizes the progress from four aspects:sparse matrix optimization problem,low rank matrix optimization problems,low rank plus sparse matrix optimization problem,and low rank tensor optimization problems.For the sparse matrix optimization problem,we mainly focus on the sparse inverse covariance matrix estimation and column sparse matrix optimization problems as examples.For the low-rank matrix optimization problem,we mainly consider the convex relaxation methods and the matrix decomposition methods.Finally,we summarize a few challenging issues in low-rank and sparse matrix optimization,and disucss some interesting topics.

关 键 词：低秩稀疏矩阵优化 凸松弛模型 因子分解模型 精确恢复条件 收敛性 

分 类 号：O221.2[理学—运筹学与控制论] O224[理学—数学]