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?