Simulation-based optimization using finite-time approximations of the infinite-time-average statistics

Simulated-based optimization problems are difficult, due both to the nonconvexity of the cost function and to the extreme cost of accurate function evaluations, especially if the cost function is derived from a finite-time-average approximation of the infinite-time-average statistics. In this work, we have developed an algorithm that controls both the location and the accuracy of each cost function evaluation. At each step of the algorithm, a Delaunay triangulation is created based on the existing evaluation points. In each simplex so created, the algorithm optimizes a cost function based on a polyharmonic spline regression. At each optimization step, an appropriately-modeled error function is combined with the regression, weighted with a tuning parameter governing the trade-off between local refinement and global exploration. In this way, the location of the new candidate point for the global minimum is found; then, based on the value of the minimum available cost function evaluations and the uncertainty associated with it, an efficient finite-time approximation at this point is calculated. The global convergence of this algorithm will be shown, and its efficiency will be tested on representatives test functions.