Skip to main content
added 214 characters in body
Source Link
user21816
  • 693
  • 5
  • 12

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

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.

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

Source Link
user21816
  • 693
  • 5
  • 12

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

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.