Skip to main content
Source Link
Kap
  • 149
  • 7

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.