Innenpunktmethoden

Innenpunktmethoden sind eine Klasse von Optimierungsverfahren, die große lineare oder konvexe Programme durch Iterationen lösen, die sich im Inneren der zulässigen Menge befinden. Der Grundgedanke ist, Nebenbedingungen durch Barrieren zu behandeln oder primal-duale Barrierefunktionen zu verwenden, sodass sich die aktuellen Iterationen stets innerhalb des zulässigen Bereichs bewegen und schrittweise zur Optimalität konvergieren.

In der typischen linear-programm-Formulierung zielt ein Innenpunktverfahren darauf ab, das Problem min c^T x unter Ax = b, x ≥ 0 durch ein barrier term zu lösen. Ein zentraler Pfad ergibt sich, indem man ein barrieriertes Ziel F_mu(x) = c^T x - mu Σ_i log x_i minimiert und mu gegen null fahren lässt. Beim primal-dualen Ansatz werden zusätzlich duale Variablen eingeführt, sodass KKT-Bedingungen gleichzeitig für Primal- und Dualvariablen erfüllt werden. Die iterativen Schritte bestehen in der Berechnung einer Newton-Richtung für das barrierierte System und einer anschließenden Linien-Suche, um Positivität und Fortschritt sicherzustellen. Varianten umfassen Path-Following-Methoden, Short- und Long-Step-Strategien sowie Mehrotra-Predictor-Corrector-Algorithmen.

Vorteile liegen in polynomialer Laufzeit bei vielen Problemklassen, guter Skalierbarkeit auf große, spärliche Probleme sowie robuster Leistung im Vergleich zu einfachen Simplex-Verfahren. Anwendungen finden sich vor allem in linearer Programmierung, konvexen Quadratik- und Semidefinit-Programmen (SDP) sowie in SOCP- und weiteren konvexen Optimierungsformen.

Historisch entstanden Innenpunktmethoden durch Karmarkar 1984 für LP; seitdem wurden sie stark erweitert, um auch SDP und andere konvexe Probleme effizient zu lösen. Ihre Bedeutung gilt insbesondere für große, komplexe Optimierungsaufgaben in Wissenschaft und Technik.