# Simplex algorithm for least absolute deviation

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!

• 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. – Brian Borchers Feb 6 '17 at 15:58
• @BrianBorchers Thanks for your reply. Sorry it was a mistake. I have edited it. – southdoor Feb 6 '17 at 18:22
• Your LP is incorrect: you need two constraints per $u_i$. Do you really want to solve a problem with $2n$ constraints by hand? – LinAlg Feb 7 '17 at 6:56
• @LinAlg Thanks for your reply. But what do you mean by $2n$ constraint? thanks a lot – southdoor Feb 7 '17 at 7:07
• If $n=10$ you end up with $20$ constraints. – LinAlg Feb 7 '17 at 8:04