Solving a non-convex quadratically-constrained quadratic program I have the following quadratic optimization problem: $\min_{\vec{x}} |\vec{x}|^2$ subject to $\vec{x}^T G_j \vec{x} \geq 1$, $j = 1 \ldots m$, where the $G_j$ are positive semidefinite. $|\vec{x}|$ is the norm of the vector $\vec{x}$ and $T$ denotes transpose. Since the $G_j$ are positive semidefinite, and we have $\geq$ in the constraints, the constraint region is non-convex. I am wondering if there are any theoretical results about the solution to this problem (except KKT conditions)? Also, are there any algorithms that can give the optimal value, and not only a local optima? Thanks.
 A: Branch-and-Bound can be used to solve problems like this, but it's an exponential time algorithm that is not practical for large instances of the problem.  What is $n$, the dimension of the $x$ vector?  How big is your $m$?  
A: In theory, there is a polynomial-time algorithm (follows from results of my joint paper with Dima Grigoriev) when $m$ is fixed, but this is not a practical one, and moreover I see from comments above that your $m$ is large compared to $n$. 
You can efficiently compute a semidefinite programming relaxation:
$$ \min Tr(X)\ \ \text{subject to $X\succeq 0$ (i.e. $X$ being p.s.d.) and  } Tr(XG_j)\geq 1,\ 1\leq j\leq m.$$ 
(To see that this is a relaxation, think of $X=xx^\top$.)
A: Your non-convex constraint is that $x$ lies on the outside of the intersection of some set of ellipsoids, which is a convex region $S$. You can try to randomly sample the surface of this set for random directions $u$, to determine the shortest vector in that direction which lies outside $S$. You can then do this repeatedly for random $u$ directions to try to approximate the answer. You might be able to get an idea of the maximum sampling density required based on the minimum angle between principal axes of $G$. This could lead to an ultimate refinement process once you have enough samples.
