Black-box combinatorial optimization using models with integer-valued minima
- PDF / 1,286,841 Bytes
- 15 Pages / 439.642 x 666.49 pts Page_size
- 95 Downloads / 263 Views
Black-box combinatorial optimization using models with integer-valued minima Laurens Bliek1
· Sicco Verwer1 · Mathijs de Weerdt1
Accepted: 4 September 2020 © The Author(s) 2020
Abstract When a black-box optimization objective can only be evaluated with costly or noisy measurements, most standard optimization algorithms are unsuited to find the optimal solution. Specialized algorithms that deal with exactly this situation make use of surrogate models. These models are usually continuous and smooth, which is beneficial for continuous optimization problems, but not necessarily for combinatorial problems. However, by choosing the basis functions of the surrogate model in a certain way, we show that it can be guaranteed that the optimal solution of the surrogate model is integer. This approach outperforms random search, simulated annealing and a Bayesian optimization algorithm on the problem of finding robust routes for a noise-perturbed traveling salesman benchmark problem, with similar performance as another Bayesian optimization algorithm, and outperforms all compared algorithms on a convex binary optimization problem with a large number of variables. Keywords Surrogate models · Bayesian optimization · Black-box optimization
1 Introduction Traditional optimization techniques such as first order methods or branch and bound make use of a known mathematical formulation of the objective function, for example by calculating the derivative or a lower bound. However, many objective functions in real-life situations have no complete mathematical formulation. For example, smart grids or railways are complex networks where every decision influences the whole network in such a way that the objective cannot be easily captured in one mathematical description. In such applications, we can observe the effect of decisions either in real life, or by running a simulation. Waiting for such a result can take some time, or may have some other cost associated with it. Furthermore, the outcome of two observations with the same decision variables may be different due to randomness that may be present in the real-life scenario, or due to Laurens Bliek
[email protected] 1
Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, Van Mourik Broekmanweg 6, 2628 XE Delft, The Netherlands
L. Bliek et al.
artificial randomness in the simulation. Such problems have been approached using methods such as black-box or Bayesian optimization [1], simulation-based optimization [2], and derivative-free optimization [3]. Here, a model fits the relation between decision variables and objective function, and then standard optimization techniques are used on the model instead of the original objective. These so-called surrogate modeling techniques have been applied successfully to continuous optimization problems in signal processing [4], optics [4], machine learning [5], robotics [6], and more. However, it is still an on-going research question on how these techniques can be applied effectively to combinat
Data Loading...
