I am trying to maximize a (semi) convex quadratic function over a convex (box constraints) set, however I don't know if it is possible to solve (in not too long computation time).
The problem is
$$\begin{array}{ll} \text{maximize} & \mathrm x^T \mathrm H \mathrm x + \mathrm G \mathrm x\\ \text{subject to} & \mathrm 1_n \leq \mathrm x \leq \mathrm 1_n\end{array}$$
where matrix $\mathrm H$ is symmetric and positive semidefinite.
I am trying to find the global optimum. If it might take too long to compute, I would happy if there is a method to upperbound this maximum as well, so any solver that could solve this approximately would also be great.
The length of my vector $\mathrm x$ could be between the sizes of $100$ and $1000$ elements, that is why I ask for an efficient algorithm, but I'm afraid the problem might be NP-hard.
Best Answer
Yes, this can be a very difficult problem to solve to optimality. This is called a non-convex problem (even though your functions are convex) and you need some kind of global solver for this. One specialized solver is GloMIQO. Otherwise BARON is also doing a good job on these. Furthermore the commercial solver Cplex has also added facilities to solve non-convex QP's. All these solvers provide bounds and "good" solutions when stopped early, before finding and proving the global optimum.