Multi-objective optimization for a discrete input space with multiple objectives and a equality constraint

[varun-go]

Hello,

I am attempting to perform multi-objective optimization for a problem with four (or more) objectives. The input for my problem is high-dimensional (~30 dimensions) and discrete. The input space can be represented as {0,1}^d, where d is the number of dimensions, and each input dimension can take on 1 of two values. I would additionally like to enforce an equality constraint on the design space (for example, the sum of the entries in the input vector should be equal to a specific integer value). The objective is to find the Pareto front for this problem, and 

I have a few questions.

1. 
Acquisition function.
   I was initially thinking of using the MESMO acquisition function -- the reference paper for the MESMO acquisition function provides an example of a similar discrete input space but with a dimensionality of 10. However, it appears that this acquisition function (qMultiObjectiveMaxValueEntrop) is now deprecated (as per the API). My understanding is that the qLowerBoundMultiObjectiveMaxValueEntropySearch is preferred. 

However, even if the MESMO acquisition function was usable (i.e., using an older version of BoTorch) or the qLowerBoundMultiObjectiveMaxValueEntropySearch is used, are these acquisition functions suitable for discrete input spaces? Based on discussion Constructing the `sample_pareto_frontiers` for the `qMultiObjectiveMaxValueEntropy` acquisition function #2405 and the API, it appears that the callable for MESMO needs to be supplied to the qMultiObjectiveMaxValueEntropy acquisition function to sample candidate points for the Pareto front. However, I am not sure if this can be achieved with a discrete input space. For the design problem that I have mentioned, would a different set of acquisition functions be better suited? 


2. Constraints. 


   I have a range of constraints that I would like to apply to the design space for different optimization scenarios. For example, I would like the sum of the entries in the input vector to equal a specific value. Based on discussion Discrete Multi-Objective BO with an Outcome Constraint #2777, I understand that the optimize_acqf_discrete_local_search could be used. However, my understanding is that for the local neighbor search, each entry input vector is randomly modified based on the discrete_choices input argument (issue [Feature Request] can optimize_acqf_discrete_local_search accept more kinds of constraints? #1285). The constraints could be applied via the inequality_constraints argument. However, I have received errors for certain constraints due to insufficient input vectors. I think this issue is due to how the local neighbor search is conducted, but I would like to verify if that is correct. If this issue does not have a resolution, is it recommended to provide a large sample of feasible input vectors from the design space and use the optimize_acqf_discrete function instead? In this case, the optimization of the acquisition function is limited to the input vectors provided, but I can ensure that the constraints on the design space are met.

Any suggestions/comments would be helpful. Thank you!

[Balandat]

How costly is it to evaluate your underlying black box function? How many evaluations do you think are feasible? I'm also curious if you can share a bit more about the particular application/problem that you're working on.

are these acquisition functions suitable for discrete input spaces?

In general yes, these acquisition functions don't require the input space to be continuous. You won't be able to do gradient-based optimization of the acquisition function but you should be able to just use something like optimize_acqf_discrete_local_search as you suggest.

For qMultiObjectiveMaxValueEntropy you should still be able to sample Pareto frontiers - I am not sure why this would be an issue with a discrete domain. But either way, this has been deprecated for a reason, and
qLowerBoundMultiObjectiveMaxValueEntropySearch does not require defining such a sampling function. Are there any issues with qLowerBoundMultiObjectiveMaxValueEntropySearch?

However, I have received errors for certain constraints due to insufficient input vectors. I think this issue is due to how the local neighbor search is conducted, but I would like to verify if that is correct.

Can you provide a minimal repro of the issue that you're running into? optimize_acqf_discrete_local_search should be able to take these kinds of constraints into account (provided ofc that they're not extremely hard to satisfy so it's hard to find any feasible point).

If this issue does not have a resolution, is it recommended to provide a large sample of feasible input vectors from the design space and use the optimize_acqf_discrete function instead? In this case, the optimization of the acquisition function is limited to the input vectors provided, but I can ensure that the constraints on the design space are met.

Yes, that would be the next best thing. You may need to evaluate a lot of points but that should be relatively quick and you can throw a lot of compute at this if you need to.