×

zbMATH — the first resource for mathematics

GLODS: global and local optimization using direct search. (English) Zbl 1328.90161
Summary: Locating and identifying points as global minimizers is, in general, a hard and time-consuming task. Difficulties increase in the impossibility of using the derivatives of the functions defining the problem. In this work, we propose a new class of methods suited for global derivative-free constrained optimization. Using direct search of directional type, the algorithm alternates between a search step, where potentially good regions are located, and a poll step where the previously located promising regions are explored. This exploitation is made through the launching of several instances of directional direct searches, one in each of the regions of interest. Differently from a simple multistart strategy, direct searches will merge when sufficiently close. The goal is to end with as many direct searches as the number of local minimizers, which would easily allow locating the global extreme value. We describe the algorithmic structure considered, present the corresponding convergence analysis and report numerical results, showing that the proposed method is competitive with currently commonly used global derivative-free optimization solvers.

MSC:
90C56 Derivative-free methods and methods using generalized derivatives
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ali, MM; Khompatraporn, C; Zabinsky, ZB, A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems, J. Glob. Optim., 31, 635-672, (2005) · Zbl 1093.90028
[2] Andricioaei, I; Straub, JE, Global optimization using bad derivatives: derivative-free method for molecular energy minimization, J. Comput. Chem., 19, 1445-1455, (1998)
[3] Audet, C; Béchard, V; Digabel, S, Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search, J. Glob. Optim., 41, 299-318, (2008) · Zbl 1157.90535
[4] Audet, C; Dennis, JE, Analysis of generalized pattern searches, SIAM J. Optim., 13, 889-903, (2003) · Zbl 1053.90118
[5] Audet, C; Dennis, JE, A pattern search filter method for nonlinear programming without derivatives, SIAM J. Optim., 14, 980-1010, (2004) · Zbl 1073.90066
[6] Audet, C; Dennis, JE, Mesh adaptive direct search algorithms for constrained optimization, SIAM J. Optim., 17, 188-217, (2006) · Zbl 1112.90078
[7] Audet, C; Dennis, JE, A progressive barrier for derivative-free nonlinear programming, SIAM J. Optim., 20, 445-472, (2009) · Zbl 1187.90266
[8] Brachetti, P; Ciccoli, MF; Pillo, G; Lucidi, S, A new version of the price’s algorithm for global optimization, J. Glob. Optim., 10, 165-184, (1997) · Zbl 0877.65038
[9] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983). Reissued by SIAM, Philadelphia (1990) · Zbl 0582.49001
[10] Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. MPS-SIAM Series on Optimization. SIAM, Philadelphia (2009) · Zbl 1163.49001
[11] Davis, C, Theory of positive linear dependence, Am. J. Math., 76, 733-746, (1954) · Zbl 0058.25201
[12] Finkel, D.E.: DIRECT Optimization Algorithm User Guide (2003). http://www4.ncsu.edu/definkel/research/index.html
[13] Gao, W; Mi, C, Hybrid vehicle design using global optimisation algorithms, Int. J. Electric Hybrid Veh., 1, 57-70, (2007)
[14] Hedar, A-R; Fukushima, M, Hybrid simulated annealing and direct search method for nonlinear unconstrained global optimization, Optim. Methods Softw., 17, 891-912, (2002) · Zbl 1065.90081
[15] Hedar, A-R; Fukushima, M, Tabu search directed by direct search methods for nonlinear global optimization, Eur. J. Oper. Res., 170, 329-349, (2006) · Zbl 1093.90091
[16] Huyer, W; Neumaier, A, Global optimization by multilevel coordinate search, J. Glob. Optim., 14, 331-355, (1999) · Zbl 0956.90045
[17] Huyer, W; Neumaier, A, SNOBFIT—stable noisy optimization by branch and fit, ACM Trans. Math. Softw., 35, 9:1-9:25, (2008)
[18] Jahn, J.: Introduction to the Theory of Nonlinear Optimization. Springer, Berlin (1996) · Zbl 0855.49001
[19] Jones, D; Perttunen, C; Stuckman, B, Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79, 157-181, (1993) · Zbl 0796.49032
[20] Kan, AHGR; Timmer, GT, Stochastic global optimization methods—part I: clustering methods, Math. Program., 39, 27-56, (1987) · Zbl 0634.90066
[21] Kan, A.H.G.R., Timmer, G.T.: Stochastic global optimization methods—Part II: Multi level methods. Math. Program. 39, 57-78 (1987) · Zbl 0634.90067
[22] Kocis, L; Whiten, WJ, Computational investigations of low-discrepancy sequences, ACM Trans. Math. Softw., 23, 266-294, (1997) · Zbl 0887.65031
[23] Kolda, TG; Lewis, RM; Torczon, V, Optimization by direct search: new perspectives on some classical and modern methods, SIAM Rev., 45, 385-482, (2003) · Zbl 1059.90146
[24] Lee, D; Kim, J-W; Lee, C-G; Jung, S-Y, Variable mesh adaptive direct search algorithm applied for optimal design of electric machines based on FEA, IEEE Trans. Magn., 47, 3232-3235, (2011)
[25] Leonetti, M; Kormushev, P; Sagratella, S, Combining local and global direct derivative-free optimization for reinforcement learning, Cybern. Inf. Technol., 12, 53-65, (2012)
[26] Locatelli, M, Relaxing the assumptions of the multilevel single linkage algorithm, J. Glob. Optim., 13, 25-42, (1998) · Zbl 0908.90238
[27] McKay, MD; Beckman, RJ; Conover, WJ, A comparison of three methods for selecting values of input variables in the analysis of output from a computer code, Technometrics, 21, 239-245, (1979) · Zbl 0415.62011
[28] Moré, J.J., Wild, S.M.: Benchmarking derivative-free optimization algorithms. SIAM J. Optim. 20, 172-191 (2009). http://www.mcs.anl.gov/ more/dfo · Zbl 1187.90319
[29] Morgans, R.C., Howard, C.Q., Zander, A.C., Hansen, C.H., Murphy, D.J.: Derivative free optimisation in engineering and acoustics. In: 14th International Congress on Sound & Vibration, pp. 1-8 (2007)
[30] Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, Berlin (2006) · Zbl 1104.65059
[31] Palomares, U.M.G.: Searching for multiple minima of bound constrained optimization problems using derivative free optimization techniques. In: Proceedings of the Eleventh International Conference on Computational Structures Technology, Paper 63 (2012)
[32] Palomares, UMG; Gonzalez-Castaño, FJ; Burguillo-Rial, JC, A combined global & local search (CGLS) approach to global optimization, J. Glob. Optim., 34, 409-426, (2006) · Zbl 1149.90426
[33] Peri, D., Fasano, G., Dessi, D., Campana, E.F.: Global optimization algorithms in multidisciplinary design optimization. In: 2th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference, pp. 1-12 (2008)
[34] Regis, RG; Shoemaker, CA, A quasi-multistart framework for global optimization of expensive functions using response surface models, J. Glob. Optim., 56, 1719-1753, (2013) · Zbl 1275.90068
[35] Santner, T.J., Williams, B.J., Notz, W.I.: The Design and Analysis of Computer Experiments. Springer, New York (2003) · Zbl 1041.62068
[36] Storn, R; Price, K, Differential evolution A simple and efficient heuristic for global optimization over continuous spaces, J. Glob. Optim., 11, 341-359, (1997) · Zbl 0888.90135
[37] Torczon, V, On the convergence of pattern search algorithms, SIAM J. Optim., 7, 1-25, (1997) · Zbl 0884.65053
[38] Vaz, A.I.F., Vicente, L.N.: A particle swarm pattern search method for bound constrained global optimization. J. Glob. Optim. 39, 197-219 (2007) · Zbl 1180.90252
[39] Vicente, LN; Custódio, AL, Analysis of direct searches for discontinuous functions, Math. Program., 133, 299-325, (2012) · Zbl 1245.90127
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.