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

SDP relaxation for linearly constrained 0-1quadratic program based on matrix decomposition

作　　者：蔡伟荣[1] 柳叶[2] 罗和治[3] 

机构地区：[1]浙江工业大学理学院,浙江杭州310023 [2]浙江东方职业技术学院社科基础部,浙江温州325000 [3]浙江工业大学经贸学院,浙江杭州310023

出　　处：《浙江工业大学学报》2015年第5期582-586,共5页Journal of Zhejiang University of Technology

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

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

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

分 类 号：O221.2[理学—运筹学与控制论]