Tell me more ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
up vote 0 down vote favorite

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

1 Answer

up vote 1 down vote

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|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 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 at 14:41

Your Answer

 
discard

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.