A geometric perspective of the Weiszfeld algorithm for solving the Fermat−Weber problem
- 12 January 2016
- journal article
- research article
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 50 (1) , 157-173
Abstract
The Fermat−Weber problem is a classical location problem that has the Weiszfeld algorithm as its main iterative solution method. This article presents a geometric interpretation of its local convergence for the particular case of three points, with the solution constrained to be an interior point, which is fundamental to the present geometric interpretation. This constraint, on the other hand, implies that the weights associated to each point must obey triangle inequalities. The eigenvalues analysis is developed considering that all weights have the same value, which simplifies calculation and explanation, but the generalization of this analysis is straightforward, as commented in the text. Step-size scaling is also considered for accelerating the convergence rate. The accompanying eigenvalues analysis determines step-size multiplier ranges that ensure convergence. Moreover, the eigenvalues depend on a parameter that is computed based on the sample points configuration.Keywords
This publication has 11 references indexed in Scilit:
- Locational analysis: highlights of growth to maturityJournal of the Operational Research Society, 2009
- Linear and Nonlinear Programming2008
- Convex Optimization2004
- Further notes on convergence of the Weiszfeld algorithm2003
- Fundamentals of Convex Analysis2001
- The convergence of the Weiszfeld algorithmComputers & Mathematics with Applications, 2000
- Accelerating convergence in the Fermat–Weber location problemOperations Research Letters, 1998
- The Fermat—Weber location problem revisitedMathematical Programming, 1995
- The Weber problem revisitedComputers & Mathematics with Applications, 1981
- Location-Allocation ProblemsOperations Research, 1963