Skip to main content
SpringerLink
Log in

Efficient domain partitioning algorithms for global optimization of rational and Lipschitz continuous functions

  • Contributed Papers
  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

A domain partitioning algorithm for minimizing or maximizing a Lipschitz continuous function is enhanced to yield two new, more efficient algorithms. The use of interval arithmetic in the case of rational functions and the estimates of Lipschitz constants valid in subsets of the domain in the case of others and the addition of local optimization have resulted in an algorithm which, in tests on standard functions, performs well.

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

Similar content being viewed by others

References

  1. Fisher, R. A.,The Design of Experiments, 1st Edition, Oliver and Boyd, Edinburgh, Scotland, 1935.

    Google Scholar 

  2. Brooks, S. H.,A Discussion of Random Methods for Seeking Maxima. Operations Research, Vol. 6, pp. 244–251, 1958.

    Google Scholar 

  3. Rudin, W.,Principles of Mathematical Analysis, McGraw-Hill, New York, New York, 1964.

    Google Scholar 

  4. Evtushenko, Yu. G.,Numerical Methods for Finding Global Extrema: Case of Nonuniform Mesh, USSR Computational Mathematics and Mathematical Physics, Vol. 11, pp. 1390–1403, 1971.

    Google Scholar 

  5. Shubert, B. O.,A Sequential Method for Seeking the Global Maximum of a Function, SIAM Journal on Numerical Analysis, Vol. 9, pp. 379–388, 1972.

    Google Scholar 

  6. Piyavskii, S. A.,An Algorithm for Finding the Absolute Extremum of a Function, USSR Computational Mathematics and Mathematical Physics, Vol 12, pp. 888–896, 1972.

    Google Scholar 

  7. Mayne, D. Q., andPolak, E.,Outer Approximation Algorithm for Non-differentiable Optimization Problems, Vol. 42, pp. 19–30, 1984.

    Google Scholar 

  8. Meewella, C. C., andMayne, D. Q.,An Algorithm for Global Optimization of Lipschitz Continuous Functions, Journal of Optimization Theory and Applications, Vol. 57, pp. 307–322, 1988.

    Google Scholar 

  9. Pinter, J.,Extended Univariate Algorithm for n-Dimensional Global Optimization, Computing, Vol. 36, pp. 91–103, 1986.

    Google Scholar 

  10. Hansen, E. R.,Global Optimization Using Interval Analysis: The Multi-Dimensional Case, Numerische Mathematik, Vol. 34, pp. 247–270, 1980.

    Google Scholar 

  11. Dixon, L. C. W., andSzego, G. P., Editors,Toward Global Optimization, North-Holland, Amsterdam, Holland, 1975.

    Google Scholar 

  12. Dixon, L. C. W., andSzego, G. P., Editors,Toward Global Optimization 2, North-Holland, Amsterdam, Holland, 1978.

    Google Scholar 

  13. Timmer, G. Th.,Global Optimization: A Stochastic Approach, Erasmus University, PhD Thesis, 1984.

  14. Bremmerman, H.,A Method of Unconstrained Global Optimization, Mathematical Biosciences, Vol. 9, pp. 1–15, 1970.

    Google Scholar 

  15. Price, W. L.,Global Optimization by Controlled Random Search, Journal of Optimization Theory and Applications, Vol. 40, pp. 333–348, 1983.

    Google Scholar 

  16. Torn, A. A.,A Search Clustering Approach to Global Optimization, Toward Global Optimization 2, Edited by L. C. W. Dixon and G. P. Szego, North-Holland, Amsterdam, Holland, 1978.

    Google Scholar 

  17. DeBiase, L., andFrontini, F.,A Stochastic Method for Global Optimization: Its Structure and Numerical Performance, Toward Global Optimization 2, Edited by L. C. W. Dixon and G. P. Szego, North-Holland, Amsterdam, Holland, 1978.

    Google Scholar 

  18. Moore, R. E.,Interval Analysis, Prentice-Hall, Englewood Cliffs, New Jersey, 1965.

    Google Scholar 

  19. Walster, G. W., Hansen, E. R., andSengupta, S.,Test Results for A Global Optimization Algorithm, Proceedings of the SIAM Conference on Numerical Optimization, Boulder, Colorado, Edited by P. T. Boggs, pp. 271–287, 1984.

  20. Goldstein, A. A., andPrice, J. F.,On Descent from Local Minima, Mathematics of Computation, Vol. 25, pp. 569–574, 1971.

    Google Scholar 

  21. Branin, F. H., Jr.,Widely Convergent Method for Finding Multiple Solutions of Simultaneous Nonlinear Equations, IBM Journal of Research and Development, Vol. 16, pp. 504–522, 1972.

    Google Scholar 

  22. Hartman, J. K.,Some Experiments in Global Optimization, Naval Research Logistics Quarterly, Vol. 20, pp. 569–576, 1973.

    Google Scholar 

  23. Branin, F. H., andHoo, S. K.,A Method for Finding Multiple Extrema of a Function of n Variables, Numerical Methods of Nonlinear Optimization, Edited by F. A. Lootsma, Academic Press, London, England, 1972.

    Google Scholar 

  24. Price, W. L.,A Controlled Random Search Procedure for Global Optimization, Toward Global Optimization 2, Edited by L. C. W. Dixon and G. P. Szego, North-Holland, Amsterdam, Holland, 1978.

    Google Scholar 

  25. Schwefel, H,Numerical Optimization of Computer Models, John Wiley and Sons, New York, New York, 1981.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical Engineering, Imperial College of Science and Technology, London, England

    C. C. Meewella (Research Assistant) & D. Q. Mayne (Professor)

Authors
  1. C. C. Meewella
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. D. Q. Mayne
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Meewella, C.C., Mayne, D.Q. Efficient domain partitioning algorithms for global optimization of rational and Lipschitz continuous functions. J Optim Theory Appl 61, 247–270 (1989). https://doi.org/10.1007/BF00962799

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00962799

Key Words

Search

Navigation