Spectral Outer-Approximation Algorithms for Binary Semidefinite Problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918067942981632 |
|---|---|
| author | de Roux, Daniel Peng, Zedong Neira, David E. Bernal |
| author_facet | de Roux, Daniel Peng, Zedong Neira, David E. Bernal |
| contents | Integer semidefinite programming (ISDP) has recently gained attention due to its connection to binary quadratically constrained quadratic programs (BQCQPs), which can be exactly reformulated as binary semidefinite programs (BSDPs). However, it remains unclear whether this reformulation effectively uses existing ISDP solvers to address BQCQPs. To the best of our knowledge, no specialized ISDP algorithms exploit the unique structure of BSDPs derived from BQCQPs. This paper proposes a novel spectral outer approximation algorithm tailored for BSDPs derived from BQCQP reformulations. Our approach is inspired by polyhedral and second-order representable regions that outer approximate the feasible set of a semidefinite program relying on a spectral decomposition of a matrix that simultaneously diagonalizes the objective matrix and an aggregation of the constraint matrices. Computational experiments show that our algorithm is competitive with, and in some cases outperforms, state-of-the-art ISDP solvers such as SCIP-SDP and PAJARITO, highlighting ISDP's potential for solving BQCQPs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_18265 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Spectral Outer-Approximation Algorithms for Binary Semidefinite Problems de Roux, Daniel Peng, Zedong Neira, David E. Bernal Optimization and Control 90-08, 90C11, 90C22 Integer semidefinite programming (ISDP) has recently gained attention due to its connection to binary quadratically constrained quadratic programs (BQCQPs), which can be exactly reformulated as binary semidefinite programs (BSDPs). However, it remains unclear whether this reformulation effectively uses existing ISDP solvers to address BQCQPs. To the best of our knowledge, no specialized ISDP algorithms exploit the unique structure of BSDPs derived from BQCQPs. This paper proposes a novel spectral outer approximation algorithm tailored for BSDPs derived from BQCQP reformulations. Our approach is inspired by polyhedral and second-order representable regions that outer approximate the feasible set of a semidefinite program relying on a spectral decomposition of a matrix that simultaneously diagonalizes the objective matrix and an aggregation of the constraint matrices. Computational experiments show that our algorithm is competitive with, and in some cases outperforms, state-of-the-art ISDP solvers such as SCIP-SDP and PAJARITO, highlighting ISDP's potential for solving BQCQPs. |
| title | Spectral Outer-Approximation Algorithms for Binary Semidefinite Problems |
| topic | Optimization and Control 90-08, 90C11, 90C22 |
| url | https://arxiv.org/abs/2506.18265 |