Wie löse ich die geringste absolute Abweichung mit der Simplex-Methode?

12

argminwL(w)=i=1n|yiwTx|

mini=1nui

uixTwyii=1,,n

ui(xTwyi)i=1,,n

Aber ich habe keine Ahnung, wie ich es Schritt für Schritt lösen soll, da ich LP-Neuling bin. Hast du irgendeine Idee? Danke im Voraus!

BEARBEITEN:

Hier ist der letzte Stand, den ich bei diesem Problem erreicht habe. Ich versuche das Problem zu lösen, indem ich diesen Hinweis befolge :

Schritt 1: Formulieren Sie es zu einem Standardformular

minZ=i=1nui

xTwui+s1=yii=1,,n

xTw+ui+s2=yii=1,,n

vorbehaltlichs10;s20;ui0 i=1,...,n

Schritt 2: Erstellen Sie ein erstes Tableau

           |      |    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

Schritt 3: Wählen Sie grundlegende Variablen

uiAls Eingangsbasisvariable wird gewählt. Hier kommt ein Problem. Bei der Auswahl der Ausgabegrundvariablen ist es offensichtlich, dass . Laut dem Hinweis, wenn , hat das Problem unbegrenzte Lösung.yi/1=yi/1=yiyi0

Ich bin hier total verloren. Ich frage mich, ob etwas nicht stimmt und wie ich die folgenden Schritte fortsetzen soll.

Südtür
quelle
2
Pragmatisch gesehen verwenden Sie einen linearen Programmlöser, anstatt Ihren eigenen zu schreiben. Ich empfehle Gurobi.
Matthew Drury
1
@MatthewDrury Danke für deine Antwort. Aber ich möchte genau wissen, wie LP bei diesem Problem funktioniert, anstatt nur die Antwort zu nehmen.
Südtür
1
Kennen Sie die Simplex-Methode von Google?
2
Das lineare Programm ist nur eine Formulierung Ihres Problems in Bezug auf die Maximierung (oder Minimierung) der linearen Zielfunktion, die einigen linearen Einschränkungen unterliegt. Es "löst" sich nicht von selbst. Es gibt eine Reihe von Algorithmen, die diese speziell formulierten Programme lösen. Eine der am häufigsten verwendeten ist Simplex
Łukasz Grad
1
@fcop Ja, in der Tat habe ich einige Anmerkungen zur Simplex-Methode gelesen. Aber ich habe keine Ahnung, wie ich es zu diesem Problem generieren soll. Da die Beispiele in diesen Notizen sehr einfach und spezifisch sind. Ich kann nicht feststellen, dass man mit allgemeinen Problemen anfängt. Ich habe bereits zwei Nächte in diesem Problem verbracht, aber immer noch verwirrt. Es tut uns leid.
Southdoor

Antworten:

5

Sie möchten ein Beispiel für die Lösung der geringsten absoluten Abweichung durch lineare Programmierung. Ich werde Ihnen eine einfache Implementierung in R zeigen. Quantile Regression ist eine Verallgemeinerung der geringsten absoluten Abweichung, wie dies beim Quantil 0.5 der Fall ist. Ich werde daher eine Lösung für die Quantile Regression zeigen. Dann können Sie die Ergebnisse mit dem R- quantregPaket überprüfen :

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)
    }

Dann verwenden wir es in einem einfachen Beispiel:

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

dann kannst du selbst die Prüfung mit machen quantreg.

kjetil b halvorsen
quelle
2
+1 Ich bin ein großer Fan davon, Dinge manuell und anders als im Vergleich zu machen!
Haitao Du
3
Für einen Beitrag mit etwas mehr Erklärung siehe Quantile Regression
Stop Closing Questions Fast
2

Die lineare Programmierung kann mit einer konvexen Optimierung verallgemeinert werden, bei der zusätzlich zu Simplex viele zuverlässigere Algorithmen zur Verfügung stehen.

Ich empfehle Ihnen, das Convex Optimization Book und die von ihnen bereitgestellte CVX-Toolbox zu überprüfen. Wo Sie mit Regularisierung leicht die geringste absolute Abweichung formulieren können.

https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

http://cvxr.com/cvx/

Haitao Du
quelle
2
Danke für deine Antwort. Aber wenn ich versuche, den Begriff "Simplex-Methode" in dem Buch zu suchen, kann ich keinen finden. Und die CVX-Toolbox ist nur ein Tool, mit dem Sie Eingaben als LP-Problem erfassen und den Algorithmus ausführen können. Was ich aber wirklich will, ist, wie der Algorithmus bei diesem Problem funktioniert. Weder das Endergebnis, noch wie man das Problem formuliert. Aber der Schritt zum Ergebnis. Danke
Southdoor