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

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?

convex-optimization linear-programming 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

, 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.

min_{x \in [- 1, 1]} x^{2}

$\min_{x \in [-1, 1]} x^{2}$

x = 0

$x = 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:

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 operacje z osi. $n$ $O(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:

$n$ $O(2^{n})$
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(n^{3.5}L^2\log{L}\log\log{L})$ $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

Dobre podsumowanie. Wygląda na to, że Klee-Minty ma na celu pomieszanie prostych metod LP ...

@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

5^{D}

$5^D$

A

$A$

x^{*}

$x^*$

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