Weiszfelds Method: Old and New Results
In 1937, the 16-years-old Hungarian mathematician Endre Weiszfeld, in a seminal paper, devised a method for solving the FermatWeber location problema problem whose origins can be traced back to the seventeenth century. Weiszfelds method stirred up an enormous amount of research in the optimization and location communities, and is also being discussed and used till these days. In this paper, we review both the past and the ongoing research on Weiszfeds method. The existing results are presented in a self-contained and concise mannersome are derived by new and simplified techniques. We also establish two new results using modern tools of optimization. First, we establish a non-asymptotic sublinear rate of convergence of Weiszfelds method, and second, using an exact smoothing technique, we present a modification of the method with a proven better rate of convergence.
weiszfelds method complexity analysis fermatweber problem gradient method localization theory 49-02 90c25 90c30 90-02 65k05 97n60