TL;DR
This paper introduces a novel Bayesian optimization criterion, mEI, that efficiently targets specific regions of the Pareto front in multi-objective optimization problems with expensive-to-evaluate functions. They also propose a batch version, q-mEI, enabling parallel computation and faster convergence to desired trade-off solutions.
What Problem Does This Paper Address?
Multi-objective optimization (MOO) aims to find a set of optimal trade-off solutions, known as the Pareto optimal set. However, when evaluating objective functions is computationally expensive, finding the entire Pareto set is often infeasible and unnecessary. Users typically have a specific region of interest within the Pareto front. Existing Bayesian optimization methods, while effective, often struggle to efficiently focus the search on these preferred regions, leading to wasted evaluations. This paper addresses this by developing a method to guide the optimization towards a user-defined target region of the Pareto front.
Methods
The core of the paper is the introduction of the modified Expected Hypervolume Improvement (mEI) criterion. Unlike traditional Expected Hypervolume Improvement (EHI), which aims to maximize the overall hypervolume, mEI focuses the search by incorporating a "reference point" (R). This reference point can be user-defined or automatically determined (e.g., as the center of the Pareto front). mEI is formulated as the product of individual Expected Improvements for each objective, conditioned on the reference point.
To leverage parallel computing, the authors extend mEI to a batch version called q-mEI. This criterion allows for the simultaneous evaluation of multiple candidate points, significantly speeding up the optimization process. They also introduce and analyze a naive batch extension (mq-EI) and demonstrate why q-mEI is the more appropriate approach for multi-objective problems. The paper also details a method for estimating the "center of the Pareto front" when no explicit preference is given.
Datasets
The paper uses the MetaNACA benchmark for evaluating their proposed methods. This benchmark is derived from real-world airfoil aerodynamic data and has 8 dimensions with 2 objectives (negative lift and drag). They also use two standard analytical test functions for multi-objective optimization: ZDT3 and P1.
Key Insights and Ideas
- Targeting is Crucial for Expensive Optimization: When function evaluations are costly, focusing the search on a specific region of the Pareto front is far more efficient than trying to explore the entire space.
- mEI as a Targeted Infill Criterion: mEI provides a computationally efficient and effective way to guide Bayesian optimization towards a desired region of the Pareto front, offering a significant advantage over standard EHI when preferences are known.
- q-mEI for Parallelism: The batch version, q-mEI, is a natural and effective extension for parallel computing environments, allowing for simultaneous evaluations and further accelerating the convergence to the targeted region.
- The "Center of the Pareto Front" as a Default Target: When no explicit user preference is provided, targeting the center of the Pareto front offers a sensible default strategy for finding "well-balanced" solutions.
- mq-EI is Not Suitable for MOO: The naive batch extension (mq-EI) fails to maintain the coupling between objectives, leading to suboptimal behavior in multi-objective settings.
Key Results
- Faster Convergence to Target Regions: Experiments show that mEI and q-mEI significantly outperform standard EHI and NSGA-II in reaching a user-defined target region of the Pareto front, especially in terms of wall-clock time.
- Improved Accuracy in Targeted Regions: For the MetaNACA benchmark, q-mEI demonstrated more accurate convergence to the center of the Pareto front compared to sequential mEI at the same wall-clock time.
- Efficiency Gains with Batching: At the same wall-clock time, q-mEI (with q=2 or 4) could perform significantly more function evaluations than sequential mEI, leading to better approximations of the targeted Pareto front region.
- Robustness: The paper demonstrates that q-mEI is more robust to GP inaccuracies compared to the naive mq-EI.
Limitations and Future Work
- Monte Carlo Estimation: The q-mEI criterion is currently computed using Monte Carlo simulations, which can be computationally intensive.
- Analytical Expression for q-mEI: The authors suggest that deriving an analytical expression for q-mEI and its gradient would allow for more efficient optimization, which is a significant future research direction.
- Broadening the Search: After reaching a target region, the remaining evaluation budget could be used to broaden the search for other parts of the Pareto set.
- Asynchronous Implementations: The paper hints at asynchronous versions of batch criteria, which are important for practical parallel implementations.
Summary updated