Weiszfeld's method: old and new results
From MaRDI portal
Publication:2260646
Research exposition (monographs, survey articles) pertaining to calculus of variations and optimal control (49-02) Numerical methods based on nonlinear programming (49M37) Numerical mathematical programming methods (65K05) Convex programming (90C25) Mathematical programming (educational aspects) (97N60)
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.
Recommendations
Cites work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A generalized Weiszfeld method for the multi-facility location problem
- A least-squares-based method for a class of nonsmooth minimization problems with applications in plasticity
- A modified Weiszfeld algorithm for the Fermat-Weber location problem
- A note on accelerating the weiszfeld procedure
- A note on Fermat's problem
- A note on the Weber location problem
- A projected newton method forl p norm location problems
- A quadratically convergent method for minimizing a sum of euclidean norms
- A Weiszfeld algorithm for the solution of an asymmetric extension of the generalized Fermat location problem
- An Efficient Primal-Dual Interior-Point Method for Minimizing a Sum of Euclidean Norms
- Convergence of the Weiszfeld Algorithm for Weber Problems Using a Generalized “Distance” Function
- Geometric methods and optimization problems
- scientific article; zbMATH DE number 1803754 (Why is no real title available?)
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 5957421 (Why is no real title available?)
- scientific article; zbMATH DE number 4164577 (Why is no real title available?)
- scientific article; zbMATH DE number 3914081 (Why is no real title available?)
- scientific article; zbMATH DE number 3595804 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1023238 (Why is no real title available?)
- scientific article; zbMATH DE number 4119957 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- Iterative Minimization Schemes for Solving the Single Source Localization Problem
- Iteratively reweighted least squares minimization for sparse recovery
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Link-Length Minimization in Networks
- Local convergence in Fermat's problem
- Location-Allocation Problems
- Nonlinear Programming
- On the Convergence of a Class of Iterative Methods for Solving the Weber Location Problem
- On the convergence of the Weiszfeld algorithm
- On the point for which the sum of the distances to n given points is minimum
- Open questions concerning Weiszfeld's algorithm for the Fermat-Weber location problem
- Pioneering Developments in Location Analysis
- Proximité et dualité dans un espace hilbertien
- Robust Regression Computation Using Iteratively Reweighted Least Squares
- Robust Statistics
- Smooth minimization of non-smooth functions
- Smoothing and first order methods: a unified framework
- Solution of location problems with radial cost functions
- The Euclidean Multifacility Location Problem
- The Fermat-Torricelli problem. I: A discrete gradient-method approach
- The Fermat-Weber location problem revisited
- The Fitting of Power Series, Meaning Polynomials, Illustrated on Band-Spectroscopic Data
- The Lawson Algorithm and Extensions
Cited in
(37)- On the point for which the sum of the distances to n given points is minimum
- On the geometric median of convex, triangular and other polygonal domains
- Proximal algorithms in statistics and machine learning
- Levels of nonoptimality of the Weiszfeld algorithm in the least-modules method
- On the robust PCA and Weiszfeld's algorithm
- Robust PCA via regularized \textsc{Reaper} with a matrix-free proximal algorithm
- New convergence results for inertial Krasnoselskii-Mann iterations in Hilbert spaces with applications
- Accelerated modified inertial Mann and viscosity algorithms to find a fixed point of -inverse strongly monotone operators
- Concentration study of M-estimators using the influence function
- On the rotational invariant \(L_1\)-norm PCA
- Using the power of ideal solutions: simple proofs of some old and new results in location theory
- Generalized Krasnoselskii-Mann-type iterations for nonexpansive mappings in Hilbert spaces
- The optimal solution set of the multi-source Weber problem
- Eigenvalue localization under partial spectral information
- The generalized Fermat-Torricelli problem in Hilbert spaces
- Estimating the geometric median in Hilbert spaces with stochastic gradient algorithms: L^p and almost sure rates of convergence
- Simple approximative algorithms for free-support Wasserstein barycenters
- On Newton's method for the Fermat-Weber location problem
- New Interpretation and Generalization of the Kameda-Weiner Method.
- Robust and scalable Bayes via a median of subset posterior measures
- A PROBABILISTIC ℓ1 METHOD FOR CLUSTERING HIGH-DIMENSIONAL DATA
- Probabilistic smallest enclosing ball in high dimensions via subgradient sampling
- On a projected Weiszfeld algorithm
- Online stochastic Newton methods for estimating the geometric median and applications
- The geometric median and applications to robust mean estimation
- Robust regression techniques for multiple method comparison and transformation
- Further analysis of the Weber problem
- Qualitative properties of k-center problems
- Reviewing extensions and solution methods of the planar Weber single facility location problem
- Local solutions of the multi-source Weber problem
- Fifty years of location theory -- a selective review
- Bearing-only solution for Fermat-Weber location problem: generalized algorithms
- On the probability that the optimal solution of the Weber location problem is at a demand point
- Online and offline robust multivariate linear regression
- The Fermat-Torricelli problem revisited
- Geometric medians on product manifolds
- An adaptive proximal safeguarded augmented Lagrangian method for nonsmooth DC problems with convex constraints
This page was built for publication: Weiszfeld's method: old and new results
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2260646)
