I wish to fine-tune a numerical optimization algorithm in a particular problem where the criterion is very slow to compute exactly but can quickly return true/false of whether the exact result will be below/above a particular value. In a sense, the function is much faster to compare than to compute. What optimization algorithms would be able to utilize this feature, i.e., be able to rely on results of comparison operations, at least in some points?
Nelder-Mead is one of such methods that comes to mind, but are there others?