Just got started with Boyd's Convex Optimization. It's great stuff and I see how it directly subsumes the all-important linear programming class of models. However, it seems that if a problem is non-convex, then the only recourse is some form of exhaustive search with smart stopping rules (e.g., branch and bound with fathoming).
Is convex optimization really the last line of demarcation between "easy" and "hard" optimization problems? By "last line" I mean that there does not exist a strict superset of convex problems that are also easily solved and well-behaved for a global optima.