The DIRECT algorithm: 25 years Later
- PDF / 3,852,928 Bytes
- 46 Pages / 439.37 x 666.142 pts Page_size
- 30 Downloads / 209 Views
The DIRECT algorithm: 25 years Later Donald R. Jones1
· Joaquim R. R. A. Martins1
Received: 13 September 2019 / Accepted: 20 September 2020 © The Author(s) 2020
Abstract Introduced in 1993, the DIRECT global optimization algorithm provided a fresh approach to minimizing a black-box function subject to lower and upper bounds on the variables. In contrast to the plethora of nature-inspired heuristics, DIRECT was deterministic and had only one hyperparameter (the desired accuracy). Moreover, the algorithm was simple, easy to implement, and usually performed well on low-dimensional problems (up to six variables). Most importantly, DIRECT balanced local and global search (exploitation vs. exploration) in a unique way: in each iteration, several points were sampled, some for global and some for local search. This approach eliminated the need for “tuning parameters” that set the balance between local and global search. However, the very same features that made DIRECT simple and conceptually attractive also created weaknesses. For example, it was commonly observed that, while DIRECT is often fast to find the basin of the global optimum, it can be slow to fine-tune the solution to high accuracy. In this paper, we identify several such weaknesses and survey the work of various researchers to extend DIRECT so that it performs better. All of the extensions show substantial improvement over DIRECT on various test functions. An outstanding challenge is to improve performance robustly across problems of different degrees of difficulty, ranging from simple (unimodal, few variables) to very hard (multimodal, sharply peaked, many variables). Opportunities for further improvement may lie in combining the best features of the different extensions. Keywords DIRECT · Global optimization · Lipschitzian optimization · Black-box · Derivative-free · Exploitation versus exploration
1 Introduction When it was published a little over 25 years ago, the DIRECT global optimization algorithm offered a new approach to minimizing a black-box objective function subject to lower and upper bounds on the variables [30]. Unlike genetic algorithms, simulated annealing, and other global optimization heuristics inspired by nature, DIRECT was motivated by Lipschitzian global optimization [22,54,55,67]—a rigorous and deterministic optimization method based on branch-and-bound, where bounds are computed based on knowledge of a Lipschitz con-
B 1
Donald R. Jones [email protected] Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI, USA
123
Journal of Global Optimization
stant for the objective function (an upper bound on the rate of change). DIRECT introduced modifications to the Lipschitzian approach that made it more tractable in higher dimensions and eliminated the need to know the Lipschitz constant. The result was an algorithm that was truly black-box, simple, deterministic, and had only one hyperparameter (the desired accuracy). On the low-dimensional (2 to 6 variable) test problems used in the original paper, DIRECT perfor
Data Loading...
