Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
复制标题
DOI：
10.1007/s10898-021-01071-6
复制
发表时间：
2021-09-02
影响因子：
1.8
通讯作者：
Yamashita, Makoto
中科院分区：
文献类型：
--
作者：
Azuma, Godai;Fukuda, Mituhiro;Yamashita, Makoto
我们研究二次约束二次规划 (QCQP) 的半定规划 (SDP) 松弛的准确性。利用来自具有 n 个变量的 QCQP 数据矩阵的聚合稀疏矩阵，检查矩阵的秩和正半定性。我们证明，如果聚合稀疏矩阵的秩不小于 n-1，并且在用零替换一些非对角非零元素后矩阵保持半正定，则标准 SDP 松弛在可行性假设下为 QCQP 提供了精确的最优解。特别是，我们证明了具有森林结构聚合稀疏矩阵（例如三对角或箭头型矩阵）的 QCQP 满足秩的精确性条件。在可行区域紧凑的假设下，通过考虑对偶 SDP 松弛的可行性、SDP 的强对偶性以及具有扰动目标函数的 QCQP 序列来获得精确性。我们通过在数据矩阵上应用同时三对角化来将我们的结果推广到更广泛的 QCQP 类。此外，同时三对角化应用于矩阵笔，以便可以通过 SDP 松弛精确求解具有两个约束的 QCQP。
We study the exactness of the semidefinite programming (SDP) relaxation of quadratically constrained quadratic programs (QCQPs). With the aggregate sparsity matrix from the data matrices of a QCQP with n variables, the rank and positive semidefiniteness of the matrix are examined. We prove that if the rank of the aggregate sparsity matrix is not less than n- 1 and the matrix remains positive semidefinite after replacing some off-diagonal nonzero elements with zeros, then the standard SDP relaxation provides an exact optimal solution for the QCQP under feasibility assumptions. In particular, we demonstrate that QCQPs with foreststructured aggregate sparsity matrix, such as the tridiagonal or arrow-type matrix, satisfy the exactness condition on the rank. The exactness is attained by considering the feasibility of the dual SDP relaxation, the strong duality of SDPs, and a sequence of QCQPs with perturbed objective functions, under the assumption that the feasible region is compact. We generalize our result for a wider class of QCQPs by applying simultaneous tridiagonalization on the data matrices. Moreover, simultaneous tridiagonalization is applied to a matrix pencil so that QCQPs with two constraints can be solved exactly by the SDP relaxation.