Rozwiązywanie najmniejszych odchyleń bezwzględnych za pomocą algorytmu Barrodale-Roberts: Przedwczesne zakończenie?

Przepraszam za długie pytanie, potrzebuje tylko wyjaśnienia, aby przejść do rzeczywistego problemu. Osoby zaznajomione z wymienionymi algorytmami prawdopodobnie mogłyby przejść bezpośrednio do pierwszego tablau simpleksowego.

Aby rozwiązać problemy z najmniejszymi odchyleniami bezwzględnymi (alias $L_1$ -optymalizacja), algorytm Barrodale-Roberts jest specjalną metodą simpleksową, która wymaga znacznie mniej pamięci i wysiłków obliczeniowych, aby znaleźć odpowiednie minimum.

Moja implementacja algorytmu kończy się na prostym przykładzie, zanim zostanie osiągnięte odpowiednie minimum. Najprawdopodobniej jednak najpierw przedstawię problem w bardziej rozbudowany sposób:

Podane dane $(x_i,y_i)$ , $L_1$ -optimization próbuje znaleźć $c\in m$ to minimalizuje

\sum_{ja = 1}^{n} | y_{ja} - fa (x_{ja}) | z fa (x) : = {ZA}_{x} \cdot ϕ

$\sum_{i=1}^n |y_i-f(x_i)| \quad\text{with}\quad f(x):=A_x\cdot \phi$ gdzie

A_{x}

$A_x$ jest

n \times m

$n\times m$ macierz, która w jakiś sposób zależy

x

$x$ . Problem ten można określić jako program liniowy i dlatego między innymi można go rozwiązać metodami typu simpleks.

Barrodale i Roberts zasugerowali (najwyraźniej szeroko stosowaną) modyfikację metody simplex, która radykalnie upraszcza metodę simpleks przy użyciu specjalnej struktury $L_1$ -problemy. Przede wszystkim dlatego, że optymalne rozwiązanie interpoluje przynajmniej $\mathop{rank}(A)$ podanych punktów danych. Osoby z dostępem do Jstor mogą znaleźć odpowiedni artykuł tutaj .

Lei i Anderson w 2002 roku zaproponowali niewielką modyfikację, która ma zwiększyć stabilność numeryczną, a tym samym przezwyciężyć znane problemy z algorytmem simpleks.

Zasadniczo ten algorytm zakłada, że zaczynasz od określonego zestawu punktów, które muszą być interpolowane, użyj podanych procedur do zbudowania tablicy simpleksowej, a następnie użyj reguł Barrodale i Robertsa, aby zdecydować, które zmienne podstawowe należy zmienić, a zatem zmodyfikować zbiór punktów danych, który jest przybliżony.

Barrodale i Roberts dają mały przykład, który próbowałem odtworzyć. Próbuje przybliżyć punkty $\{(1,1), (2,1), (3,2), (4,3), (5,2)\}$ przez funkcję $a_1+a_2x$ . Zakończ swój algorytm następującym skróconym obrazem simpleksowym:

\begin{array}{llll} Podstawa & R & u_{1} & u_{3)} \\ b_{1} & 1 / 2) & 3) / 2) & - 1 / 2) \\ v_{2)} & 1 / 2) & 1 / 2) & 1 / 2) \\ b_{2)} & 1 / 2) & - 1 / 2) & 1 / 2) \\ u_{4} & 1 / 2) & 1 / 2) & - 3) / 2) \\ v_{5} & 1 & - 1 & 2) \\ Koszt marginalny & 2) & - 1 & 0 \end{array}

$\begin{array}{l|l|ll} \hline \text{Basis}&R& u_1 & u_3\\ \hline b_1 & 1/2 & 3/2 & -1/2 \\ v_2 & 1/2 & 1/2 & 1/2 \\ b_2 & 1/2 & -1/2 & 1/2 \\ u_4 & 1/2 & 1/2 & -3/2 \\ v_5 & 1 & -1 & 2 \\ \hline \text{Marginal cost} &2 & -1 & 0\\ \hline \end{array}$

Co najważniejsze, pierwszy i trzeci punkt są interpolowane, a ogólny błąd jest równy $2$ . Wnioskują to

Ponieważ wszystkie wektory niebazowe mają niepozytywny koszt krańcowy [...]

iteracja jest zakończona i osiąga się optymalne.

Jeśli użyję algorytmu Lei i Andersona, mogę odtworzyć ten simpleksowy zbiór dla zestawu interpolacji {1,3}, zgodnie z oczekiwaniami. Jednak jeśli zacznę algorytm od zestawu $\{2, 5\}$ (co wyraźnie nie jest optymalne), otrzymuję następujący tableau simpleks:

\begin{array}{llll} Podstawa & R & u_{2)} & u_{5} \\ u_{1} & 1 / 3) & - 4 / 3) & 1 / 3) \\ b_{1} & 1 / 3) & 5 / 3) & - 2) / 3) \\ u_{3)} & 2) / 3) & - 2) / 3) & - 1 / 3) \\ u_{4} & 4 / 3) & - 1 / 3) & - 2) / 3) \\ b_{2)} & 1 / 3) & - 1 / 3) & 1 / 3) \\ Koszt marginalny & 7 / 3) & - 10 / 3) & - 5 / 3) \end{array}

$\begin{array}{l|l|ll} \hline \text{Basis}&R& u_2 & u_5\\ \hline u_1 & 1/3 & -4/3 & 1/3 \\ b_1 & 1/3 & 5/3 & -2/3 \\ u_3 & 2/3 & -2/3 & -1/3 \\ u_4 & 4/3 & -1/3 & -2/3 \\ b_2 & 1/3 & -1/3 & 1/3 \\ \hline \text{Marginal cost} &7/3 & -10/3 & -5/3\\ \hline \end{array}$

Ten wynik mnie jednak zastanawia. Jeśli dobrze rozumiem powyższy cytat, brak dodatniego kosztu krańcowego oznacza, że osiągnięto optymalne. Jednak wartość funkcji około 2,33 z pewnością nie jest optymalna. Wymiana $u_2$ z $u_1$ dałoby wynik równy rozwiązaniu Barrodale'a i Robertsa, a zatem optymalny.

Informacje dodatkowe: Jeśli zacznę od początkowego układu tabel podanego przez Barrodale i Robertsa, będę w stanie odtworzyć powyższy układ za pomocą zwykłych kroków simpleksowych, więc jestem całkiem pewien, że rzeczywiste wartości liczbowe są prawidłowe i moja interpretacja reguły wyboru przestawnej jest wadliwy.

Masz jakieś przemyślenia na ten temat?

Zdaję sobie sprawę, że samo pytanie jest dość skomplikowane i prawdopodobnie wymaga wystarczającej znajomości przynajmniej algorytmu Barrodale i Robertsa. Algorytm jako całość musi powtórzyć go tutaj szczegółowo. Jeśli jednak masz dodatkowe pytania dotyczące podjętych przeze mnie kroków lub brakujących informacji, możesz je zadać i chętnie pomogę.

optimization linear-programming Thilo
źródło

Byłbym wdzięczny, gdyby ktoś o wystarczającej reputacji mógł stworzyć tag w stylu „najmniejszych absolutnych odchyleń” lub „przybliżenia L1”.

Thilo

Warunkiem optymalności jest to, że podstawowe rozwiązanie musi być wykonalne (w odniesieniu do jego ograniczeń nieujemności) i że zmniejszone koszty muszą być mniejsze lub równe 0. Jeśli twoje podstawowe rozwiązanie jest niewykonalne, wszystkie zakłady są wyłączone.

Brian Borchers,

Podstawowe rozwiązanie jest wykonalne konstrukcyjnie. Dlatego nie powinno być problemu. Mam jednak pierwszy pomysł, gdzie może być problem. Dodam odpowiednią odpowiedź, jeśli mam rację.

Thilo,

Rozwiązałem to. W rzeczywistości Barrodale i Roberts rozwiązali ten problem, a ja po prostu nie przeczytałem uważnie.

W moim pytaniu pozostawiłem czytelnikowi zrozumienie, że zmienne Barrodale i Roberts są oznaczone $u_i$ oznaczają dodatnie reszty $i$ -ty punkt danych w stosunku do bieżącego dopasowania. Jeśli reszta jest ujemna, $u_i=0$ i $v_i$ przyjmuje odpowiednią wartość. Ponieważ tylko jeden z nich może znajdować się w obrębie podstawy, a współczynniki w tablicy simpleks są tylko ujemnymi wartościami siebie, nie jest konieczne jawne podawanie ich w tablicy simpleks. Barrodale i Roberts wspominają w swoim artykule:

[...] oraz suma kosztów krańcowych (lub obniżonych) w wysokości $b_j$ i $c_j$ wynosi zero i wynosi $u_i$ i $v_i$ wynosi -2.

Zatem mój powyższy obrazek simpleks powinien wyglądać następująco:

\begin{array}{llllll} Podstawa & R & u_{2)} & u_{5} & v_{2)} & v_{5} \\ u_{1} & 1 / 3) & - 4 / 3) & 1 / 3) & 4 / 3) & - 1 / 3) \\ b_{1} & 1 / 3) & 5 / 3) & - 2) / 3) & - 5 / 3) & 2) / 3) \\ u_{3)} & 2) / 3) & - 2) / 3) & - 1 / 3) & 2) / 3) & 1 / 3) \\ u_{4} & 4 / 3) & - 1 / 3) & - 2) / 3) & 1 / 3) & 2) / 3) \\ b_{2)} & 1 / 3) & - 1 / 3) & 1 / 3) & - 1 / 3) & - 1 / 3) \\ Koszt marginalny & 7 / 3) & - 10 / 3) & - 5 / 3) & 4 / 3) & - 1 / 3) \end{array}

$\begin{array}{l|l|ll| ll} \hline \text{Basis}&R& u_2 & u_5 & v_2 & v_5\\ \hline u_1 & 1/3 & -4/3 & 1/3 & 4/3 & -1/3 \\ b_1 & 1/3 & 5/3 & -2/3 & -5/3 & 2/3 \\ u_3 & 2/3 & -2/3 & -1/3 & 2/3 & 1/3 \\ u_4 & 4/3 & -1/3 & -2/3 & 1/3 & 2/3 \\ b_2 & 1/3 & -1/3 & 1/3 & -1/3 & -1/3 \\ \hline \text{Marginal cost} &7/3 & -10/3 & -5/3 & 4/3 & -1/3\\ \hline \end{array}$

gdzie to wyraźnie widzimy $v_2$ może zostać wykorzystany do zarchiwizowania lepszego wyniku. W ten sposób algorytm kończy się podczas interpolacji pierwszego i piątego punktu danych z ogólnym błędem 2 - co jest najlepszym rozwiązaniem.

Dziękuję za przeczytanie i danie mi miejsca do napisania mojego problemu, co zwykle pomaga znacznie zawęzić rozwiązanie. Mamy nadzieję, że ta odpowiedź może być czasem pomocna dla każdego, kto próbuje wdrożyć Barrodale & Roberts.

Thilo
źródło

Rozwiązywanie najmniejszych odchyleń bezwzględnych za pomocą algorytmu Barrodale-Roberts: Przedwczesne zakończenie?

Odpowiedzi: