Working Paper: NBER ID: w26340
Authors: Antoine Arnoud; Fatih Guvenen; Tatjana Kleineberg
Abstract: We benchmark seven global optimization algorithms by comparing their performance on challenging multidimensional test functions as well as a method of simulated moments estimation of a panel data model of earnings dynamics. Five of the algorithms are taken from the popular NLopt open-source library: (i) Controlled Random Search with local mutation (CRS), (ii) Improved Stochastic Ranking Evolution Strategy (ISRES), (iii) Multi-Level Single-Linkage (MLSL) algorithm, (iv) Stochastic Global Optimization (StoGo), and (v) Evolutionary Strategy with Cauchy distribution (ESCH). The other two algorithms are versions of TikTak, which is a multistart global optimization algorithm used in some recent economic applications. For completeness, we add three popular local algorithms to the comparison—the Nelder-Mead downhill simplex algorithm, the Derivative-Free Non-linear Least Squares (DFNLS) algorithm, and a popular variant of the Davidon-Fletcher-Powell (DFPMIN) algorithm. To give a detailed comparison of algorithms, we use a set of benchmarking tools recently developed in the applied mathematics literature. We find that the success rate of many optimizers vary dramatically with the characteristics of each problem and the computational budget that is available. Overall, TikTak is the strongest performer on both the math test functions and the economic application. The next-best performing optimizers are StoGo and CRS for the test functions and MLSL for the economic application.
Keywords: global optimization; benchmarking; algorithm performance; economic applications
JEL Codes: C13; C15; C51; C53; C61; C63; D52; J31
Edges that are evidenced by causal inference methods are in orange, and the rest are in light blue.
| Cause | Effect |
|---|---|
| performance of different global optimization algorithms (C61) | success rates in finding global optima (C61) |
| success rates of optimizers (C61) | characteristics of the optimization problem (C61) |
| success rates of optimizers (C61) | computational budget available (C63) |
| tiktak algorithm (C69) | performance across mathematical test functions and economic applications (C01) |
| computational budget (C63) | success rate of tiktak algorithm (Y10) |
| local algorithms like Nelder-Mead and dfnls (C51) | success rates with increased computational budgets (C63) |
| simple economic optimization problems (C61) | challenges for global optimizers (C61) |