Direkt zum Inhalt

Lexikon der Mathematik: Penalty-Methoden

Familie von Verfahren zur Lösung von Optimierungsproblemen.

Es sei eine Funktion f(x) unter den Gleichungsnebenbedingungen \begin{eqnarray}x\in M:=\{z\in {{\mathbb{R}}}^{n}|{h}_{i}(z)=0,\,\,i\in I\}\end{eqnarray} mit f, hiC1 (ℝn, ℝ), |I| < ∞ zu minimieren.

Durch Hinzunahme eines Strafterms zur Zielfunktion (daher der Name „Penalty“) wird das Problem in einem ersten Schritt in eine unrestringierte Aufgabenstellung überführt. Dabei wird mit dem Strafterm das Nicht-Erfülltsein einer der Nebenbedingungen in einem Punkt x mit einem positiven Wert „geahndet“. Beispiel eines sogenannten äußeren Strafterms ist die Funktion \begin{eqnarray}\frac{1}{2}\cdot \sigma \cdot h{(x)}^{T}\cdot h(x)\end{eqnarray} (mit h(x) ≔ (h1(x),…,h|I| (x))T). Man minimiert dann iterativ unrestringierte Probleme \begin{eqnarray}f(x)+\frac{1}{2}\cdot {\sigma }_{k}\cdot {h}^{T}(x)\cdot h(x),\end{eqnarray} wobei σk mit zunehmender Schrittzahl k gegen ∞ gehe (dies stellt unter geeigneten Voraussetzungen sicher, daß Konvergenz gegen einen zulässigen Punkt \(\bar{x}\in M\) vorliegt).

Eine Schwierigkeit dieses Ansatzes ist der Umstand, daß die Lösungen xk der Teilprobleme nicht zulässig sein müssen (weshalb man von einem äußeren Strafterm spricht).

Bei beiden Vorgehensweisen muß mit numerischen Instabilitäten gerechnet werden, wenn der Straffaktor σk wächst. Konvergieren oben die xk gegen eine Lösung \(\bar{x}\) des Ausgangsproblems, so konvergieren unter geeigneten Voraussetzungen die Produkte σk · hi(xk) für k → ∞ gegen die zugehörigen Lagrangeparameter \(-{\bar{\lambda }}_{i}\) von \(\bar{x}\). Ist einer davon betragsmäßig groß, so wird σk · hi(xk) instabil (man beachte, daß hi(xk) gegen 0 konvergiert). Zur Lösung dieses Problems verwendet man erfolgreich Multiplikatormethoden.

Für Ungleichungsnebenbedingungen können ebenfalls spezielle Strafterme benutzt werden. Besitzt M (beschrieben durch Ungleichungen) etwa ein nichtleeres Inneres, so verwendet man häufig innere Strafterme, die umso größer werden, je näher ein zulässiger Punkt am Rand von M liegt.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

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.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.