Discrete Bayesian Optimization algorithms and applications

When dealing with expensive-to-evaluate objective functions in optimization problems, a large class of models gathered under the name of Bayesian Optimization (BO) is efficiently able to approximate the black-box objective function and compute the optimum. This is done using a surrogate model, namely a statistical model for modelling the objective function, and an acquisition function that let us move into the feature space. The most common surrogate models are Gaussian Processes. These algorithms work well over continuous domains, however, when dealing with discrete or categorical variables, these techniques become unsuccessful and different approaches and settings are required. The Separable Bayesian Optimization algorithm (SBO) is our proposal to overcome the BO limitations. It moves from the idea of considering the discrete variables as nodes of a graph, over which a statistical model is built. This model is assumed to be a structure given to the objective function and thanks to the properties of Gaussian Processes, the main steps of BO are implemented. The thesis starts with an overview of Bayesian Optimization and its main components: surrogate model and acquisition function. In particular, the emphasis is on Gaussian Processes as surrogate models. Afterwards, the SBO algorithm is outlined in all its theoretical steps: a description of the implementation using Python is also provided. The second part of the thesis deals with some applications with discrete and black-box optimization problems. For example, the SBO algorithm is applied to the sparsification of Ising models, namely an approximation of the reticular graph that is used to assemble Ising models, which are models built to describe the thermodynamic properties of magnetic systems. Another application has been proposed by the TIM group: the problem is to realize a self-optimizing mobile network that is capable of set the best configuration of tilts for the antennas in order to get the best performances in terms of capacity and coverage (Capacity and Coverage Optimization).