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

The Generalized Fermat Problem (in the plane) is: given n≥3n≥3 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, à priori, to determine when x̄∗ a destination point. This paper generalizes earlier work by the first author by introducing an asymmetric Euclidean distance in which, at each destination, the xx-component is weighted differently from the yy-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.