Optimal and sub-optimal stopping rules for the Multistart algorithm in global optimization

Optimal and sub-optimal stopping rules for the Multistart algorithm in global optimization

0.00 Avg rating0 Votes
Article ID: iaor19932006
Country: Netherlands
Volume: 57
Issue: 3
Start Page Number: 445
End Page Number: 458
Publication Date: Dec 1992
Journal: Mathematical Programming (Series A)
Authors: ,
Keywords: optimization
Abstract:

In this paper the problem of stopping the Multistart algorithm for global optimization is considered. The algorithm consists of repeatedly performing local searches from randomly generated starting points. The crucial point in this algorithmic scheme is the development of a stopping criterion; the approach analyzed in this paper consists in stopping the sequential sampling as soon as a measure of the trade-off between the cost of further local searches is greater than the expected benefit, i.e. the possibility of discovering a better optimum. Stopping rules are thoroughly investigated both from a theoretical point of view and from a computational one via extensive simulation. This latter clearly shows that the simple 1-step look ahead rule may achieve surprisingly good results in terms of computational cost vs. final accuracy.

Reviews

Required fields are marked *. Your email address will not be published.