dc.contributor.author Li, Yuying en_US dc.date.accessioned 2007-04-04T16:14:17Z dc.date.available 2007-04-04T16:14:17Z dc.date.issued 1995-11 en_US dc.identifier.citation http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.tc/95-224 en_US dc.identifier.uri https://hdl.handle.net/1813/5559 dc.description.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. en_US dc.format.extent 231463 bytes dc.format.extent 181807 bytes dc.format.mimetype application/pdf dc.format.mimetype application/postscript dc.language.iso en_US en_US dc.publisher Cornell University en_US dc.subject theory center en_US dc.subject location problem en_US dc.subject Euclidean distance en_US dc.subject Weiszfeld method en_US dc.subject Newton method en_US dc.title A Newton Acceleration of the Weiszfeld Algorithm for Minimizing the Sum of Euclidean Distances en_US dc.type technical report en_US
﻿