7.2.3: Location Problems

The Fermat-Weber problem is to find a point $x\in\mathbb{R}^m$ such that the sum of the Euclidean distances to $m$ given points $y_1,\cdots,y_m$ is minimized. Thus our loss function is $$f(x)=\sum_{j=1}^m w_jd(x,y_j),$$ where the $w_j$ are positive weights. Other names are the single facility location problem or the spatial median problem.

An early iterative algorithm to solve the Fermat-Weber problem was proposed by Weiszfeld [1937]. For a translation see Plastria [].

Here we show how to use the arithmetic mean-geometric mean inequality for majorization. Suppose our problem is to minimize $$f(X)=\sum_{i=1}^n\sum_{j=1}^n w_{ij}d_{ij}(X),$$ where the $w_{ij}$ are non-negative weights, and the $d_{ij}(X)$ are again Euclidean distances. This is a location problem. To make it interesting, we suppose that some of the points (facilities) are fixed, others are the variables we have to minimize over. Observe that this is a convex, but non-differentiable, optimization problem.

We use the AM-GM inequality in the form $$d_{ij}(X)d_{ij}(Y)\leq\frac{1}{2}(d_{ij}^2(X)+d_{ij}^2(Y)).$$ If $d_{ij}(Y)>0$ then $d_{ij}(X)\leq\frac{1}{2}\frac{d_{ij}^2(X)+d_{ij}^2(Y)} {d_{ij}(Y)}.$ Using the notation from Example a.a we now find $\phi(X)\leq\frac{1}{2}(\hbox{tr }X'B(Y)X+\hbox{tr }Y'B(Y)Y),$ which gives us a quadratic majorization.

If $X$ is partitioned into $X_1$ and $X_2,$ with rows which are fixed and rows which are to be determined (facilities which have to be located), and $B$ is partitioned correspondingly, then the algorithm we find is $X_2^{(k+1)}=B_{22}(X^{(k)})^{-1}B_{21}(X^{(k)})X_1.$