基于矩阵分解的0-1二次规划的SDP松弛

基于矩阵分解的0-1二次规划的SDP松弛

蔡伟荣1，柳叶2，罗和治3

(1.浙江工业大学 理学院，浙江 杭州 310023；2.浙江东方职业技术学院 社科基础部，浙江 温州 325000；

3.浙江工业大学 经贸学院，浙江 杭州 310023)

摘要：0-1二次规划是整数规划中一类重要的最优化问题，广泛应用于工程、经济管理、金融和管理科学等许多重要领域.利用矩阵分解方法，给出了带线性约束的0-1二次规划的一个紧的SDP松弛.通过目标函数的矩阵分解并利用二次项的片段线性逼近技术，得到了原问题的一个凸松弛.再利用锥优化对偶性，证明了寻找凸松弛中的最优参数问题可以归结为求解一个SDP问题，数值结果也表明该SDP松弛能提供原问题的一个更紧的下界.

关键词：0-1二次规划；SDP松弛；矩阵分解；片段线性逼近

收稿日期：2015-03-19

基金项目：国家自然科学基金资助项目(11371324)；浙江省自然科学基金资助项目(LY13A010012,LY13A010017)；浙江省教育厅高等学校访问学者专业发展项目(FX2014179)

作者简介：蔡伟荣(1986—)，男，浙江温岭人，硕士研究生，研究方向为最优化理论与算法，E-mail:564507355@qq.com.

中图分类号：O221.2

文献标志码：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二次规划是应用最广泛的一类整数规划问题，它包含了许多重要的组合优化和整数规划问题，如最大割问题、稠密子集问题、图最大稳定数问题和二次背包问题[1-2].0-1二次规划是NP-难问题[3]，是近年国际优化领域研究中富有挑战性的热点问题.寻找0-1二次规划问题全局解的常用方法是基于线性规划与凸松弛的分枝-定界方法，而分枝-定界方法的关键问题是如何有效地计算紧的下界.现有的方法是连续松弛对非凸目标函数进行凸下逼近和半定规划(简记SDP)松弛方法.WOLKOWICZ等[4]证明了无约束0-1二次规划问题的某些凸松弛等价于SDP松弛.GOEMANS等[5]对最大割问题提出了基于SDP松弛和随机化方法的近似算法，得到了常数近似误差界0.878.对于无约束0-1二次规划问题，SDP松弛可以得到更紧的下界和一个好的近似可行解[6-7]；MALIK等[8]研究了SDP松弛的对偶间隙问题；BILLIONNET等[9]提出了基于对角扰动技术的凸0-1二次规划变换，且变换问题中的最优参数通过解一个SDP问题得到.随后，这种对角扰动变换方法被推广到带线性等式约束的0-1二次规划[10]及带线性约束的混合整数二次规划[11].最近，JI等[1]对二次背包问题，利用目标函数的矩阵分解和二次项对0-1变量的片段性表示，提出了一个改进的凸0-1二次规划变换，证明了该变换问题中的最优参数可以由解一个SDP问题得到；ZHENG等[12]研究了非凸二次约束二次规划的基于D.C.分解、矩阵锥分解和多胞形逼近等技术的SDP松弛方法.

受文[1,12]的启发，利用矩阵分解方法给出了带有线性约束的0-1二次规划的一个紧的SDP松弛.该SDP松弛是基于非凸目标函数中的一般矩阵分解，并利用二次项的片段线性化技术，可以得到原问题的一个凸松弛.证明了寻找凸松弛中的最佳参数的问题可归结为一个SDP问题，讨论了它与文献中已有SDP松弛界的比较关系.需要指出的是，我们所用的方法是利用锥优化对偶性，不同于文[2,12]，它们的方法是利用凸二次规划的Lagrangian对偶的强对偶性定理和Shor的齐次化方法.最后，初步数值结果表明了最佳矩阵分解方法能提供更紧的SDP界.

1最佳矩阵分解和SDP松弛

考虑下面带有线性约束的0-1二次规划问题：

(QP)minf(x)=xTQx+qTx

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

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

引入如下记号：记v(·)为问题(·)的最优值，ei为Rn的第i个单位向量；设a=(a1,a2,…,an)T∈Rn，diag(a)表示以a1,a2,…,an为对角元的对角阵.记Sn为n×n对称矩阵的集合；设A,B∈Sn，AB表示A-B为半正定矩阵，Sn中的内积定义为.再设P和N分别为非负和非正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)的最优解.类似，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)是一个凸二次规划，由内点算法它是多项式可解的.对满足Qα,β,ρ,Z,P,N0的任意(α,β,ρ,Z,P,N)，求解(Pα,β,ρ,Z,P,N)可得到(QP)的一个下界.一个自然的问题是：如何选取参数(α,β,ρ,Z,P,N)使得v(Pα,β,ρ,Z,P,N)提供(QP)的最紧下界？

在问题(Pα,β,ρ,Z,P,N)中给出最紧下界的最优参数(α,β,ρ,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

设(α*,β*,ρ*,B*,C*,D*,E*)分别为相应于约束(7～12)的最优乘子，再设P*=B*+C*和N*=-(D*+E*).则(α*,β*,ρ*,Z*,P*,N*)是问题(CP)的最优解.

(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松弛界的比较关系.文[11]对(QP)提出的连续凸松弛为

(Ρα,ρ,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；且

Ω=

易见，当令β=0,Z=0,Y=P+N时,(Pα,ρ,U)是(Pα,β,ρ,Z,P,N)的一个特例.文[11]证明了(Ρα,ρ,U)中的最优参数α,ρ,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).

从后面的数值结果看到：当n≤10时，约束式(8，10)对提供下界比较有效；同时对多数例子，不等式v(SDP1)>v(SDP0)恒成立.

2数值结果

本节给出了模型(SDP1)和(SDP0)对问题(QP)和(QKP)提供的下界的比较数值结果.数值测试在MatlabR2013b上实现，在PC机(3.33GHz，8GB，RAM)上运行，并用CVX1.2 中的SDPT3求解器来求解计算下界中的SDP模型.

为了衡量下界的紧性，定义下界的改进率为

表1，2分别给出了对(QKP)(m=5)和(QP)(m=5,l=3)的具有相同规模的10个测试问题的平均下界、CPU时间和改进率.从表1，2中可以看出：在所有的测试问题中，下界v(SDP1)比v(SDP0)更紧，而且下界改进率随着测试问题的规模增长而减少.

表1　问题(QKP)的平均数值结果

表2　问题(QP)的平均数值结果

3结论

参考文献：

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

(责任编辑：刘岩)