论文标题
在QCQPS的峰值凸面上
On convex hulls of epigraphs of QCQPs
论文作者
论文摘要
二次约束二次程序（QCQP）是一类基本的优化问题类别，众所周知，通常是NP-HARD。在本文中，我们研究了足够的条件，以立即暗示QCQP的标准半决赛计划（SDP）放松很紧。我们首先概述了证明这种足够条件的一般框架。然后，使用此框架，我们表明，每当二次特征值多重性时，凸面结果就会成立，即捕获给定问题中存在的对称性量的参数，就足够大。我们的结果还意味着二阶锥体程序的紧密度（以及凸面精确度）同时对角线qcqps的二阶锥体松弛。
Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study sufficient conditions for a convex hull result that immediately implies that the standard semidefinite program (SDP) relaxation of a QCQP is tight. We begin by outlining a general framework for proving such sufficient conditions. Then using this framework, we show that the convex hull result holds whenever the quadratic eigenvalue multiplicity, a parameter capturing the amount of symmetry present in a given problem, is large enough. Our results also imply new sufficient conditions for the tightness (as well as convex hull exactness) of a second order cone program relaxation of simultaneously diagonalizable QCQPs.
