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)
A Weiszfeld algorithm for the solution of an asymmetric extension of the generalized Fermat location problem. (English) Zbl 1189.90086
Summary: The Generalized Fermat Problem (in the plane) is: given n3 destination points find the point x * which minimizes the sum of Euclidean distances from x * to each of the destination points. The Weiszfeld iterative algorithm for this problem is globally convergent, independent of the initial guess. Also, a test is available, a priori, to determine when x * is a destination point. This paper generalizes earlier work by the first author by introducing an asymmetric Euclidean distance in which, at each destination, the x-component is weighted differently from the y-component. A Weiszfeld algorithm is studied to compute x * and is shown to be a descent method which is globally convergent (except possibly for a denumerable number of starting points). Local convergence properties are characterized. When x * is not a destination point, the iteration matrix at x * is shown to be convergent and local convergence is always linear. When x * is a destination point, local convergence can be linear, sub-linear or super-linear, depending upon a computable criterion. A test, which does not require iteration, for x * to be a destination, is derived. Comparisons are made between the symmetric and asymmetric problems. Numerical examples are given.
90B85Continuous location
52B55Computational aspects related to geometric convexity
[1]Cooper, L.: Location–allocation problems, Oper. res. 11, 331-343 (1963) · Zbl 0113.14201 · doi:10.1287/opre.11.3.331
[2]Cooper, L.: Heuristic methods for location–allocation problems, SIAM rev. 6, 37-52 (1964)
[3]Cooper, L.: Solutions of generalized locational equilibrium problems, J. regional sci. 7, 1-18 (1967)
[4]Cooper, L.: An extension of the generalized Weber problem, J. regional sci. 8, 181-197 (1968)
[5]Cooper, L.; Katz, I. Norman: The Weber problem revisited, J. comput. Math. appl. 7, 225-235 (1981) · Zbl 0457.65044 · doi:10.1016/0898-1221(81)90082-1
[6]Katz, I. Norman: On the convergence of a numerical scheme for solving some locational equilibrium problems, SIAM J. Appl. math. 17, 1224-1231 (1969) · Zbl 0187.18001 · doi:10.1137/0117113
[7]Katz, I. Norman: Local convergence in Fermat’s problem, Math. program. 6, 89-104 (1974) · Zbl 0291.90069 · doi:10.1007/BF01580224
[8]Kuhn, H. W.; Kuenne, R. E.: An efficient algorithm for the numerical solution of the generalized Weber problem in spatial economics, J. regional sci. 4, 21-23 (1962)
[9]Kuhn, H. W.: A note on Fermat’s problem, Math. program. 4, 98-107 (1973) · Zbl 0255.90063 · doi:10.1007/BF01584648
[10]Miehle, W.: Link-length minimization in networks, Oper. res. 6, 232-243 (1958)
[11]Plastria, Frank; Elosmani, Mohamed: On the convergence of the weiszfeld algorithm for continuous single facility location–allocation problems, Top 16, 388-406 (2008) · Zbl 1154.90531 · doi:10.1007/s11750-008-0056-1
[12]Morris, James G.: Convergence of the weiszfeld algorithm for Weber problems using a generalized ”distance” function, Oper. res. 29, 37-47 (1981) · Zbl 0452.90023 · doi:10.1287/opre.29.1.37
[13]Xue, G.; Ye, Y.: An efficient algorithm for minimizing a sum of P-norms, SIAM J. Optim. (1997)
[14]Eckhardt, Ulrich: Weber’s problem and weiszfeld’s algorithm in general spaces, Math. program. 18, 186-196 (1980) · Zbl 0433.65035 · doi:10.1007/BF01588313
[15]Li, Y.: A Newton acceleration of the weiszfeld algorithm for minimizing the sum of Euclidean distances, Comput. optim. Appl. 10, 219-242 (1998) · Zbl 0912.90197 · doi:10.1023/A:1018333422414
[16]Edmund, K. A.; Christiansen, E.; Conn, A. R.; Overton, M. L.: An efficient primal-dual interior-point method for minimizing a sum of Euclidean norms, SIAM J. Sci. comput. (1998)
[17]Weiszfeld, E.: Sur le point pour lequel la sommme des distances de n points donnes est minimum, Tohoku math. J. 43, 355-386 (1937) · Zbl 0017.18007 · doi:10.2748/tmj/1178227459
[18]Golub, G. H.; Van Loan, C. F.: Matrix computations, (1989)