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$ As @Brian Borchers says in his answer, this is impossible to answer without seeing the problem. $\endgroup$ – Igor Rivin Jul 5 '13 at 3:35

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.

  • $\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 Jul 5 '13 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 Jul 5 '13 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.