12
$\begingroup$

Here is the least absolute deviation problem under concerned: $ \underset{\textbf{w}}{\arg\min} L(w)=\sum_{i=1}^{n}|y_{i}-\textbf{w}^T\textbf{x}|$. I know it can be rearranged as LP problem in following way:

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

But I have no idea to solve it step by step, as I am a newbie to LP. Do you have any idea? Thanks in advance!

EDIT:

Here is the latest stage I have reached at this problem. I am trying to solve the problem following this note:

Step 1: Formulating it to a standard form

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

subject to $s_1 \ge 0; s_2\ge 0; u_i \ge 0 \ i=1,...,n$

Step 2: Construct a initial 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

Step 3: Choose basic variables

$u_i$ is chosen as input base variable. Here comes a problem. When choosing the output base variable, it is obvious $y_i/-1=-y_i/1=-y_i$. According to the note, if $y_i\ge0$, the problem has unbounded solution.

I am totally lost here. I wonder if there is anything wrong and how should I continue the following steps.

$\endgroup$
  • 2
    $\begingroup$ Pragmatically, you use a linear program solver instead of writing your own. I reccomend gurobi. $\endgroup$ – Matthew Drury Feb 7 '17 at 15:25
  • 1
    $\begingroup$ @MatthewDrury Thanks for you reply. But I want to know exactly how LP works in this problem, instead of just taking the answer. $\endgroup$ – southdoor Feb 7 '17 at 15:26
  • 1
    $\begingroup$ Do you know or did you Google 'simplex method'? $\endgroup$ – user83346 Feb 7 '17 at 15:32
  • 2
    $\begingroup$ Linear program is just a formulation of your problem in terms of maximizing (or minimizing) of linear goal function subject to some linear constraints. It doesn't "solve" itself. There are a bunch of algorithms that solve these specially formulated programs, one of most commonly used is Simplex $\endgroup$ – Łukasz Grad Feb 7 '17 at 15:33
  • 1
    $\begingroup$ @fcop Yes, indeed I have read some notes of simplex method. But I have no idea how to generate it to this problem. As the examples in those notes are very simple and specific. I can not find one begin with general problems. I have already spent two nights in this problem, but still being confused. Sorry. $\endgroup$ – southdoor Feb 7 '17 at 15:34
5
$\begingroup$

You want an example for solving least absolute deviation by linear programming. I will show you an simple implementation in R. Quantile regression is a generalization of least absolute deviation, which is the case of the quantile 0.5, so I will show a solution for quantile regression. Then you can check the results with the R quantreg package:

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

Then we use it in a simple example:

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

then you yourself can do the check with quantreg.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ +1 I am a big fan of doing things manually and differently then compare! $\endgroup$ – Haitao Du Mar 27 '17 at 16:47
  • 3
    $\begingroup$ For a post with a little more explanation see quantile regression $\endgroup$ – Jesper for President Dec 29 '18 at 22:05
2
$\begingroup$

Linear Programming can be generalized with convex optimization, where in addition to simplex, many more reliable algorithms are available.

I would suggest you to check The Convex Optimization Book and the CVX toolbox they provided. Where you can easily formulate least absolute deviation with regularization.

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

http://cvxr.com/cvx/

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Thanks for your answer. But when I try to search the term "simplex method" in the book, I can't find any. And the CVX toolbox is just a tool for take input as the LP problem and run the algorithm. But what I really want is how the algorithm works in this problem. Neither the final result, nor how to formulate the problem. But the step to get the result. thanks $\endgroup$ – southdoor Feb 7 '17 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.