4
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ math.stackexchange.com/questions/692675/… should be helpful. $\endgroup$ – user159517 Nov 12 '16 at 12:59
  • $\begingroup$ Well, I´m not sure how this helps me to formulate a linear program because I would have piecewise functions then... $\endgroup$ – WinterMensch Nov 12 '16 at 16:13
  • $\begingroup$ I don't see how to write it as one linear porgram either, but you can split it up into several linear programs where you have linear objective functions (e.g. one where $x_1 \geq A_{i1}, x_2 \geq A_{i2}$ for all $i$ with objective function $\sum_{i=1}^{n} x_1 + x_2 $). If you solve each one, you can then compare the minima you obtained to find the minimum of the original objective function. $\endgroup$ – user159517 Nov 12 '16 at 17:54
  • $\begingroup$ math.stackexchange.com/questions/432003/… $\endgroup$ – user477602 Dec 17 '17 at 12:59
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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:

enter image description here

$\endgroup$
1
  • $\begingroup$ This is similar to Erwin's 2nd linear program, but in vectorized form. $\endgroup$ – Rodrigo de Azevedo Nov 13 '16 at 10:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.