稠密k-子圖問題的雙非負松弛

稠密k-子圖問題的雙非負松弛

郭傳好,單而芳

(上海大學管理學院管理科學與工程系,上海200444 )

摘要：稠密k-子圖問題是組合優化里面一類經典的優化問題,其在通常情況下是非凸且NP-難的。本文給出了求解該問題的一個新凸松弛方法-雙非負松弛方法,并建立了問題的相應雙非負松弛模型,而且證明了其在一定的條件下等價于一個新的半定松弛模型。最后,我們使用一些隨機例子對這些模型進行了數值測試,測試的結果表明雙非負松弛的計算效果要優于等價的半定松弛。

關鍵詞：組合優化;雙非負松弛;半定松弛;稠密k-子圖

收稿日期：2014-01-23

基金項目：國家自然科學基金資助項目(11501350)

作者簡介：郭傳好(1980-),男,博士后,研究方向:最優化理論、算法及其應用;單而芳(1965-),男,教授,博士生導師,研究方向:圖論及其應用。

中圖分類號：O221.7文章標識碼：A

Doubly Nonnegative Relaxation for Densestk-subgraph Problem

GUO Chuan-hao, SHAN Er-fang

(DepartmentofManagementScienceandEngineering,SchoolofManagement,ShanghaiUniversity,Shanghai200444,China)

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; densestk-subgraph

0引言

對于一個給定的圖G(V,E),其中V表示圖的頂點集,E表示圖的邊集.圖G的稠密k-子圖(Densest K -Subgraph,簡記DkS)問題就是指:對任給一個參數k,尋找圖G中一個具有k個頂點的子圖,使得由這k個頂點所張成的子圖的所有邊所對應的權和最大.通常1

最近,Burer[3]為了處理一類全正規劃[4](Completely Positive Programming)問題,借助于Dinanada分解定理[5],得到了一類易求解的凸規劃問題,即雙非負規劃(Doubly Nonnegative Programming)問題.該問題具有多項式時間內點算法求解,而且還可以被許多凸規劃軟件求解.隨后這一方法被許多學者做進一步的研究[3, 4, 6, 7].

本文基于文獻[3]中方法的思想,對DkS問題的求解做進一步的研究. 首先, 根據DkS問題的結構特點, 我們建立其對應的雙非負松弛問題模型,探討分析其相應的模型特點.其次,還研究了雙非負松弛問題與相應的半定松弛問題之間的關系,即在一定的假設條件下,這兩類松弛問題具有一定的等價性.最后,大量的數值實驗結果表明雙非負松弛具有較好的計算效果相比較與等價的半定松弛問題.

1DkS問題數學模型

首先,簡單回顧一下DkS問題的基本定義.

定義1DkS問題就是指:在給定的圖G(V,E)上,尋找一個具有k個頂點的子圖,使得由這k頂點所張成的子圖的所有邊所對應的權和最大,其中1

記A=(aij)n×n表示圖G的加權鄰接矩陣,注意A是對稱的.則根據上面關于DkS問題的定義,可得該問題具有下面形式的數學表達式

s.t.xTe=k, (DkS)

x∈{0,1}n

s.t.xTx=k, (DkS-1)

x∈{0,1}n

不失一般性,假設A不正定,則(DkS)和(DkS-1)都是非凸的整數約束二次規劃問題,其通常是NP-難的.因此建立其相應可計算松弛問題模型是求解它們的有效方法之一.

2雙非負松弛模型

為了建立(DkS)的可計算松弛模型,同時注意到(DkS)和(DkS-1)中目標函數xTAx可以表示為A·xxT,其中·表示矩陣乘積的跡.記X=xxT,借助于向量的提升技術,則(DkS)和 (DkS-1)可分別被轉化為下面的數學表達形式

類似于文獻[4]中的定理2.6的證明,我們可以得到下面的定理,其證明過程在此省略.

定理2.1(i)(DkS)與(CPP-DkS)的最優值相等,(DkS-1)與(CPP-DkS-1)的最優值相等;(ii)如果(x*,X*)是(CPP-DkS)的最優解,則x*一定是(DkS)最優解的凸包,該結論對于(DkS-1)同樣成立.

通過定理2.1,我們可以把(DkS)和(DkS-1)分別轉化為(CPP-DkS)和(CPP-DkS-1),而且這種轉化在某種意義下是等價的.同時注意到(CPP-DkS)與(CPP-DkS-1)本質上都是線性凸規劃問題,我們希望其可以被一些現有的有效凸優化軟件有效求解.但是注意到(CPP-DkS)和 (CPP-DkS-1)中都含有約束條件C1+n,Dickinson和Gijen[8]已經證明判斷該條件的可行性是 NP-難的,所以(CPP-DkS)和(CPP-DkS-1)仍然是NP-難的,盡管其在形式上是凸問題.

值得慶幸的是,借助于下面的定理,C1+n可以被松弛為一個可計算的凸錐,這樣(CPP-DkS)和(CPP-DkS-1)就可以被進一步轉化為可計算的凸規劃問題.定理內容如下:

根據定理2.2,(CPP-DkS)和(CPP-DkS-1)可以被松弛為下面的問題

至此,由于(DkS)和(DkS-1)等價,我們分別建立了其相應的可計算雙非負松弛模型 (DNN-DkS)和(DNN-DkS-1).為了檢驗這些松弛模型的實際計算效果,下面我們將通過求解一些隨機產生的例子來展現其實際計算性能,所有的例子都通過Matlab編程調用CVX軟件進行求解.

首先使用模型(DNN-DkS)來求解可得

很容易驗證關系X*=x*(x*)T成立,所以上面得到的解是原問題的最優解.其次使用模型(DNN-DkS-1)來求解該問題得Opt(DNN-DkS-1)=1.84447, 其中

此時關系X*=x*(x*)T不成立, 所以使用模型(DNN-DkS-1)求解得到的只是原問題的一個上界1.84447.

上述兩個例子的測試結果表明盡管(DNN-DkS-1)和(DNN-DkS)同為原問題(DkS)的雙非負松弛模型,因為(DkS-1)與(DkS)等價,但是(DNN-DkS)的計算效果要優于(DNN-DkS-1).

為了進一步比較(DNN-DkS)與(DNN-DkS-1)的計算效果,我們測試了一組隨機產生的問題.

例3n=10,k=5,系數矩陣A按照下面的方式產生:rand(‘seed’, seed);G=(rand(n)<=0.5);A=round(20*rand(n)-10);A=triu(A, 1);A=A.*G;A=A+A’,其中seed=1,2,…,20.

圖1　最優值的性能描述

圖2　迭代次數的性能描述

3與半定松弛的關系

注意上一節我們所建立的(DkS)的兩個雙非負松弛模型(DNN-DkS)和(DNN-DkS-1) 中,約束條件D1+n其也可以視為半定約束加上一組線性不等式約束,這樣這些松弛模型在表達形式上就可以視為半定松弛模型,這與通常的半定松弛模型有什么關系？下面我們將研究雙非負松弛與半定松弛之間的關系.

首先注意到約束條件x∈{0,1}n?y∈{-1,1}n,y:=2x-e因此(DkS)和(DkS-1)也可以分別被等價的轉化為下面的問題

記Y=yyT,結合y∈{-1,1}n,易得1+yi+yj+Yij≥0,1≤i≤j≤n.利用yTAy可以表示為A·yyT,通過半定松弛技術,我們分別可得(DkS)和(DkS-1)的半定松弛模型如下

如上所述,我們又分別給出了(DkS)兩個新的半定松弛模型(SDR-DkS)和(SDR-DkS-1).下面的定理將進一步給出前一節所建立的雙非負松弛模型(DNN-DkS)和(DNN-DkS-1)分別與上面兩個半定松弛模型之間的關系.

定理3.1如果(DNN-DkS)與(SDR-DkS)的可行域都是非空的,那么(DNN-DkS)與(SDR-DkS)等價,即它們不僅最優值相等,而且最優解也可以相互的表示.同理,如果 (DNN-DkS-1)與(SDR-DkS-1)的可行域都是非空的,那么(DNN-DkS-1)與(SDR-DkS-1)也是等價的.

即Opt(SDR-DkS)≥Opt(DNN-DkS).

綜合上面的證明可得Opt(DNN-DkS)=Opt(SDR-DkS),而且它們的最優解可以相互的表示,所以(DNN-DkS)與(SDR-DkS)等價.對于(DNN-DkS-1)和(SDR-DkS-1)的等價性,可采用類似上面的證明方法,其證明過程與上面類似,在此省略.

定理3.1表明問題(DkS)的雙非負松弛模型,其實際上也等價于一個半定松弛模型.盡管如此,雙非負松弛模型自身的特殊結構特點還是蘊含了其具有一些較好的計算效果,相對比與半定松弛模型.下面就對一些使用隨機函數生成的問題(DkS),分別使用這些松弛模型求解,來進一步說明雙非負松弛模型的計算效果優勢.

例4n=20,k=5,系數矩陣A按照下面的生成方式產生:seed=1,2,…20; randn(‘seed’,seed);A=round(randn(n,n));A=tril(A,-1)+triu(A’, 0).

下面圖3和圖4分別給出了使用(DNN-DkS),(DNN-DkS-1),(SDR-DkS)和(SDR-DkS-1)求解這組問題的最優值與迭代次數結果相比的性能描述.從圖3中最優值比較結果顯然可得(DNN-DkS)與(SDR-DkS)具有相同的性能,(DNN-DkS-1)與(SDR-DkS-1)具有相同的性能,而且(DNN-DkS)和(SDR-DkS)的性能要優于(DNN-DkS-1)與(SDR-DkS-1)的性能.同時在測試的過程中, (DNN-DkS)與(SDR-DkS)分別能夠求得其中8個問題的最優解, 而(DNN-DkS-1)與(SDR-DkS-1)所得到的只是近似解.從圖4中迭代次數的性能比較結果可知(DNN-DkS-1)和(SDR-DkS-1)的性能比較好,要優于(DNN-DkS)與(SDR-DkS)的性能.但對于實際中的問題,特別是在一些高性能計算機的輔助條件下,我們更多關注的是問題最優值或近似解的情況,因此從這個意義上來說雙非負松弛模型(DNN-DkS)的性能更好一些.

圖3　最優值的性能描述

圖4　 CT二次接線板宏觀圖片

為了進一步驗證雙非負松弛模型的計算效果優勢,我們對下面幾個高維的例子做進一步的數值實驗測試,數值結果進一步說明了雙非負松弛模型(DNN-DkS)具有較好的計算效果,相比較與半定松弛模型.

例5n=30,k=10,矩陣A按照下面的方式產生:randn(‘2012’,2012),A=randn(n,n),A=tril(A, -1)+triu(A’,0).

下面使用(DNN-DkS)求解該問題可得Opt(DNN-DkS)=30.5894,迭代次數為52.而使用 (SDR-DkS)求解得Opt(SDR-DkS)=30.5903和迭代次數是70.很顯然,不僅 Opt(DNN-DkS)≤Opt(SDR-DkS),而且相應的求解迭代次數要優于(SDR-DkS)的.如果使用(DNN-DkS-1)和(SDR-DkS-1)來求解該問題得Opt(DNN-DkS-1)=Opt(SDR-DkS-1)=31.1136,而迭代次數分別為25和23.盡管使用(DNN-DkS-1)和(SDR-DkS-1)求解的迭代次數較少,但是它們所得到的最優值要大于(DNN-DkS)的,所以總得來說使用(DNN-DkS)求解的效果較好.

例6n=40,k=15,randn(‘7’, 7),系數矩陣A=tril(randn(n,n), -1)+triu(randn(n,n)’, 0).

調用(DNN-DkS)求解可得Opt(DNN-DkS)=53.2917和迭代次數52.而使用(SDR-DkS)求解Opt(SDR-DkS)=53.2925和迭代次數81.同樣,使用(DNN-DkS-1)和(SDR-DkS-1)來求解該問題可得Opt(DNN-DkS-1)=Opt(SDR-DkS-1)=53.8104,而迭代次數分別為24和23.綜合分析可得 (DNN-DkS)求解的效果較好.

例7n=90,k=25,randn(‘228’, 228),系數矩陣A=tril(round(randn(n,n)),-1)+triu(round(randn(n,n)’), 0).

調用(DNN-DkS)求解該問題可得Opt(DNN-DkS)=163.344,迭代次數為82,而使用 (SDR-DkS)求解得Opt(SDR-DkS)=163.361≥163.344和迭代次數12982.很明顯,使用雙非負松弛模型(DNN-DkS)求解具有非常好的計算效果.同樣,使用(DNN-DkS-1)和(SDR-DkS-1)來求解該問題可得Opt(DNN-DkS-1)=Opt(SDR-DkS-1)=167.421,而迭代次數分別為36和34.綜合分析可得使用雙非負松弛模型(DNN-DkS)求解具有非常好的計算效果.

4結論

本文研究了組合優化里面一類經典的優化問題-(DkS)問題.該問題在一般情形下是非凸且NP-難的,因此建立該問題的可計算凸松弛模型是有效求解此問題的方法之一.文中首先建立了問題的雙非負松弛模型,并分析了其相應特性.然后證明了在一定的假設條件下,該雙非負松弛模型等價于一個半定松弛模型.最后通過大量的隨機例子來測試了這些松弛模型的各自計算效果.數值結果表明雙非負松弛模型具有較好的計算效果相對比與半定松弛模型.

參考文獻：

[1]Corneil D G, Perl Y. Clustering and domination in perfect graphs[J]. Discrete Applied Mathematics, 1984, 9(1): 27-39.

[2]Goldstein D, Langberg M. The dense-subgraph problem[R]. arXiv preprint arXiv: 0912. 5327, 2009.

[3]Burer S. Optimizing a polyhedral-semidefinite relaxation of completely positive programs[J]. Mathematical Programming Computation, 2010, 2(1): 1-19.

[4]Burer S. On the copositive representation of binary and continuous nonconvex quadratic programs[J]. Mathematical Programming, 2009, 120(2): 479-495.

[5]Diananda P H. On non-negative forms in real variables some or all of which are non-negative[C]. Mathematical Proceedings of the Cambridge Philosophical Society, 1962, 58(1): 17-25.

[6]Bai Y Q, Guo C H, Sun L M. A new algorithm for solving nonconvex quadratic programming over an ice cream cone[J]. Pacific Journal of Optimization, 2012, 8(4): 651-665.

[7]Bomze I M. Copositive optimization-recent developments and applications[J]. European Journal of Operational Research, 2012, 216(3): 509-520.

[8]Dickinson P J C, Gijben L. On the computational complexity of membership problems for the completely positive cone and its dual[R]. Johann Bernoulli Institute for Mathematics and Computer Science, University of Groningen, The Netherlands, 2011.

[9]Grant M, Boyd S, Ye Y Y. CVX: Matlab software for disciplined convex programming[M]. 2008.

[10]Dolan E D, Moré J J. Benchmarking optimization software with performance profiles[J]. Mathematical Programming, 2002, 91(2): 201-213.