(530d) Tuning Global Optimization Software Using Derivative-Free Optimization (DFO) Algorithms

Options can have a significant impact on the performance of optimization solvers. Tuning is often necessary in order to identify values of options that improve solver performance in terms of execution time and solution quality.  Despite extensive work in the development of optimization algorithms and software, no work has been done in tuning options for global optimization solvers. The objectives of this paper are twofold.

First, derivative-free optimization (DFO) algorithms are used to find optimal values for global optimization solver options.  Tuning solver options can be regarded as an optimization problem.  Our goal is to automatically `learn’ a configuration of options which leads to the best solver performance in terms of execution time and solution quality.  However, the relationship between options and solver performance is implicit and the performance function is not smooth.  Therefore, we treat the global optimization solver as a black-box model, whose input is values for the options and output is a performance function.  Common gradient-based optimization method cannot be used to solve this black-box optimization problem.  DFO approaches, however, are suitable choices to solve the tuning problem, since they do not require derivative information for the objective function or constraints [1].  A set of 350 instances including problems in GlobalLib and MINLPLib are studied [2].  We show that tuning options can improve the performance of the global optimization solver BARON [3].  Performance improvements are observed for each problem in this test set collection but this requires using different options for each problem.  Interestingly, we have been unable to find a single set of options that improves default BARON settings across the entire test library.

Second, a systematic comparison is made of different DFO methods in solving tuning problems.  A total of 28 state-of-the-art DFO implementations are applied to find the optimal options of BARON.  The algorithms are tested in terms of their ability to improve the performance of BARON.  For the problems we studied, the DFO methods show remarkably different ability to solve tuning problems.  Comparisons show that several DFO approaches are much better than others in terms of finding optimal options of BARON.

The main conclusion of this work is that users of global optimization software can resort to automatic machine learning techniques based on DFO solvers in order to identify optimal parameters for software options for their specific applications.

References cited

1. Rios, L. M. and Sahinidis, N. V., Derivative-free optimization: A review of algorithms and comparison of software implementations, http://thales.cheme.cmu.edu/dfo.
2. http://www.gamsworld.org/index.htm
3. Tawarmalani, M. and N. V. Sahinidis, A polyhedral branch-and-cut approach to global optimization, Mathematical Programming, Ser. B, 103, 225-249, 2005