An {\em Abstract Optimization Problem} (AOP) is a triple $(H,<, \Phi)$ where $H$ is a finite set, $<$ a total order on $2^{H}$ and $\Phi$ an oracle that, for given $F\subseteq G\subseteq H$, either reports that $F=\min_{<}\{F'\mid F'\subseteq G\}$ or returns a set $F'\subseteq G$ with $F'<F$. To solve the problem means to find the minimum set in $H$. We present a randomized algorithm that solves any AOP with an expected number of at most $$e^{2\sqrt{n}+O(\sqrt[4]{n}\ln n)}$$ oracle calls, $n=|H|$. In contrast, any deterministic algorithm needs to make $2^{n}-1$ oracle calls in the worst case. The algorithm is applied to the problem of finding the distance between two $n$-vertex (or $n$-facet) convex polyhedra in $d$-space, and to the computation of the smallest ball containing $n$ points in $d$-space; for both problems we give the first subexponential bounds in the arithmetic model of computation.

---