Separable QCQPs and Their Exact SDP Relaxations
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911564896927744 |
|---|---|
| author | Kojima, Masakazu Kim, Sunyoung Arima, Naohiko |
| author_facet | Kojima, Masakazu Kim, Sunyoung Arima, Naohiko |
| contents | This paper studies exact semidefinite programming relaxations (SDPRs) for separable quadratically constrained quadratic programs (QCQPs). We consider the construction of a larger separable QCQP from multiple QCQPs with exact SDPRs. We show that exactness is preserved when such QCQPs are combined through a separable horizontal connection, where the coupling is induced through the right-hand-side parameters of the constraints. The proposed framework provides a simple sufficient condition for exactness of the resulting SDPR. We then identify notable classes of QCQPs for which this condition holds, including convex QCQPs, QCQPs defined by sign-pattern and graph-structural conditions, and separable homogeneous QCQPs with a limited number of constraints. Two examples illustrate the constructive nature of the proposed framework, showing how heterogeneous QCQPs can be combined to yield new instances with exact SDP relaxations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_02968 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Separable QCQPs and Their Exact SDP Relaxations Kojima, Masakazu Kim, Sunyoung Arima, Naohiko Optimization and Control 90C20, 90C22, 90C25, 90C26 This paper studies exact semidefinite programming relaxations (SDPRs) for separable quadratically constrained quadratic programs (QCQPs). We consider the construction of a larger separable QCQP from multiple QCQPs with exact SDPRs. We show that exactness is preserved when such QCQPs are combined through a separable horizontal connection, where the coupling is induced through the right-hand-side parameters of the constraints. The proposed framework provides a simple sufficient condition for exactness of the resulting SDPR. We then identify notable classes of QCQPs for which this condition holds, including convex QCQPs, QCQPs defined by sign-pattern and graph-structural conditions, and separable homogeneous QCQPs with a limited number of constraints. Two examples illustrate the constructive nature of the proposed framework, showing how heterogeneous QCQPs can be combined to yield new instances with exact SDP relaxations. |
| title | Separable QCQPs and Their Exact SDP Relaxations |
| topic | Optimization and Control 90C20, 90C22, 90C25, 90C26 |
| url | https://arxiv.org/abs/2604.02968 |