(621a) Decomposition in Derivative-Free Optimization

Derivative-free optimization (DFO) is an important class of optimization algorithms, which optimize problems based on objective and function evaluations without using the actual derivatives. 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 modeling, an abundance of legacy codes, and its application in autotuning are some of the drives which make DFO becoming an area of great demand. However, current DFO solvers have the limitation that they perform well only when the number of degrees of freedom is about a dozen or less. Decomposition is an approach to solve large-scale problems in optimization. The key idea of decomposition is to project the original problem into a series of smaller subproblems, which can be solved in parallel or in sequence. Past decomposition approaches have not succeeded in solving large-scale problems with DFO.

In this work, we propose a novel decomposition framework for DFO algorithms. Our framework significantly extends the scope of current DFO solvers to larger-scale problems. We address several key questions, including how to select variables for each subproblem, and how to determine sub-problem dimension and sub-problem function evaluation limits. A practical implementation is developed and exemplified with the global model-based solver Stable Noisy Optimization by Branch and Fit (SNOBFIT). To investigate the performance of the decomposition framework both in terms of quality of solution and efficiency, we conducted extensive computational studies on a collection of over 300 test problems with varying dimensions and complexity. Significant improvements in the quality of solutions obtained under a 2500 function evaluation limit are observed for a large fraction of the test problems. The decomposition framework wins against non-decomposition when the problem has more than 30 variables. It also achieves over 90% wins when the problem has more than 75 variables regardless of problem convexity and smoothness.