Multi-Target Optimisation via Bayesian Optimisation and Linear Programming

Alistair Shilton, Santu Rana, Sunil Gupta, Svetha VenkateshUAI 2018 · OpenReview

Abstract

Multi-objective optimization (MOO) is essential for engineering and scientific discovery where conflicting goals must be balanced. While Bayesian Optimization (BO) using Expected Hypervolume Improvement (EHI) is a standard approach, it becomes computationally intractable as the number of objectives increases. This paper introduces a scalable alternative: the Approximated Distance Gaussian Process Upper Confidence Bound (AD-GP-UCB). By replacing hypervolume calculations with a distance-based metric derived from a modified 1-norm Support Vector Machine (SVM), the proposed method leverages Linear Programming (LP) for efficiency. We demonstrate that AD-GP-UCB maintains dominance consistency and provides superior scalability and Pareto front coverage, particularly in "Many-Objective" scenarios with up to 12 objectives.

Introduction

In fields such as materials science and machine learning, researchers often face the challenge of optimizing multiple "black-box" functions simultaneously. For instance, designing a high-performance alloy requires balancing strength, weight, and cost. While Bayesian Optimization is well-suited for these expensive-to-evaluate functions, the traditional gold standard—Expected Hypervolume Improvement (EHI)—suffers from the curse of dimensionality. As the objective space expands beyond three dimensions, the geometric complexity of hypervolume calculation grows exponentially, making it impractical for "Many-Objective" Optimization (MaOO). Furthermore, existing distance-based alternatives often fail to maintain "dominance consistency," potentially leading to suboptimal recommendations.

The AD-GP-UCB Framework

To address these limitations, we propose AD-GP-UCB, which shifts the focus from measuring the volume of the dominated region to calculating the signed distance from the current estimated Pareto front.

Distance-Based Acquisition

The core innovation is the use of a restricted 1-norm, 1-class SVM to define the boundary of the dominated region. Unlike standard SVMs, this formulation is specifically constrained to ensure that any point dominating another in the objective space receives a strictly higher score. This property, termed "Dominance Consistency," is crucial for reliable optimization.

Comparison of the traditional hypervolume improvement metric (middle) with the proposed boundary distance metric (right) relative to the approximated Pareto front (left).

Linear Programming Efficiency

By employing a 1-norm formulation, the acquisition function can be optimized using Linear Programming. This provides a significant speed advantage over the complex geometric algorithms required for hypervolume. Additionally, the 1-norm SVM naturally produces sparse solutions, identifying a small set of "support vectors" that define the front, ensuring the method remains efficient as more data points are collected.

Experimental Evaluation

The performance of AD-GP-UCB was evaluated across three diverse domains:

  1. Synthetic Benchmarks: The DTLZ2 function was used to test scalability from 2 to 10 objectives.
  2. Hyperparameter Tuning: Multi-class classification tasks from the UCI repository (SAT, SEG, and WAV datasets) were optimized across 3 to 7 objectives.
  3. Real-World Material Design: A 12-objective problem involving the design of creep-resistant Ni-superalloys.

Results and Discussion

Scalability and Speed

The most striking result was observed in the 12-objective alloy design problem. While EHI was estimated to require approximately one day to generate a single recommendation, AD-GP-UCB completed the task in seconds. This efficiency makes BO practical for high-dimensional problems that were previously inaccessible.

Pareto Front Coverage

In the DTLZ2 benchmarks, AD-GP-UCB consistently outperformed EHI in terms of Hausdorff distance. This indicates that the distance-based approach provides a more diverse and comprehensive representation of the Pareto front, avoiding the common pitfall of clustering recommendations in a narrow region.

Parameter Sensitivity and Limitations

The accuracy of the boundary estimation is influenced by the smoothing parameter $\upsilon$. As shown in the figure below, $\upsilon$ controls the "tightness" of the fit to the observed data. While a smaller $\upsilon$ provides a closer fit, it may lead to higher non-linearity, which can affect the accuracy of the first-order Taylor approximation used for variance estimation in the UCB framework.

The effect of the smoothing parameter $\upsilon$ on the shape and tightness of the estimated Pareto front boundary.

Conclusion

AD-GP-UCB offers a robust and scalable solution for Many-Objective Bayesian Optimization. By combining the geometric intuition of distance-based metrics with the computational efficiency of Linear Programming and the rigor of dominance-consistent SVMs, it overcomes the dimensionality barriers of traditional hypervolume methods. Future work will focus on refining variance approximations and developing automated methods for tuning the boundary smoothing parameters.

Summary updated

BibTeX
@inproceedings{shilton2018multi,
  author = {Alistair Shilton and Santu Rana and Sunil Gupta and Svetha Venkatesh},
  title = {{Multi-Target Optimisation via Bayesian Optimisation and Linear Programming}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=kHM1slS6oRx},
}
Figure