Skip to main content


eCommons@Cornell

eCommons@Cornell >
Faculty of Computing and Information Science >
Center for Advance Computing >
Cornell Theory Center Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/5559
Title: A Newton Acceleration of the Weiszfeld Algorithm for Minimizing the Sum of Euclidean Distances
Authors: Li, Yuying
Keywords: theory center
location problem
Euclidean distance
Weiszfeld method
Newton method
Issue Date: Nov-1995
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.tc/95-224
Abstract: The Weiszfeld algorithm for continuous location problems can be considered as an iteratively reweighted least squares method. It exhibits linear convergence. In this paper, a Newton type algorithm with similar simplicity is proposed to solve a continuous multifacility location problem with Euclidean distance measure. Similar to the Weiszfeld algorithm, at each iteration the main computation can be solving a weighted least squares problem. A Cholesky factorization of a symmetric positive definite band matrix, typically with a relatively small band width (e.g., a band width of two for a Euclidean location problem on a plane) is required. This new algorithm can be regarded as a Newton acceleration to the Weiszfeld algorithm with fast global and local convergence. The simplicity and efficiency of the proposed algorithm makes it particularly suitable for large-scale Euclidean location problems and parallel implementation. Computational experience also suggests that the proposed algorithm performs remarkably well in the presence of degeneracy and near degeneracy. In addition, it is proven to be globally convergent. Although the local convergence analysis is still under investigation, computation results suggest that it is typically superlinearly convergent.
URI: http://hdl.handle.net/1813/5559
Appears in Collections:Cornell Theory Center Technical Reports

Files in This Item:

File Description SizeFormat
95-224.pdf226.04 kBAdobe PDFView/Open
95-224.ps177.55 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us