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