Bayesian optimization under mixed constraints with a slack-variable augmented Lagrangian
An augmented Lagrangian (AL) can convert a constrained optimization problem into a sequence of simpler (e.g., unconstrained) problems, which are then usually solved with local solvers. Recently, surrogate-based Bayesian optimization (BO) sub-solvers have been successfully deployed in the AL framework for a more global search in the presence of inequality constraints; however, a drawback was that expected improvement (EI) evaluations relied on Monte Carlo. Here we introduce an alternative slack variable AL, and show that in this formulation the EI may be evaluated with library routines. The slack variables furthermore facilitate equality as well as inequality constraints, and mixtures thereof. We show our new slack "ALBO" compares favorably to the original. Its superiority over conventional alternatives is reinforced on several mixed constraint examples.
This manuscript proposes a Bayesian optimization approach to problems with mixed inequality and equality constraints. The main tool used in the approach is a slack-variable version of the augmented Lagrangian, which allows the incorporation of mixed constraints and has some advantages over the use of the augmented Lagrangian without slack variables. A detailed description of the proposed method is given, including guidance on how to efficiently solve various subproblems that arise via standard library routines (in this case in R). A set of experiments on various difficult problems demonstrate that the proposed method works better than several alternatives, including one proposed only earlier this year.
This manuscript is very interesting, extremely well written, and solves an important problem, namely Bayesian optimization with mixed constraints. The main contribution of the paper is an extension of the recently-published ALBO technique for incorporating inequality constraints into Bayesian optimization problems to handle equality constraints as well. The approach is to incorporate the equality constraints via the addition of slack variables into the augmented Lagrangian. Remarkably, the addition of these variables leads to some computational niceties even in the case that there are no equality constraints at all. Specifically, the calculation of expected improvement in this setting is simplified and may be resolved via quadrature rather than via Monte Carlo sampling. This is a nice result and discussed at length, including specific recommendations for implementation. Further, the authors provide guidance on how to solve for the slack variables, which removes the only real barrier to adopting the proposed slack-variable formulation wholesale. A set of well-designed and insightful experiments establish that the proposed method is superior to (in some cases markedly so) to alternatives, in terms of the performance as a function of the number of function evaluations.  The paper is well-written and easy to read, with only a few minor issues, which I list below. The paper is also remarkably complete, providing a nice level of detail in all parts of the discussion, and helpful, more-detailed pointers in the supplementary material. I only have a few suggestions for how the paper could be strengthened. One is that I think some brief discussion regarding the wall-clock time spent computing the EI would be of interest. The authors do a good job convincing me that this is readily implemented and presumably quite fast, although I don't have a good intuition for how slow the "library routines" are. It would also be helpful to put this time in perspective with the time required by the Monte Carlo approximation used in ALBO. Again, I think this comparison would only be in the favor of the authors. Also regarding wall-clock time, it would be interesting to see how this compares end-to-end across the tested methods, perhaps on only one of the experiments.  I also have a minor complaint about the computation of EI in (2). The EI in that expression is being computed against f_min, defined to be min {y_1 ... y_n}. This is not really correct due to the noise in the observations. Rather, f_min, if I am to interpret its meaning from the notation, is a random variable with an admittedly annoying distribution. In fact, I would hazard to guess that y_min is usually an optimistic estimate of f_min in Bayesian optimization settings (and things get even more troublesome if the noise is heteroskedastic!). The result is that the computation in (2) is measuring the value of points against an inflated benchmark, which I believe would lead to over-enthusiastic exploration. This is a well-known fact that is almost always swept under the rug, and indeed the formulation in (2) is widespread. Nonetheless, I feel compelled to complain on philosophical grounds.  Minor corrections:  - Line 45: I find "Here we dub that method ALBO" somewhat awkward. I might recast as "We will refer to this method as ALBO." - Lime 137: I find "re-develop" a bit awkward as well. Perhaps "rewrite?" - Under line 153: Please typeset (13) using the amsmath align environment rather than eqnarray, which is giving you unsightly spacing around the ='s. - I might suggest adding a little negative space to the _f subscripts used on Y and \sigma; they're typeset with too much space to my eyes (inspect 6\rho\sigma_f(x) on line 166 for an example). - Line 170: "how \lambda and and \rho updated" -> "how \lambda and \rho are updated" - The sans serif font should probably be scaled down a bit. I believe this is a problem with the NIPS style file and will email the proceedings chair.