Deterministic Guarantees for Burer‐Monteiro Factorizations of Smooth Semidefinite Programs
Deterministic Guarantees for Burer‐Monteiro Factorizations of Smooth Semidefinite Programs
复制标题
DOI：
10.1002/cpa.21830
复制
发表时间：
2018-04
影响因子：
3
通讯作者：
Nicolas Boumal;V. Voroninski;A. Bandeira
中科院分区：
文献类型：
--
作者：
Nicolas Boumal;V. Voroninski;A. Bandeira
考虑具有相等约束的半定规划（sdp）。要优化的变量是一个大小为n的正半定矩阵X。按照Burer - Monteiro方法，我们优化大小为n × p的因子Y，使得X = YYT。当p很小时，这保证了问题的正半正定性，并且可以降低问题的维数，但结果是一个在Y上具有二次代价函数和二次等式约束的非凸优化问题。在本文中，我们证明了如果Y上的约束集规则地定义了一个光滑流形，那么，尽管非凸性，只要p足够大，一阶和二阶必要最优性条件也是充分的。对于较小的p值，我们显示了几乎所有（线性）成本函数的类似结果。在这些条件下，全局最优Y映射到SDP的全局最优X = YYT。我们推导了广义特征向量问题、信任域子问题和若干球面上的二次优化的SDP松弛，以及随机块建模和旋转同步中常见的Max - Cut和正交- Cut SDP松弛的旧的和新的结果。©2019 Wiley期刊公司
We consider semidefinite programs (SDPs) with equality constraints. The variable to be optimized is a positive semidefinite matrix X of size n. Following the Burer‐Monteiro approach, we optimize a factor Y of size n × p instead, such that X = YYT. This ensures positive semidefiniteness at no cost and can reduce the dimension of the problem if p is small, but results in a nonconvex optimization problem with a quadratic cost function and quadratic equality constraints in Y. In this paper, we show that if the set of constraints on Y regularly defines a smooth manifold, then, despite nonconvexity, first‐ and second‐order necessary optimality conditions are also sufficient, provided p is large enough. For smaller values of p, we show a similar result holds for almost all (linear) cost functions. Under those conditions, a global optimum Y maps to a global optimum X = YYT of the SDP. We deduce old and new consequences for SDP relaxations of the generalized eigenvector problem, the trust‐region subproblem, and quadratic optimization over several spheres, as well as for the Max‐Cut and Orthogonal‐Cut SDPs, which are common relaxations in stochastic block modeling and synchronization of rotations. © 2019 Wiley Periodicals, Inc.