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, h_i ∈ C¹ (ℝⁿ, ℝ), |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) ≔ (h₁(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 x_k 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 x_k gegen eine Lösung \(\bar{x}\) des Ausgangsproblems, so konvergieren unter geeigneten Voraussetzungen die Produkte σ_k · h_i(x_k) für k → ∞ gegen die zugehörigen Lagrangeparameter \(-{\bar{\lambda }}_{i}\) von \(\bar{x}\). Ist einer davon betragsmäßig groß, so wird σ_k · h_i(x_k) instabil (man beachte, daß h_i(x_k) 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.

Man vergleiche dazu auch das Stichwort Barrierefunktion.