A Ranking Approach to Global Optimization

In this paper, we consider the problem of maximizing an unknown and potentially nonconvex function f over a compact and convex set X ⊂ R^d using as few observations f (x) as possible. We observe that the optimization of the function f essentially relies on learning the induced bipartite ranking rule of f . Based on this idea, we relate global optimization to bipartite ranking which allows to address problems with high dimensional input space, as well as cases of functions with weak regularity properties. The paper introduces novel meta-algorithms for global optimization which rely on the choice of any bipartite ranking method. Theoretical properties are provided as well as convergence guarantees and equivalences between various optimization methods are obtained as a byproduct. Eventually, numerical evidence is provided to show that the main algorithm of the paper which adapts empirically to the underlying ranking structure is efficient in practice and displays competitive results with regards to the existing state-of-the-art global optimization methods over a wide range of usual benchmarks.