Minimization of a sum of taxicab distances formulated as a linear program

Question

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.

So, first of all, the $\ell_1$-norm of a point $x=(x_1,x_2)\in\mathbb{R}^2$ is $\|x\|_1=|x_1|+|x_2|$. The problem would then be

$$\min \sum\limits_{i=1}^n \|x-A_i\|_1 = \min \sum\limits_{i=1}^n|x_1-A_{i1}|+|x_2-A_{i2}|$$

with no constraints. But how can one formulate this as a linear program?

Answer 1

version 1.

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

version 2.

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

Answer 2

Suppose we are given $n$ points $\mathrm a_1, \mathrm a_2, \dots, \mathrm a_n \in \mathbb{R}^2$. Let

$$\mathrm A := \begin{bmatrix} | & | & & |\\ \mathrm a_1 & \mathrm a_2 & \dots & \mathrm a_n\\ | & | & & |\end{bmatrix}$$

The displacement vectors from a general $\mathrm x$ to each point $\mathrm a_i$ are the columns of the matrix

$$\mathrm x 1_n^{\top} - \mathrm A = (1_n \otimes \mathrm I_2) \, \mbox{vec} (\mathrm x) - \mbox{vec} (\mathrm A) = (1_n \otimes \mathrm I_2) \, \mathrm x - \mbox{vec} (\mathrm A)$$

The sum of the taxicab distances from a general $\mathrm x$ to each point $\mathrm a_i$ is given by

$$\text{minimize} \quad \| (1_n \otimes \mathrm I_2) \, \mathrm x - \mbox{vec} (\mathrm A) \|_1$$

which can be written as the linear program in $\mathrm x \in \mathbb R^2$ and $\mathrm y \in \mathbb R^{2n}$

$$\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\end{array}}$$

---

Addendum

From section 6.1.1 of Boyd & Vandenberghe: