稠密k-子圖問題的雙非負(fù)松弛

郭傳好,單而芳

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

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

關(guān)鍵詞：組合優(yōu)化;雙非負(fù)松弛;半定松弛;稠密k-子圖

收稿日期：2014-01-23

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(11501350)

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

中圖分類號(hào)：O221.7文章標(biāo)識(shí)碼：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引言

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

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

本文基于文獻(xiàn)[3]中方法的思想,對(duì)DkS問題的求解做進(jìn)一步的研究. 首先, 根據(jù)DkS問題的結(jié)構(gòu)特點(diǎn), 我們建立其對(duì)應(yīng)的雙非負(fù)松弛問題模型,探討分析其相應(yīng)的模型特點(diǎn).其次,還研究了雙非負(fù)松弛問題與相應(yīng)的半定松弛問題之間的關(guān)系,即在一定的假設(shè)條件下,這兩類松弛問題具有一定的等價(jià)性.最后,大量的數(shù)值實(shí)驗(yàn)結(jié)果表明雙非負(fù)松弛具有較好的計(jì)算效果相比較與等價(jià)的半定松弛問題.

1DkS問題數(shù)學(xué)模型

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

定義1DkS問題就是指:在給定的圖G(V,E)上,尋找一個(gè)具有k個(gè)頂點(diǎn)的子圖,使得由這k頂點(diǎn)所張成的子圖的所有邊所對(duì)應(yīng)的權(quán)和最大,其中1

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

s.t.xTe=k, (DkS)

x∈{0,1}n

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

x∈{0,1}n

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

2雙非負(fù)松弛模型

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

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

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

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

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

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

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

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

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

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

上述兩個(gè)例子的測試結(jié)果表明盡管(DNN-DkS-1)和(DNN-DkS)同為原問題(DkS)的雙非負(fù)松弛模型,因?yàn)?DkS-1)與(DkS)等價(jià),但是(DNN-DkS)的計(jì)算效果要優(yōu)于(DNN-DkS-1).

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

例3n=10,k=5,系數(shù)矩陣A按照下面的方式產(chǎn)生: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　最優(yōu)值的性能描述

圖2　迭代次數(shù)的性能描述

3與半定松弛的關(guān)系

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

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

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

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

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

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

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

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

例4n=20,k=5,系數(shù)矩陣A按照下面的生成方式產(chǎn)生: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)求解這組問題的最優(yōu)值與迭代次數(shù)結(jié)果相比的性能描述.從圖3中最優(yōu)值比較結(jié)果顯然可得(DNN-DkS)與(SDR-DkS)具有相同的性能,(DNN-DkS-1)與(SDR-DkS-1)具有相同的性能,而且(DNN-DkS)和(SDR-DkS)的性能要優(yōu)于(DNN-DkS-1)與(SDR-DkS-1)的性能.同時(shí)在測試的過程中, (DNN-DkS)與(SDR-DkS)分別能夠求得其中8個(gè)問題的最優(yōu)解, 而(DNN-DkS-1)與(SDR-DkS-1)所得到的只是近似解.從圖4中迭代次數(shù)的性能比較結(jié)果可知(DNN-DkS-1)和(SDR-DkS-1)的性能比較好,要優(yōu)于(DNN-DkS)與(SDR-DkS)的性能.但對(duì)于實(shí)際中的問題,特別是在一些高性能計(jì)算機(jī)的輔助條件下,我們更多關(guān)注的是問題最優(yōu)值或近似解的情況,因此從這個(gè)意義上來說雙非負(fù)松弛模型(DNN-DkS)的性能更好一些.

圖3　最優(yōu)值的性能描述

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

為了進(jìn)一步驗(yàn)證雙非負(fù)松弛模型的計(jì)算效果優(yōu)勢,我們對(duì)下面幾個(gè)高維的例子做進(jìn)一步的數(shù)值實(shí)驗(yàn)測試,數(shù)值結(jié)果進(jìn)一步說明了雙非負(fù)松弛模型(DNN-DkS)具有較好的計(jì)算效果,相比較與半定松弛模型.

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

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

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

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

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

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

4結(jié)論

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

參考文獻(xiàn)：

[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.