二次罚函数半定规划低秩解的平滑分析

Mar, 2018

二次罚函数半定规划低秩解的平滑分析

Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form

Srinadh Bhojanapalli, Nicolas Boumal, Prateek Jain, Praneeth Netrapalli

TL;DR本文采用Burer-Monteiro分解方法解决SDP问题，考虑约束条件次数随所需最优解的秩呈次二比例增长时，所有的近似局部最优解均为全局最优解，并将这个结果应用于Max-Cut和矩阵填充问题。

Abstract

semidefinite programs (SDP) are important in learning and combinatorial optimization with numerous applications. In pursuit of low-rank solutions and low complexity algorithms, we consider the burer--monteiro factorizat