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
- 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.
- 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