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 nonconvex. 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.
BranchandBound 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$? 


In theory, there is a polynomialtime 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$.) 


Your nonconvex 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. 

