NP-Completeness

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

• Regarding theoretical computer science, you may have better luck on cstheory.stackexchange.com. – Florian Brucker Jul 9 '13 at 14:23
• 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. – Geoff Oxberry Jul 11 '13 at 0:01
• @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. – 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.

• 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. – Star Jul 19 '13 at 9:24
• 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. – Geoff Oxberry Jul 19 '13 at 18:23
• It's definitely necessary to do more here Geoff. – 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.

• I cannot see how this problem is a special case of my problem. – Star Jul 18 '13 at 8:43
• 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. – Brian Borchers Aug 19 '13 at 2:29