(508c) Branch-and-Model: A Model-Based Derivative-Free Global Optimization Algorithm

Derivative-free optimization (DFO) addresses the problem of optimizing in the absence of an algebraic model.  DFO algorithms can be used to optimize over simulations and experiments, when an algebraic model is not easily available.  The subject has found renewed interest in recent time as many DFO algorithms and software have reached a level of maturity that facilitates the successful solution of many applications [1].  Unfortunately, as reported in a recent comparison of 22 DFO solvers on over 500 test problems in [1], the success of current DFO software implementations is typically limited to problems with up to 10 or 20 degrees of freedom.  Clearly, there is a strong need for advances in the DFO area.

In this paper, we address the optimization of a deterministic function  over a box-bounded domain in the absence of an algebraic model for  and its derivatives.  We assume that  can be calculated via simulation or experiment, although the cost of such a calculation may be significant.  We present a novel model-based algorithm for this problem.  This algorithm, named branch-and-model (BAM) is a DFO algorithm that builds a model around each evaluated point using available surrounding evaluated points.  The algorithm performs a dense sense and employs a local search algorithm to identify local optima.  We have proved that this algorithm converges to a global optimum of the problem.  We present extensive computational experience with the algorithm and comparisons with other DFO algorithms on a publically available collection of 500 test problems ranging from 2 variables to 30 variables [1].

[1]  Rios, L. M. and N. V. Sahinidis, Derivative-free optimization: A review of algorithms and comparison of software implementations, Journal of Global Optimization, 56, 1247-1293, 2013.