tailieunhanh - Further notes on convergence of the weiszfeld algorithm

The Fermat-Weber problem is one of the most widely studied problems in classical location theory. In his previous work, Brimberg (1995) attempts to resolve a conjecture posed by Chandrasekaran and Tamir (1989) on a convergence property of the Weiszfeld algorithm, a well-known iterative procedure used to solve this problem. | Yugoslav Journal of Operations Research 13 (2003), Number 2, 199-206 FURTHER NOTES ON CONVERGENCE OF THE WEISZFELD ALGORITHM Jack BRIMBERG Department of Business Administration Royal Military College of Canada Kingston, Ontario, Canada and GERAD, 3000, chemin de la CÚte-Sainte-Catherine Montr›al, Qu›bec Canada H3T 2A7 Abstract: The Fermat-Weber problem is one of the most widely studied problems in classical location theory. In his previous work, Brimberg (1995) attempts to resolve a conjecture posed by Chandrasekaran and Tamir (1989) on a convergence property of the Weiszfeld algorithm, a well-known iterative procedure used to solve this problem. More recently, C‹novas, MarÐn and Caflavate (2002) provide counterexamples that appear to reopen the question. However, they do not attempt to reconcile their counterexamples with the previous work. We now show that in the light of these counterexamples, the proof is readily modified and the conjecture of Chandrasekaran and Tamir reclosed. Keywords: Fermat-Weber problem, minisum location, Weiszfeld algorithm. 1. INTRODUCTION The Fermat-Weber problem, also referred to as the continuous single facility location problem, requires finding a point in space that minimizes the sum of weighted Euclidean distances to m given (or fixed) points. This problem is a cornerstone of classical location theory, and forms the basis of many other more advanced models. For an entertaining account of its long history, the reader is referred to Wesolowsky [8]; also see Love, Morris and Wesolowsky [7]. One aspect of the Fermat-Weber problem that has puzzled researchers for some time relates to the convergence of the Weiszfeld algorithm. It is well known that the sequence of points, { x q ; q = 0, 1,.}, generated by the algorithm converges to the 200 J. Brimberg / Further Notes on Convergence of the Weiszfeld Algorithm optimal solution provided that no iterate coincides with one of the fixed points. In such an eventuality, the iteration .