PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable Constrained Bayesian Optimization

David Eriksson, Matthias Poloczek

arXiv:2002.08526v3cs.LGcs.AIstat.ML

TL;DR

High-dimensional black-box constrained optimization is difficult because feasible sets are often non-convex and hard to find, while dimensionality and heterogeneity impair Bayesian optimization. The paper proposes SCBO, combining scalable constrained Bayesian optimization components, and reports strong performance across high- and low-dimensional constrained problems. Its scope remains open for highly correlated objectives and constraints, especially at very large constraint counts.

  • Problem

    High-dimensional black-box constrained optimization remains difficult because feasible sets are typically non-convex and hard to find, while dimensionality and heterogeneous functions challenge Bayesian optimization.

  • Method

    SCBO combines trust-region search, tailored transformations for objectives and constraints, and Thompson sampling for constrained batch selection.

  • Results

    SCBO outperforms previous state-of-the-art methods on high-dimensional constrained problems and matches or beats the best baseline otherwise.

  • Takeaways & Limitations

    SCBO extends constrained Bayesian optimization to high-dimensional, expensive, batched, and asynchronous settings while retaining convergence to a global optimum as sample count increases.

  • Takeaways & Limitations

    Future work is needed for strongly correlated objectives and constraints, where heterogeneous functions may make multi-output Gaussian processes challenging; hundreds of constraints remain an efficiency target.

Abstract

from arXiv · show

The global optimization of a high-dimensional black-box function under black-box constraints is a pervasive task in machine learning, control, and engineering. These problems are challenging since the feasible set is typically non-convex and hard to find, in addition to the curses of dimensionality and the heterogeneity of the underlying functions. In particular, these characteristics dramatically impact the performance of Bayesian optimization methods, that otherwise have become the de facto standard for sample-efficient optimization in unconstrained settings, leaving practitioners with evolutionary strategies or heuristics. We propose the scalable constrained Bayesian optimization (SCBO) algorithm that overcomes the above challenges and pushes the applicability of Bayesian optimization far beyond the state-of-the-art. A comprehensive experimental evaluation demonstrates that SCBO achieves excellent results on a variety of benchmarks. To this end, we propose two new control problems that we expect to be of independent value for the scientific community.

1 Introduction

High-dimensional black-box constrained optimization is difficult because feasible regions can be non-convex and hard to locate, while function heterogeneity and dimensionality challenge Bayesian optimization. SCBO targets this gap with scalable constrained optimization and performs strongly across constrained benchmarks.

  • High dimensionality and heterogeneous black-box functions are difficult to optimize, while non-convex black-box feasible sets are hard to find.
  • SCBO is proposed as a scalable algorithm for high-dimensional expensive functions under expensive constraints.
  • SCBO supports large batches and asynchronous observations for constrained problems.
  • SCBO outperforms previous state-of-the-art methods by far on high-dimensional constrained problems.
  • SCBO at least matches and often beats the best performer on low-dimensional instances.

3. We introduce two new high-dimensional con-

The paper situates SCBO among constrained Bayesian optimization, scalable Bayesian optimization, and alternative constrained black-box optimization methods. It also frames the article around new high-dimensional constrained test problems and empirical comparison.

  • The article introduces high-dimensional constrained test problems intended to be independently useful because of their novelty and anticipated impact.
  • Related work: Constrained Bayesian optimization extends Bayesian optimization to black-box constraints, including expected-improvement and entropy-search approaches.
  • Related work: Lagrangian, slack-variable, and ADMM methods reformulate constrained optimization into sequences of unconstrained problems using EI-based procedures.
  • Related work: Traditional Bayesian optimization has generally targeted at most 15 decision variables and budgets of a few hundred samples.
  • Related work: Constrained black-box optimization is also addressed by evolutionary strategies and operations-research methods such as CMA-ES, COBYLA, and BOBYQA.

2 The Model

The model seeks an optimizer of a black-box objective over a compact domain subject to black-box constraints. Queries return noisy observations of the objective and constraints without derivative information.

  • The optimization problem seeks an optimizer of a black-box objective function subject to black-box constraints.
  • The objective and constraints are defined over a compact subset Ω of a d-dimensional domain.
  • Evaluating any point returns potentially noisy observations of the objective and every constraint, but no derivative information.

3 Scalable Constrained Bayesian Optimization (SCBO)

SCBO combines trust-region search, Thompson sampling, and role-specific transformations for objectives and constraints. It selects feasible batch points from posterior samples, adapts the trust region, and is consistent under the stated procedure.

  • Algorithm: SCBO evaluates batches of q points in parallel and can be extended to asynchronous batch evaluations.
  • Trust regions: Trust regions confine high-dimensional sampling locally, move as better points are discovered, and address acquisition functions that fail to zoom in on promising solutions.
  • Thompson sampling: SCBO extends Thompson sampling to black-box constraints, enabling large batches at low computational cost.
  • Thompson sampling: Posterior realizations define sampled-feasible candidates; SCBO minimizes sampled objective values when feasible candidates exist and otherwise minimizes total violation.
  • Transformations: Gaussian copula transformations magnify objective differences at observed minima or maxima, while bilog transformations emphasize constraint sign changes near zero and dampen large values.
  • Trust regions: SCBO adapts trust-region size using success and failure counters, moving its center toward the best feasible point or the point with minimum total violation.
  • Algorithm: The algorithm fits Gaussian processes to transformed observations, generates trust-region candidates, samples posterior realizations, evaluates batches, and updates the trust region.
  • Algorithm: For noisy functions, SCBO recommends the point with minimum posterior mean among points feasible with probability at least 1−δ, and converges to a global optimum as samples increase.

4 Experimental Evaluation

SCBO is evaluated against constrained Bayesian optimization, evolutionary, local-search, and random-search baselines across low- and high-dimensional benchmarks. It performs strongly across physics, synthetic, control, route-planning, vehicle-design, and ablation experiments, with trust regions especially important on challenging problems.

  • Physics Test Problems: SCBO outperforms or matches leading methods across four low-dimensional physics design problems under a 100-evaluation budget.It obtains the best results on tension-compression string, pressure vessel, and welded beam design, while SCBO and PESC perform best on speed reducer design.
  • Synthetic Benchmarks: 2.2 · 10^-5 is the probability of randomly selecting a feasible point in the 10D Ackley benchmark, where SCBO ultimately achieves the best performance.COBYLA initially progresses well, but SCBO eventually surpasses it; PESC performs well but requires substantially more computation.
  • Synthetic Benchmarks: SCBO clearly outperforms competing algorithms on the 30D Keane function despite COBYLA receiving a sequential-sampling advantage.PESC and SLACK are omitted from this benchmark because of computational overhead.
  • Robust Multi-point Optimization: SCBO finds feasible controllers in 28/30 runs with 10 scenarios and outperforms other methods more clearly as the number of constraints increases to 30 and 50.The best reward decreases with more scenarios because solutions feasible for fewer scenarios may violate additional constraints.
  • High-dimensional Applications: SCBO performs well on 60D route planning and 124D vehicle design with 68 constraints, finding a feasible vehicle-design point in 30/30 runs.The vehicle-design benchmark fits 69 Gaussian-process models in a batch, illustrating the implementation's scalability.
  • Ablation Studies: Trust regions are critical on the 30D Keane and 5D poorly scaled Rosenbrock benchmarks, while transformations provide additional gains and TS beats EI on Rosenbrock.On the smooth 2D toy problem, methods without trust regions and EI perform comparatively well.

5 Conclusions

The paper presents SCBO for high-dimensional constrained black-box optimization, combining tailored function transformations, trust regions, and Thompson sampling. Experiments show strong performance on high-dimensional benchmarks and competitive performance otherwise, while future work targets correlated objectives and constraints.

  • SCBO combines tailored transformations, trust regions, and Thompson sampling to scale constrained Bayesian optimization to high-dimensional spaces and large sampling budgets.
  • The evaluation compares SCBO with methods from machine learning, operations research, and evolutionary algorithms across control, multi-point optimization, and physics benchmarks.
  • SCBO outperforms state-of-the-art methods on high-dimensional benchmarks and matches or beats the best baseline on lower-dimensional instances.
  • The supplement provides an efficient batch-GP GPU implementation and a formal proof that SCBO converges to a global optimum.
  • Future work considers exploiting correlations among objectives and constraints to improve efficiency on problems with hundreds of constraints.

Supplementary material

The supplementary material addresses implementation details needed to scale Gaussian-process inference and sampling for constrained Bayesian optimization. It replaces cubic-cost Cholesky computations with GPU-accelerated batch-GP methods and evaluates their computational behavior.

  • With m constraints and n observations, standard GP inference costs Θ(mn3) flops, limiting scalability to large sampling budgets.
  • Batch GPs exploit GPU parallelism by representing m+1 kernel matrices in a 3D tensor and accelerating matrix-vector products with CUDA and KeOPS.
  • Conjugate gradients solve kernel linear systems while the Lanczos process approximates log-determinants, avoiding direct Cholesky decomposition.
  • The implementation also applies these batch-GP techniques to scale constrained expected improvement to large numbers of samples.

C Details on SCBO

SCBO uses fixed trust-region and perturbation hyperparameters adopted from TURBO, with batch success and failure counters controlling trust-region expansion, contraction, and restarting. The supplementary table caption specifies how computational implementations are compared.

  • Hyperparameters: SCBO sets τs = max(3, ⌈d/10⌉), τf = ⌈d/q⌉, Lmin = 2−7, Lmax = 1.6, and Linit = 0.8.
  • Trust-region control: A batch succeeds when at least one evaluation improves the incumbent; repeated successes expand the trust region, while repeated failures halve it.
  • Trust-region control: If the trust-region side length falls below Lmin, SCBO terminates that region and starts a new one initialized with a Sobol sequence.
  • Computational comparison: Table 2 compares Cholesky-based and batch-GP implementations for training, prediction, and sampling, including mean and variance MAE.

D Global Consistency of SCBO

Under explicit assumptions on initialization, boundedness, uniqueness, and improvement thresholds, the paper proves that noise-free SCBO converges globally as the number of samples tends to infinity. The proof relies on finite sampling within each trust region and infinitely many restarted regions.

  • Assumptions: SCBO with default parameters in a multi-start framework is analyzed under assumptions including sufficiently covering initial points, bounded objective and constraints, and a unique global minimizer.
  • Assumptions: The algorithm counts a sampled point as an improvement only when it improves the current best solution by at least a constant γ > 0.
  • Result: Under noise-free observations, SCBO converges to the global minimizer x∗ as the number of samples tends to infinity.
  • Proof idea: Each trust region receives finitely many samples, so SCBO restarts infinitely often and generates an infinite subsequence of initial points.
  • Proof idea: The proof derives global convergence from random-search convergence applied to the subsequence of restarted trust-region initial points.

E Additional ablation studies

The ablations show that SCBO’s transformations and subset perturbations contribute differently across benchmarks, while combining transformations can improve performance. Trust-region-local candidate generation is especially important for the 30D Keane function.

  • The bilog transform is more important on the 30D Keane function, whereas the copula transform improves results on the 5D Rosenbrock function.
  • Using both transformations works better than using only one, although bilog transformation slows convergence while achieving final performance comparable to copula alone.
  • Perturbing only a subset of dimensions generates candidates closer to the current best point and improves performance on the 30D Keane function.

F Results on the Transformed Physics Problems

Applying SCBO’s objective and constraint transformations to physics problems changes baseline performance little overall, while PESC benefits on two problems. The transformed comparisons therefore remain broadly similar across the other test problems.

  • SCBO’s transformations do not noticeably change baseline performance except for PESC on the 3D tension-compression string and 4D welded beam design problems.
  • Performance is comparable with and without the transformations for the other physics test problems.

G Details on the Benchmarks

The benchmark suite spans constrained design, synthetic, control, trajectory-planning, and large-scale industrial problems with varied dimensions, constraints, domains, and evaluation budgets. Several benchmarks deliberately stress feasibility discovery, scaling, or difficult function structure.

  • Synthetic benchmarks: The 30D Keane benchmark is difficult for Bayesian optimization because it is hard to model with a global Gaussian process.
  • Control and trajectory problems: The robust lunar-lander benchmark constrains every individual reward to be at least 200 across fixed terrains, making evaluations deterministic.
  • Control and trajectory problems: The Rover problem constrains trajectories to start and end at specified locations and avoid 15 additional impassable obstacles.
  • Large-scale design: MOPTA08 has 124 variables and 68 performance constraints, placing it beyond the reach of existing Bayesian optimization methods according to the paper.
  • Synthetic benchmarks: The 5D Rosenbrock benchmark uses Dixon-Price and Levy constraints to create a poorly scaled constrained optimization problem.
  • Experimental procedure: SCBO restarts after consecutive failures, with average iterations between restarts ranging from 42 on the 2D Toy problem to 2710 on the 60D Rover problem.
Loading 2002.08526v3…