I have a nonconvex optimization problem with a linear objective function, a set of linear constraints and a set of nonlinear, non-convex constraints. Is this problem NP-hard? If so, how can I prove this?
$\begingroup$ $\endgroup$
1 
- $\begingroup$ As @Brian Borchers says in his answer, this is impossible to answer without seeing the problem. $\endgroup$Igor Rivin– Igor Rivin2013-07-05 03:35:52 +00:00Commented Jul 5, 2013 at 3:35
Add a comment |
1 Answer
$\begingroup$ 
$\endgroup$
2 In general, you can show that a class of problems is NP-Hard by taking a known NP-hard problem and reducing it to a problem in your class (being careful that size of the problem does not increase too much.)
Since some well known NP-hard problems can easily be rewritten as nonlinear optimization problems with non-convex constraints, the class of non-convex nonlinear optimization problems is in general NP-Hard.
However, this says nothing about your particular non-convex optimization problem.
answered Jul 3, 2013 at 13:21
- $\begingroup$ Consider a source-sink flow network that for some nodes in the network, the corresponding outgoing arcs have unknown inputs that require the amount of flow to such a node must be split based on these coefficients. All unknowns are given in some intervals. Now, we need to check if there is a realization of the unknowns in the given intervals such that for the corresponding values, the network is feasible. $\endgroup$Star– Star2013-07-05 06:36:22 +00:00Commented Jul 5, 2013 at 6:36
- $\begingroup$ I can't make sense of what you've written in the above comment. I'd suggest editing your original question to describe the problem in detail using mathematical notation. $\endgroup$Brian Borchers– Brian Borchers2013-07-05 14:41:01 +00:00Commented Jul 5, 2013 at 14:41