Maximize convex quadratic function on convex set (box constraints)

Question

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.

Answer 1

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.

Answer 2

The problem is indeed NP-hard. Of course, this doesn't prevent the possibility of solving it in some instances.

For example, consider a graph with $n$ vertices.
Let $G=0$ and $$H_{ij} = \cases{m & if $i=j$\cr -1 & if $(i,j)$ is an edge of the graph\cr 0 & otherwise\cr} $$ where $m$ is large enough to make $H$ positive definite. The constraints are $-1 \le x_i \le 1$. Since the objective is strictly convex, the optimal solution will be at a vertex of the feasible region. It's not hard to show that the optimal solution corresponds to a maximum cut in the graph (i.e. the cut is the partition $\{i: x_i = 1\}, \{i: x_i = -1\}$). The Max-Cut problem is well-known to be NP-hard.

Erwin Kalvelagen's suggestions are good ones. Also, knowing that optimal solutions will be vertices of the feasible region, you might try search methods such as simulated annealing or tabu search to get good (but not necessarily optimal) solutions. Alternatively, if $H$ is sparse, with the graph of nonzero terms having low tree-width, there are dynamical programming techniques that can be used.

BTW, I happen to work for D-Wave Systems. If $H$ is sparse with the right kind of structure, this might be something we could try to solve on a D-Wave quantum computer. E-mail me if you're interested.