运筹与管理
運籌與管理
운주여관리
Operations Research and Management Science
2015年
5期
144-150
,共7页
组合优化%双非负松弛%半定松弛%稠密k-子图
組閤優化%雙非負鬆弛%半定鬆弛%稠密k-子圖
조합우화%쌍비부송이%반정송이%주밀k-자도
combinatorial optimization%doubly nonnegative relaxation%semidefinite relaxation%densest k-subgraph
稠密k-子图问题是组合优化里面一类经典的优化问题，其在通常情况下是非凸且NP-难的。本文给出了求解该问题的一个新凸松弛方法-双非负松弛方法，并建立了问题的相应双非负松弛模型，而且证明了其在一定的条件下等价于一个新的半定松弛模型。最后，我们使用一些随机例子对这些模型进行了数值测试，测试的结果表明双非负松弛的计算效果要优于等价的半定松弛。
稠密k-子圖問題是組閤優化裏麵一類經典的優化問題，其在通常情況下是非凸且NP-難的。本文給齣瞭求解該問題的一箇新凸鬆弛方法-雙非負鬆弛方法，併建立瞭問題的相應雙非負鬆弛模型，而且證明瞭其在一定的條件下等價于一箇新的半定鬆弛模型。最後，我們使用一些隨機例子對這些模型進行瞭數值測試，測試的結果錶明雙非負鬆弛的計算效果要優于等價的半定鬆弛。
주밀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.
