Suppose that $f: \mathbb{R}^n \to \mathbb{R}$ is a continuous function for which we want to minimize. We may arbitrarily impose good conditions for $f$, such as Lipschitzness, smoothness, convexity, etc.


The intuitive way, if you were to teach about minimizing such a function in a first-course on optimization, would be **search**, rather than things like gradient descent because that takes a bit more work to motivate the concept of a gradient, etc.


Does there exist results that either show that no "search algorithm" can be competitive with optimization routine (particularly those that are gradient based), or that search algorithms are suboptimal as compared to gradient based algorithms, or that there exist search algorithms such that for some classes of problem it is better than any gradient based method, or perhaps they are equivalent in some sense.


By search algorithm, I refer to that class of algorithms where you either randomly or deterministic test points in some regions until exhaustion. One example is bisection methods for 1D functions, but I am thinking more generically.



Are there search algorithms that are competitive against (gradient based) optimization routines for continuous problems?
Yes, this can be shown. What is needed is a fair ground for comparison of different algorithms and I can recommend the book "Introductory Lectures on Convex Optimization - A Basic Course" by Yurii Nesterov. There you'll find a hands-on introduction to complexity theory for continuous problems.


(A side note: Gradient descent is inherently a search method. The gradient just tells you in which direction to look...)


