Pure adaptive search in monte carlo optimization

• DOI: 10.1007/bf01582296
• Publication Date: 2005-04-28T08:32:42Z
• Authors: Nitin R. Patel; Robert L. Smith; Zelda B. Zabinsky
• Keywords: Optimization; Numerical Analysis; 330; Science; Numerical and Computational Methods; Monte Carlo Optimization; Calculus of Variations and Optimal Control; 01 natural sciences; 510; Random Search; Combinatorics; Mathematical and Computational Physics; Mathematical Methods in Physics; Convex Programming; Mathematics of Computing; 0101 mathematics; Operation Research/Decision Theory; Mathematics

Pure adaptive search constructs a sequence of points uniformly distributed within a corresponding sequence of nested regions of the feasible space. At any stage, the next point in the sequence is chosen uniformly distributed over the region of feasible space containing all points that are equal or superior in value to the previous points in the sequence. We show that for convex programs the number of iterations required to achieve a given accuracy of solution increases at most linearly in the dimension of the problem. This compares to exponential growth in iterations required for pure random search.