Pure adaptive search for finite global optimization

Z. B. Zabinsky*, G. R. Wood, M. A. Steel, W. P. Baritompa

*Corresponding author for this work

    Research output: Contribution to journalArticle

    21 Citations (Scopus)

    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 the n-dimensional lattice {1,⋯, k}n, the expected number of iterations to find the global optimum is linear in n. 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.

    Original languageEnglish
    Pages (from-to)443-448
    Number of pages6
    JournalMathematical Programming
    Volume69
    Issue number1-3
    DOIs
    Publication statusPublished - Jul 1995

    Fingerprint Dive into the research topics of 'Pure adaptive search for finite global optimization'. Together they form a unique fingerprint.

    Cite this