Consider an instance of non-convexoptimization problem: It seems that this problem is NP-complete. How can I find a suitable reduction for this?

  • $\begingroup$ Regarding theoretical computer science, you may have better luck on cstheory.stackexchange.com. $\endgroup$ – Florian Brucker Jul 9 '13 at 14:23
  • 1
    $\begingroup$ Nonconvex optimization is known to be NP-hard in most cases, and your problem looks nonconvex. It may not be nonconvex, but if you can show this property holds, then you need not go through a reduction argument to demonstrate NP-hardness. I don't know that there is a general NP-completeness result. $\endgroup$ – Geoff Oxberry Jul 11 '13 at 0:01
  • $\begingroup$ @GeoffOxberry: In my optimization problem, I am facing up to a set of non-convex constraints. I think it is for sure an instance of non-convex optimization problems. However, I do not think just referring to their NP-hardness in general would be sufficient in my case. I tried a lot to find a suitable reduction. $\endgroup$ – Star Jul 11 '13 at 8:20

\begin{align} \text{Min}&&\frac{1}{2}\sum_{(i,j,s,t)\in I}\|x_ix_j-x_sx_t\|\\ s.t.: && Ax=b\\ &&x\geq 0 \end{align}

has the same optimal solution as (and thus has the same computational complexity as, because this transformation is a polynomial reduction)

\begin{align} \text{Min}&&\frac{1}{2}\sum_{(i,j,s,t)\in I}\|x_ix_j-x_sx_t\|^{2}\\ s.t.: && Ax=b\\ &&x\geq 0. \end{align}

The latter problem is a polynomial programming problem, which is known to be NP-hard, since this program class contains quadratic programming, which is also NP-hard. (See Complexity Issues in Global Optimization: A Survey, by Stephen Vavasis.) Obtaining a reduction (as the other answer seems to do correctly) is useful, but unnecessary, since the problem can be transformed into a polynomial programming problem.

  • 1
    $\begingroup$ I think it is necessary. Even though, this problem is an instance of polynomial programming problem and this class is NP-hard; however, it is not true if I say that every instance in this class in NP-hard as well. $\endgroup$ – Star Jul 19 '13 at 9:24
  • $\begingroup$ You would have to demonstrate a specialized algorithm for your problem. Given the difficulty people have had with simpler problems ("only" globally minimizing a single bilinear term, rather than sums of norms of differences of bilinear terms), I would be surprised if you found that your problem was not NP-hard. $\endgroup$ – Geoff Oxberry Jul 19 '13 at 18:23
  • $\begingroup$ It's definitely necessary to do more here Geoff. $\endgroup$ – Brian Borchers Aug 19 '13 at 1:48

Consider the following special case (using 0-based indices): $$ A = \begin{bmatrix}0&0&0&0&0&1\\0&1&0&0&1&0 \end{bmatrix}, \ b = \begin{bmatrix} 1\\1 \end{bmatrix},\\ I = \{ (0,4,2,3), (0,0,0,5), (1,1,1,5), (2,2,2,5), (3,3,3,5) \}. $$ In other words, $x_5=1$ and $x_4=1-x_1$. So if we fix $x_1,x_2,x_3$, then the problem reduces to: $$ \min_{x_0} |x_0 (1-x_1) - x_2 x_3| + \sum_{i=0}^3 |x_i^2 - x_i| $$ The expression equals zero if and only if $x_i \in \{0,1\}$ and $x_1 x_2 x_3=0$.

So by introducing extra variables for each clause, one can reduce any 3-SAT problem to checking whether the minimum of such a program is zero.

  • $\begingroup$ I cannot see how this problem is a special case of my problem. $\endgroup$ – Star Jul 18 '13 at 8:43
  • $\begingroup$ Star; the point here is that if you start with a 3-SAT problem, you can use this trick (assuming that it's correct, and I haven't verified it yet) to write the 3-SAT problem as a problem of your form. A polynomial time algorithm for your problem would then give a polynomial time algorithm for 3-SAT. Thus your problem would be NP-Hard. $\endgroup$ – Brian Borchers Aug 19 '13 at 2:29

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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