A trust-region approach for computing Pareto fronts in multiobjective derivative-free optimization

Abstract This paper presents a modified trust-region approach for computing approximations to the complete Pareto front of multiobjective derivative-free optimization problems. It is assumed that the derivatives of the objective function components are not available, impossible or very expensive to estimate, such as in simulation optimization, bandit optimization, and adversarial black-box machine learning. The algorithm alternates between two main steps, namely, the extreme point step and the scalarization step, until predefined stopping criteria are met. The goal of the extreme point step is to expand the approximation to the complete Pareto front, by moving towards the extreme points of it, corresponding to the individual minimization of each objective function component. The scalarization step attempts to minimize the size of gaps in the Pareto front approximation, by solving a suitable scalarization problem. The scalarization step includes a pivotal additional step, referred to as the middle point step. This step plays a significant role in determining initial points for solving the scalarization problem. To overcome the absence of derivatives, a new technique based on polynomial interpolation and minimum Frobenius norm approaches is proposed to build models that approximate different objective function components. The convergence analysis is well established, even with the extra complexity introduced by the challenge of lacking derivative information. Numerical results are presented, indicating that this algorithm is efficiently and robustly competitive against state-of-the-art multiobjective derivative-free optimization algorithms that also aim to approximate complete Pareto fronts.