×

Asynchronously parallel optimization solver for finding multiple minima. (English) Zbl 1398.65123

Summary: We propose and analyze an asynchronously parallel optimization algorithm for finding multiple, high-quality minima of nonlinear optimization problems. Our multistart algorithm considers all previously evaluated points when determining where to start or continue a local optimization run. Theoretical results show that when there are finitely many minima, the algorithm almost surely starts a finite number of local optimization runs and identifies every minimum. The algorithm is applicable to general optimization settings, but our numerical results focus on the case when derivatives are unavailable. In numerical tests, a Python implementation of the algorithm is shown to yield good approximations of many minima (including a global minimum), and this ability is shown to scale well with additional resources. Our implementation’s time to solution is shown also to scale well even when the time to perform the function evaluation is highly variable. An implementation of the algorithm is available in the libEnsemble library at https://github.com/Libensemble/libensemble.

MSC:

65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
90C56 Derivative-free methods and methods using generalized derivatives
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Audet, C; Dennis, JE; Digabel, S, Parallel space decomposition of the mesh adaptive direct search algorithm, SIAM J. Optim., 19, 1150-1170, (2008) · Zbl 1180.90363
[2] Balay, S., Abhyankar, S., Adams, M.F., Brown, J., Brune, P., Buschelman, K., Dalcin, L., Eijkhout, V., Gropp, W.D., Kaushik, D., Knepley, M.G., McInnes, L.C., Rupp, K., Smith, B.F., Zampini, S., Zhang, H.: PETSc Web page (2017). http://www.mcs.anl.gov/petsc
[3] Besserud, K., Cotten, J.: Architectural genomics, silicon + skin: biological processes and computation. In: Proceedings of the 28th Annual Conference of the Association for Computer Aided Design in Architecture, pp. 978-989 (2008)
[4] Cave, RJ; Burke, K; Castner, EW, Theoretical investigation of the ground and excited states of coumarin 151 and coumarin 120, J. Phys. Chem. A, 106, 9294-9305, (2002)
[5] Custódio, AL; Madeira, JFA, GLODS: global and local optimization using direct search, J. Glob. Optim., 62, 1-28, (2015) · Zbl 1328.90161
[6] Dalcín, L; Paz, R; Storti, M; D’Elía, J, MPI for python: performance improvements and MPI-2 extensions, J. Parallel Distrib. Comput., 68, 655-662, (2008)
[7] Easterling, DR; Watson, LT; Madigan, ML; Castle, BS; Trosset, MW, Parallel deterministic and stochastic global minimization of functions with very many minima, Comput. Optim. Appl., 57, 469-492, (2014) · Zbl 1304.90162
[8] García-Palomares, UM; Rodríguez, JF, New sequential and parallel derivative-free algorithms for unconstrained minimization, SIAM J. Optim., 13, 79-96, (2002) · Zbl 1049.90133
[9] Gaviano, M; Kvasov, DE; Lera, D; Sergeyev, YD, Algorithm 829: software for generation of classes of test functions with known local and global minima for global optimization, ACM Trans. Math. Softw., 29, 469-480, (2003) · Zbl 1068.90600
[10] Gheribi, AE; Robelin, C; Digabel, S; Audet, C; Pelton, AD, Calculating all local minima on liquidus surfaces using the factsage software and databases and the mesh adaptive direct search algorithm, J. Chem. Thermodyn., 43, 1323-1330, (2011)
[11] Gray, GA; Kolda, TG, Algorithm 856: APPSPACK 4.0: asynchronous parallel pattern search for derivative-free optimization, ACM Trans. Math. Softw., 32, 485-507, (2006) · Zbl 1230.90196
[12] Hansen, N.: CMA-ES. https://www.lri.fr/ hansen/cmaes_inmatlab.html#matlab. Accessed Nov 2016
[13] Hansen, N; Müller, SD; Koumoutsakos, P, Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES), Evol. Comput., 11, 1-18, (2003)
[14] He, J; Verstak, A; Sosonkina, M; Watson, L, Performance modeling and analysis of a massively parallel DIRECT-part 2, Int. J. High Perform. Comput. Appl., 23, 29-41, (2009)
[15] He, J; Verstak, A; Watson, L; Sosonkina, M, Performance modeling and analysis of a massively parallel DIRECT-part 1, Int. J. High Perform. Comput. Appl., 23, 14-28, (2009)
[16] He, J; Verstak, A; Watson, LT; Sosonkina, M, Design and implementation of a massively parallel version of DIRECT, Comput. Optim. Appl., 40, 217-245, (2007) · Zbl 1181.90138
[17] Hough, PD; Kolda, TG; Torczon, VJ, Asynchronous parallel pattern search for nonlinear optimization, SIAM J. Sci. Comput., 23, 134-156, (2001) · Zbl 0990.65067
[18] Johnson, S.G.: The NLopt Nonlinear-Optimization Package. http://ab-initio.mit.edu/nlopt (2017)
[19] Jones, DR; Perttunen, CD; Stuckman, BE, Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79, 157-181, (1993) · Zbl 0796.49032
[20] Larson, J.: libEnsemble. https://github.com/Libensemble/libensemble (2017)
[21] Larson, J; Wild, SM, A batch, derivative-free algorithm for finding multiple local minima, Optim. Eng., 17, 205-228, (2016) · Zbl 1364.90363
[22] Liuzzi, G; Truemper, K, Parallelized hybrid optimization methods for nonsmooth problems using NOMAD and linesearch, Comput. Appl. Math., (2017) · Zbl 1409.90190
[23] Moré, JJ; Wild, SM, Benchmarking derivative-free optimization algorithms, SIAM J. Optim., 20, 172-191, (2009) · Zbl 1187.90319
[24] Olsson, P.M.: Methods for Network Optimization and Parallel Derivative-Free Optimization, Ph.D. Thesis. Linköping University. http://liu.diva-portal.org/smash/get/diva2:695431/FULLTEXT02.pdf (2014)
[25] Plantenga, T.D.: HOPSPACK 3.0 User Manual, Technical Report October. Sandia National Laboratories, Albuquerque (2009)
[26] Powell, M.J.D.: The BOBYQA Algorithm for Bound Constrained Optimization Without Derivatives, Technical Report. DAMTP 2009/NA06, Department of Applied Mathematics and Theoretical Physics, University of Cambridge (2009)
[27] Rinnooy Kan, AHG; Timmer, GT, Stochastic global optimization methods, part I: clustering methods, Math. Program., 39, 27-56, (1987) · Zbl 0634.90066
[28] Rinnooy Kan, AHG; Timmer, GT, Stochastic global optimization methods, part II: multi level methods, Math. Program., 39, 57-78, (1987) · Zbl 0634.90067
[29] Ross, S.M.: A First Course in Probability, 8th edn. Prentice Hall, Upper Saddle River (2009)
[30] Törn, A., Zilinskas, A.: Global Optimization. Springer, New York (1989). https://doi.org/10.1007/3-540-50871-6 · Zbl 0752.90075
[31] Vanden Berghen, F.: CONDOR: A Constrained, Non-linear, Derivative-Free Parallel Optimizer for Continuous, High Computing Load, Noisy Objective Functions, Ph.D. Thesis. Université Libre de Bruxelles. http://www.applied-mathematics.net/optimization/thesis_optimization.pdf (2004)
[32] Vaz, AIF; Vicente, LN, A particle swarm pattern search method for bound constrained global optimization, J. Glob. Optim., 39, 197-219, (2007) · Zbl 1180.90252
[33] Wild, S.M.: Derivative-Free Optimization Algorithms for Computationally Expensive Functions, Ph.D. Thesis. Cornell University. http://ecommons.cornell.edu/handle/1813/11248 (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.