Skip to main content
Log in

Global Optimization by Multilevel Coordinate Search

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

Abstract

Inspired by a method by Jones et al. (1993), we present a global optimization algorithm based on multilevel coordinate search. It is guaranteed to converge if the function is continuous in the neighborhood of a global minimizer. By starting a local search from certain good points, an improved convergence result is obtained. We discuss implementation details and give some numerical results.

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

Access this article

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Bélisle, C.J.P., Romeijn, H.E. and Smith, R.L. (1990), Hide-and-Seek: a Simulated Annealing Algorithm for Global Optimization, Technical Report 90-25, Department of Industrial and Operations Engineering, University of Michigan.

  • Boender, C.G.E., Rinnoy Kan, A.H.G., Stougie, L. and Timmer, G.T. (1982), A Stochastic Method for Global Optimization, Mathematical Programming 22, 125-140.

    Google Scholar 

  • Boender, C.G.E. and Romeijn, H.E. (1995), Stochastic Methods, in Horst, R. and Pardalos, P.M. (eds.), Handbook of Global Optimization, Kluwer, Dordrecht, 829-869.

  • Brent, R.P. (1973), Algorithms for Minimization without Derivatives, Prentice-Hall, Englewood Cliffs, N.J.

    Google Scholar 

  • Csendes, T. and Ratz, D. (1997), Subdivision Direction Selection in Interval Methods for Global Optimization, SIAM Journal on Numerical Analysis 34, 922-938.

    Google Scholar 

  • Dixon, L.C.W. and Szegö, G.P. (1978), The Global Optimization Problem: an Introduction, in Dixon, L.C.W. and Szegö, G.P. (eds.), Towards Global Optimisation 2, North-Holland, Amsterdam, 1-15.

  • Elster, C. and Neumaier, A. (1995), A Grid Algorithm for Bound Constrained Optimization of Noisy Functions,IMA Journal of Numerical Analysis 15, 585-608.

    Google Scholar 

  • Goertzel, B. (1992), Global Optimization by Multilevel Search, Journal of Optimization Theory and Applications 75, 423-432.

    Google Scholar 

  • Hansen, E.R. (1992), Global Optimization Using Interval Analysis, Dekker, New York.

    Google Scholar 

  • Horst, R. and Tuy, H. (1996), Global Optimization. Deterministic Approaches, (3rd ed.), Springer, Berlin.

  • Ingber, L. (1989), Very Fast Simulated Re-Annealing, Mathematical and Computer Modelling 12, 967-973.

    Google Scholar 

  • Ingber, L. (1996), Adaptive Simulated Annealing (ASA): Lessons Learned, Control and Cybernetics 25, 33-54.

    Google Scholar 

  • Jones, D.R., Perttunen, C.D. and Stuckman, B.E. (1993), Lipschitzian Optimization without the Lipschitz Constant, Journal of Optimization Theory and Applications 79, 157-181.

    Google Scholar 

  • Kostrowicki, J. and Piela, L. (1991), Diffusion Equation Method of Global Minimization: Performance on Standard Test Functions, Journal of Optimization Theory and Applications 69, 269-284.

    Google Scholar 

  • Michalewicz, Z. (1996), Genetic Algorithms + Data Structures = Evolution Programs, 3rd ed., Springer, Berlin.

  • Migdalas, A., Pardalos, P.M. and Värbrand, P. (1998), Multilevel Optimization: Algorithms and Applications, Kluwer, Dordrecht.

    Google Scholar 

  • Nemhauser, G.L. and Wolsey, L.A. (1988), Integer and Combinatorial Optimization, Wiley, New York.

    Google Scholar 

  • Perttunen, C.D. (1990), Global Optimization Using Nonparametric Statistics, PhD Thesis, University of Louisville.

  • Perttunen, C.D. and Stuckman, B.E. (1990), The Rank Transformation Applied to a Multiunivariate Method of Global Optimization, IEEE Transactions on Systems, Man, and Cybernetics 20, 1216-1220.

    Google Scholar 

  • Pintér, J.D. (1996), Global Optimization in Action, Kluwer, Dordrecht.

    Google Scholar 

  • Pintér, J.D. (1996), Continuous Global Optimization Software: a Brief Review, Optima 52, 1-8.

    Google Scholar 

  • Powell, M.J.D. (1964), An Efficient Method for Finding the Minimum of a Function of Several Variables without Calculating Derivatives, Computer Journal 7, 155-162.

    Google Scholar 

  • Press, W.H., Teukolsky, S.A., Vetterling, W.T. and Flannery, B.P. (1992), Numerical Recipes in C, (2nd ed.), Cambridge University Press, Cambridge.

    Google Scholar 

  • Ratz, D. and Csendes, T. (1995), On the Selection of Subdivision Directions in Interval Branch-and-Bound Methods for Global Optimization, Journal of Global Optimization 7, 183-207.

    Google Scholar 

  • Snyman, J.A. and Fatti, L.P. (1987), A Multi-Start Global Minimization Algorithm with Dynamic Search Trajectories, Journal of Optimization Theory and Applications 54, 121-141.

    Google Scholar 

  • Storn, R. and Price, K. (1996),Minimizing the Real Functions of the ICEC'96 Contest by Differential Evolution, in Proceedings of the 1996 IEEE Conference on Evolutionary Computation, IEEE Press, N.J., 842-844.

    Google Scholar 

  • Storn, R. and Price, K. (1997), Differential Evolution-a Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, Journal of Global Optimization 11, 341-359.

    Google Scholar 

  • Vavasis, S.A. (1995), Complexity Issues in Global Optimization: a Survey, in Horst, R. and Pardalos, P.M. (eds.), Handbook of Global Optimization, Kluwer, Dordrecht, 27-41.

    Google Scholar 

  • Vicente, L.N. and Calamai, P.H. (1994), Bilevel and Multilevel Programming: a Bibliography Review, Journal of Global Optimization 5, 291-306.

    Google Scholar 

  • Yao, Y. (1989), Dynamic Tunneling Algorithm for Global Optimization, IEEE Transactions on Systems, Man, and Cybernetics 19, 1222-1230.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Huyer, W., Neumaier, A. Global Optimization by Multilevel Coordinate Search. Journal of Global Optimization 14, 331–355 (1999). https://doi.org/10.1023/A:1008382309369

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1008382309369

Navigation