Optimization Online


Efficient global unconstrained black box optimization

Morteza Kimiaei (kimiaeim83***at***univie.ac.at)
Arnold Neumaier (Arnold.Neumaier***at***univie.ac.at)

Abstract: For the unconstrained global 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, with reasonable accuracy, a global minimizer in small and large dimensions, or at least in the majority of cases a point as good as competing algorithms. For smooth, everywhere defined functions, it is proved that, with probability arbitrarily close to 1, one finds with $O(n\epsilon^{-2})$ function evaluations a point with gradient 2-norm $\le\epsilon$. In the smooth convex case, this number improves to $O(n\epsilon^{-1})$ and in the smooth strongly convex case to $O(n\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 )


Download: [PDF]

Entry Submitted: 08/28/2018
Entry Accepted: 08/29/2018
Entry Last Modified: 03/29/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society