Innenpunktmethoden folgen dem zentralen Weg zu einer optimalen Lösung. Wenn Sie die Zielfunktion ändern, ist die optimale Lösung aus der vorherigen Version des Problems weit vom zentralen Pfad für das neue Problem entfernt. Daher sind mehrere Iterationen erforderlich, um zum zentralen Pfad zurückzukehren, und außerdem muss zu einem ziemlich gut zentrierten Pfad zurückgekehrt werden Lösung. Dann müssen Sie sich auf dem Weg zu einer neuen optimalen Lösung arbeiten. Sie können die Methode für innere Punkte auch einfach von einem beliebigen Punkt aus starten.
Im Vergleich dazu bewegt sich die Simplex-Methode (primär oder dual) von Scheitelpunkt zu Scheitelpunkt der realisierbaren Menge. Im typischen Fall führt eine relativ kleine Änderung des Objektivs zu einer neuen optimalen Lösung, die nur wenige Simplex-Drehpunkte entfernt ist.
... zur intuitiven Erklärung oben hinzugefügt, um mehr Details zu geben ...
In der Computerpraxis hat die Erfahrung einfach keinen wesentlichen Nutzen für das Warmstarten von Primal-Dual-Interior-Point-Methoden gezeigt. Es ist kein Merkmal weit verbreiteter Codes wie CPLEX und Gurobi (die Unternehmen, die diese Pakete herstellen, würden ein solches Merkmal mit Sicherheit hinzufügen, wenn es sich lohnt), und es gibt relativ wenige Artikel, in denen Strategien für Warmstart-Innenpunktmethoden erörtert werden .
Zwei Referenzen, die ich empfehlen werde, sind:
EA Yildirim und S. Wright. Warmstartstrategien in Innenpunktmethoden für die lineare Programmierung. SIAM Journal on Optimization 12: 782-810, 2002. Dieses Papier gibt einige schöne theoretische Grenzen für einige Warmstartstrategien. Siehe
http://pages.cs.wisc.edu/~swright/papers/YilW02a.pdf
Ein später von Yildirim mitverfasstes Papier liefert einige Berechnungsergebnisse, aber die Autoren geben zu, dass ein einfacher Kaltstart in ihren Tests oft schneller ist als ein Warmstart:
E. John und EA Yildirim. Implementierung von Warmstartstrategien in Innenpunktmethoden zur linearen Programmierung in fester Dimension. Computeroptimierung und Anwendungen. 41: 151-183, 2008. Siehe
http://link.springer.com/article/10.1007/s10589-007-9096-y
