My orignal problem is to simply find the minimum of $\sum_i^nq_i|x_i-u|$, where $q_i > 0$ I firstly convert to a standard linear program format as:
$min_u\sum_i^nq_i*t_i$
$t_i >= u - x_i $
$t_i >= x_i - u$
$u,x_i >= 0 \; \forall i = 1,2,...,n$
I was trying to find the dual of this, and I got:
$max\sum_i^n((\lambda_{1i} - \lambda_{2i})(u-x_i) $
$\lambda_{1i} + \lambda_{2i} <= q_i$
$\lambda_{1i},\lambda_{2i} >= 0$
$\forall i = 1,2,3,...,n$
It looks really strange to me, the $u$ is also unknown parameter (as $\lambda$)but how to optimize it in this dual program?
I also think: when $u > x_i$ just choose $\lambda_{1i} = q_i, \lambda_{2i} = 0$, and when $u < x_i$, choose $\lambda_{1i} = 0, \lambda_{2i} = q_i$,could gurrante a maximum value. But this is actually the original format $\sum_i^nq_i|x_i-u|$. This makes me confused.
Is there something wrong when I convert the primal to dual problem?