Discrete Multi-Objective BO with an Outcome Constraint

[danemerson13]

Hello, I am using BoTorch to perform multi-objective Bayesian optimization for the following problem. There are seven input features, constrained to values between [0, max] in increments of 0.5, where max is typically in the range [6-10]. There are two outputs or objectives. One is a black box function which is modeled with a GP that takes as input the seven input features. The second objective is simply the sum of the seven input features. For our optimization problem we are trying to maximize both of the objectives. Additionally, there is an outcome constraint on the second (summation) objective that it must be less than the max value. I have a couple questions:

1). Context: With the discrete increments for the candidates, I found using the optimize_acqf_discrete() to be very computationally expensive. For reference, for max = [6,8,10] there are [50k, 245k, 888k] choices. This approach was attractive to me because the outcome constraint is inherently obeyed since I have already constrained the set of possible choices. Within optimize_acqf_discrete() I was able to increase the max_batch_size up to 2048 before I encountered a CUDA OOM error.

Question: Do you have any recommendations for efficiently running MOBO with a (large) discrete set of choices?

2.) Context: Instead of using the discrete approach, I tried to operate in a continuous space and then round the chosen candidates to 0.5 increments. Additionally, I need to impose the outcome constraint. I did this within the qLogNoisyExpectedHypervolumeImprovement() acquisition function definition with the following code:

def outcome_constraint(Z: torch.Tensor) -> torch.Tensor:
    return Z[..., 1] - 8.0

def step_mobo(model, train_X, raw_samples, num_restarts, batch_limit, max_iter):
    acq = qLogNoisyExpectedHypervolumeImprovement(
        model = model, 
        ref_point = REFERENCE, 
        X_baseline = train_X, 
        constraints = [outcome_constraint],
        prune_baseline=True
    )
    candidates, _ = optimize_acqf(
        acq_function=acq,   
        bounds=BOUNDS,
        q=BATCH_SIZE,
        num_restarts=num_restarts,
        raw_samples=raw_samples,
        options={"batch_limit": batch_limit, "maxiter": max_iter},
        sequential = True
    )

However, it seems that based on the candidates chosen at each iteration, this constraint is not being obeyed. Instead the model is choosing candidates with each of the seven features close to the maximum, leading to the sum feature being ~7*max.

Question: Why is the constraint not being strictly adhered to? Is this the correct way to impose the outcome constraint for my problem? Should I even be modeling this second summation feature with a GP model since it isn't really a black box function?

Let me know if you need additional clarifications to understand my problem or questions. Thank you for all of your work developing BoTorch and supporting this community :-)

[Balandat]

Do you have any recommendations for efficiently running MOBO with a (large) discrete set of choices?

We do have https://github.com/pytorch/botorch/blob/bc4b0c6cee13b25e4a8fb2283d29ea69be1ae803/botorch/optim/optimize.py#L1393
for cases where the cardinality is very large. This does random restarts plus local nearest neighbor search. This won't evaluate every combination but can work quite well - you'll want to compare this with the full enumeration approach on your problem. The X_avoid input allows you to provide combinations that are NOT feasible. This may be excessively large in some cases but might work in yours (one way this could be handled is instead of passing X_avoid modify optimize_acqf_discrete_local_search such that it takes a callable that can check for feasibility of a set of suggested points dynamically, but this may not be necessary in your case). @saitcakmak may have some more thoughts here.

Why is the constraint not being strictly adhered to? Is this the correct way to impose the outcome constraint for my problem?

Hmm not sure why this isn't working properly. One hypothesis would be that as the sum of the inputs is both an objective and a constraint, the HV computation will push very hard to increase all features, and if the scale of that is much larger than the penalty term imposed by the constraint feasibility weighting (which is an approximation) then it seems plausible that increasing the sum increases the weighted objective more than the constraint feasibility estimate penalizes it. You could try playing with the eta parameter to make the indicator approximation look more like an actual step function, but that will come at the cost of likely having some vanishing gradients far away from the constraint boundary (and possibly negative effect on the overall optimization): https://github.com/pytorch/botorch/blob/bc4b0c6cee13b25e4a8fb2283d29ea69be1ae803/botorch/acquisition/multi_objective/logei.py#L380-L385
cc @SebastianAment

Should I even be modeling this second summation feature with a GP model since it isn't really a black box function

No, if you have an analytic function of the constraint you shouldn't model that with a GP. One way would be to just use a
https://github.com/pytorch/botorch/blob/bc4b0c6cee13b25e4a8fb2283d29ea69be1ae803/botorch/models/deterministic.py#L59
if you stick that into a ModelList together with a GP model for your blackbox function. However, your constraint is already a linear constraint on the inputs, so you can just pass this as an inequality constraint to optimize_acqf: https://github.com/pytorch/botorch/blob/bc4b0c6cee13b25e4a8fb2283d29ea69be1ae803/botorch/optim/optimize.py#L515 and you don't need to model (or use the DeterministicModel crutch) at all. One downside of this is that this doesn't end up calling L-BFGS-B in scipy but SLSQP which can be pretty slow in some settings (though should be ok for yours).

One general comment I have is that if you have a discrete space with relatively few values for each parameter, then using the optimize-then-round approach can end up working quite poorly. So if you can just solve the actual discrete optimization problem I would recommend that.

[danemerson13]

Hi Max,

Thank you so much for the thorough response - it was incredibly helpful. I implemented a lot of the suggested changes and things are working exceptionally well now!

First, I properly formulated the second objective with the GenericDeterministicModel object and combined the two objectives using ModelList. In the continuous settings, this change also fixed the issue of the outcome constraint not being adhered to.

Second, the optimization is working remarkably well in the discrete setting with the local search method optimize_acqf_discrete_local_search. For my problem, the number of infeasible candidates was enormous (245k feasible/400M infeasible), so X_avoid was impossible to use. Instead I used the inequality_constraints option to impose the outcome constraint. Compared to the exhaustive set of choices using optimize_acqf_discrete, there is no significant difference in the quality of the hypervolume discovered, while the optimization is over 100x faster.

Here is the optimization using optimize_acqf_discrete_local_search:

And here it is using optimize_acqf_discrete:

[Balandat]

Awesome, great to hear! Thanks for the update!