Relaxationsverfahren

Relaxationsverfahren bezeichnet eine Familie von Optimierungsmethoden, bei denen ein schwer lösbares Problem durch ein leichter zu behandelndes Problem ersetzt wird. Ziel ist es, eine Lösung zu finden, die entweder zulässig ist oder deren Wert eine Schranke für die optimale Zielgröße liefert, die auf das ursprüngliche Problem zurückübertragen werden kann.

Typen sind z. B. lineare Relaxation, konvexe Relaxation, semidefinite Relaxationen (SDR) und Lagrange-Relaxation. Bei der linearen Relaxation wird eine Diskretisierung bzw. Ganzzahligkeit durch eine kontinuierliche Variable ersetzt, oft um einen Lösungswert als obere oder untere Schranke zu erhalten. Konvexe Relaxationen wandeln das Problem in ein konvexes um, das effizient lösbar ist und trotzdem wichtige Strukturen bewahrt. Semidefinite Relaxationen nutzen positive Semidefinitheit, um quadratische oder polynomialen Probleme näherungsweise zu fassen. Die Lagrange-Relaxation dualisiert einige Nebenbedingungen und liefert so untere Schranken sowie oft Decompositionseigenschaften. Hierarchische Relaxationen, wie die Lasserre-Hierarchie, liefern sukzessive engere Schranken für polynomielle Optimierungsprobleme.

In der kombinatorischen Optimierung dienen Relaxationen dazu, Ober- und Untergrenzen zu bestimmen und anschließend durch Rundung oder Rekonstruktion eine zulässige, oft nahe optimale Lösung zu erhalten. Typische Beispiele sind die lineare Relaxation von Integerprogrammen oder SDP-Relaxationen für Probleme wie MAX-CUT oder Set-Cover.

In der numerischen linearen Algebra bezieht sich der Begriff Relaxation auch auf iterative Verfahren zur Lösung von Gleichungssystemen, etwa Gauss-Seidel oder Successive Over-Relaxation, die schrittweise die Fehlergröße reduzieren.