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

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

Doubly Nonnegative Relaxation for Densest k-subgraph Problem

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.