On the approximate domain optimization of deterministic and expected value criteria

We define the concept of approximate domain optimizer for deterministic and expected value optimization criteria. Roughly speaking, a candidate optimizer is an approximate domain optimizer if only a small fraction of the optimization domain is more than a little better than it. We show how this concept relates to commonly used approximate optimizer notions for the case of Lipschitz criteria. We then show how random extractions from an appropriate probability distribution can generate approximate domain optimizers with high confidence. Finally, we discuss how such random extractions can be performed using Markov Chain Monte Carlo methods.