Solving graph equipartition SDPs on an algebraic variety

• 成果类型: Article
• 署名作者: Tang, Tianyun; Toh, Kim-Chuan
• 署名单位: National University of Singapore; National University of Singapore
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-01952-6
• 发表日期: 2024
• 页码: 299-347
• 关键词: Augmented Lagrangian method; semidefinite programs; rank; algorithm; matrices; barzilai

摘要

In this paper, we focus on using the low-rank factorization approach to solve the SDP relaxation of a graph equipartition problem, which involves an additional spectral upper bound over the traditional linear SDP. We discuss the equivalence between the decomposed problem and the original SDP problem. We also derive a sufficient condition, under which a second order stationary point of the non-convex problem is also a global minimum. Moreover, the constraints of the non-convex problem involve an algebraic variety with conducive geometric properties which we analyse. We also develop a method to escape from a non-optimal singular point on this variety. This allows us to use Riemannian optimization techniques to solve the SDP problem very efficiently with certified global optimality.