Direct-search methods in the year 2025: Theoretical guarantees and algorithmic paradigms

What the paper says

Optimizing a function without using derivatives is a challenging paradigm, that precludes from using classical algorithms from nonlinear optimization, and may thus seem intractable other than by using heuristics. Nevertheless, the field of derivative-free optimization has succeeded in producing algorithms that do not rely on derivatives and yet are endowed with convergence guarantees. One class of such methods, called direct-search methods, is particularly popular thanks to its simplicity of implementation, even though its theoretical underpinnings are not always easy to grasp. In this work, we survey contemporary direct-search algorithms from a theoretical viewpoint, with the aim of highlighting the key theoretical features of these methods. We provide a basic introduction to the main classes of direct-search methods, including line-search techniques that have received little attention in earlier surveys. We also put a particular emphasis on probabilistic direct-search techniques and their application to noisy problems, a topic that has undergone significant algorithmic development in recent years. Finally, we complement existing surveys by reviewing the main theoretical advances for solving constrained and multiobjective optimization using direct-search algorithms. • In this work, we survey contemporary direct-search algorithms from a theoretical viewpoint, with the aim of highlighting the key theoretical features of these methods. Our study goes beyond the classical, textbook cases and tackles the presence of nonsmoothness, noise, and constraints in the problem at hand. In addition to reviewing classical results in the field, we provide new perspectives on existing results, as well as novel proofs that illustrate the versatility of direct-search schemes.