Comment résoudre la moindre déviation absolue par la méthode simplex?

12

Voici le problème d'écart le moins absolu sous concerné:. Je sais qu'il peut être réorganisé comme problème LP de la manière suivante:argminwL(w)=i=1n|yiwTx|

mini=1nui

uixTwyii=1,,n

ui(xTwyi)i=1,,n

Mais je n'ai aucune idée de le résoudre étape par étape, car je suis un débutant chez LP. Avez-vous une idée? Merci d'avance!

ÉDITER:

Voici la dernière étape que j'ai atteinte à ce problème. J'essaie de résoudre le problème suite à cette note :

Étape 1: Formulation sous forme standard

minZ=i=1nui

xTwui+s1=yii=1,,n

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

sous réserve de s10;s20;ui0 i=1,...,n

Étape 2: Construire un tableau initial

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

Étape 3: Choisissez les variables de base

ui est choisi comme variable de base d'entrée. Voici un problème. Lors du choix de la variable de base de sortie, il est évident que yi/1=yi/1=yi . Selon la note, si yi0 , le problème a une solution illimitée.

Je suis totalement perdu ici. Je me demande s'il y a quelque chose qui ne va pas et comment dois-je continuer les étapes suivantes.

porte sud
la source
2
De manière pragmatique, vous utilisez un solveur de programme linéaire au lieu d'écrire le vôtre. Je recommande gurobi.
Matthew Drury
1
@MatthewDrury Merci pour votre réponse. Mais je veux savoir exactement comment LP fonctionne dans ce problème, au lieu de simplement prendre la réponse.
southdoor
1
Connaissez-vous ou avez-vous utilisé la «méthode simplex» de Google?
2
Le programme linéaire n'est qu'une formulation de votre problème en termes de maximisation (ou de minimisation) de la fonction de but linéaire soumise à certaines contraintes linéaires. Il ne se "résout" pas. Il existe un tas d'algorithmes qui résolvent ces programmes spécialement formulés, l'un des plus couramment utilisé est Simplex
Łukasz Grad
1
@fcop Oui, en effet j'ai lu quelques notes de la méthode simplex. Mais je n'ai aucune idée de comment générer ce problème. Comme les exemples dans ces notes sont très simples et spécifiques. Je ne peux pas trouver un commencer par des problèmes généraux. J'ai déjà passé deux nuits dans ce problème, mais toujours confus. Pardon.
southdoor

Réponses:

5

Vous voulez un exemple pour résoudre la moindre déviation absolue par programmation linéaire. Je vais vous montrer une implémentation simple dans R. La régression quantile est une généralisation de l'écart le moins absolu, ce qui est le cas du quantile 0,5, donc je vais vous montrer une solution pour la régression quantile. Ensuite, vous pouvez vérifier les résultats avec le quantregpackage 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)
    }

Ensuite, nous l'utilisons dans un exemple simple:

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

alors vous-même pouvez faire le contrôle avec quantreg.

kjetil b halvorsen
la source
2
+1 Je suis un grand fan de faire les choses manuellement et différemment puis comparer!
Haitao Du
3
Pour un article avec un peu plus d'explications, voir régression quantile
Arrêtez vos questions rapidement
2

La programmation linéaire peut être généralisée avec l'optimisation convexe, où en plus du simplexe, de nombreux algorithmes plus fiables sont disponibles.

Je vous suggère de vérifier le livre d'optimisation convexe et la boîte à outils CVX qu'ils ont fournie. Où vous pouvez facilement formuler l'écart le moins absolu avec la régularisation.

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

http://cvxr.com/cvx/

Haitao Du
la source
2
Merci pour votre réponse. Mais lorsque j'essaie de rechercher le terme «méthode simplex» dans le livre, je n'en trouve aucun. Et la boîte à outils CVX est juste un outil pour prendre en entrée le problème LP et exécuter l'algorithme. Mais ce que je veux vraiment, c'est comment l'algorithme fonctionne dans ce problème. Ni le résultat final, ni comment formuler le problème. Mais l'étape pour obtenir le résultat. merci
southdoor