Source-linked AI summary
A Bayesian approach to constrained single- and multi-objective optimization
Paul Feliot, Julien Bect, Emmanuel Vazquez
TL;DR
The paper addresses derivative-free constrained optimization with expensive black-box objectives and constraints under limited evaluation budgets. It proposes BMOO, combining extended domination, expected hyper-volume improvement, and sequential Monte Carlo computation. BMOO obtains good constrained single-objective results and good Pareto-front approximations on small evaluation budgets, while encountering identifiable difficulties on some test problems.
Problem
Derivative-free constrained optimization must handle expensive black-box objectives and constraints when only a limited number of evaluations is available.
Method
BMOO uses an extended domination rule and an expected hyper-volume improvement criterion, computed and optimized with sequential Monte Carlo techniques.
Results
BMOO achieves good results on constrained single-objective tests and good Pareto-front approximations for multi-objective problems under small evaluation budgets.
Takeaways & Limitations
The formulation can search for feasible solutions when none is initially available and recovers several existing Bayesian criteria as special cases.
Takeaways & Limitations
BMOO stalls on test problems g3mod, g10, g18, and PVD4, with identified causes and proposed remedies; high constraint counts can also leave too few feasible particles for candidate selection.
Abstract
from arXiv · showhide
This article addresses the problem of derivative-free (single- or multi-objective) optimization subject to multiple inequality constraints. Both the objective and constraint functions are assumed to be smooth, non-linear and expensive to evaluate. As a consequence, the number of evaluations that can be used to carry out the optimization is very limited, as in complex industrial design optimization problems. The method we propose to overcome this difficulty has its roots in both the Bayesian and the multi-objective optimization literatures. More specifically, an extended domination rule is used to handle objectives and constraints in a unified way, and a corresponding expected hyper-volume improvement sampling criterion is proposed. This new criterion is naturally adapted to the search of a feasible point when none is available, and reduces to existing Bayesian sampling criteria---the classical Expected Improvement (EI) criterion and some of its constrained/multi-objective extensions---as soon as at least one feasible point is available. The calculation and optimization of the criterion are performed using Sequential Monte Carlo techniques. In particular, an algorithm similar to the subset simulation method, which is well known in the field of structural reliability, is used to estimate the criterion. The method, which we call BMOO (for Bayesian Multi-Objective Optimization), is compared to state-of-the-art algorithms for single- and multi-objective constrained optimization.
1 Introduction
The paper targets derivative-free constrained optimization when black-box objectives and constraints are expensive, using very limited evaluation budgets. It proposes a Bayesian multi-objective method that unifies constraints and objectives through an extended domination rule and expected hyper-volume improvement.
- The problem is derivative-free multi-objective optimization of real-valued functions subject to multiple inequality constraints.
- Objective and constraint functions are continuous black boxes, with no gradient information available and expensive evaluations.
- The practical setting permits only a very limited evaluation budget, such as a few hundred evaluations.
- The proposed criterion handles multiple objectives and non-linear constraints simultaneously through an extended domination rule and dominated hyper-volume utility.
- The criterion supports searching for feasibility when none is known and recovers EI and constrained or multi-objective extensions once a feasible point is available.
2 Background literature
The background develops Bayesian optimization through one-step look-ahead expected improvement, then extends improvement to multi-objective dominated hyper-volume. Existing constrained formulations can remain uninformative before feasibility, while multi-objective integration becomes difficult as the number of objectives grows.
- Expected Improvement: Bayesian optimization models expensive functions probabilistically and selects evaluation points sequentially to reduce expected optimization error.
- Expected Improvement: Because the Bayes-optimal strategy becomes intractable beyond a few evaluations, Bayesian optimization commonly uses a one-step look-ahead strategy.
- Expected Improvement: The Expected Improvement criterion is the one-step look-ahead objective for the single-objective loss, with Gaussian-process models providing a closed-form expression.
- Multi-objective optimization: In multi-objective optimization, improvement is defined as the increase in dominated-region volume after a new evaluation.
- Multi-objective optimization: The multi-objective criterion reduces to ordinary EI in the single-objective case when at least one evaluation is below the upper bound.
- Multi-objective optimization: Analytical decomposition of multi-objective EI integration grows exponentially with the number of objectives, limiting its practicality beyond a few objectives.
- Constrained optimization: The constrained criterion based only on dominated hyper-volume remains constant until feasibility is found, so it cannot distinguish infeasible points by constraint violation.
3 An EI criterion for constrained multi-objective optimization
The paper extends Pareto domination to treat objectives and inequality constraints together, then uses the resulting expected hypervolume improvement criterion for constrained multi-objective Bayesian optimization. The criterion supports search before feasibility and reduces to established EI-based criteria after a feasible point is found.
- 3.1 Extended domination rule: The extended domination rule jointly represents objective values and constraint violations in a unified comparison space.It maps objective and constraint outcomes into a form handled by the usual Pareto rule.
- 3.1 Extended domination rule: Feasible solutions are compared by objective values, whereas non-feasible solutions are compared by their vectors of constraint violations.These cases correspond to properties (ii) and (iii) of the rule.
- 3.1 Extended domination rule: Feasible solutions always dominate non-feasible solutions under the extended rule.This ordering is property (iv) and is illustrated in Figure 2.
- 3.2 A new EI criterion: The expected improvement criterion integrates the probability that a model prediction dominates each point in the current non-dominated region.The region is defined inside bounded objective and constraint hyper-rectangles, with G_n containing the non-dominated points.
- 3.2 A new EI criterion: The criterion remains meaningful before and after the first feasible evaluation by assuming the all-zero constraint vector lies inside the bounded constraint region.This assumption supports a common improvement definition across infeasible and feasible search.
- 3.2 A new EI criterion: When at least one feasible point exists, the infeasible component vanishes, leaving feasibility-weighted objective-space improvement; in the single-objective case, classical constrained EI is recovered.With no constraints, the same construction reduces to the usual Pareto or multi-objective EI criterion.
4 Sequential Monte Carlo techniques to compute and optimize the expected improvement
The method estimates the expected improvement by sampling uniformly over nested non-dominated regions with Sequential Monte Carlo. It uses subset-simulation ideas and adaptive intermediate subsets to handle small surviving populations, then performs a discrete candidate search to optimize the criterion.
- 4.1 Computation of the expected improvement: High-dimensional integration is difficult because decomposition methods become exponentially more expensive as the combined objective-and-constraint dimension grows.The paper motivates Monte Carlo estimation when p + q is large.
- 4.1 Computation of the expected improvement: Uniform sampling over the non-dominated region becomes impractical with accept-reject methods when that region has small volume inside the bounding box.The acceptance rate then becomes small, especially as the output dimension increases.
- 4.1 Computation of the expected improvement: The algorithm uses a subset-simulation variant to estimate small-set volumes and construct uniform samples over nested non-dominated regions.Subset simulation is adapted from structural reliability and rare-event Monte Carlo methods.
- 4.1 Computation of the expected improvement: The basic Remove-Resample-Move procedure can fail when too few particles survive into the next region, so adaptive intermediate subsets limit the volume loss between levels.Intermediate subsets are inserted when the surviving count falls below a prescribed fraction of the population.
- 4.2 Maximization of the sampling criterion: The sampling criterion is optimized by a discrete search over a small set of good candidates supplied at each iteration by a sequential Monte Carlo algorithm.This avoids directly solving the highly multi-modal continuous optimization problem posed by the criterion.
- 4.2 Maximization of the sampling criterion: Weighted particles allow the Sequential Monte Carlo approximation to represent non-uniform target distributions as new observations update the particle weights.The empirical weighted distribution is designed to approximate the target distribution for sufficiently large particle populations.
5 Experiments
Experiments evaluate BMOO on a visual constrained multi-objective problem and benchmark suites, showing strong performance in many cases alongside identifiable difficulties tied to sampling and Gaussian-process modeling.
- 5.1 Settings: BMOO models objectives and constraints with independent Gaussian processes, initialized by a maximin Latin hypercube design of Ninit = 3d evaluations.The experiments use Matérn covariance functions with regularity ν = 5/2 and re-estimate parameters by MAP at each iteration.
- 5.2 Illustration: On the toy problem, BMOO samples all three disconnected feasible regions and achieves good Pareto-front coverage after only a few iterations.Starting without a feasible solution, the algorithm finds one after 10 iterations.
- 5.3 Mono-objective optimization benchmark: BMOO performs very well on most single-objective test problems, often approaching the best competitor and sometimes significantly outperforming both competitor classes.It notably outperforms both classes on g1, g6, g7, g9, g16 and WB4, but stalls on g3mod, g10, g18 and PVD4.
- 5.3 Mono-objective optimization benchmark: Stationary Gaussian-process modeling causes difficulties on g3mod, g10 and PVD4, while applying f → f^λ substantially improves performance in all three cases.The authors identify models based on ξ^λ, with λ estimated from evaluations, as a promising direction for further work.
- 5.4 Multi-objective optimization benchmark: The extended EHVI experiments favor SMC over MCSQP for finer Pareto-front convergence, while poor results on OSY reflect an ineffective uniform target density.The SMC approach also remains satisfactory with few particles, whereas random candidate selection performs much worse than sampling with mY = 200.
- 5.4 Multi-objective optimization benchmark: The SMC optimization approach generalizes across the extended EHVI, EMMI and WCPI criteria and is presented as an independently useful contribution for improvement-based sampling.Its sequential nature tracks concentration of the sampling criterion more efficiently and enables higher accuracy.
6 Conclusions and future work
The paper proposes BMOO, a Bayesian approach that unifies nonlinear constraints and multiple objectives through an extended domination rule and expected improvement criterion. Sequential Monte Carlo enables criterion computation, while experiments show useful performance but expose sampling-density, model-flexibility, and approximation-quality limitations.
- Conclusions: BMOO handles multi-objective optimization with nonlinear constraints using an extended domination rule and a new expected improvement formulation.The formulation also accommodates cases where no feasible solution is initially available and recovers several existing criteria as special cases.
- Conclusions: Sequential Monte Carlo computes and optimizes the criterion because its objective-space-and-constraint integral lacks a closed-form expression.The sampling procedure also addresses the criterion's potentially highly multimodal structure and draws on structural-reliability methods for rare-event estimation.
- Conclusions: BMOO finds feasible solutions and approximates Pareto fronts on small evaluation budgets, including problems with very small feasible regions and many constraints.The reported comparisons cover single-objective constrained test problems and multi-objective problems with nonlinear constraints.
- Future work: The numerical studies identify sampling-density choices in the input and output domains as open issues requiring further investigation.The paper specifically cites unsatisfactory results on the g18 and OSY cases.
- Future work: The quality of the sequential-Monte-Carlo approximation and its comparison with exact methods remain insufficiently studied for choosing calculation modes and sample sizes.The authors leave adaptive sample-size selection and switching rules between exact and approximate calculations for future work.
- Future work: Stationary Gaussian-process models lack flexibility on several benchmark cases, motivating warped, non-stationary, and deep Gaussian-process alternatives.The affected cases include g3mod, g10, PVD4, TwoBarTruss, and WeldedBeam.
A On the bounded hyper-rectangles Bo and Bc
The hyper-rectangles Bo and Bc bound objective and constraint spaces for the extended hyper-volume calculation. These bounds make the improvement finite and encode distinct contributions from feasibility and objective domination.
- Bounded hyper-rectangles: Bo and Bc are assumed to be bounded hyper-rectangles in objective and constraint spaces.The appendix frames these bounds as sets used in the hyper-volume construction.
- Infeasible evaluations: When an evaluated point is infeasible, the improvement includes a contribution associated with the constraints it satisfies.The text describes this contribution as a reward for feasibility with respect to each constraint.
- Infeasible evaluations: Both Bo and Bc must be bounded for the single-evaluation improvement |H1| to remain finite for every constraint-satisfaction pattern.Only the volume of Bo matters in the stated expression, not the actual lower objective-bound values.
- Infeasible evaluations: The improvement is discontinuous in the observations because constraint-related terms jump when feasibility status changes.The appendix notes a jump in the relevant product term when a constraint switches status.
- Feasible evaluations: For a feasible evaluation, the improvement combines domination of the entire infeasible subset with improvement in objective space.The two terms separate feasibility-related and objective-related gains.
B An adaptive procedure to set Bo and Bc
The adaptive procedure defines Bo and Bc from available evaluations and Gaussian-process posterior information over candidate points. It uses estimated ranges of objective and constraint functions to set the hyper-rectangle corners.
- Adaptive construction: Bo and Bc are adaptively defined using estimates of objective and constraint-function ranges.The procedure combines available evaluations with posterior quantiles from Gaussian-process models.
- Adaptive construction: The procedure uses posterior quantiles on the candidate set Xn together with n observed evaluation results to determine the corners of Bo.The text introduces the corner construction after assuming evaluation results ξ(Xi), 1 ≤ i ≤ n, are available.
C Mono-objective benchmark result tables
The appendix provides the complete single-objective benchmark tables, separating results from local optimization algorithms and Regis and reporting both feasibility and target attainment.
- Full benchmark tables: The full benchmark results are organized into tables for local optimization algorithms and algorithms from Regis (2014).These tables supplement the best-results presentation from Section 5.3.
- Reported measures: The tables report performance for finding feasible solutions and reaching the targets specified for the single-objective benchmark problems.The appendix identifies these problems as those listed in Table 1.
D Modified g3mod, g10 and PVD4 test problems
This section specifies modified g3mod, g10, and PVD4 formulations and lists evaluation-count tables for feasibility and target attainment across local and constrained optimization algorithms.
- Modified formulations: The g3mod, g10, and PVD4 formulations were modified to address modeling problems with BMOO.The stated rationale was to smooth local jumps.
- Modified formulations: The modified formulations are used in Section 5.3, with changes identified in boldface.
- Evaluation comparisons: Tables 11 and 13 report evaluations needed to find a first feasible point for several local and constrained optimization algorithms.Table 11 covers COBYLA, Active-Set, Interior-Point, and SQP; Table 13 covers COBRA-Local, COBRA-Global, and Extended-ConstrLMSRBF.
- Evaluation comparisons: Tables 12 and 14 report evaluations needed to reach the target for the same two groups of optimization algorithms.
- Problem definitions: The defined test problems use the plog function introduced with reference to Regis (2014).