ISSN:
1436-5057
Keywords:
65K05
;
Global optimization
;
interval arithmetic
;
branch and bound principle
;
best-first strategy
;
multisection
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Wir untersuchen den Einfluß verschiedener Strategien zur Auswahl der als nächstes zu teilenden Box in einem Branch-und-Bound-Verfahren zur globalen Optimierung. Ein theoretisches Resultat zeigt die Optimalität einer ‘best-first’-Strategie. Außerdem definieren wir einen Multisektions-Algorithmus zum Teilen von Boxen. Verschiedene Möglichkeiten für die Wahl der Halbierungsrichtungen und die Anzahl der Halbierungen werden anhand numerischer Ergebnisse verglichen, wobei deutlich wird, daß Multisektion der Bisektion immer überlegen ist. Zusätzlich identifizieren wir zwei wesentliche Eigenschaften für Teilungsstrategien, die zur Konvergenz von Algorithmen mit Multisektion führen.
Notes:
Abstract We study the influence of different strategies for selecting the next box for subdivision in an interval branch and bound method for global optimization. A theoretical result establishes the optimality of a ‘best-first’ strategy. Moreover, we define a multisection algorithm for subdivision of boxes. Different possibilities for the choice of bisection directions and the number of bisections are compared by numerical results showing that multisection is usually superior to bisection. In addition, we identify crucial properties of a division strategy which yield convergence of an algorithm with multisection.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02252252
Permalink