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

摘要：

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

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

所属期刊栏目：43

分类号：O221.2(运筹学)

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

在线出版日期：2015-11-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：582-586