基于矩陣分解的0-1二次規(guī)劃的SDP松弛

蔡偉榮1，柳葉2，羅和治3

(1.浙江工業(yè)大學(xué) 理學(xué)院，浙江 杭州 310023；2.浙江東方職業(yè)技術(shù)學(xué)院 社科基礎(chǔ)部，浙江 溫州 325000；

3.浙江工業(yè)大學(xué) 經(jīng)貿(mào)學(xué)院，浙江 杭州 310023)

摘要：0-1二次規(guī)劃是整數(shù)規(guī)劃中一類重要的最優(yōu)化問題，廣泛應(yīng)用于工程、經(jīng)濟(jì)管理、金融和管理科學(xué)等許多重要領(lǐng)域.利用矩陣分解方法，給出了帶線性約束的0-1二次規(guī)劃的一個緊的SDP松弛.通過目標(biāo)函數(shù)的矩陣分解并利用二次項的片段線性逼近技術(shù)，得到了原問題的一個凸松弛.再利用錐優(yōu)化對偶性，證明了尋找凸松弛中的最優(yōu)參數(shù)問題可以歸結(jié)為求解一個SDP問題，數(shù)值結(jié)果也表明該SDP松弛能提供原問題的一個更緊的下界.

關(guān)鍵詞：0-1二次規(guī)劃；SDP松弛；矩陣分解；片段線性逼近

收稿日期：2015-03-19

基金項目：國家自然科學(xué)基金資助項目(11371324)；浙江省自然科學(xué)基金資助項目(LY13A010012,LY13A010017)；浙江省教育廳高等學(xué)校訪問學(xué)者專業(yè)發(fā)展項目(FX2014179)

作者簡介：蔡偉榮(1986—)，男，浙江溫嶺人，碩士研究生，研究方向為最優(yōu)化理論與算法，E-mail:564507355@qq.com.

中圖分類號：O221.2

文獻(xiàn)標(biāo)志碼：A

文章編號：1006-4303(2015)05-0582-05

Abstract:The 0-1 quadratic program is an important class of optimization problems in integer programming, which has a wide range of applications in many important fields, including engineering, economics, finance, military and management science. A tight SDP relaxation is presented in this paper for 0-1quadratic programs with linear constraints based on the matrix decomposition approach. A convex relaxation of the original problem is first obtained by employing matrix decomposition of the objective function and piecewise linear approximation techniques of quadratic term. By means of the duality of cone optimization, it is then shown that the problem of finding the optimal parameters in the convex relaxation can be reduced to an SDP problem. Finally, numerical results show that the SDP relaxation can provide a tighter lower bound of the original problem.

Keywords:0-1 quadratic program; SDP relaxation; matrix decomposition; piecewise linear approximation

SDP relaxation for linearly constrained 0-1quadratic

program based on matrix decomposition

CAI Weirong1, LIU Ye2, LUO Hezhi3

(1.College of Science, Zhejiang University of Technology, Hangzhou 310023, China；

2.Department of Basic Social Science, Zhejiang Dongfang Vocational & Technical College, Wenzhou 325000, China;

3.College of Business Administration, Zhejiang University of Technology, Hangzhou 310023, China)

0-1二次規(guī)劃是應(yīng)用最廣泛的一類整數(shù)規(guī)劃問題，它包含了許多重要的組合優(yōu)化和整數(shù)規(guī)劃問題，如最大割問題、稠密子集問題、圖最大穩(wěn)定數(shù)問題和二次背包問題[1-2].0-1二次規(guī)劃是NP-難問題[3]，是近年國際優(yōu)化領(lǐng)域研究中富有挑戰(zhàn)性的熱點問題.尋找0-1二次規(guī)劃問題全局解的常用方法是基于線性規(guī)劃與凸松弛的分枝-定界方法，而分枝-定界方法的關(guān)鍵問題是如何有效地計算緊的下界.現(xiàn)有的方法是連續(xù)松弛對非凸目標(biāo)函數(shù)進(jìn)行凸下逼近和半定規(guī)劃(簡記SDP)松弛方法.WOLKOWICZ等[4]證明了無約束0-1二次規(guī)劃問題的某些凸松弛等價于SDP松弛.GOEMANS等[5]對最大割問題提出了基于SDP松弛和隨機(jī)化方法的近似算法，得到了常數(shù)近似誤差界0.878.對于無約束0-1二次規(guī)劃問題，SDP松弛可以得到更緊的下界和一個好的近似可行解[6-7]；MALIK等[8]研究了SDP松弛的對偶間隙問題；BILLIONNET等[9]提出了基于對角擾動技術(shù)的凸0-1二次規(guī)劃變換，且變換問題中的最優(yōu)參數(shù)通過解一個SDP問題得到.隨后，這種對角擾動變換方法被推廣到帶線性等式約束的0-1二次規(guī)劃[10]及帶線性約束的混合整數(shù)二次規(guī)劃[11].最近，JI等[1]對二次背包問題，利用目標(biāo)函數(shù)的矩陣分解和二次項對0-1變量的片段性表示，提出了一個改進(jìn)的凸0-1二次規(guī)劃變換，證明了該變換問題中的最優(yōu)參數(shù)可以由解一個SDP問題得到；ZHENG等[12]研究了非凸二次約束二次規(guī)劃的基于D.C.分解、矩陣錐分解和多胞形逼近等技術(shù)的SDP松弛方法.

受文[1,12]的啟發(fā)，利用矩陣分解方法給出了帶有線性約束的0-1二次規(guī)劃的一個緊的SDP松弛.該SDP松弛是基于非凸目標(biāo)函數(shù)中的一般矩陣分解，并利用二次項的片段線性化技術(shù)，可以得到原問題的一個凸松弛.證明了尋找凸松弛中的最佳參數(shù)的問題可歸結(jié)為一個SDP問題，討論了它與文獻(xiàn)中已有SDP松弛界的比較關(guān)系.需要指出的是，我們所用的方法是利用錐優(yōu)化對偶性，不同于文[2,12]，它們的方法是利用凸二次規(guī)劃的Lagrangian對偶的強(qiáng)對偶性定理和Shor的齊次化方法.最后，初步數(shù)值結(jié)果表明了最佳矩陣分解方法能提供更緊的SDP界.

1最佳矩陣分解和SDP松弛

考慮下面帶有線性約束的0-1二次規(guī)劃問題：

(QP)minf(x)=xTQx+qTx

s.t.Ax≤b,Bx=d,x∈{0,1}n

其中e=(1,1,…,1)T∈Rn，且K>0.

引入如下記號：記v(·)為問題(·)的最優(yōu)值，ei為Rn的第i個單位向量；設(shè)a=(a1,a2,…,an)T∈Rn，diag(a)表示以a1,a2,…,an為對角元的對角陣.記Sn為n×n對稱矩陣的集合；設(shè)A,B∈Sn，AB表示A-B為半正定矩陣，Sn中的內(nèi)積定義為.再設(shè)P和N分別為非負(fù)和非正n×n矩陣的集合，即

(1)

對任意的xi,xj∈{0,1}，有

xTdiag(ρ)x=ρTx，xixj=min{xi,xj}

xixj=max{0,xi+xj-1}

則對滿足Bx=d的x∈{0,1}n，f(x)可改寫為

(2)

其中：sij=min{xi,xj}；tij=max{0,xi+xj-1}.

(3)

(4)

tij=max{0,xi+xj-1},i,j=1,2,…,n

由于Pij≥0，約束sij=min{xi,xj}可松弛為兩個不等式sij≤xi，sij≤xj，不影響問題(4)的最優(yōu)解.類似，tij=max{0,xi+xj-1}可松弛為tij≥0，tij≥xi+xj-1.因此，凸松弛問題(4)等價于

s.t.Ax≤b,Bx=d,0≤x≤e

sij≤xi,sij≤xj,i,j=1,2,…,n

tij≥0,tij≥xi+xj-1,i,j=1,2,…,n

注意到(Pα,β,ρ,Z,P,N)是一個凸二次規(guī)劃，由內(nèi)點算法它是多項式可解的.對滿足Qα,β,ρ,Z,P,N0的任意(α,β,ρ,Z,P,N)，求解(Pα,β,ρ,Z,P,N)可得到(QP)的一個下界.一個自然的問題是：如何選取參數(shù)(α,β,ρ,Z,P,N)使得v(Pα,β,ρ,Z,P,N)提供(QP)的最緊下界？

在問題(Pα,β,ρ,Z,P,N)中給出最緊下界的最優(yōu)參數(shù)(α,β,ρ,Z,P,N)可以通過求解下面的問題得到

(CP) maxv(Pα,β,ρ,Z,P,N)

s.t.Qα,β,ρ,Z,P,N,

下面定理證明了問題(CP)等價于SDP問題.

定理1v(CP)=v(SDP1)，其中問題(SDP1)為下面的SDP問題：

(SDP1)minQ·X+qTx

s.t.Ax≤b,Bx=d,0≤x≤e

(6)

BTB·X-2dTBx+dTd=0

(7)

i=1,2,…,n

(8)

Xii=xi,i=1,2,…,n

(9)

AX≤bxT

(10)

Xij≤xi,Xij≤xj,i,j=1,2,…,n

(11)

Xij≥0,Xij≥xi+xj-1

i,j=1,2,…,n

(12)

X-xxT0

設(shè)(α*,β*,ρ*,B*,C*,D*,E*)分別為相應(yīng)于約束(7～12)的最優(yōu)乘子，再設(shè)P*=B*+C*和N*=-(D*+E*).則(α*,β*,ρ*,Z*,P*,N*)是問題(CP)的最優(yōu)解.

(14)

(DSDP1) max?(α,β,μ,ν,ξ,E)+τ

(15)

B+C=P,D+E=-N

(16)

其中Qα,β,ρ,Z,P,N是由式(1)定義的，且

Γ(α,β,ρ,μ,ν,η,ξ,B,C,E)=-ρ-ZTb+2αBTd-

(17)

(18)

(19)

由式(3，16)推出

v(DSDP1)

v(SDP1)≥v(CP)

注意到，(SDP1)中的約束Bx=d是多余的.事實上，BTB0和X-xxT0蘊含BTB·(X-xxT)≥0，從而由式推出Bx=d.

下面，討論問題(SDP1)與文[11]中對問題(QP)的SDP松弛界的比較關(guān)系.文[11]對(QP)提出的連續(xù)凸松弛為

(Ρα,ρ,U)minxT(Q+diag(ρ)+αBTB+U)x+

(q-2αBTd)Tx+αdTd-U·Y

s.t.(x,Y)∈Ω

其中：α∈R；ρ∈Rn；U∈Sn；Q+diag(ρ)+αBTB+U0；且

Ω=

易見，當(dāng)令β=0,Z=0,Y=P+N時,(Pα,ρ,U)是(Pα,β,ρ,Z,P,N)的一個特例.文[11]證明了(Ρα,ρ,U)中的最優(yōu)參數(shù)α,ρ,U可以通過求解SDP問題得到，即

(SDP0)minQ·X+qTx

s.t.Ax≤b,Bx=d,0≤x≤e

BTB·X-2dTBx+dTd=0

Xii=xi,i=1,2,…,n

Xij≤xi,Xij≤xj,i,j=1,2,…,n

Xij≥0,Xij≥xi+xj-1,i,j=1,2,…,n

X-xxT0

立即有

定理2v(SDP1)≥v(SDP0).

從后面的數(shù)值結(jié)果看到：當(dāng)n≤10時，約束式(8，10)對提供下界比較有效；同時對多數(shù)例子，不等式v(SDP1)>v(SDP0)恒成立.

2數(shù)值結(jié)果

本節(jié)給出了模型(SDP1)和(SDP0)對問題(QP)和(QKP)提供的下界的比較數(shù)值結(jié)果.數(shù)值測試在MatlabR2013b上實現(xiàn)，在PC機(jī)(3.33GHz，8GB，RAM)上運行，并用CVX1.2 中的SDPT3求解器來求解計算下界中的SDP模型.

為了衡量下界的緊性，定義下界的改進(jìn)率為

表1，2分別給出了對(QKP)(m=5)和(QP)(m=5,l=3)的具有相同規(guī)模的10個測試問題的平均下界、CPU時間和改進(jìn)率.從表1，2中可以看出：在所有的測試問題中，下界v(SDP1)比v(SDP0)更緊，而且下界改進(jìn)率隨著測試問題的規(guī)模增長而減少.

表1　問題(QKP)的平均數(shù)值結(jié)果

表2　問題(QP)的平均數(shù)值結(jié)果

3結(jié)論

參考文獻(xiàn)：

[1]JISH,ZHENGXJ，SUNXL.Animprovedconvex0-1quadraticprogramreformulationforquadraticknapsackproblems[J].PacificJournalofOptimization,2012,8(1):75-87.

[2]LOIOLAEM,ABREUNMMD,BOAVENTURA-NETTOPO,etal.Asurveyforthequadraticassignmentproblem[J].EuropeanJournalofOperationalResearch,2007,176(2):657-690.

[3]GAREYM,JOHNSOND.Computersandintractability:aguidetothetheoryofNP-completeness[M].NewYork:WHFreeman&Company,1979.

[4]WOLKOWICZH,POLJAKS.Convexrelaxationsof0-1quadraticprogramming[J].MathematicsofOperationsResearch,1993,20(3):550-561.

[5]GOEMANSMX,WILLIAMSONDP.Improvedapproximationalgorithmsformaximumcutandsatisfiabilityproblemsusingsemidefiniteprogramming[J].JournaloftheAssociationforComputingMachinery,1995,42(6):1115-1145.

[6]YUN.Semidefiniterelaxationandnonconvexquadraticoptimization[J].OptimizationMethods&Software,2010,9(1):141-160.

[7]YEY.Approximatingquadraticprogrammingwithboundandquadraticconstraints[J].MathematicalProgramming,1999,84(2):219-226.

[8]MALIKU,JAIMOUKHAIM,HALIKIASGD,etal.Onthegapbetweenthequadraticintegerprogrammingproblemanditssemidefiniterelaxation[J].MathematicalProgramming,2006,107(3):505-515.

[9]BILLIONNETA,ELLOUMIS.Usingamixedintegerquadraticprogrammingsolverfortheunconstrainedquadratic0-1problem[J].MathematicsProgram,2007,109(1):55-68.

[10]BILLIONNETA,ELLOUMIS,PLATEAUM.Improvingtheperformanceofstandardsolversforquadratic0-1programsbyatightconvexreformulation:theQCRmethod[J].DiscreteAppliedMathematics,2009,157(6):1185-1197.

[11]BILLIONNETA,ELLOUMIS,LAMBERTA.ExtendingtheQCRmethodtogeneralmixed-integerprograms[J].MathematicalProgramming,2012,131(1/2):381-401.

[12]ZHENGXJ,SUNXL,LID.Convexrelaxationsfornonconvexquadraticallyconstrainedquadraticprogramming:matrixconedecompositionandpolyhedralapproximation[J].MathematicalProgramming,2011,129(2):301-329.

(責(zé)任編輯：劉巖)