Exact SDP relaxations for quadratic programs with bipartite graph structures
Exact SDP relaxations for quadratic programs with bipartite graph structures
复制标题
DOI：
10.1007/s10898-022-01268-3
复制
发表时间：
2022-04
影响因子：
1.8
通讯作者：
Godai Azuma;Mituhiro Fukuda;Sunyoung Kim;M. Yamashita
中科院分区：
文献类型：
--
作者：
Godai Azuma;Mituhiro Fukuda;Sunyoung Kim;M. Yamashita
对于非凸二次约束二次规划（QCQP），我们首先表明，在一定的可行性条件下，标准的半定规划（SDP）松弛是精确的二部图结构的QCQP。在强对偶条件下，通过研究对偶SDP松弛及其最优解的秩，得到了精确的最优解。我们的结果推广了以前的结果与符号确定的二部图结构的QCQP，森林结构的QCQP和非正非对角数据元素的QCQP。其次，我们提出了一种从没有特定结构的QCQP到具有二部图结构的QCQP的转换方法。因此，我们证明了更广泛的类QCQP可以精确地解决SDP松弛。最后给出了数值例子。
For nonconvex quadratically constrained quadratic programs (QCQPs), we first show that, under certain feasibility conditions, the standard semidefinite programming (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 generalize the previous results on QCQPs 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.