(10d) Exact Penalty Bayesian Optimization: No-Regret Data-Driven Optimization with Unknown Equality and Inequality Constraints

In many engineering applications, we must optimize a set of design parameters where the true system structure is unknown. For example, this can occur in calibration of expensive simulators [1], automated controller tuning [2], material design and discovery [3], as well as many other applications. Under these circumstances, we can only query the objective f(x) (which we seek to minimize) by picking specific inputs from our design space. These so-called “black-box” objective functions are often expensive to query, requiring computationally expensive simulations, or costly real-world experiments. In this low-data regime setting, we must make the trade-off between exploring the design space and exploiting our current knowledge of where f(·) is predicted to be optimal.

Bayesian Optimization (BO) is a family of algorithms that can solve black-box problems by modeling f(x) using Gaussian Processes (GP) [4], which represent a non-parametric and probabilistic class of surrogates that can provide effective models in data-scarce scenarios. Using the queried samples of f(·), BO constructs a statistical surrogate (most commonly a GP model) for the objective function. The GP model thus gives us a probabilistic distribution of the objective function; we can couple this with an acquisition (or expected utility) function α(x), which intelligently optimizes the location of our next sample point by trading off between exploration of our design space and exploitation of the current model predictions.

In addition to having a fully or partially unknown objective function, many engineering problems also contain expensive-to-evaluate constraints c(x). This can significantly complicate the optimization process in practice; not only must we explore the objective f(x), but we must now also identify a feasible region in our design space by also actively exploring the constraint region c(x). The most common strategy for extending BO to handle constrained problems is to model each constraint separately with an independent GP. Although a significant amount of work on extending BO to constrained problems has been done, it remains an open question for how to best factor the constraints into the definition of the acquisition function.

We can roughly sort the different methods for handling constraints in BO into two main categories: explicit and implicit methods. Implicit methods incorporate constraints directly into the acquisition function through a meri-type function, resulting in an unconstrained optimization sub-problem. In the literature, merit-type functions can include a probability of feasibility on the acquisition [5] or follow an augmented Lagrangian approach for BO [6]. However, these methods can run into sensitivity issues, as these merit functions must be tuned specifically to the scale of the current problem, which can be difficult to determine a-priori. Explicit methods, on the other hand, involve optimizing the acquisition function α(x) while imposing a hard constraint on the GP approximations of the unknown constraints. A popular method includes using the mean function GP constraints [7]; however, when data is scarce, solely relying on the mean function can result in overly conservative solutions. Although many options exist for handling constraints in the black-box setting, no rigorous performance guarantees have been established for any constrained BO method to the best of our knowledge, which makes it difficult to choose from the suite of available methods as well as to decide what technical innovations are most needed. Furthermore, most constrained BO methods do not differentiate between equality and inequality constraints; although we can always convert between these two representations, this often leads to important challenges including lack of feasibility of the sub-problem that can be difficult to handle in practice.

In this work, we introduce a novel approach to constraint handling for BO, which we refer to as Exact Penalty BO (EPBO). Taking advantage of the theory of exact penalty functions [8], we show how EPBO can be interpreted as relaxed version of explicit constraint handling approaches. However, differing from other explicit methods, we show EPBO can always provide a feasible solution to the optimization sub-problem in the presence of both equality and inequality constraints, which can be efficiently obtained by introducing slack variables into the formulation. Additionally, we introduce the notion of penalty-based regret, which is an extension of standard regret that measures the difference between the current recommended solution and the true global minimum. We show that, under certain assumptions on the structure of the penalty term and the class of covariance functions that can be used to model the objective and constraints, we can guarantee that the penalty-based regret is a sub-linearly decaying function of the total number of iterations. A direct consequence of this result is that we can guarantee that there exists a finite iteration in which we are arbitrarily close to the constrained global minimum (i.e., EBPO is a convergent, asymptotically consistent algorithm under mild assumptions). Finally, we demonstrate the that a practical implementation of EPBO can outperform alternative constrained BO methods on a benchmark constrained global optimization problem.

[1] B. Sakhdari and N. L. Azad, “Adaptive Tube-Based Nonlinear MPC for Economic Autonomous Cruise Control of Plug-In Hybrid Electric Vehicles,” IEEE Trans. Veh. Technol., vol. 67, no. 12, pp. 11390–11401, 2018, doi: 10.1109/TVT.2018.2872654.

[2] F. Sorourifar, G. Makrygirgos, and A. Mesbah, “A Data-Driven Automatic Tuning Method for MPC under Uncertainty using.”

[3] A. M. Schweidtmann, A. D. Clayton, N. Holmes, E. Bradford, R. A. Bourne, and A. A. Lapkin, “Machine learning meets continuous fl ow chemistry : Automated optimization towards the Pareto front of multiple objectives,” Chem. Eng. J., vol. 352, no. July, pp. 277–282, 2018, doi: 10.1016/j.cej.2018.07.031.

[4] C. E. Rasmussen and C. K. . Williams, Gaussian Process for Machine Learning, vol. 7, no. 5. 2000.

[5] J. R. Gardner, M. J. Kusner, Z. E. Xu, K. Q. Weinberger, and J. P. Cunningham, “Bayesian Optimization with Inequality Constraints,” vol. 32, 2014.

[6] V. Picheny, R. B. Gramacy, and C. O. May, “Bayesian optimization under mixed constraints with a slack-variable augmented Lagrangian,” 2018.

[7] M. J. Sasena, P. Papalambros, and P. Goovaerts, “Exploration of Metamodeling Sampling Criteria for Constrained Global Optimization,” vol. 0273, 2010, doi: 10.1080/03052150211751.

[8] G. Di, “Exact penalty functions in constrained optimization*,” vol. 27, no. 6, pp. 1333–1360, 1989.