Como resolver o desvio mínimo absoluto pelo método simplex?

12

Aqui está o problema de desvio menos absoluto em questão:. Eu sei que pode ser reorganizado como problema de LP da seguinte maneira:argminwL(w)=i=1n|yiwTx|

mini=1nui

uixTwyii=1,,n

ui(xTwyi)i=1,,n

Mas não tenho idéia de resolvê-lo passo a passo, pois sou um novato no LP. Você tem alguma ideia? Desde já, obrigado!

EDITAR:

Aqui está o estágio mais recente que cheguei a esse problema. Estou tentando resolver o problema seguindo esta nota :

Etapa 1: Formulando-o em um formulário padrão

minZ=i=1nui

xTwui+s1=yii=1,,n

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

sujeito as10;s20;ui0 i=1,...,n

Etapa 2: construir um quadro inicial

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

Etapa 3: Escolha variáveis ​​básicas

ui é escolhido como variável de base de entrada. Aí vem um problema. Ao escolher a variável base de saída, é óbvio . De acordo com a nota, se , o problema tem solução ilimitada.yi/1=yi/1=yiyi0

Estou totalmente perdido aqui. Gostaria de saber se há algo errado e como devo continuar os seguintes passos.

southdoor
fonte
2
Pragmaticamente, você usa um solucionador de programa linear em vez de escrever o seu. Eu recomendo Gurobi.
Matthew Drury
1
@MatthewDrury Obrigado pela sua resposta. Mas quero saber exatamente como o LP funciona nesse problema, em vez de apenas responder.
southdoor
1
Você conhece ou usou o "método simplex" do Google?
2
O programa linear é apenas uma formulação do seu problema em termos de maximização (ou minimização) da função de objetivo linear, sujeita a algumas restrições lineares. Não "resolve" a si próprio. Há um monte de algoritmos que resolvem esses programas especialmente formulados, um dos mais comumente usado é Simplex
Łukasz Grad
1
@ fcop Sim, na verdade eu li algumas notas do método simplex. Mas não tenho ideia de como gerá-lo para esse problema. Como os exemplos nessas notas são muito simples e específicos. Não consigo encontrar um começo com problemas gerais. Eu já passei duas noites neste problema, mas ainda estou confuso. Desculpe.
southdoor

Respostas:

5

Você deseja um exemplo para resolver o mínimo desvio absoluto pela programação linear. Mostrarei a você uma implementação simples em R. A regressão quantílica é uma generalização de desvio menos absoluto, que é o caso do quantil 0,5; portanto, mostrarei uma solução para a regressão quantil. Então você pode verificar os resultados com o quantregpacote 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)
    }

Em seguida, usamos em um exemplo simples:

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

então você mesmo pode fazer a verificação com quantreg.

kjetil b halvorsen
fonte
2
+1 Eu sou um grande fã de fazer as coisas manualmente e de forma diferente e comparar!
Haitao Du
3
Para um post com um pouco mais de explicação, consulte regressão quantílica
Pare de fechar perguntas rapidamente
2

A programação linear pode ser generalizada com otimização convexa, onde, além do simplex, muitos algoritmos mais confiáveis ​​estão disponíveis.

Eu sugiro que você verifique o Convex Optimization Book e a caixa de ferramentas CVX que eles forneceram. Onde você pode formular facilmente o menor desvio absoluto com regularização.

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

http://cvxr.com/cvx/

Haitao Du
fonte
2
Obrigado pela sua resposta. Mas quando tento pesquisar o termo "método simplex" no livro, não consigo encontrar nenhum. E a caixa de ferramentas CVX é apenas uma ferramenta para considerar a entrada como o problema do LP e executar o algoritmo. Mas o que realmente quero é como o algoritmo funciona nesse problema. Nem o resultado final, nem como formular o problema. Mas o passo para obter o resultado. obrigado
southdoor