InteriorPointMethoden

InteriorPointMethoden (IPMs) sind eine Klasse von Optimierungsverfahren, die das Innere der zulässigen Menge nutzen, statt entlang der Randgrenze zu iterieren, wie es bei Verfahren auf dem Rand der Feasible-Region oft der Fall ist. Sie sind besonders verbreitet bei linearer Programmierung, quadratischer Programmierung und allgemeinen konvexen Optimierungsproblemen.

Grundprinzipien: Typischerweise wird ein Problem in eine Form gebracht, in der Ungleichheitsbeschränkungen x ≥ 0 durch eine Barrierefunktion abgebildet werden. Die Barriere phi(x) = −∑ log(x_i) wirkt als Schutzwall gegen das Verlassen des Inneren der Feasible-Region. Man löst dann schrittweise Probleme der Form min c^T x + μ phi(x) subj. Ax = b, wobei μ > 0 der Barriereparameter ist und μ nach und nach gegen Null abgenommen wird. Dadurch nähert man sich allmählich dem ursprünglichen Problem. Primal- und Dualvariablen werden meist simultan aktualisiert ( primal-dual-Ansatz ), und zentrale KKT-Bedingungen werden als Gleichungssysteme mit Newton-Schritten gelöst. Beim Pfadfolge-Verfahren (path-following) verfolgt man einen zentralen Pfad, während μ schrittweise reduziert wird.

Typische Varianten: Primal-Dual-Interior-Point-Methoden, einschließlich der Mehrotra-Predictor-Corrector-Technik, sind heute in vielen Softwarepaketen dominierend. Für lineare Programme liefern IPMs polynomielle Laufzeitdaten und sind besonders gut geeignet für große, sparse Systeme. Für quadratische Programme und allgemeine konvexe Probleme lassen sich IPMs ebenfalls anwenden und liefern oft robuste Leistung.

Anwendung und Bedeutung: IPMs gehören zu den standardmäßigen Werkzeugen in der Theorie und Praxis der Optimierung. Sie bieten eine skalierbare Alternative zum Simplex-Verfahren, besonders bei großen oder schlecht konditionierten Problemen, und bilden die Grundlage moderner Solver für LP, QP und konvexe Optimierung.