arXiv Open Access 2024

On semidefinite descriptions for convex hulls of quadratic programs

Alex L. Wang Fatma Kilinc-Karzan

Lihat Sumber

Abstrak

Quadratically constrained quadratic programs (QCQPs) are a highly expressive class of nonconvex optimization problems. While QCQPs are NP-hard in general, they admit a natural convex relaxation via the standard semidefinite program (SDP) relaxation. In this paper we study when the convex hull of the epigraph of a QCQP coincides with the projected epigraph of the SDP relaxation. We present a sufficient condition for convex hull exactness and show that this condition is further necessary under an additional geometric assumption. The sufficient condition is based on geometric properties of $Γ$, the cone of convex Lagrange multipliers, and its relatives $Γ_1$ and $Γ^\circ$.

Topik & Kata Kunci

math.OC

Penulis (2)

Alex L. Wang

Fatma Kilinc-Karzan

Format Sitasi

APA MLA BibTeX

Wang, A.L., Kilinc-Karzan, F. (2024). On semidefinite descriptions for convex hulls of quadratic programs. https://arxiv.org/abs/2403.04752

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2024
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓