Maximize convex function on box constraints

572 Views Asked by At

I try to maximize a quadratic function on box constraints as shown below

\begin{array}{l} \max {x^T}Qx\\ s.t.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} a \le {x_i} \le b \end{array} The length of vector $x$ is approximately $2000$ and $Q$ is symmetric. I am wondering if there exists a solver (like Cplex or Gurobi) which can solve this maximization problem efficiently.

1

There are 1 best solutions below

3
On

The problem that you've stated is in general NP-Hard, so you can't expect an "efficient" (meaning polynomial time) solver for all cases.

You haven't said anything about the convexity/concavity of the objective function. If $Q$ is negative semi-definite, then you've got a convex QP that can easily be solved to a global optimum by many software packages for convex QP. For example, this can easily be done with CPLEX. If your problems are convex, $N=2000$ is big but not really huge.

If $Q$ is indefinite or even positive semidefinite, then you've got a non-convex problem that can be solved by various exponential time algorithms. In particular, branch and bound methods for non-convex QP work pretty well in practice. Recent versions of CPLEX include this feature. Whether or not your particular instances will be practically solvable is impossible to say without experimenting.