Systematic Search in High Dimensional Sets

This paper presents a study of algorithms for searching high dimensional sets and presents a new systematic algorithm for this purpose. The context used for this study (and its original motivation) is the generation of starting points for algorithms to optimize functions of several variables. Such algorithms involve “local” iterative methods, and convergence analysis, etc. assumes that a starting point is sufficiently close to the solution. Such points are not available for many real problems, but rather one knows reasonable bounds on the solution. Thus, a general purpose program for real problems would be based on a polyalgorithm which combines several local methods and a global search method. The current practice is to use random searching. The new algorithm is compared with random searching in three distinct ways. First, four criteria for measuring the dispersion of a point set are discussed and applied. Second, a probabilistic model is developed and used to measure abilities to generate points in certain convergence sets. The third way is a comparison of the performance of the algorithms on a test problem. The conclusion is reached that the systematic algorithm provides a better way of searching a region (and provides better starting points) than the random algorithm.