MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a nonconvex optimization problem. It is actually optimizing a linear objective function over a set of linear constraints and a set of nonlinear, non convex constraints.

Is this problem NP-hard? If so, haw can I prove this?

share|cite|improve this question
As @Brian Borchers says in his answer, this is impossible to answer without seeing the problem. – 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.

share|cite|improve this answer
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. – Star Jul 5 '13 at 6:36
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. – Brian Borchers Jul 5 '13 at 14:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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