I'm trying to wrap my head around an apparent paradox that I've come across while trying to learn more about optimization algorithms:
On one hand several sources state that convex optimization is easy, because every local minimum is a global minimum. In this video, starting at 27:00, Stephen Boyd from Stanford claims that convex optimization problems are tractable and in polynomial time.
Other sources state that a convex optimization problem can be NP-hard. See for example this post.
I can't wrap my head around the two statements, are convex optimization problems tractable or not?
As I try to dig deeper, one thing I noticed it that the term convex doesn't seem to be used the same way by different people when it comes to integer problems.
By some definitions, it seems that a convex integer optimization problem is impossible by definition: the very fact of constraining the variables to integer values removes the convexity of the problem, since for a problem to be convex, both the objective function and the feasible set have to be convex.
Other places seem to consider problems where if aside from the integer constraint, all other constraints and the objective function are convex, to be convex optimization problems.
Which one of the two is correct? Can an integer programming problem be convex? Or is it non-convex by definition, given the restrictions it puts on the feasible set?
If it is possible for an integer programming problem to be convex, then in what sense are convex optimization problems "easier" that non-convex problems, since both are NP-Hard?