Często spotykam się z ogólnym stwierdzeniem, że metody punktów wewnętrznych są trudne do rozgrzania. Czy kryje się za tym intuicyjne wyjaśnienie? Czy są sytuacje, w których można oczekiwać korzyści z ciepłego startu metodą punktową? Czy ktoś może polecić przydatne informacje na ten temat?
Odpowiedzi:
Metody punktów wewnętrznych działają, podążając centralną ścieżką do optymalnego rozwiązania. Po zmianie funkcji celu optymalne rozwiązanie z poprzedniej wersji problemu jest dalekie od głównej ścieżki dla nowego problemu, więc powrót do ścieżki centralnej wymaga kilku iteracji, a ponadto musi powrócić do dość dobrze wyśrodkowanego rozwiązanie. Następnie musisz popracować na ścieżce do nowego optymalnego rozwiązania. Równie dobrze możesz po prostu uruchomić metodę punktu wewnętrznego od dowolnego punktu.
Dla porównania metoda simpleksowa (pierwotna lub podwójna) przemieszcza się od wierzchołka do wierzchołka wykonalnego zestawu. W typowym przypadku stosunkowo niewielka zmiana celu spowoduje powstanie nowego optymalnego rozwiązania, które jest oddalone tylko o kilka simpleksów.
... dodano do powyższego intuicyjnego wyjaśnienia, aby podać więcej szczegółów ...
W praktyce obliczeniowej doświadczenie po prostu nie wykazało żadnej istotnej korzyści z metod ciepłego rozpoczynania od pierwotnego podwójnego punktu wewnętrznego. Nie jest to cecha powszechnie używanych kodów, takich jak CPLEX i Gurobi (firmy, które produkują te pakiety, z pewnością dodaliby taką funkcję, gdyby była tego warta), a stosunkowo mało jest artykułów omawiających strategie dotyczące metod rozpoczynania od ciepłego punktu wewnętrznego .
Dwie referencje, które polecę to:
EA Yildirim i S. Wright. Strategie ciepłego startu w metodach wewnętrznych punktów programowania liniowego. SIAM Journal on Optimization 12: 782-810, 2002. Ten dokument zawiera kilka dobrych teoretycznych granic dla niektórych strategii ciepłego startu. Zobacz http://pages.cs.wisc.edu/~swright/papers/YilW02a.pdf
Późniejszy artykuł autorstwa Yildirima daje pewne wyniki obliczeń, ale autorzy przyznają, że po prostu zimny rozruch jest często szybszy w testach niż ciepły:
E. John i EA Yildirim. Wdrożenie strategii ciepłego startu w metodach wewnętrznych dla programowania liniowego w ustalonym wymiarze. Optymalizacja obliczeniowa i aplikacje. 41: 151-183, 2008. Patrz http://link.springer.com/article/10.1007/s10589-007-9096-y