论文标题
具有森林结构的二次限制性二次计划的精确SDP放松
Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
论文作者
论文摘要
我们研究半二次二次程序（QCQPS）的半决赛编程（SDP）松弛的精确性。通过来自具有$ n $变量的QCQP的数据矩阵的总稀疏矩阵，检查了矩阵的等级和正半数。我们证明，如果总稀疏矩阵的等级不少于$ n-1 $，并且在用零替换一些偏高的非零元素后，矩阵仍然是正半芬矿，那么标准的SDP松弛为可行性假设下的QCQP提供了一个准确的最佳解决方案。特别是，我们证明了具有森林结构的聚集稀疏矩阵（例如Tridiagonal或箭头型矩阵）的QCQP满足等级上的精确性条件。在假设可行区域是紧凑的假设下，考虑双重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 forest-structured 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.
