Bagaimana mengatasi penyimpangan absolut terkecil dengan metode simpleks?

12

Berikut adalah masalah deviasi absolut terkecil yang terkait:. Saya tahu ini bisa diatur ulang sebagai masalah LP dengan cara berikut:argminwL(w)=i=1n|yiwTx|

mini=1nui

uixTwyii=1,,n

ui(xTwyi)i=1,,n

Tapi saya tidak punya ide untuk menyelesaikannya langkah demi langkah, karena saya seorang pemula untuk LP. Apakah kamu punya ide? Terima kasih sebelumnya!

EDIT:

Inilah tahap terakhir yang saya capai pada masalah ini. Saya mencoba menyelesaikan masalah dengan mengikuti catatan ini :

Langkah 1: Merumuskannya ke bentuk standar

minZ=i=1nui

xTwui+s1=yii=1,,n

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

tunduk pada s10;s20;ui0 i=1,...,n

Langkah 2: Buat tablo awal

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

Langkah 3: Pilih variabel dasar

ui dipilih sebagai variabel basis input. Di sinilah masalah. Ketika memilih variabel basis output, jelas yi/1=yi/1=yi . Menurut catatan, jika yi0 , masalah memiliki solusi tidak terikat.

Saya benar-benar tersesat di sini. Saya bertanya-tanya apakah ada yang salah dan bagaimana saya harus melanjutkan langkah-langkah berikut.

pintu selatan
sumber
2
Secara pragmatis, Anda menggunakan pemecah program linier alih-alih menulis sendiri. Saya merekomendasikan gurobi.
Matthew Drury
1
@MatthewDrury Terima kasih atas balasan Anda. Tapi saya ingin tahu persis bagaimana LP bekerja dalam masalah ini, bukan hanya mengambil jawabannya.
southdoor
1
Apakah Anda tahu atau apakah Anda Google 'metode simpleks'?
2
Program linear hanyalah perumusan masalah Anda dalam hal memaksimalkan (atau meminimalkan) fungsi tujuan linear yang tunduk pada beberapa kendala linier. Itu tidak "memecahkan" dirinya sendiri. Ada banyak algoritma yang menyelesaikan program yang diformulasikan khusus ini, salah satu yang paling umum digunakan adalah Simplex
Łukasz Grad
1
@ fcop Ya, memang saya telah membaca beberapa catatan metode simpleks. Tetapi saya tidak tahu bagaimana cara menghasilkannya untuk masalah ini. Sebagai contoh dalam catatan itu sangat sederhana dan spesifik. Saya tidak dapat menemukannya dengan masalah umum. Saya sudah menghabiskan dua malam dalam masalah ini, tetapi masih bingung. Maaf.
southdoor

Jawaban:

5

Anda ingin contoh untuk menyelesaikan deviasi absolut terkecil oleh pemrograman linier. Saya akan menunjukkan kepada Anda implementasi sederhana dalam R. Regresi kuantil adalah generalisasi dari deviasi absolut terkecil, yang merupakan kasus dari kuantil 0,5, jadi saya akan menunjukkan solusi untuk regresi kuantil. Kemudian Anda dapat memeriksa hasilnya dengan quantregpaket 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)
    }

Kemudian kami menggunakannya dalam contoh sederhana:

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

maka Anda sendiri dapat melakukan cek dengan quantreg.

kjetil b halvorsen
sumber
2
+1 Saya penggemar berat melakukan hal-hal secara manual dan berbeda kemudian membandingkan!
Haitao Du
3
Untuk posting dengan penjelasan lebih lanjut, lihat regresi kuantitatif
Stop Closing Question Fast
2

Linear Programming dapat digeneralisasi dengan optimasi cembung, di mana selain simpleks, banyak algoritma yang lebih andal tersedia.

Saya akan menyarankan Anda untuk memeriksa Buku Optimasi Cembung dan kotak alat CVX yang mereka berikan. Di mana Anda dapat dengan mudah merumuskan deviasi absolut terkecil dengan regularisasi.

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

http://cvxr.com/cvx/

Haitao Du
sumber
2
Terima kasih atas jawaban anda. Tetapi ketika saya mencoba mencari istilah "metode simpleks" di buku, saya tidak dapat menemukannya. Dan kotak alat CVX hanyalah alat untuk mengambil input sebagai masalah LP dan menjalankan algoritme. Tapi yang saya inginkan adalah bagaimana algoritma bekerja dalam masalah ini. Baik hasil akhir, maupun cara merumuskan masalah. Tetapi langkah untuk mendapatkan hasilnya. terima kasih
southdoor