3. Nichtkonvexe Optimierungsprobleme

Gängige Verfahren zur Identifizierung globaler Optimalpunkte und -werte nichtkonvexer Optimierungsprobleme basieren auf Branch-and-Bound-Ideen. Das vorliegende Kapitel präsentiert als exemplarisches Branch-and-Bound-Verfahren das \(\alpha \)BB-Verfahren. Eine Möglichkeit zur effizienten Berechnung der dort erforderlichen Unterschranken basiert auf der konvexen Relaxierung nichtkonvexer Mengen und Funktionen, wobei die \(\alpha \)BB-Methode dazu die Technik der Intervallarithmetik nutzt. Die Branch-and-Bound-Techniken diskutiert das Kapitel in einem ersten Schritt nur für den einfachsten Fall von Problemen mit boxförmiger zulässiger Menge, bevor die notwendigen Modifikationen für den Fall konvexer zulässiger Mengen und schließlich für allgemeine nichtkonvexe Probleme betrachtet werden. Abschließend thematisiert das Kapitel einige Möglichkeiten, in Branch-and-Bound-Verfahren neben der Konvexität der definierenden Funktionen zusätzlich oder alternativ ihre Lipschitz-Stetigkeit auszunutzen.