Efficient optimization through response surface modeling: a grope algorithm

An algorithm to address this class of GROPE problems (Global $\Re\sp{d}$ Optimization when Probes are Expensive) is developed and implemented, which is very efficient in the number of function evaluations required.

Abstract

For many real-world optimization applications, such as finding control parameters for a physical or simulated system, responses to test probes are expensive to obtain and gradient information is unavailable. An algorithm to address this class of GROPE problems (Global $\Re\sp{d}$ Optimization when Probes are Expensive) is developed and implemented, which is very efficient in the number of function evaluations required. The multi-dimensional search algorithm generalizes a 1-dimensional procedure in which a random walk or fractal form is assumed for the response surface (Kushner 1964). A piecewise model of the emerging surface is maintained, with each region (Delaunay simplex) having linear expectation and quadratic variance. The model is queried for promising new search locations; i.e., the design points (given all known results) most likely to exceed the current performance goal. A parameter-free implementation of the algorithm demonstrates results superior to those of other techniques in the literature on a suite of standard two-dimensional test functions.