Given an ordered input set of boolean values $S$ of length $|S|$,

I want to minimize a function $f(S)$

while maximizing the number of $True \in S$

constrained by $|True \in S|$ $\ge$ $threshold$

I understand this is NP-hard to manage with the $2^{|S|}$ possible inputs, but know some of them will be nonsensical.

Is there a way to frame this problem as a bayesian optimization problem for generating a set of booleans which minimize $f$ in such a way that I can avoid most of this parameter space?


Bayesian optimization over binary vectors is still a problem of major research. One potential way was proposed in https://arxiv.org/pdf/1806.08838.pdf. The key idea here is to represent the surrogate model as a second order model $\sum_i \alpha_j x_j + \sum_i \sum_j \alpha_{ij} x_i x_j$ which allows the acquisition function optimization to be approximately solved by a semidefinite relaxation.

Regarding your constraints $|True \in S| \geq threshold$, local search allows you to search over vectors which satisfies the constraints but might be sub-optimal.

The source code of above paper is available here https://github.com/baptistar/BOCS.

  • $\begingroup$ great read, thank you! $\endgroup$ – Anisotropic May 15 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.