Direkt zum Inhalt

Lexikon der Mathematik: Lösungsverifikation in der globalen Optimierung

in der Intervallrechnung die Einschließung des absoluten Minimums m* = f(x*) einer stetigen Funktion f : b → ℝ und der zugehörigen Minimalstellen x* ∈ b.

Dabei bezeichnet b einen n-komponentigen Intervallvektor. Abschwächung der Glattheit, Berücksichtigung von Nebenbedingungen, aber auch Spezialisierung von f auf lineare Funktionen (lineare Programmierung, duales Problem) sind ebenfalls möglich.

Ein einfaches Verfahren besteht darin, b in kleinere Intervalle xα zu unterteilen, und die Intervallauswertung f(xα) von f über xα zu betrachten.

Gilt xα, xβb und \begin{eqnarray}\text{max}\{y|y\in {\bf{\text{f}}}({{\bf{\text{x}}}}_{\alpha })\}\lt \text{min}\{y|y\in {\bf{\text{f}}}({{\bf{\text{x}}}}_{\beta })\}\end{eqnarray} so enthält xβ sicher keine Minimalstelle. Durch wiederholte Verfeinerung der Unterteilung von b kann man sukzessive Intervallvektoren aussondern, die keine solche Stelle enthalten.

Den Prozeß kann man über ein Listenkonzept systematisieren und in vielfacher Weise verfeinern. So kann man statt der Intervallauswertung im Fall einer differenzierbaren Funktion f die Mittelwertform oder eine andere zentrierte Form verwenden, die den Wertebereich f (b) weniger stark überschätzt (Inneneinschließung).

[1] Herzberger, J. (ed.): Topics in Validated Computations. North-Holland Amsterdam, 1994.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte