Minimización de una suma de distancias de taxis formulada como un programa lineal

Question

Supongamos que nos dan $n$ puntos $A_1, \dots, A_n \in \mathbb{R}^2$ . La tarea consiste en encontrar un punto $x = (x_1,x_2) \in \mathbb{R}^2$ tal que la suma de las distancias a los puntos $A_1, \dots, A_n$ en el $\ell_1$ -se minimiza. Formule este problema como un programa lineal.

Así que, en primer lugar, el $\ell_1$ -norma de un punto $x=(x_1,x_2)\in\mathbb{R}^2$ es $\|x\|_1=|x_1|+|x_2|$ . El problema sería entonces

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

sin restricciones. Pero, ¿cómo se puede formular esto como un programa lineal?

Answer 1

Versión 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}$$

versión 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

Supongamos que nos dan $n$ puntos $\mathrm a_1, \mathrm a_2, \dots, \mathrm a_n \in \mathbb{R}^2$ . Sea

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

Los vectores de desplazamiento de un $\mathrm x$ a cada punto $\mathrm a_i$ son las columnas de la matriz

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

La suma de los taxi distancias de un general $\mathrm x$ a cada punto $\mathrm a_i$ viene dado por

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

que puede escribirse como programa lineal en $\mathrm x \in \mathbb R^2$ y $\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}}$$

---

Anexo

Del apartado 6.1.1 de Boyd & Vandenberghe :