论文标题
QCQPS及其应用中SDP精确性的几何视图
A Geometric View of SDP Exactness in QCQPs and its Applications
论文作者
论文摘要
二次约束二次程序（QCQP）是一类高度表达的非convex优化问题。虽然QCQP通常是NP-HARD，但他们通过标准（SHOR）半决赛计划（SDP）放松承认自然凸松弛。为了理解这种放松何时精确，我们研究了一般的QCQP及其（预测的）SDP放松。我们提供了足够的（在某些情况下，在某些情况下也是必要的）条件，以实现客观价值精确性（QCQP的客观值及其SDP松弛重合的条件）和凸出的船体精确度（QCQP ePigraph凸出的条件与其SDP弛豫的ePigraph syver hull相一致）。我们的精确度条件基于$γ$，凸Lagrange乘数的锥及其亲戚$γ_p$和$γ^\ circ $的几何特性。这些工具构成了我们的主要信息的基础：只要$γ$，$γ_p$或$γ^\ circ $就可以系统地处理精确性问题。作为此消息的进一步证据，我们应用工具来解决涉及二进制开关约束，二次矩阵程序的QCQP精确性问题，QCQP的分区问题公式以及随机和半随机QCQP。
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 (Shor) semidefinite program (SDP) relaxation. Towards understanding when this relaxation is exact, we study general QCQPs and their (projected) SDP relaxations. We present sufficient (and in some cases, also necessary) conditions for objective value exactness (the condition that the objective values of the QCQP and its SDP relaxation coincide) and convex hull exactness (the condition that the convex hull of the QCQP epigraph coincides with the epigraph of its SDP relaxation). Our conditions for exactness are based on geometric properties of $Γ$, the cone of convex Lagrange multipliers, and its relatives $Γ_P$ and $Γ^\circ$. These tools form the basis of our main message: questions of exactness can be treated systematically whenever $Γ$, $Γ_P$, or $Γ^\circ$ is well-understood. As further evidence of this message, we apply our tools to address questions of exactness for a prototypical QCQP involving a binary on-off constraint, quadratic matrix programs, the QCQP formulation of the partition problem, and random and semi-random QCQPs.
