一类混合0-1非凸二次约束二次规划问题的近似算法

摘要：

研究一类混合0-1非凸二次约束二次规划问题的近似算法.该问题是在M个非凸二次约束与一个基数约束下,求解一个n维向量的极小范数,变量包含M个0-1变量与一个n维连续向量.该问题是NP-难的.在求解其半正定规划(SDP)松弛问题的基础上,提出了一种随机舍入算法,能够得到原始的问题的一个可行解.数值仿真实验结果表明该方法是十分有效的.

关键词：非凸二次约束二次规划、半正定松弛、NP-难

所属期刊栏目：29

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

资助基金：国家自然科学基金资助项目11101261;"上海高校一流学科B"经费资助项目

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

页数：共8页

页码：305-312