Jak rozwiązać najmniejsze odchylenie bezwzględne metodą simpleks?

12

Oto problem najmniejszych odchyleń bezwzględnych:. Wiem, że można to zmienić jako problem LP w następujący sposób:argminwL.(w)=ja=1n|yja-wT.x|

minja=1nuja

ujaxT.w-yjaja=1,,n

uja-(xT.w-yja)ja=1,,n

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

minZ=ja=1nuja

xT.w-uja+s1=yjaja=1,,n

xT.w+uja+s2)=-yjaja=1,,n

z zastrzeżeniem s10;s2)0;uja0 ja=1,...,n

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

uja jest wybierany jako wejściowa zmienna podstawowa. Nadchodzi problem. Wybierając wyjściową zmienną podstawową, oczywiste jest, że yi/1=yi/1=yi . Zgodnie z uwagą, jeśli yja0 , 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.

Southdoor
źródło
2
Pragmatycznie używasz liniowego solvera programowego zamiast pisać własny. Polecam gurobi.
Matthew Drury,
1
@MatthewDrury Dzięki za odpowiedź. Ale chcę dokładnie wiedzieć, jak LP działa w tym problemie, zamiast po prostu wziąć odpowiedź.
southdoor
1
Czy znasz, czy używałeś „metody simpleksowej” Google?
2
Program liniowy jest tylko sformułowaniem problemu pod względem maksymalizacji (lub minimalizacji) liniowej funkcji celu podlegającej pewnym ograniczeniom liniowym. Sam siebie „nie rozwiązuje”. Istnieje wiele algorytmów, które rozwiązują te specjalnie sformułowane programy, jednym z najczęściej używanych jest Simplex
Łukasz Grad
1
@fcop Tak, rzeczywiście przeczytałem kilka uwag na temat metody simplex. Ale nie mam pojęcia, jak wygenerować ten problem. Ponieważ przykłady w tych notatkach są bardzo proste i konkretne. Nie mogę znaleźć jednego z ogólnymi problemami. Spędziłem już dwie noce na tym problemie, ale nadal jestem zdezorientowany. Przepraszam.
southdoor

Odpowiedzi:

5

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 quantregpakietem R :

rq_LP  <-  function(x, Y, r=0.5, intercept=TRUE) {
    require("lpSolve")
    if (intercept) X  <-  cbind(1, x) else X <-  cbind(x)
    N   <-  length(Y)
    n  <-  nrow(X)
    stopifnot(n == N)
    p  <-  ncol(X)
    c  <-  c(rep(r, n), rep(1-r, n), rep(0, 2*p))  # cost coefficient vector
    A  <- cbind(diag(n), -diag(n), X, -X)
    res  <-  lp("min", c, A, "=", Y, compute.sens=1)
### Desempaquetar los coefs:
    sol <- res$solution
    coef1  <-  sol[(2*n+1):(2*n+2*p)]
    coef <- numeric(length=p)
    for (i in seq(along=coef)) {
         coef[i] <- (if(coef1[i]<=0)-1 else +1) *  max(coef1[i], coef1[i+p])
    }
    return(coef)
    }

Następnie używamy go w prostym przykładzie:

library(robustbase)
data(starsCYG)
Y  <- starsCYG[, 2]
x  <- starsCYG[, 1]
rq_LP(x, Y)
[1]  8.1492045 -0.6931818

wtedy sam możesz to sprawdzić za pomocą quantreg.

kjetil b halvorsen
źródło
2
+1 Jestem wielkim fanem robienia rzeczy ręcznie i inaczej niż porównuj!
Haitao Du
3
Post z nieco więcej wyjaśnień znajduje się w regresji kwantowej
Szybko przestań zamykać pytania
2

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/

Haitao Du
źródło
2
Dzięki za odpowiedź. Ale kiedy próbuję wyszukać w książce termin „metoda simpleksowa”, nie mogę go znaleźć. A zestaw narzędzi CVX jest tylko narzędziem do wprowadzania danych jako problemu LP i uruchamiania algorytmu. Ale tak naprawdę chcę, aby algorytm działał w tym problemie. Ani wynik końcowy, ani sposób sformułowania problemu. Ale krok, aby uzyskać wynik. dzięki
southdoor,