Multi-Objective Simultaneous Optimistic Optimization

Optimistic methods have been applied with success to single-objective optimization. Here, we attempt to bridge the gap between optimistic methods and multi-objective optimization. In particular, this paper is concerned with solving black-box multi-objective problems given a finite number of function evaluations and proposes an optimistic approach, which we refer to as the Multi-Objective Simultaneous Optimistic Optimization (MO-SOO). Popularized by multi-armed bandits, MO-SOO follows the optimism in the face of uncertainty principle to recognize Pareto optimal solutions, by combining several multi-armed bandits in a hierarchical structure over the feasible decision space of a multi-objective problem. Based on three assumptions about the objective functions smoothness and hierarchical partitioning, the algorithm finite-time and asymptotic convergence behaviors are analyzed. The finite-time analysis establishes an upper bound on the Pareto-compliant unary additive epsilon indicator characterized by the objectives smoothness as well as the structure of the Pareto front with respect to its extrema. On the other hand, the asymptotic analysis indicates the consistency property of MO-SOO. Moreover, we validate the theoretical provable performance of the algorithm on a set of synthetic problems. Finally, three-hundred bi-objective benchmark problems from the literature are used to substantiate the performance of the optimistic approach and compare it with three state-of-the-art stochastic algorithms in terms of two Pareto-compliant quality indicators. Besides sound theoretical properties, MO-SOO shows a performance on a par with the top performing stochastic algorithm.