Bayesian optimization with sum constraint

I have an issue with the implementation of a particular problem to be optimized with a Bayesian Optimization (it could be argued that it is not the best choice for this particular case, but let's say I have no other choices).

Now, I have N decisional variables. These variables control the way a time series is quantized into discrete values. Without going into much details, I want to optimize a performance index related to the way the signal is quantized. So, there is an optimal quantization, which does not consist in equally spaced intervals, and I want to find this quantization.

Now, each decisional variable is the space between two dotted lines in the figure above (in that example, ). Ideally, this signal has a maximum value B. Therefore, each decisional variable is bounded in the interval . Moreover, they can be set to integer (no need for more precision).

For the very nature of the problem, I want the maximum possible generalization, so I would like the optimizer to take into account every possible combination of variables, with the only constraint being of course the following:

where are the variables. Still, I want every to assume any possible value in the defined interval. So for instance extreme choices where one variable is equal to B and the other ones are 0 should be feasible and possibly generated.

If I try to set the number of variables to or so (I would need to work with similar numbers), the Bayesian Optimization fails at attempting to find feasible sets of parameters: it eventually generates 10000 combinations of variables, but no combinations (or at most 1-2 of them) satisfy the sum constraint. Now, is there a way to increase the number of randomly generated variables (let's say from 10000 up to 10^7 or even more), so that enough combinations are produced satisfying this constraint?

Thank you in advance!

Answer 1

[Alan Weiss]

This sounds like a balls-in-buckets problem. You have up to B balls to place into N buckets. The occupancy (number of balls) of bucket i is .

What I am suggesting is that you can generate random occupancies by this balls-in-buckets mechanism. The Statistics and Machiie Learning Toolbox™ mnrnd function can generate these random samples for fixed B and N. For example, if and , you can generate 10 random samples as follows:

N = 50;
B = 20;
p = ones(1,N)/N;
A = mnrnd(B,p,10);

The resulting matrix A has 10 rows, each row represents one of your variables a.

If, instead, you are looking to generate all possible occupancies, ask again. But I think that this mechanism gives you a good way of thinking about how to generate feasible samples.

Alan Weiss

MATLAB mathematical toolbox documentation

[Federico]

This seems the variables generation algorithm that solves the problem! Is there a way I can implement that function into the bayesopt() variables generation procedure?

EDIT: Just to be on the same line, what I am doing right now is the following, with :

B  = 150;
a1 = optimizableVariable('a1',[0,B],'Type','integer');
a2 = optimizableVariable('a2',[0,B],'Type','integer');
a3 = optimizableVariable('a3',[0,B],'Type','integer');

[Alan Weiss]

You can provide initial points for the algorithm. See the InitialX option. Be careful, you need to pass a table of initial points.

Alan Weiss

MATLAB mathematical toolbox documentation

[Federico]

Thank you Alan.

I tried, but at the second iteration, the algorithm starts again by selecting random points and eventually fails. Is there way to directly modify the acquisition function code, so I can control the random points generation procedure?

[Alan Weiss]

I am not sure, but you might be able to get your optimization going by using Conditional Constraints. In your conditional constraint function, check that the passed points satisfy the constraint, and if not, change them so that they do.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation