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, are generally heuristics like "ant colony optimization". Essentially all generalizable non-convex optimization algorithms I've come across are 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.

Edit: An example. A polynomial of known degree k only needs k + 1 samples to reconstruct - does this also give you the minimum within a given range for free, or do you still need to search for it manually? For any more general class of functions, does "ability to reconstruct" carry over at all to "ability to find global optima"?