Pure adaptive search for finite global optimization

Pure adaptive search for finite global optimization

0.00 Avg rating0 Votes
Article ID: iaor19971120
Country: Netherlands
Volume: 69
Issue: 3
Start Page Number: 443
End Page Number: 448
Publication Date: Sep 1995
Journal: Mathematical Programming (Series A)
Authors: , , ,
Keywords: programming: integer, computational analysis
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. The authors 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.

Reviews

Required fields are marked *. Your email address will not be published.