A polynomial case of cardinality constrained quadratic optimization problem

摘要：

　　We investigate in this paper a fixed parameter polynomial algorithm for cardinality constrained quadratic optimization problem, which is NP-hard in general. More specifically, we prove that, given a problem of size n, the number of decision variables, and s, the cardinality, if, for some 0<k ≤ n, the n - k largest eigenvalues of the coefficient matrix of the problem are identical, we can construct a solution algorithm with computational complexity of (O)(n2k), which is independent of the cardinality s. Our main idea is to decompose the primary problem into several convex subproblems, while the total number of the subproblems is determined by the number of cells generated by a corresponding hyperplane arrangement in (R)k space.

关键词： Cardinality constrained quadratic optimization Mixed-integer optimization cell enumeration nonconvex optimization fixed parameter polynomial algorithm

作者: Jianjun Gao Duan Li

作者单位: Department of Systems Engineering and Engineering Management,The Chinese University of Hong Kong, Shatin, Hong Kong S.A.R., P.R. China

会议类型: 国际会议

会议名称: 第8届国际最优化方法及应用大会

会议地点: 上海

会议语种:英文

页码: 182-183

在线出版日期: 2010-12-10（万方平台首次上网日期，不代表论文的发表时间）