Namespaces
Variants
Actions

Difference between revisions of "Weber problem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
Line 1: Line 1:
 +
{{TEX|done}}
 
A problem formulated in [[#References|[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
 
A problem formulated in [[#References|[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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w1200401.png" /></td> </tr></table>
+
$$f(x)=\sum_{i=1}^nw_i\rho(x-x_i),$$
  
where the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w1200402.png" /> are positive scalars, the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w1200403.png" /> are given vectors in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w1200404.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w1200405.png" /> is in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w1200406.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w1200407.png" /> is the Euclidean norm of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w1200408.png" />. The case when all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w1200409.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004010.png" /> 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 [[#References|[a4]]].)
+
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 [[#References|[a4]]].)
  
The function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004011.png" /> is convex (cf. [[Convex function (of a real variable)|Convex function (of a real variable)]]) and one shows that, with some exceptions, it has a unique minimizer. These assertions remain valid when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004012.png" /> is allowed to be an arbitrary norm and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004013.png" /> is replaced by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004014.png" />.
+
The function $f$ is convex (cf. [[Convex function (of a real variable)|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 [[#References|[a1]]]), one seeks good computational methods for finding a minimizer of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004015.png" />, either with the Euclidean norm or with other norms. For the Euclidean case, E. Weiszfeld [[#References|[a8]]] provided a much used method; see [[#References|[a6]]] for a discussion of this and other cases. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004016.png" /> is the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004017.png" />-norm, explicit solution is possible (see [[#References|[a2]]], Chap. 4).
+
For applications, of which there are many (see [[#References|[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 [[#References|[a8]]] provided a much used method; see [[#References|[a6]]] for a discussion of this and other cases. If $\rho$ is the $\mathrm l_1$-norm, explicit solution is possible (see [[#References|[a2]]], Chap. 4).
  
Minimizing the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004018.png" /> is a problem in optimization and it is natural to seek a dual problem (cf. [[Duality|Duality]] in extremal problems and convex analysis): to maximize a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004019.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004020.png" />. A dual was found for special cases by H.W. Kuhn and others [[#References|[a4]]]. A major result in this direction was provided by C. Witzgall in [[#References|[a9]]], who provided a dual for a more general minimum problem, in which the function to be minimized has the form
+
Minimizing the function $f$ is a problem in optimization and it is natural to seek a dual problem (cf. [[Duality|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 [[#References|[a4]]]. A major result in this direction was provided by C. Witzgall in [[#References|[a9]]], who provided a dual for a more general minimum problem, in which the function to be minimized has the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004021.png" /></td> </tr></table>
+
$$F(x)=\sum_{i=1}^n[w_i\rho(x-x_i)+w_i'\rho'(x-x_i)],$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004022.png" /> is now allowed to be an asymmetric norm in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004023.png" /> (that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004024.png" /> is required to be valid only for non-negative <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004025.png" />) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004026.png" />. Witzgall's result and others are subsumed under a duality theorem of W. Kaplan and W.H. Yang [[#References|[a3]]]. In this theorem, the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004027.png" /> has the form
+
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 [[#References|[a3]]]. In this theorem, the function $f$ has the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004028.png" /></td> </tr></table>
+
$$f(x)=\sigma(A^Tx-c)+b^Tx$$
  
in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004029.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004030.png" /> is a norm, allowed to be asymmetric, in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004031.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004032.png" /> is a constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004033.png" />-matrix, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004034.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004035.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004036.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004037.png" /> are constant vectors. The dual function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004038.png" /> is the linear function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004039.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004040.png" />, subject to the constraints <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004041.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004042.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004043.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004044.png" /> are dual norms in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004045.png" />: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004046.png" />. It is assumed that the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004047.png" /> has a solution with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004048.png" />. In [[#References|[a3]]] it is shown how, when the norms are differentiable (except at the origin), a minimizer of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004049.png" /> can be obtained from or determines a maximizer of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004050.png" />. It is also shown that the theorem provides a dual for the multi-facility location problem, for which the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004051.png" /> to be minimized is the sum of the weighted distances from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004052.png" /> new facilities to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004053.png" /> given facilities as well as the weighted distances between the new facilities; the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004054.png" /> is a convex function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004055.png" />, where the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004056.png" />th new facility is placed at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004057.png" />.
+
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 [[#References|[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 [[#References|[a1]]] for an overview.
 
The Weber problem has been generalized in many ways to fit the great variety of problems arising in the location of facilities. See [[#References|[a1]]] for an overview.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  Z. Drezner,  "Facility location, a survey of applications and methods" , Springer  (1995)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R.L. Francis,  J.A. White,  "Facility layout and location: an analytical approach" , Prentice-Hall  (1974)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  W. Kaplan,  W.H. Yang,  "Duality theorem for a generalized Fermat–Weber problem"  ''Math. Progr.'' , '''7''' :  6  (1997)  pp. 285–297</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  H.W. Kuhn,  "On a pair of dual nonlinear programs"  J. Abadie (ed.) , ''Nonlinear programming'' , Wiley  (1967)  pp. 39–54</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  R.F. Love,  J.G. Morris,  G.O. Wesolovsky,  "Facilities location, models and methods" , North-Holland  (1988)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  F. Plastria,  "Continuous location problems"  Z. Drezner (ed.) , ''Facility location, a survey of applications and methods'' , Springer  (1995)  pp. 225–262</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  A. Weber,  "Theory of the location of industries" , Univ. Chicago Press  (1957)  (Translated from German)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  E. Weiszfeld,  "Sur le point lequel la somme des distances de <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120040/w12004058.png" /> points donnés est minimum"  ''Tôhoku Math. J.'' , '''43'''  (1937)  pp. 355–386</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  C. Witzgall,  "Optimal location of a central facility: mathematical models and concepts"  ''Nat. Bureau Standards Report'' , '''8388'''  (1964)</TD></TR></table>
+
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  Z. Drezner,  "Facility location, a survey of applications and methods" , Springer  (1995)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R.L. Francis,  J.A. White,  "Facility layout and location: an analytical approach" , Prentice-Hall  (1974)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  W. Kaplan,  W.H. Yang,  "Duality theorem for a generalized Fermat–Weber problem"  ''Math. Progr.'' , '''7''' :  6  (1997)  pp. 285–297</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  H.W. Kuhn,  "On a pair of dual nonlinear programs"  J. Abadie (ed.) , ''Nonlinear programming'' , Wiley  (1967)  pp. 39–54</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  R.F. Love,  J.G. Morris,  G.O. Wesolovsky,  "Facilities location, models and methods" , North-Holland  (1988)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  F. Plastria,  "Continuous location problems"  Z. Drezner (ed.) , ''Facility location, a survey of applications and methods'' , Springer  (1995)  pp. 225–262</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  A. Weber,  "Theory of the location of industries" , Univ. Chicago Press  (1957)  (Translated from German)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  C. Witzgall,  "Optimal location of a central facility: mathematical models and concepts"  ''Nat. Bureau Standards Report'' , '''8388'''  (1964)</TD></TR></table>

Latest revision as of 14:13, 21 August 2014

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)
How to Cite This Entry:
Weber problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Weber_problem&oldid=33043
This article was adapted from an original article by Wilfred Kaplan (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article