Generally, Quadratic Programming solves the problem


$$\text{Given }Q, c, A, b,\text{ choose }x \text{ to maximize } x^TQx + c^Tx \text{ subject to } Ax \le b$$


In this form, Quadratic Programming is NP-hard. For my purposes, I happen to know that $b$ and $c$ are $0$ and $Q$ is diagonal. Thus, the problem looks like:


$$\text{Given }q, A, \text{ choose } x \text{ to maximize } q \cdot \langle x\_1^2, \dots, x\_n^2 \rangle \text{ subject to } Ax \le 0$$


Does the problem now admit an efficient solution?


The problem is not entirely theoretical, so I am somewhat interested in approximation methods if no exact solution can be found efficiently.


Edit: we can introduce the additional constraint $\sum\_j x\_j \le 1$ to prevent unbounded growth of optimization from scaling our solutions. This works because the condition $x \ge 0$ is already built into $A$.



Does Quadratic Programming get easier when it's described by a diagonal matrix?
The problem is still NP-hard. The proof is by reduction from checking matrix copositivity, [which is co-NP-complete](http://www-personal.umich.edu/~murty/np.pdf). A symmetric matrix $Q$ is said to be copositive if $x^TQx\geq 0$ for all $x\geq 0$, so it is a weaker condition than positive semidefiniteness.


For a symmetric matrix $Q$ one can pose the optimization problem of maximizing $-x^TQx$ subject to $x\geq 0$. The optimum value is $0$ if $Q$ is copositive and $\infty$ if $Q$ is not copositive. Diagonalizing $Q$ as $Q = P^{-1}DP$ with $P^{-1} = P^T$ and substituting $y = Px$, we can rewrite this optimization problem as one of maximizing $y^T(-D)y$ subject to $-P^{-1}y\leq 0$, which is of the form you specified.


