3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Regarding theoretical computer science, you may have better luck on cstheory.stackexchange.com. $\endgroup$ Jul 9, 2013 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$ Jul 11, 2013 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, 2013 at 8:20

2 Answers 2

2
$\begingroup$

\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.

$\endgroup$
3
  • 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, 2013 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$ Jul 19, 2013 at 18:23
  • $\begingroup$ It's definitely necessary to do more here Geoff. $\endgroup$ Aug 19, 2013 at 1:48
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I cannot see how this problem is a special case of my problem. $\endgroup$
    – Star
    Jul 18, 2013 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$ Aug 19, 2013 at 2:29

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.