A geometric perspective of the Weiszfeld algorithm for solving the Fermat−Weber problem
Venceslau, Helder Manoel1, 2 ; Karam Venceslau, Marilis Bahr1, 3 ; Xavier, Adilson Elias1 ; Maculan, Nelson1
1 COPPE – PESC, Federal University of Rio de Janeiro, Cidade Universitária, Centro de Tecnologia, Bloco H, zip 21941-972, Rio de Janeiro − RJ, Brazil.
2 CEFET/RJ − Centro Federal de Educação Tecnológica Celso Suckow da Fonseca, Av. Maracanã, 229, Maracanã, zip 20271-110, Rio de Janeiro − RJ, Brazil.
3 Colégio Pedro II, Campo de São Cristóvão, 177, São Cristóvão, zip 20921-903, Rio de Janeiro − RJ, Brazil.
RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 1, pp. 157-173.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2015022
Classification : 90B85, 90C90
Mots-clés : Fermat−Weber problem, location problem, Weiszfeld algorithm, local convergence
Venceslau, Helder Manoel 1, 2 ; Karam Venceslau, Marilis Bahr 1, 3 ; Xavier, Adilson Elias 1 ; Maculan, Nelson 1

1 COPPE – PESC, Federal University of Rio de Janeiro, Cidade Universitária, Centro de Tecnologia, Bloco H, zip 21941-972, Rio de Janeiro − RJ, Brazil.
2 CEFET/RJ − Centro Federal de Educação Tecnológica Celso Suckow da Fonseca, Av. Maracanã, 229, Maracanã, zip 20271-110, Rio de Janeiro − RJ, Brazil.
3 Colégio Pedro II, Campo de São Cristóvão, 177, São Cristóvão, zip 20921-903, Rio de Janeiro − RJ, Brazil. 
@article{RO_2016__50_1_157_0,
     author = {Venceslau, Helder Manoel and Karam Venceslau, Marilis Bahr and Xavier, Adilson Elias and Maculan, Nelson},
     title = {A geometric perspective of the {Weiszfeld} algorithm for solving the {Fermat\ensuremath{-}Weber} problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {157--173},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {1},
     year = {2016},
     doi = {10.1051/ro/2015022},
     zbl = {1333.90076},
     mrnumber = {3460669},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2015022/}
}
TY  - JOUR
AU  - Venceslau, Helder Manoel
AU  - Karam Venceslau, Marilis Bahr
AU  - Xavier, Adilson Elias
AU  - Maculan, Nelson
TI  - A geometric perspective of the Weiszfeld algorithm for solving the Fermat−Weber problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 157
EP  - 173
VL  - 50
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2015022/
DO  - 10.1051/ro/2015022
LA  - en
ID  - RO_2016__50_1_157_0
ER  - 
%0 Journal Article
%A Venceslau, Helder Manoel
%A Karam Venceslau, Marilis Bahr
%A Xavier, Adilson Elias
%A Maculan, Nelson
%T A geometric perspective of the Weiszfeld algorithm for solving the Fermat−Weber problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 157-173
%V 50
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2015022/
%R 10.1051/ro/2015022
%G en
%F RO_2016__50_1_157_0
Venceslau, Helder Manoel; Karam Venceslau, Marilis Bahr; Xavier, Adilson Elias; Maculan, Nelson. A geometric perspective of the Weiszfeld algorithm for solving the Fermat−Weber problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 1, pp. 157-173. doi : 10.1051/ro/2015022. http://www.numdam.org/articles/10.1051/ro/2015022/

J. Brimberg, The Fermat−Weber location problem revisited. Math. Program. Ser. A 71 (1995) 71–76. | DOI | MR | Zbl

J. Brimberg, Further notes on convergence of the Weiszfeld algorithm. Yugoslav J. Oper. Res. 13 (2003) 199–206. | DOI | MR | Zbl

J. Brimberg, R. Chen and D. Chen, Accelerating convergence in the Fermat−Weber location problem. Oper. Res. Lett. 22 (1998) 151–157. | DOI | MR | Zbl

S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, Cambridge (2004). | MR | Zbl

L. Cooper, Location-allocation problems. Oper. Res. 11 (1963) 331–343. | DOI | MR | Zbl

L. Cooper and I. Katz, The Weber problem revisited. Comput. Math. Appl. 7 (1981) 225–234. | DOI | MR | Zbl

Z. Drezner, Facility Location: A Survey of Applications and Methods. Springer Ser. Oper. Res. Springer-Verlag, New York (1995). | MR | Zbl

Z Drezner and H.W. Hamacher, Facility Location: Applications and Theory. Springer, Berlin (2004). | MR | Zbl

J.B. Hiriart-Urruty and C. Lemarechal, Fundamentals of Convex Analysis. Springer, Berlin (2001). | MR | Zbl

H. Üster and R.F. Love, The convergence of the Weiszfeld algorithm. Comput. Math. Appl. 40 (2000) 443–451. | DOI | MR | Zbl

D.G. Luenberger, Y. Ye, Linear and Nonlinear Programming, third edn. Springer, New York (2008). | MR | Zbl

H.K. Smith, G. Laporte and P.R. Harper, Locational analysis: highlights of growth to maturity. J. Oper.Res. Soc. 60 (2009) 140–148. | DOI | Zbl

E. Weiszfeld, Sur le point par lequel la somme des distances de n points donnés est minimum. Tohoku Math. J. 43 (1937) 355–386. | JFM | Zbl

G.O. Wesolowsky, The Weber problem: history and perspectives. Location Sci. 1 (1993) 5–23. | Zbl

Cité par Sources :