Projects per year
Abstract
For the unconstrained optimization of black box functions, this paper introduces a new randomized algorithm called VRBBO. In practice, VRBBO matches the quality of other stateoftheart algorithms for finding, in small and large dimensions, a local minimizer with reasonable accuracy. Although our theory guarantees only local minimizers our heuristic techniques turn VRBBO into an efficient global solver. In very thorough numerical experiments, we found in most cases either a global minimizer, or where this could not be checked, at least a point of similar quality to the best competitive global solvers. For smooth, everywhere defined functions, it is proved that, with probability arbitrarily close to 1, a basic version of our algorithm finds with O(n epsilon(2)) function evaluations a point whose unknown exact gradient 2norm is below a given threshold epsilon > 0, where n is the dimension. In the smooth convex case, this number improves to O(n log epsilon(1)) and in the smooth (strongly) convex case to O(n log n epsilon(1)). This matches known recent complexity results for reaching a slightly different goal, namely the expected unknown exact gradient 2norm is below a given threshold epsilon > 0. Numerical results show that VRBBO is effective and robust in comparison with the stateoftheart local and global solvers on the unconstrained CUTEst test problems of GOULD et al. (Comput Optim Appl 60:545557, 2014) for optimization and the test problems of JAMIL and YANG (Int J Math Model Numer Optim 4:150, 2013) for global optimization with 25000 variables.
Original language  English 

Pages (fromto)  365–414 
Number of pages  50 
Journal  Mathematical Programming Computation 
Volume  14 
Issue number  2 
DOIs  
Publication status  Published  3 Feb 2022 
Austrian Fields of Science 2012
 101016 Optimisation
 101019 Stochastics
Keywords
 ALGORITHM
 CONVERGENCE
 DERIVATIVEFREE OPTIMIZATION
 DIRECT SEARCH
 Derivativefree optimization
 EVOLUTION
 GLOBAL OPTIMIZATION
 SOFTWARE
 WORSTCASE COMPLEXITY
 complexity bounds
 global optimization
 line search
 sufficient decrease
Projects
 1 Finished

Vienna Graduate School on Computational Optimization
Pflug, G., Stelzer, V., Henzinger, M., Bot, R. I., Bomze, I., Schichl, H., Neumaier, A., Raidl, G. R., Scarinci, T., Geiersbach, C., Gabl, M., Böhm, A., Nguyen, D. K., Kimiaei, M., Neumann, S., Djukanovic, M., Horn, M., Glanzer, M., Birghila, C., Brandstätter, G., Luipersbeck, M., Meier, D., Ponleitner, B., Goranci, G., Kahr, M., Klocker, B. & Hungerländer, P.
1/03/16 → 29/02/20
Project: Research funding