A Weiszfeld algorithm for the solution of an asymmetric extension of the generalized Fermat location problem

作者：Katz I Norman^*; Vogl Steven R

来源：Computers & Mathematics with Applications, 2010, 59(1): 399-410.

DOI：10.1016/j.camwa.2009.07.007

• Generalized Fermat location
• Asymmetric distance
• Weiszfeld algorithm

The Generalized Fermat Problem (in the plane) is: given n >= 3 destination points rind the point (x) over bar* which minimizes the sum of Euclidean distances from (x) over bar* 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, 6 priori, to determine when (x) over bar* 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) over bar* 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) over bar* is not a destination point the iteration matrix at (x) over bar* is shown to be convergent and local convergence is always linear. When (x) over bar* 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) over bar* to be a destination, is derived. Comparisons are made between the symmetric and asymmetric problems. Numerical examples are given.

• 出版日期2010-1