A Low-Rank ADMM Splitting Approach for Semidefinite Programming
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916337964548096 |
|---|---|
| author | Han, Qiushi Li, Chenxi Lin, Zhenwei Chen, Caihua Deng, Qi Ge, Dongdong Liu, Huikang Ye, Yinyu |
| author_facet | Han, Qiushi Li, Chenxi Lin, Zhenwei Chen, Caihua Deng, Qi Ge, Dongdong Liu, Huikang Ye, Yinyu |
| contents | We introduce a new first-order method for solving general semidefinite programming problems, based on the alternating direction method of multipliers (ADMM) and a matrix-splitting technique. Our algorithm has an advantage over the Burer-Monteiro approach as it only involves much easier quadratically regularized subproblems in each iteration. For a linear objective, the subproblems are well-conditioned quadratic programs that can be efficiently solved by the standard conjugate gradient method. We show that the ADMM algorithm achieves sublinear or linear convergence rates to the KKT solutions under different conditions. Building on this theoretical development, we present LoRADS, a new solver for linear SDP based on the Low-Rank ADMM Splitting approach. LoRADS incorporates several strategies that significantly increase its efficiency. Firstly, it initiates with a warm-start phase that uses the Burer-Monteiro approach. Moreover, motivated by the SDP low-rank theory [So et al. 2008], LoRADS chooses an initial rank of logarithmic order and then employs a dynamic approach to increase the rank. Numerical experiments indicate that LoRADS exhibits promising performance on various SDP problems. A noteworthy achievement of LoRADS is its successful solving of a matrix completion problem with $15,694,167$ constraints and a matrix variable of size $40,000 \times 40,000$ in $351$ seconds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_09133 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Low-Rank ADMM Splitting Approach for Semidefinite Programming Han, Qiushi Li, Chenxi Lin, Zhenwei Chen, Caihua Deng, Qi Ge, Dongdong Liu, Huikang Ye, Yinyu Optimization and Control We introduce a new first-order method for solving general semidefinite programming problems, based on the alternating direction method of multipliers (ADMM) and a matrix-splitting technique. Our algorithm has an advantage over the Burer-Monteiro approach as it only involves much easier quadratically regularized subproblems in each iteration. For a linear objective, the subproblems are well-conditioned quadratic programs that can be efficiently solved by the standard conjugate gradient method. We show that the ADMM algorithm achieves sublinear or linear convergence rates to the KKT solutions under different conditions. Building on this theoretical development, we present LoRADS, a new solver for linear SDP based on the Low-Rank ADMM Splitting approach. LoRADS incorporates several strategies that significantly increase its efficiency. Firstly, it initiates with a warm-start phase that uses the Burer-Monteiro approach. Moreover, motivated by the SDP low-rank theory [So et al. 2008], LoRADS chooses an initial rank of logarithmic order and then employs a dynamic approach to increase the rank. Numerical experiments indicate that LoRADS exhibits promising performance on various SDP problems. A noteworthy achievement of LoRADS is its successful solving of a matrix completion problem with $15,694,167$ constraints and a matrix variable of size $40,000 \times 40,000$ in $351$ seconds. |
| title | A Low-Rank ADMM Splitting Approach for Semidefinite Programming |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2403.09133 |