A Customized ADMM Approach for Large-Scale Nonconvex Semidefinite Programming
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 object...
| 主要作者: | |
|---|---|
| 格式: | 文件 |
| 语言: | English |
| 出版: |
MDPI AG
2023-10-01
|
| 丛编: | Mathematics |
| 主题: | |
| 在线阅读: | https://www.mdpi.com/2227-7390/11/21/4413 |
| _version_ | 1827765653644247040 |
|---|---|
| author | Chuangchuang Sun |
| author_facet | Chuangchuang Sun |
| author_sort | Chuangchuang Sun |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-11T11:25:38Z |
| format | Article |
| id | doaj.art-b51a3ed6d88344239f831cf8a3e4c8b5 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-11T11:25:38Z |
| publishDate | 2023-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-b51a3ed6d88344239f831cf8a3e4c8b52023-11-10T15:07:48ZengMDPI AGMathematics2227-73902023-10-011121441310.3390/math11214413A Customized ADMM Approach for Large-Scale Nonconvex Semidefinite ProgrammingChuangchuang Sun0Mississippi State University, Starkville, MS 39762, USAWe 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.https://www.mdpi.com/2227-7390/11/21/4413semidefinite optimizationsymmetric matrix factorizationnonconvex optimizationlarge-scale graph problems |
| spellingShingle | Chuangchuang Sun A Customized ADMM Approach for Large-Scale Nonconvex Semidefinite Programming Mathematics semidefinite optimization symmetric matrix factorization nonconvex optimization large-scale graph problems |
| title | A Customized ADMM Approach for Large-Scale Nonconvex Semidefinite Programming |
| title_full | A Customized ADMM Approach for Large-Scale Nonconvex Semidefinite Programming |
| title_fullStr | A Customized ADMM Approach for Large-Scale Nonconvex Semidefinite Programming |
| title_full_unstemmed | A Customized ADMM Approach for Large-Scale Nonconvex Semidefinite Programming |
| title_short | A Customized ADMM Approach for Large-Scale Nonconvex Semidefinite Programming |
| title_sort | customized admm approach for large scale nonconvex semidefinite programming |
| topic | semidefinite optimization symmetric matrix factorization nonconvex optimization large-scale graph problems |
| url | https://www.mdpi.com/2227-7390/11/21/4413 |
| work_keys_str_mv | AT chuangchuangsun acustomizedadmmapproachforlargescalenonconvexsemidefiniteprogramming AT chuangchuangsun customizedadmmapproachforlargescalenonconvexsemidefiniteprogramming |