I try to maximize a quadratic function on box constraints as shown below max x T Q x s . t . a ≤ x i ≤ b 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.

Question

I try to maximize a quadratic function on box constraints as shown below                    max                              x            T                          Q        x                            s        .        t        .                                                                                                                                          a        ≤                              x            i                          ≤        b            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.

Josie Stephenson · Accepted Answer

The problem that you&#039;ve stated is in general NP-Hard, so you can&#039;t expect an &quot;efficient&quot; (meaning polynomial time) solver for all cases.You haven&#039;t said anything about the convexity/concavity of the objective function. If   Q is negative semi-definite, then you&#039;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&#039;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.

I try to maximize a quadratic function on box constraints as shown below <mtable columnalign=

Answered question

Answer & Explanation

New Questions in High school geometry