Penalty-Verfahren

mini|Illustration des Penalty-Verfahrens bei der Minimierung einer Funktion; der zulässige Bereich sind alle Stellen größer oder gleich 1. In der numerischen Mathematik und speziell der mathematischen Optimierung sind Penalty-Verfahren (, auch Penalty-Methode oder Strafterm-Methode) eine Klasse von Methoden zur Lösung von Optimierungsproblemen mit Nebenbedingungen, bei denen eine Folge von deutlich einfacheren Problemen (mit potentiell unzulässigen Lösungen) gelöst wird, deren Lösungen aber wenigstens gegen die (zulässige) Lösung des ursprünglichen Problems konvergieren.

In der Theorie der Optimierungsprobleme unterscheidet man zwischen Optimierung (also Minimierung oder Maximierung) einer Funktion mit Nebenbedingungen, das heißt, das Optimum muss auf einer Menge von zulässigen Punkten angenommen werden, und Optimierung ohne Einschränkungen auf dem gesamten Quellraum. Dabei ist die Optimierung ohne Nebenbedingungen um ein Vielfaches leichter als solche mit Nebenbedingungen und kann mit naiveren, oft aus der Analysis bekannten Verfahren gelöst werden.

Für die Optimierung mit Nebenbedingungen sind die Penalty-Verfahren nun eine Methode, die Arbeit auf eine Lösung eines Optimierungsproblems ohne Nebenbedingungen zurückzuführen. Dafür werden die Nebenbedingungen in die Optimierungsfunktion „eingebunden“; konkret wird mittels einer Penalty-Funktion das Verlassen des zulässigen Bereichs (bezogen auf das ursprüngliche Optimierungsziel) so sehr „bestraft“, dass die gefundene Lösung trotz fallengelassener Nebenbedingungen „von alleine“ im (zumindest beinahe) zulässigen Bereich zu finden ist. Lässt man diesen Penalty mit der Zeit immer größer werden, konvergiert die Folge der Beinahe-Lösungen tatsächlich mit der Zeit gegen die Lösung des eigentlichen Optimierungsproblems.

Restriktivere Verwandte der Penalty-Verfahren sind die Barriereverfahren (auch ), bei denen die Klasse der zulässigen Punkte überhaupt nicht verlassen werden darf, aber dennoch formal ein Optimierungsproblem ohne Nebenbedingungen gelöst wird.

Definition

Sei eine Funktion von einem -Vektorraum (häufig der euklidische Raum für große ) in die reellen Zahlen. Sei eine Teilmenge; Elemente von heißen zulässige Punkte. OBdA wollen wir auf minimieren, d. h. wir suchen , sodass .

Sei ein Penalty-Parameter und eine Penalty-Funktion, d. h. für und für .

Dann definiert die globale Optimierung (ohne Nebenbedingung) von einen Penalty-Schritt. Ein Penalty-Verfahren mit Penalty-Funktion ist dann gegeben dadurch, dass die Penalty-Schritte für wachsende iterativ durchgeführt werden, wobei die Lösung des letzten Verfahrens als Startpunkt für das nächste genutzt werden kann.

Die Lösung dieser Optimierungsprobleme konvergiert gegen einen zulässigen Punkt, wenn . (Wir nehmen an, dass das Ursprungsproblem und alle Teilprobleme überhaupt gelöst werden können.)

Konkrete Darstellung

Üblicherweise kodiert man die Nebenbedingungen durch eine Aufteilung in Ungleichungs- und Gleichungs-Kriterien, d. h. es gibt und , sodass die Nebenbedingungen erfüllt genau dann, wenn für alle und für alle . Die Menge der zulässigen Punkte ist dann gegeben durch .

Für eine Penalty-Funktion möchte man i. d. R., dass ihre Größe (also der Strafterm) weiter anwächst, je mehr man von den zulässigen Punkten abweicht.

Die gängigste Möglichkeit für die Penalty-Funktion ist , wobei . (Diese Funktion ist Ck für .) In der Regel verwendet man dabei Quadratic Loss, also .

Es gibt aber auch viele andere Möglichkeiten. Obwohl in der überwiegenden Mehrheit der relevanten Probleme eine Charakterisierung wie oben gegeben ist, sind theoretisch auch Penalty-Funktionen denkbar, die weniger auf die Struktur von angewiesen sind. Ein Beispiel ist die Funktion , die für jeden normierten Raum und jede abgeschlossene Teilmenge als Penalty-Funktion herangezogen werden könnte.

Eigenschaften

Abgesehen davon, dass Penalty-Verfahren auf die vielen bekannten Verfahren zur globalen Optimierung zurückgreifen können, hat ihre genaue Umsetzung einige Vorteile: Bei exakter Arithmetik wird die Lösung für größere Penalty-Parameter nur „besser“; zum Beispiel bleibt eine bereits zulässige Lösung auch für alle größeren Parameter zulässig Sobald die Lösung eines Penalty-Schritts ein zulässiger Punkt ist, kann das Verfahren terminieren, da auf zulässigen Punkten gilt und somit das zulässige, globale Minimum von insbesondere das eingeschränkte Minimum von ist Ist auf nach oben beschränkt (), werden unzulässige Punkte zwangsweise jedem zulässigen Punkt unterliegen. Das liegt daran, dass für einen nicht zulässigen Punkt die Penalty-Funktion positiv ist und somit für diesen Punkt ein existiert, sodass

Barriereverfahren mini|Die Lösungen der Barriere-Schritte nähern sich dem zulässigen Minimum, das sich vom globalen Minimum der Funktion unterscheidet Einen formal ähnlichen Gedanken wie Penalty-Verfahren verfolgen die sogenannten Barriere-Verfahren. Erneut optimiert man eine Hilfsfunktion, die die Nebenbedingungen „enthält“, auf dem (fast) gesamten Quellraum mit gängigen Verfahren.

Im Gegensatz zu einer Straffunktion wie oben addiert man hier eine Barriere-Funktion zu der zu minimierenden Funktion auf, die schon am Rand der zulässigen Punkte unbeschränkt wächst und damit insbesondere alle unzulässigen Punkte ausschließt. Statt einen Penalty-Parameter zu erhöhen, muss man den positiven Barriere-Parameter immer kleiner werden lassen, um eine Konvergenz gegen korrekte Lösungen auch nahe am (oder auf dem) Rand zu ermöglichen.

Wie genau ein Barriere-Verfahren aussieht, hängt auch von der Struktur der Nebenbedingungen ab (etwa bei konvexen oder affinen Problemen). Sicher kann man aber nur Ungleichungs-Nebenbedingungen betrachten, da für Gleichungskriterien kein sinnvoller Begriff des „Inneren“ existiert. Stattdessen muss man diese Kriterien auf andere Weise berücksichtigen, was oft dadurch ermöglicht wird, dass die Gleichungen durch affin-lineare Funktionen ausgedrückt werden können.

Barriere-Funktionen Seien die Nebenbedingungen wie oben, d. h. . Die Barrierefunktion stellt man dann mithilfe einer skalaren Barriere-Funktion auf, also mit . Die für das Verfahren genutzte Funktion folgt dann als , und der entsprechende Schritt im Barriereverfahren für den Barriere-Parameter ist dann .

Eine Möglichkeit für die skalare Barrierefunktion ist die mit , deutlich gängiger ist aber die logarithmische Barrierefunktion .

Inneres Die Durchführung eines Barriere-Schritts liefert eine Lösung für die Minimierung von ohne Nebenbedingungen. Da die Optimierungsfunktion außerhalb des zulässigen Bereichs unendlich ist, werden solche Punkte niemals als Lösung auftreten. Mit demselben Argument treten aber auch keine Punkte auf, für die mindestens eine Ungleichungsbedingung aktiv ist, also für ein gilt. Insgesamt befindet sich die Lösung eines Barriere-Schritts also immer im strikt zulässigen Bereich , der manchmal auch als Inneres bezeichnet wird. Jedoch kann er sowohl größer ( und ist echter Untervektorraum) als auch kleiner () sein als das topologische Innere von .

Randpunkte können aber – genau wie Punkte, die zumindest sehr nah am Rand liegen – als korrektes Minimum für das ursprüngliche Minimierungsproblem auftreten. In diesem Fall kann anders als bei Penalty-Verfahren keine exakte Lösung erreicht werden; indem jedoch , wird der Einfluss der Barriere-Funktion im strikt zulässigen Bereich immer geringer. Folglich „dürfen“ Näherungslösungen näher an den Rand, bevor die Strafe durch die Barriere so hoch wird, dass die Punkte für das Minimum unattraktiv werden.

Bei entsprechenden Voraussetzungen erwartet man also für korrekte Lösungen mit aktiven Nebenbedingungen, dass Penalty-Verfahren von außen und Barriere-Verfahren von innen gegen diese Lösung konvergieren.

Quellen

Kategorie:Numerische Mathematik Kategorie:Optimierungsalgorithmus