Does Quadratic Programming get easier when it's described by a diagonal matrix?

Question

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$.

Answer 1

The problem is still NP-hard. The proof is by reduction from checking matrix copositivity, which is co-NP-complete. 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.