Index branch-and-bound algorithm for Lipschitz univariate global optimization with multiextremal constraints
type: Item
instance of: scholarly article
title: Index branch-and-bound algorithm for Lipschitz univariate global optimization with multiextremal constraints
zbMATH Open document ID: 1033.49038
DOI: 10.1023/A:1012391611462
author: Yaroslav D. Sergeyev
author: Domenico Famularo
author: Paolo Pugliese
published in: Journal of Global Optimization
publication date: 2002-12-15T00:00:00Z
review text: \textit{S. A. Pijavskij} hat bereits 1972 gezeigt [``An algorithm for finding the absolute extremum of a function'', USSR Comput. Math. Math. Phys. 12(1972), No. 4, 57--67 (1973; Zbl 0282.65052)]{}, wie man durch eine iterative Reihe von stückweise linearen Stützfunktionen \(\psi(x)\) das globale Minimum einer Funktion \(F(x)\) mit \(x\in [a,b]\) von oben und unten eingrenzen kann, wobei nur vorausgesetzt werden muss, dass \(F(x)\) einer Lipschitzbedingung im Intervall \([a,b]\) genügt. Das Problem mit Nebenbedingungen \(\min\{f(x) : x\in [a,b]\), \(g_j(x)\leq 0\), \(1\leq j\leq m\}\), wobei nun \(f\) und alle \(g_j\) Lipschitzbedingungen genügen, kann mittels der Index Methode von \textit{R. G. Strongin} [``Numerical methods for multiextremal nonlinear programming problems with nonconvex constraints'', Lect. Notes Econ. Math. Syst. 255, 278--283 (1985; Zbl 0581.90089)]{} auf ein unstetiges Problem ohne Nebenbedingungen zurückgeführt werden. Obwohl die Unstetig\-keits\-punkte der so definierten Objektivfunktion nicht bekannt sind, ist es möglich, durch adaptiv verbesserte Indexstützfunktionen obere und untere Schranken für das globale Minimum von \(f(x)\) mit den Nebenbedingungen \(g_j(x)\) zu berechnen. Das Konvergenzverhalten dieses Index Branch and Bound Algorithmus (IBBA) wird bewiesen und die numerischen Vorteile von IBBA gegenüber Pijavskij's Methode (hier mit PEN bezeichnet) werden an Hand von mehreren differenzierbaren und nicht-differenzierbaren Beispielen illustriert.
Mathematics Subject Classification ID: 49M05
Mathematics Subject Classification ID: 90C26
zbMATH DE Number: 1845257
zbMATH Keywords: global optimization
zbMATH Keywords: multiextremal constraints
zbMATH Keywords: branch-and-bound algorithms
zbMATH Keywords: index scheme
reviewed by: Franz Selig
describes a project that uses: Global Optimization Toolbox For Maple
MaRDI profile type: Publication
full work available at URL: a:1012391611462
OpenAlex ID: W168211946
Recommended article: Branch- and bound algorithms for solving global optimization problems with Lipschitzian structure
Recommended article: On the investigation of the practical convergence of an algorithm of global optimization
Recommended article: Q4295107
Recommended article: About branch and bound method
Recommended article: Q4868537
Recommended article: Some problems of solving Lipschitzian global optimization problems using the branch and bound method
Recommended article: Q3796975
Recommended article: Q5688498
Recommended article: A branch-and-bound algorithm for bound constrained optimization problems without derivatives
Recommended article: Q4855843
description: scientific article; zbMATH DE number 1845257