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

@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