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 BruckerJul 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$– Geoff OxberryJul 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$– StarJul 11, 2013 at 8:20
2 Answers
\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$– StarJul 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
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$– StarJul 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