Skip to main content
Computer Science

Return to Question

Tweeted twitter.com/StackCompSci/status/1174835566803869696
added 4 characters in body
Source Link
Sasha the Noob
Sasha the Noob
  • 623
  • 1
  • 7
  • 9

Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time.

Now I am learning that a convex optimization problem can be NP-Hard, but that convex problems are still somehow considered easier than non-convex problems.

Can someone explain this apparent contradiction to me:

  • Is it true that a convex optimization can be NP-Hard? On one hand, based on this post and the accepted answer, yes, There are examples of convex optimization problems which are NP-hard. On the other hand, This lecture from a Stanford Professor, around 28:00 states that convexity means tractability and polynomial time algorithms.

  • If it is indeed true that convex optimization problems can be NP-Hard, then in what sense are they "easier" than non-convex problems? As far as I know, there are no levels of NP-Hardness, anything between NP-Complete and P-Space is NP-Hard. I frequently hear Operations Research people say that we have all sorts of tools for convex problems, while non-convex problems are still very hard to deal with?

Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time.

Now I am learning that a convex optimization problem can be NP-Hard, but that convex problems are still somehow considered easier than non-convex problems.

Can someone explain this apparent contradiction to me:

  • Is it true that a convex optimization can be NP-Hard? On hand, based on this post and the accepted answer, yes, There are examples of convex optimization problems which are NP-hard. On the other hand, This lecture from a Stanford Professor, around 28:00 states that convexity means tractability and polynomial time algorithms.

  • If it is indeed true that convex optimization problems can be NP-Hard, then in what sense are they "easier" than non-convex problems? As far as I know, there are no levels of NP-Hardness, anything between NP-Complete and P-Space is NP-Hard. I frequently hear Operations Research people say that we have all sorts of tools for convex problems, while non-convex problems are still very hard to deal with?

Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time.

Now I am learning that a convex optimization problem can be NP-Hard, but that convex problems are still somehow considered easier than non-convex problems.

Can someone explain this apparent contradiction to me:

  • Is it true that a convex optimization can be NP-Hard? On one hand, based on this post and the accepted answer, yes, There are examples of convex optimization problems which are NP-hard. On the other hand, This lecture from a Stanford Professor, around 28:00 states that convexity means tractability and polynomial time algorithms.

  • If it is indeed true that convex optimization problems can be NP-Hard, then in what sense are they "easier" than non-convex problems? As far as I know, there are no levels of NP-Hardness, anything between NP-Complete and P-Space is NP-Hard. I frequently hear Operations Research people say that we have all sorts of tools for convex problems, while non-convex problems are still very hard to deal with?

Source Link
Sasha the Noob
Sasha the Noob
  • 623
  • 1
  • 7
  • 9

If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?

Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time.

Now I am learning that a convex optimization problem can be NP-Hard, but that convex problems are still somehow considered easier than non-convex problems.

Can someone explain this apparent contradiction to me:

  • Is it true that a convex optimization can be NP-Hard? On hand, based on this post and the accepted answer, yes, There are examples of convex optimization problems which are NP-hard. On the other hand, This lecture from a Stanford Professor, around 28:00 states that convexity means tractability and polynomial time algorithms.

  • If it is indeed true that convex optimization problems can be NP-Hard, then in what sense are they "easier" than non-convex problems? As far as I know, there are no levels of NP-Hardness, anything between NP-Complete and P-Space is NP-Hard. I frequently hear Operations Research people say that we have all sorts of tools for convex problems, while non-convex problems are still very hard to deal with?