3.5. Penalty-Verfahren

Die grundlegende Idee hinter Penalty-Verfahren besteht darin, ein restringiertes Optimierungsproblem in ein unrestringiertes Problem umzuschreiben. Sollte das ohne Probleme möglich sein, ständen uns sofort alle Techniken und Algorithmen der unrestringierten Optimierung zur Verfügung. Um (3.1) möglichst unverändert umzuformen, definieren wir dazu einen Penalty-Parameter \(\alpha>\) und betrachten

(3.38)\[\min_{x\in\R^n}\quad f(x) + \frac{\alpha}{2}\sum_{i=1}^m \max\big\{0,g_i(x)\big\}^2 + \frac{\alpha}{2}\sum_{i=1}^p h_i(x)^2.\]

Wir haben hierbei der Einfachheit halber \(\Omega=\R^n\) angenommen. Wir stellen fest, dass die beiden Strafterme in (3.38) für zulässige Punkte \(x\in X\) stets Null sind, ungeachtet der Wahl von \(\alpha\). Für unzulässige Punkte hingegen liefern sie einen positiven (also für die Minimierung schlechten) Beitrag zum Funktionswert. Wählen wir \(\alpha>0\) also groß genug, so können wir hoffen, dass Lösungen von (3.38) sehr nahe bei Lösungen von (3.1) liegen. Allerdings führt eine zu große Wahl von \(\alpha\) zu einer zunehmend schlechteren Konditionierung des Penalty-Problems.

Die obige Wahl, ein sogenannter \(\ell^2\)-Penalty (denn alle Penalty-Terme sind quadratisch) hat den angenehmen Vorteil, dass alle Terme stetig differenzierbar sind. Leider bedeutet dies im Allgemeinen, dass exakte Lösung und Lösung des Penalty-Problems für kein endliches \(\alpha>0\) übereinstimmen. Deswegen betrachten wir im Folgenden den \(\ell^1\)-Penalty

(3.39)\[\min_{x\in\R^n}\quad f(x) + \alpha\sum_{i=1}^m \max\big\{0,g_i(x)\big\} + \alpha\sum_{i=1}^p \vert h_i(x)\vert.\]

Dieser ist in vielen Fällen (für eine geeignete Wahl von \(\alpha\)) exakt, d.h., Lösungen des unrestringierten Optimierungsproblems bleiben erhalten. Um (3.39) zu lösen, müssen wir allerdings Algorithmen entwickeln, die mit nicht-differenzierbaren Funktionen umgehen können.