MOBO-OSD: Batch Multi-Objective Bayesian Optimization via Orthogonal Search Directions

AI summary

Overview

Research area: Machine learning — specifically multi-objective Bayesian optimization (MOBO) for expensive black-box objective functions, sitting at the intersection of surrogate-model-based optimization and multi-objective decision making.

Technical level: Intermediate to Advanced. The paper assumes familiarity with Gaussian Processes, acquisition functions, Pareto dominance, and the hypervolume indicator; the core proposal builds on constrained optimization and a geometric construction (the convex hull of individual minima).

Scope: The paper introduces MOBO-OSD, a batch multi-objective Bayesian optimization algorithm that generates a diverse set of Pareto optimal candidates by solving constrained subproblems along search directions orthogonal to an approximated convex hull of individual objective minima.

What This Paper Is About

Multi-objective optimization problems involve several conflicting objectives, so there is no single best solution — the goal is a well-spread set of Pareto optimal trade-offs. Bayesian optimization is sample-efficient but was largely developed for single objectives, and existing multi-objective variants struggle with diversity, scaling beyond three objectives, and the computational cost of batch (parallel) evaluation. The paper's goal is an algorithm that produces a diverse Pareto front, improving hypervolume, and that works for an arbitrary number of objectives in both sequential and batch settings.

Key Contributions

1. A geometry-driven search strategy. MOBO-OSD generates a diverse set of Pareto optimal candidates by solving multiple constrained optimization subproblems defined along search directions orthogonal to an approximated convex hull of individual minima (the approximated CHIM) of the objective space. The directions are made well-distributed using the Riesz s-Energy method.

2. Local Pareto front enrichment. A Pareto Front Estimation technique (First Order Approximation) locally explores the neighborhood of each subproblem solution to generate additional candidate Pareto solutions, avoiding the need to solve an excessive number of nearby subproblems.

3. Batch optimization support. The method performs in batch settings by combining the Kriging Believer technique (re-training GP models on the posterior mean of selected but unobserved points) with an exploration-space diversity constraint, so selected points originate from different exploration regions.

4. Empirical validation. The authors report that MOBO-OSD outperforms state-of-the-art MOBO baselines across synthetic and real-world multi-objective benchmarks spanning a wide range of numbers of objectives, in both sequential and batch settings.

Main Findings

• Claimed outperformance: The abstract states that MOBO-OSD "consistently outperforms the state-of-the-art algorithms" on a variety of synthetic and real-world benchmark functions with two to six objectives. The specific numerical results, benchmark-by-benchmark figures, and statistical comparisons are not included in the truncated content provided, so no per-problem numbers can be quoted here.

• Sequential-setting evaluation: Figure 2 reports a comparison of MOBO-OSD against state-of-the-art baselines on 5 synthetic and 4 real-world benchmark problems in the sequential setting (batch size 1). The figure caption states that DGEMO does not extend to problems with M > 3 objectives, and that overall MOBO-OSD outperforms the baselines.

• Baselines compared: qParEGO, USeMO, DGEMO, PDBO, JES, qEHVI, NSGA-II, and NBI. USeMO is run with the EI acquisition function; qParEGO uses the batch implementation developed by Daulton et al.; DGEMO's authors' implementation only supports M = 2 and M = 3 objectives; JES is compared only in the sequential setting (batch size 1) because of its prohibitive computational cost.

• Search-region preservation: The proposed approximated CHIM, built from M boundary points derived from the ideal and nadir points of observed data, maintains a broader search region than the alternative of using individual minima found so far in the observed dataset. The paper argues the alternative shrinks the search region prematurely if a good solution is found early, overlooking unexplored regions.

• Handling of concave Pareto fronts: The scalar λ along a search direction can be negative for concave Pareto fronts, such as the DTLZ2 benchmark function, which is why λ is not treated as a Euclidean distance from the CHIM point.

• Ablation study: The paper points to an ablation study in Section 5.2 covering the Pareto Front Estimation step; the details and results are not contained in the truncated content.

• Reference-point heuristic: When selecting among multiple starting-point solutions to a subproblem, the hypervolume contribution is computed with reference point r_s = s_nadir + 0.1 · (s_nadir − s_ideal).

• Batch diversity constraint: Batch selection maximizes the Hypervolume Improvement acquisition function subject to the condition that the number of selected points from different exploration spaces differs by at most one.

Methodology in Plain English

The method borrows a geometric insight from the Normal Boundary Intersection (NBI) method: if you draw lines outward from the convex hull of the individual objective minima, the points where those lines cross the boundary of the achievable objective space tend to be Pareto optimal.

Because the individual minima are unknown under a limited evaluation budget, the authors approximate that hull using M "boundary points." Each boundary point is constructed by taking the ideal point (the best value observed so far for each objective) and replacing one component with the nadir value (the worst observed value for that objective). This approximated hull is deliberately kept broad so the search space does not shrink prematurely.

From this hull, they draw a set of search directions that are orthogonal (perpendicular) to it. The directions are spaced out by first generating well-distributed convex combination weight vectors on a unit simplex using the Riesz s-Energy method — a physics-inspired trick where minimizing a potential-energy function over the points yields a diverse spread — and then mapping those weights onto the hull.

For each direction, the algorithm solves a constrained single-objective problem: maximize how far along the direction the surrogate model's predicted objective values reach, subject to staying within a hyper-rectangular confidence region around the direction. This is solved with a gradient-based off-the-shelf optimizer (SLSQP), using multiple random starting points because the problem is non-convex. From the many solutions produced by those starting points, the one with the best trade-off between "far along the line" and "close to the line" is chosen via a hypervolume-contribution rule.

Around each chosen solution, a First Order Approximation technique defines a local exploration space, and random perturbations inside that space generate extra candidate solutions — cheap additional Pareto candidates without solving more subproblems.

Finally, all candidates from all directions are pooled, and a batch of points is selected by the hypervolume improvement of the posterior mean. The Kriging Believer method re-trains the Gaussian Process models after each selection (treating the predicted mean of a selected point as if it were observed) so that later picks in the batch do not duplicate earlier ones. The exploration-space constraint forces the batch to spread across different regions.

Why This Matters

Impact on research. The work offers an alternative to scalarization-based MOBO methods, which the authors argue often fail to capture a diverse Pareto front and therefore underperform on the hypervolume indicator. It also targets two known weaknesses in the literature: methods that cannot scale beyond three objectives, and methods whose batch acquisition functions become computationally expensive as the number of objectives grows. Since the authors note the approach operates on a hypervolume-improvement acquisition function but is compatible with alternative multi-objective acquisition functions, it can potentially absorb future acquisition-function developments.

Real-world applications (as listed in the paper's introduction):

• Machine learning (e.g., tuning models with competing objectives)
• Material design
• Agriculture
• Robotics
• Vehicle design

(Note: the paper's introduction lists all five of these domains; the paper does not report detailed application case studies for any of them in the provided content.)

Industry relevance. Every setting cited above involves objective evaluations that are expensive in time or money — physical experiments, simulations, or long training runs. Batch support matters because it allows parallel evaluations to accelerate the optimization process "when resources are available," which maps directly onto industrial practice of running many evaluations concurrently on a compute cluster or parallel experimental rig. The reduction in the number of evaluations needed, and the ability to handle more than three objectives, broadens the class of practical design problems the method can address.

Future Directions

• Scaling to higher objective counts and larger budgets. The paper demonstrates results for two to six objectives; whether the geometric construction and well-distributed direction generation remain effective for many more objectives is an open question.

• Reducing the cost of competitive acquisition functions. The authors exclude JES from batch comparisons because of its prohibitive computational cost and note that qEHVI can suffer from high computational cost even for M > 2. Making such acquisition functions tractable in batch MOBO remains a live problem.

• Extending beyond the current experimental scope. The truncated content ends mid-sentence in the discussion of the NBI baseline's implementation availability, so the full set of comparisons, batch-setting results, and sensitivity analyses reported in the paper cannot be summarized here. The reported sensitivity analyses over the number of weight vectors, number of perturbation samples, and the confidence scaling factor are likewise not available in the provided content.

• Handling constrained and multi-fidelity settings. The paper notes that the HVKG acquisition function targets multi-fidelity and decoupled multi-objective problems, and states that MOBO-OSD is compatible with other acquisition functions — suggesting integration with such settings as a natural extension.

Target Audience

Researchers and practitioners in Bayesian optimization and multi-objective optimization who are familiar with Gaussian Processes, acquisition functions, Pareto optimality, and the hypervolume indicator. It is most useful to those working on expensive black-box design problems with several competing objectives and access to parallel evaluation resources, and to method developers looking for a geometry-based, non-scalarization approach to Pareto front generation.

Authors’ abstract

Bayesian Optimization (BO) is a powerful tool for optimizing expensive black-box objective functions. While extensive research has been conducted on the single-objective optimization problem, the multi-objective optimization problem remains challenging. In this paper, we propose MOBO-OSD, a multi-objective Bayesian Optimization algorithm designed to generate a diverse set of Pareto optimal solutions by solving multiple constrained optimization problems, referred to as MOBO-OSD subproblems, along orthogonal search directions (OSDs) defined with respect to an approximated convex hull of individual objective minima. By employing a well-distributed set of OSDs, MOBO-OSD ensures broad coverage of the objective space, enhancing both solution diversity and hypervolume performance. To further improve the density of the set of Pareto optimal candidate solutions without requiring an excessive number of subproblems, we leverage a Pareto Front Estimation technique to generate additional solutions in the neighborhood of existing solutions. Additionally, MOBO-OSD supports batch optimization, enabling parallel function evaluations to accelerate the optimization process when resources are available. Through extensive experiments and analysis on a variety of synthetic and real-world benchmark functions with two to six objectives, we demonstrate that MOBO-OSD consistently outperforms the state-of-the-art algorithms. Our code implementation can be found at https://github.com/LamNgo1/mobo-osd.