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.
[Math] Solving a non-convex quadratically-constrained quadratic program
non-convex-optimizationoc.optimization-and-controlqcqp
Best Answer
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$?