Black-Box Optimization (BBO)
Black-Box Optimization (BBO) refers to a broad class of optimization problems in which the objective function—and possibly the constraints—are not available in explicit mathematical form. Instead, the problem can only be evaluated by querying a black box: given a candidate solution, the black box returns a numerical value (and sometimes feasibility information), but provides no derivatives, algebraic structure, or internal details.
This problem class arises frequently in simulation-based optimization, engineering design, machine learning hyperparameter tuning, algorithm configuration, and experimental sciences.
What is Black-Box Optimization (BBO)?
In a Black-Box Optimization problem, the decision maker seeks to minimize or maximize an unknown function subject to optional constraints. Key characteristics include:
- The objective function is unknown or implicit,
- Function evaluations may be expensive, noisy, or stochastic,
- Gradients and higher-order derivatives are typically unavailable,
- Constraints, if present, may also be implicit or simulation-based.
If the objective and constraints were explicitly defined and differentiable, the problem could be addressed using Nonlinear Programming (NLP) techniques. When discrete variables are involved, Black-Box problems may resemble Mixed-Integer Nonlinear Programs (MINLP), but without the structural information required by classical solvers.
Solving Black-Box Optimization (BBO) Problems
Since classical gradient-based or relaxation-based methods are generally inapplicable, Black-Box Optimization (BBO) relies on alternative techniques, including:
- Direct search methods, such as pattern search or simplex-based heuristics,
- Derivative-free optimization algorithms, including trust-region methods,
- Surrogate modeling, where an approximate model is learned from sampled data,
- Bayesian optimization, which balances exploration and exploitation using probabilistic models,
- Metaheuristics, such as genetic algorithms or simulated annealing.
When constraints or discrete decisions are present, hybrid methods combining black-box techniques with Constraint Programming (CP), MILP heuristics, or local search are sometimes used.
Black-Box Optimization (BBO) is particularly relevant when function evaluations are costly or noisy, and when building an accurate mathematical model is impractical. However, the lack of structural information typically leads to weaker optimality guarantees and higher computational effort compared to classical optimization methods.
As a result, Black-Box Optimization (BBO) is often used when no better-structured formulation is available, or as a complementary approach within hybrid or multi-stage optimization workflows.
Relationship to other problem classes
Black-Box Optimization (BBO) is defined more by information access than by mathematical structure:
- It contrasts with LP, MILP, NLP, and MINLP, where objective functions and constraints are explicitly known.
- It overlaps with derivative-free optimization, which focuses on solving problems without gradient information.
- It often interacts with simulation optimization, where objective evaluations require running a complex model or simulator.
Because of this, Black-Box Optimization (BBO) is not tied to a single mathematical formulation, but instead to the limitations imposed by the evaluation process.
Further reading and references
Jones, D. R., Schonlau, M., & Welch, W. J. (1998). Efficient Global Optimization of Expensive Black-Box Functions. Journal of Global Optimization, 13(4), 455–492.
The seminal paper introducing Bayesian optimization and surrogate-based approaches for expensive black-box problems.
Conn, A. R., Scheinberg, K., & Vicente, L. N. (2009). Introduction to Derivative-Free Optimization. SIAM.
A comprehensive reference on optimization methods that do not require derivatives, including direct search, trust-region, and model-based approaches commonly used in black-box optimization.
Rios, L. M., & Sahinidis, N. V. (2013). Derivative-Free Optimization: A Review of Algorithms and Comparison of Software Implementations. Journal of Global Optimization, 56(3), 1247–1293.
A widely cited survey of derivative-free optimization algorithms and their practical applications in black-box settings.