Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.