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$

I have no idea to solve it with simplex method. I don't want to use package but solve it with written computation. Could you please help me with this problem? Thanks in advance!

  • 1
    $\begingroup$ Do want the minimum or maximum (as you've written) of the objective function? The maximization problem is non-convex and can't be formulated as an LP. $\endgroup$ – Brian Borchers Feb 6 '17 at 15:58
  • $\begingroup$ @BrianBorchers Thanks for your reply. Sorry it was a mistake. I have edited it. $\endgroup$ – southdoor Feb 6 '17 at 18:22
  • $\begingroup$ Your LP is incorrect: you need two constraints per $u_i$. Do you really want to solve a problem with $2n$ constraints by hand? $\endgroup$ – LinAlg Feb 7 '17 at 6:56
  • $\begingroup$ @LinAlg Thanks for your reply. But what do you mean by $2n$ constraint? thanks a lot $\endgroup$ – southdoor Feb 7 '17 at 7:07
  • $\begingroup$ If $n=10$ you end up with $20$ constraints. $\endgroup$ – LinAlg Feb 7 '17 at 8:04

Your Answer

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

Browse other questions tagged or ask your own question.