Skip to main content
1 of 7
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Linear optimization with positive definite quadratic conditions in P?

I have a minimizing problem.

$$\min\sum_{i} y_{i}$$ $$y_i=x_iQ_ix_i'$$ $$0\leq x_{ij}\leq1$$ $$Az\leq b$$ where $Q_i$ are diagonal and has positive diagonal values and $A\in\mathbb R^{m\times n}$ and $b\in\mathbb R^m$ are constant matrix and vector respectively while $z\in\mathbb R^n$ is variables that contain $x,y$ as well.

Is this problem $NP$-hard or solvable in polynomial time?

Turbo
  • 13.9k
  • 1
  • 27
  • 76