Escaping local minima with local derivative-free methods: a numerical investigation

References

• Conn AR, Scheinberg K, Vicente LN. Introduction to derivative-free optimization. Philadelphia: MPS/SIAM; 2009. (MPS-SIAM series on optimization; vol. 8).
   Google Scholar
• Locatelli M, Schoen F. Global optimization: theory, algorithms, and applications. Philadelphia: MOS/SIAM; 2013. (MOS-SIAM series on optimization; vol. 15).
   Google Scholar
• Rios LM, Sahinidis NV. Derivative-free optimization: a review of algorithms and comparison of software implementations. J Glob Optim. 2013;56:1247–1293.
   Web of Science ®Google Scholar
• Powell MJD. Developments of NEWUOA for minimization without derivatives. University of Cambridge; Cambridge, UK; 2007. DAMTP 2007/NA05.
   Google Scholar
• Cartis C, Fiala J, Marteau B, et al. Improving the flexibility and robustness of model-based derivative-free optimization solvers. ACM Trans Math Softw. 2019;45(3):1–41.
   Web of Science ®Google Scholar
• Powell MJD. The BOBYQA algorithm for bound constrained optimization without derivatives. University of Cambridge; Cambridge, UK; 2009. DAMTP 2009/NA06.
   Google Scholar
• Kolda TG, Lewis RM, Torczon V. Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev. 2003;45:385–482.
   Web of Science ®Google Scholar
• Wright MH. Direct search methods: once scorned, now respectable. In: Griffiths D, Watson G, editors. Numerical analysis 1995 (Proceedings of the 1995 Dundee Biennal Conference in Numerical Analysis); Harlow, UK; Addison-Wesley; 1996. p. 191–208.
   Google Scholar
• Powell MJD. Direct search algorithms for optimization calculations. Acta Numer. 1998;7:287–336.
   Google Scholar
• Kelley CT. Implicit filtering. Philadelphia: SIAM; 2011. (Software, environments and tools). Available from: https://epubs.siam.org/doi/book/10 .1137/1.9781611971903.
   Google Scholar
• Nocedal J, Wright SJ. Numerical optimization. 2nd ed. New York: Springer; 2006. (Springer series in operations research and financial engineering).
   Google Scholar
• Custódio AL, Scheinberg K, Vicente LN. Methodologies and software for derivative-free optimization. In: Terlaky T, Anjos MF, Ahmed S, editors. Advances and trends in optimization with engineering applications. Philadelphia: SIAM; 2017. (MOS-SIAM book series on optimization).
   Google Scholar
• Moré JJ, Wild SM. Benchmarking derivative-free optimization algorithms. SIAM J Optim. 2009;20(1):172–191.
   Web of Science ®Google Scholar
• Roberts L. Derivative-free optimisation for data fitting. University of Oxford; Oxford, UK; 2016. InFoMM CDT Report. Available from: http://people.maths.ox.ac.uk/robertsl/docs/DFO_MiniprojectReport_updateNov18.pdf
   Google Scholar
• Hansen N, Ostermeier A. Adapting arbitrary normal mutation distributions in evolution strategies: the covariance matrix adaptation. In: Proceedings of 1996 IEEE International Conference on Evolutionary Computation; Nagoya; 1996. p. 312–317.
   Google Scholar
• Hansen N, Ostermeier A. Completely derandomized self-adaptation in evolution strategies. Evol Comp. 2001;9:159–195.
   PubMed Web of Science ®Google Scholar
• Jones DR, Perttunen CD, Stuckman BE. Lipschitzian optimization without the Lipschitz constant. J Optim Theory Appl. 1993;79(1):157–181.
   Web of Science ®Google Scholar
• Ali MM, Khompatraporn C, Zabinsky ZB. A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems. J Glob Optim. 2005;31(4):635–672.
   Web of Science ®Google Scholar
• Ghanbari H, Scheinberg K. Black-box optimization in machine learning with trust region based derivative free algorithm; 2017. Preprint arXiv:170306925.
   Google Scholar
• Eriksson D, Bindel D, Shoemaker C. Surrogate optimization toolbox (pySOT); 2015. Available from: https://github.com/dme65/pySOT.
   Google Scholar
• Conn AR, Gould NIM, Toint PL. Trust-region methods. Philadelphia: MPS/SIAM; 2000. (MPS-SIAM series on optimization).
   Google Scholar
• Hare W, Loeppky J, Xie S. Methods to compare expensive stochastic optimization algorithms with random restarts. J Glob Optim. 2018;72(4):781–801. doi:https://doi.org/10.1007/s10898-018-0673-7
   Web of Science ®Google Scholar
• Rinnooy Kan AHG, Timmer GT. Stochastic global optimization methods part I: clustering methods. Math Prog. 1987;39(1):27–56.
   Web of Science ®Google Scholar
• Rinnooy Kan AHG, Timmer GT. Stochastic global optimization methods part II: multi level methods. Math Prog. 1987;39(1):57–78.
   Web of Science ®Google Scholar
• Törn A, Viitanen S. Topographical global optimization using pre-sampled points. J Glob Optim. 1994;5(3):267–276.
   Web of Science ®Google Scholar
• Ali MM, Storey C. Topographical multilevel single linkage. J Glob Optim. 1994;5(4):349–358.
   Web of Science ®Google Scholar
• Custódio AL, Madeira JFA, Vaz AIF, et al. Direct multisearch for multiobjective optimization. SIAM J Optim. 2011;21(3):1109–1140.
   Web of Science ®Google Scholar
• Audet C, Hare W. Derivative-free and blackbox optimization. . Cham (Switzerland): Springer; 2017. (Springer series in operations research and financial engineering).
   Google Scholar
• Mockus J, Tiesis V, Zilinskas A. Bayesian methods for seeking the extremum. Toward Glob Optim. 1978;2:117–129.
   Google Scholar
• Jones DR, Schonlau M, Welch WJ. Efficient global optimization of expensive black-box functions. J Glob Optim. 1998;13(4):455–492.
   Web of Science ®Google Scholar
• Brochu E, Cora VM, De Freitas N. A tutorial on Bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning; 2010. Preprint arXiv:10122599.
   Google Scholar
• Shahriari B, Swersky K, Wang Z, et al. Taking the human out of the loop: a review of Bayesian optimization. Proc IEEE. 2016;104(1):148–175.
   Web of Science ®Google Scholar
• Fowkes J. Bayesian numerical analysis: global optimization and other applications [dissertation]. Oxford University; 2011.
   Google Scholar
• The GPyOpt authors. GPyOpt: a Bayesian optimization framework in Python; 2016. Available from: http://github.com/SheffieldML/GPyOpt.
   Google Scholar
• Hutter F, Hoos HH, Leyton-Brown K. Sequential model-based optimization for general algorithm configuration. In: International Conference on Learning Intelligence Optimization; Rome; 2011. p. 507–223.
   Google Scholar
• Bergstra J, Yamins DLK, Cox DD. Making a science of model search: hyperparameter optimization in hundreds of dimensions for vision architectures. In: 30th International Conference on Machine Learning; Atlanta; 2013. p. 115–123.
   Google Scholar
• Rasmussen CE, Williams CK. Gaussian processes for machine learning. Vol. Cambridge (MA): The MIT Press; 2006. p. 715–719.
   Google Scholar
• Hutter F, Hoos HH, Stützle T. Automatic algorithm configuration based on local search. In: AAAI; Vol. 7; 2007. p. 1152–1157.
   Google Scholar
• Snoek J, Larochelle H, Adams RP. Practical Bayesian optimization of machine learning algorithms. Adv Neural Inf Process Syst. 2012;25:2951–2959.
   Google Scholar
• Li L, Jamieson K, DeSalvo G, et al. Hyperband: a novel bandit-based approach to hyperparameter optimization; 2016. Preprint arXiv:160306560.
   Google Scholar
• Gutmann HM. Radial basis function methods for global optimization [dissertation]. Cambridge University; 2001.
   Google Scholar
• Jones DR. A taxonomy of global optimization methods based on response surfaces. J Glob Optim. 2001;21(4):345–383.
   Web of Science ®Google Scholar
• Huyer W, Neumaier A. SNOBFIT: stable noisy optimization by branch and fit. ACM Trans Math Softw. 2008;35(2):1–25.
   Web of Science ®Google Scholar
• He J, Watson LT, Ramakrishnan N, et al. Dynamic data structures for a direct search algorithm. Comput Optim Appl. 2002;23(1):5–25.
   Web of Science ®Google Scholar
• He J, Verstak A, Watson LT, et al. Design and implementation of a massively parallel version of DIRECT. Comput Optim Appl. 2008;40(2):217–245.
   Web of Science ®Google Scholar
• He J, Watson LT, Sosonkina M. Algorithm 897: VTDIRECT95: serial and parallel codes for the global optimization algorithm direct. ACM Trans Math Softw. 2009;36(3):1–24.
   Web of Science ®Google Scholar
• Paulavičius R, Sergeyev YD, Kvasov DE, et al. Globally-biased Disimpl algorithm for expensive global optimization. J Glob Optim. 2014;59(2–3):545–567.
   Web of Science ®Google Scholar
• Liuzzi G, Lucidi S, Piccialli V. Exploiting derivative-free local searches in DIRECT-type algorithms for global optimization. Comput Optim Appl. 2016;65(2):449–475.
   Web of Science ®Google Scholar
• Di Pillo G, Liuzzi G, Lucidi S, et al. A DIRECT-type approach for derivative-free constrained global optimization. Comput Optim Appl. 2016;65(2):361–397.
   Web of Science ®Google Scholar
• Abramson MA, Audet C. Convergence of mesh adaptive direct search to second-order stationary points. SIAM J Optim. 2006;17(2):606–619.
   Web of Science ®Google Scholar
• Abramson MA, Audet C, Dennis JE, et al. OrthoMADS: a deterministic MADS instance with orthogonal directions. SIAM J Optim. 2009 Jan;20(2):948–966.
   Web of Science ®Google Scholar
• Audet C, Dennis JE, Le Digabel S. Globalization strategies for mesh adaptive direct search. Comput Optim Appl. 2010;46(2):193–215.
   Web of Science ®Google Scholar
• Audet C, Dennis JE. Mesh adaptive direct search algorithms for constrained optimization. SIAM J Optim. 2006;17(1):188–217. doi:https://doi.org/10.1137/040603371
   Web of Science ®Google Scholar
• Audet C, Ianni A, Le Digabel S, et al. Reducing the number of function evaluations in mesh adaptive direct search algorithms. SIAM J Optim. 2014;24(2):621–642.
   Web of Science ®Google Scholar
• Audet C, Béchard V, Digabel SL. Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search. J Glob Optim. 2008;41(2):299–318.
   Web of Science ®Google Scholar
• Audet C, Dennis JE, Digabel SL. Parallel space decomposition of the mesh adaptive direct search algorithm. SIAM J Optim. 2008;19(3):1150–1170.
   Web of Science ®Google Scholar
• Audet C, Le Digabel S, Tribes C. The mesh adaptive direct search algorithm for granular and discrete variables. SIAM J Optim. 2019;29(2):1164–1189.
   Web of Science ®Google Scholar
• Audet C, Le Digabel S, Tribes C. NOMAD user guide. Les cahiers du GERAD; 2009. G-2009-37. Available from: https://www.gerad.ca/nomad/Downloads/user_guide.pdf.
   Google Scholar
• Le Digabel S. Algorithm 909: NOMAD: nonlinear optimization with the MADS algorithm. ACM Trans Math Softw. 2011;37(4):1–15.
   Web of Science ®Google Scholar
• Abramson M, Audet C, Couture G, et al. The NOMAD project. Available from: https://www.gerad.ca/nomad.
   Google Scholar
• Lucidi S, Sciandrone M. A derivative-free algorithm for bound constrained optimization. Comput Optim Appl. 2002;21(2):119–142.
   Web of Science ®Google Scholar
• Fasano G, Liuzzi G, Lucidi S, et al. A linesearch-based derivative-free approach for nonsmooth constrained optimization. SIAM J Optim. 2014;24(3):959–992.
   Web of Science ®Google Scholar
• Liuzzi G, Lucidi S, Rinaldi F. An algorithmic framework based on primitive directions and nonmonotone line searches for black-box optimization problems with integer variables. Math Prog Comp. 2020;12:673–702.
   Web of Science ®Google Scholar
• Liuzzi G, Lucidi S, Sciandrone M. SDBOX; 2011. Available from: http://www.iasi.cnr.it/liuzzi/DFL/index.php/list3/10-local-optimization/4-sdbox.
   Google Scholar
• Hansen N. pycma; 2018. Available from: https://github.com/CMA-ES/pycma.
   Google Scholar
• Gablonsky JM. pydirect; 2012. Available from: https://code.google.com/archive/p/pydirect.
   Google Scholar
• Liuzzi G, Lucidi S, Piccialli V. DIRMIN; 2014. Available from: http://www.iasi.cnr.it/liuzzi/DFL/index.php/list3/11-global-optimization/10-dirmin.
   Google Scholar
• Bergstra J, Yamins DLK, Cox DD. Hyperopt: distributed asynchronous hyper-parameter optimization; 2018. Available from: https://github.com/hyperopt/hyperopt.
   Google Scholar
• Regis RG, Shoemaker CA. Combining radial basis function surrogates and dynamic coordinate search in high-dimensional expensive black-box optimization. Eng Optim. 2013;45(5):529–555.
   Web of Science ®Google Scholar
• Fu Z. Package snobfit; 2009. Available from: http://reflectometry.org/danse/docs/snobfit.
   Google Scholar
• Liang JJ, Qu BY, Suganthan PN, et al. Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization. Computational Intelligence Laboratory, Zhengzhou University; 2013. (Technical Report 201212).
   Google Scholar
• Locatelli M. A note on the Griewank test function. J Glob Optim. 2003;25(2):169–174.
   Web of Science ®Google Scholar
• Cartis C, Roberts L. A derivative-free Gauss-Newton method. Math Prog Comp. 2019;11(4):631–674. doi:https://doi.org/10.1007/s12532-019-00161-7
   Web of Science ®Google Scholar