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"?
Best Answer
If the question is "Are there non-convex global search algorithms with provably nice properties?" then the answer is "Yes, lots." The algorithms I'm familiar with use interval analysis. Here's a seminal paper from 1979: Global Optimization Using Interval Analysis. And here's a book on the topic. The requirements on the function are that it be Lipschitz or smooth to some order, and that it not have a combinatorial explosion of local optima. These techniques aren't as fast as linear or convex programming, but they're solving a harder problem, so you can't hold it against them. And from a practical point of view, for reasonable functions, they converge plenty fast.