- Efficient global unconstrained black box optimization Morteza Kimiaei (kimiaeim83univie.ac.at) Arnold Neumaier (Arnold.Neumaierunivie.ac.at) Abstract: For the unconstrained optimization of black box functions, this paper presents a new stochastic algorithm called VSBBO. In practice, VSBBO matches the quality of other state-of-the-art 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 VSBBO 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 with the best competitive global solvers. For smooth, everywhere defined functions, it is proved that, with probability arbitrarily close to 1, the basic version of our algorithm finds with $O(nR\epsilon^{-2})$ function evaluations a point with gradient 2-norm $\le\epsilon$, where $n$ is the dimension and $R$ is the number of random directions used in each iteration. In the smooth convex case, this number improves to $O(nR\epsilon^{-1})$ and in the smooth (strongly) convex case to $O(nR\log \epsilon^{-1})$. This matches known recent complexity results for reaching a slightly different goal, namely the expected gradient 2-norm $\le\epsilon$. Keywords: Derivative-free optimization, complexity bounds, global optimization, sufficient decrease, line search Category 1: Global Optimization (Stochastic Approaches ) Category 2: Nonlinear Optimization (Unconstrained Optimization ) Citation: Download: [PDF]Entry Submitted: 08/28/2018Entry Accepted: 08/29/2018Entry Last Modified: 07/21/2020Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.