Innenpunktsverfahren

Innenpunktsverfahren (engl. interior-point methods) sind eine Klasse von Optimierungsalgorithmen zur Lösung linearer Programme und konvexer Optimierungsprobleme. Sie arbeiten im Inneren der zulässigen Menge und bewegen sich entlang eines zentralen Pfads, der durch Barrierefunktionen wie die Logbarriere definiert wird. Ziel ist es, das ursprüngliche Problem durch ein barrierenver deinerendes Problem zu lösen, wobei der Barriereparameter mu schrittweise verringert wird.

Typische Problemstellung ist min c^T x unter Ax = b, x ≥ 0. Durch Einführung einer Barrierefunktion wird das Problem zu einer barrierenaugmentierten Version, in der die Nebenbedingungen durch zusätzliche Terme wie mu sum_i log x_i bestraft werden. Die Suchrichtung wird mittels Newton-Schritten berechnet, indem man die optimalen Bedingungen des barrieren Problems löst. Es gibt reine primal- oder reine dual- sowie primal-dual-Varianten; bekannter Bestandteil vieler Implementierungen ist der predictor-corrector-Ansatz (Mehrotra).

Vorteile dieser Verfahren liegen in der guten Skalierbarkeit bei großen, spärlichen Problemen und in robustem Konvergenzverhalten im Innenraum der Feasible-Region. Sie sind in der Praxis oft schneller als Simplex-Methoden bei großen LPs und bilden die Grundlage moderner Solver. Nachteile umfassen den hohen linearen Algebra-Aufwand pro Iteration, der Kondition des Problems und den Implementierungsaufwand.

Historisch waren Innenpunktsverfahren seit Karmarkars Algorithmus (1984) maßgeblich für die Entwicklung polynomialzeitlicher Lösungsansätze in der linearen Programmierung. Heute finden sie auch Anwendung in Quadrik- und Semidefiniten Programmen sowie in vielen praxisnahen Optimierungsaufgaben.