Model-optimal optimization by solving bellman equations
Alan J. Lockett · 2014
This paper analytically identifies the points chosen by the best black-box optimization methods, measured by assigning values to the history of points examined by stochastic optimization methods applied to randomly chosen but static (single) objective functions. Optimizers that make these "best" choices are called {\it model-optimal}. Model-optimal optimizers may not exist for a given model of static objectives but can always be approximated. If the search domain and the fitness range are both compact, or if other more abstract conditions are satisfied, it can be proven that model-optimal optimizers exist and at least one of them is deterministic. Model-optimality is studied by treating the average performance as a Bellman equation. The overall performance of an optimizer can be assessed based on the sequence of points selected for evaluation. Each choice introduces an error, and the overall performance is in every case just the sum of these errors. It might be possible to extend these results to certain stochastic or dynamic objectives, but they probably do not apply in adaptive or coevolutionary environments. The properties of model-optimality may make it possible to assess the tightness of existing bounds on average performance, and it may be possible to approximate model-optimal optimization decisions directly.