Convex Optimization is a mathematically rigorous and well-studied field. In linear programming a whole host of tractable methods give your global optimums in lightning fast times. Quadratic programming is almost as easy, and there's a good deal of semi-definite, second-order cone and even integer programming methods that can do quite well on a lot of problems.

Non-convex optimization (and particularly weird formulations of certain integer programming and combinatorial optimization problems), however, uses algorithms with names like "ants", "bees", and "bat" search, and no these aren't clever acronyms. Essentially all generalizable non-convex optimization algorithms I've come across are just some (often clever, but still) combination of gradient descent and genetic algorithms.

I can understand why this is - in non-convex surfaces local information is a lot less useful - but I would figure that there would at least be an algorithm that provably learns for a broad class of functions whether local features indicate a nearby global optimum or not. Also, perhaps, general theories of whether and how you can project a non-convex surface into higher dimensions to make it convex or almost convex.