Branching and bounding improvements for global optimization algorithms with Lipschitz continuity properties
| Autor: | Jaroslav Fowkes, Nicholas I. M. Gould, Coralia Cartis |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Hessian matrix
Mathematical optimization Control and Optimization Branch and bound Applied Mathematics Nonconvex programming Context (language use) Management Science and Operations Research Lipschitz continuity Lipschitzian optimization Computer Science Applications symbols.namesake Quadratic equation Bounding overwatch Ball (bearing) symbols Parallel branch and bound Global optimization Mathematics |
| Zdroj: | Cartis, C, Fowkes, J M & Gould, N I M 2015, ' Branching and bounding improvements for global optimization algorithms with Lipschitz continuity properties ', Journal of Global Optimization, vol. 61, no. 3, pp. 429-457 . https://doi.org/10.1007/s10898-014-0199-6 Cartis, C, Fowkes, J & Gould, N 2013, Branching and Bounding Improvements for Global Optimization Algorithms with Lipschitz Continuity Properties . vol. 13-010 . |
| DOI: | 10.1007/s10898-014-0199-6 |
| Popis: | We present improvements to branch and bound techniques for globally optimizing functions with Lipschitz continuity properties by developing novel bounding procedures and parallelisation strategies. The bounding procedures involve nonconvex quadratic or cubic lower bounds on the objective and use estimates of the spectrum of the Hessian or derivative tensor, respectively. As the nonconvex lower bounds are only tractable if solved over Euclidean balls, we implement them in the context of a recent branch and bound algorithm (Fowkes et al. in J Glob Optim 56:1791---1815, 2013) that uses overlapping balls. Compared to the rectangular tessellations of traditional branch and bound, overlapping ball coverings result in an increased number of subproblems that need to be solved and hence makes the need for their parallelization even more stringent and challenging. We develop parallel variants based on both data- and task-parallel paradigms, which we test on an HPC cluster on standard test problems with promising results. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|