Optimization Under Unknown Constraints

By Robert B. Gramacy, Herbert K. H. Lee. 2010

165 citations recorded by the source corpus.

Optimization of complex functions, such as the output of computer simulators, is a difficult task that has received much attention in the literature. A less studied problem is that of optimization under unknown constraints, i.e., when the simulator must be invoked both to determine the typical real-valued response and to determine if a constraint has been violated, either for physical or policy reasons. We develop a statistical approach based on Gaussian processes and Bayesian learning to both approximate the unknown function and estimate the probability of meeting the constraints. A new integrated improvement criterion is proposed to recognize that responses from inputs that violate the constraint may still be informative about the function, and thus could potentially be useful in the optimization. The new criterion is illustrated on synthetic data, and on a motivating optimization problem from health care policy.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Ocean Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Ocean Engineering

Citations in the corpus

Scalable Bayesian Optimization Using Deep Neural Networks (2015, methodology): “Recent work (Gelbart et al., 2014; Snoek, 2013; Gramacy & Lee, 2010) has developed approaches for modeling unknown constraints in GP-based Bayesian optimization by learning a constraint classiﬁer and then discounting expected improvement by the probability of constraint violation.”
Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, background): “Gramacy and Lee [62] proposed the integrated expected conditional improvement (IECI) acquisition function: This gives the change in expected improvement from observing x under the density h .”
Google Vizier: A Service for Black-Box Optimization (2017, background): “In the case of Bayesian Optimization, previous work either assigns them a particularly bad objective value, attempts to incorporate a probability of infeasibility into the acquisition function to penalize points that are likely to be infeasible [3], or tries to explicitly model the shape of the infe”
Constrained Bayesian Optimization with Noisy Experiments (2017, background): “Gramacy and Lee (2011) recognize this problem and propose replacing f ∗ in (1) with the GP mean estimate of the best function value: g ∗ = min x µ f ( x ).”
Bayesian Optimization and Semiparametric Models with Applications to Assistive Technology (2014, methodology): “Indeed this is a major motivation for the Bayesian treed GP approach developed by Gramacy and Lee [2008]. A major consideration is how to determine partitioning points for the various GPs.”
HyperPower: Power- and memory-constrained hyper-parameter optimization for neural networks (2017, methodology): “Note that uncertainty can be also encapsulated by replacing the indicator functions with probabilistic Gaussian models as in [17], whose implementation is already supported by the used tool [4] and whose analysis we leave for future work.”
Learning search spaces for Bayesian optimization: Another view of hyperparameter transfer learning (2019, methodology): “They would require resorting to constrained BO modelling [16, 13, 14], e.g., to optimize the acquisition function over the ellipsoid, which would add signiﬁcant complexity to the procedure.”
A benchmark of kriging-based infill criteria for noisy optimization (2013, methodology): “The IAGO strategy maximizes the gain of information, i.e. selects for the next evaluation the point that minimizes the expected conditional entropy of the minimizer; the IECI evaluates by how much a candidate measurement at a given point would affect the expected improvement over the design space.”
Quantile-Based Optimization of Noisy Computer Experiments With Tunable Precision (2013, methodology): “A more rigorous alternative, as noted in Gramacy and Lee ( 2010b ) and Gramacy and Polson ( 2011 ), consists of computing the EI based on the joint distribution of (min( Y ( X n )), Y ( x )) conditional on <inline-graphic xmlns:xlink="http://www.”
Predictive Entropy Search for Bayesian Optimization with Unknown Constraints (2015, methodology): “2) in the toy problem described in Gramacy et al. (2014). We seek to minimize the function f(x) = x1 + x2, subject to the constraint functions c1(x) ≥ 0 and c2(x) ≥ 0, given by c1(x) = 0.”
Recent Advances in Bayesian Optimization (2022, background): “Using the same principle, integrated expected conditional improvement in [15] defines the expected reduction in EI under the constrained satisfaction probabilities, allowing the unfeasible area to provide information.”