PURE ADAPTIVE SEARCH FOR FINITE GLOBAL OPTIMIZATION

Pure Adaptive Search is a stochastic algorithm which has been analyzed for continuous global optimization. When a uniform distribution is us ed in PAS, it has been shown to have complexity which is linear in dim ension, We define strong and weak variations of PAS in the setting of finite global optimization and prove analogous results. Ln particular, for the n-dimensional lattice (1,...,k)(n), the expected number of it erations to find the global optimum is linear in n. Many discrete comb inatorial optimization problems, although having intractably large dom ains, have quite small ranges. The strong version of PAS for all probl ems, and the weak version of PAS for a limited class of problems, has complexity the order of the size of the range.