Optimally Stopped Optimization

Understand

We combine the fields of heuristic optimization and optimal stopping.

• We propose a strategy for benchmarking randomized optimization algorithms that minimizes the expected total cost for obtaining a good solution with an optimal number of calls to the solver.
• To do so, rather than letting the objective function alone define a cost to be minimized, we introduce a further cost-per-call of the algorithm.
• We show that this problem can be formulated using optimal stopping theory.