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 RivinCommented 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$– StarCommented 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$ Commented Jul 5, 2013 at 14:41