Techniki wyszukiwania łuków dla metod punktów wewnętrznych

Oryginalny tytuł:

Arc-Search Techniques for Interior-Point Methods

Zawartość książki:

Niniejsza książka omawia ważną dziedzinę optymalizacji numerycznej, zwaną metodą punktów wewnętrznych. Temat ten jest popularny od lat 80-tych XX wieku, kiedy ludzie stopniowo zdali sobie sprawę, że wszystkie algorytmy simpleksowe nie są zbieżne w czasie wielomianowym, a wiele algorytmów wewnętrzno-punktowych można udowodnić, że są zbieżne w czasie wielomianowym.

Jednak przez długi czas istniała zauważalna luka między teoretycznymi granicami wielomianowymi algorytmów wewnętrzno-punktowych a wydajnością tych algorytmów. Strategie, które były ważne dla wydajności obliczeniowej, stawały się barierami w dowodzie dobrych ograniczeń wielomianowych. Im więcej strategii było wykorzystywanych w algorytmach, tym gorsze stawały się granice wielomianowe.

Aby jeszcze bardziej zaostrzyć problem, algorytm Mehrotra's predictor-corrector (MPC) (do niedawna najpopularniejszy i najbardziej wydajny algorytm wewnątrz-punktowy) wykorzystuje wszystkie dobre strategie i nie udowadnia zbieżności.

Dlatego też MPC nie ma wielomianowości, co jest krytycznym problemem w przypadku metody simpleks. Niniejsza książka omawia najnowsze osiągnięcia, które rozwiązują ten dylemat.

Składa się ona z trzech głównych części. Pierwsza, obejmująca rozdziały 1, 2, 3 i 4, przedstawia niektóre z najważniejszych algorytmów podczas rozwoju metody punktów wewnętrznych w latach 90-tych, z których większość jest powszechnie znana. Głównym celem tej części jest wyjaśnienie opisanego powyżej dylematu poprzez analizę wielomianowych ograniczeń tych algorytmów i podsumowanie związanych z nimi doświadczeń obliczeniowych.

Druga część, obejmująca rozdziały 5, 6, 7 i 8, opisuje, jak krok po kroku rozwiązać dylemat za pomocą technik wyszukiwania łuków. Na końcu tej części przedstawiono bardzo wydajny algorytm z najniższą granicą wielomianową. Ostatnia część, zawierająca rozdziały 9, 10, 11 i 12, rozszerza techniki wyszukiwania po łuku na bardziej ogólne problemy, takie jak wypukłe programowanie kwadratowe, liniowy problem komplementarności i programowanie półokreślone.