On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets

摘要

In the paper we prove that any nonconvex quadratic problem over some set K ? ?~n with additional linear and binary constraints can be rewritten as a linear problem over the cone, dual to the cone of K-semidefinite matrices. We show that when K is defined by one quadratic constraint or by one concave quadratic constraint and one linear inequality, then the resulting K-semidefinite problem is actually a semidefinite programming problem. This generalizes results obtained by Sturm and Zhang (Math Oper Res 28:246-267, 2003). Our result also generalizes the well-known completely positive representation result from Burer (Math Program 120:479-495, 2009), which is actually a special instance of our result with K=?_+ ~n.