Open questions concerning Weiszfeld's algorithm for the Fermat-Weber location problem

The Fermat—Weber location problem is to find a point in ⁿ that minimizes the sum of the weighted Euclidean distances fromm given points in ⁿ . A popular iterative solution method for this problem was first introduced by Weiszfeld in 1937. In 1973 Kuhn claimed that if them given points are not collinear then for all but a denumerable number of starting points the sequence of iterates generated by Weiszfeld's scheme converges to the unique optimal solution. We demonstrate that Kuhn's convergence theorem is not always correct. We then conjecture that if this algorithm is initiated at the affine subspace spanned by them given points, the convergence is ensured for all but a denumerable number of starting points.     

New models for locating a moving service facility

In this paper we analyze a new location problem which is a generalization of the well-known single facility location model. This extension consists of introducing a general objective function and replacing fixed locations by trajectories. We prove that the problem is well-stated and solvable. A Weiszfeld type algorithm is proposed to solve this generalized dynamic single facility location problem on L ^p spaces of functions, with p ∈(1,2]. We prove global convergence of our algorithm once we have assumed that the set of demand functions and the initial step function belong to a subspace of L ^p called Sobolev space. Finally, examples are included illustrating the application of the model to generalized regression analysis and the convergence of the proposed algorithm. The examples also show that the pointwise extension of the algorithm does not have to converge to an optimal solution of the considered problem while the proposed algorithm does.     

On the global convergence of a generalized iterative procedure for the minisum location problem with ℓ p distances for p > 2

This paper presents a procedure to solve the classical location median problem where the distances are measured with ? _p -norms with p > 2. In order to do that we consider an approximated problem. The global convergence of the sequence generated by this iterative scheme is proved. Therefore, this paper closes the still open question of giving a modification of the Weiszfeld algorithm that converges to an optimal solution of the median problem with ? _p norms and ${p \in (2, \infty)}$ . The paper ends with a computational analysis of the different provided iterative schemes.     

The Fermat—Weber location problem revisited

The Fermat—Weber location problem requires finding a point in ^N that minimizes the sum of weighted Euclidean distances tom given points. A one-point iterative method was first introduced by Weiszfeld in 1937 to solve this problem. Since then several research articles have been published on the method and generalizations thereof. Global convergence of Weiszfeld's algorithm was proven in a seminal paper by Kuhn in 1973. However, since them given points are singular points of the iteration functions, convergence is conditional on none of the iterates coinciding with one of the given points. In addressing this problem, Kuhn concluded that whenever them given points are not collinear, Weiszfeld's algorithm will converge to the unique optimal solution except for a denumerable set of starting points. As late as 1989, Chandrasekaran and Tamir demonstrated with counter-examples that convergence may not occur for continuous sets of starting points when the given points are contained in an affine subspace of ^N . We resolve this open question by proving that Weiszfeld's algorithm converges to the unique optimal solution for all but a denumerable set of starting points if, and only if, the convex hull of the given points is of dimensionN.     

Algebraic optimization: The Fermat-Weber location problem

The Fermat-Weber location problem is to find a point in ⁿ that minimizes the sum of the (weighted) Euclidean distances fromm given points in ⁿ . In this work we discuss some relevant complexity and algorithmic issues. First, using Tarski's theory on solvability over real closed fields we argue that there is an infinite scheme to solve the problem, where the rate of convergence is equal to the rate of the best method to locate a real algebraic root of a one-dimensional polynomial. Secondly, we exhibit an explicit solution to the strong separation problem associated with the Fermat-Weber model. This separation result shows that an-approximation solution can be constructed in polynomial time using the standard Ellipsoid Method.     

A Newton Acceleration of the Weiszfeld Algorithm for Minimizing the Sum of Euclidean Distances

The Weiszfeld algorithm for continuous location problems can be considered as an iteratively reweighted least squares method. It generally exhibits linear convergence. In this paper, a Newton algorithm with similar simplicity is proposed to solve a continuous multifacility location problem with the Euclidean distance measure. Similar to the Weiszfeld algorithm, the main computation can be solving a weighted least squares problem at each iteration. A Cholesky factorization of a symmetric positive definite band matrix, typically with a small band width (e.g., a band width of two for a Euclidean location problem on a plane) is performed. 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 suggests that the proposed algorithm often performs well in the absence of the linear independence or strict complementarity assumption. In addition, the proposed algorithm is proven to be globally convergent under similar assumptions for the Weiszfeld algorithm. Although local convergence analysis is still under investigation, computation results suggest that it is typically superlinearly convergent.     

On the convergence of the generalized Weiszfeld algorithm

In this paper we consider Weber-like location problems. The objective function is a sum of terms, each a function of the Euclidean distance from a demand point. We prove that a Weiszfeld-like iterative procedure for the solution of such problems converges to a local minimum (or a saddle point) when three conditions are met. Many location problems can be solved by the generalized Weiszfeld algorithm. There are many problem instances for which convergence is observed empirically. The proof in this paper shows that many of these algorithms indeed converge.     

Accelerating the convergence in the single-source and multi-source Weber problems

The modified Weiszfeld method [Y. Vardi, C.H. Zhang, A modified Weiszfeld algorithm for the Fermat-Weber location problem, Mathematical Programming 90 (2001) 559-566] is perhaps the most widely-used algorithm for the single-source Weber problem (SWP). In this paper, in order to accelerate the efficiency for solving SWP, a new numerical method, called Weiszfeld-Newton method, is developed by combining the modified Weiszfeld method with the well-known Newton method. Global convergence of the new Weiszfeld-Newton method is proved under mild assumptions. For the multi-source Weber problem (MWP), a new location-allocation heuristic, Cooper-Weiszfeld-Newton method, is presented in the spirit of Cooper algorithm [L. Cooper, Heuristic methods for location-allocation problems, SIAM Review 6 (1964) 37-53], using the new Weiszfeld-Newton method in the location phase to locate facilities and adopting the nearest center reclassification algorithm (NCRA) in the allocation phase to allocate the customers. Preliminary numerical results are reported to verify the evident effectiveness of Weiszfeld-Newton method for SWP and Cooper-Weiszfeld-Newton method for MWP.     

Finding the optimal solution to the Huff based competitive location model

In this paper we solve the gravity (Huff) model for the competitive facility location problem. We show that the generalized Weiszfeld procedure converges to a local maximum or a saddle point. We also devise a global optimization procedure that finds the optimal solution within a given accuracy. This procedure is very efficient and finds the optimal solution for 10,000 demand points in less than six minutes of computer time. We also experimented with the generalized Weiszfeld algorithm on the same set of randomly generated problems. We repeated the algorithm from 1,000 different starting solutions and the optimum was obtained at least 17 times for all problems.     

On the convergence of the Weiszfeld algorithm

In this work we analyze the paper “Brimberg, J. (1995): The Fermat-Weber location problem revisited. Mathematical Programming 71, 71–76” which claims to close the question on the conjecture posed by Chandrasekaran and Tamir in 1989 on the convergence of the Weiszfeld algorithm. Some counterexamples are shown to the proofs showed in Brimberg’s paper. Received: January 1999 / Accepted: December 2001?Published online April 12, 2002 RID="*" ID="*"Partially supported by PB/11/FS/97 of Fundación Séneca of the Comunidad Autónoma de la Región de Murcia RID="**" ID="**"Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica (I+I+D), project TIC2000-1750-C06-06 RID="*" RID="**"     

The <Emphasis Type="Italic">p</Emphasis>-Centre Problem—Heuristic and Optimal Algorithms

The p-centre problem, or minimax location-allocation problem in location theory terminology, is the following: given n demand points on the plane and a weight associated with each demand point, find p new facilities on the plane that minimize the maximum weighted Euclidean distance between each demand point and its closest new facility. We present two heuristics and an optimal algorithm that solves the problem for a given p in time polynomial in n. Computational results are presented.     

Proximity Function Minimization Using Multiple Bregman Projections, with Applications to Split Feasibility and Kullback–Leibler Distance Minimization

Problems in signal detection and image recovery can sometimes be formulated as a convex feasibility problem (CFP) of finding a vector in the intersection of a finite family of closed convex sets. Algorithms for this purpose typically employ orthogonal or generalized projections onto the individual convex sets. The simultaneous multiprojection algorithm of Censor and Elfving for solving the CFP, in which different generalized projections may be used at the same time, has been shown to converge for the case of nonempty intersection; still open is the question of its convergence when the intersection of the closed convex sets is empty.Motivated by the geometric alternating minimization approach of Csiszár and Tusnády and the product space formulation of Pierra, we derive a new simultaneous multiprojection algorithm that employs generalized projections of Bregman to solve the convex feasibility problem or, in the inconsistent case, to minimize a proximity function that measures the average distance from a point to all convex sets. We assume that the Bregman distances involved are jointly convex, so that the proximity function itself is convex. When the intersection of the convex sets is empty, but the closure of the proximity function has a unique global minimizer, the sequence of iterates converges to this unique minimizer. Special cases of this algorithm include the Expectation Maximization Maximum Likelihood (EMML) method in emission tomography and a new convergence result for an algorithm that solves the split feasibility problem.     

Approximation Algorithms for Pick-and-Place Robots

In this paper we study the problem of finding placement tours for pick-and-place robots, also known as the printed circuit board assembly problem with m positions on a board, n bins containing m components and n locations for the bins. In the standard model where the working time of the robot is proportional to the distances travelled, the general problem appears as a combination of the travelling salesman problem and the matching problem, and for m=n we have an Euclidean, bipartite travelling salesman problem. We give a polynomial-time algorithm which achieves an approximation guarantee of 3+. An important special instance of the problem is the case of a fixed assignment of bins to bin-locations. This appears as a special case of a bipartite TSP satisfying the quadrangle inequality and given some fixed matching arcs. We obtain a 1.8 factor approximation with the stacker crane algorithm of Frederikson, Hecht and Kim. For the general bipartite case we also show a 2.0 factor approximation algorithm which is based on a new insertion technique for bipartite TSPs with quadrangle inequality. Implementations and experiments on real-world as well as random point configurations conclude this paper.     

Duality theorem for a generalized Fermat-Weber problem

The classical Fermat-Weber problem is to minimize the sum of the distances from a point in a plane tok given points in the plane. This problem was generalized by Witzgall ton-dimensional space and to allow for a general norm, not necessarily symmetric; he found a dual for this problem. The authors generalize this result further by proving a duality theorem which includes as special cases a great variety of choices of norms in the terms of the Fermat-Weber sum. The theorem is proved by applying a general duality theorem of Rockafellar. As applications, a dual is found for the multi-facility location problem and a nonlinear dual is obtained for a linear programming problem with a priori bounds for the variables. When the norms concerned are continuously differentiable, formulas are obtained for retrieving the solution for each primal problem from the solution of its dual.     

Convergence of Greedy Algorithms in Banach Spaces

We study the convergence of greedy algorithms in Banach spaces. We construct an example of a smooth Banach space, where the X-greedy algorithm converges not for all dictionaries and initial vectors. We also study the R-greedy algorithm, which, along with the X-greedy algorithm, is a generalization of the simple greedy algorithm in Hilbert space. We prove its convergence for a certain class of Banach spaces. In particular, this class contains, the spaces ^p,p 2.     

Minmax p-Traveling Salesmen Location Problems on a Tree

Suppose that p traveling salesmen must visit together all points of a tree, and the objective is to minimize the maximum of the lengths of their tours. The location–allocation version of the problem (where both optimal home locations of the salesmen and their optimal tours must be found) is known to be NP-hard for any p2. We present exact polynomial algorithms with a linear order of complexity for location versions of the problem (where only optimal home locations must be found, without the corresponding tours) for the cases p=2 and p=3.     

An extension of the proximal point algorithm with Bregman distances on Hadamard manifolds

In this paper we present an extension of the proximal point algorithm with Bregman distances to solve constrained minimization problems with quasiconvex and convex objective function on Hadamard manifolds. The proposed algorithm is a modified and extended version of the one presented in Papa Quiroz and Oliveira (J Convex Anal 16(1): 49–69, 2009). An advantage of the proposed algorithm, for the nonconvex case, is that in each iteration the algorithm only needs to find a stationary point of the proximal function and not a global minimum. For that reason, from the computational point of view, the proposed algorithm is more practical than the earlier proximal method. Another advantage, for the convex case, is that using minimal condition on the problem data as well as on the proximal parameters we get the same convergence results of the Euclidean proximal algorithm using Bregman distances.     

Applications of Variational Analysis to a Generalized Fermat-Torricelli Problem

In this paper we develop new applications of variational analysis and generalized differentiation to the following optimization problem and its specifications: given n closed subsets of a Banach space, find such a point for which the sum of its distances to these sets is minimal. This problem can be viewed as an extension of the celebrated Fermat-Torricelli problem: given three points on the plane, find another point that minimizes the sum of its distances to the designated points. The generalized Fermat-Torricelli problem formulated and studied in this paper is of undoubted mathematical interest and is promising for various applications including those frequently arising in location science, optimal networks, etc. Based on advanced tools and recent results of variational analysis and generalized differentiation, we derive necessary as well as necessary and sufficient optimality conditions for the extended version of the Fermat-Torricelli problem under consideration, which allow us to completely solve it in some important settings. Furthermore, we develop and justify a numerical algorithm of the subgradient type to find optimal solutions in convex settings and provide its numerical implementations.     

Optimal solution of nonlinear equations satisfying a Lipschitz condition

Summary For a given nonnegative we seek a pointx ^* such that |f(x ^*)| wheref is a nonlinear transformation of the cubeB=[0,1] ^m into (or ^p ,p>1) satisfying a Lipschitz condition with the constantK and having a zero inB.The information operator onf consists ofn values of arbitrary linear functionals which are computed adaptively. The pointx ^* is constructed by means of an algorithm which is a mapping depending on the information operator. We find an optimal algorithm, i.e., algorithm with the smallest error, which usesn function evaluations computed adaptively. We also exhibit nearly optimal information operators, i.e., the linear functionals for which the error of an optimal algorithm that uses them is almost minimal. Nearly optimal information operators consists ofn nonadaptive function evaluations at equispaced pointsx _j in the cubeB. This result exhibits the superiority of the T. Aird and J. Rice procedure ZSRCH (IMSL library [1]) over Sobol's approach [7] for solving nonlinear equations in our class of functions. We also prove that the simple search algorithm which yields a pointx ^*=x _k such that is nearly optimal. The complexity, i.e., the minimal cost of solving our problem is roughly equal to (K/) ^m .