zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Open questions concerning Weiszfeld’s algorithm for the Fermat-Weber location problem. (English) Zbl 0683.90026
Summary: The Fermat-Weber location problem is to find a point in ${\bbfR}\sp n$ that minimizes the sum of the weighted Euclidean distances from given points in ${\bbfR}\sp n$. A popular iterative solution method for this problem was first introduced by {\it E. Weiszfeld} [Tôhoku Math. J. 43, 355-386 (1937; Zbl 0017.18007)]. {\it H. W. Kuhn} [Math. Program. 4, 98-107 (1973; Zbl 0255.90063)] claimed that if the given points are not collinear then for all but a denumerable number of starting points the sequence of iterates generated by Weiszfeld’s scheme converges to the unique optimal solution. We demonstrate that Kuhn’s convergence theorem is not always correct. We then conjecture that if this algorithm is initiated at the affine subspace spanned by the given points, the convergence is ensured for all but a denumerable number of starting points.

90B85Continuous location
Full Text: DOI
[1] M. Blum, R.W. Floyd, V.R. Pratt, R.L. Rivest and R.E. Tarjan, ”Time bounds for selection,”Journal of Computer and System Sciences 7 (1972) 448--461. · Zbl 0278.68033 · doi:10.1016/S0022-0000(73)80033-9
[2] P.H. Calamai and A.R. Conn, ”A second-order method for solving the continuous multifacility location problem,” in: G.A. Watson, ed.,Numerical analysis: Proceedings of the Ninth Biennial Conference, Dundee, Scotland, Lecture Notes in Mathematics, Vol. 912 (Springer, Berlin, Heidelberg and New York, 1982) pp. 1--25. · Zbl 0485.65013
[3] J.A. Chatelon, D.W. Hearn and T.J. Lowe, ”A subgradient algorithm for certain minimax and minisum problems,”Mathematical Programming 15 (1978) 130--145. · Zbl 0392.90065 · doi:10.1007/BF01609012
[4] J.W. Eyster, J.A. White and W.W. Wierwille, ”On solving multifacility location problems using a hyperboloid approximation procedure,”AIEE Transactions 5 (1973) 1--6.
[5] I.N. Katz, ”Local convergence in Fermat’s problem,”Mathematical Programming 6 (1974) 89--104. · Zbl 0291.90069 · doi:10.1007/BF01580224
[6] H.W. Kuhn, ”On a pair of dual nonlinear programs,” in: J. Abadie, ed.,Nonlinear Programming (North-Holland, Amsterdam, 1967) pp. 38--54. · Zbl 0183.22804
[7] H.W. Kuhn, ”A note on Fermat’s problem,”Mathematical Programming 4 (1973) 98--107. · Zbl 0255.90063 · doi:10.1007/BF01584648
[8] M.L. Overton, ”A quadratically convergence method for minimizing a sum of Euclidean norms,”Mathematical Programming 27 (1983) 34--63. · Zbl 0536.65053 · doi:10.1007/BF02591963
[9] A. Weber,Theory of the Location of Industries, translated by Carl J. Friedrich (The University of Chicago Press, Chicago, 1937).
[10] E. Weiszfeld, ”Sur le point par lequel la somme des distances den points donnés est minimum,”Tohoku Mathematics Journal 43 (1937) 355--386. · Zbl 63.0583.01