An adaptive sampling algorithm for simulation-based optimization with descriptive complexity constraints

The pervasive application of digital computers in simulation-based optimization requires solutions that can be implemented in the given memory space and run in a reasonably short time. However, these descriptive complexity constraints are usually nonlinear and take discrete values, which make traditional methods such as linear programming and gradient-based local search not applicable. In this paper, we develop an adaptive sampling algorithm (ASA) to find simple and good solutions. We prove that ASA terminates within finite steps and finds a simple and good solution with small type II error, i.e., a small probability to output a solution that is not the simplest among all good solutions. Numerical experiments show that ASA makes good tradeoff between type II error and computational time, comparing with blind picking and Levin search. We hope this work can shed some insight to how to find simple and good solution in general.