Weber problem

A problem formulated in [a7] as a model for the optimum location of a facility in the plane intended to serve several users; for example, a central source of electric power. One is seeking the minimum of a function

$$f(x)=\sum_{i=1}^nw_i\rho(x-x_i),$$

where the $w_i$ are positive scalars, the $x_i$ are given vectors in $\mathbf R^2$, $x$ is in $\mathbf R^2$ and $\rho(u)$ is the Euclidean norm of $u$. The case when all $w_i=1$ and $n=3$ had been considered by P. Fermat in 1629, by E. Torricelli in 1644 and by J. Steiner in 1837. (For the early history of the problem, see [a4].)

The function $f$ is convex (cf. Convex function (of a real variable)) and one shows that, with some exceptions, it has a unique minimizer. These assertions remain valid when $\rho$ is allowed to be an arbitrary norm and $\mathbf R^2$ is replaced by $\mathbf R^N$.

For applications, of which there are many (see [a1]), one seeks good computational methods for finding a minimizer of $f$, either with the Euclidean norm or with other norms. For the Euclidean case, E. Weiszfeld [a8] provided a much used method; see [a6] for a discussion of this and other cases. If $\rho$ is the $\mathrm l_1$-norm, explicit solution is possible (see [a2], Chap. 4).

Minimizing the function $f$ is a problem in optimization and it is natural to seek a dual problem (cf. Duality in extremal problems and convex analysis): to maximize a function $g$ such that $\max g=\min f$. A dual was found for special cases by H.W. Kuhn and others [a4]. A major result in this direction was provided by C. Witzgall in [a9], who provided a dual for a more general minimum problem, in which the function to be minimized has the form

$$F(x)=\sum_{i=1}^n[w_i\rho(x-x_i)+w_i'\rho'(x-x_i)],$$

where $\rho$ is now allowed to be an asymmetric norm in $\mathbf R^N$ (that is, $\rho(tx)=t\rho(x)$ is required to be valid only for non-negative $t$) and $\rho'(x)=\rho(-x)$. Witzgall's result and others are subsumed under a duality theorem of W. Kaplan and W.H. Yang [a3]. In this theorem, the function $f$ has the form

$$f(x)=\sigma(A^Tx-c)+b^Tx$$

in $\mathbf R^m$, where $\sigma$ is a norm, allowed to be asymmetric, in $\mathbf R^n$, $A$ is a constant $(m\times n)$-matrix, $b$ in $\mathbf R^m$ and $c$ in $\mathbf R^n$ are constant vectors. The dual function $g$ is the linear function $g(y)=c^ty$ in $\mathbf R^n$, subject to the constraints $Ay=b$ and $\rho'(y)\leq1$, where $\rho$ and $\sigma$ are dual norms in $\mathbf R^n$: $\sigma(y)=\max\{x^Ty\colon\rho(x)=1\}$. It is assumed that the equation $Ay=b$ has a solution with $\rho'(y)<1$. In [a3] it is shown how, when the norms are differentiable (except at the origin), a minimizer of $f$ can be obtained from or determines a maximizer of $g$. It is also shown that the theorem provides a dual for the multi-facility location problem, for which the function $f$ to be minimized is the sum of the weighted distances from $k$ new facilities to $n$ given facilities as well as the weighted distances between the new facilities; the function $f$ is a convex function of $(x_1,\dots,x_n)$, where the $i$th new facility is placed at $x_i$.

The Weber problem has been generalized in many ways to fit the great variety of problems arising in the location of facilities. See [a1] for an overview.

References

[a1]	Z. Drezner, "Facility location, a survey of applications and methods" , Springer (1995)
[a2]	R.L. Francis, J.A. White, "Facility layout and location: an analytical approach" , Prentice-Hall (1974)
[a3]	W. Kaplan, W.H. Yang, "Duality theorem for a generalized Fermat–Weber problem" Math. Progr. , 7 : 6 (1997) pp. 285–297
[a4]	H.W. Kuhn, "On a pair of dual nonlinear programs" J. Abadie (ed.) , Nonlinear programming , Wiley (1967) pp. 39–54
[a5]	R.F. Love, J.G. Morris, G.O. Wesolovsky, "Facilities location, models and methods" , North-Holland (1988)
[a6]	F. Plastria, "Continuous location problems" Z. Drezner (ed.) , Facility location, a survey of applications and methods , Springer (1995) pp. 225–262
[a7]	A. Weber, "Theory of the location of industries" , Univ. Chicago Press (1957) (Translated from German)
[a8]	E. Weiszfeld, "Sur le point lequel la somme des distances de $n$ points donnés est minimum" Tôhoku Math. J. , 43 (1937) pp. 355–386
[a9]	C. Witzgall, "Optimal location of a central facility: mathematical models and concepts" Nat. Bureau Standards Report , 8388 (1964)