Jakie są zalety / wady metod punktów wewnętrznych w porównaniu z metodą simpleks do optymalizacji liniowej?

14

Jak rozumiem, ponieważ rozwiązanie programu liniowego zawsze występuje w wierzchołku jego wielościennego wykonalnego zestawu (jeśli istnieje rozwiązanie, a optymalna wartość funkcji celu jest ograniczona od dołu, zakładając problem minimalizacji), w jaki sposób można przeszukać wnętrze realnego regionu może być lepsze? Czy zbiega się szybciej? W jakich okolicznościach korzystniejsze byłoby zastosowanie metody simpleksowej niż metody punktów wewnętrznych? Czy jedno jest łatwiejsze do zaimplementowania w kodzie niż drugie?

Paweł
źródło
Jedno z twoich stwierdzeń jest nieprawidłowe. Rozwiązanie wypukłego problemu optymalizacji NIE zawsze występuje na granicy. Weźmy na przykład , gdzie optymalne rozwiązanie występuje przy x = 0 , która znajduje się we wnętrzu wykonalnego obszaru. Poza kontekstem programowania liniowego metoda simpleks ogólnie odnosi się do metody simpleks Neldera-Meada, która może nawet nie zbiegać się z optymalnym rozwiązaniem w wymiarze większym niż 1. Ta metoda nie jest zalecana do programowania wypukłego. Zmodyfikuj swoje pytanie, aby było jasne i poprawne. minx[1,1]x2x=0
Geoff Oxberry
Czy bardziej właściwe byłoby powiedzenie „optymalizacja liniowa” zamiast „optymalizacja wypukła”?
Paweł
Tak, to twoje oświadczenie jest poprawne. Dziękujemy za edycję pytania.
Geoff Oxberry
Problem z metodą simpleks polega na tym, że nie można jej uogólniać na problemy nieliniowe, tj. Większość problemów w świecie rzeczywistym.

Odpowiedzi:

17

Opierając się na osobistym doświadczeniu, powiedziałbym, że metody simpleksowe są nieznacznie łatwiejsze do zrozumienia niż metody punktowe wewnętrzne, w oparciu o osobiste doświadczenia z implementacji zarówno podstawowej pierwotnej simpleksu, jak i podstawowej metody punktowej wewnętrznej w MATLAB w ramach przyjmowania liniowej klasy programowania . Głównymi przeszkodami w pierwotnym simpleksie jest upewnienie się, że poprawnie wdrażasz fazę I i fazę II, a także poprawnie wdrażasz regułę antycykliczną. Główne przeszkody we wdrażaniu metody punktu wewnętrznego dla programowania liniowego zwykle polegają na poprawnym wdrażaniu metody iteracyjnej i odpowiednim skalowaniu parametru bariery.

Pełniejsze omówienie zalet i wad każdego algorytmu można znaleźć w podręczniku programowania liniowego, takim jak Wprowadzenie do optymalizacji liniowej autorstwa Bertsimasa i Tsitsiklisa. ( Zastrzeżenie: Nauczyłem się programowania liniowego z tego podręcznika i wziąłem programowanie liniowe na MIT od żony Bertsimasa.) Oto niektóre z podstawowych zasad:

Zalety simplex:

  • Biorąc pod uwagę zmienne decyzyjne, zwykle zbieżny w O ( n ) operacje z O ( n ) osi.nO(n)O(n)
  • Wykorzystuje geometrię problemu: odwiedza wierzchołki wykonalnego zestawu i sprawdza optymalność każdego odwiedzanego wierzchołka. (W primal simplex do tej kontroli można wykorzystać obniżony koszt).
  • Dobry na małe problemy.

Wady simplex:

  • nO(2n)
  • Nie tak świetnie w przypadku dużych problemów, ponieważ operacje obracania stają się kosztowne. Algorytmy płaszczyzny cięcia lub algorytmy opóźnionego generowania kolumn, takie jak Dantzig-Wolfe, mogą czasem zrekompensować tę niedociągnięcie.

Plusy wewnętrznych metod punktowych:

  • O(n3.5L2logLloglogL)L
  • Lepsze w przypadku dużych, rzadkich problemów, ponieważ algebra liniowa wymagana dla algorytmu jest szybsza.

Wady metod punktów wewnętrznych:

  • Nie jest tak intuicyjnie satysfakcjonujące, ponieważ masz rację, te metody nie odwiedzają wierzchołków. Wędrują przez region wewnętrzny, szukając rozwiązania, gdy odniesie sukces.
  • W przypadku małych problemów simplex prawdopodobnie będzie szybszy. (Możesz konstruować przypadki patologiczne, takie jak kostka Klee-Minty.)
Geoff Oxberry
źródło
2
Dobre podsumowanie. Wygląda na to, że Klee-Minty ma na celu pomieszanie prostych metod LP ...
JM
@JM Tak, właśnie o to chodzi - jest to wyraźna konstrukcja pokazująca, że ​​metody simpleksowe nie są wielomianowe (chociaż istnieją warianty, które powodują, że metody punktowe wewnętrzne również płaczą).
Christian Clason
Dziękuję za ten pouczający post. Zastanawiam się, ile zmiennych sprawia, że ​​problem jest duży? Dziesiątki? Setki? Tysiące?
KjMag
5DAx
3

Odpowiedź jest łatwa. Obie metody (simpleks i metoda punktowa wewnętrzna) są dojrzałym polem z algorytmicznego punktu widzenia. Oba działają bardzo dobrze w praktyce. Dobra reputacja IPM (metody punktów wewnętrznych) wynika z jego złożoności wielomianowej w najgorszym przypadku. Tak nie jest w przypadku simpleksu, który ma złożoność kombinatoryczną. Niemniej jednak kombinatoryczne programy liniowe prawie nigdy nie zdarzają się w praktyce. W przypadku problemów na bardzo dużą skalę IP wydaje się być nieco szybszy, ale reguła nie jest konieczna. Moim zdaniem własność intelektualna może być łatwa do zrozumienia i wdrożenia, ale na pewno ktoś inny może się nie zgodzić, i to jest w porządku. Teraz, w LP, jeśli rozwiązanie jest unikalne, zdecydowanie znajduje się w wierzchołku (zarówno IP, jak i Simplex mają się tutaj dobrze). Rozwiązanie może również znajdować się na powierzchni wielościanu lub na krawędzi, w którym to przypadku, sąsiadujący wierzchołek jest (lub wierzchołki są) rozwiązaniem (znowu, zarówno IP, jak i simplex mają się dobrze). Więc są prawie takie same.

Carlos Ramirez
źródło
Zdaję sobie sprawę, że podany przeze mnie przykład nie był programem liniowym; jeśli spojrzysz na historię zmian, we wcześniejszej wersji tego pytania zadano porównanie metod simpleks i metod punktów wewnętrznych dla problemów optymalizacji wypukłej. Dałem kontrprzykład, aby uzasadnić dokonane przeze mnie zmiany, i zachęcić oryginalny plakat, by poprawił swoje pytanie, które zrobił.
Geoff Oxberry