Constructing QCQP Instances Equivalent to Their SDP Relaxations
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_ | 1866929724011315200 |
|---|---|
| author | Kojima, Masakazu Arima, Naohiko Kim, Sunyoung |
| author_facet | Kojima, Masakazu Arima, Naohiko Kim, Sunyoung |
| contents | General quadratically constrained quadratic programs (QCQPs) are challenging to solve as they are known to be NP-hard. A popular approach to approximating QCQP solutions is to use semidefinite programming (SDP) relaxations. It is well-known that the optimal value $η$ of the SDP relaxation problem bounds the optimal value $ζ$ of the QCQP from below, i.e., $η\leq ζ$. The two problems are considered equivalent if $η= ζ$. In the recent paper by Arima, Kim and Kojima [arXiv:2409.07213], a class of QCQPs that are equivalent to their SDP relaxations are proposed with no condition imposed on the quadratic objective function, which can be chosen arbitrarily. In this work, we explore the construction of various QCQP instances within this class to complement the results in [arXiv:2409.07213]. Specifically, we first construct QCQP instances with two variables and then extend them to higher dimensions. We also discuss how to compute an optimal QCQP solution from the SDP relaxation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_15206 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Constructing QCQP Instances Equivalent to Their SDP Relaxations Kojima, Masakazu Arima, Naohiko Kim, Sunyoung Optimization and Control 90C20, 90C22, 90C25, 90C26 General quadratically constrained quadratic programs (QCQPs) are challenging to solve as they are known to be NP-hard. A popular approach to approximating QCQP solutions is to use semidefinite programming (SDP) relaxations. It is well-known that the optimal value $η$ of the SDP relaxation problem bounds the optimal value $ζ$ of the QCQP from below, i.e., $η\leq ζ$. The two problems are considered equivalent if $η= ζ$. In the recent paper by Arima, Kim and Kojima [arXiv:2409.07213], a class of QCQPs that are equivalent to their SDP relaxations are proposed with no condition imposed on the quadratic objective function, which can be chosen arbitrarily. In this work, we explore the construction of various QCQP instances within this class to complement the results in [arXiv:2409.07213]. Specifically, we first construct QCQP instances with two variables and then extend them to higher dimensions. We also discuss how to compute an optimal QCQP solution from the SDP relaxation. |
| title | Constructing QCQP Instances Equivalent to Their SDP Relaxations |
| topic | Optimization and Control 90C20, 90C22, 90C25, 90C26 |
| url | https://arxiv.org/abs/2502.15206 |