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 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 )


Download: [PDF]

Entry Submitted: 08/28/2018
Entry Accepted: 08/29/2018
Entry Last Modified: 07/21/2020

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