Skip to main content
Log in

The bisection method in higher dimensions

  • Published:
Mathematical Programming Submit manuscript

Abstract

Is the familiar bisection method part of some larger scheme? The aim of this paper is to present a natural and useful generalisation of the bisection method to higher dimensions. The algorithm preserves the salient features of the bisection method: it is simple, convergence is assured and linear, and it proceeds via a sequence of brackets whose infinite intersection is the set of points desired. Brackets are unions of similar simplexes. An immediate application is to the global minimisation of a Lipschitz continuous function defined on a compact subset of Euclidean space.

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

  1. Patricio Basso, “Iterative methods for the localization of the global maximum,”SIAM Journal on Numerical Analysis 19 (1982) 781–792.

    Google Scholar 

  2. Gustave Choquet,Lectures on Analysis, Vol. 1 (Benjamin, New York, 1969).

    Google Scholar 

  3. A. Eiger, K. Sikorski and F. Stenger, “A bisection method for systems of nonlinear equations,”ACM Transactions on Mathematical Software 10 (1984) 367–377.

    Google Scholar 

  4. P. McMullen, “Space tiling zonotopes,”Mathematika 22 (1975) 202–211.

    Google Scholar 

  5. Regina Hunter Mladineo, “An algorithm for finding the global maximum of a multimodal, multivariate function,”Mathematical Programming 34 (1986) 188–200.

    Google Scholar 

  6. S.A. Piyavskii, “An algorithm for finding the absolute extremum of a function,”USSR Computational Mathematics and Mathematical Physics 12 (1972) 57–67.

    Google Scholar 

  7. J.E. Dennis Jr. and Robert B. Schnabel,Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Prentice-Hall, Englewood Cliffs, NJ, 1983).

    Google Scholar 

  8. Bruno O. Shubert, “A sequential method seeking the global maximum of a function,”SIAM Journal on Numerical Analysis 9 (1972) 379–388.

    Google Scholar 

  9. G.R. Wood, “On computing the dispersion function,”Journal of Optimization Theory and Applications 58 (1988) 331–350.

    Google Scholar 

  10. G.R. Wood, “Multidimensional bisection applied to global optimisation,”Computers and Mathematics with Applications 21 (1991) 161–172.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wood, G.R. The bisection method in higher dimensions. Mathematical Programming 55, 319–337 (1992). https://doi.org/10.1007/BF01581205

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

AMS 1980 Subject Classification

Key words

Navigation