$\underset{\textbf{w}}{\arg\min} L(w)=\sum_{i=1}^{n}|y_{i}-\textbf{w}^T\textbf{x}|$

$\min \sum_{i=1}^{n}u_{i}$

$u_i \geq \textbf{x}^T\textbf{w}- y_{i} \; i = 1,\ldots,n$

$u_i \geq -\left(\textbf{x}^T\textbf{w}-y_{i}\right) \; i = 1,\ldots,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

$\min Z=\sum_{i=1}^{n}u_{i}$

$\textbf{x}^T\textbf{w} -u_i+s_1=y_{i} \; i = 1,\ldots,n$

$\textbf{x}^T\textbf{w} +u_i+s_2=-y_{i} \; i = 1,\ldots,n$

vorbehaltlich$s_1 \ge 0; s_2\ge 0; u_i \ge 0 \ 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

$u_i$Als 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.$y_i/-1=-y_i/1=-y_i$$y_i\ge0$

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

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.

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/