An algorithmic framework based on primitive directions and nonmonotone line searches for black-box optimization problems
- PDF / 835,445 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 51 Downloads / 162 Views
An algorithmic framework based on primitive directions and nonmonotone line searches for black-box optimization problems with integer variables Giampaolo Liuzzi1 · Stefano Lucidi2 · Francesco Rinaldi3 Received: 2 February 2018 / Accepted: 6 February 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract In this paper, we develop a new algorithmic framework to solve black-box problems with integer variables. The strategy included in the framework makes use of specific search directions (so called primitive directions) and a suitably developed nonmonotone line search, thus guaranteeing a high level of freedom when exploring the integer lattice. First, we describe and analyze a version of the algorithm that tackles problems with only bound constraints on the variables. Then, we combine it with a penalty approach in order to solve problems with simulation constraints. In both cases we prove finite convergence to a suitably defined local minimum of the problem. We report extensive numerical experiments based on a test bed of both bound-constrained and generally-constrained problems. We show the effectiveness of the method when compared to other state-of-the-art solvers for black-box integer optimization. Keywords Derivative free optimization · Black box problems · Integer variables · Nonmonotone line search Mathematics Subject Classification 90C56 · 90C10 · 90C30
B
Giampaolo Liuzzi [email protected] Stefano Lucidi [email protected] Francesco Rinaldi [email protected]
1
Istituto di Analisi dei Sistemi ed Informatica “A. Ruberti”, Consiglio Nazionale delle Ricerche, Via dei Taurini 19, 00185 Rome, Italy
2
Dipartimento di Ingegneria Informatica Automatica e Gestionale “A. Ruberti”, “Sapienza” Università di Roma, Via Ariosto 25, 00185 Rome, Italy
3
Dipartimento di Matematica “Tullio Levi-Civita”, Università di Padova, Via Trieste, 63, 35121 Padua, Italy
123
G. Liuzzi et al.
1 Introduction Many real-world problems coming from different fields (e.g., engineering, economics, biology) can be modeled using black-box functions. Those functions represent the experimentally obtained behavior of a system and in practice are given by means of specific simulation tools. Hence no internal or analytical knowledge for the functions is provided. Furthermore, evaluating the function at a given point is usually (or might be) an expensive task in terms of computational resources, and only a limited budget of evaluations is available for the optimization. On top of that, real systems are often described by means of unrelaxable integer variables (e.g., number of nurses in a ward, number of coils in a magnet, and so on) that need to be properly handled. When dealing with this kind of problems, it is neither possible to cut away part of the feasible set nor to get an optimality gap for the solutions (like the exact algorithmic frameworks in integer programming usually do). Certifying global optimality is exceptionally difficult in the black-box setting, e
Data Loading...
