论文标题
具有两分图结构的二次程序的精确SDP松弛
Exact SDP relaxations for quadratic programs with bipartite graph structures
论文作者
论文摘要
对于非convex二次约束二次程序（QCQPS），我们首先表明，在某些可行性条件下，对于具有双部分图形结构的QCQP，标准的半芬特（SDP）放松是精确的。通过检查双重SDP弛豫的双重SDP弛豫和该双SDP弛豫的最佳解决方案的等级来获得确切的最佳解决方案。我们对QCQPS的结果将QCQP上的结果推广，该结果具有标志性的两部分图结构，带森林结构的QCQP和具有非阳性非对基因对基因的数据元素的QCQP。其次，我们提出了一种从没有特定结构的QCQP的转换方法，向具有两分图结构的结构。结果，我们证明了可以通过SDP松弛来精确地解决更宽的QCQP。提出了数字实例以进行插图。
For nonconvex quadratically constrained quadratic programs (QCQPs), we first show that, under certain feasibility conditions, the standard semidefinite (SDP) relaxation is exact for QCQPs with bipartite graph structures. The exact optimal solutions are obtained by examining the dual SDP relaxation and the rank of the optimal solution of this dual SDP relaxation under strong duality. Our results on the QCQPs generalize the results on QCQP with sign-definite bipartite graph structures, QCQPs with forest structures, and QCQPs with nonpositive off-diagonal data elements. Second, we propose a conversion method from QCQPs with no particular structure to the ones with bipartite graph structures. As a result, we demonstrate that a wider class of QCQPs can be exactly solved by the SDP relaxation. Numerical instances are presented for illustration.
