Skip to main content

Linear optimization with one positive definite quadratic equality condition in P?

I have the following minimization problem in $z \in \mathbb R^n$, which contains $x_1, \dots, x_t, y \in \mathbb R$.

$$\begin{array}{ll} \text{minimize} & y\\ \text{subject to} & xQx'= y\\ & 0 \leq x_i \leq1\\ & Az \leq b\end{array}$$

where $Q$ is diagonal and has positive diagonal integer values, $A \in \mathbb Z^{m \times n}$ and $b \in \mathbb Z^m$ are given.

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

Turbo
  • 13.9k
  • 1
  • 27
  • 76