(624a) Branch-and-Model: A Derivative-Free Global Optimization Algorithm

Derivative-free optimization (DFO) is an important class of optimization algorithms that solve problems based on objective and function evaluations. DFO methods have enormous practical potential to address problems where derivatives are unavailable, unreliable, or only available at a significant cost. Increasing complexity in mathematical software, an abundance of legacy codes, and applications in auto-tuning are some of the drivers that put DFO algorithms in high demand. DFO algorithms can be classified as local search algorithms and global search algorithms.

In this work, we present a novel derivative-free global algorithm Branch-and-Model (BAM). The BAM algorithm utilizes a flexible partition scheme and model-based search techniques, which exploit the local trend and speed up the convergence in solution refinement. The BAM algorithm is guaranteed to converge to the globally optimal function value under mild assumptions. Extensive computational experiments over 500 publicly open-source test problems show that BAM outperforms state-of-the-art DFO algorithms, especially for higher-dimension problems.