Linear programming with non-convex quadratic constraint

Question

Could anyone let me know if the following linear programming problem can be solved in polynomial time or should be NP-hard?

$\min c^Tx$

s.t. $x^TQx\geq C^2, x\in [0,1]^n,c\in \mathbb{R}_+^n,Q\in\mathbb{R}_+^{n\times n}$ is positive semi-definite matrix.

Answer 1

I am afraid you can't.

This is a not convex problem due to the quadratic constraint. If your $Q$ matrix were negative semidefinite, then it would have been solvable in polynomial time.

Answer 2

My guess is that this problem can be solved in polynomial time.

It is well known that $\min_x c'x$, such that $x'Qx \geq C$ can be solved in polynomial time (since SDP relaxation is tight). Your problem has extra bound constraints $x_i$ in $[0,1]$, which may or may not change the answer. But I think it is quite possible.