Optimization by Direct Search: New Perspectives on Some Classical and Modern Methods

TLDR

Direct search methods, introduced in the 1960s as derivative‑free unconstrained optimizers, fell out of favor in the 1970s due to limited analysis but have recently resurged thanks to new mathematical foundations and advances in parallel computing. This review surveys the historical development of direct search techniques and examines the problem classes for which they excel, then proposes a unifying framework for a broad class of methods that yields convergence guarantees. The framework extends naturally to handle bound, linear, and nonlinear constraints by generalizing the underlying principles of direct search.

Abstract

Direct search methods are best known as unconstrained optimization techniques that do not explicitly use derivatives. Direct search methods were formally proposed and widely applied in the 1960s but fell out of favor with the mathematical optimization community by the early 1970s because they lacked coherent mathematical analysis. Nonetheless, users remained loyal to these methods, most of which were easy to program, some of which were reliable. In the past fifteen years, these methods have seen a revival due, in part, to the appearance of mathematical analysis, as well as to interest in parallel and distributed computing. This review begins by briefly summarizing the history of direct search methods and considering the special properties of problems for which they are well suited. Our focus then turns to a broad class of methods for which we provide a unifying framework that lends itself to a variety of convergence results. The underlying principles allow generalization to handle bound constraints and linear constraints. We also discuss extensions to problems with nonlinear constraints.