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

Aboozar Mohammadi, Davood Hajinezhad, Alfredo GarcíaOptim. Lett 2025 · OpenReview

Introduction

Multiobjective optimization problems (MOPs) are prevalent in engineering and data science, where decision-makers must navigate trade-offs between conflicting objectives, such as safety versus fuel efficiency. The goal is to identify the Pareto front—the set of optimal solutions where no objective can be improved without degrading another. However, in many practical applications like simulation-based optimization or black-box machine learning, the derivatives of the objective functions are unavailable or prohibitively expensive to compute. This paper introduces a novel Multiobjective Trust-Region Derivative-Free Optimization (MOTRDFO) algorithm designed to efficiently approximate the complete Pareto front in these challenging scenarios.

Methodology

The MOTRDFO algorithm employs a trust-region framework that alternates between two primary phases to ensure both the breadth and density of the Pareto front approximation.

Extreme Point and Scalarization Steps

  1. Extreme Point Step: This phase focuses on expanding the boundaries of the Pareto front. By individually minimizing each objective function component, the algorithm identifies the extreme points of the trade-off curve, establishing the full range of the solution set.
  2. Scalarization Step: To fill gaps within the identified boundaries, the algorithm solves scalarization sub-problems. A critical component here is the Middle Point Step, a heuristic that selects initial points in the largest gaps of the current approximation, ensuring a uniform distribution of solutions.

Surrogate Modeling

In the absence of gradients, MOTRDFO constructs local surrogate models using polynomial quadratic interpolation. When data points are insufficient for a full quadratic model, the algorithm utilizes a minimum Frobenius norm approach. This ensures the creation of "fully linear" models, providing the necessary accuracy to maintain theoretical convergence guarantees even without derivative information.

Experimental Setup

The performance of MOTRDFO was evaluated using a benchmark suite of 54 bound-constrained multiobjective optimization problems, ranging from 1 to 30 variables and 2 to 3 objectives. The algorithm was compared against three state-of-the-art derivative-free solvers:

  • MOIF (Implicit Filtering)
  • BoostDMS (Directional Direct Search)
  • DMultiMADS (Mesh Adaptive Direct Multisearch)

Testing was conducted across three computational budgets: 500, 5,000, and 20,000 function evaluations.

Results and Discussion

Numerical results indicate that MOTRDFO is highly competitive and robust. Key findings include:

  • Efficiency and Density: MOTRDFO consistently produced denser Pareto fronts than its competitors. In several instances, it generated thousands of non-dominated points where other methods produced only a few hundred within the same budget.
  • Purity and Spread: The algorithm outperformed MOIF and BoostDMS in terms of Purity (the ratio of optimal points found) and Spread (the uniformity of point distribution).
  • Robustness: While DMultiMADS showed strength in Hypervolume metrics, MOTRDFO demonstrated superior robustness across a broader variety of problem types and dimensions.

A significant advantage of MOTRDFO is its "data recycling" capability, which reuses sample points from previous iterations to build surrogate models, making it particularly suitable for expensive black-box functions.

Conclusion

MOTRDFO offers a mathematically rigorous yet practical solution for multiobjective derivative-free optimization. By combining geometric heuristics with trust-region convergence theory, it provides a reliable method for mapping complex trade-off surfaces. Future research will focus on extending the algorithm to handle general nonlinear constraints and addressing stochastic noise in black-box evaluations.

Summary updated

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.
BibTeX
@inproceedings{mohammadi2025trust,
  author = {Aboozar Mohammadi and Davood Hajinezhad and Alfredo García},
  title = {{A trust-region approach for computing Pareto fronts in multiobjective derivative-free optimization}},
  booktitle = {Optim. Lett},
  year = {2025},
  url = {https://openreview.net/forum?id=zpN5zB0vqX},
}
Figure