Source-linked AI summary
Optimization Under Unknown Constraints
Robert B. Gramacy, Herbert K. H. Lee
TL;DR
Optimization under unknown constraints requires learning both an expensive objective and whether each input is feasible. The paper uses Gaussian-process regression and classification with Bayesian sequential design, then proposes integrated expected improvement to use information from constraint-violating inputs. The method is illustrated on synthetic data and a health-care policy optimization problem, while convergence remains supported mainly by a heuristic.
Problem
Optimization under unknown constraints is less studied because expensive simulator evaluations must reveal both the real-valued response and whether a constraint is violated.
Method
The paper combines Gaussian-process surrogates for the objective and constraints with Bayesian sequential design and an integrated improvement statistic.
Results
The integrated conditional expected improvement statistic is illustrated on synthetic data and a health-care policy optimization problem.
Takeaways & Limitations
Constraint-violating evaluations can still inform the objective and improve decisions about promising feasible locations.
Takeaways & Limitations
Convergence theory for statistical optimization algorithms is scant, and the paper's convergence assessment relies on a heuristic that works well in its examples.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses expensive optimization when both objective responses and constraint satisfaction are learned through noisy evaluations. It proposes sequential Gaussian-process modeling and an integrated improvement criterion that can value constraint-violating evaluations for their information about feasible optima.
- Expensive joint evaluations must reveal both the real-valued response and whether an input satisfies the constraint.
- Unknown objective and constraint relationships are approximated with regression and classification surrogates using a small number of evaluations.The process sequentially adds new observations and can stop at convergence or when resources are exhausted.
- Constraint-violating inputs can still be useful because their responses inform the objective function and may reduce uncertainty about the best feasible location.Thus, evaluating outside the constraint region is not necessarily wasteful.
- Standard expected improvement cannot directly measure how an infeasible candidate improves information about feasible locations.
- The paper proposes an integrated improvement statistic that combines uncertainty about the objective and constraints in sequential decisions.The paper illustrates the approach on synthetic data and describes its application to a health-care policy problem.
2 Previous Work
Previous work establishes Gaussian-process surrogates and expected improvement for sequential optimization, while constrained extensions face analytical and computational complications. The paper builds on these tools using predictive distributions and simulation-based treatment of noisy responses.
- Stationary Gaussian processes model computer-experiment responses by specifying covariance between input locations.Conditioned on observed data, the GP supplies a predictive distribution for a new response.
- Expected improvement selects candidate inputs by the predicted improvement over the current minimum under the GP surrogate.For deterministic responses, improvement is max{fmin − Z(x), 0}.
- The EI calculation takes expectation over the GP predictive distribution and can be maximized to choose the next design point.The selected observation is then added to the design and the surrogate is updated.
- Noisy responses require estimating the nugget and treating the current minimum as random, which removes the analytical tractability of the standard EGO calculation.Monte Carlo methods provide a way to proceed in this setting.
- Earlier constrained surrogate approaches modeled constraints as additional responses, but tractable EI calculations required independence assumptions.
3 Integrated Expected Conditional Improvement
The integrated expected conditional improvement (IECI) generalizes expected improvement by measuring how adding candidate x reduces improvement at reference locations y. It supports constrained optimization by weighting reference locations according to feasibility and can select informative candidates outside the constraint region.
- Conditional improvement: The conditional predictive distribution Z(y|x) represents the response at reference location y if candidate x is added before its response is observed.Under the GP surrogate, its predictive variance can be deduced without observing z(x), enabling expected conditional improvement calculations.
- Integrated expected conditional improvement: IECI evaluates expected improvement at reference locations after candidate x is added, then aggregates those conditional improvements over a density g(y).The candidate is selected by maximizing the aggregated statistic, under a monotonicity condition ensuring conditional improvement does not increase.
- Constraints: For constrained optimization, g(y) can be uniform on the feasible region or assign greater weight to reference locations with higher feasibility probability.This lets candidates be evaluated by their effect on improvement across feasible reference locations rather than only at the candidate itself.
- Conditional improvement: Observing z(x) reduces predictive variance at y by an amount determined by the separation between x and y, providing a basis for measuring candidate influence.The GP covariance structure supplies this distance-dependent variance reduction.
- Choosing fmin: Using fmin as the minimum posterior predictive mean preserves the required monotonicity, unlike the noisy observed minimum whose monotonicity is not guaranteed.The paper therefore uses the minimum of the posterior mean-predictive surface throughout the remaining development.
- Illustration: In the known-constraint illustration, EI is maximized near x = 2.75 outside C, whereas IECI is maximized at x = 3.75 because it produces the greatest average reduction over C.The IECI reference locations are restricted to the feasible region, so the selected point need not itself satisfy the constraint.
4 Dealing with Unknown Constraints
The paper extends its integrated improvement criterion to unknown constraints by combining regression and classification Gaussian-process surrogates with sequential inference. Synthetic examples illustrate how the method allocates samples near feasible minima and constraint boundaries while tracking optimization progress.
- An Appropriate Constraint Surrogate, and Sequential Inference: The unknown-constraint extension incorporates a classification surrogate into the integrated expected improvement calculation through Monte Carlo inference.The joint parameter vector includes both regression and constraint-surrogate parameters, with constraint labels added to the data.
- An Appropriate Constraint Surrogate, and Sequential Inference: A classification Gaussian process complements the canonical regression Gaussian process for modeling constraint satisfaction.The classification surrogate estimates the probability that an input satisfies the constraint.
- An Appropriate Constraint Surrogate, and Sequential Inference: Sequential Monte Carlo replaces repeated MCMC refitting, enabling faster online posterior updates for the regression and classification models.The authors describe particle learning as producing fast online posterior summaries and, in some cases, lower Monte Carlo error.
- Illustrations and Examples: After 80 samples in the 1-d example, most post-initial-design samples concentrate near two local minima, with a few outside the constraint region.The estimated constraint surface and decreasing expected improvement provide a heuristic indication of convergence.
- Illustrations and Examples: After 125 samples in the 2-d example, sampling concentrates near feasible minima and the constraint boundary, while the progress meter indicates that additional improvement remains possible.Very few samples fall outside the unknown constraint region except near local minima.
5 Health Policy Optimization
The health policy application calibrates six simulator parameters while enforcing elasticity constraints that can only be evaluated by running the simulator. Fitted response and constraint-violation surfaces identify promising parameter regions, while the progress meter provides a heuristic convergence check.
- Application setup: The COMPARE simulator predicts health insurance choices and costs, and the optimization focuses on six calibration parameters selected as important by collaborators.The parameters cover adult and child utility tuning for ESI, individual, and public programs.
- Application setup: The objective minimizes prediction discrepancy subject to negative insured elasticities and positive uninsured elasticities, which are unknown until simulation runs.These simulation-dependent constraints place the problem in the unknown-constraints setting.
- Fitted surfaces: Figure 6 indicates that both ESI parameters should be relatively high, the child individual parameter relatively low, and the remaining three parameters are less important near the fitted minimum.The plots show pairwise slices with the other four parameters held near a minimum-producing value.
- Fitted surfaces: Figure 7 estimates constraint-violation probabilities in routinely sampled regions, with the highest risks at large ESI values, jointly small individual and child-individual values, and corner values for public parameters.Violating sampled points are marked with asterisks, while sparsely sampled regions are omitted because their estimates are strongly influenced by the prior mean.
- Convergence: After about 250 samples, the progress meter appears to bottom out, but reducing later up-spikes could increase confidence that the constrained global minimum was found.The meter is evaluated over 500 optimization rounds and serves as a heuristic rather than a formal convergence guarantee.
6 Discussion
The paper introduces IECI for optimization with unknown constraints and illustrates it on synthetic examples and a health care policy problem. The discussion emphasizes that convergence theory remains limited and that the method is chiefly supported by a heuristic that worked in the examples.
- Contribution: IECI integrates conditional expected improvement so candidate evaluations can account for improvement at reference locations believed to satisfy unknown constraints.It provides a less greedy alternative to standard EI without requiring a tuning parameter.
- Evidence: The method was illustrated on two synthetic examples and a motivating health care policy problem, with an implementation provided in the plgp CRAN package.
- Limitations: Convergence understanding for statistical optimization algorithms is limited, and IECI is supported by a heuristic that appeared to work well in the reported examples.The authors identify convergence analysis as an area requiring further work.
- Extensions: Potential extensions include modeling constraints using both inputs and responses, handling hidden simulation failures, and using surrogate models beyond Gaussian processes.The discussion gives dynamic trees as one promising alternative for regression and classification.