稠密 k-子图问题的双非负松弛

摘要

稠密k-子图问题是组合优化里面一类经典的优化问题，其在通常情况下是非凸且NP-难的。本文给出了求解该问题的一个新凸松弛方法-双非负松弛方法，并建立了问题的相应双非负松弛模型，而且证明了其在一定的条件下等价于一个新的半定松弛模型。最后，我们使用一些随机例子对这些模型进行了数值测试，测试的结果表明双非负松弛的计算效果要优于等价的半定松弛。%Densest k-subgraph problem is a classical problem of combinatorial optimization, which is nonconvex and NP-hard in general.In this paper, we propose a new convex relaxation method, i.e., doubly non-negative relaxation method, for solving this problem, and establish the corresponding doubly nonnegative relaxation model for the problem.Moreover, we prove that the doubly nonnegative relaxation model is equivalent to a new semidef-inite relaxation model under some conditions.Finally, some random examples are tested by these relaxation mod-els.The numerical results show that the doubly non-negative relaxation is more promising than the corresponding semidefinite relaxation.