Innere-Punkte-Verfahren

Herleitung

Vom heutigen Standpunkt aus gibt es verschiedene Wege, um Innere-Punkte-Verfahren zu motivieren. Eine Möglichkeit ist über Logarithmische Barrieren: Hierbei werden die Positivitätsbedingungen durch logarithmische Strafterme in der Zielfunktion ersetzt (hierbei ist ein Parameter). Anstatt des Ursprungsproblems löst man also

Für kleine Werte von x wird - ln x sehr groß, man versucht also durch Bestrafung kleiner x-Werte die Lösung des Optimierungsproblems im Inneren der Menge der positiven Koordinaten zu halten. Diese Bestrafung wird umso kleiner, je kleiner der Parameter ist. Im Grenzwert erwartet man, dass die Lösung des Barriereproblems gegen die Lösung des Ursprungsproblems konvergiert. Das Barriereproblem ist ein (streng) konvexes Problem, seine (einzige, globale) Lösung findet man durch Anwendung des lagrangeschen Multiplikatorensatz als Lösung des (nichtlinearen) Gleichungssystems

Für jeden Wert ist dieses Gleichungssystem eindeutig lösbar. Die Menge aller Lösungen für verschiedene beschreibt einen Pfad (den zentralen Pfad), der das Analytische Zentrum des zulässigen Polyeders (für ) mit der Lösung des Ursprungsproblems (für ) verbindet.Algorithmisch kann das Gleichungssystem per Newton-Verfahren gelöst werden. In Innere-Punkte-Verfahren wird nach jeder Iteration des Newton-Verfahrens der Parameter reduziert. Durch geeignete Heuristiken wird sichergestellt, dass die Konvergenz von und die des Newton-Verfahrens synchron ablaufen.

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

Anbieterkennzeichnung