Lagrange-Relaxierung

Lagrange-Relaxierung (auch Lagrange-Relaxation) bezeichnet ein Verfahren der mathematischen Optimierung, bei dem ausgewählte Nebenbedingungen eines Optimierungsproblems entfernt und stattdessen mithilfe von Lagrange-Multiplikatoren in die Zielfunktion aufgenommen werden. Die entfernten Nebenbedingungen werden so gewählt, dass das verbleibende Problem einfacher gelöst oder in voneinander unabhängige Teilprobleme zerlegt werden kann. Das Verfahren wird insbesondere in der gemischt-ganzzahligen und kombinatorischen Optimierung verwendet.

Die Lösung eines relaxierten Problems muss die entfernten Nebenbedingungen nicht erfüllen. Sein Optimalwert liefert bei geeigneter Vorzeichenwahl jedoch eine Schranke für den Optimalwert des ursprünglichen Problems. Durch die Optimierung der Lagrange-Multiplikatoren wird versucht, diese Schranke zu verbessern.

Mathematische Formulierung

Gegeben sei das Minimierungsproblem

Die Menge enthält alle Bedingungen, die nicht relaxiert werden. Dazu können weitere Gleichungen und Ungleichungen sowie Ganzzahligkeitsbedingungen gehören. Die Bedingungen werden als die zu relaxierenden oder komplizierenden Nebenbedingungen ausgewählt.

Für einen Vektor nichtnegativer Lagrange-Multiplikatoren

lautet die zugehörige Lagrange-Funktion

Bei festem ergibt sich das relaxierte Problem zu

Ist für das ursprüngliche Problem zulässig, so gilt wegen und

Daraus folgt die Schrankeneigenschaft

Jeder zulässige Multiplikatorvektor liefert somit eine untere Schranke für ein Minimierungsproblem. Die bestmögliche durch diese Relaxierung erzeugte Schranke ist der Optimalwert des Lagrange-dualen Problems

Nach der schwachen Dualität gilt

Bei einem Maximierungsproblem kehren sich die Richtungen der Schranken entsprechend um. Werden Gleichungsbedingungen relaxiert, sind die zugehörigen Multiplikatoren nicht auf nichtnegative Werte beschränkt.

Eigenschaften der dualen Funktion

Die duale Funktion ist konkav, da sie das punktweise Infimum von Funktionen ist, die für festes affin in sind. Ist endlich, ist außerdem stückweise linear. An den Übergängen zwischen den Teilstücken ist sie im Allgemeinen nicht differenzierbar.

Zwischen dem primalen und dem dualen Optimalwert kann eine Dualitätslücke bestehen. Dies tritt insbesondere bei nichtkonvexen und ganzzahligen Problemen auf. Die Maximierung von liefert deshalb nicht notwendigerweise den Optimalwert des ursprünglichen Problems. Auch ein Minimierer des relaxierten Problems muss die entfernten Nebenbedingungen nicht erfüllen.

Für ein lineares ganzzahliges Problem mit einer endlichen Menge und den relaxierten Bedingungen lässt sich die optimale Lagrange-Schranke unter üblichen Zulässigkeits- und Beschränktheitsvoraussetzungen als

darstellen. Dabei bezeichnet die konvexe Hülle von . Stimmt diese konvexe Hülle mit der verwendeten LP-Relaxierung von überein, liefern beide Relaxierungen dieselbe Schranke. Andernfalls kann die Lagrange-Relaxierung eine stärkere Schranke als die entsprechende LP-Relaxierung ergeben.

Erfüllt eine Lösung eines relaxierten Problems zusätzlich die entfernten Nebenbedingungen und gilt

so stimmen der Wert der Lagrange-Funktion und der ursprünglichen Zielfunktion überein. Erreicht dieser Wert zugleich die duale Schranke, ist eine Optimallösung des ursprünglichen Problems.

Bestimmung der Multiplikatoren

Zur Lösung des Lagrange-dualen Problems wird für einen gegebenen Multiplikatorvektor zunächst das relaxierte Problem gelöst:

Der Vektor der Nebenbedingungsverletzungen

bildet einen Obergradienten der konkaven dualen Funktion. In der Literatur werden die darauf beruhenden Verfahren meist als Subgradientenverfahren bezeichnet. Ein projizierter Subgradientenschritt lautet

wobei die Schrittlänge und die komponentenweise Projektion auf den nichtnegativen Orthanten bezeichnet. Ist eine Nebenbedingung verletzt, also , wird ihr Multiplikator durch diesen Schritt erhöht. Die betreffende Verletzung erhält dadurch beim nächsten Lösen des relaxierten Problems ein größeres Gewicht.

Die Wahl der Schrittlängen beeinflusst die Konvergenz des Verfahrens. Neben Subgradientenverfahren werden unter anderem Schnittebenenverfahren, Bündelmethoden und der Volumenalgorithmus zur Lösung des dualen Problems verwendet. Diese Verfahren verbessern die duale Schranke, erzeugen aber nicht zwangsläufig eine zulässige Lösung des ursprünglichen Problems. Zulässige Lösungen werden daher häufig mit problemspezifischen Lagrange-Heuristiken aus den Lösungen der relaxierten Teilprobleme konstruiert.

Auswahl der Nebenbedingungen

Für die Anwendung werden die Nebenbedingungen gewöhnlich in zwei Gruppen unterteilt. Die in verbleibenden Bedingungen sollen eine Struktur bilden, für die ein geeignetes Lösungsverfahren verfügbar ist. Relaxiert werden vor allem Nebenbedingungen, die diese Struktur stören oder mehrere ansonsten unabhängige Teilsysteme miteinander koppeln.

Durch die Relaxierung von Kopplungsbedingungen kann das Optimierungsproblem in mehrere Teilprobleme zerfallen. Diese lassen sich für feste Multiplikatoren unabhängig voneinander lösen. Die Auswahl der zu relaxierenden Bedingungen bestimmt sowohl den Rechenaufwand der Teilprobleme als auch die Qualität der resultierenden dualen Schranke.

Verhältnis zum Verfahren der Lagrange-Multiplikatoren

Die Lagrange-Relaxierung und das klassische Verfahren der Lagrange-Multiplikatoren verwenden dieselbe Lagrange-Funktion, verfolgen jedoch unterschiedliche Ziele. Das klassische Verfahren leitet notwendige Bedingungen für lokale Extrema eines differenzierbaren Optimierungsproblems mit Nebenbedingungen her. Dazu werden stationäre Punkte der Lagrange-Funktion bestimmt.

Bei der Lagrange-Relaxierung werden die Multiplikatoren dagegen zunächst festgehalten und das verbleibende Optimierungsproblem bezüglich gelöst. Anschließend werden die Multiplikatoren im dualen Problem optimiert. Das Verfahren setzt keine Differenzierbarkeit bezüglich der Entscheidungsvariablen voraus und kann daher auch auf diskrete und ganzzahlige Probleme angewandt werden. Es ist eine partielle Anwendung der Lagrange-Dualität, da nur ausgewählte Nebenbedingungen dualisiert werden.

Entwicklung und Anwendungen

A. M. Geoffrion stellte die Lagrange-Relaxierung 1974 als allgemeines Verfahren zur Ausnutzung der Struktur gemischt-ganzzahliger Optimierungsprobleme dar. Marshall L. Fisher veröffentlichte 1981 eine Übersicht über die bis dahin entwickelten theoretischen und anwendungsbezogenen Verfahren.

Lagrange-Relaxierungen werden unter anderem bei Tourenplanungs-, Standort-, Ablaufplanungs-, Zuordnungs- und Mengenüberdeckungsproblemen eingesetzt. Die berechneten Schranken können innerhalb von Branch-and-Bound-Verfahren verwendet werden, um Teilprobleme auszuschließen, die keine bessere Lösung als die bereits bekannte zulässige Lösung enthalten können.

Einzelnachweise

Kategorie:Optimierungsalgorithmus Kategorie:Kombinatorische Optimierung Kategorie:Joseph-Louis Lagrange als Namensgeber