A Customized ADMM Approach for Large-Scale Nonconvex Semidefinite Programming

Chuangchuang Sun ()
Additional contact information
Chuangchuang Sun: Mississippi State University, Starkville, MS 39762, USA

Mathematics, 2023, vol. 11, issue 21, 1-27

Abstract: We investigate a class of challenging general semidefinite programming problems with extra nonconvex constraints such as matrix rank constraints. This problem has extensive applications, including combinatorial graph problems, such as MAX-CUT and community detection, reformulated as quadratic objectives over nonconvex constraints. A customized approach based on the alternating direction method of multipliers (ADMM) is proposed to solve the general large-scale nonconvex semidefinite programming efficiently. We propose two reformulations: one using vector variables and constraints, and the other further reformulating the Burer–Monteiro form. Both formulations admit simple subproblems and can lead to significant improvement in scalability. Despite the nonconvex constraint, we prove that the ADMM iterates converge to a stationary point in both formulations, under mild assumptions. Additionally, recent work suggests that in this matrix form, when the matrix factors are wide enough, the local optimum with high probability is also the global optimum. To demonstrate the scalability of our algorithm, we include results for MAX-CUT, community detection, and image segmentation.

Keywords: semidefinite optimization; symmetric matrix factorization; nonconvex optimization; large-scale graph problems (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/21/4413/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/21/4413/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:21:p:4413-:d:1266554

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().