Oto problem najmniejszych odchyleń bezwzględnych:. Wiem, że można to zmienić jako problem LP w następujący sposób:
Ale nie mam pojęcia, jak to rozwiązać krok po kroku, ponieważ jestem nowicjuszem w LP. Masz jakiś pomysł? Z góry dziękuję!
EDYTOWAĆ:
Oto ostatni etap, w którym osiągnąłem ten problem. Próbuję rozwiązać problem po tej notatce :
Krok 1: Sformułowanie go do standardowego formularza
z zastrzeżeniem
Krok 2: Zbuduj początkowy obraz
| | 0 | 1 | 0 | 0 | 0
basic var | coef | $p_0$ | $u_i$ | W | $s_1$ | $s_2$
$s_1$| 0 | $y_i$ | -1 | x | 1 | 0
$s_2 | 0 | $-y_i$ | 1 | x | 0 | 1
z | | 0 | -1 | 0 | 0 | 0
Krok 3: Wybierz podstawowe zmienne
jest wybierany jako wejściowa zmienna podstawowa. Nadchodzi problem. Wybierając wyjściową zmienną podstawową, oczywiste jest, że . Zgodnie z uwagą, jeśli , problem ma nieograniczone rozwiązanie.
Jestem tu całkowicie zagubiony. Zastanawiam się, czy coś jest nie tak i jak powinienem kontynuować następujące kroki.
regression
optimization
quantile-regression
linear-programming
least-absolute-deviations
Southdoor
źródło
źródło
Odpowiedzi:
Chcesz przykład rozwiązania najmniejszego odchylenia absolutnego przez programowanie liniowe. Pokażę prostą implementację w R. Regresja kwantylowa jest uogólnieniem najmniejszego odchylenia absolutnego, co ma miejsce w przypadku kwantyla 0,5, więc pokażę rozwiązanie regresji kwantylowej. Następnie możesz sprawdzić wyniki z
quantreg
pakietem R :Następnie używamy go w prostym przykładzie:
wtedy sam możesz to sprawdzić za pomocą
quantreg
.źródło
Programowanie liniowe można uogólnić za pomocą optymalizacji wypukłej, w której oprócz simpleksów dostępnych jest wiele bardziej niezawodnych algorytmów.
Sugeruję, abyś sprawdził wypukłą książkę optymalizacji i dostarczony przez nią zestaw narzędzi CVX. Gdzie można łatwo sformułować najmniejsze odchylenie absolutne dzięki regularyzacji.
https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf
http://cvxr.com/cvx/
źródło