Affine FR: an Effective Facial Reduction Algorithm for Semidefinite Relaxations of Combinatorial Problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908625502470144 |
|---|---|
| author | Hu, Hao Yang, Boshi |
| author_facet | Hu, Hao Yang, Boshi |
| contents | We develop a new method called affine facial reduction (FR) for recovering Slater's condition for semidefinite programming (SDP) relaxations of combinatorial optimization (CO) problems. Affine FR is a user-friendly method, as it is fully automatic and only requires a description of the problem. We provide a rigorous analysis of differences between affine FR and the existing methods. We also present numerical results to demonstrate the effectiveness of affine FR in reducing the size of SDP relaxations for CO problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_11796 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Affine FR: an Effective Facial Reduction Algorithm for Semidefinite Relaxations of Combinatorial Problems Hu, Hao Yang, Boshi Optimization and Control We develop a new method called affine facial reduction (FR) for recovering Slater's condition for semidefinite programming (SDP) relaxations of combinatorial optimization (CO) problems. Affine FR is a user-friendly method, as it is fully automatic and only requires a description of the problem. We provide a rigorous analysis of differences between affine FR and the existing methods. We also present numerical results to demonstrate the effectiveness of affine FR in reducing the size of SDP relaxations for CO problems. |
| title | Affine FR: an Effective Facial Reduction Algorithm for Semidefinite Relaxations of Combinatorial Problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2402.11796 |