Skip to main content
SpringerLink
Log in

Pure adaptive search for finite global optimization

  • Published:
Mathematical Programming Submit manuscript

Abstract

Pure Adaptive Search is a stochastic algorithm which has been analyzed for continuous global optimization. When a uniform distribution is used in PAS, it has been shown to have complexity which is linear in dimension. We define strong and weak variations of PAS in the setting of finite global optimization and prove analogous results. In particular, for then-dimensional lattice {1,⋯,k}n, the expected number of iterations to find the global optimum is linear inn. Many discrete combinatorial optimization problems, although having intractably large domains, have quite small ranges. The strong version of PAS for all problems, and the weak version of PAS for a limited class of problems, has complexity the order of the size of the range.

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. S.H. Brooks, “A discussion of random methods for seeking maxima,”Operations Research 6 (1958) 244–251.

    Google Scholar 

  2. D. Dueck and T. Scheuer, “Threshold Accepting: a general purpose optimization algorithm appearing superior to simulated annealing,”Journal of Computational Physics 90 (1990) 161–175.

    Google Scholar 

  3. M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-completeness (Freeman, San Francisco, CA, 1979).

    Google Scholar 

  4. J.G. Kemeny and J.L. Snell,Finite Markov Chains (Springer, New York, 1976).

    Google Scholar 

  5. N.R. Patel, R.L. Smith and Z.B. Zabinsky, “Pure adaptive search in Monte Carlo optimization,”Mathematical Programming 43 (1988) 317–328.

    Google Scholar 

  6. Z.B. Zabinsky and R.L. Smith, “Pure adaptive search in global optimization,”Mathematical Programming 53 (1992) 323–338.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Industrial Engineering Program, FU-20, University of Washington, 98195, Seattle, WA, USA

    Z. B. Zabinsky

  2. Department of Mathematics and Computing, Central Queensland University, Rockhampton, Australia

    G. R. Wood

  3. Department of Mathematics and Statistics, University of Canterbury, Christchurch, New Zealand

    M. A. Steel & W. P. Baritompa

Authors
  1. Z. B. Zabinsky
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. G. R. Wood
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. A. Steel
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. W. P. Baritompa
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The authors would like to thank the Department of Mathematics and Statistics at the University of Canterbury for support of this research.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zabinsky, Z.B., Wood, G.R., Steel, M.A. et al. Pure adaptive search for finite global optimization. Mathematical Programming 69, 443–448 (1995). https://doi.org/10.1007/BF01585570

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Keywords

Search

Navigation