This question is about quadratic programming problems with box constraints (box-QP), i.e., optimisation problems of the form
- minimise $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T \mathbf{x}$ subject to $\mathbf{x} \in [0,1]^n$.
If $A$ was positive semi-definite, then everything would be nice and convex and easy, and we could solve the problem in polynomial time.
On the other hand, if we had the integrality constraint $\mathbf{x} \in \{0,1\}^n$, we could easily solve the problem in time $O(2^n \cdot \mathrm{poly}(n))$ by brute force. For the purposes of this question, this is reasonably fast.
But what about the non-convex continuous case? What is the fastest known algorithm for general box-QPs?
For example, can we solve these in moderately exponential time, e.g., $O(3^n \cdot \mathrm{poly}(n))$, or is the worst-case complexity of the best known algorithms something much worse?
Background: I have some fairly small box-QPs that I would actually like to solve, and I was a bit surprised to see how poorly some commercial software packages perform, even for very small values of $n$. I started to wonder if there is a TCS explanation for this observation.