Weiszfeld's method: old and new results (Q2260646)

The paper is devoted to convergence properties of Weiszfeld's method, which is treated as a fixed-point or gradient method for minimization of the weighted distance to a set of given points \(A=\{a^{1}, \ldots,a^{m} \}\) in some space. It is called the Fermat-Weber problem. It is known that the method possesses a monotone convergence, but may fail at a point of \(A\), since the cost function is non-differentiable. The authors describe modifications avoiding these points. They show that the convergence rate of the method is \(O(1/k)\), but that utilization of a smooth equivalent problem together with Nesterov's fast gradient method allows them to obtain the estimate \(O(1/k^{2})\) for this version. The exposition contains also historical notes and some related results.