Abstract: 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 semidefinite relaxation model under some conditions. Finally, some random examples are tested by these relaxation models. The numerical results show that the doubly non-negative relaxation is more promising than the corresponding semidefinite relaxation.

Key words: combinatorial optimization, doubly nonnegative relaxation, semidefinite relaxation, densest k-subgraph

摘要： 稠密k-子图问题是组合优化里面一类经典的优化问题,其在通常情况下是非凸且NP-难的。本文给出了求解该问题的一个新凸松弛方法-双非负松弛方法,并建立了问题的相应双非负松弛模型,而且证明了其在一定的条件下等价于一个新的半定松弛模型。最后,我们使用一些随机例子对这些模型进行了数值测试,测试的结果表明双非负松弛的计算效果要优于等价的半定松弛。

关键词: 组合优化, 双非负松弛, 半定松弛, 稠密k-子图