Report
On semidefinite descriptions for convex hulls of quadratic programs
| العنوان: | On semidefinite descriptions for convex hulls of quadratic programs |
|---|---|
| المؤلفون: | Wang, Alex L., Kilinc-Karzan, Fatma |
| سنة النشر: | 2024 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Optimization and Control |
| الوصف: | 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 $\Gamma$, the cone of convex Lagrange multipliers, and its relatives $\Gamma_1$ and $\Gamma^\circ$. Comment: This paper is a significant rewrite of arXiv:2011.07155 [math.OC] and contains both new content and rewritten content |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2403.04752 |
| رقم الانضمام: | edsarx.2403.04752 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |