(558g) Model-and-Search: A Derivative-Free Local Optimization Algorithm

Derivative-free optimization (DFO) is an important class of optimization algorithms that optimize 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. Thorough reviews of DFO algorithms and a comparison of DFO software appear in [1, 2]. Some well-known DFO solvers developed based on local search algorithms include BOBYQA [3], FMINSEARCH [4], IMFIL [5], NEWUOA [6], NOMAD [7] and DAKOTA/PATTERN [8].

In this work, we propose Model-and-Search (MAS), a novel local search DFO algorithm, and show it is convergent to a stationary point. The problem of interest is the optimization of a deterministic function over a box-bounded domain of interest. In MAS, the search is oriented to improve the value of the incumbent by combining a set of techniques, including gradient estimation, quadratic model building and optimization. A novel sensitivity-based approach is proposed to construct an incomplete quadratic model when points are not enough to build a complete quadratic surrogate model of the true function. The surrogate model is then used to guide the search.

We present extensive computational results on a collection of over 300 test problems from publicly available sources with varying dimensions and complexity. These results show that the proposed algorithm outperforms all other DFO local solvers.

[1] Conn, A. R., Scheinberg, K., Vicente, L. N.: Introduction to derivative-free optimization. SIAM, Philadelphia, PA (2009).

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

[3] Powell, M. J. D.: The BOBYQA Algorithm for Bound Constrained Optimization without Derivatives. Technical report, Department of Applied Mathematics and Theoretical Physics, University of Cambridge (2009).

[4] Mathworks. FMINSEARCH. https://www.mathworks.com/help/matlab/ref/fminsearch.html.

[5] Kelley, C. T.: Users Guide for IMFIL version 1.0. http://www4.ncsu.edu/ctk/imfil.html.

[6] Powell, M. J. D.: Developments of NEWUOA for minimization without derivatives. IMA Journal of Numerical Analysis, 28, 649-664 (2008).

[7] Abramson, M. A., Audet, C., Couture, G., Dennis, J. E. Jr., LeDigabel, S.: The Nomad project. http://www.gerad.ca/nomad/

[8] B. M. Adams, M. S. Ebeida, M. S. Eldred, G. Geraci, J. D. Jakeman, K. A. Maupin, J. A. Monschke, J. A. Stephens, L. P. Swiler, D. M. Vigil, T. M. Wildey, W. J. Bohnhoff, K. R. Dalbey, J. P. Eddy, J. R. Frye, R. W. Hooper, K. T. Hu, P. D. Hough, M. Khalil, E. M. Ridgway, J. G. Winokur, and A. Rushdi.: DAKOTA, A Multilevel Parallel Object-Oriented Framework for Design Optimization, Parameter Estimation, Uncertainty Quantification, and Sensitivity Analysis: Version 6.9 User's Manual. Sandia National Laboratories, Albuquerque, NM and Livermore, CA, 2018. https://dakota.sandia.gov/.