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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ It depends on what 'z' contains, because otherwise it's just a convex optimization problem. $\endgroup$
    – Suvrit
    Commented 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
    Commented 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
    Commented May 3, 2018 at 2:23
  • $\begingroup$ @Suvrit Only $x,y\in\mathbb R$. $\endgroup$
    – Turbo
    Commented 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
    Commented May 3, 2018 at 18:48

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .