2
$\begingroup$

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?

$\endgroup$
6
  • 1
    $\begingroup$ It depends on what 'z' contains, because otherwise it's just a convex optimization problem. $\endgroup$
    – Suvrit
    May 3, 2018 at 1:51
  • $\begingroup$ @Suvrit Thank you. $z$ contains $x_i$, $y$ and other intermediate variables and in my case $xQx'=y$ holds (not $xQx'\leq y$) and you assign $y$ exactly $xQx'$ and I am not completely sure. $\endgroup$
    – Turbo
    May 3, 2018 at 1:54
  • $\begingroup$ The moment you have equality, things break down, because then you essentially have a non-convex constraint quadratic constraint, and this problem seems to not turn into an eigenvalue problem; this is not yet a proof of NP-Hardness (that's of course used a little loosely here, given that this is over real numbers not integers, but that's ok). $\endgroup$
    – Suvrit
    May 3, 2018 at 2:23
  • $\begingroup$ @Suvrit Only $x,y\in\mathbb R$. $\endgroup$
    – Turbo
    May 3, 2018 at 2:26
  • 1
    $\begingroup$ @RodrigodeAzevedo -- the OP changed the question's statement to make it not a QP; the original version as stated was a convex QP. $\endgroup$
    – Suvrit
    May 3, 2018 at 18:48

1 Answer 1

3
$\begingroup$

The following conditions

$$ \begin{array}{l} y=\sum x_i^2\\ 0\leq x_i\leq 1\\ y=\sum x_i \end{array} $$

are equivalent to $x_i\in \{0,1\}$, which means your construction allows you to introduce binary variables. Then you can use the minimization objective to encode something NP-hard, like the smallest dominating set in a graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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