Skip to main content
SpringerLink
Log in

GLODS: Global and Local Optimization using Direct Search

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Ali, M.M., Khompatraporn, C., Zabinsky, Z.B.: A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems. J. Glob. Optim. 31, 635–672 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  2. Andricioaei, I., Straub, J.E.: Global optimization using bad derivatives: derivative-free method for molecular energy minimization. J. Comput. Chem. 19, 1445–1455 (1998)

    Article  Google Scholar 

  3. Audet, C., Béchard, V., Le Digabel, S.: Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search. J. Glob. Optim. 41, 299–318 (2008)

    Article  MATH  Google Scholar 

  4. Audet, C., Dennis Jr, J.E.: Analysis of generalized pattern searches. SIAM J. Optim. 13, 889–903 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  5. Audet, C., Dennis Jr, J.E.: A pattern search filter method for nonlinear programming without derivatives. SIAM J. Optim. 14, 980–1010 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  6. Audet, C., Dennis Jr, J.E.: Mesh adaptive direct search algorithms for constrained optimization. SIAM J. Optim. 17, 188–217 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  7. Audet, C., Dennis Jr, J.E.: A progressive barrier for derivative-free nonlinear programming. SIAM J. Optim. 20, 445–472 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  8. Brachetti, P., Ciccoli, M.F., Di Pillo, G., Lucidi, S.: A new version of the Price’s algorithm for global optimization. J. Glob. Optim. 10, 165–184 (1997)

    Article  MATH  Google Scholar 

  9. Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983). Reissued by SIAM, Philadelphia (1990)

  10. Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. MPS-SIAM Series on Optimization. SIAM, Philadelphia (2009)

    Book  MATH  Google Scholar 

  11. Davis, C.: Theory of positive linear dependence. Am. J. Math. 76, 733–746 (1954)

    Article  MATH  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  16. Huyer, W., Neumaier, A.: Global optimization by multilevel coordinate search. J. Glob. Optim. 14, 331–355 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  17. Huyer, W., Neumaier, A.: SNOBFIT—stable noisy optimization by branch and fit. ACM Trans. Math. Softw. 35, 9:1–9:25 (2008)

    Article  MathSciNet  Google Scholar 

  18. Jahn, J.: Introduction to the Theory of Nonlinear Optimization. Springer, Berlin (1996)

    Book  MATH  Google Scholar 

  19. Jones, D., Perttunen, C., Stuckman, B.: Lipschitzian optimization without the Lipschitz constant. J. Optim. Theory Appl. 79, 157–181 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  20. Kan, A.H.G.R., Timmer, G.T.: Stochastic global optimization methods—Part I: clustering methods. Math. Program. 39, 27–56 (1987)

    Article  MATH  Google Scholar 

  21. Kan, A.H.G.R., Timmer, G.T.: Stochastic global optimization methods—Part II: Multi level methods. Math. Program. 39, 57–78 (1987)

  22. Kocis, L., Whiten, W.J.: Computational investigations of low-discrepancy sequences. ACM Trans. Math. Softw. 23, 266–294 (1997)

    Article  MATH  Google Scholar 

  23. Kolda, T.G., Lewis, R.M., Torczon, V.: Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev. 45, 385–482 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Google Scholar 

  26. Locatelli, M.: Relaxing the assumptions of the multilevel single linkage algorithm. J. Glob. Optim. 13, 25–42 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  27. McKay, M.D., Beckman, R.J., Conover, W.J.: 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)

    MATH  MathSciNet  Google Scholar 

  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

  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)

    MATH  Google Scholar 

  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, U.M.G., Gonzalez-Castaño, F.J., Burguillo-Rial, J.C.: A combined global & local search (CGLS) approach to global optimization. J. Glob. Optim. 34, 409–426 (2006)

    Article  MATH  Google Scholar 

  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, R.G., Shoemaker, C.A.: A quasi-multistart framework for global optimization of expensive functions using response surface models. J. Glob. Optim. 56, 1719–1753 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  35. Santner, T.J., Williams, B.J., Notz, W.I.: The Design and Analysis of Computer Experiments. Springer, New York (2003)

    Book  MATH  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  37. Torczon, V.: On the convergence of pattern search algorithms. SIAM J. Optim. 7, 1–25 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  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)

  39. Vicente, L.N., Custódio, A.L.: Analysis of direct searches for discontinuous functions. Math. Program. 133, 299–325 (2012)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, FCT-UNL-CMA, Quinta da Torre, 2829-516 , Caparica, Portugal

    A. L. Custódio

  2. IDMEC, Instituto Superior Técnico, Universidade de Lisboa, Av. Rovisco Pais, 1040-001 , Lisbon, Portugal

    J. F. A. Madeira

  3. Department of Mathematics, ISEL, Rua Conselheiro Emídio Navarro, 1, 1959-007 , Lisbon, Portugal

    J. F. A. Madeira

Authors
  1. A. L. Custódio
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. F. A. Madeira
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to A. L. Custódio.

Additional information

A. L. Custódio: Support for this author was provided by Fundação para a Ciência e a Tecnologia (Portuguese Foundation for Science and Technology) under the project PEst-OE/MAT/UI0297/2014 (CMA) and the grant PTDC/MAT/116736/2010.

J. F. A. Madeira: Support for this author was provided by ISEL, IPL, Lisboa, Portugal and LAETA, IDMEC, Instituto Superior Técnico, Universidade de Lisboa, Lisboa, Portugal.

Appendix: Detailed numerical results

Appendix: Detailed numerical results

See Tables 7, 8, 9, and 10.

Table 7 Numerical results for MCS, DIRECT, and three variants of GLODS (first part)
Full size table
Table 8 Numerical results for MCS, DIRECT, and three variants of GLODS (second part)
Full size table
Table 9 Numerical results for MCS, DIRECT, and three variants of GLODS (third part)
Full size table
Table 10 Numerical results for MCS, DIRECT, and three variants of GLODS (fourth part)
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Custódio, A.L., Madeira, J.F.A. GLODS: Global and Local Optimization using Direct Search. J Glob Optim 62, 1–28 (2015). https://doi.org/10.1007/s10898-014-0224-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-014-0224-9

Keywords

Mathematics Subject Classification

Search

Navigation