Index branch-and-bound algorithm for Lipschitz univariate global optimization with multiextremal constraints (Q1850829): Difference between revisions

\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.