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 destination points find the point which minimizes the sum of Euclidean distances from 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 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 -component is weighted differently from the -component. A Weiszfeld algorithm is studied to compute 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 is not a destination point, the iteration matrix at is shown to be convergent and local convergence is always linear. When 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 to be a destination, is derived. Comparisons are made between the symmetric and asymmetric problems. Numerical examples are given.
|52B55||Computational aspects related to geometric convexity|