Innere-Punkte-Verfahren

Innere-Punkte-Verfahren sind in der Optimierung eine Klasse von Algorithmen zur Lösung von Optimierungsaufgaben. Ihr Hauptanwendungsgebiet sind lineare oder quadratische Programme. Sie werden aber auch zur Lösung (allgemeiner) nichtlinearer Programme, semidefinierter Programme oder Komplementaritätsproblemen eingesetzt.

Im Vergleich zu den traditionelleren Active-Set-Methoden (z. B. Simplex-Verfahren) zeichnen sich Innere-Punkte-Verfahren durch bessere theoretische Eigenschaften (polynomiale Komplexität) und schnellere Konvergenz für sehr große dünnbesetzte Probleme aus. Ein Nachteil ist, dass sie vergleichbar ungeeignet zum Lösen einer Serie von Optimierungsaufgaben sind (was für viele Algorithmen der ganzzahligen Optimierung, wie z. B. Branch and Bound oder Schnittebenenverfahren, wichtig ist).

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Innere-Punkte-Verfahren aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren