From this post:
Suppose we are given \(n\) points \(A_1, \dots, A_n \in \mathbb{R}^2\). The task is to find a point \(x = (x_1,x_2) \in \mathbb{R}^2\) such that the sum of distances to the points \(A_1, \dots, A_n\) in the \(\ell_1\)-norm is minimized. Formulate this problem as a linear program.
There are at least two (primal) formulations. A variable splitting technique can look like:
| \[\boxed{\begin{align}
\min & \sum_{i,j} y^+_{i,j} + y^-_{i,j}\\
&y^+_{i,j} - y^-_{i,j} = x_j-A_{i,j}\\
&y^+_{i,j}\ge 0, y^-_{i,j}\ge 0
\end{align}}\] |
A different formulation is
| \[\boxed{\begin{align}
\min & \sum_{i,j} y_{i,j}\\
&-y_{i,j} \le x_j-A_{i,j} \le y_{i,j}\\
&y_{i,j}\ge 0
\end{align}}\] |
I don’t think this formulation has a name. We can drop \(y_{i,j}\ge 0\) if we want, as this is implied by \(-y_{i,j}\le y_{i,j}\).
If you let mathematicians loose on this, you may end up with formulation 2 stated as:
| \[\boxed{\begin{array}{ll} \text{minimize} & 1_{2n}^{\top} \mathrm y\\ \text{subject to} & -\mathrm y \leq (1_n \otimes \mathrm I_2) \, \mathrm x - \mbox{vec} (\mathrm A) \leq \mathrm y\\ & \mathrm y \geq 0_{2n}\end{array}}\] |
I don’t really like this type of notation: at least for me it is much less intuitive.
The first formulation has fewer equations but more variables. The second formulation has more constraints as we need to split \(-y_{i,j} \le x_j-A_{i,j} \le y_{i,j}\) into \(x_j-A_{i,j} \ge –y_{i,j}\) and \(x_j-A_{i,j} \le y_{i,j}\). I don’t think there is much reason to choose one formulation above the other. Depending largely on my mood I use either version 1 or 2.
