Optimal and sub-optimal stopping rules for the multistart algorithm in global optimization
type: Item
instance of: scholarly article
title: Optimal and sub-optimal stopping rules for the multistart algorithm in global optimization
zbMATH Open document ID: 0785.90086
DOI: 10.1007/BF01581094
published in: Mathematical Programming. Series A. Series B
publication date: 1993-06-29T00:00:00Z
review text: This paper proposes stopping rules for the multistart algorithm for the global optimization problem `\(\text{Max}_{x\in K} f(x)\), \(K\subset R^ k\), \(k\geq 1\)'. The algorithm consists in sequentially performing local optimizations from randomly choosen starting points. The algorithm will eventually succeed in locating the global optimum. A crucial point is the decision at each step whether to stop or continue performing local optimizations. The authors introduce a cost criterion \(L(t^ 1,t^ 2,\dots,t^ n; c)=-t^*_ n+ nc\), where \(t_ i\) is the function value at the local optimum during the \(i\)th local search and \(c>0\) is a fixed constant. \(n\) is the number of local searches. Stopping rules can be deduced by considering the \(t_ i\)s as realizations of discrete random variables. This approach leads to the definition of two stopping rules. The 1-step rule gives good results in terms of computational cost vs. final accuracy.
Mathematics Subject Classification ID: 90C30
Mathematics Subject Classification ID: 90-08
zbMATH DE Number: 219857
zbMATH Keywords: stopping rules
zbMATH Keywords: multistart algorithm
zbMATH Keywords: global optimization
author: Bruno Betrò
author: Fabio Schoen
reviewed by: Yves Cherruault
MaRDI profile type: Publication
cites work: Statistical decision theory. Foundations, concepts, and methods
cites work: Sequential stopping rules for the multistart algorithm in global optimisation
cites work: A stochastic technique for global optimization
cites work: Bayesian stopping rules for multistart global optimization methods
cites work: Q5631860
cites work: Q5512461
cites work: Stopping eules for the multistart method when different local minima have different function values
cites work: A statistical estimate of the structure of multi-extremal problems
full work available at URL: https://doi.org/10.1007/bf01581094
OpenAlex ID: W1994654315
description: scientific article; zbMATH DE number 219857